Mathématiques pour l’informatique

Christophe Guyeux et Jean-François Couchot

guyeux[arobase]iut-bm.univ-fcomte[point]fr
couchot[arobase]iut-bm.univ-fcomte[point]fr

9 septembre 2013

Table des matières

I Logique 2

1 Algèbre de Boole 3 I Propriétés générales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 II Règles de calcul dans une algèbre de Boole . . . . . . . . . . . . . . . . . . . . . . . . 4 III Fonctions booléennes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

III.1 Formes canoniques d’une fonction booléenne . . . . . . . . . . . . . . . . . . . 6 III.2 Obtention des formes canoniques . . . . . . . . . . . . . . . . . . . . . . . . . 7

IV Diagrammes de Karnaugh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Logique des prédicats 11 I Les propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 II Les connecteurs logiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

II.1 Tables de vérité des connecteurs logiques . . . . . . . . . . . . . . . . . . . . . 12 II.2 Variables et formules propositionnelles . . . . . . . . . . . . . . . . . . . . . . 14

III Sémantique du calcul propositionnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 III.1 Fonctions de vérité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 III.2 Formules propositionnelles particulières . . . . . . . . . . . . . . . . . . . . . . 17 III.3 Conséquences logiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 III.4 Formules équivalentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 III.5 Simplification du calcul des fonctions de vérité . . . . . . . . . . . . . . . . . . 20 III.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

II Annexes 24

3 Programme Pédagogique National 2005 (PPN) 25

Index 26

Première partie

Chapitre 1

Logique Algèbre de Boole

I Propriétés générales

Définition 1.1 (Algèbre de Boole). On appelle algèbre de Boole la structure algébrique (A, +, ., ) définie par un ensemble (non vide) A et trois opérations :

– la somme booléenne (binaire) : “+”,

– le produit booléen (binaire) : “.” et

– la négation booléenne (unaire) : “ ” (par exemple \overline{a}). et qui doivent posséder les propriétés données du tableau ci-dessous. ♢

Propriété

idempotence

a + a = a  distributivités  a · (b + c) = a · b + a · c
a · a = a  a + b · c = (a + b) · (a + c)

commutativité a + b = b + a involution

\overline{\overline{a}} = a
a · b = b · a
associativité a + (b + c) = (a + b) + c  complémentation  \overline{0} = 1
a · (b · c) = (a · b) · c  \overline{1} = 0

éléments neutres a + 0 = a partition

a + \overline{a} = 1
a · 1 = a  a · \overline{a} = 0

absorption

a + 1 = 1  « Lois de De Morgan »  \overline{a + b} = \overline{a} · \overline{b}
a · 0 = 0  \overline{a · b}= \overline{a} + \overline{b}

Propriétés d’une algèbre de Boole

Remarque 1.1. Les signes opératoires utilisés sont les mêmes que ceux de l’addition et de la multiplication des réels. Cependant, ces opérations n’ont évidemment pas les mêmes propriétés, et ne portent pas sur les mêmes éléments.

Exercice 1.1 (Somme disjonctive). On considère une algèbre de Boole quelconque (E, +, ·, ). On définit l’opération « somme disjonctive », notée ⊕, par a ⊕ b = \overline{a}b + a\overline{b}.

1. Que vaut a ⊕ 0 ? a ⊕ 1 ?

2. Calculez a ⊕ a et a ⊕ \overline{a}.

3. Calculez \overline{a ⊕ b}.

4. Montrez que ⊕ est associative et commutative.

Exercice 1.2 (Opérateurs de Sheffer et de Peirce). Soit (E, +, ·, ) une algèbre de Boole. 1. On définit l’opération de Sheffer^{1} par : a|b = \overline{a} + \overline{b}.

1. D’après le logicien H.M. Sheffer

Comment obtenir \overline{a}, a+b, a·b en n’utilisant que l’opérateur |? Faire de même pour a+\overline{b}; étudier l’associativité de cette opération.

2. On définit la flèche de Peirce^{2} par : a ↓ b = \overline{a} · \overline{b}.Mêmes questions.

II Règles de calcul dans une algèbre de Boole

1. Les priorités habituelles sont respectées pour la somme et le produit booléen.

2. Les éléments neutres sont notés 0 et 1, par analogie avec les entiers de même symbole (ne pas oublier que ces calculs ne se déroulent pas dans ℝ...)

3. Il y a deux distributivités. Celle de la somme (booléenne) sur le produit (booléen) n’est pas habituelle. Par exemple, simplifier (a + b)(a + c)(a + d)(a + e)(a + f)

4. Signalons pour finir que, comme ci-dessus, le point pour le produit est souvent omis. Dans une expression booléenne, une sous-expression est dite « redondante » lorsqu’on peut la sup-

primer sans changer la « valeur » de l’expression :

Propriété 1.1 (Suppression de redondance) : On a les trois règles suivantes : 1. Dans une somme booléenne, tout terme absorbe ses multiples : a + a · b = a.

2. Dans un produit booléen, tout facteur absorbe tout autre facteur qui le contient en tant que terme : a · (a + b) = a.

3. Ajouter à un terme un multiple b de son complément revient à ne lui ajouter que b: a + \overline{a}· b = a + b

Preuve On déomntre les trois règles comme suit :

1. En effet, a + a · b = a · (\overline{b}+ b) + a · b = a · \overline{b}+ a · b + a · b = a · \overline{b}+ a · b (par idempotence) = a · (\overline{b}+ b) = a.

2. En effet, a · (a + b) = a · a + a · b = a + a · b = a.

3. a + \overline{a} · b = (a + \overline{a}) · (a + b) = 1 · (a + b) = a + b.

Exemple 1.3. ab + \overline{a}c + \overline{b}c = ab + (\overline{a} + \overline{b}) · c = ab + \overline{ab}· c = ab + c

Exercice 1.4. Montrer que a · b + \overline{a} · c + b.c = a · b + \overline{a} · c

Exercice 1.5 (Calcul booléen élémentaire). Appliquer au maximum les règles précédentes pour supprimer les redondances dans les calculs suivants.

1. (a + b + c) · (a + \overline{b}+ c) · (a + \overline{b}+ \overline{c})

2. a + \overline{a} · b · c + \overline{a} + a · b

3. a · b + \overline{a} · b · c + a · \overline{b}· c

4. (a + b + c) · (\overline{a} + \overline{b}+ \overline{c} + d)

Exercice 1.6 (Calcul booléen). Même énoncé qu’à l’exercice précédent.

1. (\overline{a} + b)(\overline{c} + \overline{a} · \overline{b}+ a · b) .

2. (a + \overline{b}+ \overline{c}) · (\overline{a} + b) · (\overline{b}+ c).

3. (a + c) · (\overline{a} + d) · (\overline{b}+ \overline{e}) · (\overline{b}· \overline{c} + b · c) · (\overline{d}+ c · e) · (\overline{c} + d).

4. (\overline{a} · \overline{a · (\overline{b}+ \overline{c})} + a · (\overline{b}+ \overline{c})) · (\overline{b}· \overline{\overline{a} + c} + (\overline{a} + c) · b) · (a · \overline{b}· c + \overline{a · \overline{b}}· \overline{c}).

2. Lorsque les logiciens, dans les années 1930, cherchèrent un symbole pour exprimer le connecteur découvert par C.S.

Peirce (1839-1914), “Pierce Arrow” était le nom d’une célèbre marque de voiture !

III Fonctions booléennes

Soit A une algèbre de Boole.

Définition 1.2 (Fonction booléenne). On appelle fonction booléenne de n variables toute application de A^{n} dans A dont l’expression ne contient que :

– les symboles des opérations booléennes,

– des symboles de variables, de constantes,

– d’éventuelles parenthèses. ♢

Exemple 1.7. f(a, b, c) = a · \overline{b}+ c.

Définition 1.3 (Aspect d’une variable). Si a est une variable booléenne, elle peut intervenir dans l’expression d’une fonction booléenne sous la forme a ou sous la forme \overline{a}, qui sont appelées les deux aspects de cette variable : affirmé et nié. ♢

