CHAPITRE 1

LOGIQUE PROPOSITIONNELLE

1.1 INTRODUCTION

En logique mathématique, le calcul propositionnel est la première étape dans la

définition de la logique et du raisonnement.

Quand on parle d’un calcul arithmétique, on dit que c’est un calcul qui s’effectue sur des
nombres en utilisant des opérateurs comme l’addition, la soustraction,…

Par analogie, le calcul propositionnel est un calcul qui s’effectue sur des propositions en
utilisant un certain nombre d’opérateurs appelés connecteurs logique.

Le calcul propositionnel ne s’occupe pas du contenu de la proposition

Pour lui par exemple le fait de dire que « Les gens sont méchants » et « René est
méchant » sont deux propositions complètement différentes malgré que dans la réalité
ces deux propositions sont en liaison vu que René fait partie des gens.

Cette distinction n’est faite que dans le calcul des prédicats qui est bien adapté pour la
représentation des concepts mathématique.

1.2 SYNTAXE DU CALCUL PROPOSITIONNEL

1.2.1 Définition d’une proposition

Une proposition donne une information sur un état de chose.

Une proposition est un énoncé pouvant être vrai ou faux. On dit alors que les deux
valeurs de vérité d’une proposition sont « vrai » et « faux ». A partir d’une ou plusieurs
propositions, on peut en construire d’autres.

Exemple

3=5 est une proposition, « Un carré est un rectangle » est une proposition.

« Il fait beau » est une proposition

Mais « j’espère que vous allez bien » n’est pas une proposition.

« Ferme la porte » n’est pas une proposition

En général, une proposition est déduite à partir des phrases déclaratives affirmative ou
négative

1.2.2 Définition du langage

Le langage propositionnel est formé de :

- Un ensemble de variables propositionnels ou bien propositions atomiques noté P,

Q, R, S,…
- Un ensemble de connecteur logique de base qui sont la conjonction (), la
disjonction(), la négation (), l’implication(), l’équivalence().
- Les parenthèses ( ) utilisées pour lever l’ambigüité entre les différents
connecteurs.
- Deux constantes qui sont le vrai et le faux (V(T), F()).

1.2.3 Formules
On appelle formule ou bien expression bien formée (EBF) ou bien proposition
composé et elle est définie de la manière suivante :
- Si A est une proposition atomique alors A est une formule ou EBF.
- Si A est une formule alors (A) et A sont des formules.
- Si A et B sont des formules alors AB sont des formule avec {,,,} .

Remarque
Il existe un ordre de priorité entre les connecteurs logiques


1.2.4 Formalisation du langage naturel vers le langage propositionnel

Pour transformer un énoncé en langage naturel vers son équivalent sous forme
de formule logique, on doit premièrement lire l’énoncé ensuite déterminer les
propositions atomiques et à la fin traduire les phrases sous forme de formules
composé à partir de ces propositions atomiques.
 Exemple

Soit le raisonnement en langage naturel suivant :

S’il fait beau, je vais en mer. PQ

P Q
Si la marée est basse, l’écluse est fermée. RS
R S
Si l’écluse est fermée, je ne peux pas aller en mer SQ

La marée est basse et il fait beau. RP

Donc je ne vais pas en mer. Q

Formalisation

P : il fait beau ; Q : je vais en mer ; R : la marée est basse ; S : l’écluse est fermée.

1.2.5 Arbre de décomposition d’une formule

C’est un arbre dont la racine est la formule, les nœuds correspondent aux
différents connecteurs de la formule et les feuilles sont les propositions
atomiques de cette formule.
On décompose en branche suivant le connecteur le moins prioritaire.
La hauteur d’une formule est la longueur de la plus longue branche dans l’arbre
de décomposition d’une formule.

1.3 SEMANTIQUE DU CALCUL PROPOSITIONNEL

1.3.1 Définition

La sémantique c’est évaluer les formules propositionnelles et leur attribuer une valeur
de vérité. Les formules prennent leur valeur dans l’ensemble BOOL={V, F}.

1.3.2 Tables de vérité des connecteurs

P Q PQ PQ PQ PQ P

V V V V V V F
V F F V F F F
F V F V V F V
F F F F V V V
1.3.3 Notion d’interprétation d’une formule

[Link] Définition1

L’interprétation d’une formule est une fonction qui permet d’associer une valeur de
vérité à une formule une fois les valeurs de vérité des propositions atomique composant
la formule sont fixées.

I F BOOL
F {V, F}

Remarque

Le nombre d’interprétation d’une formule dépend du nombre de propositions atomique

qui composent cette formule

Pour n propositions atomique on a 2n interprétations possibles

[Link] Définition2

