Algèbre de Boole

Fonctions Booléennes
Calcul Propositionnel

Mathématiques Discrètes
Chapitre 5
Calcul propositionnel et Algèbre de Boole

Leo Donati Noëlle Stolfi

Université de Nice Sophia Antipolis

IUT Nice Côte d’Azur
DUT Informatique

2016-2017

1/32 Donati & Stolfi M1201-5

 Algèbre de Boole Définition
Fonctions Booléennes Propriétés de B
Calcul Propositionnel Exemples

Chapitre 5 : Calcul propositionnel et

Algèbre de Boole

1 Algèbre de Boole 3 Calcul

Définition Propositionnel
Propriétés de B Formules
Exemples Sémantique
2 Fonctions Séquents
Booléennes
Définition
Propriétés

2/32 Donati & Stolfi M1201-5

 Algèbre de Boole Définition
Fonctions Booléennes Propriétés de B
Calcul Propositionnel Exemples

Algèbre de Boole
Une algèbre de Boole est un ensemble B possédant
au moins deux éléments distincts notés 0 et 1
deux opérations de composition interne + et ×
une loi qui à tout élément x ∈ B associe x ∈ B
Ces lois doivent vérifier 5 groupes de 2 axiomes :
1 Règle de la barre : x + x = 1 x ×x = 0
2 O et 1 sont des éléments neutres :
x +0 = 0+x = x x ×1 = x ×1 = x
3 Commutativité : x + y = y + x x ×y = y ×x
4 Associativité :
x + (y + z) = (x + y ) + z x × (y × z) = (x × y ) × z
5 Distributivité : x × (y + z) = (x × y ) + (x × z)
x + (y × z) = (x + y ) × (x + z)
3/32 Donati & Stolfi M1201-5
 Algèbre de Boole Définition
Fonctions Booléennes Propriétés de B
Calcul Propositionnel Exemples

B2
Algèbre de Boole B2
L’algèbre de Boole la plus simple de toutes n’a que deux éléments :

B2 = {0, 1}

+ 0 1 × 0 1
0 0 1 0 0 0
1 1 1 1 0 1

Remarque
Cette algèbre de Boole est celle de la logique mathématique où
0 c’est Faux et 1 c’est Vrai
+ c’est OU et × c’est ET
x c’est NON(x )
4/32 Donati & Stolfi M1201-5
 Algèbre de Boole Définition
Fonctions Booléennes Propriétés de B
Calcul Propositionnel Exemples

Propriétés fondamentales

Théorème 1
0 = 1 et 1 = 0

Démonstration
Comme le 0 est l’élément neutre de + on a

0+0 = 0

d’autre part, d’après l’axiome de la barre

0+0 = 1

donc
0=1

5/32 Donati & Stolfi M1201-5

 Algèbre de Boole Définition
Fonctions Booléennes Propriétés de B
Calcul Propositionnel Exemples

Propriétés fondamentales - 2

Théorème 2
∀x ∈ B x + x = x

Démonstration
∀x ∈ B on a
x = x +0
= x + (x × x )
= (x + x ) × (x + x )
= (x + x ) × 1
= x +x

6/32 Donati & Stolfi M1201-5

 Algèbre de Boole Définition
Fonctions Booléennes Propriétés de B
Calcul Propositionnel Exemples

Propriétés fondamentales - 3

Théorèmes 3
∀x ∈ B x × x = x
∀x ∈ B x + 1 = 1
∀x ∈ B x × 0 = 0

Démonstration
En TD

7/32 Donati & Stolfi M1201-5

 Algèbre de Boole Définition
Fonctions Booléennes Propriétés de B
Calcul Propositionnel Exemples

Lemme
Si dans une algèbre de Boole B il existe deux élémente x et y tels
que x + y = 1 et x × y = 0 alors on a

y =x

Démonstration
Preuve :
x +y = 1
⇒ x (x + y ) = x
⇒ (x x ) + (x y ) = x
⇒ 0 + (x y ) = x
⇒ (xy ) + (x y ) = x
⇒ (x + x )y = x
⇒ (1y ) = x
⇒ y = x

8/32 Donati & Stolfi M1201-5

 Algèbre de Boole Définition
Fonctions Booléennes Propriétés de B
Calcul Propositionnel Exemples

Loi de De Morgan
Lois de De Morgan : ∀x ∈ B, ∀y ∈ B
x ×y = x +y
x +y = x ×y

Démonstration
Posons A = xy et B = x + y . On cherche à montrer que A = B.
Utilisons le lemme : il nous faut prouver que A + B = 1 et AB = 0.