Définition 1.4 (Fonction booléenne nulle). On appelle fonction booléenne nulle la fonction booléenne qui, à chaque valeur des variables, associe la valeur 0. Son expression est f(x_{1}, x_{2}, …, x_{n}) = 0. ♢

Définition 1.5 (Fonction référentiel). On appelle fonction référentiel la fonction booléenne qui, à chaque valeur des variables, associe la valeur 1. Son expression est f(x_{1}, x_{2}, …, x_{n}) = 1. ♢

Définition 1.6 (Minterme, maxterme). Un minterme à n variables est une fonction booléenne à n variables dont l’expression se présente sous la forme du produit d’un aspect et d’un seul de chacune des n variables.

Définition analogue pour un maxterme , en remplaçant dans la définition précédente « produit » par « somme ». ♢

Exemple 1.8 (Minterme à trois variables). a · \overline{b}· c

Exemple 1.9 (Maxterme à trois variables). \overline{a} + b + \overline{c}.

Exercice 1.10. Pour 3 variables a, b et c, repérez les mintermes et les maxtermes : b\overline{c}, a + \overline{b}+ c, a\overline{b}b\overline{c}, \overline{a}bc, a + \overline{b}c.

Exercice 1.11. Dressez la liste des mintermes et des maxtermes pour deux variables a et b.

Propriété 1.2 (Nombre de mintermes et de maxtermes) : Les mintermes et maxtermes, pour un nombre donné n de variables, sont au nombre de 2^{n} chacun.

III.1 Formes canoniques d’une fonction booléenne

Définition 1.7 (Monômes). Un monôme est une fonction booléenne produit de variables booléennes éventuellement niées. ♢

Exercice 1.12. Parmi les expressions suivantes dire lesquelles sont des monômes et lesquelles ne le sont pas en justifiant : a + b, a + bc, a(b + c), a\overline{b}, b.

Propriété 1.3 : Quelle que soit l’expression de la fonction booléenne, il est possible de la mettre sous la forme d’une somme de monômes.

Preuve En effet, comme elle ne fait intervenir que les trois opérations booléennes, il suffit de lui appliquer les règles du calcul booléen :

1. On développe les négations (en appliquant les règles \overline{a + b} = \overline{a} · \overline{b}et \overline{a · b}= \overline{a} + \overline{b}), jusqu’à ce qu’il n’y ait plus de négations que sur les variables ;

2. Puis on développe les produits qui portent sur des sommes, en utilisant la distributivité du produit sur la somme ;

3. On obtient ainsi une expression qui s’écrit sans parenthèses, et qui ne contient que des sommes de produits de variables éventuellement niées.

Propriété 1.4 : Chaque monôme peut ensuite être mis sous la forme d’une somme de mintermes.

Preuve En effet, si, dans l’expression de ce monôme, toutes les variables interviennent, c’est déjà un minterme.

Dans le cas contraire, il manque (par exemple) la variable a dans son expression : on la fait intervenir sous la forme (\overline{a}+ a). On développe, les deux monômes obtenus font intervenir la variable a.

Ou bien, il s’agit de mintermes et le processus est terminé, ou bien il manque encore une variable, qu’on fait intervenir en utilisant le même procédé, et ainsi de suite jusqu’à aboutir aux mintermes.

On fait évidemment disparaître du résultat, par idempotence, les occurrences multiples de mintermes, pour pouvoir énoncer le résultat suivant :

Propriété 1.5 (Forme canonique disjonctive) : Toute fonction booléenne à n variables (autre que la fonction nulle) peut se mettre sous la forme d’une somme de mintermes à n variables.

Cette forme, unique, s’appelle Forme Canonique Disjonctive (dans la suite, FCD).

Remarque 1.2. L’unicité de cette FCD permet la comparaison des fonctions booléennes entre elles.

Par négation booléenne de ce résultat, on obtient :

Propriété 1.6 (Forme canonique conjonctive) : Toute fonction booléenne de n variables (autre que la fonction référentiel) peut se mettre sous la forme d’un produit de maxtermes à n variables.

Cette forme, unique, est la Forme Canonique Conjonctive (FCC dans la suite).

III.2 Obtention des formes canoniques

La méthode algébrique consiste à :

– tout développer pour mettre l’expression sous la forme d’une somme de monômes,

– dans chaque terme de cette somme, faire apparaître les valeurs qui n’y figurent pas.

Exemple 1.13. On illustre cela : f(a, b, c) = a + bc = a(\overline{b}+ b)(\overline{c} + c) + (\overline{a} + a)bc = a\overline{b}\overline{c} + a\overline{b}c + ab\overline{c} + abc + \overline{a}bc + abc = m_{3} + m_{4} + m_{5} + m_{6} + m_{7}.

Pour la FCC, on peut imaginer une méthode analogue.

Exemple 1.14. f(a, b, c) = a + bc = (a + b)(a + c) = (a + b + \overline{c}c)(a + \overline{b}b + c)

= (a + b + \overline{c}) · (a + b + c) · (a + \overline{b}+ c) · (a + b + c) = M_{5}M_{6}M_{7}

Remarque 1.3. Si on prend la négation de la FCD, on obtient bien sûr une FCC... mais pas celle de la fonction, celle de sa négation !

Il suffit de prendre la négation de la fonction, de calculer sa FCD puis de prendre la négation du résultat.

Exercice 1.15. Obtenir la FCC de x + \overline{y}z.

Il existe une autre méthode pour obtenir ces formes canoniques : la méthode des diagrammes.

IV Diagrammes de Karnaugh

La représentation des fonctions booléennes par diagrammes de Karnaugh-Veitch : est fondée sur les propriétés des mintermes (ils réalisent une partition de l’unité),

Ces derniers diagrammes deviennent rapidement inextricables quand le nombre de variables augmente, c’est pourquoi, dans les diagrammes de Karnaugh, on divise systématiquement l’« univers » (le référentiel E) en deux parties égales en superficie pour représenter la partie concernée et son complémentaire.

À chaque introduction de variable supplémentaire, chaque case du précédent diagramme est divisée en 2.

On obtient, par exemple :

\begin{aligned}& \overline{a} & a \\ \overline{b} & \overline{a}\overline{b} & a\overline{b} \\ b & \overline{a}b & ab \end{aligned}

Cas de trois variables :

– les deux premières colonnes correspondent à \overline{a}, les deux dernières à a,

– la première et la dernière colonne correspondent à \overline{b}, les deux centrales à b,

– enfin, la première ligne est associée à \overline{c}, la deuxième à c. ...ce qui donne

00 01 11 10
0 \overline{a}\overline{b}\overline{c} \overline{a}b\overline{c} ab\overline{c} a\overline{b}\overline{c}
1 \overline{a}\overline{b}c \overline{a}bc abc a\overline{b}c

Dans un tel diagramme, chaque case représente un minterme. Les autres monômes regroupent un nombre de cases qui est une puissance de 2, selon le nombre de variables présentes.

Exercice (corrigé) 1.16. Faire un diagramme à cinq variables.

000 001 011 010 110 111 101 100
00 \overline{a}\overline{b}\overline{c}\overline{d}\overline{e} \overline{a}\overline{b}c\overline{d}\overline{e} \overline{a}bc\overline{d}\overline{e} \overline{a}b\overline{c}\overline{d}\overline{e} ab\overline{c}\overline{d}\overline{e} abc\overline{d}\overline{e} a\overline{b}c\overline{d}\overline{e} a\overline{b}\overline{c}\overline{d}\overline{e}
01 \overline{a}\overline{b}\overline{c}\overline{d}e \overline{a}\overline{b}c\overline{d}e \overline{a}bc\overline{d}e \overline{a}b\overline{c}\overline{d}e ab\overline{c}\overline{d}e abc\overline{d}e a\overline{b}c\overline{d}e a\overline{b}\overline{c}\overline{d}e
11 \overline{a}\overline{b}\overline{c}de \overline{a}\overline{b}cde \overline{a}bcde \overline{a}b\overline{c}de ab\overline{c}de abcde a\overline{b}cde a\overline{b}\overline{c}de
10 \overline{a}\overline{b}\overline{c}d\overline{e} \overline{a}\overline{b}cd\overline{e} \overline{a}bcd\overline{e} \overline{a}b\overline{c}d\overline{e} ab\overline{c}d\overline{e} abcd\overline{e} a\overline{b}cd\overline{e} a\overline{b}\overline{c}d\overline{e}

