Chapitre 1 : Introduction à la

logique, aux ensembles, et aux

techniques de démonstration

Algèbre 1

Agnès Gadbled - Université d’Avignon

Année 2023–24

1/68
Plan

1. Langage mathématique, éléments de logique

2. ”Calcul” et propriétés des assertions

3. Raisonnement mathématique

4. Notions d’ensemble et d’application

2/68
Plan

1. Langage mathématique, éléments de logique

1.1. Introduction
1.2. Vocabulaire

D on va admettre des notions de logique.

3/68
1.1. Introduction

Théorème des quatre couleurs

1852 : Guthrie remarque qu’il lui suffit de quatre couleurs pour

colorer la carte des cantons d’Angleterre, sans donner la même
couleur à deux cantons adjacents (ayant une frontière commune).

McIntyre (engraver), Vigurs (printer), John Wallis 1734-1793 (author), Public domain, via Wikimedia Commons
4/68
 1852:Guthrie
> De
Morgan
la preuve
1878: Cayley: public
i
I

i
à 1478
etHaken
réduit le problème
Appel
u

1976:
ordinateur.
critiques"
37
-
cas par
Werner: "Formalise"la preuve
2005:Gonthier &
vérifier la preuve par ordinateur

5/68
1.2. Vocabulaire

Trois processus fondamentaux :

I construire des objets mathématiques,
Exemples d’objets mathématiques fonction, variable,
équation, une suite, une
inéquatern, une
intégrale,
Sun tenseur)Veel
I faire des assertions concernant ces objets,

fr son intervalle
Exemples d’assertions P: 243
R:la fonction
définition
de
fest
telle
que
S:Porte suite majorée.
est

I démontrer que certaines de ces assertions sont vraies, ou au

contraire, fausses. P: vraie &: fausse

Exemple R: dépend def!

S:faux pour les suites réelles.

6/68
 Quelques assertions:
I Axiome : assertion dont on décide qu’elle est vraie a priori.
↑axiome d'Euclide: par 2 points distincts du plan passe une unique
droite
I Théorème : assertion vraie qu’on démontre à partir
d’axiomes (ou d’autres théorèmes déjà démontrés).
Théorème de
Pythagore
12
de Thales
I Tautologie : une assertion qui est toujours vraie par les
règles du calcul sur les assertions. ↳- voir plus loin un exemple)

Assertions équivalentes : deux assertions P

et Q sont dites équivalentes lorsqu’elles ont la même valeur de vérité.
p: "Pour fort uAR, 2x +1 3x
=
+1"
est equivalente à
①: "Pour tout
me, 2x=3x"
elaassi equivalente à R: "Pour touta ER, m 0"fausse! =

7/68
On peut encoder les assertions grâce à des tables de vérités qui
P
consignent les valeurs de vérité d’une assertion: V
F

On peut définir des opérations sur les assertions et les comparer

(assertions équivalentes).
Exemple : Soit les assertions :
P : ”je suis motivé(e) par le cours d’analyse et le cours d’algèbre”,
Q : ”je suis motivé(e) par le cours d’analyse”,
R : ”je ne suis pas motivé(e) par le cours d’algèbre”.
L’assertion P est-elle équivalente à une assertion construite à partir
de Q et R?
de
Pest equivalente à pe la
magion

8/68
Plan

2. ”Calcul” et propriétés des assertions

2.1. Négation
2.2. Connecteurs binaires
2.3. Quelques propriétés
2.4. Quantificateurs

9/68
2.1. Négation
Négation
Si P est une assertion, l’assemblage non P (notée aussi ¬P)
appelé négation de P est aussi une assertion qui prend la valeur
de vérité “vrai” lorsque P est fausse, et la valeur de vérité “faux”
lorsque P est vraie.
Table de vérité de la négation
P non P
V F
F V

