Są || i ! operatory wystarczające, aby każde możliwe wyrażenie logiczne?

294

Logicznym wyrażenie ( a && b ) (oba ai bmają wartości logicznych) można zapisać jak !(!a || !b), na przykład. Czy to nie znaczy, że &&jest „niepotrzebne”? Czy to oznacza, że wszystkie wyrażenia logiczne można tworzyć tylko przy użyciu ||i !?

JakeTheSnake
źródło
83
Jest to bardziej podstawowe symboliczne pytanie logiczne niż kwestia Java, ale tak. W kombinacji LUB i NIE można użyć do zbudowania wszystkiego innego. To samo z AND i NOT. Na przykład, kiedy byłem w szkole, nauczono nas budować wszystko przy użyciu tylko bramek NAND, ponieważ zabrali mniej tranzystorów.
azurefrog
79
Nie należy mylić możliwości napisania instrukcji w ten sposób z potrzebą zrobienia tego. Cukier syntaktyczny to dobra rzecz.
azurefrog
20
Wiele układów logicznych bramek zapewnia tylko bramki NAND lub NOR, ponieważ możliwe jest wdrożenie wszystkich operacji z nimi, a to sprawia, że ​​są tanie w produkcji - A and B == !A nor !B == !(!A or !B). Podobnie A or B == !A nand !B == !(!A and !B). Oczywiście przekazanie tej samej wartości do obu wejść NAND lub NOR da taki sam wynik jak zwykłe NIE. XOR i XNOR są również możliwe, ale bardziej złożone. Zobacz twierdzenie De Morgana
Basic
16
Czy to nie pytanie z zakresu informatyki? Nie widzę tu kodu. W szczególności to, czy jest to prawdą w praktyce, będzie się różnić w zależności od implementacji, np. W C ++ przy przeciążeniu operacyjnym nie jest to w ogóle.
Wyścigi lekkości na orbicie
6
@ SnakeDoc Nie sądzę, żeby ktokolwiek tutaj opowiadał się za taką rzeczą. Uważam, że to pytanie było bardziej teoretycznym pytaniem logicznym niż programowym, naprawdę.
ryuu9187

Odpowiedzi:

425

Tak, jak inne odpowiedzi wskazał, zestaw składający się z operatorami ||i !jest funkcjonalnie kompletne . Oto konstruktywny dowód na to, pokazujący, jak używać ich do wyrażania wszystkich szesnastu możliwych logicznych połączeń między zmiennymi logicznymi Ai B:

Zauważ, że zarówno NAND, jak i NOR same w sobie są funkcjonalnie kompletne (co można udowodnić za pomocą tej samej metody powyżej), więc jeśli chcesz sprawdzić, czy zestaw operatorów jest funkcjonalnie kompletny, wystarczy pokazać, że możesz wyrazić NAND lub NOR z tym.

Oto wykres przedstawiający diagramy Venna dla każdego z wyżej wymienionych połączeń:

wprowadź opis zdjęcia tutaj

[ źródło ]

Peter Olson
źródło
20
Trudno powiedzieć, czy pytanie to ma na celu, ale ta odpowiedź nie odnosi się do zachowania zwarciowego (istotne, ponieważ pytanie dotyczy ||raczej niż |) lub skutków ubocznych (istotne, ponieważ ocena wartości true, false, XOR i XNOR ocenia ich argumenty więcej razy niż pierwotna stała lub operator).
David Richerby
5
Kręgi zawierające kręgi i przejścia tworzą diagram Hassego ( en.wikipedia.org/wiki/Hasse_diagram ). (Tak, nauczyłem się dziś czegoś nowego!)
Kasper van den Berg
5
@DavidRicherby To prawda. Inne niż XOR, XNOR, prawda i fałsz, o ile mogę powiedzieć, skutki uboczne i liczba ocen powinny być takie same jak wbudowane odpowiedniki (np. !(!A || !B)Ma takie same zwarcia i oceny, jak A && B). Nie sądzę, że możesz to zrobić dla XOR i XNOR bez dodatkowych konstrukcji (np. a ? !b : b), A prawda lub fałsz nie jest problemem, jeśli możesz zapisać wartości, ponieważ możesz uruchomić swój program, definiując truei falseużywając jakiejś sztucznej zmiennej boolean.
Peter Olson,
Warto zauważyć, że powyższa lista obejmuje 16 operacji. Jest to zgodne z faktem, że istnieje 16 możliwych tabel prawdy dla przypadku, w którym masz 2 wejścia i 1 wyjście.
Paul R
1
Chciałem tylko dodać kolejną wizualizację jako tabelę do odniesienia przez ludzi. To samo źródło co powyżej.
sierpnia
125

Opisujesz kompletność funkcjonalną .

Opisuje to zestaw operatorów logicznych, który wystarcza do „wyrażenia wszystkich możliwych tabel prawdy”. Zestaw operatora Java { ||, !} jest wystarczający; odpowiada on zestawowi {∨, ¬}, który jest wymieniony w sekcji „Minimalne kompletne funkcjonalnie zestawy operatorów”.

Zbiór wszystkich tabel prawdy oznacza wszystkie możliwe zestawy 4 wartości logicznych, które mogą być wynikiem operacji między 2 wartościami logicznymi. Ponieważ istnieją dwie możliwe wartości wartości logicznej, istnieją 2 4 lub 16 możliwych tabel prawdy.

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

Oto tabela numerów tabel prawdy (0–15) ||oraz !kombinacji, które ją dają, oraz opis.

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

Istnieje wiele innych takich funkcjonalnie kompletnych zestawów, w tym zestawy jednego elementu {NAND} i {NOR}, które nie mają odpowiadających pojedynczych operatorów w Javie.

rgettman
źródło
4
+1 za edycję. Pomimo różnicy w głosowaniu, myślę, że twoja odpowiedź jest w rzeczywistości bardziej szczegółowa niż moja.
Peter Olson
Tabele prawdy, o których myślałem, że zostawiłem je po pierwszym roku studiów
Barkermn01,
80

Tak.

Wszystkie bramki logiczne mogą być wykonane z bram NOR.

Ponieważ bramka NOR może być wykonana z NOT i OR, wynik jest następujący.

Paul Boddington
źródło
64
@PaulDraper lub NAND gates
slebetman
25
Wylądowanie dwóch osób na Księżycu zajęło 4100 bram NOR.
Hans Passant
4
@HansPassant I trochę sznurka. Dużo sznurka. (Pamięć o rdzeniu liny, nie odmiany puszek).
CVn
3
@HansPassant Czasami chciałbym, aby Stack Exchange była Wikipedią, wtedy wstawiałbym tam [citation-needed]znak.
Simon Forsberg,
11
Tak, przepraszam, komputer prowadzący Apollo .
Hans Passant,
64

Poświęć trochę czasu na zapoznanie się z Prawami DeMorgan, jeśli możesz.

Znajdziesz tam odpowiedź w czytaniu, a także odniesienia do logicznych dowodów.

Ale w zasadzie odpowiedź brzmi tak.

EDYCJA : Dla jasności chodzi mi o to, że można logicznie wywnioskować wyrażenie OR z wyrażenia AND i odwrotnie. Istnieje również więcej praw dotyczących logicznej równoważności i wnioskowania, ale myślę, że to najbardziej apropos.


EDYCJA 2 : Oto dowód za pomocą tabeli prawdy pokazujący logiczną równoważność następującego wyrażenia.

Prawo DeMorgan: !(!A || !B) -> A && B

 _____________________________________________________
| A | B | ! A | ! B | ! A || ! B | ! (! A ||! B) | A i&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
źródło
19
Niektórzy ludzie rezygnują z głosowania w ramach „kompletności funkcjonalnej”
Jesse
3
Przy + 27 / -2 nie martwiłbym się zbytnio zbłąkanym głosowaniem negatywnym.
CVn
2
@ MichaelKjörling Jestem ciekawy, dlaczego niektórzy uważali, że moja odpowiedź nie była pomocna / była szkodliwa.
ryuu9187
3
Zasadniczo odpowiedzi, które opierają się na linkach, nie są zbyt lubiane (ponieważ linki umierają), ale w tym przypadku istnieje tak wiele alternatywnych wyjaśnień praw DeMorgan, że nie widzę problemu - nadal sądzę, że DV
2813274
@ user2813274 Dziękujemy za wyjaśnienie. Mam nadzieję, że moje zmiany pomogą wypełnić lukę między osobistymi badaniami a uzyskaniem odpowiedzi.
ryuu9187,
11

NAND i NOR są uniwersalne, można ich użyć do zbudowania dowolnej operacji logicznej, którą chcesz gdziekolwiek; inni operatorzy są dostępni w językach programowania, aby ułatwić pisanie i tworzenie czytelnych kodów.

Również wszystkie operacje logiczne, które muszą być podłączone w obwodzie, są również opracowywane przy użyciu układów scalonych NAND lub NOR.

anand
źródło
10

Tak, zgodnie z algebrą boolowską, dowolną funkcję boolowską można wyrazić jako sumę minterms lub iloczyn maxterms, który nazywa się kanoniczną formą normalną . Nie ma powodu, dla którego taka logika nie mogłaby zostać zastosowana do tych samych operatorów wykorzystywanych w informatyce.

https://en.wikipedia.org/wiki/Canonical_normal_form

Michał Szydłowski
źródło