1ʳᵉ Bac · Sciences Maths · Chapitre 1

Notions de logique

1 · Résumé du cours

1.1 Propositions et fonctions propositionnelles

Définition — proposition Une proposition (ou assertion) est un énoncé mathématique auquel on peut attribuer une seule valeur de vérité : vrai (V) ou faux (F).

1.1.1 La négation

Définition La négation de

P

, notée

\overline P

(ou

\neg P

), est vraie lorsque

P

est fausse, et fausse lorsque

P

est vraie.

\begin{array}{|c|c|}\hline P & \overline P\\ \hline V & F\\ \hline F & V\\ \hline\end{array}

Deux principes fondamentaux Pour toute proposition

P

$P$ et $\overline P$ ne peuvent être vraies en même temps — principe de non-contradiction ;
$P\vee\overline P$ est toujours vraie — principe du tiers exclu.

Exemples. « $2+3=5$ » est vraie ; « $7$ est pair » est fausse ; « $x>1$ » n'est pas une proposition (sa vérité dépend de $x$ ) ; « Quel âge as-tu ? » non plus (ce n'est pas une affirmation).

1.1.2 Fonction propositionnelle

Définition — prédicat Une fonction propositionnelle (ou prédicat) est un énoncé

P(x)

dépendant d'une variable

x

d'un ensemble

E

. Pour chaque valeur fixée de

x

P(x)

devient une proposition.

Exemple. Dans $E=\mathbb{R}$ , $P(x):$ « $x^2-1=0$ ». Alors $P(1)$ est vraie, $P(2)$ est fausse, et l'ensemble des $x$ qui rendent $P(x)$ vraie est $\{-1,\,1\}$ .

Proposition ou pas ? Le test : peut-on répondre sans ambiguïté « vrai » ou « faux » ? Si oui, c'est une proposition. Un énoncé à variable libre n'est qu'une fonction propositionnelle, tant qu'on n'a pas fixé la variable ou placé un quantificateur devant.

1.2 Les quantificateurs

Définition Pour transformer

P(x)

en proposition, on quantifie la variable :

quantificateur universel $\forall$ (« pour tout ») : $\forall x\in E,\ P(x)$ se lit « pour tout $x$ de $E$ , $P(x)$ est vraie » ;
quantificateur existentiel $\exists$ (« il existe ») : $\exists x\in E,\ P(x)$ se lit « il existe au moins un $x$ de $E$ tel que $P(x)$ ».

On note

\exists!\,x\in E,\ P(x)

pour « il existe un unique

x

tel que

P(x)

».

Exemples. $\forall x\in\mathbb{R},\ x^2\ge0$ (V) ; $\exists x\in\mathbb{R},\ x^2=2$ (V, $x=\sqrt2$ ) ; $\forall x\in\mathbb{R},\ x^2=2$ (F, $x=0$ ne convient pas) ; $\exists!\,x\in\mathbb{R},\ x+3=5$ (V, seul $x=2$ ).

L'ordre des quantificateurs compte

\forall

\exists

ne commutent pas. Comparez, pour

x,y\in\mathbb{R}

\underbrace{\forall x,\ \exists y,\ y>x}_{\text{V : }y=x+1\text{ marche}}\qquad\text{et}\qquad\underbrace{\exists y,\ \forall x,\ y>x}_{\text{F : aucun }y\text{ ne dépasse tout }x}.

Dans le premier,

y

peut dépendre de

x

; dans le second, le même

y

devrait dépasser tous les

x

. Lisez toujours de gauche à droite.

Domaine et portée Le domaine

E

fait partie de l'énoncé :

\exists x\in\mathbb{R},\ x^2=2

est vraie, mais

\exists x\in\mathbb{Q},\ x^2=2

est fausse.

1.2.1 Négation d'une proposition quantifiée

Règle La négation échange les quantificateurs et nie le prédicat :

\overline{\big(\forall x\in E,\ P(x)\big)}\;=\;\exists x\in E,\ \overline{P(x)}

\overline{\big(\exists x\in E,\ P(x)\big)}\;=\;\forall x\in E,\ \overline{P(x)}

