Une table de vérité est un tableau mathématique utilisé en logique — notamment en algèbre de Boole , en fonctions booléennes et en calcul propositionnel — qui présente les valeu...
Une table de vérité comporte une colonne pour chaque variable d'entrée (par exemple, A et B), et une dernière colonne indiquant le résultat de l'opération logique qu'elle représente (par exemple, A OU exclusif B ). Chaque ligne de la table de vérité contient une configuration possible des variables d'entrée (par exemple, A = vrai, B = faux) et le résultat de l'opération pour ces valeurs.
La table de vérité d'une proposition est une représentation graphique de sa fonction de vérité . La fonction de vérité peut s'avérer plus utile à des fins mathématiques, bien que les deux représentations contiennent la même information.
Ludwig Wittgenstein est généralement crédité de l'invention et de la popularisation de la table de vérité dans son Tractatus Logico-Philosophicus , achevé en 1918 et publié en 1921. Un tel système a également été proposé indépendamment en 1921 par Emil Leon Post .
En 1997, John Shosky découvrit, au verso d'une page de la transcription dactylographiée de la conférence de Bertrand Russell de 1912 sur « La philosophie de l'atomisme logique », des matrices de tables de vérité. La matrice de la négation est de Russell, et à côté figure la matrice de l'implication matérielle, de la main de Ludwig Wittgenstein. Il est démontré qu'un manuscrit inédit, attribué à Peirce et datant de 1893, contient une matrice de table de vérité équivalente à celle de l'implication matérielle découverte par John Shosky. Un autre manuscrit inédit de Peirce, daté de 1883-1884 et lié à la rédaction de son article « Sur l'algèbre de la logique : une contribution à la philosophie de la notation », paru dans l' American Journal of Mathematics en 1885, présente un exemple de table de vérité indirecte pour la conditionnelle.
Applications
Les tables de vérité peuvent servir à démontrer de nombreuses autres équivalences logiques . Par exemple, considérons la table de vérité suivante :
logiquement équivalent à .
Table de vérité des portes logiques
Voici une table de vérité qui donne les définitions de chacune des 6 fonctions possibles d' une porte logique à 2 entrées de deux variables booléennes P et Q :
oùTsignifie vrai etla logique booléenne utilise cette notation de table de vérité condensée :
tables de consultation (LUT) matérielles dans circuits logiques numériques . Pour une LUT à n entrées, la table de vérité comporte valeurs (ou lignes, selon le format tabulaire présenté ci-dessus), définissant complètement la fonction booléenne de la LUT. En représentant chaque valeur booléenne par un bit binaire , les valeurs de la table de vérité peuvent être efficacement encodées sous forme d'entiers dans les logiciels de CAO électronique (EDA) . Par exemple, un entier 32 bits permet d'encoder la table de vérité d'une LUT à 5 entrées maximum.
Lorsqu'on utilise 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 à partir des valeurs d'entrée de la LUT. Dans ce cas, la valeur de sortie de la LUT correspond au k -ième bit de l'entier. Par exemple, pour évaluer la valeur de sortie d'une LUT étant donné un tableau de n valeurs d'entrée booléennes, l'indice binaire de la valeur de sortie de la table de vérité peut être calculé comme suit : si la i -ème entrée est vraie, soit 1 ; sinon , soit 0. Le k -ième bit de la représentation binaire de la table de vérité correspond alors à la valeur de sortie de la LUT.
Les tables de vérité constituent une méthode simple et directe pour encoder les fonctions booléennes ; cependant, compte tenu de la croissance exponentielle de leur taille avec l’augmentation du nombre d’entrées, elles ne conviennent pas aux fonctions comportant un grand nombre d’entrées. D’autres représentations, plus économes en mémoire, sont les équations textuelles et les diagrammes de décision binaire .
Applications des tables de vérité en électronique numérique
En électronique numérique et en informatique (domaines de l'ingénierie logique appliquée et des mathématiques), les tables de vérité permettent de réduire les opérations booléennes de base à de simples corrélations entre entrées et sorties, sans recourir à des portes logiques ni à du code. Par exemple, une addition binaire peut être représentée par la table de vérité suivante :
Addition binaire
additionneur complet .
des variables propositionnelles , différents auteurs ont des recommandations différentes sur la façon de les remplir, bien que cela n'ait aucune signification logique.
Méthode alternée
Lee Archie, professeur à l'université Lander , recommande cette procédure, qui est couramment suivie dans les tables de vérité publiées :
Écrivez le nombre de variables (correspondant au nombre d'instructions) par ordre alphabétique.
Le nombre de lignes nécessaires est de 2<sup> n</sup> où n est le nombre de variables. (Par exemple, avec trois variables, 2 <sup>3</sup> = 8).
Commencez par la colonne de droite et alternez Stephen Cole Kleene :
Colin Howson , quant à lui, estime que « c'est une bonne règle pratique » de faire ce qui suit :
On commence par tous les V, puis on examine les trois façons de combiner deux V avec un F, puis les trois façons de combiner un V avec deux F, et on termine par tous les F. Si un composé est construit à partir de n lettres distinctes, sa table de vérité comportera 2ⁿ lignes , car il y a deux façons d'attribuer V ou F à la première lettre, et pour chacune de ces combinaisons, il y aura deux façons d'attribuer V ou F à la deuxième, et pour chacune de ces combinaisons, il y aura deux façons d'attribuer V ou F à la troisième, et ainsi de suite, ce qui donne 2, 2, 2, …, n fois, soit 2ⁿ .
Cela donne lieu à des tables de vérité comme celle-ci « montrant que fonctionnellement équivalents en termes de vérité », inspirée d'une table produite par Howson :
double exponentiel 2ⁿ .
n
2 n
2 2 n
0
1
2
1
2
4
2
4
16
3
8
256
4
16
65 536
5
32
4 294 967 296
≈ 4,3
F
T
De même, un multiplexeur 4 vers 1 avec des entrées de sélection et , des entrées de données multiplexeur 4 vers 1
Z
F
F
commutatif – associatif – opération duale obtenue en intervertissant V et F, et ET et OU.
La ligne L id indique les identités gauches de l'opérateur s'il a des valeurs les identités droites de l'opérateur s'il a des valeurs Tractatus Logico-Philosophicus , Wittgenstein a listé le tableau ci-dessus comme suit :
La valeur de sortie est toujours vraie, car cet opérateur n'a pas d'opérandes et donc aucune valeur d'entrée.
p
p
L'identité logique est une opération sur une valeur logique p, pour laquelle la valeur de sortie reste p.
La table de vérité de l'opérateur d'identité logique est la suivante :
p
La négation logique est une opération sur une valeur logique , généralement la valeur d'une proposition , qui produit une valeur vraie si son opérande est faux et une valeur fausse si son opérande est vrai.
La table de vérité de NON p (également écrite ¬p , Np , Fpq , ou ~p ) est la suivante :
p
fonctions de vérité possibles pour deux variables binaires , chaque opérateur ayant son propre nom.
La table de vérité de p ET q (également écrite p ∧ q , Kpq , p & q , ou p q ) est la suivante :
p
q
p ∧ q
La disjonction logique est une opération sur deux valeurs logiques , généralement les valeurs de deux propositions , qui produit une valeur vraie si au moins un de ses opérandes est vrai.
La table de vérité de p OU q (également écrite p ∨ q , Apq , p || q , ou p + q ) est la suivante :
p
q
p ∨ q
conditionnelle matérielle sont toutes deux associées à une opération sur deux valeurs logiques , généralement les valeurs de deux propositions , qui produit une valeur fausse si le premier opérande est vrai et le second opérande est faux, et une valeur vraie sinon.
La table de vérité associée à l'implication logique p implique q (symbolisée p ⇒ q , ou plus rarement Cpq ) est la suivante :
p
q
p ⇒ q
p
q
p → q
L'égalité logique (également connue sous le nom de biconditionnelle ou de ni exclusif ) est une opération sur deux valeurs logiques , généralement les valeurs de deux propositions , qui produit une valeur vraie si les deux opérandes sont faux ou si les deux opérandes sont vrais.
La table de vérité de p XNOR q (également écrite p ↔ q , Epq , p = q , ou p ≡ q ) est la suivante :
p
q
p ↔ q
valeur de vérité (tous deux vrais ou tous deux faux), et faux s'ils ont des valeurs de vérité différentes.
La table de vérité de p XOR q (également écrite Jpq ou p ⊕ q ) est la suivante :
p
q
p ⊕ q
logique NAND est une opération sur deux valeurs logiques , généralement les valeurs de deux propositions , qui produit la valeur faux si ses deux opérandes sont vrais. Autrement dit, elle produit la valeur vrai si au moins un de ses opérandes est faux.
La table de vérité de p NAND q (également écrite p ↑ q , Dpq , ou p | q ) est la suivante :
p
q
p ↑ q
opération composée , c'est-à-dire comme une opération construite ou composée à partir d'autres opérations. De nombreuses compositions de ce type sont possibles, selon les opérations considérées comme basiques ou « primitives » et celles considérées comme composées ou « dérivées ».
Dans le cas de la porte logique NAND, elle peut clairement être exprimée comme une combinaison des portes NON et ET.
La négation d'une conjonction : ¬( p ∧ q ), et la disjonction des négations : (¬ p ) ∨ (¬ q ) peuvent être tabulées comme suit :
Worldlex Wiki