Précédent / Suivant / Table des matières

I. Eléments de calcul propositionnel

I-1. Généralités

L’approche “ naïve ” de la logique des propositions permet d’acquérir rapidement et clairement les notions de base utiles, sinon nécessaires, pour toute la suite. Cependant l’étudiant intéressé par une exposition formelle et approfondie dispose d’excellents ouvrages dont certains figurent dans la bibliographie proposée dans le cours « Mathématique pour l’informatique ».

 

Définitions et principes 1:
On désigne par expression tout assemblage de signes (lettres, symboles, chiffres, mots, locution …) admettant une signification dans une théorie fixée. Dans une théorie fixée une proposition logique est une expression nécessairement vraie ou fausse (principe du tiers exclu et principe de non contradiction). On parlera donc de valeur de vérité d’une proposition (logique) donnée. Dans le calcul propositionnel les propositions sont considérées comme des variables pouvant prendre l’une des valeurs de vérité VRAI ou FAUX.
Val(p) désigne la valeur de vérité de la proposition p. On a Val(p)= VRAI ou Val(p)= FAUX.

 

Remarque 1:
Dans une théorie fixée, on appelle axiome toute proposition (primitive) à laquelle on attribue de façon conventionnelle la valeur vrai. On appelle théorème toute proposition dont on démontre quelle est vraie, en respectant les règles admises ou établies dans cette théorie.

 

Notation 1:

Les propositions sont souvent notées par des lettres minuscules p, q, r … éventuellement indicées p1, p2, p3…

On désigne souvent par V la valeur de vérité VRAI et par F la valeur de vérité FAUX (ou encore 1 et 0).

Deux propositions p et q ayant la même valeur de vérité sont dites synonymes ou égales ou équivalentes. On écrit p=q ou p≡q.

I-2. Connecteurs logiques

L’un des avantages du fait qu’une proposition ne peut prendre qu’une valeur de vérité parmi deux est, qu’en considérant un nombre fini de propositions, on peut dresser un état exhaustif des combinaisons possibles des valeurs de vérité.
Ainsi pour deux propositions p et q on a 2×2 = 4 cas : (VV ou VF ou FV ou FF)
pour trois propositions p, q et r on a 2×2×2  = 8 cas : (VVV ou VVF ou VFV ou VFF ou FVV ou FVF ou FFV ou FFF) et de façon générale pour n propositions on 2n cas.
Cet énorme avantage va nous permettre de construire un “ calcul ” sur les propositions en introduisant des opérateurs (connecteurs logiques) et en associant aux résultats des vecteurs de vérité.

 

p	p
V	F
F	V

I-2-1 La négation :
La négation d’une proposition p est la proposition, notée p, qui est vraie quand p est fausse et fausse quand p est vraie. Ainsi on a une opération unaire qui à chaque proposition p associe sa négation p. L’opérateur (connecteur logique) unaire est symbolisé par  , il représente le NON et se définit par la table de vérité :
On note aussi : ¬p,  et p’

 

Remarque 2: Val((p)= Val(p)

 

p	q	pq
V	V	V
V	F	F
F	V	F
F	F	F

I-2-2 La conjonction :
La conjonction de deux propositions p et q est la proposition, notée pq, qui est vraie dans le seul cas où  p et q sont vraies toutes les deux. Ainsi on a une opération binaire qui à deux propositions p et q associe leur conjonction, notée pq. L’opérateur (connecteur logique) binaire est symbolisé par  , il représente le ET et se définit par la table de vérité :
On note aussi : p&q, p.q, p×q et pq

 

p	q	pq
V	V	V
V	F	V
F	V	V
F	F	F

I-2-3 La disjonction (inclusive) :
La disjonction (inclusive) de deux propositions p et q est la proposition, notée pq, qui est fausse dans le seul cas où  p et q sont fausses toutes les deux. Ainsi on a une opération binaire qui à deux propositions p et q associe leur disjonction, notée
pq. L’opérateur (connecteur logique) binaire est symbolisé par  , il représente le OU et se définit par la table de vérité :
On note aussi : p+q

 

p	q	p→q
V	V	V
V	F	F
F	V	V
F	F	V

I-2-4 Le conditionnel :
Le conditionnel de deux propositions p et q est la proposition, notée p→q, qui est fausse dans le seul cas où  p est vraie et q est fausse. Ainsi on a une opération binaire qui à deux propositions p et q associe leur conditionnel, notée p→q. L’opérateur (connecteur logique) binaire est symbolisé par → , il représente le SI … ALORS et se définit par la table de vérité :

 

p	q	p↔q
V	V	V
V	F	F
F	V	F
F	F	V

I-2-5 Le biconditionnel :
Le biconditionnel de deux propositions p et q est la proposition, notée p↔q, qui est fausse dans les deux cas où  p et q n’ont pas la même valeur de vérité. Ainsi on a une opération binaire qui à deux propositions p et q associe leur biconditionnel, notée p↔q. L’opérateur (connecteur logique) binaire est symbolisé par ↔ , il représente le SI  ET SEULEMENT SI et se définit par la table de vérité :

 

I-3. Calcul des propositions

Les connecteurs (ceux définis plus haut et d’autres à venir) peuvent se combiner entre eux et engendrer ainsi des propositions “ complexes ” constituées par un certain nombre de propositions que l’on qualifie d’atomiques. Nous utiliserons le parenthésage de la façon habituelle pour établir les hiérarchies calculatoires entre différents connecteurs. Les expressions obtenues sont appelées propositions composées ou expressions bien formées (e.b.f). Elles sont souvent notées par des lettres majuscules P, Q, R …  éventuellement indicées P1, P2, P3,… On peut aussi écrire P(p1, p2, p3,… , pn ) pour expliciter les propositions (atomiques) p1, p2, p3,… , pn constituant la proposition (composée) P.

 

Définition 2 : Deux propositions (composées) sont égales si et seulement si elles ont le même vecteur de vérité. On note P ≡ Q. (quelque soit les valeurs de vérités attribuées aux propositions (atomiques) qui les composent).

 

Définition 3 : Une proposition dont le vecteur de vérité ne contient que des “ V ” (respectivement que des “ F ”) est une tautologie (resp une contradiction). On note T la tautologie et C la contradiction.

 

Propriétés 1 :
Commutativité :
       pq ≡ qp  pq ≡ qp  p↔q ≡ q↔p
Associativité :
       (pq)r ≡ p(qr)        (pq)r ≡ p(qr)        (p↔q) ↔r ≡ p↔(q↔r)
Distributivité :
       (pq)r ≡ (pr)(qr)            (pq)r ≡ (pr)(qr)
Idempotence :
       pp ≡ p        pp ≡ p
Identité :
pT ≡ p  pC ≡ C      pT ≡ T     pC ≡ p
Théorème de Morgan :
       (pq) ≡ (p)( q)                (pq) ≡ (p)( q)
Quelques égalités usuelles :
       p→q ≡ (p)q                   p↔q ≡ (p→q)( q→p)

 

I-4. Relations entre propositions

 

I-4-1 Implication logique :

 

Définition 4 : On dit qu’une proposition (composée) P implique logiquement une proposition (composée) Q si P→Q est une tautologie. On note PQ.
La réciproque de PQ est QP
La contraposée de PQ est QP

 

I-4-1 Equivalence logique :

 

Définition 5 : On dit que deux propositions (composées) P et Q sont logiquement équivalentes si P↔Q est une tautologie. On note PQ.

Haut de page