Sont || et ! opérateurs suffisants pour rendre toutes les expressions logiques possibles?

L'expression logique ( a && b ) (les deux aet bont des valeurs booléennes) peut être écrite comme !(!a || !b), par exemple. Cela ne veut-il pas dire que &&c'est "inutile"? Est-ce à dire que toutes les expressions logiques ne peuvent être faites qu'en utilisant ||et !?

Oui, comme l'ont souligné les autres réponses, l'ensemble des opérateurs comprenant ||et !est fonctionnellement complet . Voici une preuve constructive de cela, montrant comment les utiliser pour exprimer les seize connecteurs logiques possibles entre les variables booléennes Aet B:

• Vrai :A || !A
• A NAND B :!A || !B
• B implique A :!B || A
• A implique B :!A || B
• A OU B :A || B
• Pas B :!B
• Pas A :!A
• A XOR B :!(!A || B) || !(A || !B)
• A XNOR B :!(!A || !B) || !(A || B)
• Un :A
• B :B
• A NI B :!(A || B)
• A n'implique pas B :!(!A || B)
• B n'implique pas A :!(!B || A)
• A ET B :!(!A || !B)
• Faux :!(A || !A)

Notez que NAND et NOR sont en eux-mêmes fonctionnellement complets (ce qui peut être prouvé en utilisant la même méthode ci-dessus), donc si vous voulez vérifier qu'un ensemble d'opérateurs est fonctionnellement complet, il suffit de montrer que vous pouvez exprimer NAND ou NOR avec ça.

Voici un graphique montrant les diagrammes de Venn pour chacun des connecteurs répertoriés ci-dessus:

[ source ]

Ce que vous décrivez est l'exhaustivité fonctionnelle .

Ceci décrit un ensemble d'opérateurs logiques qui sont suffisants pour "exprimer toutes les tables de vérité possibles". Votre ensemble d'opérateurs Java, { ||, !}, est suffisant; il correspond à l'ensemble {∨, ¬}, qui est répertorié dans la section "Ensembles d'opérateurs fonctionnellement minimaux".

L'ensemble de toutes les tables de vérité signifie tous les ensembles possibles de 4 valeurs booléennes qui peuvent être le résultat d'une opération entre 2 valeurs booléennes. Puisqu'il y a 2 valeurs possibles pour un booléen, il y a 2 ⁴ ou 16 tables de vérité possibles.

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

Voici un tableau des numéros de table de vérité (0-15), les combinaisons ||et !qui le produisent, et une description.

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

Il existe de nombreux autres ensembles fonctionnellement complets, y compris les ensembles d'éléments {NAND} et {NOR}, qui n'ont pas d'opérateurs uniques correspondants en Java.

Oui.

Toutes les portes logiques peuvent être réalisées à partir de portes NOR.

Puisqu'une porte NOR peut être faite à partir d'un NON et d'un OU, le résultat suit.

Prenez le temps de lire sur les lois de DeMorgan si vous le pouvez.

Vous y trouverez la réponse dans la lecture, ainsi que des références aux preuves logiques.

Mais essentiellement, la réponse est oui.

EDIT : Pour explicitation, mon point est que l'on peut logiquement déduire une expression OR d'une expression AND, et vice-versa. Il existe également d'autres lois pour l'équivalence et l'inférence logiques, mais je pense que celle-ci est tout à fait appropriée.

EDIT 2 : Voici une preuve via la table de vérité montrant l'équivalence logique de l'expression suivante.

Loi de DeMorgan: !(!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 |
_______________________________________________________

NAND et NOR sont universels, ils peuvent être utilisés pour créer n'importe quelle opération logique que vous voulez n'importe où; d'autres opérateurs sont disponibles dans les langages de programmation pour faciliter l'écriture et la lisibilité des codes.

Toutes les opérations logiques qui doivent être câblées en circuit sont également développées en utilisant des circuits intégrés NAND ou NOR uniquement.

Oui, selon l'algèbre booléenne, toute fonction booléenne peut être exprimée comme une somme de minterms ou un produit de maxterms, qui est appelé forme normale canonique . Il n'y a aucune raison pour laquelle une telle logique ne pourrait pas être appliquée aux mêmes opérateurs utilisés en informatique.

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