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 = a¯a, sowie a Ù b = Ø(Øa Ú Øb) = Øa ¯ Øb = (a¯a) ¯ (b¯b). ) 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: |