Sheffer-Schlaganfall - Sheffer stroke

Sheffer-Schlaganfall

NAND
Definition	${\displaystyle {\overline {x\cdot y}}}$
Wahrheitstabelle	${\displaystyle (1110)}$
Logikgatter
Normalformen
Disjunktiv	${\displaystyle {\overline {x}}+{\overline {y}}}$
Konjunktiv	${\displaystyle {\overline {x}}+{\overline {y}}}$
Zhegalkin-Polynom	${\displaystyle 1\oplus xy}$
Gitter der Post
0-erhaltend	Nein
1-konservierend	Nein
Monoton	Nein
Affin	Nein
v T e

In Booleschen Funktionen und Aussagenkalkül bezeichnet der Sheffer-Strich eine logische Operation , die der Negation der Konjunktionsoperation entspricht , die in der gewöhnlichen Sprache als "nicht beides" ausgedrückt wird. Es wird auch nand ("nicht und") oder die alternative Verweigerung genannt , da es tatsächlich sagt, dass mindestens einer seiner Operanden falsch ist. In der Digitalelektronik entspricht es dem NAND-Gatter . Es ist nach Henry M. Sheffer benannt und wird als ↑ oder als | . geschrieben (aber nicht als ||, oft verwendet, um Disjunktion darzustellen ). In der Bocheński-Notation kann es als D pq geschrieben werden .

Sein Dual ist der NOR-Operator (auch bekannt als Peirce- Pfeil oder Quine- Dolch). Wie sein duales System kann NAND allein, ohne einen anderen logischen Operator, verwendet werden, um ein logisches formales System zu bilden (wodurch NAND funktional vollständig wird ). Diese Eigenschaft macht das NAND-Gatter für die moderne digitale Elektronik entscheidend , einschließlich seiner Verwendung im Computerprozessordesign .

Definition

Die NAND-Operation ist eine logische Operation mit zwei logischen Werten . Sie erzeugt den Wert wahr, wenn – und nur wenn – mindestens eine der Aussagen falsch ist.

Wahrheitstabelle

Die Wahrheitstabelle von (auch geschrieben als , oder D pq ) ist wie folgt ${\displaystyle P\uparrow Q}$${\displaystyle P\mathop {|} Q}$

${\displaystyle P}$	${\displaystyle Q}$	${\displaystyle P\uparrow Q}$
T	T	F
T	F	T
F	T	T
F	F	T

Logische Äquivalenzen

Der Sheffer-Strich von und ist die Negation ihrer Konjunktion ${\displaystyle P}$${\displaystyle Q}$

${\displaystyle P\uparrow Q}$	${\displaystyle \Leftrightarrow}$	${\displaystyle\neg (P\land Q)}$
	${\displaystyle \Leftrightarrow}$	${\displaystyle \neg}$

Nach den Gesetzen von De Morgan ist dies auch gleichbedeutend mit der Disjunktion der Negationen von und${\displaystyle P}$${\displaystyle Q}$

${\displaystyle P\uparrow Q}$	${\displaystyle \Leftrightarrow}$	${\displaystyle \neg P}$	${\displaystyle \lor}$	${\displaystyle \neg Q}$
	${\displaystyle \Leftrightarrow}$		${\displaystyle \lor}$

Geschichte

Der Strich ist nach Henry M. Sheffer benannt , der 1913 in den Transactions of the American Mathematical Society ein Papier veröffentlichte, das eine Axiomatisierung von Booleschen Algebren unter Verwendung des Strichs lieferte , und seine Äquivalenz zu einer Standardformulierung davon von Huntington unter Verwendung der bekannten Operatoren von . bewies Aussagenlogik ( und , oder , nicht ). Wegen der Selbstdualität von Booleschen Algebren gelten die Sheffer-Axiome gleichermaßen für NAND- oder NOR-Operationen anstelle des Strichs. Sheffer interpretierte den Strich in seiner Arbeit als Zeichen für die Nicht- Disjunktion ( NOR ) und erwähnte die Nicht-Konjunktion nur in einer Fußnote und ohne besonderes Zeichen dafür. Es war Jean Nicod , der den Strich als Zeichen für die Nicht-Konjunktion (NAND) in einer Arbeit von 1917 zum ersten Mal verwendete und die seitdem gängige Praxis ist. Russell und Whitehead verwendeten den Sheffer-Strich in der zweiten Ausgabe von Principia Mathematica von 1927 und schlugen ihn als Ersatz für die "oder"- und "nicht"-Operationen der ersten Ausgabe vor.