A+B = x + y + (xy ) A×B = (x + y ) × (xy )

= (x + y + x )(x + y + y ) = (x .y .x )(y .x .y )
= (1 + y )(1 + x ) = (0.y ) + (0.x )
= 1×1 = 0+0
= 1 = 0
De même pour l’autre loi de Morgan.
9/32 Donati & Stolfi M1201-5
 Algèbre de Boole Définition
Fonctions Booléennes Propriétés de B
Calcul Propositionnel Exemples

Involution

Théorème d’Involution
∀a ∈ B, a = a

Démonstration
On utilise le lemme avec x = a et y = a.
On a x + y = a + a = 1 et x × y = a × a = 0.
Donc par le lemme on a bien y = x
c’est à dire a = a.

10/32 Donati & Stolfi M1201-5

 Algèbre de Boole Définition
Fonctions Booléennes Propriétés de B
Calcul Propositionnel Exemples

B22

Algèbre de Boole Bn2

On applique sur des mots de n bits, le ou et le et bit–à–bit (bitwise
or/and) et le complément à 1.
C’est une algèbre de Boole avec 2n éléments.

Cas de B22
B22 = {00, 01, 10, 11} et on a les tables suivantes :

+ 00 01 10 11 × 00 01 10 11
00 00 01 10 11 00 00 00 00 00
01 01 01 11 11 01 00 01 00 01
10 10 11 10 11 10 00 10 00 10
11 11 11 11 11 11 00 01 10 11

11/32 Donati & Stolfi M1201-5

 Algèbre de Boole Définition
Fonctions Booléennes Propriétés de B
Calcul Propositionnel Exemples

Parties d’un ensemble

Parties de E
On obtient une algèbre de Boole en prenant l’intersection (×),
l’union (+) et le complémentaire (barre).

Si E = {a, b}
On obtient une algèbre de Boole à 4 éléments {∅, {a}, {b}, {a, b}}
avec les opérations suivantes :

∪ ∅ {a} {b} E ∩ ∅ {a} {b} E

∅ ∅ {a} {b} E ∅ ∅ ∅ ∅ ∅
{a} {a} {a} E E {a} ∅ {a} ∅ {a}
{b} {b} E {b} E {b} ∅ ∅ {b} {b}
E E E E E E ∅ {a} {b} E
12/32 Donati & Stolfi M1201-5
 Algèbre de Boole
Définition
Fonctions Booléennes
Propriétés
Calcul Propositionnel

Chapitre 5 : Calcul propositionnel et

Algèbre de Boole

1 Algèbre de Boole 3 Calcul

Définition Propositionnel
Propriétés de B Formules
Exemples Sémantique
2 Fonctions Séquents
Booléennes
Définition
Propriétés

13/32 Donati & Stolfi M1201-5

 Algèbre de Boole
Définition
Fonctions Booléennes
Propriétés
Calcul Propositionnel

Fonction Booléenne

Définition
Une fonction booléenne (ou fonction logique) est une application
de Bn2 → B2 .

Exemple

f : B32 → B2
(x , y , z) 7→ x · (y + x · z)

Remarque
Une table de vérité permet de préciser l’état de la sortie en
fonction de l’état de l’entrée.

14/32 Donati & Stolfi M1201-5

 Algèbre de Boole
Définition
Fonctions Booléennes
Propriétés
Calcul Propositionnel

Composant électronique
Circuits logiques
Une fonction booléenne modélise le comportement de n’importe
quel composant électronique qui, en fonction de l’état de l’entrée
(des 0 et des 1 selon le niveau du courant électrique) donne un
résultat en sortie (toujours sous la forme de 0 et de 1).
Ainsi un circuit logique est modélisé par la composition de
plusieurs fonctions logiques.

15/32 Donati & Stolfi M1201-5

 Algèbre de Boole
Définition
Fonctions Booléennes
Propriétés
Calcul Propositionnel

Combien de fonctions booléennes différentes ?

Théorème
Il y a exactement
n
22
fonctions booléennes à n arguments (de arité n).

Démonstration
Définir une fonction booléenne à n arguments revient à remplir un
tableau de vérité qui a 2n lignes (une ligne pour chaque choix de 0
et de 1 de chaque argument).
Pour chacune de ces 2n lignes, il faut choisir entre deux valeurs : 0
ou 1, ce qui donne bien
n
22
choix possibles.
16/32 Donati & Stolfi M1201-5
 Algèbre de Boole
Définition
Fonctions Booléennes
Propriétés
Calcul Propositionnel

Fonctions booléennes à deux arguments

