1. Introduction la logique mathmatique Encadr par: Mr Laroussi
Gary Anim par: Mr Houssem Eddine Fitati Anne scolaire 2012 2013
CREFOC-Rads
2. Introduction: La logique mathmatique, logique formelle ou
mta- mathmatique est une discipline des mathmatiques introduite la
fin du XIXe sicle, qui s'est donne comme objet l'tude des
mathmatiques en tant que langage. Les objets fondamentaux de la
logique mathmatique sont les formules modlisant les noncs
mathmatiques, les drivations ou dmonstrations formelles modlisant
les raisonnements mathmatiques et les smantiques ou modles qui
dfinissent le sens des formules (et parfois mme des dmonstrations)
comme certains invariants : par exemple l'interprtation des
formules du calcul des prdicats dans les structures permet de leur
affecter une valeur de vrit. ( source wikipdia ) Introduction la
logique mathmatique CREFOC Rads 2012~2013 2
3. a sert quoi ? Introduction la logique mathmatique CREFOC
Rads 2012~2013 3
4. Prambule Un rsultat mathmatique (ou une proposition) est un
nonc vrai. Suivant son importance, il est quali de : lemme :
rsultat dune importance mineure, thorme : rsultat dune importance
majeure. Faire une dmonstration (on dit aussi preuve), cest raliser
un processus qui permet de passer de propositions supposes vraies
prises comme hypothses une proposition appele: conclusion et ce en
utilisant les rgles strictes de logique. Introduction la logique
mathmatique CREFOC Rads 2012~2013 4
5. Plan du cours Introduction la logique mathmatique CREFOC
Rads 2012~2013 5 Assertion et prdicat Proprits Les connecteurs
logiques Les quanticateurs mathmatiques Diffrents modes de
dmonstration
6. Assertion & prdicat Dfinitions et exemples Introduction
la logique mathmatique CREFOC Rads 2012~2013 6
7. Assertion: Dfinition: Une assertion est un nonc mathmatique
auquel on peut attribuer la valeur de vrit: vraie (V) ou faux (F)
mais jamais les deux la fois. Cest le principe du tiers-exclu.
Exemple: Lnonc 24 est un multiple de 2 est vrai (V). Lnonc 19 est
un multiple de 2 est faux (F). Lnonc Tunis est la capitale de la
Tunisie est vrai (V). Introduction la logique mathmatique CREFOC
Rads 2012~2013 7
8. Prdicat: Dfinition: Un prdicat est un nonc mathmatique
contenant des lettres appeles variables tel que quand on remplace
chacune de ces variables par un lment donn dun ensemble, on obtient
une assertion. Exemple: Lnonc suivant : P(n) = n est un multiple de
2 est un prdicat car il devient une assertion quand on donne une
valeur n. P(10) = 10 est un multiple de 2 est une assertion vraie,
P(11) = 11 est un multiple de 2 est une assertion fausse.
Introduction la logique mathmatique CREFOC Rads 2012~2013 8
9. Remarque: Une assertion peut sinterprter comme un prdicat
sans variable, cest--dire comme un prdicat toujours vrai ou
toujours faux. Lnonc suivant : P(x, A) = x A est un prdicat deux
variables. P(1, N) est une assertion vraie, P( 2, Q) est une
assertion fausse. Introduction la logique mathmatique CREFOC Rads
2012~2013 9
10. Les connecteurs logiques Ngation, conjonction , disjonction
, implication & quivalence. Introduction la logique mathmatique
CREFOC Rads 2012~2013 10
11. Ngation: Introduction la logique mathmatique CREFOC Rads
2012~2013 11 Les connecteurs logiques permettent de crer de
nouveaux prdicats (dits prdicats composs) partir de prdicats P, Q,
Soit P un prdicat. La ngation du prdicat P est le prdicat not
non(P) qui: est vrai lorsque P est faux, est faux lorsque P est
vrai. P Non(P) V F F V
12. Exemples: Lassertion P = 24 est un multiple de 2 est une
assertion vraie (V). Lassertion non(P) est dnie par : non(P) = 24
nest pas un multiple de 2 . Cest une assertion fausse (F). A partir
du prdicat x A , on dnie le prdicat non (x A) = x / A . Par
exemple, lassertion 1/2 Z est vraie car lassertion 1/2 Z est
fausse. Introduction la logique mathmatique CREFOC Rads 2012~2013
12
13. Conjonction: Soient P et Q deux prdicats. Le prdicat P et Q
, appel conjonction de P et de Q, est un prdicat qui: est vrai
lorsque P et Q sont vrais simultanment, est faux dans tous les
autres cas. On rsume ceci dans la table de vrit: On crit par fois :
PQ au lieu de P et Q. Introduction la logique mathmatique CREFOC
Rads 2012~2013 13 P Q P et Q V V V F V F V F F F F F
14. Disjonction: Soient P et Q deux prdicats. Le prdicat P ou Q
, appel disjonction de P et de Q, est un prdicat qui: est vrai
lorsque lun au mois des deux prdicat P et Q est vrais, est faux
lorsque les deux sont faux. On rsume ceci dans la table de vrit: On
crit par fois : PQ au lieu de P ou Q. Introduction la logique
mathmatique CREFOC Rads 2012~2013 14 P Q P ou Q V V V F V V V F V F
F F
15. Exemple: On en dduit les deux assertions : Considrons les
deux assertions P et Q suivantes : P = 10 est divisible par 2 , Q =
10 est divisible par 3 . Lassertion P est vraie tandis que
lassertion Q est fausse. P et Q = 10 est divisible par 2 et 10 est
divisible par 3 , P ou Q = 10 est divisible par 2 ou 10 est
divisible par 3 . Lassertion P et Q est une assertion fausse. En
revanche, lassertion P ou Q est une assertion vraie. Introduction
la logique mathmatique CREFOC Rads 2012~2013 15
16. Implication: Soient P et Q deux prdicats. Le prdicat P Q
appel implication de P vers Q est un prdicat qui: est faux lorsque
P est vrai et Q faux, est vrai dans tous les autres cas. On rsume
ceci dans la table de vrit : On dit que P est une condition
suffisante pour Q. Q P sappelle limplication rciproque de P Q.
Introduction la logique mathmatique CREFOC Rads 2012~2013 16 P Q P
Q V V V F V V V F F F F V
17. Equivalence: Soient P et Q deux prdicats. Le prdicat P Q
appel quivalence de P et de Q est un prdicat qui: est vrai lorsque
P et Q sont simultanment vrai ou faux, est faux dans tous les
autres cas. On rsume ceci dans la table de vrit : (P Q) et (Q R) se
note: P Q R. (P Q) et (Q R) se note: P Q R. Introduction la logique
mathmatique CREFOC Rads 2012~2013 17 P Q P Q V V V F V F V F F F F
V
19. quivalences: Soient R1 et R2 deux prdicats. Si R1 est vrai
lorsque R2 est vrai R1 est faux lorsque R2 est faux Alors on dit
que R1 et R2 sont de mme table de vrit ou quils sont logiquement
quivalents, et on note R1 R2 . Dans le cas contraire on note: R1 R2
. Exemple: Soit P un prdicat. Non(non(P))P. Soit P et Q deux
prdicats. P et ( P ou Q) P. Introduction la logique mathmatique
CREFOC Rads 2012~2013 19
20. Tautologie: Considrons un prdicat P. Ce prdicat peut
prendre la valeur (de vrit) Vrai ou Faux. Considrons le prdicat
compos : R = P ou non (P) . Ce prdicat est remarquable. En effet, R
est toujours vrai et ce indpendamment de P. Vrions-le : Le prdicat
compos R est alors quali de tautologie. Dfinition: Un prdicat
compos R qui est vrai quelles que soient les valeurs de vrit des
prdicats qui le composent, est appel une tautologie. Introduction
la logique mathmatique CREFOC Rads 2012~2013 20 P Non P P ou non P
V F V F V V
21. Prdicats incompatibles: Soit P un prdicat. Considrons le
prdicat compos : P et non (P) . Ce prdicat est toujours faux.
Vrions-le : On dit que les prdicats P et non(P) sont incompatibles.
Dfinition: On dit que deux prdicats composs sont incompatibles si
leur conjonction est fausse quelles que soient les valeurs de vrit
des prdicats qui les composent. Introduction la logique mathmatique
CREFOC Rads 2012~2013 21 P Non P P et non P V F F F V F
22. Proprits incontournables: Soit P et Q deux prdicats, on a
les quivalences logiques suivantes: Non(P ou Q) non(P) et non(Q)
Non(P et Q) non(P) ou non(Q) Ce sont les lois de Morgan pour les
prdicats. Soit P, Q et R trois prdicats, on a aussi les quivalences
suivantes: P ou ( Q et R) (P ou Q) et (P ou R) P et ( Q ou R) (P et
Q) ou (P et R) Introduction la logique mathmatique CREFOC Rads
2012~2013 22
23. Proprits incontournables: Soit P et Q deux prdicats , on a
les les quivalences logiques suivantes: 1) P Q (non P) ou Q 2) (Non
P) Q P et (non Q) 3) P Q (non Q) (non P) 4) P Q (P Q ) et (Q P ) On
dit que Q est une condition ncessaire pour P. Limplication: (non Q)
(non P) est appele la contrapose de P Q . Introduction la logique
mathmatique CREFOC Rads 2012~2013 23
25. Les quantificateurs simples: A partir dun prdicat P(x) dnie
sur un ensemble E, on construit de nouvelles assertions (dites
assertions quanties ) en utilisant les quanticateurs quel que soit
et il existe . Dfinition: Le quanticateur quel que soit not ,
permet de dnir lassertion quantie x E P(x) qui est vraie si pour
tous les lments x appartenant E, lassertion P(x) est vraie.
Introduction la logique mathmatique CREFOC Rads 2012~2013 25
26. Les quantificateurs simples: Exemples: x [3, 1] x+2x-30 est
vraie. n (n 3)n > 0 est fausse. n ( n paire n est paire ) est
vraie. Dfinition: Le quanticateur il existe not , permet de dnir
lassertion quantie x E P(x) qui est vraie si on peut trouver (au
moins) un lment x appartenant E tel que lassertion P(x) soit vraie.
Sil en existe un et un seul, on pourra crire ! x E P(x) et on dira
quil existe un unique lment x de E vriant P(x). Introduction la
logique mathmatique CREFOC Rads 2012~2013 26
27. Les quantificateurs simples: Exemples: Lassertion
quantifie: x x=4 est vraie. Lassertion quantifie: !x ln(x)=1 est
vraie. Si x E P(x) est vraie alors x E P(x) est vraie ATTENTION On
manipulera avec prcaution les assertions de la forme ! x E P(x)
pour lesquelles la notation ! ne dsigne pas un quanticateur (bien
quelle en ait lair !) Introduction la logique mathmatique CREFOC
Rads 2012~2013 27
28. Quantificateurs simples: En effet, on se convainc
facilement de lquivalence logique : ! x E P(x) R1 et R2 O les deux
assertions R1 et R2 sont dfinies comme suit: R1= x E P(x) . R2= xE
xE ( P(x) et P(x)) x=x Lassertion R1 traduit lexistance dun lment
de E vrifiant p(x) Lassertion R2 traduit lunicit de cet lment.
Introduction la logique mathmatique CREFOC Rads 2012~2013 28
29. Rgle de ngation: Soit P(x) un prdicat sur E. De manire
vidente, on a : Non( x E P(x) x E non(P(x)) Non( x E P(x) x E
non(P(x)) Exemple: Soit P(x) un prdicat sur E. On a : Non( x E
P(x)Q(x) x E (P(x) et non Q(x)) ATTENTION On vrie aussi que lon a :
Non( x E P(x) ) nonR1 et non R2 Avec existence et unicit
Introduction la logique mathmatique CREFOC Rads 2012~2013 29
30. Quantificateurs multiple: Dfinition: Soit P(x, y) un
prdicat deux variables avec x E et y F. Lassertion quantie: x E y F
; P(x, y) est vraie lorsque tous les lments x de E et tous les
lments y de F vriant P(x, y). Lassertion quantie: x E y F P(x, y)
est vraie lorsquil existe (au moins) un lment x appartenant E et
lorsquil existe (au moins) un lment y appartenant F vriant P(x, y).
Introduction la logique mathmatique CREFOC Rads 2012~2013 30
31. Quantificateurs multiple: Exemples: Soit le prdicat deux
variables avec z et n : est vrai. Alors, lassertion z C n N P(z, n)
est vraie. Lassertion quantie: n x + 1+nx (1+x)n est vraie
Lassertion quantie: x R y R x + y = 5 est vraie. Introduction la
logique mathmatique CREFOC Rads 2012~2013 31 1 0 ( , ) 1 (1 ) n n k
k P z n z z z
32. Rgles dutilisation: On peut combiner des quanticateurs de
natures diffrentes Par exemple, lnonc tout nombre complexe possde
au moins une racine carre scrit sous la forme :z u u= z. Mais,
attention, il faut respecter les rgles suivantes : On peut permuter
deux quanticateurs identiques : x E y F ; P(x, y) y F x E ; P(x, y)
On peut permuter deux quanticateurs identiques : x E y F ; P(x, y)
y F x E ; P(x, y) Introduction la logique mathmatique CREFOC Rads
2012~2013 32
33. Rgles dutilisation: Lassertion quantifie: ! x +* ln(x)= est
vraie Lassertion x R y R x + y = 0 est vraie. En revanche,
lassertion y R x R x + y = 0 est fausse. Lassertion quantie x R y R
x y est une assertion vraie puisque si x R alors, en prenant y = x
+ 1 on a : x x + 1. En revanche lassertion y R x R x y est fausse
puisque lensemble des rels nest pas born. Introduction la logique
mathmatique CREFOC Rads 2012~2013 33
34. Diffrents modes de demonstration Par hypothse auxiliaire,
par labsurde ,par contrapose, par contre-exemple, par rcurrence .
Introduction la logique mathmatique CREFOC Rads 2012~2013 34
35. Raisonnement par hypothse auxiliaire But : montrer quun
nonc Q est vrai. Principe : il sappuie sur la tautologie : (P et (
PQ)) Q Ainsi, si lnonc P est vrai et si limplication P Q est vraie
alors lnonc Q est ncessairement vrai. Mthodologie : on montre que
lnonc P est vrai. Lnonc Q sera alors vrai puisque P Q est vraie.
Exemple Considrons les deux ensembles A = {2,3} et B = {x /x+ x 6 =
0}. Montrons que : A = B. Introduction la logique mathmatique
CREFOC Rads 2012~2013 35
36. Raisonnement par labsurde: But : montrer quun nonc P est
vrai. Principe : il sappuie sur lquivalence logique : (non(P) Q) et
(non(P) non(Q)) P. Un raisonnement par labsurde consiste montrer
que non(P) entrane un nonc Q et son contraire non(Q). Mthodologie :
on suppose lnonc non(P) vrai et on cherche alors Q qui, sous cette
hypothse, serait la fois vrai et faux. On dit que lon a obtenu une
contradiction ou que lhypothse est contradictoire Exemple: Montrons
que 2 . Introduction la logique mathmatique CREFOC Rads 2012~2013
36
37. Raisonnement par contrapose: But : montrer des rsultats
faisant apparatre une implication P Q . Principe : il sappuie sur
lquivalence logique : P Q non(Q) non(P) Ainsi, au lieu de montrer
limplication P Q , on montre sa contrapose non(Q) non(P).
Mthodologie : on fait lhypothse que non(Q) est vrai et on montre
que cela entrane que non(P) est vrai. Exemple: Montrons que :n n
impair n impair Introduction la logique mathmatique CREFOC Rads
2012~2013 37
38. Raisonnement par contre exemple: But : il sert montrer quun
nonc de la forme x E P(x) est un nonc faux. Principe : on montre
que sa ngation est vraie. Rappel : Non x E P(x) x E non P(x)
Mthodologie : on cherche alors exhiber un lment x E qui ne vrifie
pas P(x). Exemple:Montrons que x > 0|x| < x = 0 est faux.
ATTENTION ne pas confondre avec lassertion x ( > 0 |x|< x =
0) qui est utilise pour montrer quun nombre rel est nul.
Introduction la logique mathmatique CREFOC Rads 2012~2013 38
39. Raisonnement par rcurrence: But : montrer quun nonc de la
forme: Pour tout entier naturel n > n0 P(n) est un nonc vrai.
Par exemple, n n x 1 + nx (1 + x)n Principe : Si la proprit P(n0)
est vraie et si limplication P(n) P(n + 1) est vraie pour tout
entier n n0 alors la proprit P(n) est vraie pour tout entier n n0
Introduction la logique mathmatique CREFOC Rads 2012~2013 39 n 3
k=1 n(n+1) k = 4
40. Raisonnement par rcurrence: Mthodologie: elle seffectue
ainsi en deux tapes successives. 1. tape dinitialisation : on
commence par vrifier que P(n0) est vraie. 2. tape dhrdit : on
montre ensuite que si P(n) est vraie alors P(n + 1) est vraie.
Exemple: Montrons par rcurrence que pour tout entier naturel n 0 (1
+ 2 + . . . + n)2 = 13 + 23 + . . . + n3. Introduction la logique
mathmatique CREFOC Rads 2012~2013 40
41. Pour finir: Attention aux raisonnements htifs ! Suivez
attentivement chacune des tapes suivantes : Considrons dans
lquation : x=x-1 (1) Puisque la valeur nulle ne vrifie pas cette
quation, divisons par x membre membre. Aprs rarrangement des
termes, nous obtenons (2) En regroupant les galits (1) et (2), nous
en dduisons (3) Finalement, puisque x est non nul, nous multiplions
par x lgalit (3) pour obtenir lquation: x3 = -1 (4) dont 1 est de
toute vidence une solution. Injectons cette solution dans lgalit
(1). Nous obtenons au final que 1 = 2. Donc, firement, on crit : 2
= -1 du Candide Bien videmment, nous avons commis une erreur dans
notre raisonnement. Mais o ? Introduction la logique mathmatique
CREFOC Rads 2012~2013 41 1 - = x-1 x 1 - = x x
42. Annexes: Wikipdia. INSA de Lyon Le site du zro Introduction
la logique mathmatique CREFOC Rads 2012~2013 42
43. Introduction la logique mathmatique CREFOC Rads 2012~2013
43
