Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Junktorbasen

Gibt es Sprachen in denen es ein Wort für die Scheffer-Strich oder Peirce-Pfeil Verknüpfung von Aussagen gibt? Jedenfalls haben alle mir bekannten Sprachen Worte für "", "", "", "" 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:

Weiter zur Booleschen Algebra ...
Erich Prisner
File partially translated from TEX by T TH, version 2.53.
erstellt im Februar 2000.