Exemple : p:
" estun entier naturel"
"* SIN"
nonp:"
n'est pas
un entier
naturel"**4IN"
est
Pestfausse donc houp vraie.

10/68
2.2. Connecteurs binaires

Conjonction
Si P et Q sont deux assertions, la conjonction

P et Q (notée aussi P ^ Q)

est encore une assertion. Pour que l’assertion (P et Q) soit vraie,

il faut et il suffit que les deux assertions P, Q le soient.

Exemple : Pour x un nombre réel, soit R = “x est strictement

positif et x 2 x 2 est strictement négatif“.
R est de la forme (P et Q) où
P = se eststrictementpositif ,
et Q = e-x 2 est strictement
-

. négatif
trouver les zeros.
Le discriminantde e-x-2 my

1 et2
(x
zeros
&W -2 - x - 1)(x 2):
2 =
+
-
- comme

9 u2,x - 220 xt] 1,2) et donc R=

= - e e]0,2 [.
11/68
Table de vérité de la conjonction. Si P et Q sont deux
assertions, la conjonction

P et Q (notée aussi P ^ Q)

est encore une assertion. Pour que l’assertion (P et Q) soit vraie,

il faut et il suffit que les deux assertions P, Q le soient.

P Q P et Q
V V V
V F I
F V F
F F F

12/68
Disjonction
Si P et Q sont deux assertions, la disjonction

P ou Q (notée aussi P _ Q)

est encore une assertion. Pour que l’assertion (P ou Q) soit vraie,

il suffit que l’une au moins des deux assertions P, Q le soit.

Exemple : Pour n et p des entiersser

relatifs, soittion
-
la proposition
R = “np est pair ou n 2 2
p est multiple de 8”.
R est de la forme (P ou Q) où P = mp est pair ,
et Q = m<- p2 estmultiple de 8 .
Pour n = 5 et p = 3, P est fausse et Q est vraie , donc R est vraie .
Pour n = 5 et p = 2, P est vraie et Q est fausse , donc R est vraie .
Pour n = 6 et p = 2, P est vraie et Q est vraie , donc R est vraie .
↳ vraien
general?
13/68
Table de vérité de la disjonction. Si P et Q sont deux
assertions, la conjonction

P ou Q (notée aussi P _ Q)

est encore une assertion. Pour que l’assertion (P ou Q) soit vraie,

il suffit que l’une au moins des deux assertions P, Q le soit.

P Q P ou Q
V V V
V F V
F V V

F F F

14/68
Implication
Si P et Q sont deux assertions, l’implication

Q non
P ) Q =) ou

est encore une assertion qu’on lit ”P implique Q” (ou bien ”si P,
alors Q”). L’assertion P ) Q est vraie si et seulement si P est
fausse ou Q est vraie.
Elle est donc équivalente à l’assertion (Q ou non P).

Exemples :
I si n est un entier positif, alors n3 n est multiple de 3.
I n est un entier positif implique que n3 n est multiple de 3.
I x 2] 1, 4[ ) x 2 + 3x 4 > 0.

15/68
Table de vérité de l’implication.
Si P et Q sont deux assertions, l’implication

P ) Q

est une assertion qui est vraie si et seulement si P est fausse ou Q

est vraie.

P Q P)Q
V V V
V F F
F V V
F F V

16/68
 Vocabulaire
I L’implication Q ) P est appelée réciproque de P ) Q.
I L’implication non Q ) non P est la contraposée de P ) Q.

Exemple : On considère l’assertion ”si n est un entier positif, alors

n3 n est multiple de 3”. Si
- P
L’implication réciproque est :
Si m2 m estmultiple de 3
-
alors mestun entier
positif.
La contraposée est :
n'estpas multiple des alors n'est
Si ns -m un

pas un entier positif.

17/68
Équivalence
Si P et Q sont deux assertions, l’équivalence

P , Q

est encore une assertion qu’on lit : P est équivalente à Q.