Les diagrammes peuvent être utilisés en réunion, en intersection ou en complémentation. Ils permettent :

– d’obtenir la FCD d’une fonction booléenne plus aisément que par le calcul algébrique (utilisé pour découvrir la forme en question),

– une première approche du problème de la simplification des fonctions booléennes (dans des cas simples et pour un petit nombre de variables)...

Utilisation des diagrammes de Karnaugh pour représenter les fonctions booléennes...

En réunion. Soit par exemple f(a, b, c) = a + \overline{b}c. Son diagramme est :

[figure: c; ab] 00 01 11 10
0  0 2 6 4
1  1 3 7 5

On lit aisément la FCD de f sur le diagramme : f(a, b, c) = m_{1} + m_{4} + m_{5} + m_{6} + m_{7}. En intersection. Soit f(a, b, c) = (a + \overline{b})(a + c).

On peint en rouge les cases correspondant à a+\overline{b}, et on note en italique les nombres correspondant à a + c:

[figure: c; ab] 00 01 11 10
0  0 2 6 4
1  1 3 7 5

La représentation de f est contenue dans les cases rouges possédant les nombres en italique. Comme (a + \overline{b})(a + c) = a + \overline{b}c, on retrouve la même FCD.

En complémentation. Soit f(a, b, c) = a + \overline{b}c, de diagramme :

[figure: c; ab] 00 01 11 10
0  0 2 6 4
1  1 3 7 5
Alors la négation de a + \overline{b}c est dans les cases pas rouge : la FCD de \overline{f} est m_{0} + m_{2} + m_{3}.

Exercice 1.17 (Fonctions booléennes). Donner la forme canonique disjonctive de la fonction booléeene dont l’expression est

f(a, b, c, d, e) = \overline{a} · [\overline{b}· \overline{e} · (c + d) + b · (\overline{c} · \overline{d}· \overline{e} + c · \overline{d · e})].

Exercice 1.18. Pour chacune des expressions suivantes...

\begin{aligned}E_{1} & = & xyz + xy\overline{z} + \overline{x}y\overline{z} + \overline{x}\overline{y}z \\ E_{2} & = & xyz + xy\overline{z} + x\overline{y}z + \overline{x}\overline{y}z \\ E_{3} & = & xyz + xy\overline{z} + \overline{x}y\overline{z} + \overline{x}\overline{y}\overline{z} + \overline{x}\overline{y}z \end{aligned}

donner la forme minimale en exploitant les diagrammes de Karnaugh

Exercice 1.19 (Application de la méthode de Karnaugh). Trouver une forme minimale de E = x\overline{y} + xyz + \overline{x}\overline{y}\overline{z} + \overline{x}yz\overline{t}.

Exercice 1.20 (Composition de la méthode de Karnaugh). On considère deux fonctions booléennes u et v des quatres variables a, b, c, d définies par u = (a + d)(b + c) et v = (a + c)(\overline{b}+ d).

1. Dessiner les diagrammes de Karnaugh de u et de v.

2. En déduire le diagramme de Karnaugh de w = uv + \overline{u}\overline{v}.

3. Donner une forme minimale pour w

Exercice 1.21 (BTS-2009). La société K-Gaz décide de recruter en interne des collaborateurs pour sa filiale en Extrême-Orient. Pour chaque employé, on définit les variables booléennes suivantes :

– a = 1 s’il a plus de cinq ans d’ancienneté dans l’entreprise ;

– b = 1 s’il possède un B.T.S. informatique de gestion (BTS-IG) ;

– c = 1 s’il parle couramment l’anglais. La direction des ressources humaines décide que pourront postuler les employés :

– qui satisfont aux trois conditions,

– ou qui ont moins de 5 ans d’ancienneté mais qui maîtrisent l’anglais,

– ou qui ne maîtrisent pas l’anglais mais qui possèdent un BTS-IG.

1. Écrire une expression booléenne E traduisant les critères de la direction.

2. Représenter l’expression E par un tableau de Karnaugh.

3. À l’aide du tableau de Karnaugh, donner une expression simplifiée de E.

4. Retrouver ce résultat par le calcul.

5. En déduire une version simplifiée des critères de la direction.

Exercice 1.22 (BTS-2002). On considère l’expression E = a.c + b.c + a.b + a.b.c dépendant des variables booléennes a, b et c:

1. Simplifier l’expression E à l’aide de la lecture d’un tableau de Karnaugh (ou d’une table de vérité).

2. Dans un organisme qui aide des personnes au chômage à trouver un emploi, on considère pour ces personnes, trois variables booléennes définies ainsi :

– a = 1 si la personne est âgée de 45 ans ou plus (sinon a = 0) ;

– b = 1 si la personne est au chômage depuis un an ou plus (sinon b = 0) ;

– c = 1 si la personne a déjà suivi une formation l’année précédente (sinonc = 0). Une formation qualifiante sera mise en place pour les personnes vérifiant au moins un des critères suivants :

– avoir 45 ans ou plus et être au chômage depuis moins de un an ;

– avoir moins de 45 ans et ne pas avoir suivi de formation l’année précé- dente ;

– être au chômage depuis un an ou plus et ne pas avoir suivi de formation l’année précédente ;

– avoir moins de 45 ans, être au chômage depuis moins de un an et avoir suivi une formation l’année précédente.

Les personnes qui ne répondent à aucun de ces quatre critères, pourront par- ticiper à un stage d’insertion en entreprise.

(a) Écrire l’expression booléenne F en fonction des variables a, b et c qui traduit le fait que la personne pourra suivre cette formation qualifiante.

(b) En déduire une caractérisation simple des personnes qui participeront à un stage d’insertion en entreprise.

Fin du Chapitre

Logique des prédicats

Qu’est-ce donc qu’un raisonnement ? Si l’on sait que tous les écureuils sont des rongeurs, que tous les rongeurs sont des mammifères, que tous les mammifères sont des vertébrés et que tous les vertébrés sont des animaux, on peut en déduire que tous les écureuils sont des animaux.[…].

Ce raisonnement est simple à l’extrême, mais sa structure ne diffère pas fondamentalement de celle d’un raisonnement mathématique. Dans les deux cas, le raisonnement est formé d’une suite de propositions dans laquelle chacune découle logiquement des précédentes, […]. Dans ce cas, on applique la même règle trois fois. Cette règle permet, si l’on sait déjà que tous les Y sont des X et que tous les Z sont des Y, de déduire que tous les Z sont des X [Dow07].

I Les propositions

L’homme exprime son raisonnement par un discours, et ce discours utilise une langue (une langue naturelle, français, anglais,…). D’une manière générale, ce discours est articulé en phrases, d’un niveau de complexité variable, et c’est l’étude de ces « énoncés » que se propose de faire la logique.

Définition 2.1 (Proposition). Parmi tous les énoncés possibles qui peuvent être formulés dans une langue, on distingue ceux auxquels il est possible d’attribuer une « valeur de vérité » : vrai ou faux. Ces énoncés porteront le nom de propositions . ♢

Exemple 2.1. Ainsi, « Henri IV est mort assassiné en 1610 », « Napoléon Bonaparte a été guillotiné en 1852 » sont des propositions, puisqu’on peut leur attribuer une valeur de vérité (« vrai » pour la première, « faux » pour la seconde).

Le calcul que l’on étudie considère toujours comme acquises les vérités suivantes, élevées au rang d’axiomes.

Principe de non-contradiction : Une proposition ne peut être simultanément vraie et fausse. Principe du tiers-exclu : Une proposition est vraie ou fausse (il n’y a pas d’autre possibilité).

II Les connecteurs logiques

