In Boolean-Funktionen und Satzrechnung, dem Schlag von Sheffer, genannt nach Henry M. Sheffer, schriftlich "|" (sieh vertikale Bar, um mit "||" nicht verwirrt zu sein, der häufig verwendet wird, um Trennung zu vertreten), zeigt "Dpq" oder "", eine logische Operation an, die zur Ablehnung der Verbindungsoperation gleichwertig ist, die auf der gewöhnlichen Sprache als "nicht beide" ausgedrückt ist. Es wird auch die alternative Leugnung genannt, da es tatsächlich sagt, dass mindestens ein seiner operands falsch sind. In der Boolean Algebra und Digitalelektronik ist es als die NAND Operation ("nicht und") bekannt.

Wie sein Doppel-, NOCH Maschinenbediener (a.k.a. der Pfeil von Peirce oder Dolch von Quine), kann NAND allein ohne jeden anderen logischen Maschinenbediener verwendet werden, um ein logisches formelles System einzusetzen (NAND lassend, funktionell vollenden). Dieses Eigentum macht das NAND Tor entscheidend für die moderne Digitalelektronik, einschließlich seines Gebrauches im NAND-Blitz-Gedächtnis und Computerverarbeiter-Design.

Definition

Die NAND Operation ist eine logische Operation auf zwei logischen Werten. Es erzeugt einen Wert von wahren, wenn — und nur wenn — mindestens ein der Vorschläge falsch sind.

Wahrheitstabelle

Die Wahrheitstabelle Eines NAND B (auch schriftlich als Ein B, Dpq oder Ein  B) ist wie folgt:

Geschichte

Der Schlag wird genannt nach Henry M. Sheffer, der (Sheffer 1913) einen axiomatization von Algebra von Boolean mit dem Schlag zur Verfügung gestellt hat, und hat seine Gleichwertigkeit zu einer Standardformulierung davon durch Huntington bewiesen, der die vertrauten Maschinenbediener der Satzlogik (und, oder, nicht) anstellt. Wegen der Selbstdualität von Algebra von Boolean sind die Axiome von Sheffer entweder für des NAND oder für NOCH Operationen im Platz des Schlags ebenso gültig. Sheffer hat den Schlag als ein Zeichen für die Nichttrennung (NOCH) in seiner Zeitung interpretiert, Nichtverbindung nur in einem Kommentar und ohne ein spezielles Zeichen dafür erwähnend. Es war Jean Nicod, der zuerst den Schlag als ein Zeichen für die Nichtverbindung (NAND) in einer Zeitung von 1917 verwendet hat, und der aktuelle Praxis seitdem geworden ist.

Charles Sanders Peirce (1880) hatte die funktionelle Vollständigkeit von NAND oder NOCH mehr als 30 Jahre früher entdeckt, den Begriff ampheck gebrauchend (um beide Wege' 'zu schneiden), aber er hat nie seine Entdeckung veröffentlicht.

Eigenschaften

NAND besitzt keinen der folgenden fünf Eigenschaften, von denen jeder erforderlich ist, von, und die Abwesenheit zu fehlen, von von dem allem für, mindestens ein Mitglied von einer Reihe funktionell ganzer Maschinenbediener genügend ist: Wahrheitsbewahrung, Unehrlichkeitsbewahrung, Linearität, Monomuskeltonus, Selbstdualität. (Ein Maschinenbediener ist Wahrheit - (Unehrlichkeit-) Bewahrung, wenn sein Wert Wahrheit (Unehrlichkeit) ist, wann auch immer alle seine Argumente Wahrheit (Unehrlichkeit) sind.) Deshalb {NAND} ist ein funktionell ganzer Satz.

Das kann auch wie folgt begriffen werden: Alle drei Elemente des funktionell ganzen Satzes {UND, ODER, NICHT} können mit nur NAND gebaut werden. So muss der Satz {NAND} ebenso funktionell abgeschlossen sein.

Einführung, Beseitigung und Gleichwertigkeiten

Der Sheffer-Schlag ist die Ablehnung der Verbindung:

Ausgedrückt in Bezug auf NAND sind die üblichen Maschinenbediener der Satzlogik:

|

|

Formelles System auf dem Schlag von Sheffer gestützt

Der folgende ist ein Beispiel eines formellen Systems gestützt völlig auf dem Schlag von Sheffer, noch das funktionelle Ausdrucksvolle der Satzlogik habend:

Symbole

p für natürliche Zahlen n

(|)

Der Sheffer-Schlag pendelt, aber verkehrt nicht (z.B, (T|T) |F = T, aber T | (T|F) = F). Folglich muss jedes formelle System einschließlich des Schlags von Sheffer auch ein Mittel einschließen, Gruppierung anzuzeigen. Wir werden' (' und')' zu dieser Wirkung verwenden.

