Fonction vérité - Truth function

En logique , une fonction de vérité est une fonction qui accepte des valeurs de vérité comme entrée et produit une valeur de vérité unique comme sortie. En d'autres termes: l'entrée et la sortie d'une fonction de vérité sont toutes des valeurs de vérité; une fonction de vérité produira toujours exactement une valeur de vérité; et l'entrée de la ou des mêmes valeurs de vérité produira toujours la même valeur de vérité. L'exemple typique est dans la logique propositionnelle , dans laquelle une instruction composée est construite en utilisant des instructions individuelles reliées par des connecteurs logiques ; si la valeur de vérité de la déclaration composée est entièrement déterminée par la ou les valeurs de vérité de la ou des déclarations constituantes, la déclaration composée est appelée une fonction de vérité , et tous les connecteurs logiques utilisés sont dits fonctionnels de la vérité .

La logique propositionnelle classique est une logique fonctionnelle de la vérité, en ce que chaque déclaration a exactement une valeur de vérité qui est vraie ou fausse, et chaque connecteur logique est fonctionnel de vérité (avec une table de vérité correspondante ), ainsi chaque déclaration composée est une fonction de vérité. D'un autre côté, la logique modale n'est pas fonctionnelle de la vérité.

Aperçu

Un connectif logique est fonctionnel de la vérité si la valeur de vérité d'une phrase composée est une fonction de la valeur de vérité de ses sous-phrases. Une classe de connecteurs est fonctionnelle de la vérité si chacun de ses membres l'est. Par exemple, le connectif " et " est fonctionnel car une phrase comme "Les pommes sont des fruits et les carottes sont des légumes " est vraie si et seulement si chacune de ses sous-phrases "les pommes sont des fruits " et "les carottes sont des légumes " est vrai, et c'est faux autrement. Certains connecteurs d'une langue naturelle, comme l'anglais, ne sont pas fonctionnels avec la vérité.

Les connecteurs de la forme "x croit que ..." sont des exemples typiques de connecteurs qui ne sont pas fonctionnels en fonction de la vérité. Si, par exemple, Mary croit à tort qu'Al Gore était président des États-Unis le 20 avril 2000, mais qu'elle ne croit pas que la lune est faite de fromage vert, alors la phrase

" Mary pense qu'Al Gore était président des États-Unis le 20 avril 2000 "

est vrai alors que

" Mary croit que la lune est faite de fromage vert "

c'est faux. Dans les deux cas, chaque phrase composante (c'est-à-dire " Al Gore était président des États-Unis le 20 avril 2000 " et " la lune est faite de fromage vert ") est fausse, mais chaque phrase composée formée en préfixant la phrase " Mary croit que "diffère en valeur de vérité. C'est-à-dire que la valeur de vérité d'une phrase de la forme « Mary croit que ... » n'est pas déterminée uniquement par la valeur de vérité de sa phrase composante, et donc le connectif ( unaire) (ou simplement l' opérateur car il est unaire ) n'est pas fonctionnelle de la vérité.

La classe des connecteurs logiques classiques (par exemple & , ) utilisés dans la construction des formules est fonctionnelle de la vérité. Leurs valeurs pour diverses valeurs de vérité comme argument sont généralement données par des tables de vérité . Le calcul propositionnel fonctionnel de la vérité est un système formel dont les formules peuvent être interprétées comme vraies ou fausses.

Tableau des fonctions de vérité binaire

Dans une logique à deux valeurs, il y a seize fonctions possibles de vérité, aussi appelées fonctions booléennes , de deux entrées P et Q . Chacune de ces fonctions correspond à une table de vérité d'un certain connectif logique en logique classique, comprenant plusieurs cas dégénérés comme une fonction ne dépendant pas de l'un ou des deux de ses arguments. La vérité et le mensonge sont notés respectivement 1 et 0 dans les tableaux de vérité suivants par souci de concision.

Contradiction / Faux
Notation
Formules équivalentes
Table de vérité Diagramme de Venn

"bas"
P ∧ ¬ P
O pq
  Q
0 1
P 0    0   0 
1    0   0 
Venn0000.svg


Tautologie / Vrai
Notation
Formules équivalentes
Table de vérité Diagramme de Venn

"Haut"
P ∨ ¬ P
V pq
  Q
0 1
P 0    1   1 
1    1   1 
Venn1111.svg


