HAI105X– 1 – Logique, raisonnement, ensembles

François Fillastre

Université de Montpellier

2021-2022
 Que ce soit en informatique ou en mathématiques, l’écrit
est par essence le principal vecteur de communication. La
conséquence de ce fait indiscutable est qu’aucune méthode
d’apprentissage, aussi innovante soit-elle, ne pourra rem-
placer une pratique intensive de la lecture et de l’écriture
pour progresser dans ces deux disciplines.
http://zanotti.univ-tln.fr/MD/MD-Logique.html
Éléments du discours mathématique

Un texte mathématique contient généralement des

Définitions qui précisent la dénomination d’objets mathématiques
dont on va parler, elles disent ce qui est et ce qui
n’est pas dans la catégorie d’objet étudié.
Théorèmes (et lemmes, corollaires...) qui énoncent des résultats
mathématiques.
Démonstrations (ou preuves) qui attestent, justifient, prouvent
que les théorèmes énoncés sont vrais.
Mais aussi des exemples, commentaires, illustrations,
remarques, notes etc.
Definition
On appelle proposition un énoncé (assertion) qui a un sens et est
soit vrai soit faux (c’est la valeur de vérité de la proposition).

Exemple
Les énoncés  2 est un nombre pair ,  2 + 2 = 7 ,  HAI105X
est un cours de première année de Licence ,  Le mouton est un
animal carnivore  sont des propositions. 2+ = ×37− ,
2
 3x − 1 ,  Le premier ministre ,  être un nombre

premier  ne sont pas des propositions.

Soit A une proposition, la négation de A se note non(A).
La proposition non(A) est vraie quand A est fausse, et elle est
fausse quand A est vraie.
Table de vérité
A non(A)
F V
V F

Exercice
Valeur de vérité de non(2 + 2 = 4) ? Valeur de vérité de
non(2 + 2 = 2 × 2) ?Valeur de vérité de non(non(2 est pair)) ?

Remarque
A et non(non(A)) ont la même table de vérité.
Soit A et B deux propositions, la conjonction de A et de B se note
A et B.
La proposition  A et B  est vraie quand A et B sont vraies, et
fausse sinon.
Table de vérité
A B A et B
F F F
F V F
V F F
V V V

Exercice
Valeur de vérité de :  (2 + 2 = 4) et (1 + 1 = 1)  ?
Valeur de vérité de :  (2 est pair) et (3 est impair)  ?
Soit A et B deux propositions, la disjonction de A et de B se note
A ou B.
La proposition  A ou B  est vraie quand au moins l’une des
propositions A ou B est vraie, et fausse sinon.
Table de vérité
A B A ou B
F F F
F V V
V F V
V V V

Exercice
Valeur de vérité de :  (2 + 2 = 4) ou (1 + 1 = 2)  ?
Valeur de vérité de :  (2 est impair) ou (3 est impair)  ?
On construit ainsi de nouvelles propositions, auxquelles on peut de
nouveau appliquer des opérateurs logiques.
Exemple
Si A, B, C et D sont des propositions, on peut former les
propositions suivantes :
I non(A et B)
I (A et B) ou (non(C ) ou D)
I (B et C ) ou (non(B) et D)
I (non(A) et B) ou non(B)
Definition
Soit A et B deux propositions, l’implication de A vers B se note
A =⇒ B ( A implique B ).
La proposition A =⇒ B est fausse uniquement quand A est vraie
et B est fausse.

Table de vérité
A B A =⇒ B
F F V
F V V
V F F
V V V
L’implication A =⇒ B est vraie seulement quand A est fausse ou
quand A et B sont vraies toutes les deux.
AEn d’autres termes, si A est fausse, A =⇒ B est vraie, mais ça
ne dit pas si B est vraie ou fausse !
Exercice
Valeur de vérité de (1 + 1 = 2) =⇒ (2 + 2 = 4) ?
Valeur de vérité de (2 est impair) =⇒ (3 est pair) ?
Valeur de vérité de (2 est pair) =⇒ (4 est impair) ?
Valeur de vérité de (1 + 1 = 3) =⇒ (2 est pair) ?

A =⇒ B peut aussi se lire  Si A est vraie, alors B est vraie .

Si A =⇒ B est vraie, alors A est une condition suffisante pour
que B soit vraie, et B est une condition nécessaire pour que A soit
vraie.
Théorème (1-1)
Soit A et B deux propositions. Les proposition A =⇒ B et
 non(A) ou B  ont la même table de vérité.
A B A =⇒ B non(A) non(A) ou B
V V V F V
Démonstration V F F F F 
F V V V V
F F V V V
Exemple
 Si le Père Noël existe, alors je recevrai une Switch en cadeau. 

On peut réécrire cette expression à l’aide de l’opérateur d’implication :