L’analyse logique d’une phrase (reconnue comme proposition) fait apparaître des sous-phrases qui constituent elles-mêmes des propositions. Ces « membres de phrases » sont reliés entre eux par des « connecteurs logiques ».

Considérons l’énoncé : « J’ai obtenu une mauvaise note à cet examen parce que je n’ai pas assez travaillé ou parce que le cours est trop difficile ». On suppose qu’il est possible d’attribuer une valeur de vérité à cet énoncé « global », ce qui le classe parmi les propositions.

Globalement, cet énoncé exprime que « ma mauvaise note » est conséquence de l’une (au moins) des deux causes suivantes :

– « mon manque de travail »,

– « un cours trop difficile », soit :

( « mon manque de travail » ou « cours trop difficile ») entraîne « ma mauvaise note »

D’une manière générale, le calcul propositionnel ne se préoccupe que des valeurs de vérité, et pas du tout des liens sémantiques qui peuvent exister entre des propositions. Ces dernières sont reliées entre elles syntaxiquement par des connecteurs comme « ou » ou « entraîne ». Les connecteurs logiques sont donc des symboles qui permettent de produire des propositions (« plus complexes ») à partir d’autres propositions (« plus simples »).

II.1 Tables de vérité des connecteurs logiques

P Q P ∨ Q
F F  F
F V  V
V F  V
V V  V
P Q P ∧ Q
F F  F
F V  F
V F  F
V V  V

\begin{matrix}P & ¬P \\ F & V \\ V & F \end{matrix}

P Q P ⇒ Q
F F  V
F V  V
V F  F
V V  V
P Q P ⟺ Q
F F  V
F V  F
V F  F
V V  V

Remarque 2.1. – Dans le langage courant, le mot « ou » est souvent employé de deux façons distinctes :

– il est parfois utilisé avec le sens « les deux cas peuvent se produire » (comme ici) et,

– parfois avec le sens « p ou q , mais pas les deux » (e.g. « il ira à Paris ou à Marseille »). Sauf indication contraire, le « ou » sera toujours employé avec cette première signification.

– Lorsque la proposition P est fausse, la proposition « Si P, alors Q » est vraie, quelle que soit la valeur de vérité de la proposition Q,

Exercice 2.2. Déterminer la valeur de vérité des propositions suivantes dans le monde actuel (c.-à-d. celui dans lequel nous vivons) :

1. « si la terre est plate, alors la lune est carrée ; »

2. « si le soleil tourne autour de la terre alors la terre est ronde »

3. « si la terre est ronde alors le soleil tourne autour de la terre »

4. « si vous étudiez la logique alors E = m.c^{2} »

5. « si Napoléon est mort alors il a gagné la bataille de Waterloo »

6. « s’il pleut en ce moment alors il pleut en ce moment »

7. « si tous les hommes sont passionnés par la logique alors Dieu existe »

8. « si le Diable existe alors ceci est un exercice de logique »

La manière de mener un raisonnement qui utilise éventuellement des propositions qui se présentent sous la forme d’implications logiques est l’objet de la théorie de la déduction qui sera étudiée plus loin. Remarque 2.2. Même remarque que pour l’implication logique : l’équivalence logique de deux propositions fausses est une proposition vraie.

Exercice (corrigé) 2.3. En notant M et C les affirmations suivantes :

– M = « Jean est fort en Maths »,

– C = « Jean est fort en Chimie », représenter les affirmations qui suivent sous forme symbolique, à l’aide des lettres M et C et des connecteurs usuels.

1. « Jean est fort en Maths mais faible en Chimie »

2. « Jean n’est fort ni en Maths ni en Chimie »

3. « Jean est fort en Maths ou il est à la fois fort en Chimie et faible en Maths »

4. « Jean est fort en Maths s’il est fort en Chimie »

5. « Jean est fort en Chimie et en Maths ou il est fort en Chimie et faible en Maths » Réponses :

1. M ∧ (¬C) ; 2. (¬M) ∧ (¬C) ; 3. M ∨ (C ∧ ¬M) ; 4. C ⇒ M ; 5. (M ∧ C) ∨ (¬M ∧ Q).

Exercice 2.4. En notant M, C et A les trois affirmations suivantes :

– M = « Pierre fait des Maths » ;

– C = « Pierre fait de la Chimie » ;

– A = « Pierre fait de l’Anglais ». Représenter les affirmations qui suivent sous forme symbolique, à l’aide des lettres M, C, A et des

connecteurs usuels.

1. « Pierre fait des Maths et de l’Anglais mais pas de Chimie »

2. « Pierre fait des Maths et de la Chimie mais pas à la fois de la Chimie et de l’Anglais »

3. « Il est faux que Pierre fasse de l’Anglais sans faire de Maths »

4. « Il est faux que Pierre ne fasse pas des Maths et fasse quand même de la chimie »

5. « Il est faux que Pierre fasse de l’Anglais ou de la Chimie sans faire des Maths »

6. « Pierre ne fait ni Anglais ni Chimie mais il fait des Maths »

Exercice 2.5.

1. Dans un même tableau, construire les tables de vérité de P ∧ Q, ¬(P ∧ Q), ¬P ∧ ¬Q, P ∧ ¬Q P ∨ Q, ¬(P ∨ Q) , ¬P ∨ ¬Q, P ⇒ Q et ¬(P ⇒ Q)

2. Définir les négations de P ∧ Q, P ∨ Q et P ⇒ Q.

Exercice 2.6. Énoncer la négation des affirmations suivantes en évitant d’employer l’expression : « il est faux que »

1. « S’il pleut ou s’il fait froid je ne sors pas »

2. « Le nombre 522 n’est pas divisible par 3 mais il est divisible par 7 »

3. « Ce quadrilatère n’est ni un rectangle ni un losange »

4. « Si Paul ne va pas travailler ce matin il va perdre son emploi »

5. « Tout nombre entier impair peut être divisible par 3 ou par 5 mais jamais par 2 »

6. « Tout triangle équilatéral a ses angles égaux à 60° »

II.2 Variables et formules propositionnelles

Comme le calcul propositionnel ne s’occupe que des valeurs de vérité, il est possible, dans une expression logique, de remplacer chaque proposition donnée par un symbole (en général, une lettre de l’alphabet majuscule), ou variable propositionnelle et d’étudier ensuite les valeurs de vérité de l’expression en fonction des valeurs de vérité de ces symboles.

Propriété 2.1 : Les règles (de syntaxe) qui permettent de former des formules propositionnelles sont les suivantes :

– toute variable propositionnelle est une formule propositionnelle ;

– si F et G sont des formules propositionnelles, alors ¬(F), (F) ∨ (G), (F) ∧ (G), (F) ⇒ (G) et (F) ⟺ (G) sont des formules propositionnelles.

Remarque 2.3. Ce ne sont plus des propositions, en ce sens qu’elles n’ont en général pas de valeur de vérité déterminée. Cette dernière est une fonction des valeurs de vérité des variables propositionnelles qui interviennent dans l’expression de la formule propositionnelle considérée.

Exercice 2.7. A et B sont des variables propositionnelles, susceptibles de représenter n’importe quelle proposition. Formaliser, à l’aide de connecteurs logiques appropriés, les énoncés suivants :

1. « A si B »

2. « A est condition nécessaire pour B »

3. « A sauf si B »

4. « A seulement si B »

5. « A est condition suffisante pour B »

6. « A bien que B »

7. « Non seulement A, mais aussi B »

8. « A et pourtant B »

9. « A à moins que B »

10. « Ni A, ni B » Exercice 2.8. Les variables propositionnelles N et T serviront, dans cet exercice, à représenter (respectivement) les propositions « Un étudiant a de bonnes notes » et « Un étudiant travaille ». À l’aide des variables propositionnelles N et T, formaliser les propositions suivantes (si, pour l’une ou l’autre d’entre elles, la traduction vous paraît impossible, dites-le et expliquez pourquoi) :

1. C’est seulement si un étudiant travaille qu’il a de bonnes notes.

