Sind || und ! Operatoren, die ausreichen, um jeden möglichen logischen Ausdruck zu machen?

294

Der logische Ausdruck ( a && b ) (beide aund bhaben 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 !?

JakeTheSnake
quelle
83
Dies ist eher eine grundlegende symbolische Logikfrage als ein Java-Problem, aber ja. ODER und NICHT in Kombination können verwendet werden, um alles andere zu konstruieren. Das gleiche gilt für AND und NOT. Als ich in der Schule war, wurde uns zum Beispiel beigebracht, alles nur mit NAND-Gattern zu bauen, weil sie weniger Transistoren benötigten.
Azurefrog
79
Verwechseln Sie nicht die Fähigkeit, eine Erklärung auf diese Weise zu schreiben, mit der Wünschbarkeit, dies zu tun. Syntaktischer Zucker ist eine gute Sache.
Azurefrog
20
Viele Logikgatterchips bieten nur NAND- oder NOR-Gatter, da alle Operationen mit ihnen implementiert werden können und die Herstellung billig ist A and B == !A nor !B == !(!A or !B). Ebenso A 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 Theorem
Basic
16
Ist das nicht eine Informatikfrage? Ich sehe hier keinen Code. Ob dies in der Praxis zutrifft, hängt von der Implementierung ab, z. B. in C ++ mit Betriebsüberlastung. Dies ist im Allgemeinen nicht der Fall .
Leichtigkeitsrennen im Orbit
6
@SnakeDoc Ich glaube nicht, dass sich hier jemand dafür einsetzt. Ich glaube, diese Frage war eher eine theoretische als eine programmatische Frage.
Ryuu9187

Antworten:

425

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ücken Aund B:

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:

Geben Sie hier die Bildbeschreibung ein

[ Quelle ]

Peter Olson
quelle
20
Es ist schwer zu sagen, ob die Frage dies beabsichtigt, aber diese Antwort behandelt nicht das Kurzschlussverhalten (relevant, da die Frage ||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).
David Richerby
5
Die Kreise mit Kreisen und die Übergänge bilden ein Hasse-Diagramm ( en.wikipedia.org/wiki/Hasse_diagram ). (Ja, ich habe heute etwas Neues gelernt!)
Kasper van den Berg
5
@ DavidRicherby Das stimmt. Abgesehen von XOR, XNOR, true und false sollten die Nebenwirkungen und die Anzahl der Bewertungen, soweit ich das beurteilen kann, mit den eingebauten Äquivalenten !(!A || !B)identisch sein (z. B. die gleiche Anzahl an Kurzschlüssen und Bewertungen wie A && 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 Definieren trueund falseVerwenden einer booleschen Dummy-Variablen starten könnten .
Peter Olson
Es ist interessant festzustellen, dass die obige Liste 16 Operationen umfasst. Dies steht im Einklang mit der Tatsache, dass es 16 mögliche Wahrheitstabellen für den Fall gibt, dass Sie 2 Eingänge und 1 Ausgang haben.
Paul R
1
Ich wollte nur eine weitere Visualisierung als Tabelle als Referenz hinzufügen . Gleiche Quelle wie oben.
aug
125

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.

A B | 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
----+------------------------------------------------
T T | T  T  T  T  T  T  T  T  F  F  F  F  F  F  F  F
T F | T  T  T  T  F  F  F  F  T  T  T  T  F  F  F  F
F T | T  T  F  F  T  T  F  F  T  T  F  F  T  T  F  F 
F F | T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F

Hier ist eine Tabelle mit den Wahrheitstabellennummern (0-15), den ||und !Kombinationen, die sie ergeben, und einer Beschreibung.

Table  |  Operation(s)                    | Description
-------+----------------------------------+-------------
  0    | A || !A                          | TRUE
  1    | A || B                           | OR
  2    | A || !B                          | B IMPLIES A
  3    | A                                | A
  4    | !A || B                          | A IMPLIES B
  5    | B                                | B
  6    | !(!A || !B) || !(A || B)         | XNOR (equals)
  7    | !(!A || !B)                      | AND
  8    | !A || !B                         | NAND
  9    | !(A || !B) || !(!A || B)         | XOR
 10    | !B                               | NOT B
 11    | !(!A || B)                       | NOT A IMPLIES B
 12    | !A                               | NOT A
 13    | !(A || !B)                       | NOT B IMPLIES A
 14    | !(A || B)                        | NOR
 15    | !(A || !A)                       | FALSE

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.

rgettman
quelle
4
+1 für die Bearbeitung. Trotz der unterschiedlichen Stimmenzahlen denke ich, dass Ihre Antwort jetzt detaillierter ist als meine.
Peter Olson
Wahrheitstabellen Ich dachte, ich hätte sie nach dem ersten Jahr an der Universität zurückgelassen
Barkermn01
80

Ja.

Alle Logikgatter können aus NOR-Gattern bestehen.

Da ein NOR-Gatter aus einem NOT und einem OR bestehen kann, folgt das Ergebnis.

Paul Boddington
quelle
64
@ PaulDraper oder NAND Gates
Slebetman
25
Es dauerte 4100 NOR-Tore, um zwei Menschen auf dem Mond zu landen.
Hans Passant
4
@ HansPassant Und ein String. Viel Schnur. (Kernseilspeicher, nicht die Blechdosenvariante.)
ein CVn
3
@HansPassant Manchmal wünschte ich mir, Stack Exchange wäre Wikipedia, dann würde ich [citation-needed]genau dort eine Markierung einfügen .
Simon Forsberg
11
Ja, sorry, Apollo-Leitcomputer .
Hans Passant
64

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

 _____________________________________________________
| A | B | ! A | ! B | ! A || ! B | ! (! A ||! B) | A && B |
-------------------------------------------------- -----
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
-------------------------------------------------- -----
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
-------------------------------------------------- -----
| 1 | 0 | 0 | 1 | 1 | 0 | 0 |
-------------------------------------------------- -----
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
_______________________________________________________
ryuu9187
quelle
19
Einige Leute müssen im Rahmen ihrer "funktionalen Vollständigkeit" abstimmen
Jesse
3
Bei + 27 / -2 würde ich mir keine Sorgen um eine verirrte Gegenstimme machen.
Ein CVn
2
@ MichaelKjörling Ich bin nur neugierig, warum manche Leute meine Antwort für nicht hilfreich / schädlich hielten.
Ryuu9187
3
Im Allgemeinen werden Antworten, die auf Links beruhen, nicht allzu sehr gemocht (da Links sterben), aber in diesem Fall gibt es so viele alternative Erklärungen zu DeMorgans Gesetzen, dass ich kein Problem sehe - dennoch, das ist meine Vermutung bezüglich der DV's
user2813274
@ user2813274 Danke für die Erklärung. Hoffentlich helfen meine Änderungen dabei, die Lücke zwischen persönlicher Recherche und der Beantwortung zu schließen.
ryuu9187
11

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.

anand
quelle
10

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

Michał Szydłowski
quelle