Logique des propositions/Définitions

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Syntaxe et sémantique de la logique des propositions

Objets de base

• Un ensemble de propositions de base, appelées atomes ou propositions atomiques :

$a,b,c,\dots$

• Un ensemble de connecteurs qui seront :
  • unaires : ne s'applique qu’à un atome
    • la négation ou non, qui s'écrit $\lnot$.
      Exemple : $\lnot a$ qui se prononce « non a ».
  • binaires : s'applique à deux atomes
    • la conjonction ou « et », qui s'écrit $\land$.
      Exemple : $a\land b$ qui se prononce « a et b » ou « la conjonction de a et de b ».
    • la disjonction ou « ou », qui s'écrit $\lor$.
      Exemple :$a\lor b$ qui se prononce « a ou b » ou « la disjonction de a et de b ».
    • le conditionnel ou « si… alors… », qui s'écrit $\to$.
      Exemple : $a\to b$ qui se prononce « si a, alors b » ou « le conditionnel dont l'antécédent est a et dont le conséquent est b ».
    • le biconditionnel ou « … si et seulement si… », qui s'écrit $\leftrightarrow$.
      Exemple : $a\leftrightarrow b$ qui se prononce « a si et seulement si b » ou « le biconditionnel de a et b ».

Règles syntaxiques

• Règle 1 : Une proposition atomique est une proposition.
• Règle 2 : Si « $a$ » est une proposition, alors « $\lnot a$ » est une proposition.
• Règle 3 : Si « $a$ » et « $b$ » sont des propositions, alors « $a\land b$ » est une proposition.
• Règle 4 : Si « $a$ » et « $b$ » sont des propositions, alors « $a\lor b$ » est une proposition.
• Règle 5 : Si « $a$ » et « $b$ » sont des propositions, alors « $a\to b$ » est une proposition.
• Règle 6 : Si « $a$ » et « $b$ » sont des propositions, alors « $a\leftrightarrow b$ » est une proposition.
• Règle 7 : Rien d’autre n'est une proposition.

Début de l'exemple

Exemple

Si $a,b,c,d,e$ sont des propositions atomiques, alors

${\Bigl (}{\bigl (}a\land b{\bigr )}\lor {\bigl (}\lnot c\to d{\bigr )}{\Bigr )}\leftrightarrow {\bigl (}\lnot e\to \lnot {\Bigl (}d\to \lnot c{\bigr )}{\Bigr )}$

est une proposition.

Fin de l'exemple

Méthode pour vérifier si une expression est bien formée

Pour cela, on décompose l'énoncé grâce à un arbre syntaxique :

On obtient, après décomposition, chaque atome présent dans l'énoncé initial ; aucun connecteur n'est resté : l'énoncé est donc bien une e.b.f..

Règles sémantiques

• Règle 1 : Les propositions atomiques sont affectées de la valeur de vérité VRAI (V) ou FAUX (F).
• Règle 2 : Si "$a$" est une proposition, alors la valeur de vérité de $\lnot a$ est :
  • V si celle de $a$ est F
  • F si celle de $a$ est V
• Règle 3 : Si "$a$" et "$b$" sont des propositions, la valeur de vérité de $a\land b$ est :
  • V si et seulement si les valeurs de vérité de $a$ et de $b$ sont V
  • F si l'une des valeurs de vérité de $a$ ou $b$ est F
• Règle 4 : Si "$a$" et "$b$" sont des propositions, la valeur de vérité de $a\lor b$ est :
  • V si l'une des valeurs de vérité de $a$ ou $b$ est V
  • F si et seulement si les valeurs de vérité de $a$ et de $b$ sont F
• Règle 5 : Si "$a$" et "$b$" sont des propositions, la valeur de vérité de $a\to b$ est V dans tous les cas SAUF si la valeur de vérité de l' antécédent ($a$) est V et que la valeur de vérité du conséquent ($b$) est F.
• Règle 6 : Si "$a$" et "$b$" sont des propositions, la valeur de vérité de $a\leftrightarrow b$ est V si et seulement si $a$ et $b$ ont la même valeur de vérité.

Tableau de vérité de la négation (¬a)

$a$	V	F
$\lnot a$	F	V

Tableau de vérité de la conjonction (a∧b)

$a\land b$	V	F
V	V	F
F	F	F

Tableau de vérité de la disjonction (a∨b)

$a\lor b$	V	F
V	V	V
F	V	F

Tableau de vérité du conditionnel (a→b)

$a\to b$	V	F
V	V	F
F	V	V

Tableau de vérité du biconditionnel (a↔b)

$a\leftrightarrow b$	V	F
V	V	F
F	F	V

Démonstration

Reprenons l'exemple précèdent :

On va attribuer une valeur de vérité à chaque atome (soit vrai soit faux) puis voir ce que nous révèle l'arbre ci-dessus vis-à-vis de la valeur vérité de l'énoncé de départ :

• On suppose que les valeurs de vérité de $a,b,c,d,e$ sont respectivement dans cet ordre : V, V, F, F, V.
• On va partir du bas de l'arbre qu'on appelle les feuilles, écrire la valeur de vérité de chaque feuille/atome à côté de ce dernier, puis remonter au nœud supérieur, ainsi de suite jusqu'à la racine en se servant des tableaux de vérité plus haut :

Partons par exemple du $c$ qui est complètement à droite : On a supposé que sa valeur de vérité était faux.

Au-dessus, nous avons $\lnot c$, qui sera donc vrai.

À côté de $\lnot c$, on a $d$, qui est faux.

La formule du dessus, $(d\to \lnot c)$, si l’on se réfère au tableau de vérité du conditionnel, on a F $\to$ V qui nous donne V.

Si on remonte d'un niveau, on a $\lnot (d\to \lnot c)$, qui sera donc faux puisque c’est la négation d'un énoncé vrai.

On remonte ainsi de suite jusqu'à la racine comme cela :

On obtient ainsi ${\Bigl (}{\bigl (}a\land b{\bigr )}\lor {\bigl (}\lnot c\to d{\bigr )}{\Bigr )}\leftrightarrow {\bigl (}\lnot e\to \lnot {\Bigl (}d\to \lnot c{\bigr )}{\Bigr )}$ qui est VRAI avec cette distribution des valeurs de vérités aux atomes : il est important de souligner que si l’on change la distribution initiale, le résultat final peut changer à tout moment.

Pour vous entraîner, essayez de refaire cet exercice en changeant la distribution :

Par exemple :

• F,F,F,F,F
• V,V,V,V,V
• F,V,F,V,F
• ...