2. Un étudiant n’a de bonnes notes que s’il travaille.

3. Pour un étudiant, le travail est une condition nécessaire à l’obtention de bonnes notes.

4. Un étudiant a de mauvaises notes, à moins qu’il ne travaille.

5. Malgré son travail, un étudiant a de mauvaises notes.

6. Un étudiant travaille seulement s’il a de bonnes notes.

7. À quoi bon travailler, si c’est pour avoir de mauvaises notes ?

8. Un étudiant a de bonnes notes sauf s’il ne travaille pas.

Exercice 2.9. Combien de lignes contient la table de vérité d’une formule propositionnelle qui dépend de n variables ?

Lorsqu’on remplace, dans une formule propositionnelle, les variables propositionnelles par des propositions, l’assemblage obtenu est une proposition. Cependant, une formule propositionnelle n’est pas une proposition : A ⇒ B n’est ni vrai ni faux.

Propriété 2.2 (Règles de priorité des connecteurs logiques) : Les conventions de priorité des connecteurs logiques sont les suivantes (par ordre de priorité décroissante) :

– la négation,

– la conjonction et la disjonction (au même niveau),

– l’implication et l’équivalence (au même niveau).

Exemple 2.10. ¬A ∧ B ⇒ C doit être interprété par ((¬A) ∧ B) ⇒ C et A ∨ B ∧ C n’a pas de sens, car les deux connecteurs ont même niveau de priorité.

Propriété 2.3 (Associativité des opérateurs ∨ et ∧) : Les opérateurs ∨ et ∧ sont associatifs :

– (A ∨ B) ∨ C = A ∨ (B ∨ C) = A ∨ B ∨ C,

– (A ∧ B) ∧ C = A ∧ (B ∧ C) = A ∧ B ∧ C. Mais le parenthésage est obligatoire quand ∨ et ∧ se trouvent dans la même proposition, puisqu’il n’y a pas de priorité entre ∨ et ∧: (A ∨ B) ∧ C ≠ A ∨ (B ∧ C).

Remarque 2.4. L’implication n’est pas associative : A ⇒ (B ⇒ C) ≠ (A ⇒ B) ⇒ C. Donc les parenthèses sont obligatoires. Il en est de même pour ⟺, et a fortiori quand ces deux opérateurs sont mélangés dans une même proposition.

Exercice (corrigé) 2.11. Quelles sont les façons de placer des parenthèses dans ¬P ∨ Q ∧ ¬R afin d’obtenir l’expression correcte d’une formule propositionnelle ? Déterminer la table de vérité de chacune des formules obtenues.

Réponses :

1) ¬P ∨(Q∧¬R) ; 2) (¬P ∨Q)∧¬R; 3) (¬(P ∨Q))∧¬R; 4) ¬(P ∨(Q∧¬R)) ; 5) ¬((P ∨Q)∧¬R). Tables de vérité :

\begin{matrix}P & Q & R & 1 & 2 & 3 & 4 & 5 \\ V & V & V & F & F & F & F & V \\ V & V & F & V & V & F & F & F \\ V & F & V & F & F & F & F & V \\ V & F & F & F & F & F & F & F \\ F & V & V & V & F & F & V & V \\ F & v & F & V & V & F & F & F \\ F & F & V & V & F & F & V & V \\ F & F & F & V & V & V & V & V \end{matrix}

Exercice (corrigé) 2.12. Construire les tables de vérité des formules propositionnelles suivantes : 1. ¬P ∧ Q

2. ¬P ⇒ P ∨ Q

3. ¬(¬P ∧ ¬Q)

4. P ∧ Q ⇒ ¬Q

5. (P ⇒ Q) ∨ (Q ⇒ P)

6. (P ⇒ ¬Q) ∨ (Q ⇒ ¬P)

7. (P ∨ ¬Q) ∧ (¬P ∨ Q)

8. P ⇒ (¬P ⇒ P) Réponse :

\begin{matrix}P & Q & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ V & V & F & V & V & F & V & F & V & V \\ V & F & F & V & V & V & V & V & F & V \\ F & V & V & V & V & V & V & V & F & V \\ F & F & F & F & F & V & V & V & V & V \end{matrix}

Exercice 2.13. Faire de même avec 1. (P ∨ Q) ∨ (¬R)

2. P ∨ (¬(Q ∧ R))

3. (¬P) ⇒ ((¬Q) ∨ R)

4. (P ∨ R) ⇒ (R ∨ (¬P))

5. (P ⇒ (¬Q)) ∨ (Q ⇒ R)

6. (P ∨ (¬Q)) ⇒ ((¬P) ∨ R)

7. (P ⇒ (¬R)) ∨ (Q ∧ (¬R))

8. (P ⇒ Q) ⇒ ((Q ⇒ R) ⇒ (P ⇒ R))

III Sémantique du calcul propositionnel

Dans ce qui suit, on donne un sens aux symboles représentant les connecteurs logiques en fonction de la valeur de vérité des propositions de base (ainsi ¬ signifie non).

III.1 Fonctions de vérité

Soit F une formule propositionnelle, dans l’expression de laquelle interviennent les variables propositionnelles P_{1}, P_{2}, P_{3}, …, P_{n}. À chacune de ces variables propositionnelles, on associe une variable booléenne (généralement la même lettre de l’alphabet, mais en minuscules), qui représente la valeur de vérité qu’elle peut prendre (faux ou vrai, F ou V, 0 ou 1).

Définition 2.2 (Fonction de vérité de F). La fonction de vérité de F est la fonction booléenne Φ_{F} des n variables booléennes concernées, obtenue de la manière suivante :

1. Si F est de la forme P, où P est une variable propositionnelle, alors Φ_{F}(p) = p.

2. Si F est de la forme ¬G, où G est une formule propositionnelle, alors Φ_{F} = \overline{Φ_{G}} .

3. Si F est de la forme G∨H, où G et H sont des formules propositionnelles, alors Φ_{F} = Φ_{G}+Φ_{H}.

4. Si F est de la forme G ∧ H, où G et H sont des formules propositionnelles, alors Φ_{F} = Φ_{G} · Φ_{H}.

5. Si F est de la forme G ⇒ H, où G et H sont des formules propositionnelles, alors Φ_{F} = \overline{Φ_{G}} +Φ_{H}.

6. Si F est de la forme G ⟺ H, où G et H sont des formules propositionnelles, alors Φ_{F} = \overline{Φ_{G}} · \overline{Φ_{H}} + Φ_{G} · Φ_{H}.

Exemple 2.14. Soit F = A ∨ ¬B ⟺ (B ⇒ C). On a alors :

Φ_{F}(a, b, c) = \overline{a + \overline{b}} · \overline{\overline{b}+ c} + (a + \overline{b}) · (\overline{b}+ c) = \overline{a} · b · b · \overline{c} + \overline{b}+ a · c = \overline{b}+ \overline{a} · \overline{c} + a · c.

Remarque 2.5. Il est clair que les « tables de vérité » des connecteurs logiques sont les mêmes que les tables des opérations booléennes sur {faux, vrai}

– de la négation booléenne (pour la négation logique),

– de la somme booléenne (pour la disjonction logique),

– du produit booléen (pour la conjonction logique),

Ainsi, la détermination de la valeur de vérité d’une proposition composée se ramène à un simple calcul en algèbre de Boole sur la fonction de vérité de la formule propositionnelle associée.

III.2 Formules propositionnelles particulières

On verra dans cette section deux formules particulières : les tautologies et les antilogies.

III.2.1 Tautologies

Définition 2.3 (Tautologie). Toute formule propositionnelle dont la fonction de vérité est la fonction référentielle est appelée tautologie . ♢

Ainsi, une tautologie est une formule propositionnelle dont la fonction de vérité est indépendante des valeurs de vérité associées à ses variables. Autrement dit, quelle que soit la valeur de vérité des propositions par lesquelles on remplacerait les variables propositionnelles, la proposition obtenue serait vraie.

Notation : La notation utilisée pour marquer une tautologie F est ⊧ F (se lit : « F est une tautologie »).