Charles Sanders Peirce (1880) hatte die funktionale Vollständigkeit von NAND oder NOR mehr als 30 Jahre zuvor unter Verwendung des Begriffs Ampheck (für 'Schneiden in beide Richtungen') entdeckt, aber er veröffentlichte seine Ergebnisse nie.

Eigenschaften

NAND besitzt keine der folgenden fünf Eigenschaften, von denen jede bei mindestens einem Mitglied einer Menge funktional vollständiger Operatoren fehlen muss und deren Abwesenheit ausreicht : Wahrheitserhaltung, Falschheit Erhaltung, Linearität , Monotonie , Selbstdualität . (Ein Operator ist wahrheits-(falsch-)erhaltend, wenn sein Wert wahr (falsch) ist, wenn alle seine Argumente wahr sind (falsch).) Daher ist {NAND} eine funktional vollständige Menge.

Dies kann auch wie folgt realisiert werden: Alle drei Elemente der funktional vollständigen Menge {AND, OR, NOT} können nur mit NAND konstruiert werden . Somit muss auch die Menge {NAND} funktional vollständig sein.

Andere boolesche Operationen in Bezug auf den Sheffer-Strich

In Form von NAND ausgedrückt sind die üblichen Operatoren der Aussagenlogik: ${\displaystyle\uparrow}$

${\displaystyle \neg P}$     ${\displaystyle \Leftrightarrow}$     ${\displaystyle P}$ ${\displaystyle\uparrow}$ ${\displaystyle P}$     ${\displaystyle \Leftrightarrow}$     ${\displaystyle\uparrow}$		${\displaystyle P\rightarrow Q}$     ${\displaystyle \Leftrightarrow}$     ${\displaystyle ~P}$ ${\displaystyle\uparrow}$ ${\displaystyle (Q\uparrow Q)}$     ${\displaystyle \Leftrightarrow}$     ${\displaystyle ~P}$ ${\displaystyle\uparrow}$ ${\displaystyle (P\uparrow Q)}$     ${\displaystyle \Leftrightarrow}$     ${\displaystyle\uparrow}$     ${\displaystyle \Leftrightarrow}$     ${\displaystyle\uparrow}$		${\displaystyle P\leftrightarrow Q}$     ${\displaystyle \Leftrightarrow}$     ${\displaystyle (P\uparrow Q)}$ ${\displaystyle\uparrow}$ ${\displaystyle ((P\uparrow P)\uparrow (Q\uparrow Q))}$     ${\displaystyle \Leftrightarrow}$     ${\displaystyle\uparrow}$
${\displaystyle P\land Q}$     ${\displaystyle \Leftrightarrow}$     ${\displaystyle (P\uparrow Q)}$ ${\displaystyle\uparrow}$ ${\displaystyle (P\uparrow Q)}$     ${\displaystyle \Leftrightarrow}$     ${\displaystyle\uparrow}$		${\displaystyle P\lor Q}$     ${\displaystyle \Leftrightarrow}$     ${\displaystyle (P\uparrow P)}$ ${\displaystyle\uparrow}$ ${\displaystyle (Q\uparrow Q)}$     ${\displaystyle \Leftrightarrow}$     ${\displaystyle\uparrow}$

Formales System basierend auf dem Sheffer-Strich

Das Folgende ist ein Beispiel für ein formales System, das vollständig auf dem Sheffer-Strich basiert, jedoch die funktionale Ausdruckskraft der Aussagenlogik besitzt :

Symbole

p _n für natürliche Zahlen n :

( | )

Der Sheffer-Strich pendelt, assoziiert aber nicht (zB (T | T) | F = T , aber T | (T | F) = F ). Daher muss jedes formale System, das den Sheffer-Strich als Infixsymbol enthält, auch ein Mittel enthalten, um eine Gruppierung anzuzeigen (die Gruppierung erfolgt automatisch, wenn der Strich als Präfix verwendet wird, also: || TTF = T und | T | TF = F ). Dazu verwenden wir '(' und ')'.

Wir schreiben auch p , q , r , … statt p ₀ , p ₁ , p ₂ .

Syntax

Konstruktionsregel I: Für jede natürliche Zahl n ist das Symbol p _n eine wohlgeformte Formel (wff), Atom genannt.

Konstruktionsregel II: Wenn X und Y wffs sind, dann ist ( X  |  Y ) ein wff.

Abschlussregel: Alle Formeln, die nicht mit den ersten beiden Konstruktionsregeln konstruiert werden können, sind keine wffs.

Die Buchstaben U , V , W , X und Y sind Metavariablen, die für wffs stehen.

