Chapitre n°2 Logique mathématiques et raisonnement

Les connecteurs logiques

Expression, proposition, axiome et théorème

Définition : Une expression est un ensemble de signes (lettres, chiffres, symboles, mots, ..) possédant un sens
dans un univers donné.

Exemple : En algèbre « 3x2 + 4x-5 »

En géométrie « ABC un triangle »

Définition : Une proposition propose l’expression d’un fait. Une proposition est un synonyme d’énoncé.

Exemple : En algèbre « 3x2 + 4x 5 = 0 », « 23 =−8 »

En géométrie « ABC est un triangle équilatéral », « ABCD est un losange ».
On peut composer des expressions ou des propositions en utilisant certains mots ou certains symboles
possédant une signification tels que les connecteurs logiques (connecteurs propositionnels) et les
quantificateurs. On répartit les propositions en deux catégories : les axiomes et les théorèmes.

Définition : Un axiome est une proposition dont on admet qu’elle est vraie.
Un théorème est une proposition dont il faut établir la véracité.
Un théorème est donc vrai s’il se déduit logiquement d’un axiome
Exemple d’axiome : (5ème postulat d’Euclide)
« Par un point extérieur à une droite, on ne peut tracer qu’une parallèle. »

Exemple de théorème : (théorème de Pythagore)

« Un triangle est rectangle si et seulement si le carré de son hypoténuse est égal à la somme des carrés
des deux côtés »

La négation : le connecteur logique NON

Définition : La négation d'une proposition notée 𝑃̅ est la proposition qui affirme que P est fausse. Elle
est vraie si P est fausse, et fausse si P est vraie.
𝑃̅ n'est pas son (( contraire )) (même si des fois cela peut être le cas).
Quelques exemples :
P 𝑃̅
x>4 x≤ 4
A, B, C alignés ABC triangle

Du fait du principe de dualité, c’est à dire qu’une proposition est soit vraie soit fausse, on a donc : soit la
proposition P est vraie soit la proposition 𝑃̅ est vraie. Pour analyser les différents cas possibles, on a l’habitude
de présenter les connecteurs logiques à l’aidede tables appelées « tables de vérité » . La table de vérité du
connecteur NON sera donc :
P 𝑃̅
Vrai Faux
Faux Vrai

Si on utilise une notation informatique on remplaçant Vrai par 1 et Faux par 0 on obtient alors :
P 𝑃̅
1 0
0 1
La conjonction : le connecteur logique ET

Définition : le connecteur logique ET porte sur deux propositions P, Q. La proposition (P et Q) notée P∧Q est
vraie si les deux propositions P et Q sont vraies. La proposition P∧Q est fausse dans tous les autres cas.
On a la table de vérité suivante :

P Q P∧Q
Vrai Vrai Vrai
Vrai Faux Faux
Faux Vrai Faux
Faux Faux Faux

Quelques exemples :