Exemple 2.15. Soit F = A ⇒ A. Comme Φ_{F}(a) = \overline{a} + a = 1, on a ⊧ F.

Exemple 2.16. F = (A ⇒ C) ⇒ ((B ⇒ C) ⇒ (A ∨ B ⇒ C)).

\begin{aligned}Φ_{F}(a, b, c) & = \\ \overline{Φ_{A⇒C}} (a, c) + \overline{Φ_{B⇒C}} (b, c) + Φ_{A∨B⇒C} (a, b, c) & = \\ \overline{\overline{a} + c} + \overline{\overline{b}+ c} + \overline{a + b} + c & = \\ a\overline{c} + b\overline{c} + \overline{a}\overline{b}+ c & = \\ a + b + \overline{a}\overline{b}+ c & = 1 + c = 1 \end{aligned}

Il ne faudrait pas croire, au vu de ces exemples simples, que les tautologies se ramènent toutes à des trivialités totalement inintéressantes et indignes d’être énoncées. Ainsi, dans une théorie mathématique, tous les théorèmes sont des tautologies ; la reconnaissance de cette propriété n’est cependant pas toujours complètement évidente…

Exercice 2.17. Les formules propositionnelles suivantes sont-elles des tautologies ?

1. P ⇒ ((¬P) ⇒ P)

2. ⊧ ¬¬A ⇒ A

3. P ⇒ (P ⇒ P)

4. (P ⇒ Q) ⇒ ((Q ⇒ R) ⇒ (P ⇒ R))

5. ⊧ (A ⇒ C) ⇒ ((B ⇒ C) ⇒ (A ∨ B ⇒ C))

6. P ⇒ (P ⇒ Q)

7. ⊧ (A ⇒ B) ⇒ ((A ⇒ ¬B) ⇒ A)

III.2.2 Antilogies

Définition 2.4 (Antilogie). Toute formule propositionnelle dont la fonction de vérité est la fonction nulle est appelée antilogie . ♢

La proposition obtenue en remplaçant les variables par des propositions ne peut alors jamais être vraie.

Exemple 2.18. Soit F = A ∧ ¬A. Φ_{F}(a) = a · \overline{a} = 0. Donc F est bien une antilogie.

Exercice 2.19. Calculer les fonctions de vérité des formules propositionnelles suivantes, et dire s’il s’agit éventuellement de tautologies ou d’antilogies :

1. A ∧ (A ∨ B) ⟺ A

2. (¬A ∨ B ⇒ (A ⇒ ¬A ∨ B)) ⟺ (¬A ∨ B ⇒ (A ⇒ (A ⇒ B)))

3. (A ⇒ B) ∧ (A ∨ C) ⇒ B ∨ C

4. (A ⇒ B) ∧ (A ∨ C) ⇒ (A ⇒ C)

III.3 Conséquences logiques

Soit F = {F_{1}, …, F_{n}} un ensemble de formules propositionnelles .

Définition 2.5 (Conséquence logique). On dit que la formule propositionnelle A est une conséquence logique des formules propositionnelles F_{1}, …, F_{n} lorsque, chaque fois que les fonctions de vérité Φ_{F_{1}}, …, Φ_{F_{n}} prennent simultanément la valeur « vrai » (ou 1), il en est de même pour la fonction de vérité de la forme A. ♢

Notation : On note ce résultat : {F_{1}, …, F_{n}} ⊧ A (se lit : A est conséquence logique de {F_{1}, …, F_{n}}).

Exemple 2.20. On reconsidère l’ensemble des deux formules propositionnelles

{P, P ⇒ Q}

et on va montrer autrement que Q est conséquence logique de ces deux formules. Autrement dit, on va remontrer que : {P, P ⇒ Q}⊧ Q.

– Φ_{P}(p) = p: prend la valeur 1 lorsque p prend la valeur 1.

– Φ_{P ⇒Q} (p, q) = \overline{p}+ q : prend la valeur 1 lorsque p = 0 (quelle que soit la valeur de q) et lorsque p = 1 et q = 1.

– Φ_{P}(p) et Φ_{P ⇒Q} (p, q) prennent simultanément la valeur 1 uniquement lorsque p = 1 et q = 1 ; dans ce cas, Φ_{Q}(q) = q = 1 aussi. Donc Q est conséquence logique de {P, P ⇒ Q}.

Exercice 2.21. Dans chacun des cas suivants, déterminer si le premier ensemble de formules a pour conséquence logique la deuxième formule :

\begin{matrix}4 & \{P ⇒ (Q ∨ R)\} & (P ⇒ Q) ∨ (P ⇒ R) \\ 5 & \{A ⇒ (P ∨ Q), ¬S ∨ A\} & (¬P ∨ S) ⇒ Q \\ 5 & \{A ⇒ (B ∧ C), ¬C ∨ D ∨ R, R ⇒ ¬B\} & (A ∧ D) ⇒ ¬R \end{matrix}

Exercice 2.22. Dans chacun des cas suivants, que peut-on dire d’une formule propositionnelle : 1. qui a pour conséquence logique une antilogie,

2. qui a pour conséquence logique une tautologie,

3. qui est conséquence logique d’une antilogie,

4. qui est conséquence logique d’une tautologie.

Exercice 2.23. La formule propositionnelle F étant fixée, que peut-on dire d’une formule propositionnelle G qui possède chacune des deux propriétés :

– F ∨ G est une tautologie,

– F ∧ G est une antilogie.

III.4 Formules équivalentes

Définition 2.6 (Formules équivalentes). Si la formule propositionnelle G est conséquence logique de la formule propositionnelle F et si F est aussi conséquence logique de G, alors ces deux formules sont dites équivalentes (que l’on note ≈), soit :

{F } ⊧ G et {G} ⊧ F si et seulement si F ≈ G.

C’est cette notion de formules équivalentes qui autorise le remplacement d’une expression par une autre (équivalente, bien sûr) dans une formule propositionnelle.

Remarque 2.6. On est autorisé à remplacer ¬¬A par A, puisque ces formules sont équivalentes.

Exercice 2.24. Dans chacun des cas suivants, dire si les deux formules propositionnelles inscrites sur la même ligne sont équivalentes :

\begin{matrix}1 & ¬(¬P) & P \\ 2 & P ∧ (P ⇒ Q) & P ∧ Q \\ 3 & P ⇒ Q & (¬P) ∨ (P ∧ Q) \\ 4 & P ⇒ Q & (¬P) ⇒ (¬Q) \\ 5 & P ∨ Q & ¬((¬P) ∧ (¬Q)) \\ 6 & P ∧ Q & ¬((¬P) ∨ (¬Q)) \\ 7 & ¬P & (¬(P ∨ Q)) ∨ ((¬P) ∧ Q) \\ 8 & P ⇒ (Q ⇒ R) & (P ⇒ Q) ⇒ R \\ 9 & P ⇒ (Q ∧ R) & (P ⇒ Q) ∧ (P ⇒ R) \\ 10 & P ⇒ (Q ∨ R) & (P ⇒ Q) ∨ (P ⇒ R) \\ 11 & (P ⇒ Q) ∧ (Q ⇒ P) & (P ∧ Q) ⇒ (P ∧ Q) \\ 12 & (P ∧ Q) ∨ (Q ∧ R) ∨ (R ∧ P) & (P ∨ Q) ∧ (Q ∨ R) ∧ (P ∨ R) \end{matrix}

Exercice (corrigé) 2.25. Soit F une formule propositionnelle dépendant de trois variables P, Q, R qui possède deux propriétés :

– F (P, Q, R) est vraie si P, Q, R sont toutes les trois vraies,

– la valeur de vérité de F (P, Q, R) change quand celle d’une seule des trois variables change. Construire la table de vérité de F, et déterminer une formule possible pour F.

Réponse : table de vérité

\begin{matrix}P & Q & R & F \\ V & V & V & V \\ V & V & F & F \\ V & F & V & F \\ F & V & V & F \\ V & F & F & V \\ F & F & V & V \\ F & V & F & V \\ F & F & F & F \end{matrix}

