Erzeugendensysteme in der Aussagenlogik

Der Darstellung der zweistelligen logischen Operationen entnimmt man sofort, dass sich alle Operationen vermittels \(\displaystyle \not\), \(\displaystyle \and\) und \(\displaystyle \or\) erzeugen lassen. Wegen der DeMorganschen Regeln kann man wahlweise \(\displaystyle \and\) gegen \(\displaystyle \or\) austauschen. Damit gilt:
Jede zweistellige logische Operation lässt sich mittels \(\displaystyle \not\) und \(\displaystyle \and\) oder mittels \(\displaystyle \not\) und \(\displaystyle \or\) darstellen.
Die Junktoren \(\displaystyle \and\) und \(\displaystyle \or\) reichen allein nicht aus, denn \(\displaystyle a\and a=a \or a= a\) und damit liefert jede Verknüpfung bestehend nur aus \(\displaystyle \and\) und \(\displaystyle \or\), die auf \(\displaystyle a\) angewendet wird wieder \(\displaystyle a\) und niemals \(\displaystyle \not a\).
 
 

Darstellung mit \(\displaystyle +\) und \(\displaystyle \cdot\)

Diese wird durch folgende Ersetzungsreglungen klar.
\(\displaystyle \not a = a+1\)
\(\displaystyle a \and b = a\cdot b\)
\(\displaystyle a \or b = a\cdot b+a+b\)
Dieses System hat den Vorteil, dass es "algebraisch" ist; man kann also logische Zusammenhänge durch reines Zahlenrechnen erhalten. Der Nachteil ist, dass es uns weniger intuitiv erscheint.

Darstellung mit \(\displaystyle \not\) und \(\displaystyle \follows\)

Auch die Negation und die Implikation reichen zur Erzeugung aller Operationen aus, was aus der Beziehung \(\displaystyle a \or b=(a\follows b) \follows b\) unmittelbar ersichtlich ist.
Bisher benötigten wir immer zwei Operationen, um die anderen Operationen zu erzeugen. Es stellt sich sofort die Frage, ob dies notwendigerweise so ist, oder ob auch eine Operation ausreichen würde. Und tatsächlich:

Darstellung mit nand

Die Operation nand, für die wir das Symbol \(\displaystyle \nand\) verwenden wollen, ist folgendermaßen definiert: \(\displaystyle \nand= \not(a \and b)\)
Der Name leitet sich aus dem Englischen von "not and" her.
Man verifiziert leicht, dass \(\displaystyle \not a = a \nand a\) und \(\displaystyle a\or b = (a\nand a)\nand(b\nand b)\).

Scherzhafte Beispiele haben manchmal größere Bedeutung als ernste.

Michael Stifel

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе