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

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 !?

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:

• Prawda :A || !A
• A NAND B :!A || !B
• B oznacza A :!B || A
• A implikuje B :!A || B
• A LUB B :A || B
• Nie B :!B
• Nie A :!A
• A XOR B :!(!A || B) || !(A || !B)
• A XNOR B :!(!A || !B) || !(A || B)
• Odp . :A
• B :B
• A NOR B :!(A || B)
• A nie implikuje B :!(!A || B)
• B nie implikuje A :!(!B || A)
• A ORAZ B :!(!A || !B)
• Fałsz :!(A || !A)

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ń:

[ źródło ]

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 ⁴ 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.

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.

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 |
_______________________________________________________

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.

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