",
"
", "
"
und "
".
Können wir damit jede n-stellige Verknüpfung auf {w,f}
ausdrücken?
Und wenn ja, sind alle diese Worte wirklich dazu notwendig?
Satz von Post (1921):
Jede n-stellige Verknüpfung auf {w,f} läßt sich
mittels den binären Verknüpfungen
"¬", "" und
"" ausdrücken.
|
|
Beweis: Nach den
obigen Überlegungen können
wir jede nicht kontradiktorische n-stellige Verknüpfung h auf {w,f}
auf kanonische disjunktive Normalform bringen.
Ist h kontradiktorisch, so können wir sie auf
kanonische konjunktive Normalform bringen.
Diese Normalformen benutzen nur "¬",
"" und "".
|
Offenbar können wir wegen den
de Morganschen Regeln sogar auf
eins von "" und ""
verzichten
(Versuchen Sie mal einen Tag ohne das Wort "und" auszukommen.
Es ist zwar mühsam, aber es geht.)
Solche Mengen von Verknüpfungen, mit denen man
alle n-stelligen Verknüpfungen auf {w,f} außer
Tautologien und Kontradiktionen erzeugen kann, heißen
Junktorbasen.
Weil sich jedes "¬" und ""
durch "|" ersetzen läßt (aber auch durch "
")
(¬a =
¬a ¬a = a|a, sowie
a b = ¬(a|b) =(a|b)|(a|b),
und ziemlich ähnlich
¬ a = ¬a
¬a = aa, sowie
a b = ¬(¬a
¬b) =
¬a
¬b = (aa)
(bb).
)
genügt auch "|" allein (bzw. ""allein).
|
{,,
¬},
{,¬},
{,¬},
{|}, sowie
{} sind Junktorbasen.
|
Auf "nicht" kann man aber nicht verzichten (falls man ansonsten nur "und" und "oder" verwendet).
|
{,} ist keine
Junktorbasis.
Beweis: |