Proposition P
Notation
Formules équivalentes
Table de vérité Diagramme de Venn
P p
je pq
  Q
0 1
P 0    0   0 
1    1   1 
Venn0101.svg


Négation de P
Notation
Formules équivalentes
Table de vérité Diagramme de Venn
¬ P
~ P
N p
F pq
  Q
0 1
P 0    1   1 
1    0   0 
Venn1010.svg


Proposition Q
Notation
Formules équivalentes
Table de vérité Diagramme de Venn
Q q
H pq
  Q
0 1
P 0    0   1 
1    0   1 
Venn0011.svg


Négation de Q
Notation
Formules équivalentes
Table de vérité Diagramme de Venn
¬ Q
~ Q
N q
G pq
  Q
0 1
P 0    1   0 
1    1   0 
Venn1100.svg


Conjonction
Notation
Formules équivalentes
Table de vérité Diagramme de Venn
P Q
P & Q
P   ·   Q
P  ET  Q
P ↛¬ Q
¬ P Q
¬ P ↓ ¬ Q
K pq
  Q
0 1
P 0    0   0 
1    0   1 
Venn0001.svg


Déni alternatif
Notation
Formules équivalentes
Table de vérité Diagramme de Venn
P Q
P | Q
P  NAND  Q
P → ¬ Q
¬ P Q
¬ P ∨ ¬ Q
D pq
  Q
0 1
P 0    1   1 
1    1   0 
Venn1110.svg


Disjonction
Notation
Formules équivalentes
Table de vérité Diagramme de Venn
P Q
P  OU  Q
P ← ¬ Q
¬ P Q
¬ P ↑ ¬ Q
¬ (¬ P ∧ ¬ Q )
A pq
  Q
0 1
P 0    0   1 
1    1   1 
Venn0111.svg


Déni conjoint
Notation
Formules équivalentes
Table de vérité Diagramme de Venn
P Q
P  NOR  Q
P ↚ ¬ Q
¬ P Q
¬ P ∧ ¬ Q
X pq
  Q
0 1
P 0    1   0 
1    0   0 
Venn1000.svg


Non-implication matérielle
Notation
Formules équivalentes
Table de vérité Diagramme de Venn
P Q
P Q P Q
P ∧ ¬ Q
¬ P Q
¬ P ↚ ¬ Q
L pq
  Q
0 1
P 0    0   0 
1    1   0 
Venn0100.svg


Implication matérielle
Notation
Formules équivalentes
Table de vérité Diagramme de Venn
P Q
P Q
P Q
P ↑ ¬ Q
¬ P Q
¬ P ← ¬ Q
C pq
  Q
0 1
P 0    1   1 
1    0   1 
Venn1011.svg


Nonimplication Converse
Notation
Formules équivalentes
Table de vérité Diagramme de Venn
P Q
P Q P Q
P ↓ ¬ Q
¬ P Q
¬ P ↛ ¬ Q
M pq
  Q
0 1
P 0    0   1 
1    0   0 
Venn0010.svg


Implication réciproque
Notation
Formules équivalentes
Table de vérité Diagramme de Venn
P Q
P Q
P Q
P ∨ ¬ Q
¬ P Q
¬ P → ¬ Q
B pq
  Q
0 1
P 0    1   0 
1    1   1 
Venn1101.svg


Disjonction exclusive
Notation
Formules équivalentes
Table de vérité Diagramme de Venn
P Q
P Q
P Q
P  XOR  Q
P ¬ Q ¬ P Q ¬ P ↮ ¬ Q J pq


  Q
0 1
P 0    0   1 
1    1   0 
Venn0110.svg


Biconditionnel
Notation
Formules équivalentes
Table de vérité Diagramme de Venn
P Q PQ P  XNOR  Q P  IFF  Q


P ↮ ¬ Q
¬ P Q
¬ P ¬ Q E pq
  Q
0 1
P 0    1   0 
1    0   1 
Venn1001.svg


Exhaustivité fonctionnelle

Du fait qu'une fonction peut être exprimée sous la forme d'une composition , un calcul logique fonctionnel de vérité n'a pas besoin d'avoir des symboles dédiés pour que toutes les fonctions mentionnées ci-dessus soient fonctionnellement complètes . Ceci est exprimé dans un calcul propositionnel comme l'équivalence logique de certains énoncés composés. Par exemple, la logique classique a ¬ P  ∨  Q équivalent à P  →  Q . L'opérateur conditionnel "→" n'est donc pas nécessaire pour un système logique classique si "¬" (non) et "∨" (ou) sont déjà utilisés.