Exemple. La négation de $\forall x\in\mathbb{R},\ \exists y\in\mathbb{R},\ x+y=0$ est $\exists x\in\mathbb{R},\ \forall y\in\mathbb{R},\ x+y\neq0$ : on échange chaque quantificateur, de gauche à droite, puis on nie la relation finale.

1.3 Opérations sur les propositions

À partir de $P$ et $Q$ , on construit de nouvelles propositions à l'aide de connecteurs logiques, décrits par leur table de vérité.

1.3.1 Conjonction et disjonction

Définition

la conjonction « $P$ et $Q$ », notée $P\wedge Q$ , est vraie uniquement quand $P$ et $Q$ sont vraies toutes les deux ;
la disjonction « $P$ ou $Q$ », notée $P\vee Q$ , est fausse uniquement quand $P$ et $Q$ sont fausses toutes les deux.

\begin{array}{|c|c|c|c|}\hline P & Q & P\wedge Q & P\vee Q\\ \hline V & V & V & V\\ \hline V & F & F & V\\ \hline F & V & F & V\\ \hline F & F & F & F\\ \hline\end{array}

Le « ou » mathématique est inclusif En français courant, « fromage ou dessert » est exclusif. En maths, le « ou » est inclusif :

P\vee Q

reste vraie quand

P

Q

le sont ensemble. Ainsi «

x\le2

x\ge0

» est vraie pour tout réel.

1.3.2 L'implication

Définition L'implication «

P\Rightarrow Q

» (« si

P

alors

Q

») est fausse dans le seul cas où

P

est vraie et

Q

fausse ; vraie dans tous les autres cas.

\begin{array}{|c|c|c|c|}\hline P & Q & P\Rightarrow Q & Q\Rightarrow P\\ \hline V & V & V & V\\ \hline V & F & F & V\\ \hline F & V & V & F\\ \hline F & F & V & V\\ \hline\end{array}

« Le faux implique n'importe quoi » Quand

P

est fausse,

P\Rightarrow Q

est vraie, quelle que soit

Q

. Ainsi «

2<0\Rightarrow 3=7

» est vraie ! Une implication ne garantit rien sur

Q

tant que

P

n'est pas réalisée.

Vocabulaire de l'implication Pour

P\Rightarrow Q

: la réciproque est

Q\Rightarrow P

; la contraposée est

\overline Q\Rightarrow\overline P

; on dit que

P

est suffisante pour

Q

, et

Q

nécessaire pour

P

Exemple. « $x=2\Rightarrow x^2=4$ » est vraie. Sa réciproque « $x^2=4\Rightarrow x=2$ » est fausse ( $x=-2$ est un contre-exemple), mais sa contraposée « $x^2\neq4\Rightarrow x\neq2$ » est vraie.

1.3.3 L'équivalence

Définition L'équivalence «

P\Leftrightarrow Q

» («

P

si et seulement si

Q

») est vraie lorsque

P

Q

ont la même valeur de vérité. Elle équivaut à

(P\Rightarrow Q)\wedge(Q\Rightarrow P)

\begin{array}{|c|c|c|}\hline P & Q & P\Leftrightarrow Q\\ \hline V & V & V\\ \hline V & F & F\\ \hline F & V & F\\ \hline F & F & V\\ \hline\end{array}

Prouver une équivalence = prouver DEUX implications Pour établir

P\Leftrightarrow Q

, on démontre séparément

P\Rightarrow Q

(sens direct) puis

Q\Rightarrow P

(réciproque). Oublier un sens est l'erreur classique.

1.4 Lois logiques

Définition — tautologie Une loi logique (ou tautologie) est une proposition toujours vraie, quelles que soient les valeurs de vérité des propositions qui la composent (sa colonne finale ne contient que des V).

Les lois à connaître Pour toutes propositions

P,Q,R

\overline{\overline P}\Leftrightarrow P,\qquad P\wedge Q\Leftrightarrow Q\wedge P,\qquad P\vee Q\Leftrightarrow Q\vee P\quad(\text{commutativité}),

P\wedge(Q\vee R)\Leftrightarrow(P\wedge Q)\vee(P\wedge R),\qquad P\vee(Q\wedge R)\Leftrightarrow(P\vee Q)\wedge(P\vee R)\quad(\text{distributivité}),