Chaque ligne de la table de vérité d’une formule correspond { une interprétation de

cette formule

[Link] Définition3

Pour une interprétation donnée si la valeur de vérité de la formule est vrai, on dit que
cette interprétation satisfait la formule et on dit que cette interprétation est un modèle
pour cette formule.

Exemple

Soit F : PQP

I P Q P PQ PQP
i1 V V F V F
i2 V F F F V
i3 F V V F V
i4 F F V F V

Dans cet exemple i2, i3, i4 satisfont la formule F.

1.3.4 Validité, satis faisabilité

- Une formule F est dite satisfaisable s’il existe au moins une interprétation qui
satisfait la formule.
- Une formule F est dite valide ou tautologie si pour toutes les interprétations
possibles la formule est vraie. On note
- Une formule F est dite contradictoire ou antilogie si pour toutes les
interprétations possibles la formule est fausse. On note

1.3.5 Les tautologies

Double négation P  P

Idempotence PP  P PPP

Commutativité PQ QP PQ QP

Associativité P(QR) (PQ)R (PQ)R P(QR)
Distributivité P(QR) (PQ) (PR) P(QR) (PQ)( PR)
Loi de Morgan (PQ) PQ (PQ) PQ
Définition de l’implication (PQ) PQ
Définition de  (PQ) (PQ)  (QP)
Elément neutre PV P PF P
Elément absorbant PF F PV V
Loi d’absorption P(PQ) P P(PQ) P

1.3.6 Equivalence de formules

Deux formules sont dites équivalentes ssi elles possèdent les mêmes variables
propositionnelles atomiques et elles ont les mêmes valeurs de vérités.
Généralement, on démontre l’équivalence de formule soit en utilisant les tables
de vérité ou bien en utilisant la simplification algébrique pour le passage d’une
formule { l’autre et inversement.

Exemple : Démontrer que les formules suivantes sont équivalentes

( ⇒ ) ( ⇒ ) et ⇒ ⇒ ( ⇒ )
B(AB(CA))  B((AB)(CA))

 B((AB) (CA))

 B(AB) (CA) ( est associatif donc on supprime les () )

B (absoption)

 B (CA)  (BC) (BA)  (BC) (AB)  1

1.3.7 Formes particulières d’une formule

[Link] Forme normale conjonctive (FNC)

Une formule F est dite en FNC si elle est écrite sous la forme de conjonction de
disjonction de littéraux. Un littéral est une proposition atomique ou bien la négation
d’une proposition atomique

Exemple F :(PQR)(PQR)

[Link] Forme normale disjonctive(FND)

Une 7ormule F est dite en FND si elle est écrite sous la forme de disjonction de
conjonction de littéraux. Un littéral est une proposition atomique ou bien la négation
d’une proposition atomique

Exemple F :(PQR)  (PQR)

Propriété : Toute formule est équivalente à sa FNC et FND.

[Link] Calcul de FNC et FND d’une formule

 1ère méthode : Table de vérité

Exemple

F : PQ
P Q PQ
V V V
V F F
F V V
F F V
Pour déterminer

FNC : On regarde les lignes où la formule est fausse. Les variables fausses sont prises
sans utiliser la négation sinon elles sont prises avec le connecteur .

FNC :PQ

FND : On regarde les lignes ou la formule vaut vrai : Si la variable propositionnelle est
vraie, on la prend telle qu’elle est sinon on la prend en négation.

FND : (PQ) (PQ)( PQ)

 2ème méthode : Algorithme de normalisation

Algorithme de normalisation

Etape1 : Eliminer les et .

Etape 2 : Introduire les  en appliquant la loi de Morgan ;

Etape3 : Essayer d’écrire le formule sous forme FNC ou FND.

Exemple

Soit la formule suivante :

[(P  ( (Q  P)  (R  P) ) ) (R (PQ)) ]

[(P  ( (Q  P)  (R  P) ) ) (R (PQ))] ………1

[ (R (PQ)) (P  ( (Q  P)  (R  P) ) )]………..2

1(P  (Q  P)  (R  P) ) (R (PQ))

 P absorption
 (P(R  P) ) (R (PQ))
 ((PR)(PP))  (R (PQ))

Faux

 (PR)  R (PQ)

PR( PQ)

PR( PQ) PR (absorption)

 2 (R(PQ)) (P  ( (Q  P)  (R  P) ) )

 (R(PQ)) (P  (Q  P)  (R  P) )

 (R(PQ)) P  (R  P)

 (R P  (R  P) ) (PQ  P  (R  P))

P

 (R P  (R  P) ) (PQ  (R  P))

Vrai

( PQ  R)  P) (PQ P)  PQ  R

Donc FNC : (PR)( PQ  R)

Calcul de FND :R(P(PQ))  R(PQ)

Propriété :

Le passage d’une FNC { une FND et inversement se fait par distributivité.

1.3.8 Système complet de connecteurs

Un ensemble de connecteurs forme un système complet si on peut exprimer { l’aide de

ces connecteurs tous les connecteurs de base de la logique.

En ayant cet ensemble de connecteur, on peut s’en passer des autres connecteurs de
base.

Exemple (,) ;(,) ;(,) sont des systèmes complet de connecteurs.

Démonstration (,) il contient les connecteurs,. Il reste à exprimer 

PQ  (PQ) (PQ) (PQ).

PQPQ
(PQ)(PQ)(QP)  ((PQ) (QP))