Un ensemble minimal d'opérateurs qui peuvent exprimer chaque instruction exprimable dans le calcul propositionnel est appelé un ensemble fonctionnellement complet minimal . Un ensemble minimalement complet d'opérateurs est obtenu par NAND seul {↑} et NOR seul {↓}.

Voici les ensembles minimaux d'opérateurs fonctionnellement complets dont les arités ne dépassent pas 2:

Un élément
{↑}, {↓}.
Deux éléments
, , , , , , , , , , , , , , , , , .
Trois éléments
, , , , , .

Propriétés algébriques

Certaines fonctions de vérité possèdent des propriétés qui peuvent être exprimées dans les théorèmes contenant le connectif correspondant. Certaines de ces propriétés qu'une fonction de vérité binaire (ou un connecteur logique correspondant) peut avoir sont:

  • associativité : dans une expression contenant au moins deux des mêmes connecteurs associatifs dans une ligne, l'ordre des opérations n'a pas d'importance tant que la séquence des opérandes n'est pas modifiée.
  • commutativité : les opérandes du connectif peuvent être permutés sans affecter la valeur de vérité de l'expression.
  • distributivité : Un connectif noté · distribue sur un autre connectif noté +, si a · ( b + c ) = ( a · b ) + ( a · c ) pour tous les opérandes a , b , c .
  • idempotence : chaque fois que les opérandes de l'opération sont les mêmes, le connectif donne l'opérande comme résultat. En d'autres termes, l'opération préserve à la fois la vérité et le mensonge (voir ci-dessous).
  • absorption : Une paire de connecteurs satisfait la loi d'absorption si pour tous les opérandes a , b .

Un ensemble de fonctions de vérité est fonctionnellement complet si et seulement si pour chacune des cinq propriétés suivantes il contient au moins un membre qui en manque:

  • monotone : Si f ( a 1 , ..., a n ) ≤ f ( b 1 , ..., b n ) pour tout a 1 , ..., a n , b 1 , ..., b n ∈ {0,1} tel que a 1 b 1 , a 2 b 2 , ..., a n b n . Par exemple, .
  • affine : Pour chaque variable, la modification de sa valeur change toujours ou jamais la valeur de vérité de l'opération, pour toutes les valeurs fixes de toutes les autres variables. Par exemple, , .
  • self dual : Lire les attributions de valeur de vérité pour l'opération de haut en bas sur sa table de vérité revient à prendre le complément de la lecture de bas en haut; en d'autres termes, f a 1 , ..., ¬ a n ) = ¬ f ( a 1 , ..., a n ). Par exemple, .
  • préservation de la vérité : L'interprétation selon laquelle toutes les variables se voient attribuer une valeur de vérité de «vrai» produit une valeur de vérité de «vrai» à la suite de ces opérations. Par exemple, . (voir validité )
  • préservation du mensonge : L'interprétation selon laquelle toutes les variables se voient attribuer une valeur de vérité de «faux» produit une valeur de vérité de «faux» à la suite de ces opérations. Par exemple, . (voir validité )

Arity

Une fonction concrète peut également être appelée un opérateur . Dans la logique à deux valeurs, il existe 2 opérateurs nulles (constantes), 4 opérateurs unaires , 16 opérateurs binaires , 256 opérateurs ternaires et n -opérateurs. Dans la logique à trois valeurs il existe 3 opérateurs nulaires (constantes), 27 opérateurs unaires , 19683 opérateurs binaires , 7625597484987 opérateurs ternaires et n opérateurs -aire. Dans la logique à valeurs k , il existe k opérateurs nullaires, opérateurs unaires, opérateurs binaires, opérateurs ternaires et opérateurs n -ary. Un opérateur n -ary dans la logique à k valeurs est une fonction de . Par conséquent, le nombre de ces opérateurs est , c'est ainsi que les nombres ci-dessus ont été dérivés.

Cependant, certains des opérateurs d'une arité particulière sont en fait des formes dégénérées qui effectuent une opération de moindre arité sur certaines des entrées et ignorent le reste des entrées. Sur les 256 opérateurs booléens ternaires cités ci-dessus, parmi eux sont des formes dégénérées d'opérateurs binaires ou de moindre arité, utilisant le principe d'inclusion – exclusion . L'opérateur ternaire est l'un de ces opérateurs qui est en fait un opérateur unaire appliqué à une entrée et ignorant les deux autres entrées.

