Peirce-Funktion

aus Wikipedia, der freien Enzyklopädie

Die Peirce-Funktion (Nicht-Oder, NOR-Funktion) ist nach dem amerikanischen Philosophen, Logiker und Mathematiker Charles S. Peirce benannt. Es handelt sich um eine Wahrheitsfunktion in der zweiwertigen Logik, die dem Ausdruck „weder A noch B“ und damit der verneinten Disjunktion „nicht (A oder B)“ beziehungsweise der Konjunktion „nicht A und nicht B“ entspricht.

In der formalen Schreibweise wird die Peirce-Funktion oft mit „NOR“ (not-or) oder dem Zeichen $\downarrow$ dargestellt. Die Peirce-Funktion ist eine Boolesche Funktion mit folgender Definition: NOR(x,y)=1 wenn sowohl x=0 als auch y=0; NOR(x,y)=0 andernfalls. Die Funktion ist nicht assoziativ, das heißt (a NOR b) NOR c ist nicht äquivalent zu a NOR (b NOR c).

Die folgende Wahrheitstabelle zeigt den Wahrheitswertverlauf der Peirce-Funktion:

x	y	$x \downarrow y$
0	0	1
0	1	0
1	0	0
1	1	0

Mit der Peirce-Funktion allein sind alle zweiwertigen Wahrheitsfunktionen darstellbar, das heißt jede boolesche Funktion ist äquivalent mit einer Formel, die ausschließlich die NOR-Funktion enthält. Auf Grund dieser Eigenschaft der funktionalen Vollständigkeit nennt man die Peirce-Funktion eine Basis der zweistelligen logischen Funktionen (eine weitere Basis ist die NAND-Funktion).

Negation: $\neg$ a = a $\downarrow$ a
Disjunktion: a $\vee$ b = (a $\downarrow$ b) $\downarrow$ (a $\downarrow$ b)
Konjunktion:a $\wedge$ b = (a $\downarrow$ a) $\downarrow$ (b $\downarrow$ b)