Proposition
Il y a 16 fonction booléennes à 2 arguments.
Il y a 256 fonction booléennes à 3 arguments.
Il y a 65536 fonction booléennes à 4 arguments.

Liste
Exercice en TD pour trouver toutes celles à 2 arguments.

17/32 Donati & Stolfi M1201-5

 Algèbre de Boole
Définition
Fonctions Booléennes
Propriétés
Calcul Propositionnel

Théorème

Théorème
Toutes les fonctions booléennes peuvent s’exprimer à l’aide des
trois opérations élémentaires de l’algèbre de Boole :
la somme
le produit
la barre

Remarque
En général, il peut y avoir plusieurs façons de l’écrire.
Par exemple pour le ou exclusif :

(x · y ) + (x · y ) où (x + y ) · x · y

18/32 Donati & Stolfi M1201-5

 Algèbre de Boole Formules
Fonctions Booléennes Sémantique
Calcul Propositionnel Séquents

Chapitre 5 : Calcul propositionnel et

Algèbre de Boole

1 Algèbre de Boole 3 Calcul

Définition Propositionnel
Propriétés de B Formules
Exemples Sémantique
2 Fonctions Séquents
Booléennes
Définition
Propriétés

19/32 Donati & Stolfi M1201-5

 Algèbre de Boole Formules
Fonctions Booléennes Sémantique
Calcul Propositionnel Séquents

Formules du calcul propositionnel

Définition
Une formule du calcul des propositions est une phrase construite
avec les éléments suivants :
des symboles propositionnels (atomes) : P = {p, p 0 , q, q 0 , . . .}
des symboles de liaison qui sont : ¬ pour la négation, ⇒ pour
l’implication et les parenthèses (),
En suivant les règles suivantes :
1 tout atome est une proposition
2 si F est une proposition alors ¬F est aussi une proposition
3 si F et F 0 sont des propositions alors (F ⇒ F 0 ) est aussi une
proposition
4 toute formule est obtenue par application répétée un nombre
fini de fois des étapes (1), (2), (3).
20/32 Donati & Stolfi M1201-5
 Algèbre de Boole Formules
Fonctions Booléennes Sémantique
Calcul Propositionnel Séquents

Le langage L

Définition
On dénote par L l’ensemble de toutes les formules du calcul des
propositions.
Il s’agit d’un langage dont les règles ci–dessus donnent la syntaxe.

Extension
On ajoute à L deux nouveaux symboles : ∧ (et) et ∨ (ou) qui sont
des "raccourcis" pour :
F ∧ F 0 est ¬(F ⇒ ¬F 0 )
F ∨ F 0 est ¬F ⇒ F 0

21/32 Donati & Stolfi M1201-5

 Algèbre de Boole Formules
Fonctions Booléennes Sémantique
Calcul Propositionnel Séquents

Exemples de formules

Exemples
¬((p ⇒ q) ⇒ (p ⇒ ¬p 0 )) est une proposition ;
p ⇒ (⇒ p)) n’est pas une proposition.
((p ∧ q) ⇒ (p ∨ q))

22/32 Donati & Stolfi M1201-5

 Algèbre de Boole Formules
Fonctions Booléennes Sémantique
Calcul Propositionnel Séquents

Trois niveaux de langage

Il ne faut pas confondre

le méta–langage qui est celui utilisé pour parler de la logique ;
le langage formel L qui est le langage sujet ;
l’algèbre de Boole B2 qui est un espace où l’on calcule.
Bien qu’il y ait des correspondances :

Notion métalangage L B2
disjonction ou ∨ +
conjonction et ∧ ×
implication si...alors ⇒ x +y
négation non ¬ x

23/32 Donati & Stolfi M1201-5

 Algèbre de Boole Formules
Fonctions Booléennes Sémantique
Calcul Propositionnel Séquents

Sémantique

Donner du sens
Une formule du calcul propositionnel n’est a priori qu’une phrase,
construite en suivant certaines règles syntaxique, faisant partie
d’un langage.
Ajouter du sens, c’est faire parler les symboles.
Dans notre cas, on donne un sens en définissant une interprétation
de la formule.
La même formule peut avoir plusieurs interprétations : l’analyse
sémantique consiste à examiner ces interprétation possibles et ce
qui en découle.

24/32 Donati & Stolfi M1201-5

 Algèbre de Boole Formules
Fonctions Booléennes Sémantique
Calcul Propositionnel Séquents

