Loading AI tools
représentation d'expressions logiques De Wikipédia, l'encyclopédie libre
Une table de vérité (parfois appelée fonction de vérité) est une table mathématique utilisée en logique classique — en particulier le calcul propositionnel classique et l'algèbre de Boole — pour représenter de manière sémantique des expressions logiques et calculer la valeur de leur fonction relativement à chacun de leurs arguments fonctionnels (chaque combinaison de valeur assumée par leurs variables logiques). Les tables de vérité peuvent être utilisées en particulier pour dire si une proposition est vraie pour toutes les valeurs légitimement imputées, c'est-à-dire : si une proposition est « logiquement valide ».
En pratique, une table de vérité est composée d'une colonne pour chaque variable imputée (A et B par exemple, ou p et q), et d'une colonne où sont inscrits tous les résultats possibles de l'opération logique représentée par le tableau (A XOR B par exemple). Chaque ligne de la table de vérité contient ainsi une des configurations possibles des variables imputées (par exemple : A=vrai, B=faux), ainsi que le résultat de l'opération pour ces valeurs.
Ces outils sont couramment utilisés en mathématiques (logique propositionnelle), en électronique (porte logique) et en informatique (tests) selon un code d'entrée binaire (1 / 0, vrai / faux, allumé / éteint, etc.) Une sortie, également représentée sous forme de colonne, est la résultante des états d'entrée, elle-même exprimée sous forme d'état binaire. En d'autres termes, lorsque les entrées remplissent les conditions du circuit, la (les) sortie est activée.
Entrées | Sortie |
---|---|
États | État |
Une table de vérité est un tableau comportant plusieurs colonnes[1],[2],[3]. Les valeurs des cellules de ce tableau sont appelées « valeurs de vérité » (1 ou V pour vrai, 0 ou F pour faux) en mathématiques, et « états logiques » (1 ou V pour activé, 0 ou F pour désactivé) en électronique.
Les colonnes de gauche définissent les valeurs de vérité de différentes propositions en mathématiques (logique propositionnelle), ou les états logiques de différentes entrées logiques en électronique.
La colonne de droite indique la valeur de vérité de l'expression logique en mathématiques, ou l'état de sortie de la porte logique en électronique.
Optionnellement, on peut également trouver des colonnes au centre du tableau précisant des calculs intermédiaires.
Les quatre tables de vérité présentées ci-dessous permettent de définir les connecteurs logiques et, ou, ou exclusif et implication en mathématiques, ou les portes logiques correspondantes en électronique.
Par exemple, en langage électronique, nous devons avoir les deux entrées à 1 pour que la sortie de la porte logique ET soit activée ; alors que la porte logique OU n'a besoin que d'une des entrées à 1 pour afficher un 1 à la sortie ; ou encore nous devons avoir a et b ayant la même entrée ou que a soit FAUX et b soit VRAI pour avoir un 1 en sortie pour la porte logique de l'implication.
|
|
|
|
Table de vérité de a ∧ (b ∨ c) avec calcul intermédiaire de b ∨ c | ||||
---|---|---|---|---|
a | b | c | b ou c | a et (b ou c) |
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 1 |
1 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | 1 | 1 |
Le ∧ se lit et, le ∨ se lit ou.
Les trois premières colonnes de ce tableau fournissent les valeurs de vérité de a, b et c (par ex. des propositions logiques en mathématiques, ou des états logiques en électronique).
La 4e colonne fournit les valeurs de vérité de : b ou c.
La 5e colonne fournit les valeurs de vérité de : a et (b ou c).
Il existe 4 opérations unaires (ne requérant qu'un seul argument ou opérande, ici « p ») : fausseté (F), vérité (V), identité (p) et négation (¬p) ; et voici leurs tables de vérité respectives.
p | F |
---|---|
V | F |
F | F |
p | V |
---|---|
V | V |
F | V |
L'identité logique est une opération appliquée à un énoncé logique — typiquement une proposition (p) — afin d'en établir la valeur de vérité : vraie dans le cas où l'opérande est vrai, et fausse lorsqu'il est faux.
p | p |
---|---|
V | V |
F | F |
La négation logique est une opération qui inverse la valeur de l'opérande auquel elle est appliquée : il prend valeur de faux lorsqu'il est vrai, et de vrai lorsqu'il est faux. L'opérateur de la négation est symbolisé par les signes « ¬ » ou « ~ ».
p | ¬p |
---|---|
V | F |
F | V |
Une opération binaire est une opération à deux arguments (p et q par exemple), chacun pouvant être vrai ou faux (p {V, F} ; q {V, F}) : leur combinaison (p x q) donne ainsi 2² = 4 manières de combiner leur valeur de vérité.
p | q | p | q | ||
V | V | ||||
V | F | ||||
F | V | ||||
F | F |
Chacune de ces 2² combinaisons d'entrée ayant elles-mêmes deux résultats possibles (« [{V, F} x {V, F}] → {V,F} »), on obtient ainsi 4² = 16 fonctions de vérité, décrites par les 16 colonnes de la table suivante :
Où V = vrai et F = Faux.
On a également que les opérateurs ꓕ, ↓, ⊕, ↑, ꓥ, ↔, ꓦ, et T sont commutatifs - P opérateur Q = Q opérateur P.
Une conjonction logique est une opération logique sur deux valeurs de vérité, typiquement les valeurs de deux propositions, qui produit une valeur vraie si ses deux opérandes sont vrais. La table de vérité pour p et q (aussi noté p ∧ q, Kpq, ou p & q) est la suivante:
p | q | p ∧ q |
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Nous pouvons aussi dire que, si p, p ∧ q est q, sinon p ∧ q est égal à p.
Une disjonction logique est une opération logique sur deux valeurs de vérité, typiquement les valeurs de deux propositions, qui produit une valeur vraie si au moins un des opérandes est vrai.
La table de vérité pour p OU q (aussi noté p ∨ q, Apq, p || q ou p + q) est la suivante :
p | q | p ∨ q |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
Une implication logique est une opération logique sur deux valeurs de vérité, typiquement les valeurs de deux propositions, qui produit une valeur fausse seulement dans le cas où le premier opérande est vrai, et le second est faux. La table de vérité associée à l'implication si p alors q (aussi noté p → q) et l'implication logique p implique q (aussi noté p ⇒ q, ou encore Cpq) est la suivante :
p | q | p → q |
---|---|---|
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
Il peut également être noté p → q qui équivaut à ¬p ∨ q.
Une équivalence logique (également connue sous le nom de biconditionelle) est une opération logique sur deux valeurs de vérité, typiquement les valeurs de deux propositions, qui produit une valeur vraie si les deux opérandes sont faux ou vrais. La table de vérité pour p XNOR q (écrit aussi p ↔ q, Epq, p = q, ou p ≡ q) est la suivante :
p | q | p ≡ q |
---|---|---|
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Une disjonction exclusive est une opération logique sur deux valeurs de vérité, typiquement les valeurs de deux propositions, qui produit une valeur vraie si une et une seule des deux des opérandes est une valeur vraie. La table de vérité pour p XOR q (aussi noté p ⊕ q, Jpq, ou p ≠ q) est la suivante:
p | q | p ⊕ q |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Pour deux propositions, XOR peut également être noté (p ∧ ¬q) ∨ (¬p ∧ q).
Le NON-ET est une opération logique sur deux valeurs de vérité, typiquement les valeurs de deux propositions, qui produit une valeur fausse si les deux opérandes sont vrais. En d'autres termes, il produit une valeur vraie si au moins un de ses opérandes est faux. La table de vérité de p NAND q (aussi noté p ↑ q, Dpq, ou p | q) est la suivante :
p | q | p ↑ q |
---|---|---|
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Il est souvent utile d'exprimer une opération logique comme une opération composée, qui est, construite ou composé d'autres opérations logiques. Beaucoup de ces compositions sont possibles, et dépendent des opérations qui sont prises comme base, et les opérations qui sont prises en composite.
La négation d'une conjonction: ¬(p ∧ q), et de la disjonction de négations: (¬p) ∨ (¬q) peuvent être 'totalisées' comme suit:
p | q | p ∧ q | ¬(p ∧ q) | ¬p | ¬q | (¬p) ∨ (¬q) |
---|---|---|---|---|---|---|
0 | 0 | 0 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | 0 | 0 | 0 | 0 |
Le NON-OU logique est une opération logique sur deux valeurs de vérité, typiquement les valeurs de deux propositions, qui produit une valeur vraie si ses deux opérandes sont fausses. En d'autres termes, il produit une valeur fausse, si au moins l'un de ses opérandes est vrai. ↓ est également connu sous le nom de la flèche de Peirce, nom provenant de son inventeur, Charles Sanders Peirce.
La table de vérité de p NOR q (aussi noté p ↓ q, Xpq, ou ¬(p ∨ q)) est la suivante :
p | q | p ↓ q |
---|---|---|
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 0 |
La négation d'une disjonction ¬(p ∨ q), et la conjonction de négations (¬p) ∧ (¬q) peuvent être décomposées sous forme de tableau comme suit :
p | q | p ∨ q | ¬(p ∨ q) | ¬p | ¬q | (¬p) ∧ (¬q) |
---|---|---|---|---|---|---|
0 | 0 | 0 | 1 | 1 | 1 | 1 |
0 | 1 | 1 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 0 | 0 | 1 | 0 |
1 | 1 | 1 | 0 | 0 | 0 | 0 |
Les premières et les secondes expressions de chaque paire sont logiquement équivalentes, et peuvent être substituées les unes les autres dans tout contextes qui se rapportent uniquement à leurs valeurs logiques.
Cette équivalence est l'une des lois de De Morgan.
Les tables de vérité peuvent être utilisées pour prouver beaucoup d'autres équivalences logique. Par exemple, considérons la table de vérité suivante:
p | q | ¬p | ¬p ∨ q | p → q |
---|---|---|---|---|
0 | 0 | 1 | 1 | 1 |
0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 1 | 1 |
Ceci démontre que p → q est logiquement équivalent à ¬p ∨ q.
Voici une table de vérité donnant la définition des 6 fonctions de vérité les plus couramment utilisée des 16 possibles de 2 variables binaires (P, Q sont ainsi des variables booléennes)[4] :
0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
Légende :
Les opérateurs logiques peuvent également être représentés à l'aide de diagrammes de Venn.
Pour les opérateurs binaires, une forme condensée de table de vérité est également utilisée[réf. nécessaire] où les en-têtes de colonnes et de lignes spécifient les opérandes, et les cellules du tableau précisent le résultat. Par exemple, la logique booléenne utilise cette notation :
|
|
Cette notation est particulièrement utile si les opérations sont commutatives. Sa forme est rapidement reconnaissable à partir de la distribution des valeurs dans le tableau, ce qui peut aider le lecteur à saisir les règles plus rapidement.
Tables de vérité en logique numérique
Les tables de vérité sont également utilisées pour spécifier la fonction des tables de correspondance (LUT en anglais) dans les circuits logiques numériques. Pour une LUT à n entrées, la table de vérité aura 2n valeurs (ou lignes dans le format tabulaire ci-dessus), spécifiant complètement une fonction booléenne pour la LUT. En représentant chaque valeur booléenne sous la forme d'un bit dans un nombre binaire, les valeurs de la table de vérité peuvent être efficacement codées sous forme de valeurs entières dans le logiciel EDA (Electronic Design Automation). Par exemple, un entier 32 bits peut coder la table de vérité pour une LUT avec jusqu'à 5 entrées. Lorsque vous utilisez une représentation entière d'une table de vérité, la valeur de sortie de la LUT peut être obtenue en calculant un indice binaire k sur la base des valeurs d'entrée de la LUT, auquel cas la valeur de sortie de la LUT est le ke bit de l'entier. Les tables de vérité sont un moyen simple et direct d'encoder des fonctions booléennes, mais étant donné la croissance exponentielle de la taille à mesure que le nombre d'entrées augmente, elles ne conviennent pas aux fonctions avec un grand nombre d'entrées. D'autres représentations plus efficaces en mémoire sont les équations de texte et les diagrammes de décision binaires.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.