Le Père Noël existe =⇒ Je recevrai une Switch en cadeau.
On sait que ceci équivaut à l’expression suivante :
non( Le Père Noël existe. ) ou  Je recevrai une Switch en cadeau. 
On constate que cette expression est fausse si et seulement si le Père
Noël existe et que je ne reçois pas de Switch en cadeau. Aussi, le fait que
le Père Noël n’existe pas n’exclut pas la possibilité que je reçoive une
Switch en cadeau !
Tiré de
Mathématiques pour informaticien MAT-1919 François Laviolette, Josée Desharnais, Pascal Germain
AAttention aux parenthèses ! ! !
(A =⇒ B) =⇒ C , A =⇒ (B =⇒ C )

(A ou B) =⇒ C , A ou (B =⇒ C ) , (A ou B) =⇒ C
Théorème (1-2)
Soit A et B deux propositions. A =⇒ B et non(B) =⇒ non(A)
ont la même table de vérité.
non(B) =⇒ non(A) est la contraposée de A =⇒ B.
Exercice
(Maison) Prouver ce théorème en faisant les tables de vérité de
A =⇒ B et non(B) =⇒ non(A)

Remarque
I Il équivalent d’affirmer une implication ou sa contraposée.
I Ne pas confondre la contraposée de A =⇒ B avec sa
réciproque B =⇒ A ! Il n’y a aucun lien entre les deux.
Definition
Soit A et B deux propositions, l’équivalence de A et B se note
A ⇐⇒ B ( A équivalent à B ). La proposition A ⇐⇒ B est
vraie seulement quand les propositions A ou B ont même valeur de
vérité.

Table de vérité
A B A ⇐⇒ B
F F V
F V F
V F F
V V V

Exercice
Valeur de vérité de (2 + 2 = 4) ⇐⇒ (1 + 1 = 1) ?
Valeur de vérité de (2 est impair) ⇐⇒ (3 est pair) ?
Théorème (1-3)
Les propositions  A ⇐⇒ B  et
 (A =⇒ B) et (B =⇒ A)  ont la même table de vérité.

Exercice (Maison)
Construire la table de vérité de (A =⇒ B) et (B =⇒ A) et en
déduire ce théorème.
Les opérations“et” et “ou” sont commutatives et associatives, et
elles sont distributives l’une par rapport à l’autre.
Pour A, B et C des propositions :
I (A ou B) ⇐⇒ (B ou A)
I (A et B) ⇐⇒ (B et A)
I ((A ou B) ou C ) ⇐⇒ (A ou (B ou C ))
I ((A et B) et C ) ⇐⇒ (A et (B et C ))
I (A et (B ou C )) ⇐⇒ ((A et B) ou (A et C ))
I (A ou (B et C )) ⇐⇒ ((A ou B) et (A ou C ))
Théorème (1-4 Lois de De Morgan )
Soit A et B deux propositions.
non(A ou B) ⇐⇒ (non(A) et non(B))
non(A et B) ⇐⇒ (non(A) ou non(B))

Exercice
(Maison) Prouver les lois de Morgan en faisant les tables de vérité.
Théorème (1-5)
Soit A et B deux propositions.

(non(A =⇒ B)) ⇐⇒ (A et non(B))

Démonstration D’après les théorèmes précédents, non(A =⇒ B) a

la même table de vérité que non(non(A) ou B), donc que
(non(non(A)) et non(B)), et enfin que (A et non(B)). 

ALa négation d’une implication n’est pas une implication !

Exemple
Soit A= il pleut  et B= je prends mon parapluie . Supposons
que A =⇒ B est vraie : si il pleut je prends mon parapluie. Il
suffit qu’il pleuve pour que je prenne mon parapluie. Pour qu’il
pleuve, il est nécessaire que j’ai mon parapluie (dans le sens ou si
je ne l’ai pas, ça signifie qu’il ne pleut pas).
La contraposée de A =⇒ B est :  si je ne prends pas mon
parapluie alors il ne pleut pas . Ce n’est pas la même chose que
B =⇒ A :  Si je prends mon parapluie alors il pleut .
La négation de A =⇒ B est :  il pleut et je ne prends pas mon
parapluie .
Variables dans les énoncés

Un énoncé peut dépendre d’une variable, c’est-à-dire un élément

d’un certain ensemble, par exemple  x 2 − 1 est un réel positif  :
on affirme quelque chose concernant x, on sait déjà ce que
représente x.
Definition
On appelle prédicat (ou assertion ouverte) une assertion
mathématique qui dépend d’une ou plusieurs variables (et qui a un
sens mathématique).

Exemple
I  n est pair  qui porte sur un entier n.
I  x 6y  qui porte sur deux éléments réels x et y .
Un prédicat peut être vrai ou faux selon les valeurs données aux
variables.
Exemple
I  n est pair  est vrai pour n = 2 et faux pour n = 3
I  x 6y  est faux pour x = 1 et y = −1
Soyons un peu plus précis.
Definition
Un ensemble est une collection d’éléments (des objets
mathématiques). Pour dire qu’un objet x est élément d’un
ensemble E , on dit  x est élément de E , ou  x est dans
E  ou  x appartient à E  et on note x ∈ E .
Si x n’est pas un élément de E (i.e. non(x ∈ E )), on note x ∈
/E