"Non" est un opérateur unaire , il prend un seul terme (¬ P ). Les autres sont des opérateurs binaires , prenant deux termes pour faire une déclaration composée ( P Q , P Q , P Q , P Q ).

L'ensemble des opérateurs logiques Ω peut être partitionné en sous-ensembles disjoints comme suit:

Dans cette partition, se trouve l'ensemble des symboles d'opérateurs d' arité j .

Dans les calculs propositionnels plus familiers, est typiquement partitionné comme suit:

opérateurs nulles:
opérateurs unaires:
opérateurs binaires:

Principe de compositionnalité

Au lieu d'utiliser des tables de vérité , les symboles conjonctifs logiques peuvent être interprétés au moyen d'une fonction d'interprétation et d'un ensemble fonctionnellement complet de fonctions de vérité (Gamut 1991), comme détaillé par le principe de compositionnalité du sens. Soit I une fonction d'interprétation, soit Φ , Ψ deux phrases quelconques et que la fonction de vérité f n et soit définie comme:

  • f nand (T, T) = F; f nand (T, F) = f nand (F, T) = f nand (F, F) = T

Ensuite, pour plus de commodité, f pas , f ou f et et ainsi de suite sont définis au moyen de f nand :

  • f pas ( x ) = f nand ( x , x )
  • f ou ( x , y ) = f nand ( f pas ( x ), f pas ( y ))
  • f et ( x , y ) = f pas ( f nand ( x , y ))

ou, en variante f pas , f ou f et et ainsi de suite sont définis directement:

  • f pas (T) = F; f pas (F) = T;
  • f ou (T, T) = f ou (T, F) = f ou (F, T) = T; f ou (F, F) = F
  • f et (T, T) = T; f et (T, F) = f et (F, T) = f et (F, F) = F

Puis

  • I (~) = I ( ) = f pas
  • I (&) = I ( ) = f et
  • I ( v ) = I ( ) = f ou
  • I (~ Φ ) = I ( Φ ) = I ( ) ( I ( Φ )) = f pas ( I ( Φ ))
  • I ( Φ Ψ ) = I ( ) ( I ( Φ ), I ( Ψ )) = f et ( I ( Φ ), I ( Ψ ))

etc.

Ainsi, si S est une phrase qui est une chaîne de symboles constituée de symboles logiques v 1 ... v n représentant des connecteurs logiques, et de symboles non logiques c 1 ... c n , alors si et seulement si I ( v 1 ) ... I ( v n ) ont été fournis en interprétant v 1 à v n au moyen de f nand (ou de tout autre ensemble de fonctions de vérité complètes fonctionnelles) alors la valeur de vérité de est déterminée entièrement par les valeurs de vérité de c 1 ... c n , c'est-à-dire de I ( c 1 ) ... I ( c n ) . En d'autres termes, comme prévu et requis, S n'est vrai ou faux que sous une interprétation de tous ses symboles non logiques.

L'informatique

Les opérateurs logiques sont implémentés comme des portes logiques dans les circuits numériques . Pratiquement tous les circuits numériques (la principale exception est DRAM ) sont construits à partir de portes NAND , NOR , NOT et de transmission . Les portes NAND et NOR avec 3 entrées ou plus plutôt que les 2 entrées habituelles sont assez courantes, bien qu'elles soient logiquement équivalentes à une cascade de portes à 2 entrées. Tous les autres opérateurs sont implémentés en les décomposant en une combinaison logiquement équivalente de 2 ou plus des portes logiques ci-dessus.

L '«équivalence logique» de «NAND seul», «NOR seul» et «NOT et AND» est similaire à l' équivalence de Turing .

Le fait que toutes les fonctions de vérité peuvent être exprimées avec NOR seul est démontré par l' ordinateur de guidage Apollo .

Voir également

Remarques

Les références

Lectures complémentaires

  • Józef Maria Bocheński (1959), A Précis of Mathematical Logic , traduit des versions française et allemande par Otto Bird, Dordrecht, Hollande méridionale: D. Reidel.
  • Église Alonzo (1944), Introduction à la logique mathématique , Princeton, NJ: Princeton University Press. Voir l'introduction pour une histoire du concept de fonction de vérité.