L’assertion P , Q est vraie si et seulement si P et Q sont toutes
les deux vraies ou toutes les deux fausses.
Lorsque l’assertion P , Q est vraie, on dit aussi que les assertions
P et Q sont équivalentes.

Exemple : Soit x un nombre réel, on a l’équivalence

((x 1)(x 2) = 0) , ((x 1 = 0) ou (x 2 = 0))

-
P
④
18/68
Table de vérité de l’équivalence. Si P et Q sont deux
assertions, l’équivalence
P , Q
est une assertion qui est vraie si et seulement si si et seulement si
P et Q sont toutes les deux vraies ou toutes les deux fausses.

P Q P,Q
V V V
V F -
F V F

F F V

19/68
2.3. Quelques propriétés

Quelques propriétés

tautologie.
1) L’assertion (P et non P) est toujours fausse.
2) L’assertion (P ou non P) est toujours vraie.
3) Les assertions P, (P et P), (P ou P), non (non P) sont
équivalentes.

P non P Pet nonD Por nunP Det D non (non

V F F V V V

=V F V F F

20/68
Quelques propriétés
4) Les assertions suivantes sont toujours vraies (à retenir!):
(i) (P et Q) , (Q et P); (P ou Q) , (Q ou P)
(commutativité de “ou” et de “et”)
(ii) (P et (Q et R)) , ((P et Q) et R);
(P ou (Q ou R)) , ((P ou Q) ou R)
(associativité de “ou” et de “et”).
(iii) (P et (Q ou R)) , ((P et Q) ou (P et R));
(P ou (Q et R)) , ((P ou Q) et (P ou R)) (distributivité).
(iv) non(P et Q) , ((non P) ou (non Q));
non(P ou Q) , (non P) et (non Q)
(v) ((P ) Q) et (Q ) R)) ) (P ) R) (transitivité de
l’implication).

E
(vi) (P ) Q) , (non Q ) non P) (loi de contraposition).
(vii) non(P ) Q) , (P et non Q) (négation de l’implication, à
bien retenir!).
(viii) (P , Q) , ((P ) Q) et (Q ) P)) (propriété de condition
nécessaire et suffisante). ->
TD.

21/68
2.4. Quantificateurs
On note P(x) une assertion qui dépend d’un objet x appartenant à
un certain ensemble. (voir section 4). On ne s’intéresse qu’aux
valeurs de x pour lesquelles P(x) a un sens.
Le quantificateur universel 8
L’ assertion
“pour tout x appartenant à l’ensemble A, P(x) est vraie”
est notée
8 x 2 A, P(x).

L’assertion (8 x 2 A, P(x)) est vraie si et seulement si P(x) est

vraie pour tout x 2 A.
Exemple : L’assertion “pour tout nombre x appartenant à
] 1, 2[, on a x 2 x 2 < 0” se formalise mathématiquement en :

Vue] -1,2[, x2 x -

240

22/68
Le quantificateur existentiel 9
L’assertion
“il existe (au moins un) x appartenant à A tel que P(x) soit vraie”
est notée
9 x 2 A, P(x).

Exemple : L’assertion “il existe un nombre réel x tel que

x 2 + 5x + 3 = 0” se traduit mathématiquement par :
JaCIR, 5x 3 0
2
x
+
=
+

relisantle cours.
↳ vai? à voir en

Remarque : L’assertion (9x 2 A, P(x)) est fausse si et seulement

si P(x) est fausse portaEA

23/68
Négation d’une assertion avec quantificateur(s)

:
non(8 x 2 A, P(x))
est équivalent à
9 x 2 A, non(P(x)).

-I
non(9 x 2 A, P(x))
est équivalent à
8 x 2 A, non(P(x)).

24/68
Négation d’une assertion avec quantificateur(s)
non(8 x 2 A, P(x)) est équivalent à 9 x 2 A, non(P(x)).
non(9 x 2 A, P(x)) est équivalent à 8 x 2 A, non(P(x)).

Exemple : La négation des deux exemples précédents est :

non (Vae]-1,25, ex -

240)
20
1,22,x2
x
(Ix]
-
-