Ein Entscheidungsverfahren zur Bestimmung, ob eine Formel wohlgeformt ist, geht wie folgt: "Dekonstruieren" Sie die Formel, indem Sie die Konstruktionsregeln rückwärts anwenden, wodurch die Formel in kleinere Teilformeln zerlegt wird. Wiederholen Sie dann diesen rekursiven Dekonstruktionsprozess für jede der Teilformeln. Schließlich sollte die Formel auf ihre Atome reduziert werden, aber wenn eine Unterformel nicht so reduziert werden kann, dann ist die Formel keine wff.

Infinitesimalrechnung

Alle wffs des Formulars

(( U | ( V | W )) | (( Y | ( Y | Y )) | (( X | V ) | (( U | X ) | ( U | X )))))

sind Axiome. Instanzen von

${\displaystyle (U|(V|W)),U\vdash W}$

sind Inferenzregeln.

Vereinfachung

Da die einzige Verknüpfung dieser Logik | ist, ist das Symbol | ganz verworfen werden, so dass nur die Klammern übrig bleiben, um die Buchstaben zu gruppieren. Ein Paar Klammern muss immer ein Paar wff s einschließen . Beispiele für Theoreme in dieser vereinfachten Notation sind

( p ( p ( q ( q (( pq )( pq )))))),

( p ( p ( ( qq ) ( pp )))).

Die Notation kann weiter vereinfacht werden, indem man

( U ) := ( UU )

${\displaystyle ((U))\equiv U}$

für jede U . Diese Vereinfachung führt dazu, dass einige Regeln geändert werden müssen:

1. In Klammern sind mehr als zwei Buchstaben erlaubt.
2. Buchstaben oder wffs in Klammern dürfen pendeln.
3. Wiederholte Buchstaben oder wffs innerhalb eines gleichen Satzes von Klammern können eliminiert werden.

Das Ergebnis ist eine in Klammern gesetzte Version der Peirce- Existenzgraphen .

Eine andere Möglichkeit, die Notation zu vereinfachen, besteht darin, Klammern mithilfe der polnischen Notation zu entfernen . Zum Beispiel könnten die früheren Beispiele mit nur Klammern wie folgt umgeschrieben werden, indem nur Striche verwendet werden

( p ( p ( q ( q (( pq )( pq )))))) wird

| p | p | q | q || pq | pq , und

( p ( p (( qq )( pp )))) wird,

| p | p || qq | pp .

Dies folgt den gleichen Regeln wie die Klammerversion, wobei die öffnende Klammer durch einen Sheffer-Strich ersetzt und die (redundante) schließende Klammer entfernt wird.

Oder (bei einigen Formeln) könnte man sowohl Klammern als auch Striche weglassen und die Reihenfolge der Argumente erlauben, die Reihenfolge der Funktionsanwendung zu bestimmen, so dass zum Beispiel die Anwendung von rechts nach links (umgekehrte polnische Notation – jede andere eindeutige Konvention basierend auf) Bestellung würde reichen)

${\displaystyle {\begin{ausgerichtet}&pqr\equiv (p\mid (q\mid r)),{\text{ wohingegen}}\\&rqp\equiv (r\mid (q\mid p)).\end {ausgerichtet}}}$

Siehe auch

Anmerkungen

Verweise

• Bocheński, Józef Maria (1960), Precis of Mathematical Logic , Rev., Albert Menne, herausgegeben und übersetzt aus der französischen und deutschen Ausgabe von Otto Bird, Dordrecht , Südholland : D. Reidel .
• Kirche, Alonzo (1956). Einführung in die mathematische Logik. Band 1 . Princeton University Press .
• Nicod, Jean GP (1917). „Eine Reduzierung der Anzahl der primitiven Sätze der Logik“. Verfahren der Cambridge Philosophical Society . 19 : 32–41.
• Charles Sanders Peirce , 1880, "A Boolian [sic] Algebra mit einem Constant", in Hartshorne, C. und Weiss, P. , Hrsg., (1931-1935) Collected Papers von Charles Sanders Peirce , Vol. 4 : 12–20, Cambridge : Harvard University Press .
• Sheffer, HM (1913), "Ein Satz von fünf unabhängigen Postulaten für Boolesche Algebren, mit Anwendung auf logische Konstanten", Transactions of the American Mathematical Society , 14 : 481–488, doi : 10.2307/1988701 , JSTOR  1988701

Externe Links

• Sheffer Stroke Artikel in der Internet Encyclopedia of Philosophy
• http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
• Implementierungen von NAND-Gattern mit 2 und 4 Eingängen
• Beweise einiger Axiome durch die Stroke-Funktion von Yasuo Setô @ Project Euclid