Formule : (P ∧ Q ∧ R) ∨ (P ∧ ¬Q ∧ ¬R) ∨ (¬P ∧ ¬Q ∧ R) ∨ (¬P ∧ Q ∧ ¬R)

Exercice 2.26. Déterminer des formules propositionnelles F, G, H dépendant des variables P, Q, R qui admettent les tables de vérité :

\begin{matrix}P & Q & R & F \\ V & V & V & V \\ V & V & F & F \\ V & F & V & V \\ V & F & F & F \\ F & V & V & F \\ F & V & F & V \\ F & F & V & V \\ F & F & F & V \end{matrix} \begin{matrix}P & Q & R & G \\ V & V & V & F \\ V & V & F & V \\ V & F & V & V \\ V & F & F & F \\ F & V & V & F \\ F & V & F & V \\ F & F & V & V \\ F & F & F & F \end{matrix} \begin{matrix}P & Q & R & H \\ V & V & V & V \\ V & V & F & V \\ V & F & V & V \\ V & F & F & F \\ F & V & V & F \\ F & V & F & V \\ F & F & V & V \\ F & F & F & V \end{matrix}

III.5 Simplification du calcul des fonctions de vérité

III.5.1 Théorème de substitution

Propriété 2.4 (Théorème de substitution) : Soit F une formule propositionnelle dans laquelle interviennent les variables propositionnelles P_{1} , P_{2} , P_{3} ,…, P_{n}. Supposons que l’on remplace ces variables par des formules propositionnelles G_{1} , G_{2} , G_{3} ,…, G_{n} ; la nouvelle formule propositionnelle obtenue est notée F^{∗}.

Dans ces conditions : si ⊧ F, alors ⊧ F^{∗}.

Preuve F étant une tautologie, sa fonction de vérité ne dépend pas des valeurs de vérité des variables booléennes, qui peuvent donc être remplacées par n’importe quelle fonction booléenne.

Attention, la réciproque n’est pas vraie…

Exemple 2.27. Soit F = A ⇒ B et F^{∗} = P ∧ ¬P ⇒ Q, obtenue à partir de F en remplaçant A par P ∧ ¬P et B par Q. Comme Φ_{F^{∗}}(p, q) = \overline{p · \overline{p}}+ q = \overline{0} + q = 1 + q = 1, alors F^{∗} est une tautologie. Cependant de Φ_{F}(a, b), on ne peut pas dire que F est une tautologie.

Exemple d’utilisation de ce résultat :

Exemple 2.28. La formule propositionnelle

F^{∗} = ((P ⇒ Q ∧ ¬R) ∨ (¬S ⟺ T)) ⇒ ((P ⇒ Q ∧ ¬R) ∨ (¬S ⟺ T)),

est compliquée puisqu’elle contient 5 variables propositionnelle. il y a donc 32 lignes à calculer pour obtenir les valeurs de la fonction de vérité. Cependant, il suffit de remarquer que F^{∗} est obtenue à partir de F = A ⇒ A, qui est une tautologie ; donc F^{∗} en est une aussi.

Ce résultat peut évidemment être appliqué aussi à des parties de formules propositionnelles, pour accélérer le calcul de leurs fonctions de vérité : si une partie d’une formule propositionnelle constitue à elle seule une tautologie, la partie correspondante de la fonction de vérité peut être avantageusement remplacée par 1.

III.5.2 Théorème de la validité

Propriété 2.5 (Théorème de la validité) : Soit {G_{1}, G_{2}, …, G_{n}} un ensemble de formules propositionnelles et H une formule propositionnelle ; alors :

{G_{1}, G_{2}, …, G_{n−1} } ⊧ G_{n} ⇒ H si et seulement si {G_{1}, G_{2}, …, G_{n}} ⊧ H

Preuve Si. Supposons {G_{1}, G_{2}, …, G_{n}} ⊧ H, c’est à dire, chaque fois que les formules de {G_{1}, G_{2}, …, G_{n}} sont vraies, H l’est aussi). Supposons que les formules de {G_{1}, G_{2}, …, G_{n−1} } soient vraies :

– Alors, si G_{n} est vraie, toutes les formules de {G_{1}, G_{2}, …, G_{n}} sont vraies, et donc, d’après l’hypothèse, H est vraie. Dans ce cas (voir table de vérité de l’implication logique), G_{n} ⇒ H est vraie.

– Et si G_{n} n’est pas vraie, alors G_{n} ⇒ H est vraie. Seulement si. Supposons {G_{1}, G_{2}, …, G_{n−1} } ⊧ G_{n} ⇒ H. En d’autres termes, chaque fois que les formules de {G_{1}, G_{2}, …, G_{n−1} } sont vraies, G_{n} ⇒ H est vraie. Regardons si H est une conséquence logique de {G_{1}, G_{2}, …, G_{n}} en distinguant selon que G_{n} est vraie ou pas.

– soit lorsque G_{n} n’est pas vraie, indépendamment de la valeur de vérité de H sur laquelle on ne peut alors rien dire, mais peu importe, puisque, dans ce cas, les formules de {G_{1}, G_{2}, …, G_{n}} ne sont pas toutes vraies, puisque G_{n} n’est pas vraie.

– soit lorsque G_{n} est vraie, et, dans ce cas, on sait que H est obligatoirement vraie aussi. Ceci se produit chaque fois que toutes les formules de {G_{1}, G_{2}, …, G_{n}} sont vraies, et, dans ce cas, H l’est aussi. Donc {G_{1}, G_{2}, …, G_{n}} ⊧ H.

Exemple 2.29 (Exemple d’application). Soit à montrer que :

⊧ (A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C)).

On pourrait bien entendu déterminer la fonction de vérité de cette formule. Mais, d’après le théorème précédent, la démonstration du résultat demandé est équivalente à celle de :

{A ⇒ (B ⇒ C)} ⊧ (A ⇒ B) ⇒ (A ⇒ C).

Une nouvelle application de ce même théorème nous montre que la démonstration demandée est encore équivalente à celle de :

{A ⇒ (B ⇒ C), (A ⇒ B)} ⊧ (A ⇒ C).

Et enfin à celle de :

{A ⇒ (B ⇒ C), (A ⇒ B), A} ⊧ C.

Or les fonctions de vérité de {A ⇒ (B ⇒ C), (A ⇒ B), A} sont

