Chapitre 3 : Logique des propositions et Algèbre de Boole
1. Logique des propositions
1.1. Notion de Proposition
Les propositions sont des énoncés non-ambiguës, phrases décrivant une
situation, une propriété, une relation, un jugement, auxquels on serait susceptible
d’associer dans des circonstances précises une valeur de vérité : vrai (valeur V) ou
fausse (valeur F).
En d’autres termes, une proposition est toute expression qui peut être dite vraie
ou fausse, ce qui exclut, entre autres, les questions (a), les impératifs (b), les
exclamatifs (c), et plus généralement tous les énoncés dits non assertifs, comme
certains performatifs (d), certains énoncés à fonction phatique (e), ou — on peut en
discuter — toute la classe des énoncés modalisés (f). Sont de même exclues les
expressions correspondant à des constituants non phrastiques.
a) Est-ce que Paul aime la marche à pied ?
b) Fermez la porte !
c) Qu’elle est gentille !
d) Je te promets de venir.
e) Tu m’entends !
f) La bataille aura lieu demain
On peut s’intéresser à l’analyse du rapport entre phrase (au sens linguistique) et
proposition (au sens logique). Il est clair que ce rapport n’est pas direct : (a) deux
phrases peuvent exprimer la même proposition, par exemple dans deux langues
différentes, ou encore lorsque l’on utilise des variantes lexicales (dame/femme), mais
aussi parce que la proposition correspond au contenu littéral, qui peut être le même
pour deux phrases dont le contenu exprimé est différent. (b) Une phrase peut contenir
plusieurs propositions, soit par la présence d’un connecteur (a), soit par des effets
sémantiques (présupposition en (b)) ou pragmatiques (d), soit par ambiguïté(une
expression signifiant deux ou plusieurs sens) (e).
a) Si Jean chante, tout le monde se plaint
b) Le Ministre de la Santé de France est chauve
c) Avant son mariage, il était moins bien nourri
d) Même Paul est venue.
e) Toutes les camerounaises admirent un acteur
De manière formelle, on distingue trois catégories d’énoncés :
➢ Les énoncés élémentaires sont des énoncés de base. Ils sont indécomposables
et sont représentés par des variables appelées variables propositionnelles
➢ Les énoncés composés sont formés d’un ou de plusieurs énoncés (élémentaires
ou composés) combinés par des connecteurs (∧, ∨, ¬, ⇒, ⇔), ∨, ¬, ⇒, ⇔), ¬, ⇒, ⇔), ⇔))
1
➢ Des combinaisons plus complexes peuvent être formées par parenthésage
((A ⇒, ⇔) D) ⇒, ⇔) (D ⇒, ⇔) B)) ⇒, ⇔) (A ⇒, ⇔) B)
Exemples
➢ Énonces élémentaires
– soit A la proposition « la terre est plate »
– soit B la proposition « 17 est un nombre premier »
➢ Énonces composés
– (non A) et B : « la terre n’est pas plate et 17 est un nombre premier »
– (non A) et (non B) : « la terre n’est pas plate et 29 n’est pas premier »
– P ou B : « la terre est plate ou 17 est un nombre premier »
1.2. Tables de Vérité
La Négation de la Proposition P (non P) : ˥P
Étant donnée une proposition P, sa négation est la proposition non P, également
notée ¬P, dont la véracité est l’opposée de celle de P.
P ˥P
V F
F V
La Disjonction (ou adjonction) de Deux Propositions P et Q : P ∨ Q Q
La disjonction de deux propositions P et Q (P ou Q), notée P ∨ Q Q, est vraie si
l’une des deux propositions P et Q est vraie. Elle est fausse uniquement dans le cas où
les deux propositions sont P et Q sont fausse. Ici le « ou » est dans un sens inclusif
La conjonction est réflexive (P et (P ∨, ¬, ⇒, ⇔) P) ont la même valeur de vérité) et
commutative ( (P ∨, ¬, ⇒, ⇔) Q) et (Q ∨, ¬, ⇒, ⇔) P) ont la même valeur de vérité).
P Q P ∨ Q Q
F F F
F V V
V F V
V V V
La Conjonction de Deux Propositions P et Q : P ∧ Q Q
La conjonction de deux proposition P et Q (P et Q), notée P ∧ Q Q, est vraie
uniquement dans le cas où les deux propositions P et Q sont vraies. La conjonction
est réflexive et commutative. La conjonction est réflexive et commutative
2
P Q P ∧ Q Q
F F F
F V F
V F F
V V V
L’Implication « si P alors Q » : P ⇒ Q Q
Dans l’implication « P implique Q », notée « si P alors Q », « P ⇒, ⇔) Q », P est
appelée hypothèse et Q est appelée conclusion. Une implication traduit une
proposition conditionnelle. Elle est fausse uniquement dans le cas où l’hypothèse est
vraie et la conclusion est fausse.
L’implication n’est ni réflexive, ni commutative.
P Q P ⇒ Q Q
F F V
F V V
V F F
V V V
Si l’implication P ⇒, ⇔) Q est vraie
➢ P est une condition suffisante pour Q
➢ Q est une condition nécessaire pour P
L’Équivalence « P est équivalent à Q » : P ⇔ Q Q
Si P et Q sont deux propositions, leur équivalence est notée (P ⇔) Q). Elle est
vraie si les deux propositions P et Q ont la même valeur de vérité. L’équivalence est
réflexive et commutative.
Une équivalence est une implication dans les deux sens : condition nécessaire
et suffisante.
P Q P ⇔ Q Q
F F V
F V F
V F F
V V V
1.3. Tautologies
3
Une tautologie est une assertion qui dépend d’autres assertions mais qui est toujours
vraie, quelles que soient les valeurs de vérité de ces dernières.
Exemples
➢ « A ∨, ¬, ⇒, ⇔) ¬A » est une tautologie
➢ « A ⇔) ¬¬A » est une tautologie
A ¬A A ∨ Q ¬A ¬¬A A ⇔ Q ¬¬A
F V V F V
V F V V V
Une tautologie de type A ⇔) B permet de remplacer A par B (ou B par A) dans
toute expression logique quel que soit le contexte. Une telle tautologie traduit le fait
que les deux propositions A et B sont logiquement équivalentes
Pour démontrer que deux propositions sont logiquement équivalentes, il suffit
de montrer qu’elles ont la même table de vérité.
Voici quelques tautologies à connaître :
N° Énonce de la Tautologie Commentaire
1 ¬¬A ⇔) A Une double négation est une
affirmation
2 ¬(A ∨, ¬, ⇒, ⇔) B) ⇔) ¬A ∧, ∨, ¬, ⇒, ⇔) ¬B 1ère loi de Morgan
3 ¬(A ∧, ∨, ¬, ⇒, ⇔) B) ⇔) ¬A ∨, ¬, ⇒, ⇔) ¬B 2ème loi de Morgan
4 A ∨, ¬, ⇒, ⇔) ¬A tiers exclus
5 (A ⇒, ⇔) B) ⇔) ¬A ∨, ¬, ⇒, ⇔) B
6 (A ⇒, ⇔) B) ⇔) (¬B ⇒, ⇔) ¬A) Contraposition : Toute
implication est équivalente à sa
contraposée
7 (A ⇔) B) ⇔) (A ⇒, ⇔) B) ∧, ∨, ¬, ⇒, ⇔) (B ⇒, ⇔) A) Une équivalence est une double
implication
8 ((A ⇒, ⇔) B) ∧, ∨, ¬, ⇒, ⇔) (B ⇒, ⇔) C)) ⇒, ⇔) (A ⇒, ⇔) C) Transitivité de l’implication
9 (A ∨, ¬, ⇒, ⇔) (B ∧, ∨, ¬, ⇒, ⇔) C)) ⇔) (A ∨, ¬, ⇒, ⇔) B) ∧, ∨, ¬, ⇒, ⇔) (A ∨, ¬, ⇒, ⇔) C) Distributivité de ∨, ¬, ⇒, ⇔) par rapport à
∧, ∨, ¬, ⇒, ⇔)
10 (A ∧, ∨, ¬, ⇒, ⇔) (B ∨, ¬, ⇒, ⇔) C)) ⇔) (A ∧, ∨, ¬, ⇒, ⇔) B) ∨, ¬, ⇒, ⇔) (A ∧, ∨, ¬, ⇒, ⇔) C) Distributivité de ∧, ∨, ¬, ⇒, ⇔) par rapport à
∨, ¬, ⇒, ⇔)
Démonstration de l’Équivalence : ¬(A ∨ Q B) ⇔ Q ¬A ∧ Q ¬B
4
A B ¬A ¬B A ∨ Q B ¬(A ∨ Q B) ¬A ∧ Q ¬B
F F V V F V V
F V V F V F F
V F F V V F F
V V F F V F F
En appliquant cette tautologie (1ère loi de Morgan), le contraire de la phrase «
ce tableau est vert ou blanc» est « ce tableau n’est pas vert et ce tableau n’est pas
blanc », soit « ce tableau n’est ni vert et ni blanc ».
Démonstration de l’Équivalence :¬(A ∧ Q B) ⇔ Q ¬A ∨ Q ¬B
¬A ∨, ¬, ⇒, ⇔) ¬B ⇔) ¬¬(¬A ∨, ¬, ⇒, ⇔) ¬B) D’après (1) : Une double négation est une affirmation
⇔) ¬(¬¬A ∧, ∨, ¬, ⇒, ⇔) ¬¬B) D’après (2) : 1ère loi de Morgan
⇔) ¬(A ∧, ∨, ¬, ⇒, ⇔) B) D’après (1) : ¬¬A (¬¬B) est équivalente à A (B).
En suivant cette tautologie (2ème loi de Morgan), le contraire de la phrase «
Paul le chocolat et la vanille » est « Paul n’aime pas le chocolat ou Paul n’aime pas la
vanille », soit « Paul n’aime pas le chocolat ou la vanille ».
Démonstration de l’Équivalence : (A ⇒ Q B) ⇔ Q ¬A ∨ Q B
A B ¬A ¬A ∨ Q B A ⇒ Q B
F F V V V
F V V V V
V F F F F
V V F V V
Démonstration de l’Équivalence :(A ⇒ Q B) ⇔ Q (¬B ⇒ Q ¬A)
(A ⇒, ⇔) B) ⇔) (¬A ∨, ¬, ⇒, ⇔) B) D’après (5)
⇔) (¬A ∨, ¬, ⇒, ⇔) ¬¬B) D’après (1) : ¬¬B est équivalente à B
⇔) (¬¬B ∨, ¬, ⇒, ⇔) ¬A) Commutativité de ∨, ¬, ⇒, ⇔)
⇔) (¬B ⇒, ⇔) ¬A) D’après (5)
1.4 Le Raisonnement Logique
La logique est utilisée pour raisonner ou produire des démonstrations, c’est-à-
dire, à partir d’énoncés de départ (les hypothèses), aboutir à un ensemble de
conclusions par l’application successives de règles d’inférence. Ces règles
5
d’inférences peuvent être des tautologies. On peut considérer différentes formes de
raisonnement :
➢ le syllogisme
➢ la contraposition
➢ le raisonnement par l’absurde
Le raisonnement par syllogisme
Le syllogisme est un raisonnement de la la forme :
Si A est vraie
Et A ⇒, ⇔) B est vraie
Alors B est vraie
Cette forme de raisonnement avait été identifiée par Aristote :
– « Socrate est un homme »
– « Les hommes sont mortels »
– « Donc Socrate est mortel »
Le raisonnement par contraposition
La contraposition est un raisonnement de la la forme :
Si ¬B ⇒, ⇔) ¬A
Alors A ⇒, ⇔) B
La contraposée de « Si c² = a² + b² Alors le triangle de cotés a, b et c est
rectangle » est « Si c² ≠ a² + b² Alors le triangle de cotés a, b et c n’est pas
rectangle »
Le raisonnement par l’absurde
Le raisonnement par l’absurde est un raisonnement de la la forme :
¬A ⇒, ⇔) F (Si A est fausse)
donc A vraie
Ceci provient du principe du tiers exclus : Soit A vraie, soit ¬A vraie. Mais pas les
deux à la fois. Ainsi la valeur de vérité de l’un (par exemple ¬A) est l’opposée de
celle de l’autre (A).
2. Algèbre de Boole
2.1. Introduction
De nombreux dispositifs électronique, électromécanique, (mécanique,
électrique, pneumatique, etc.) fonctionnement en TOUT ou [Link] peuvent prendre
deux états :
➢ vrai/faux
➢ avant/arrière
➢ arrêt/marche
➢ ouvert/fermé
➢ enclenché/déclenché
6
➢ conduction/blocage
Ceci corresponds un système mathématique n'utilisant que deux valeurs numériques
(exemple O ou 1). Il est donc avantageux d’utiliser un tel système mathématique
pour étudier le fonctionnement de ces dispositifs.
L’algèbre de Bool est constituée d’un ensemble de deux valeurs et des
opérations sur lesdites valeurs :
➢ L’ensemble des valeurs :{0,1}
➢ L’ensemble des opérations :
- la disjonction (+) (équivalent du « OU INCLUSIF» logique)
- la conjonction (.) (équivalent du « ET » logique)
- la négation (-) (équivalent du « NON » logique)
- la disjonction exclusive (⊕) (équivalent du OU EXCLUSIF : XOR).
- l’opérateur NON-ET
- l’opérateur NON-OU
2.2. Les Opérateurs
L’Opérateur de Disjonction : +
Table de vérité Porte Logique
+ 0 1
0 0 1
1 1 1
L’Opérateur XOR : ⊕
Table de vérité Porte Logique
⊕ 0 1
0 0 1
1 1 0
L’Opérateur de Conjonction : .
Table de vérité Porte Logique
. 0 1
0 0 0
1 0 1
7
L’Opérateur de Négation : -
Table de Vérité Porte Logique
-
0 1
1 0
L’Opérateur NON-ET
Table de Vérité Porte Logique
↓ 0 1
0 1 1
1 1 0
L’Opérateur NON-OU
Table de Vérité Porte Logique
↑ 0 1
0 1 0
1 0 0
2.3. Propriétés des Opérateurs
Propriétés de l’opérateur +
Propriété Formule
associativité (a + b) + c = a + (b + c)
élément neutre a+0=a=0+a
élément absorbant a+1=1=1+a
idempotence a+a=a
commutativité a+b=b+a
ordre préfixe a≤a+b
réflexif a≤a
transitif a ≤ b, b ≤ c ⇒, ⇔) a ≤ c
antisymétrique a ≤ b, b ≤ a ⇒, ⇔) a = b
treillis sup(a, b) = a + b
Propriétés de l’opérateur .
8
Propriété Formule
associativité (a.b).c = a.(b.c)
élément neutre a.1 = a = 1.a
élément absorbant a.0 = 0 = 0.a
idempotence a.a = a
commutativité a.b = b.a
ordre préfixe a ≥ a.b
réflexif a≥a
transitif a ≥ b, b ≥ c ⇒, ⇔) a ≥ c
antisymétrique a ≥ b, b ≥ a ⇒, ⇔) a = b
treillis inf(a, b) = a.b
Propriétés mutuelles des opérateurs + et .
Propriété
distributivité a.(b + c) a + (b.c)
= a.b + a.c = (a + b).(a + c)
= b.a + c.a = (b + a).(c + a)
= (b + c).a = (b.c) + a
absorption a + (a.b) = a a.(a + b)=a
Propriétés du « non » dans B
Propriété
involution a’’ = a
complémentarité a + a’ = 1 a.a’ = 0
dualité (a + b)’ = a’.b’ (a.b)’ = a’ + b’
antitonie a ≤ b ↔ a’ ≥ b’ a ≥ b ↔ a’ ≤ b’
L’opérateur de négation utilisé ici est ’. La négation de a est : a’
2.4. Fonctions Logiques
Une fonction logique est une fonction qui prends en entrée une ou plusieurs
variables constituée chacune d’une suite de bits (0 et 1) et retourne en sortie une
suite de bits. Il traduit le résultat de la combinaison (logique combinatoire) d'une ou
9
plusieurs suites de bits reliées entre elles par des opérations booléennes. La valeur
résultante de cette fonction dépend des valeurs des suites de bits.
Exemples Fonctions Booléennes à Deux Variables Constituées d’une Suite de
Quatre Bits
N° Expression de f(x,y), où Valeur de f(x,y) pour
x=x3 x2 x1 x0 et x=0011 et
y=y3 y2 y1 y0 y=0101
1 0000 0000
2 x.y = x3.y3 x2.y2 x1.y1 x0.y0 0001
3 x.y’= x3.y3’ x2.y2’ x1.y1’ x0.y0’ 0010
4 X = x3 x2 x1 x0 0011
5 x’.y= x3’.y3 x2’.y2 x1’.y1 x0’.y0 0100
6 y= y3 y2 y1 y0 0101
7 x ⊕ y = x3⊕y3 x2⊕y2 x1⊕y1 x0⊕y0 0110
8 x + y = x3+y3 x2+y2 x1+y1 x0+y0 0111
9 x ↑ y = (x+y)’=x3↑y3 x2↑y2 x1↑y1 x0.↑y0 1000
10 (x ⊕ y)’=(x3⊕y3)’ (x2⊕y2)’ (x1⊕y1)’ 1001
(x0⊕y0)’
11 y’=y3’ y2’ y1’ y0’ 1010
12 x’ ↓ y=x3’↓y3 x2’↓y2 x1’↓y1 x0’↓y0 1011
13 x’=x3’ x2’ x1’ x0’ 1100
14 x ↓ y’=x3↓y3’ x2↓y2’ x1↓y1’ x0↓y0’ 1101
15 x ↓ y =(x.y)’=x3↓y3 x2↓y2 x1↓y1 x0↓y0 1110
16 1111 1111
Représentation d’une Fonction Booléenne par une Table de Vérité
Soit la fonction booléenne f(p, q,r)= (p.q) + (q’.r). Sa table de vérité est :
p q r f(p,q,r)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
10
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Exercice : Dessiner le circuit logique correspondant
Représentation Canonique (Forme Normale Disjonctive) d’une Fonction
Booléenne
La représentation canonique, encore appelée forme normale disjonctive, d’une
fonction booléenne est obtenue retenant dans sa table de vérité toutes les lignes dont
la valeur de vérité est 1. En appliquant cette définition, la forme canonique de la
fonction f(p, q, r)= (p.q) + (q’.r) est : (p’.q’.r) + (p.q’.r) + (p.q.r’) + (p.q.r). Chacun
des quatre termes est appelé minterm.
Exercice : Dessiner le circuit logique correspondant
2.5. Simplification des Expressions Booléennes
2.5.1. Simplification des Expressions booléennes
Simplifions l’expression p’q’r + p’qr + pq’r’. Nous avons :
p’q’r + p’qr + pq’r’ = p’rq’ + p’rq + pq’r’ (commutativité)
= (p’rq’ + p’rq) + pq’r’ (associativité)
= p’r (q’ + q) + pq’r’ (distributivité)
= p’r + pq’r’ (q’ + q) = 1
Exercice : Dessiner le circuit logique correspondant
2.5.2. Simplification par Exploitation du Diagramme de Karnaugh
Le Diagramme de Karnaugh avait été inventé dans les années 50 pour
simplifier la conception de circuits logiques.
➢ C’est représentation visuelle qui mets en évidence les paires de minterms que
l’on peut réunir et fusionner en une seule expression plus simple.
➢ Les lignes et les colonnes sont étiquetées de manière à ce qu’en se déplaçant de
ligne en ligne ou de colonne en colonne, on observe exactement un
changement dans l’étiquette.
➢ Pour une expression booléenne donnée sous forme normale disjonctive, on
écrit un 1 dans chaque case représentant les minterms présents.
➢ La simplification correspond aux groupes de 2n cellules contiguës.
➢ On admets que des groupes de 2n cellules contiguës peuvent être non-disjoints.
11
Étude de la Simplification de l’expression suivante : p’q’r + p’qr + pq’r’
pq p’q p’q’ pq’
r 1 1
r’ 1
q q’
Cette expression n’est pas simplifiable par le diagramme de Karnaugh.
Étude de la Simplification de l’expression suivante : pqr + p’qr’ + pq’
pq p’q p’q’ pq’
r 1 1
r’ 1
q q’
Cette expression se simplifie en r(pq + pq’) + r’p’q= rp(q+q’) + r’p’q=rp + r’p’q.
Étude de la Simplification de l’expression pqr + p’q’r’ + p’qr + pqr’ + p’qr’
pq p’q p’q’ pq’
r 1 1
r’ 1 1 1
q q’
Cette expression se simplifie en q+ r’p’q’
12
