L'expression logique ( a && b ) (les deux a et b ont des valeurs booléennes) peut s'écrire comme suit !(!a || !b) par exemple. Cela ne signifie-t-il pas que && est "inutile" ? Cela signifie-t-il que tous les expressions logiques ne peuvent être réalisées qu'en utilisant || et ! ?
Réponses
Trop de publicités?
Oui, comme les autres réponses l'ont souligné, l'ensemble des opérateurs composé de || 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. A et B :
-
Véritable :
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) -
A :
A -
B :
B -
A NOR 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 que 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 soit NAND soit NOR avec lui.
Voici un graphique montrant les Diagrammes de Venn pour chacun des connecteurs énumérés ci-dessus :
[ source ]
rgettman
Points
74908
Ce que vous décrivez est complétude fonctionnelle .
Il décrit un ensemble d'opérateurs logiques suffisant pour "exprimer toutes les tables de vérité possibles". Votre ensemble d'opérateurs Java, { || , ! }, est suffisant ; il correspond à l'ensemble {∨, ¬}, qui figure dans la section " Ensembles d'opérateurs minimaux fonctionnellement complets ".
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. Comme il y a deux valeurs possibles pour un booléen, il y a deux tables de vérité. 4 soit 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 FVoici un tableau des numéros de la table de vérité (0-15), les || et ! les combinaisons 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) | FALSEIl existe de nombreux autres ensembles fonctionnellement complets, notamment les ensembles à un élément {NAND} et {NOR}, qui n'ont pas d'opérateurs uniques correspondants en Java.
Paul Boddington
Points
9671
Oui.
Toutes les portes logiques peuvent être fabriquées à partir de portes NOR.
Puisqu'une porte NOR peut être fabriquée à partir d'un NOT et d'un OR, le résultat est le suivant.
ryuu9187
Points
972
Prenez le temps de vous renseigner sur Les lois de DeMorgan si vous le pouvez.
Vous trouverez la réponse dans la lecture qui y est faite, ainsi que les références aux preuves logiques.
Mais en gros, la réponse est oui.
EDIT : Pour être explicite, je veux dire qu'on peut logiquement inférer une expression OR d'une expression AND, et vice-versa. Il existe d'autres lois pour l'équivalence logique et l'inférence, mais je pense que celle-ci est la plus appropriée.
EDIT 2 : Voici une preuve par table de vérité montrant l'équivalence logique de l'expression suivante.
La 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 |
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
anand
Points
797
NAND et NOR sont universels ; ils peuvent être utilisés pour construire n'importe quelle opération logique n'importe où ; d'autres opérateurs sont disponibles dans des langages de programmation pour faciliter l'écriture et la lisibilité des codes.
De même, toutes les opérations logiques qui doivent être câblées dans le circuit sont également développées en utilisant uniquement des circuits intégrés NAND ou NOR.