\overline{P\wedge Q}\Leftrightarrow\overline P\vee\overline Q,\qquad \overline{P\vee Q}\Leftrightarrow\overline P\wedge\overline Q\quad(\textbf{De Morgan}),

(P\Rightarrow Q)\Leftrightarrow(\overline P\vee Q),\qquad \overline{P\Rightarrow Q}\Leftrightarrow(P\wedge\overline Q),

(P\Rightarrow Q)\Leftrightarrow(\overline Q\Rightarrow\overline P),\qquad \big[(P\Rightarrow Q)\wedge(Q\Rightarrow R)\big]\Rightarrow(P\Rightarrow R)\quad(\text{transitivité}).

Vérifier la contraposition par table

\begin{array}{|c|c|c|c|c|c|}\hline P & Q & P\Rightarrow Q & \overline Q & \overline P & \overline Q\Rightarrow\overline P\\ \hline V & V & V & F & F & V\\ \hline V & F & F & V & F & F\\ \hline F & V & V & F & V & V\\ \hline F & F & V & V & V & V\\ \hline\end{array}

Les colonnes

P\Rightarrow Q

\overline Q\Rightarrow\overline P

sont identiques : les deux propositions sont équivalentes.

De Morgan, le réflexe pour nier Pour nier une conjonction ou une disjonction, on échange

\wedge

\vee

et on nie chaque morceau. La négation de «

x\ge0

x\le1

» est «

x<0

x>1

». Couplé à la règle des quantificateurs, c'est l'outil universel de la négation.

1.5 Les raisonnements mathématiques

Démontrer une proposition, c'est établir qu'elle est vraie à partir des hypothèses, des définitions et des propriétés connues. Voici les principales méthodes.

1.5.1 Raisonnement direct

Méthode Pour démontrer directement

P\Rightarrow Q

, on suppose

P

vraie, puis on enchaîne des déductions justifiées jusqu'à

Q

Exemple. La somme de deux rationnels est rationnelle : si $a=\frac pq$ et $b=\frac rs$ avec $p,r\in\mathbb{Z}$ , $q,s\in\mathbb{N}^*$ , alors $a+b=\frac{ps+rq}{qs}\in\mathbb{Q}$ .

1.5.2 Raisonnement par contre-exemple

Méthode Pour montrer qu'une proposition «

\forall x\in E,\ P(x)

» est fausse, il suffit d'exhiber un seul

x_0

tel que

P(x_0)

soit fausse.

Exemple. « Tout entier naturel est somme de deux carrés » est faux : $3$ n'est pas somme de deux carrés. L'entier $3$ est un contre-exemple.

1.5.3 Raisonnement par contraposée

Méthode Pour démontrer

P\Rightarrow Q

, on peut démontrer sa contraposée

\overline Q\Rightarrow\overline P

(qui lui est équivalente). On y gagne quand

\overline Q

est plus maniable que

P

Exemple. « si $n^2$ est pair alors $n$ est pair » : la contraposée « $n$ impair $\Rightarrow n^2$ impair » se prouve avec $n=2k+1$ , $n^2=2(2k^2+2k)+1$ .

1.5.4 Raisonnement par équivalences successives

Méthode Pour résoudre une équation ou prouver une équivalence, on enchaîne des

\Leftrightarrow

jusqu'à un résultat évident. Chaque étape doit être réversible — sinon on n'a qu'une implication.

Exemple. $2x-1=5\iff 2x=6\iff x=3$ . Toutes les étapes sont réversibles : $S=\{3\}$ .

1.5.5 Raisonnement par disjonction des cas

Méthode Lorsqu'une propriété se démontre différemment selon les situations, on partage l'ensemble d'étude en cas qui le recouvrent entièrement, et l'on conclut dans chaque cas.

Exemple. $\forall n\in\mathbb{N},\ n(n+1)$ est pair : si $n$ est pair, $n(n+1)$ l'est ; si $n$ est impair, $n+1$ est pair. Dans les deux cas, $n(n+1)$ est pair.

1.5.6 Raisonnement par l'absurde

Méthode Pour démontrer

P

, on suppose qu'elle est fausse (

\overline P

vraie) et l'on en déduit une contradiction : l'hypothèse