Wir schreiben auch p, q, r, … statt p, p, p.

Syntax

Bauregel I: Für jede natürliche Zahl n ist das Symbol p eine gut gebildete Formel (wff), genannt ein Atom.

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

Verschluss-Regel: Irgendwelche Formeln, die mittels der ersten zwei Bauregeln nicht gebaut werden können, sind nicht wffs.

Die Briefe U, V, W, X und Y sind metavariables, der wffs eintritt.

Ein Entscheidungsverfahren, um zu bestimmen, ob eine Formel gut gebildet wird, geht wie folgt: "Dekonstruieren Sie" die Formel, indem Sie die Bauregeln umgekehrt dadurch anwenden, die Formel in kleinere Subformeln brechend. Dann wiederholen Sie diesen rekursiven Deconstruction-Prozess zu jeder der Subformeln. Schließlich sollte die Formel auf seine Atome reduziert werden, aber wenn eine Subformel nicht so reduziert werden kann, dann ist die Formel nicht ein wff.

Rechnung

Der ganze wffs der Form

: ((U (VW)) | ((Y (YY)) | ((XV) | ((UX) | (UX)))))

sind Axiome. Beispiele von

: (U (VW)), U W

sind Interferenzregeln.

Vereinfachung

Da das einzige Bindewort dieser Logik | ist, konnte das Symbol | zusammen verworfen werden, nur die Parenthesen verlassend, um die Briefe zu gruppieren. Ein Paar von Parenthesen muss immer ein Paar von wffs einschließen. Beispiele von Lehrsätzen in dieser vereinfachten Notation sind

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

: (p (p ((qq) (Seiten)))).

Die Notation kann weiter, durch das Lassen vereinfacht werden

: (U): = (UU)

: ((U)) U

für jeden U. Diese Vereinfachung verursacht das Bedürfnis, einige Regeln zu ändern:

1. Mehr als zwei Briefen wird innerhalb von Parenthesen erlaubt.
2. Briefen oder wffs innerhalb von Parenthesen wird erlaubt zu pendeln.
3. Wiederholte Briefe oder wffs innerhalb desselben Satzes von Parenthesen können beseitigt werden.

Das Ergebnis ist eine parenthetische Version des Peirces existenzielle Graphen.

Eine andere Weise, die Notation zu vereinfachen, soll Parenthese durch das Verwenden polnischer Notation beseitigen. Zum Beispiel konnten die früheren Beispiele mit nur der Parenthese damit umgeschrieben werden nur streicht wie folgt

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

: |ppqqpqpq und

: (p (p ((qq) (Seiten)))), wird

: |ppqqpp.

Das folgt denselben Regeln wie die Parenthese-Version mit der öffnenden Parenthese, die durch einen Schlag von Sheffer und die (überflüssige) entfernte Schlussparenthese ersetzt ist.

Siehe auch

• UND Tor
• Gebiet von Boolean
• CMOS
• Gleichwertiges Tor (GE)
• Gesetze der Form
• Logiktor
• Logischer Graph
• NAND Blitz-Gedächtnis
• NAND Logik
• NAND Tor
• NOCH Tor
• NICHT Tor
• ODER Tor
• Das Gesetz von Peirce
• Pfeil von Peirce = NOCH
• Satzlogik
• Alleiniger genügend Maschinenbediener
• XOR Tor

Referenzen

• Bocheński, Józef Maria (1960), Précis der Mathematischen Logik, die aus den französischen und deutschen Ausgaben von Otto Bird, Dordrecht, das Südliche Holland übersetzt ist:D. Reidel.
• Kirche, Alonzo, (1956) Einführung in die mathematische Logik, Vol. 1, Princeton: Universität von Princeton Presse.
• Nicod, Jean G. P., (1917) "Die Verminderung der Zahl von Primitiven Vorschlägen der Logik", Verhandlungen des Cambridges Philosophische Gesellschaft, Vol. 19, Seiten 32-41.
• Charles Sanders Peirce, 1880, "Ein Boolian [sic] Algebra mit Einer Konstante", in Hartshorne, C. und Weiss, P., Hrsg., (1931-35) Gesammelte Papiere von Charles Sanders Peirce, Vol. 4: 12-20, Cambridge: Universität von Harvard Presse.
• H. M. Sheffer, 1913. "Eine Reihe fünf unabhängige Postulate für Algebra von Boolean, mit der Anwendung auf logische Konstanten," Transaktionen der amerikanischen Mathematischen Gesellschaft 14: Seiten 481-488.

Links

• http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
• Durchführungen 2 und NAND 4-Eingänge-Tore
• Beweise von einigen Axiomen durch den Schlag fungieren durch Yasuo Setô Projekt Euklid