\{ \begin{matrix}\overline{a} + \overline{b}+ c \\ \overline{a} + b \\ a \end{matrix} qui valent sim. 1 quand \{ \begin{matrix}a = 1 \\ b = 1 \\ c = 1 \end{matrix}

Ainsi C est vraie et on a terminé la démonstration.

Exercice 2.30. Trois dirigeants d’une Société (Pierre P., Marc M. et Alain A.) sont prévenus de malversations financières ; au cours de l’enquête, l’agent du fisc enregistre leurs déclarations :

– Pierre P. : “Marc est coupable et Alain est innocent”.

– Marc M. : “Si Pierre est coupable, Alain l’est aussi”.

– Alain A. : “Je suis innocent, mais l’un au moins des deux autres est coupable”.

1. Ces trois témoignages sont-ils compatibles ?

2. En supposant qu’ils sont tous les trois innocents, lequel a menti ?

3. En supposant que chacun dit la vérité, qui est innocent et qui est coupable ?

4. En supposant que les innocents disent la vérité et que les coupables mentent, qui est innocent et qui est coupable ?

Exercice 2.31. Simplifier le règlement suivant :

– Les membres de la Direction Financière doivent être choisis parmi ceux de la Direction Générale.

– Nul ne peut être à la fois membre de la Direction Générale et de la Direction Technique s’il n’est membre de la Direction Financière.

– Aucun membre de la Direction Technique ne peut être membre de la Direction Financière.

Exercice 2.32. Un inspecteur des services de santé visite un hôpital psychiatrique où des phénomènes étranges lui ont été signalés.

Dans cet hôpital, il n’y a que des malades et des médecins, mais les uns comme les autres peuvent être sains d’esprit ou totalement fous. L’inspecteur doit faire sortir de l’hôpital les personnes qui n’ont rien à y faire, c’est à dire les malades sains d’esprit et les médecins totalement fous (quitte à les réintégrer ultérieurement en tant que malades…). Il part du principe que les personnes saines d’esprit ne disent que des choses vraies, alors que les personnes folles ne disent que des choses fausses.

Dans une salle, il rencontre deux personnes (appelons-les A et B pour préserver leur anonymat). A affirme que B est fou et B affirme que A est médecin.

1. Après une intense réflexion, l’inspecteur fait sortir l’un des deux de l’hôpital. Lequel (et pourquoi ?)

2. Peut-il dire quelque chose au sujet de l’autre ?

Exercice 2.33. Le prince de Beaudiscours est dans un cruel embarras. Le voici au pied du manoir où la méchante fée Antinomie maintient prisonnière la douce princesse Vérité. Deux portes y donnent accès. L’une d’elles conduit aux appartements de la princesse, mais l’autre s’ouvre sur l’antre d’un dragon furieux. Le prince sait seulement que l’une de ces deux portes s’ouvre lorsqu’on énonce une proposition vraie, et l’autre si on énonce une proposition fausse.

Comment peut-il délivrer la princesse ?

Exercice 2.34. Que dire des raisonnements suivants ?

1. Si Jean n’a pas rencontré Pierre l’autre nuit, c’est que Pierre est le meurtrier ou que Jean est un menteur. Si Pierre n’est pas le meurtrier, alors Jean n’a pas rencontré Pierre l’autre nuit et le crime a eu lieu après minuit. Si le crime a eu lieu après minuit, alors Pierre est le meurtrier ou Jean n’est pas un menteur. Donc Pierre est le meurtrier 2. Manger de la vache folle est dangereux pour la santé ; manger du poulet aux hormones aussi,

d’ailleurs. Quand on ne mange pas de la vache folle, on mange du poulet aux hormones. Notre santé est donc en danger.

3. Si je n’étudie pas, j’ai des remords. Mais si je ne vis pas à fond ma jeunesse, j’ai aussi des remords. Or je n’ai pas de remords. C’est donc que j’étudie tout en vivant à fond ma jeunesse.

4. Quand Marie est là, c’est qu’elle accompagne Paul ou Jean. Paul ne vient jamais en même temps que son cousin Serge. Si Jean et Serge viennent tous les deux, leur sœur Louise les accompagne. Si Louise se pointe, Raoul ne reste pas. Hier, Raoul et Serge étaient présents jusqu’au bout. Peut-on en conclure que Marie n’était pas présente ?

III.6 Conclusion

Le calcul sur les fonctions de vérité paraît tout-à-fait satisfaisant et séduisant, lorsqu’il s’agit de calculer des valeurs de vérité ou d’examiner des conséquences logiques. Il est vrai qu’il est simple, nécessite un minimum de réflexion (très important dans le cas des ordinateurs !) et qu’il est très facile à programmer.

Mais, pour une formule propositionnelle qui comporte 10 variables propositionnelles (ce qui n’est pas beaucoup pour les problèmes que l’on cherche à programmer !), la table des valeurs de la fonction de vérité comporte 2^{10} = 1024 lignes. Celui qui opère à la main a déjà démissionné. L’ordinateur démissionne un peu plus loin, certes, mais il finit aussi par avouer son incapacité :

– Sur les machines modernes, il n’est plus impossible d’envisager d’écrire et d’exécuter une « boucle vide » qui porte sur toutes les valeurs entières représentables sur 32 bits, donc de 0 à 2^{32} − 1, le temps d’exécution est récemment devenu raisonnable.

– Il ne faut cependant pas exiger que ce temps demeure raisonnable dès qu’il s’agit d’exécuter un algorithme un peu compliqué. Et 32 variables constituent un nombre ridiculement petit pour un système expert, dans lequel les expressions offrent souvent une complexité qui n’a aucune commune mesure avec ce que l’on peut imaginer de plus compliqué…

Les « raccourcis » qui viennent d’être étudiés et qui permettent d’accélérer, voire de supprimer totalement, le calcul d’une fonction de vérité, sont plus utiles lorsque l’on opère « à la main » que pour la programmation d’algorithmes de logique.

Il faut donc garder en réserve la méthode des fonctions de vérité : celle-ci peut être très utile dans certains cas, essentiellement lorsque le problème peut être résolu « à la main », mais il faut aussi trouver une autre méthode pour songer à aborder des problèmes plus complexes.

Cette méthode, qui supprime toute référence aux valeurs de vérité, fait l’objet du chapitre suivant.

Fin du Chapitre

Deuxième partie

Annexes Programme Pédagogique National 2005 (PPN)

Voici le contenu de l’Unité de Formation Mathématiques Discrètes (TC-CCG-MATH1) du PPN actuel :

Volume horaire : 70 h Pré-requis : aucun. Objectifs : – Connaître le calcul booléen.

– Calculer dans Z/nZ.

– Connaître les notions de base en théorie des graphes, des langages et des automates. Compétences minimales : – Mettre en œuvre des schémas de raisonnement (contraposée, absurde,

récurrence, etc.).

– Mettre en œuvre des algorithmes d’arithmétique (Euclide, Bézout, etc.).

– Faire le lien entre langage usuel et langage formalisé (propositions et prédicats). Contenu : – Vocabulaire de la théorie des ensembles, relations, ensembles ordonnés.

– Logique : calcul propositionnel et calcul des prédicats.

– Arithmétique : nombres premiers, division euclidienne, congruences.

– Éléments de théorie des graphes : graphes orientés et non orientés.

– Éléments de langages et d’automates. Indications de mise en œuvre : Exemples d’algorithmes de plus courts chemins, de parcours et d’arbre

couvrant de poids minimum. Prolongements possibles : – Exemples de raisonnement par récurrence (en liaison avec les enseigne-

ments d’algorithmique).

– Développement des liens avec les enseignements d’informatique, en particulier « Architectures, Systèmes et Réseaux » et « Outils et Modèles du Génie logiciel » (algèbre relationnelle, etc.).

– Chaînage avant et chaînage arrière.

– Résolution d’équations en nombres entiers.

– Cryptographie (RSA, méthode du « sac à dos », etc.).

– Codes correcteurs et codes détecteurs d’erreurs.

Bibliographie

[Dow07] Gilles Dowek. Les Métamorphoses du calcul, une étonnante histoire des mathématiques. Éditions le Pommier, 2007.

Bibliographie (suite)

Outils mathématiques pour l’informaticien, Michel Marchand [De Boeck ] : les thèmes abordés sont proches de ce cours de mathématiques discrètes (notre première année y est plus détaillée que la partie concernant automates, graphes et langages). On y trouve des exercices, corrigés, parfois repris dans ce support. Cependant, le formalisme choisi s’éloigne par moment de celui adopté dans notre document, ce qui pourrait en destabiliser certains.

Méthodes mathématiques pour l’informatique, Jacques Vélu [Dunod ] : Reprend une grande partie du cours de mathématiques discrètes, et y ajoute un peu de probabilités et d’algèbres linéaires. Contient des exercices corrigés. Un peu dense par moment, mais une bonne référence quand même.

Le magazine Tangente : que l’on trouve chaque mois chez les bons marchants de journaux. Niveau lycée et plus. On y trouve fréquemment des articles sur les graphes, la logique, le cryptage, etc. Ludique et plaisant, pour ceux qui aiment les mathématiques, veulent les découvrir. Les hors-séries sur la logique, sur les codes secrets, etc. me servent à trouver des idées de TP, ou à enrichir le cours.

Introduction à la logique, François Rivenc [Petite Bibliothèque Payot ] : Pour un public avertis, souhai-

tant étudier plus systématiquement la logique, sous ses aspects mathématiques et philosophiques. http ://www.apprendre-en-ligne.net/ Site de Didier Müller, sur lequel j’ai repris la partie graphes. A

noter une autre partie (très riche, bien fournie) consacrée à la cryptographie, et un blog très intéressant sur les mathématiques.