\overline P

était intenable, donc

P

est vraie.

Exemple — $\sqrt2$ est irrationnel. Si $\sqrt2=\frac pq$ irréductible, alors $p^2=2q^2$ , donc $p$ pair ( $p=2k$ ), puis $q^2=2k^2$ donc $q$ pair : $p$ et $q$ tous deux pairs contredit « $\frac pq$ irréductible ». Donc $\sqrt2\notin\mathbb{Q}$ .

1.5.7 Raisonnement par récurrence

Principe de récurrence Soit

P(n)

une propriété dépendant de

n\in\mathbb{N}

n_0\in\mathbb{N}

. Si

(Initialisation) $P(n_0)$ est vraie ;
(Hérédité) pour tout $n\ge n_0$ , $P(n)\Rightarrow P(n+1)$ ,

alors

P(n)

est vraie pour tout

n\ge n_0

Rédiger une récurrence

Énoncer clairement $P(n)$ ;
Initialisation : vérifier $P(n_0)$ ;
Hérédité : supposer $P(n)$ vraie (hypothèse de récurrence) pour un $n\ge n_0$ fixé, et en déduire $P(n+1)$ ;
Conclusion : $P(n)$ est vraie pour tout $n\ge n_0$ .

Exemple :

1+2+\dots+n=\frac{n(n+1)}2

. Init.

n=1

1=\frac{1\cdot2}2

. Hérédité :

\frac{n(n+1)}2+(n+1)=\frac{(n+1)(n+2)}2

L'initialisation n'est pas une formalité Une propriété peut être héréditaire sans jamais être vraie : «

P(n): 2^n

est divisible par

3

» vérifie

P(n)\Rightarrow P(n+1)

(si

3\mid 2^n

alors

3\mid 2^{n+1}=2\cdot2^n

), pourtant

P(0)

est fausse et

P(n)

l'est pour tout

n

. Sans initialisation, la récurrence ne prouve rien.

2 · Exercices résolus

Négation · quantificateurs

Exercice 1

Écrire la négation de : a) $\forall x\in\mathbb{R},\ x^2+1>0$ ; b) $\exists x\in\mathbb{R},\ x^2=x$ ; c) $\forall x\in\mathbb{R},\ \exists y\in\mathbb{R},\ x+y=0$ .

Voir la correction

On échange les quantificateurs et on nie le prédicat. a) $\exists x\in\mathbb{R},\ x^2+1\le0$ . b) $\forall x\in\mathbb{R},\ x^2\neq x$ . c) $\exists x\in\mathbb{R},\ \forall y\in\mathbb{R},\ x+y\neq0$ .

Contraposée

Exercice 2

Soit $n\in\mathbb{N}$ . Montrer que « si $n^2$ est impair, alors $n$ est impair ».

Voir la correction

Par contraposée, montrons « si $n$ est pair, alors $n^2$ est pair ». Si $n=2k$ , alors $n^2=4k^2=2(2k^2)$ est pair. La contraposée est vraie, donc l'implication initiale aussi. ∎

Récurrence

Exercice 3

Démontrer que $\forall n\in\mathbb{N}^*,\ 1^2+2^2+\dots+n^2=\dfrac{n(n+1)(2n+1)}6$ .

Voir la correction

Initialisation ( $n=1$ ) : à gauche $1$ , à droite $\frac{1\cdot2\cdot3}6=1$ . ✓

Hérédité : en supposant la formule au rang $n$ , $\displaystyle\sum_{k=1}^{n+1}k^2=\frac{n(n+1)(2n+1)}6+(n+1)^2=\frac{(n+1)\,[\,n(2n+1)+6(n+1)\,]}6$ . Or $n(2n+1)+6(n+1)=2n^2+7n+6=(n+2)(2n+3)$ , d'où $\displaystyle\sum_{k=1}^{n+1}k^2=\frac{(n+1)(n+2)(2n+3)}6$ , la formule au rang $n+1$ .

Conclusion : vraie pour tout $n\ge1$ . ∎

Fiche de révisionL’essentiel du chapitre en une page — formules, méthodes et astucesVoir la fiche QCM interactifTeste-toi sur ce chapitre — 22 questions auto-corrigéesCommencer le QCM