Interprétation
Définition
Une interprétation est une application I : P → B2 qui donne à
chaque variable propositionnelle de P = {p, p 0 , q . . .} une valeur de
vérité 0 ou 1 dans B2 .
Cette interprétation est étendue à toute formule F de L de la
façon suivante :
si F = p ∈ P alors I(F ) = I(p)
si F = ¬F 0 alors I(F ) = I(F 0 )
si F = (F1 ⇒ F2 ) alors I(F ) = I(F1 ) + I(F2 )

Il en découle les interprétations suivantes

si F = (F1 ∧ F2 ) alors I(F ) = I(F1 ) × I(F2 )
si F = (F1 ∨ F2 ) alors I(F ) = I(F1 ) + I(F2 )
25/32 Donati & Stolfi M1201-5
 Algèbre de Boole Formules
Fonctions Booléennes Sémantique
Calcul Propositionnel Séquents

Interprétation et Vérité

Vérité
On dit qu’une formule du calcul des propositions F est vraie pour
l’interprétation I si I(F ) = 1 et fausse si I(F ) = 0.

Exemple
La formule
¬(p ⇒ (q ⇒ ¬p 0 ))
est
vraie pour l’interprétation I(p) = 1, I(q) = 1, I(p 0 ) = 1
fausse pour l’interprétation I(p) = 0, I(q) = 1, I(p 0 ) = 1

26/32 Donati & Stolfi M1201-5

 Algèbre de Boole Formules
Fonctions Booléennes Sémantique
Calcul Propositionnel Séquents

Tautologie

Définitions
Soit F une formule du calcul des propositions.
On dit que :
F est une tautologie si et seulement si ∀I : P → B2 , I(F ) = 1
F est satisfaisable si et seulement si il existe une
interprétation I telle que I(F ) = 1
F est insatisfaisable si et seulement si ∀I : P → B2 , I(F ) = 0

Proposition
Si F est une tautologie, alors ¬F est insatisfaisable.

27/32 Donati & Stolfi M1201-5

 Algèbre de Boole Formules
Fonctions Booléennes Sémantique
Calcul Propositionnel Séquents

Exemples

Exemples
Pour montrer que p ∨ ¬p est une tautologie, il y a deux méthodes
possibles :
table de vérité : chaque ligne est une interprétation possible.
Pour avoir une tautologie, toutes doivent donner 1.

I(p) I(¬p) I(p ∨ ¬p)

0 1 1
1 0 1

on utilise les propriétés de I et les connaissances de B2 :

soit I une interprétation quelconque, alors
I(p ∨ ¬p) = I(p) + I(p) = 1

28/32 Donati & Stolfi M1201-5

 Algèbre de Boole Formules
Fonctions Booléennes Sémantique
Calcul Propositionnel Séquents

Séquents

Définition
Un séquent est un couple (A, F ) où A est un ensemble fini de
formules du calcul des propositions formant les hypothèses, et F
une formule du calcul des propositions formant la conclusion.

Exemples
({p, q, p ⇒ r }, q ⇒ r )
({p ⇒ q, q ⇒ r }, p ⇒ r )

29/32 Donati & Stolfi M1201-5

 Algèbre de Boole Formules
Fonctions Booléennes Sémantique
Calcul Propositionnel Séquents

Conséquences

Définition
Soit A un ensemble de formules du calcul des propositions et F
une formule. On dit que de A on déduit F lorsque

∀I : P → B2 , [ si ∀β ∈ A t.q. I(β) = 1, alors I(F ) = 1]

on note
A |= F

Vocabulaire
On dit que F est une conséquence de A.
Ou encore que le séquent (A, F ) est valide.

30/32 Donati & Stolfi M1201-5

 Algèbre de Boole Formules
Fonctions Booléennes Sémantique
Calcul Propositionnel Séquents

Exemple

Pour prouver que

p ⇒ q, q ⇒ r |= p ⇒ r

on applique toutes les interprétations possibles (il y en a 8) ;

on sélectionne celles qui rendent vraies toutes les hypothèses ;
on vérifie que pour ces interprétations là, la conclusion est
aussi vraie.

31/32 Donati & Stolfi M1201-5

 Algèbre de Boole Formules
Fonctions Booléennes Sémantique
Calcul Propositionnel Séquents

Remarque

Tautologies
Si F est une tautologie, alors le séquent (∅, F ) est valide.

|= F

Prolongements possibles
A |= F
correspond à une vérité sémantique du séquent puisqu’elle se base
sur les interprétations des propositions.
Il existe une théorie de la preuve qui permet de définir quand on
peut construire une preuve de F à partie des hypothèses A. Dans
ce cas on notera :
A`F
32/32 Donati & Stolfi M1201-5