Der logische Ausdruck ( a && b )
(beide a
und b
haben boolesche Werte) kann wie folgt geschrieben werden !(!a || !b)
. Bedeutet das nicht, dass &&
das "unnötig" ist? Bedeutet dies, dass alle logischen Ausdrücke nur mit ||
und erstellt werden können !
?
logic
logical-operators
JakeTheSnake
quelle
quelle
A and B == !A nor !B == !(!A or !B)
. EbensoA or B == !A nand !B == !(!A and !B)
. Wenn Sie offensichtlich denselben Wert an beide Eingänge eines NAND oder NOR übergeben, erhalten Sie das gleiche Ergebnis wie bei einem einfachen NOT. XOR und XNOR sind ebenfalls möglich, aber komplexer. Siehe De Morgans TheoremAntworten:
Ja, wie die anderen Antworten zeigten, ist die Gruppe der Operatoren, die aus
||
und funktional vollständig!
besteht , vollständig . Hier ist ein konstruktiver Beweis dafür, wie man sie verwendet, um alle 16 möglichen logischen Verknüpfungen zwischen den booleschen Variablen auszudrückenA
undB
:A || !A
!A || !B
!B || A
!A || B
A || B
!B
!A
!(!A || B) || !(A || !B)
!(!A || !B) || !(A || B)
A
B
!(A || B)
!(!A || B)
!(!B || A)
!(!A || !B)
!(A || !A)
Beachten Sie, dass sowohl NAND als auch NOR für sich genommen funktional vollständig sind (was mit derselben Methode wie oben bewiesen werden kann). Wenn Sie also überprüfen möchten, ob eine Reihe von Operatoren funktional vollständig ist, reicht es aus, um zu zeigen, dass Sie entweder NAND oder NOR ausdrücken können damit.
Hier ist eine Grafik, die die Venn-Diagramme für jede der oben aufgeführten Verbindungen zeigt:
[ Quelle ]
quelle
||
eher nach als fragt|
) oder Nebenwirkungen (relevant, weil die Erweiterung von wahr, falsch, XOR und XNOR ausgewertet wird) ihre Argumente öfter als die ursprüngliche Konstante oder der Operator).!(!A || !B)
identisch sein (z. B. die gleiche Anzahl an Kurzschlüssen und Bewertungen wieA && B
). Ich glaube nicht, dass Sie dies für XOR und XNOR ohne zusätzliche Konstrukte (z. B.a ? !b : b
) tun können , und true oder false ist kein Problem, wenn Sie Werte speichern können, da Sie Ihr Programm durch Definierentrue
undfalse
Verwenden einer booleschen Dummy-Variablen starten könnten .Was Sie beschreiben, ist funktionale Vollständigkeit .
Dies beschreibt eine Reihe von logischen Operatoren, die ausreichen, um "alle möglichen Wahrheitstabellen auszudrücken". Ihr Java-Operatorsatz {
||
,!
} ist ausreichend. es entspricht der Menge {∨, ¬}, die im Abschnitt "Minimale funktional vollständige Operatorsätze" aufgeführt ist.Die Menge aller Wahrheitstabellen bedeutet alle möglichen Mengen von 4 Booleschen Werten, die das Ergebnis einer Operation zwischen 2 Booleschen Werten sein können. Da es 2 mögliche Werte für einen Booleschen Wert gibt, gibt es 2 4 oder 16 mögliche Wahrheitstabellen.
Hier ist eine Tabelle mit den Wahrheitstabellennummern (0-15), den
||
und!
Kombinationen, die sie ergeben, und einer Beschreibung.Es gibt viele andere solche funktional vollständigen Mengen, einschließlich der Ein-Element-Mengen {NAND} und {NOR}, die in Java keine entsprechenden Einzeloperatoren haben.
quelle
Ja.
Alle Logikgatter können aus NOR-Gattern bestehen.
Da ein NOR-Gatter aus einem NOT und einem OR bestehen kann, folgt das Ergebnis.
quelle
[citation-needed]
genau dort eine Markierung einfügen .Nehmen Sie sich Zeit, um sich über die Gesetze von DeMorgan zu informieren, wenn Sie können.
Die Antwort finden Sie in der Lesung dort sowie Verweise auf die logischen Beweise.
Aber im Wesentlichen lautet die Antwort ja.
EDIT : Meiner Meinung nach kann man einen ODER-Ausdruck logisch aus einem UND-Ausdruck ableiten und umgekehrt. Es gibt auch mehr Gesetze für logische Äquivalenz und Folgerung, aber ich denke, dieses ist am besten geeignet.
EDIT 2 : Hier ist ein Beweis über die Wahrheitstabelle, der die logische Äquivalenz des folgenden Ausdrucks zeigt.
DeMorgans Gesetz:
!(!A || !B) -> A && B
quelle
NAND und NOR sind universell und können verwendet werden, um jede gewünschte logische Operation überall aufzubauen. Andere Operatoren sind in Programmiersprachen verfügbar, um das Schreiben und Lesen lesbarer Codes zu vereinfachen.
Alle logischen Operationen, die erforderlich sind, um in der Schaltung fest verdrahtet zu werden, werden ebenfalls unter Verwendung von NAND- oder NOR-ICs entwickelt.
quelle
Ja, gemäß der Booleschen Algebra kann jede Boolesche Funktion als Summe von Mintermen oder als Produkt von Maxtermen ausgedrückt werden, was als kanonische Normalform bezeichnet wird . Es gibt keinen Grund, warum eine solche Logik nicht auf dieselben Operatoren angewendet werden könnte, die in der Informatik verwendet werden.
https://en.wikipedia.org/wiki/Canonical_normal_form
quelle