Logique des propositions/Définitions

**Définitions**
Leçon : Logique des propositions

Chapitre n^o 2
Chap. préc. :	Introduction
Chap. suiv. :	Arbres de Quine

En raison de limitations techniques, la typographie souhaitable du titre, « Logique des propositions : Définitions
Logique des propositions/Définitions », n'a pu être restituée correctement ci-dessus.

Syntaxe et sémantique de la logique des propositions[modifier | modifier le wikicode]

Objets de base[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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.

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.

Méthode pour vérifier si une expression est bien formée[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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)[modifier | modifier le wikicode]

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

Tableau de vérité de la conjonction (a∧b)[modifier | modifier le wikicode]

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

Tableau de vérité de la disjonction (a∨b)[modifier | modifier le wikicode]

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

Tableau de vérité du conditionnel (a→b)[modifier | modifier le wikicode]

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

Tableau de vérité du biconditionnel (a↔b)[modifier | modifier le wikicode]

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

Démonstration[modifier | modifier le wikicode]

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
...

Logique des propositions

Introduction

Arbres de Quine