non (5x (R,x2 5x 3 0) +

+
=

+52 3
+0
VxCIR, x +

25/68
 Autres propriétés
8 x 2 ;, P(x) est une assertion vraie (il s’agit d’un axiome).
On a les équivalences suivantes :
8x 2 A, (P(x) et Q(x)) , (8x 2 A, P(x)) et (8x 2 A, Q(x))).
9x 2 A, (P(x) ou Q(x)) , (9x 2 A, P(x)) ou (9x 2 A, Q(x))).

Interversion de quantificateurs
I Les assertions suivantes 8x 2 A, 8y 2 B, P(x, y ) et
8y 2 B, 8x 2 A, P(x, y ) sont équivalentes,
VaEI, Vye, axy Vye VrtIR, uyeR
I De même les assertions 9x 2 A, 9y 2 B, P(x, y ) et
9y 2 B, 9x 2 A, P(x, y ) sont équivalentes,
INER Jye, ry CIR
I Les assertions 9x 2 A, 8y 2 B, P(x, y ) et
8y 2 B, 9x 2 A, P(x, y ) ne sont pas équivalentes en
général.
Yuc, JycR, utye yR, VEIR, esye
esttel 2.
SineR, y = - x 0
querety=
=
26/68
Autres propriétés
8 x 2 ;, P(x) est une assertion vraie (il s’agit d’un axiome).
On a les équivalences suivantes :
8x 2 A, (P(x) et Q(x)) , (8x 2 A, P(x)) et (8x 2 A, Q(x))).
9x 2 A, (P(x) ou Q(x)) , (9x 2 A, P(x)) ou (9x 2 A, Q(x))).

Interversion de quantificateurs
I Les assertions suivantes 8x 2 A, 8y 2 B, P(x, y ) et
8y 2 B, 8x 2 A, P(x, y ) sont équivalentes,
I De même les assertions 9x 2 A, 9y 2 B, P(x, y ) et
9y 2 B, 9x 2 A, P(x, y ) sont équivalentes,
I Les assertions 9x 2 A, 8y 2 B, P(x, y ) et
8y 2 B, 9x 2 A, P(x, y ) ne sont pas équivalentes en
général.
ie
untelavecce que y sy,e e
si on a
Pour
26/68
 "Jye IR, VrEIR, xxy" fausse
Rédaction de
est
On l'absurde)- c'estun exemple pour
procède par
le prochain cours
(
réel tel que pour tout
On suppose qu'il existe un
y
neel estun entier relatif
er
eiR, setry
certain réel do:
Ceciestvraipour
un

R.
notye
Or a estu n autre réel pour lequel
e =
+
estdonc e.
la propriete vrain:
entry
+
Or cyty=4++y xoty
=

e, (raxy) alors -

(nity) Ve
=

Mais si
rity (4, Roxy
Ceci estabsurde donc l'assertion estfausse.
p26 bis
30/68
 WIMS
la note est
Pour les exercices de la plateforme WIMs,
calculé
par wims en compte de la note de
tenant

qualite (mais très

légèrement). Vous pourrez toujours
ameliorer la qualitéen répétantles exercices (etdonc
obtenir beaucoup de réponses
vous entrainer) pour

justes?
de la feuille WIMS 1 relatifs au cours du 11/09:
Les exercices

1,2,3 sur la negation, l'implication, contraposée

la
=x
fentintervenir des quantificateurs
=-4, 5, 7,8,9
semaine prochaine)
pas l'ex 6 (CM les ensembles (10 à 14)
sur
exercices
i les
nietes altendre les
Remarque:Si vous pas allaise, vous
pouvez

ID de la semaine prochaine.
30/68
--