Erzeugendensysteme in der Aussagenlogik

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

Darstellung mit ++ und ⋅\cdot

Diese wird durch folgende Ersetzungsreglungen klar.
¬a=a+1\not a = a+1
a∧b=a⋅ba \and b = a\cdot b
a∨b=a⋅b+a+ba \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 ¬\not und   ⟹  \follows

Auch die Negation und die Implikation reichen zur Erzeugung aller Operationen aus, was aus der Beziehung a∨b=(a  ⟹  b)  ⟹  ba \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 ◊\nand verwenden wollen, ist folgendermaßen definiert: ◊=¬(a∧b)\nand= \not(a \and b)
Der Name leitet sich aus dem Englischen von "not and" her.
Man verifiziert leicht, dass ¬a=a◊a\not a = a \nand a und a∨b=(a◊a)◊(b◊b)a\or b = (a\nand a)\nand(b\nand b).

Die Mathematik muß man schon deswegen studieren, weil sie die Gedanken ordnet.

M. W. Lomonossow

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е
Datenschutzerklärung

 

Logik