Souvent, on note les ensembles en majuscule, et les éléments en

minuscule.
Un ensemble est lui-même un élément d’un autre ensemble, on
verra ça plus tard !
Exemple
I On note N l’ensemble des entiers naturels, c’est-à-dire les
nombres entiers positifs : 0, 1, 2, . . .
I On note par R l’ensemble des réels, qui est essentiellement
l’ensemble
√ de tous les nombres que vous pouvez imaginer
(2, 2, π, . . .).
I Il y a un ensemble qui ne contient aucun élément : l’ensemble
vide, noté ∅.

ANe jamais confondre ∅ et 0.

On peut aussi vouloir affirmer une assertion pour tous les éléments
d’un ensemble ou dire qu’il existe un élément vérifiant l’assertion.
Definition
Soit P(x) une assertion ouverte dépendant d’une variable x d’un
ensemble E .
 ∀x ∈ E , P(x)  est l’assertion qui affirme que tous les éléments

de E vérifient P.
 ∃x ∈ E , P(x)  est l’assertion qui affirme qu’il existe un

élément de E vérifie P.

∀ et ∃ sont des quantificateurs.

∀x ∈ E , P(x) est vraie si et seulement si tous les éléments x de E
rendent vrai P(x).
∃x ∈ E , P(x) est vraie si et seulement si au moins un élément x de
E rend vrai P(x).
Exemple
I ∀n ∈ N, n est pair.
I ∃n ∈ N, n est pair.
I ∀y ∈ R, y 2 > 0.
I ∃y ∈ R, y 2 > 0.
I ∃z ∈ R, z 2 = 2.
∀x ∈ E , P(x) et ∃x ∈ E , P(x) ne dépendent plus de la valeur de
x, ils sont soit vrai soit faux :
Dans les assertions ∀x ∈ E , P(x) et ∃x ∈ E , P(x), la variable x est
dite muette.
Il n’y a pas d’objet qui s’appelle x.
Il est strictement identique d’affirmer ∀x ∈ E , P(x) et
∀z ∈ E , P(z), ou encore ∃x ∈ E , P(x) et ∃ϕ ∈ E , P(ϕ).
Autrement dit, ∀x ∈ R, x 2 > 0 est la même chose que
∀y ∈ R, y 2 > 0 et que  Le carré de tout réel est positif .
Exercice
Quelle est la négation de  Tous les étudiants écoutent le cours  ?

Solution Il existe un étudiant qui n’écoute pas le cours.

Exercice
Quelle est la négation de  Il y a un étudiant qui a compris le
cours  ?
Solution Aucun étudiant n’a compris le cours.

non(∀x ∈ E , P(x)) ⇐⇒ (∃x ∈ E , non(P(x)))

non(∃x ∈ E , P(x)) ⇐⇒ (∀x ∈ E , non(P(x)))

 non(∀x ∈ E , P(x)) ⇐⇒ (∃x ∈ E , non(P(x)))

non(∃x ∈ E , P(x)) ⇐⇒ (∀x ∈ E , non(P(x)))

ALes seuls symboles barrés qu’on utilise sont ∈/ et 6=) (le symbole
6⊂ existe, mais on ne devrait pas en avoir besoin).
Pour prouver une assertion de la forme  ∃x ∈ E , P(x) , on peut
trouver un élément de E qui vérifie la propriété P.
Pour prouver une assertion de la forme ∀x ∈ E , P(x), il faut
montrer que tous les éléments de E vérifient la propriété P.
Il faut comprendre que c’est la même chose que de montrer P(x)
pour un élément x ∈ E quelconque. En effet, c’est la même chose
de dire
 Pour tout x ∈ E , P(x) est vraie 

que de dire
 Soit x ∈ E . Alors P(x) est vraie 
On doit parfois démontrer l’existence d’un unique élément x
vérifiant une certaine propriété P.
On note  ∃!x ∈ E , P(x) pour dire  il existe un unique x ∈ E
tel que P(x) est vraie .
Pour montrer une telle proposition, il faut montrer :
1. ∃x ∈ E , P(x)
2. ET ∀x ∈ E , ∀y ∈ E , (P(x) et P(y )) =⇒ x = y
Raisonnement par l’absurde

On veut prouver une assertion A.

On prouve que si A est faux, alors on aboutit à une contradiction.
On en conclut que A est nécessairement vraie.
Autrement dit : Si non(A) implique une contradiction, c’est-à-dire
une proposition fausse B, alors A est vraie.
En fait, on montre que non(A) =⇒ B, c’est-à-dire que A ne peut
pas être fausse.
Pour se convaincre
non(A) B non(A) =⇒ B
F F V
F V V
V F F
V V V
Exemple
A = ∀x ∈ N, x + 1 6= x + 2  . Montrons par l’absurde que A
est faux.
Supposons donc qu’il existe x ∈ N tel que x + 1 = x + 2
Alors, 1 = 2 (en soustrayant x dans chaque membre).
Cela est impossible. Donc A est vraie.