P Q P∧Q
x < 10 X>2 x ∈ ] 2 ; 10 [
ABCD losange ABCD rectangle ABCD carré

La disjonction : le connecteur logique OU

Définition : le connecteur logique OU porte sur deux propositions P, Q.

La proposition (P ou Q) notée P∨Q est fausse si les deux propositions sont simultanément fausses. La
proposition P∨Q est vraie dans tous les autres cas.
On a la table de vérité suivante :

P Q P∨Q
Vrai Vrai Vrai
Vrai Faux Vrai
Faux Vrai Vrai
Faux Faux Faux
Quelques exemples :

P Q P∨Q
x<2 x > 10 x ∈] − ∞ ; 2 [∪]10 ; +∞[
n multiple de 3 n pair
inférieur à 10 inférieur à 10 n ∈ {2, 3, 4, 6, 8, 9}

̅̅̅̅̅̅̅
On peut exprimer le connecteur OU à l’aide des connecteurs ET et NON : P ∨ Q = 𝑃 ̅ ⋀𝑄̅

Pour s’en convaincre voici la table de vérité montrant ceci :

P Q 𝑃̅ 𝑄̅ P∨Q 𝑃̅ ∧ 𝑄̅ P̅̅̅̅̅̅
̅ ⋀Q̅
Vrai Vrai Faux Faux Vrai Faux Vrai
Vrai Faux Faux Vrai Vrai Faux Vrai
Faux Vrai Vrai Faux Vrai Faux Vrai
Faux Faux Vrai Vrai Faux Vrai Faux
L’implication : le connecteur logique Si. . . alors

Définition : Le connecteur logique SI … alors, porte sur deux propositions. La proposition (Si P alors Q) notée
P ⟹ Q est fausse lorsque l’on a simultanément la proposition P vraie et la proposition Q fausse, la proposition
P ⟹ Q est fausse, la proposition P ⟹ Q est vraie dans tous les autres cas.

On a la table de vérité suivante :

P Q P⇒Q 𝑃̅ ou Q
Vrai Vrai Vrai Vrai
Vrai Faux Faux Faux
Faux Vrai Vrai Vrai
Faux Faux Vrai Vrai
Quelques exemples :
P Q P⇒Q
x = −2 2
x =4 Si x = −2 alors x2 = 4
ABC Si ABC équilatéral alors
ABC isocèle
équilatéral ABC isocèle

On peut exprimer le connecteur logique : Si . . . alors, à l’aidedes connecteurs OU et NON :

P ⇒ Q = 𝑃̅ ⋁𝑄̅

Pour s’en convaincre voici la table de vérité montrant ceci :

P 𝑃̅ Q 𝑃 ̅ ∨ 𝑄̅
Vrai Faux Vrai Vrai
Vrai Faux Faux Faux
Faux Vrai Vrai Vrai
Faux Vrai Faux Vrai

Lorsque l’on a 𝑃 ⟹ 𝑄, on dit que Q est une condition nécessaire à P et que P est une condition suffisante à Q.

Exemple : Soit P la proposition : « le triangle ABC est équilatéral »

Soit Q la proposition : « le triangle ABC est isocèle »

Nous avons 𝑃 ⟹ 𝑄, un triangle équilatéral est nécessairement isocèle. En effet un triangle équilatéral est au
moins isocèle.
Par contre pour montrer qu’un triangle est isocèle, il est suffisant qu’il soit équilatéral mais cela n’est pas
nécessaire.

La structure d’un théorème obéit à la structure Si … alors. En effet il se décompose de 2 parties :

- les hypothèses (proposition H) puis les conclusions (proposition C). Si le théorème est démontré alors on a :
H ⟹ C. Pour montrer qu’un théorème est faux, il suffit de montrer, par un contre-exemple, qu’il existe un cas
où H est vrai avec C faux.

- Pour montrer que 𝑃 ⟹ 𝑄, il est parfois plus facile de démontrer que, si l’on a pas Q alors on n’a pas P.
Cela s’appelle la contraposée :

𝑄̅ ⇒ 𝑃 ̅

Cela revient à dire que : si le triangle n’est pas isocèle, il n’est pas équilatéral.
Montrons cette propriété grâce à une table de vérité :

P Q 𝑄̅ 𝑃̅ 𝑄̅ ⇒ 𝑃 ̅ 𝑃 ⇒𝑄
Vrai Vrai Faux Faux Vrai Vrai
Vrai Faux Vrai Faux Faux Faux
Faux Vrai Faux Vrai Vrai Vrai
Faux Faux Vrai Vrai Vrai Vrai

L’équivalence logique : le connecteur logique Si et seulement si

Le connecteur logique Si et seulement si porte sur deux propositions. La proposition(P si et seulement si
Q) notée P⟺ Q est vrai lorsque l’on a simultanément P et Q vraies ou fausses. La proposition est fausse dans
les autres cas. On a la table de vérité suivante :

P Q 𝑃 ⇒𝑄 𝑄 ⇒𝑃 P ⇔Q
Vrai Vrai Vrai Vrai Vrai
Vrai Faux Faux Vrai Faux
Faux Vrai Vrai Faux Faux
Faux Faux Vrai Vrai Vrai

Pour qu’une équivalence soit vraie, il faut avoir : P ⇒ Q et Q ⇒ P

Quelques exemples :

P Q P ⇔Q
2
x =4 x = 2 ou x = −2 x = 4 ⇔ x = 2 ou x = −2
2

ABC triangle rectangle ABC rectangle en A

BC2 = AB2 + AC2
en A ⇔ BC2 = AB2 + AC2

Pour démontrer une équivalence logique, on procèdera souvent en deux étapes :

-P⇒Q

-Q⇒P

C’est le cas du deuxième exemple qui correspond au théorème de Pythagore et à sa réciproque. Lorsque
l’on a P Q, on dit que P est une condition nécessaire et suffisante de Q et inversement

Le quantificateur universel

Définition : Un quantificateur permet de préciser le domaine de la validité d’une proposition. Le symbole ∀ qui
signifie « quel que soit » ou « pour tout » représente le quantificateur universel. Ce symbole représente la lettre
A renversée qui est l’initiale du mot anglais « ALL ».

Exemple : ∀x ∈IR, x2 ≥ 0 « quel que soit x appartenant à R, x2 est positif ou nul »

Le quantificateur existentiel
Définition : Le symbole ∃ qui signifie « il existe au moins un … » représente le quantificateur existentiel. Ce
ce symbole représente la lettre « E » renversée qui est l’initiale du mot anglais « EXIST ».
On ajoute un point d’exclamation pour désigner l’unicité. On a alors :

∃ ! qui signifie « il existe un unique .. ; tel que »

Exemple :
∃! x∈[0;1], x2 + 4x + 1=0 «Il existe un unique x appartenant à l’intervalle [0;1] tel que : x2 + 4x + 1 = 0 »
Propriétés des quantificateurs
L’ordre des quantificateurs
L’ordre dans lequel on écrit les quantificateurs change la signification : ∀ x ∈ R, ∃ y ∈ R, y > x
« Quel que soit le réel x, il existe au moins un réel y tel que y soit supérieur à x »
On peut toujours trouver un nombre supérieur à un nombre réel donné car l’ensemble R n’est pas borné. La
propositionest vraie.
Inversons maintenant les quantificateurs : ∃ x ∈ R, ∀ y ∈ R, y>x
« Il existe au moins un réel x tel que pour tout réel y, y soit supérieur à x »
Cette proposition cette fois est fausse car on ne peut trouver unréel inférieur à tous les autres. En effet l’ensemble
R n’a pas de borne inférieure.

Négation d’une proposition universelle

Définition : Une proposition universelle s’énonce : « Pout tout élément x d’un en- semble E, x possède la
proposition P ». Sa négation sera : « il existe au moins un élément x de l’ensemble E qui ne possède pas la
propriété P »

Soit la proposition
« Tous les lecteurs de ce chapitre comprennent tout ce qui est écrit »
Sa négation sera donc : « Il existe au moins un lecteur qui ne comprend pas ce chapitre »
Pour démontrer qu’une proposition universelle n’est pas vraie, il suffit donc de trou- ver un seul x qui ne
vérifie pas la proposition P. C’est ce qu’on nomme un « contre- exemple ». Lorsque l’on énonce une
proposition, on cherche un contre-exemple pour tester si cette proposition peut être vraie. Si aucun contre-
exemple ne vient, il reste à démontrer la proposition ce qui s’avère souvent bien plus difficile.

Négation d’une proposition existentielle

Définition : Une proposition existentielle s’énonce : « Il existe au moins un élément x de l’ensemble E qui
possède la propriété P ». Sa négation sera : « Pour tout élément x de l’ensemble E, x ne vérifie pas P ».

Soit la proposition P : ∃ x ∈ R, x2 = −1
Cette proposition est fausse car un carré ne peut être négatif. Par contre sa négation est vraie :
∀ x ∈ R, x2 ≠ −1

Raisonnement par récurrence

Le raisonnement par récurrence est une forme de raisonnement mathématique dont l'objet est de démontrer
qu’une propriété est vraie de tous les entiers naturels. Il utilise le fait que si un ensemble d’entiers naturels
contient 0 et contient le successeur de chacun de ses éléments alors cet ensemble contient tous les entiers naturels.

Pour montrer que la propriété Pn est vraie pour tout n, on procède en trois étapes :

- Etape 1 (initialisation) : On vérifie que la propriété est vraie pour n = 0.

- Etape 2 (hérédité ) : On suppose que la propriété Pn est vraie on démontre que P(n+1) est vraie

- Etape 3 (conclusion) :On rédige alors « comme P(n)est vraie et qu’il y a hérédité, P(n)est vraie pour tout n».

Le raisonnement par récurrence est intimement lié à la propriété de bon ordre de N, l'ensemble des entiers
naturels, qui dit que tout ensemble non vide d’entiers naturels possède un plus petit élément.
 𝒏(𝒏+𝟏)
Exemple : Montrons que la somme des n premiers entiers 𝟏 + 𝟐 + 𝟑+. . +𝒏 = 𝟐
1×(1+1)
Initialisation : P1 est vraie car 1 =
𝟐

Hérédité : On suppose que jusqu’à l’ordre n, la propriété P(n)est vraie c-à-d que 1 + 2 + 3+. . +n = n(n+1) est
𝟐
(n+1)(n+2)
varie et démontrons que 𝑃(𝑛) est vraie c-à-d que 1 + 2 + 3+. . +n + (n + 1) = 𝟐

Exercice d’entrainement : montrer par récurrence que pour tout 𝑛 ≥ 1, 1 + 3 + 5+. . +(2𝑛 − 1) = 𝑛²

Raisonnement par contraposée

Nous avons vu au chapitre précédent que les implications P⟹Q et 𝑄̅⟹𝑃̅ 𝑠𝑜𝑛𝑡 é𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑡𝑒𝑠. En logique,
la contraposition est un type de raisonnement consistant à affirmer l’implication « 𝑄̅⟹𝑃̅» à partir de
l’implication « P⟹Q». L’implication « 𝑄̅⟹𝑃̅ » est appelée contraposée de « P⟹Q».

Exemple : proposition contraposée de la proposition :

« s’il pleut, alors le sol est mouillé » est « si le sol n’est pas mouillé, alors il ne pleut pas ».

Exercice : donner la proposition contraposée du théorème de Pythagore :

« Si ABC est un triangle rectangle en A, alors BC² = AB² + AC² ».

Sa contraposée est : « Si BC² ≠ AB² + AC² alors, ABC n’est pas un triangle rectangle en A »

Exercice : Soit, 𝑃𝑛 la proposit ion suivant e :

𝑃𝑛 : « Pour tout entier naturel n, si n² est un nombre pair, alors n est un nombre pair ».

1) Ecrire la proposition 𝑃𝑛 à l’aide des quantificateurs logiques,

2) Ecrire la contraposée de la proposition 𝑃𝑛 à l’aide des quantificateurs logiques

3) Démontrons par contraposée la proposition 𝑃𝑛

Raisonnement par l’absurde

Pour démontrer l’implication P⟹Q (autrement dit si P est vraie, alors Q l’est aussi). Le raisonnement par
l’absurde consiste à supposer que P est vraie et que Q est fausses. On aboutit alors à une contradiction, ce qui
entraîne que Q doit être nécessairement vraie.

Exemple : On considère deux réels positifs x et y. On souhaite montrer par l’absurde la proposition :
x y
« Si 1+y = 1+x, alors x=y. »

1.) Pour raisonner par l’absurde, quelles hypothèses doit-on faire ?

2.) Montrer alors que 𝑥² − 𝑦² = −(𝑥 − 𝑦)

3.) En déduire que 𝑥 + 𝑦 = −1. Est-ce possible ?

4.) Conclure