Mis à jour le mercredi 28 septembre 2016
  • 4 heures
  • Facile
Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Introduction du cours

‌À la limite de la philosophie, la logique est une branche fondamentale des mathématiques qui permet d'établir la valeur de vérité de propositions et de construire des raisonnements mathématiques.

Ce tutoriel constitue une initiation à cette branche primordiale des mathématiques. Nous définirons les notions de proposition et d'opérateur, construirons des tables de vérité, expliquerons les notions d'implication, d'implication réciproque et d'équivalence avant d'aborder les différents types de raisonnements que l'on peut suivre en mathématiques. Le tout sera saupoudré de nombreux exercices accessibles à partir de zéro ou presque !

C'est parti !

Propositions logiques

Définition

Une proposition logique (ou assertion) est une affirmation formée d'un assemblage de symboles et de mots, portant sur des objets mathématiques, à laquelle on peut clairement attribuer la valeur vraie ou la valeur faux.

On note $\(P\)$ une proposition.
Par définition A satisfait les 3 principes (ou axiomes) suivants :

  • Principe d'identité : P est P.

    Autrement dit si P est vrai alors P est vrai et si P est faux alors P est faux.

  • Principe de non contradiction : P ne peut pas à la fois être vrai et faux.

  • Principe du tiers exclus : soit P est vrai, soit P est faux.
    Il n'existe pas d'autre valeur de vérité en logique mathématique.

Ces trois principes constituent le fondement de tout raisonnement mathématique. Le dernier point mérite que l'on s'y attarde un instant :

Soit $\(P\)$ la proposition « Le carré d'un nombre réel est strictement positif ».

Alors ? Vrai ou faux ?
L'intuition première serait de répondre "ça dépend du nombre", c'est le cas pour la plupart des nombres mais c'est faux pour zéro (car $\(0^2 \not > 0\)$).

Le problème est que cette réponse est en contradiction avec le principe du tiers exclus. Il faut donc attribuer clairement à cette proposition la valeur vrai ou la valeur faux.

Étant donné qu'il existe au moins un nombre (ici zéro) pour lequel cette proposition est fausse, on dira que la proposition $\(P\)$ est fausse.

Quelques exemples

Image utilisateur

$\(A\)$ : « Le nombre de lettres dans l'alphabet français est 10. »
La proposition A est fausse.

$\(B\)$ : « $\(2 + 2 = 4\)$ »
La proposition  $\(B\)$ est vraie.

$\(C\)$ :  «  $\(x> 1\)$ »
$\(C\)$ n'est pas une proposition logique complète car elle contient une variable libre $\(x\)$. On ne sait pas ce qu'est $\(x\)$ (un point ? un nombre entier ? un vecteur ? une étoile de l'univers ?). On ne peut donc pas attribuer de valeur de vérité à la proposition $\(C\)$.

$\(C'\)$ : « Soit $\(x\)$ un nombre réel, alors $\(x > 1\)$ »
La proposition $\(C'\)$ est fausse. En effet $\(C'\)$ est une proposition logique car on a défini la variable $\(x\)$ comme étant un nombre réel. Mais elle est fausse car par exemple 0 est un nombre réel et $\(0 < 1\)$.

À retenir

Les propositions logiques ne peuvent prendre que deux valeurs : VRAI ou FAUX (d'où le nom de logique bivalente).
Il faut bien faire la distinction entre une proposition (qui est une phrase) et sa valeur (qui est soit VRAI soit FAUX).

Opérateurs de base

Les opérateurs permettent de construire de nouvelles propositions à partir d'une ou de plusieurs propositions initiales.
Commençons par le premier (et le plus simple !) d'entre eux l'opérateur « NON ».

La négation

Apprenons à dire non !
Soit A une proposition. On définit une proposition « non A » que l'on note ¬A (avec une sorte de petit L allongé vers le bas).
Si A est vraie alors ¬A est fausse.
Si A est fausse alors ¬A est vraie.

Image utilisateur

On peut établir la table de vérité de l'opérateur de négation à partir de sa définition.

Définition :
Une table de vérité est un tableau définissant la valeur d'une fonction logique pour chacune des combinaisons possibles des entrées.

Construction :
Dans la première colonne, je place toutes les valeurs que peut prendre A (c'est à dire Vrai ou Faux). Dans la seconde colonne, je place la valeur de vérité de ¬A correspondante.

A

¬A

VRAI

FAUX

FAUX

VRAI

Par convention et pour faciliter la lecture de grandes tables, on écrit 0 pour la valeur FAUX et 1 pour la valeur VRAI.

A

¬A

1

0

0

1

Ce connecteur est assez intuitif dans la mesure ou nous l'utilisons quotidiennement.

Quelques exemples :
A : « Paris est la capitale de la France » (1)
¬A : « Paris n'est pas la capitale de la France » (0)

B : « π est un nombre entier » (0)
¬B : « π n'est pas un nombre entier » (1)

C : « 5 est un nombre impair » (1)
¬C : « 5 est un nombre pair » (0)

Ce premier opérateur doit maintenant vous paraître assez simple. Pour construire des raisonnements logiques on a besoin d'utiliser des opérateurs permettant de lier deux propositions logiques entre elles (on les appelle des opérateurs binaires).

La conjonction

Le premier d'entre eux est l'opérateur « ET ».
Soient A et B deux propositions.
On définit une nouvelle proposition « A ET B » que l'on note « A ∧ B » (Avec une sorte de v à l'envers)
Cette nouvelle proposition est

  • vraie lorsque A et B sont vraies en même temps

  • fausse dans tous les autres cas

Image utilisateur

On déduit de cette définition la table de vérité de la proposition « A ∧ B »

A

B

A ∧ B

1

1

1

1

0

0

0

1

0

0

0

0

Les deux première colonnes permettent de lister tous les cas possibles pour les valeurs de vérité de A et de B. La dernière colonne associe la valeur de vérité de la proposition « A ∧ B ».
Il est important de bien comprendre la table de vérité de l'opérateur « ET » car il est utilisé dans de nombreux raisonnements.

Quelques exemples :
$\(A\)$ : « 5 est un nombre inférieur à 10 ET 5 est pair »
Soit $\(A'\)$ : « 5 est un nombre inférieur à 10 » $\(A'\)$ est vraie
Soit $\(A''\)$ : « 5 est pair » $\(A''\)$ est fausse
La proposition $\(A\)$ est la proposition « $\(A' \wedge A''\)$ »

D'après la table de vérité de l'opérateur binaire « ET », on en déduit que la proposition $\(A\)$ est fausse.

$\(B\)$ : « La lettre A est une voyelle et T est une consonne. »
En résonnant de même, on en déduit que la proposition $\(B\)$ est vraie.

La disjonction

Le deuxième opérateur binaire que nous allons étudier est l'opérateur « OU »
Soient A et B deux propositions.
On définit une nouvelle proposition « A OU B » que l'on note « A ∨ B » (On retourne le symbole ∧).
Cette proposition est :

  • fausse lorsque A et B sont fausses en même temps

  • vraie sinon

Autrement dit, la proposition « A ∨ B » est vraie uniquement si A ou B est vraie (ou les deux !).

Image utilisateur

Exercice 1 :
Essayez d'établir la table de vérité de cet opérateur. Prenez un petit bout de papier sur votre bureau dérangé, armez-vous d'un crayon et mettez-vous au travail !
Je vous conseille de vous inspirer de la table de vérité de l'opérateur « ET »

Correction :
Cette table se construit de la même manière que la précédente.
J’espère que vous n'avez pas eu trop de mal ! Sinon essayez de bien comprendre le fonctionnement des tables de vérité, la prochaine fois sera la bonne !

A

B

A ∨ B

1

1

1

1

0

1

0

1

1

0

0

0

Exercice 2 :
On considère une proposition A2.
A2 : « 5 est un nombre inférieur à 10 OU 5 est pair »
Quelle est la valeur de vérité de cette proposition ?

Correction :
Soit A' : « 5 est un nombre inférieur à 10 ». A' est vraie
Soit A'' : « 5 est pair ». A'' est fausse
La proposition A2 est la proposition "A' ∨ A'' »
D'après la table de vérité de l'opérateur « OU », la proposition A2 est vraie

Les opérateurs binaires « NON », « ET », et « OU » notés respectivement « ¬ » « ∧ » et « ∨ » sont les plus importants en mathématiques car ils permettent de définir tous les autres opérateurs.

Lois de Morgan

Morgan (1806-1871)

Combinons maintenant les trois opérateurs vus précédemment !
Comme toujours, on considère A et B deux propositions.

Cherchons les propositions équivalentes aux propositions P et Q telles que
P: ¬(A ∧ B)
Q: ¬(A ∨ B)

Définition :
On dit que deux propositions sont équivalentes lorsqu'elles ont les même valeurs de vérité.
On va donc une nouvelle fois utiliser les tables de vérité.

Exercice 3 :
Établissez les tables de vérité des propositions P et Q

Correction :
On commence dans les deux cas par la proposition à l’intérieur de la parenthèse, puis on réalise l'opération « NON » pour obtenir respectivement P et Q.

A

B

A ∧ B

P

1

1

1

0

1

0

0

1

0

1

0

1

0

0

0

1

De même la table de vérité de la proposition Q s'écrit :

A

B

A ∨ B

Q

1

1

1

0

1

0

1

0

0

1

1

0

0

0

0

1

J’espère que vous êtes maintenant à l'aise avec les tables de vérité ! :-°

Exercice 4 :
Établissez maintenant les tables de vérité des proposions P' et Q' telles que
P' : ¬A ∨ ¬B
Q' : ¬A ∧ ¬B
Puis comparez les valeurs de vérités de P et P' et de Q et Q'

Correction :
Vos tables doivent normalement s'être un petit peu complexifiées... mais tout ceci reste très simple !
Pour cette correction, je me suis permis de faire deux tableaux en un, voyez de vous même :

A

B

¬A

¬B

P'

P

Q'

Q

1

1

0

0

0

0

0

0

1

0

0

1

1

1

0

0

0

1

1

0

1

1

0

0

0

0

1

1

1

1

1

1

On remarque que P et P' (respectivement Q et Q') ont les même valeurs de vérité. Les propositions P et P' (respectivement Q et Q') sont donc équivalentes.

Si la proposition P est vraie alors la proposition P' est vraie.
Si la proposition P est fausse alors la proposition P' est fausse.
Si la proposition P' est vraie alors la proposition P est vraie
Si la proposition P' est fausse alors la proposition P est fausse.
De même avec Q et Q'.

Autrement dit on dira que P est P' et que Q est Q'.

Cette conclusion nous permet d'écrire les lois de Morgan :

¬(A ∧ B) équivaut à ¬A ∨ ¬B
¬(A ∨ B) équivaut à ¬A ∧ ¬B

Les lois de Morgan

Exercice 5 :
A : « Il est grand et a 15 ans ou plus. »

B : « $\((pi > 3 \land \pi \leq 2)\)$ »

Ecrivez ¬A et ¬B.

Correction :
Soit A' : « Il est grand. »
¬A' est « Il n'est pas grand. » ou bien « Il est petit. » (on considérant qu'il n'existe pas de gens moyens !)

Soit A'' : « Il a 15 ans ou plus. »
¬A'' est « Il a moins de 15 ans. » (et non pas « Il a 15 ans ou moins. ». En effet le contraire de l'opérateur supérieur ou égal est l'opérateur inférieur strict.)

La proposition A est A' ∧ A''. Donc la proposition ¬A que nous devons déterminer est ¬(A' ∧ A'')
Or d'après les lois de Morgan, ¬(A' ∧ A'') est ¬A' ∨ ¬A''
Donc ¬A est ¬A' ∨ ¬A''

Donc ¬A est « Il n'est pas grand ou a moins de 15 ans. »

En raisonnant de même, on déduit que ¬B est « $\(\pi \leq 3 \lor \pi > 2\)$ »

Avec les lois de Morgan vous êtes maintenant capable de combiner comme bon vous semble toute proposition logique en utilisant les trois opérateurs de base : ¬, ∧ et ∨ .

Ces trois opérateurs vont nous permettre de définir l'implication et l'équivalence.

Implications et équivalences

Nous voilà au coeur du sujet ! En effet les implications et les équivalences sont utilisées dans la grande majorité des démonstrations en mathématiques. Bien les comprendre permet donc d'éviter des erreurs de raisonnement dans une copie... mais aussi dans la vie !

Notion d'implication

L'implication, au même titre que l'opérateur « ET » par exemple, est un opérateur binaire (c'est à dire, rappelons le, qui lie deux propositions entre elles).

Soient deux propositions P et Q.
On note P ⇒ Q (et on lit P implique Q) la proposition qui prend les même valeurs de vérité que la proposition ¬P ∨ Q.

Un exemple

Image utilisateur

Prenons un exemple de relation d'implication : « Il pleut. » ⇒ « Le sol est mouillé. ». Cette proposition est vraie s'il suffit qu'il pleuve pour que le sol soit mouillé. Mais attention si le sol est mouillé il ne pleut pas forcément (le fleuriste peut avoir vidé un sceau d'eau sur le sol).

Il est important de bien comprendre cette notion. On suppose vraie l'implication précédente.
S'il pleut alors le sol est mouillé.
En revanche si le sol est mouillé, il est impossible de prévoir s'il pleut ou non.

Très bien, mais je ne vois pourquoi P ⇒ Q c'est la même chose que ¬P ∨ Q ?! :euh:

Je dois avouer que cette définition de l'implication n'est pas des plus intuitives.
Reprenons notre exemple précédent. Je dis : s'il pleut alors le sol est mouillé, cela veut dire bien qu'il est impossible qu'il pleuve et que le sol ne soit pas mouillé.
En formalisant on obtient ¬(« Il pleut. » ∧ ¬ « Le sol est mouillé. »). Et d'après les lois de Morgan
¬« Il pleut. » ∨ ¬¬« Le sol est mouillé. », c'est à dire ¬« Il pleut. » ∨ « Le sol est mouillé. »

On retrouve bien que P⇒Q a les mêmes valeurs de vérité que ¬P ∨ Q

Ce n'est peut-être pas encore clair dans votre esprit alors prenons un autre exemple.
On considère vraie la proposition : « Si je suis fatigué, je vais me reposer. »
C'est à dire que « Je suis fatigué. » ⇒ « Je vais me reposer. »
Cela veut bien dire que « Je ne suis pas fatigué. » ou « Je vais me reposer. »

Table de vérité

Exercice 6:
Après avoir encore un petit peu cogité cette notion, je vous laisse construire la table de vérité de l'implication.

Correction :

P

Q

¬P

P ⇒ Q

1

1

0

1

1

0

0

0

0

1

1

1

0

0

1

1

Remarque :
Si P est fausse, P ⇒ Q est est vraie.

Plusieurs formulations pour une même notion

P ⇒ Q se lit aussi :

  • Si P alors Q

  • Il suffit que P pour que Q

  • Il est nécessaire que Q pour que P

  • Il faut que Q pour que P

Ainsi, à chaque fois que vous entendez dans le langage courant l'une des formulations précédente, c'est en fait une implications entre deux propositions.

Exemple :
« Il suffit qu'il soit là pour que je sois joyeux(se). » correspond à « Il est là » ⇒ « Je suis joyeux(se) »

Syllogisme

Socrate (470 av. J-C — 399 av. J-C)

On peut d'ores et déjà utiliser nos connaissances sur l'implication pour construire un raisonnement appelé syllogisme. peut d'ores et déjà utiliser nos connaissances sur l'implication pour construire un raisonnement appelé syllogisme.

Soient P et Q deux propositions.
Pour montrer que Q est vraie, on utilise la règle suivante :
Si P est vraie et si P ⇒ Q est vraie, alors Q est vraie.

Je ne vois pas bien d'où tu sors ce raisonnement miracle ?!

De la table de vérité de l'implication pardi !
Je vous la rappelle juste ici :

P

Q

¬P

P ⇒ Q

1

1

0

1

1

0

0

0

0

1

1

1

0

0

1

1

On remarque que les conditions initiales (P est vraie et P ⇒ Q est vraie) correspondent à la première ligne. Or sur cette ligne Q est aussi vraie. Ce qui prouve que notre raisonnement est correct.

Exemple :
Socrate est un homme.
Tous les hommes sont mortels. (C'est à dire « Être un homme. » ⇒ « Être mortel. »)
Donc Socrate est mortel.

Vous le voyez, le syllogisme est un raisonnement plutôt intuitif.
Il était souvent utilisé par les grecs de l'antiquité, d'où l'exemple de Socrate. (en savoir plus sur Wikipédia)

Implication réciproque

Encore un petit quelque chose. P et Q sont toujours deux propositions.
La proposition Q ⇒ P est appelée l'implication réciproque de la proposition P ⇒ Q.
Retenez cette expression, on va s'en resservir dans deux lignes !

Equivalence

Définition, table de vérité

Le symbole de l'équivalence est ⇔. Une double flèche qui n'est pas sans rappeler la flèche de l'implication vue juste au dessus.
On dit que la proposition P ⇔ Q est vraie (et on lit P équivaut à Q ou P si et seulement si Q) quand l'implication P ⇒ Q et l'implication réciproque Q ⇒ P sont vérifiées en même temps.

Donc P ⇔ Q est (P ⇒ Q) ∧ (Q ⇒ P).

Exercice 7 :
Je vous laisse trouver la table de vérité de l'équivalence (Courage, c'est la dernière !).

Correction :

P

Q

¬P

¬Q

P ⇒ Q

Q ⇒ P

P ⇔ Q

1

1

0

0

1

1

1

1

0

0

1

0

1

0

0

1

1

0

1

0

0

0

0

1

1

1

1

1

On remarque que l'équivalence entre P et Q est vraie lorsque P et Q ont la même valeur de vérité (toutes deux vraies, ou toutes deux fausses).

Pour démontrer une équivalence, on utilise souvent a règle de la double implication :

  • on démontre dans un premier temps une implication

  • puis dans un second temps on démontre l'implication réciproque

On en déduit que l'équivalence est vérifiée.

Exemples

Vous êtes maintenant capable de comprendre et de justifier de nombreuses propriétés mathématiques.
Voici quelques exemples :

A, B et C sont trois propositions
$\(A \Leftrightarrow A\)$ (Évident, c'est le principe d'identité, que l'on a évoqué au début de ce cours)
$\(\lnot \lnot A \Leftrightarrow A\)$  (Principe du tiers exclus, aussi évoqué au début de ce cours)
$\((A \Leftrightarrow B) \Leftrightarrow (B \Leftrightarrow A)\)$ (On dit que l'équivalence est symétrique)
$\((A \Leftrightarrow B) \land (B \Leftrightarrow C) \Rightarrow (A \Leftrightarrow C)\)$ (On dit que l'équivalence est transitive)

Exercice 8 :

Remplacez dans chaque expression le symbole $\(\star\)$ par l'un des opérateurs suivants : $\(\Rightarrow\)$, $\(\Leftarrow\)$ ou $\(\Leftrightarrow\)$.

A, B et C sont trois points du plan.

x, y et z sont trois nombres réels.

$\(P : ABC \text{ est isocèle en } A \star AB = AC\)$ 
$\(Q : x > 0 \star x > 5\)$ 
$\(R : x = 3 \star x^2 = 9\)$ 
$\(S : x + z = y + z \star x = y\)$ 
$\(T : x \times z = y \times z \star x = y\)$ 

Correction :

P : ABC est isocèle en $\(A \Leftrightarrow AB = AC\)$ 
$\(Q : x > 0 \Leftarrow x > 5\)$ 
$\(R : x = 3 \Rightarrow x^2 = 9\)$ 
$\(S : x + z = y + z \Leftrightarrow x = y\)$ 
$\(T : x \times z = y \times z \Leftarrow x = y\)$  (L'implication réciproque est fausse pour z = 0)

Quantificateurs

Soit P la proposition « 8 est un nombre pair ». On peut remplacer le nombre 8 par un autre nombre quelconque afin de former de nouvelles propositions. On pourra par exemple écrire la proposition P(6) « 6 est un nombre pair » qui est vraie, ou la proposition P(3) « 3 est un nombre pair » qui est fausse.
On écrira alors la forme générale de cette proposition P(x) : « x est un nombre pair », x est appelé argument de la proposition P. La valeur de vérité de la proposition P(x) dépend de x.

Le problème est que je ne sais pas ce qu'est x dans la proposition P(x). Dans notre exemple, x est un nombre il faut le préciser car sinon notre proposition n'a pas de sens (par exemple P(ABC) : « le triangle ABC est un nombre pair » n'a pas de sens).

On a donc inventé des quantificateurs pour indiquer que l'on prend notre x parmi un ensemble déterminé.

Le quantificateur universel

On note « pour tout x élément de Ω, la proposition P(x) est vraie » ainsi « $\(\forall x \in \Omega, P(x)\)$ ».

Oulà ! C'est quoi tous ces symboles ?!

Du calme, du calme. On s'habitue rapidement à lire les quelques symboles mathématiques.

  • Le symbole ∀ (un A retourné) se lit "quel que soit". C'est un quantificateur, il indique que la propriété est vraie pour tous les objets satisfaisants la condition qui suit.

  • x est un objet mathématique (un nombre, un point, un vecteur...).

  • Le symbole ∈ signifie « appartient à ». C'est un opérateur qui permet de dire que x appartient à un ensemble précisé.

  • Ω est un ensemble d'objets. Par exemple le plan qui est un ensemble de points, ou bien l'ensemble R qui est l'ensemble des nombre réels.

Exemple 1 :
On nomme $\(\mathbb{A}\)$ l'ensemble des élèves d'une classe.
On note P(x) : « x est présent » (x est un élève de la classe)

La proposition Q : « Tous les élèves de la classe sont présents » s'écrit alors $\(\forall x \in \mathbb{A},P(x)\)$ 

Exemple 2 :
On nomme $\(\mathbb{R}\)$ l'ensemble des nombres réels.

La proposition Q' : « Le carré d'un nombre réel est toujours positif » s'écrit alors $\(\forall x \in \mathbb{R}, x^2 \geq 0\)$ 

Exercice 9 :
Traduire la proposition sous sa forme mathématique équivalente (en utilisant le quantificateur et le connecteur logique adéquat).
P : « Pour tout x nombre réel, il suffit que x soit supérieur ou égal à 5 pour que x² soit supérieur ou égal à 25 »

Correction :
La formulation « il suffit que P soit vraie pour que Q soit vraie » se traduit par P ⇒ Q
Cette équivalence est vraie pour tout x nombre réel, on utilise donc le quantificateur ∀.

La proposition P s'écrit donc $\(\forall x \in \mathbb{R}, x \ge 5 \Rightarrow x^2 \ge 25\)$.

Le quantificateur existenciel

Image utilisateur

Reprenons notre premier exemple.
La proposition Q : « Tous les élèves de la classe sont présents ». Essayez de déterminer ¬Q (dans une phrase française).
Attention ! Il y a un piège !
Le contraire de « Tous les élèves de la classe sont présents » n'est pas « Tous les élèves de la classe sont absents » !
En effet, il suffit qu'un seul élève soit absent pour que la proposition Q soit fausse.
On dira donc que la proposition contraire de Q est « Au moins un élève de la classe est absent »

Il nous faut un autre quantificateur pour traduire « il existe au moins un ».
On pourrait noter ce quantificateur ¬∀, car il est simplement la négation du quantificateur universel. Mais pour simplifier la notation, on utilisera le symbole ∃ (un E à l'envers).

∃ s'utilise exactement de la même façon que ∀.

Exemple :

P : « $\(\exists x \in \mathbb{R}, x^2 = 1\)$ »
La proposition P se lit « Il existe au moins un nombre réel x dont le carré est égal à 1. ».
Voyez comme la notation mathématiques est plus pratique !

Plusieurs quantificateurs

On peut utiliser deux quantificateurs (ou plus) dans une même proposition. Dans ce cas l'ordre des quantificateurs est important.

Exercice 10 :
Traduisez en français les proposition P et Q et donnez leur valeur de vérité :

Traduisez en français les proposition P et Q et donnez leur valeur de vérité :
$\(P : \forall x \in \mathbb{N}, \exists y \in \mathbb{N}, x < y\)$ 
$\(Q : \exists y \in \mathbb{N}, \forall x \in \mathbb{N}, x < y\)$ 

Correction : La proposition P signifie « Pour tout entier naturel x, il existe un entier naturel y strictement supérieur à x. »
La proposition P est vraie (d'après le second axiome de Peano)

La proposition Q signifie « Il existe un entier naturel strictement inférieur à tous les entiers naturels »
La proposition Q est fausse. Pour le prouver, on peut utiliser un contre exemple. En effet il n'existe aucun entier naturel strictement inférieur à 0. (d'après le troisième axiome de Peano)

En savoir plus sur les axiomes de Peano (Wikipédia)

Ces deux propositions si proches en apparence n'ont donc absolument rien à voir !
Retenez donc que changer la nature ou l'ordre des quantificateurs change le sens de la proposition.

Raisonnons !

Nous avons maintenant tous les outils en main pour réaliser des raisonnements mathématiques complets.
Un raisonnement permet d'établir une proposition à partir d'une ou de plusieurs propositions initiales admises (ou précédemment démontrées) en suivant les règles de la logique.
Nous allons dans cette dernière partie détailler quatre "types" de raisonnement, quatre "méthodes" pour démontrer une proposition :

  • Trouver un exemple ou un contre-exemple

  • Démontrer la contraposée

  • Raisonner par l'absurde

  • Raisonner par récurrence

Ces différentes formes de raisonnements devront s'appliquer dans des cas bien particuliers.

Exemple et contre exemple

Pour montrer qu'une proposition de la forme $\(\exists x \in \Omega , P(x)\)$ est vraie, on cherche un x pour lequel P(x) est vraie. C'est donner un exemple.

Exercice 11 :
P : « $\(\exists x \in \mathbb{N}, \exists y \in \mathbb{N}, \exists z \in \mathbb{N}, x^2 = y^2 + z^2\)$ »
Démontrez que P est vraie.

Correction :
Soient x = 5, y = 4, z = 3.
x, y et z vérifient x² = y² + z² (car 25 = 16 + 9)

Donc la proposition P est vraie.

Pour montrer qu'une proposition de la forme $\(\forall x \in \Omega / P(x)\)$ est fausse, on montre que sa négation$\(\exists x \in \Omega / \lnot P(x)\)$) est vraie. C'est donner un contre-exemple.

Exercice 12 :
Soit P la proposition «$\(\forall n \in \mathbb{N}, n^2 + 1 \text{ est un nombre premier}\)$ »
Démontrez que P est fausse.

Correction :
Pour démontrer que P est fausse on va montrer que ¬P est vraie.
¬P est la proposition $\(\exists n \in \mathbb{N}, n^2 + 1 \text{ n'est pas un nombre premier}\)$ 

Soit n=3.
n² + 1 = 10
10 n'est pas un nombre premier.

Donc la proposition P est fausse.

La contraposée

J’espère que vous vous souvenez de la table de vérité de l'implication ! Comment ça non ?! :o Je vous laisse la retrouver (dans votre esprit si possible sinon plus haut sur cette page) avant de passer à l'exercice suivant...

Exercice 13 :
Soient P et Q deux propositions.
Montrer que P ⇒ Q équivaut à ¬Q ⇒ ¬P

Correction :
Vous l'avez deviné, on utilise une nouvelle fois une table de vérité pour justifier cette équivalence.

P

Q

¬P

¬Q

P ⇒ Q

¬Q ⇒ ¬P

1

1

0

0

1

1

1

0

0

1

0

0

0

1

1

0

1

1

0

0

1

1

1

1

Donc P ⇒ Q équivaut à ¬Q ⇒ ¬P.

Définition :
La proposition ¬Q ⇒ ¬P est appelée proposition contraposée de la proposition P ⇒ Q.

Une proposition et sa contraposée sont équivalentes, ce qui signifie que l'on peut démontrer l'une pour démontrer l'autre. On souhaite par exemple montrer que P ⇒ Q. Le raisonnement par contraposée consiste à prouver que ¬Q ⇒ ¬P.

Exemple :
Pour démontrer que « S'il pleut, alors le sol est mouillé », je vais démontrer que « Si le sol n'est pas mouillé, alors il ne pleut pas ».

Exercice 14 :
Démontrez la proposition $\(P: \forall n \in \mathbb{N}\)$, si $\(n^2\)$ est pair, alors $\(n\)$ est pair.

Correction :

On réalise cette démonstration par contraposition. Ainsi plutôt que de montrer que si $\(n^2\)$ est pair, alors $\(n\)$ est pair. Nous allons montrer que si $\(n\)$ est impair alors $\(n^2\)$ est impair.

$\(n \text{ est impair} \Rightarrow \exists k \in \mathbb{Z}, n = 2k + 1\)$  (d'après l'indication)

$\(n\text{ est impair} \Rightarrow \exists k \in \mathbb{Z}, n^2 = (2k + 1)^2\)$  (on élève au carré)

$\(n \text{ est impair} \Rightarrow \exists k \in \mathbb{Z}, n^2 = 4k^2 + 4k + 1\)$‌   (on développe)

$\(n \text{ est impair} \Rightarrow \exists k \in \mathbb{Z}, n^2 = 2(k^2 + k) + 1\)$  (on factorise)

$\(n \text{ est impair} \Rightarrow \exists m \in \mathbb{Z}, n^2 = 2m + 1\)$  (k est un entier relatif, donc k² + k est aussi un entier relatif)

$\(n \text{ est impair} \Rightarrow n^2 \text{ est impair}\)$ (d'après l'indication)

$\(n^2 \text{ est pair} \Rightarrow n \text{ est pair}\)$  (par contraposition)

On obtient le résultat demandé.

Le raisonnement par l'absurde

Image utilisateur

À quoi bon mettre de l'absurdité dans un raisonnement logique ?!

Drôle d'idée en effet ! Mais rassurez-vous, le raisonnement par l'absurde (comme son nom ne l'indique pas) n'a rien d'absurde. Il est même tout ce qu'il y a de plus logique ! :-°

Ce raisonnement repose sur le principe du Tiers-exclus, à savoir que si une proposition n'est pas fausse, alors elle est vraie.

Imaginons par exemple que vous savez que quelque chose est vrai, mais vous ne savez pas le démontrer. En raisonnant par l'absurde vous allez commencer par admettre par hypothèse que cette chose est fausse. Puis en suivant les règles de la logique vous allez développer les conséquences de cette hypothèse et aboutir à une contradiction irréfutable (comme 1 = 2, ou 2 et 4 sont premiers entre eux). Vous allez en déduire que votre hypothèse de départ est nécessairement fausse, c'est à dire que la chose que vous vouliez démontrer n'est pas fausse, donc qu'elle est vraie.

Définition :
Le raisonnement par l'absurde est une forme de raisonnement logique. Il consiste

  • soit à démontrer qu'une proposition A est vraie en prouvant l'absurdité de la proposition ¬A

  • soit à démontrer qu'une proposition A est fausse en déduisants logiquement des conséquences absurdes

Voyons maintenant le raisonnement par l'absurde dans toute sa splendeur à travers l'un de ses exemples les plus classiques : l'irrationnalité de $\(\sqrt{2}\)$

Exemple

On souhaite démontrer que la proposition P est vraie.

$\(P : « \sqrt{2} \text{ est un nombre irrationnel } »\)$ 

On raisonne par l'absurde. On va donc montrer que la proposition ¬P est absurde.
¬P se traduit par « $\(\sqrt{2} \text{ est un nombre rationnel }\)$ »

$\(\sqrt{2}\)$ est rationnel, il peut se mettre sous la forme d'une fraction.
C'est à dire$\(\exists a \in \mathbb{Z}, \exists b \in \mathbb{Z}, \sqrt{2}=\frac{a}{b}\)$ avec a et b premiers entre eux.
On simplifie cette égalité :

$\(\exists a \in \mathbb{Z}, \exists b \in \mathbb{Z}, 2=\frac{a^2}{b^2}\)$ (on élève au carré)

$\(\exists a \in \mathbb{Z}, \exists b \in \mathbb{Z}, 2b^$$2=a^2\)$ (par produit de b²)

Donc a² est pair, donc a est pair (cf. démonstration par contraposée du paragraphe précédent)

Donc $\(\exists k \in \mathbb{Z}, a=2k\)$ (propriété vue précédemment)
En remplaçant dans l'égalité précédente, on obtient $\(\exists a \in \mathbb{Z},\exists k \in \mathbb{Z}, 2b^2=(2k)^2\exists a \in \mathbb{Z},\exists k \in \mathbb{Z}, 2b^2=4k^2\exists a \in \mathbb{Z}, \exists k \in \mathbb{Z}, b^2=2k^2\)$.

Donc b² est pair, donc b est pair ce qui est impossible car a est pair et que a et b sont premiers entre eux.
On aboutit à une contradiction.
Donc la proposition ¬P est fausse.

Donc $\(\sqrt{2} \text{ est un nombre irrationnel }\)$

Dans le cas où la proposition à démontrer est de la forme P ⇒ Q, raisonner par l'absurde consiste à démontrer que la proposition P ∧ ¬Q est fausse. Pour se faire, on suppose que P est vraie et que Q est fausse, on développe les conséquences et on montre que l'on arrive à une contradiction.

Exercice 15 :
Démontrez que si vous rangez (n+1) pulls dans $\(n\)$ tiroirs distincts, alors il y a au moins un tiroir contenant 2 pulls.

Correction :
On résonne par l'absurde.

Supposons qu'il n'y a aucun tiroir contenant 2 pulls ou plus.
Cela signifie que tous les tiroirs contiennent soit 1 pull soit 0 pull.

Il faudrait donc au minimum n+1 tiroirs pour ranger n+1 pulls.
Ce qui est absurde puisque l'on ne dispose que de n tiroirs.

Donc il y a au moins un tiroir contenant 2 pulls.

Exercice 16 :

Montrez en utilisant un raisonnement par l'absurde que $\(\forall n \in \mathbb{N}, n^2 \text{ est pair} \Rightarrow n \text{ est pair}\)$

Correction :
Il faut montrer que « n² est pair » ET « n est impair » aboutit à une contradiction.
Soit n² un nombre pair.

On suppose que n n'est pas pair, c'est à dire n est impair.

Donc $\(\exists k' \in \mathbb{Z}, n = 2k' + 1\)$ 

Or n² est pair, donc $\(\exists k \in \mathbb{Z}, n^2 = 2k\)$ 

Or $\(k' \in \mathbb{Z}\text{, donc } (k'^2 + k') \in \mathbb{Z}\)$
Donc $\(2(k'^2 + k') + \frac{1}{2} \notin \mathbb{Z}\)$
Donc $\(k \notin \mathbb{Z}\)$
Or par définition, $\(k \in \mathbb{Z}\)$

D'où contradiction.
Donc l’hypothèse de départ est fausse.

Donc $\(\forall n \in \mathbb{N}, n^2 \text{ est pair} \Rightarrow n \text{ est pair}\)$

Cet exercice nous a permis de voir que plusieurs méthodes différentes permettaient de démontrer une même propriété (ici en utilisant soit la contraposée, soit un raisonnement par l'absurde).

Le raisonnement par récurrence

Permettez-moi un petit exemple d'introduction.

Monsieur Pognon est un entrepreneur un peu particulier, il a lancé il y a peu un nouveau forfait téléphonique aux tarifications alléchantes.
Sur le site internet qui présente l'offre, on peut lire :

« Les appels sont facturés à la minute.
Le prix d'un appel correspond au prix de la dernière minute.
Le prix d'une minute correspond au double du prix de la précédente minute augmentée d'un centime.
Ainsi un appel d'une minute ne vous coûtera que 0,01 € (2 × 0 + 0,01)
Un appel de deux minutes ne vous coûtera que 0,03 € (2 × 0,01 + 0,01)
Un appel de trois minutes ne vous coûtera que 0,07 € (2 × 0,03 + 0,01)
Et ainsi de suite... »

Les tarifications de M. Pognon
Les tarifications de M. Pognon

Hum. Je ne sais pas vous, mais j'ai comme l'impression que cette tarification attractive (quoique un peu obscure) cache une belle arnaque...

Pour en avoir le coeur net je vous propose de trouver une formule donnant le prix d'un appel d'une durée quelconque (sans avoir à multiplier le prix de la minute précédente par deux et ajouter un centime). Ceci s’avérera bien pratique pour calculer le prix d'un appel de 15 minutes, d'une heure, et pourquoi pas plus !

On note $\(u_n\)$ le prix en centimes d'un appel de $\(n\)$ minutes.
D'après le site internet de l'offre, on a donc :

$\[u_1 = 1u_2 = 2 \times u_1 + 1 = 3u_3 = 2 \times u_2 + 1 = 7u_4 = 2 \times u_3 + 1 = 15u_5 = 2 \times u_4 + 1 = 31\]$

Tiens, il y a comme une logique dans cette suite de nombres. En effet il semble qu'en ajoutant 1 à chaque valeur, on obtient les puissances successives de 2 :

$\[u_1 + 1 = 1 + 1 = 2 = 2^1u_2 + 1 = 3 + 1 = 4 = 2^2u_3 + 1 = 7 + 1 = 8 = 2^3u_4 + 1 = 15 + 1 = 16 = 2^4u_5 + 1 = 31 + 1 = 32 = 2^5\]$

 

Nous allons supposer que cette propriété est vraie pour tout n. Cette remarque se formalise alors de la sorte : $\(\forall n \in \mathbb{N}, u_n + 1 = 2^n\)$ 

Ce qui nous permet d'exprimer $\(u_n\)$ uniquement en fonction de $\(n\)$ : $\(\forall n \in \mathbb{N}, u_n = 2^n - 1\)$.
Nous pouvons donc maintenant calculer de manière simple le prix d'un appel de 15, 60 ou 180 minutes !

Mais attends, ce n'est pas parce que cette propriété est vraie pour n=0, n=1, n=2, n=3, n=4 et n=5 qu'elle est aussi vraie pour n=180 !
Ceci n'est pas une démonstration !

Bonne remarque ;)
C'est à ce moment qu'intervient le raisonnement par récurrence.

On considère la propriété $\(P(n): \forall n \in \mathbb{N}, u_n = 2^n -1\)$.

On va supposer, par hypothèse, que pour un certain $\(n\)$ la propriété $\(P(n)\)$ est vraie.
On calcule alors $\(u_{(n+1)}\)$.

$\(u_{n+1} = 2 \times u_n + 1\)$ (Par définition)

$\(u_{n+1} = 2 \times (2^n - 1) + 1\)$ (Par hypothèse)

$\(u_{n+1} = 2^{n+1} - 2 + 1u_{n+1} = 2^{n+1} - 1\)$ c'est à dire $\(P(n+1)\)$ est vraie.

Nous venons de démontrer que si $\(P(n)\)$ est vraie, alors $\(P(n+1)\)$ est vraie.

Or P(0) est vraie. Donc P(1) est vraie. Donc P(2) est vraie. Donc P(3) est vraie. [...] Donc P(200) est vraie.
La propriété est donc vraie pour tout n entier naturel (C'est ce que l'on appelle le principe de récurrence).

Image utilisateur

Nous pouvons maintenant calculer le prix d'un appel de 15 minutes :
$\(u_{15} = 2^{15} - 1 = 32767\)$
Un appel de quinze minutes coûte donc 327, 67€ ! Je vous laisse imaginer calculer pour un appel d'une heure ou plus !

Définition :
Un raisonnement par récurrence permet de montrer qu'une propriété est vraie ou qu'elle est fausse pour tous les entiers à partir d'un certain "rang".

La forme générale des propriétés que nous allons démontrer par récurrence est :

$\(\forall n \in \mathbb{N})_{n \geq k}, P(n)\)$

Pour se faire il faudra démontrer les deux points si dessous :

$\(P(k)\)$ 

  • C'est l'initialisation. On montre que la propriété est vérifiée au rang k.

$\((\forall n \in \mathbb{N})_{n \geq k}, P(n) \Rightarrow P(n+1)\)$ 

  • C'est l'hérédité. On montre que si la propriété est vraie au rang n, alors elle est vraie au rang n+1. (On montre une implication)

Pour terminer la démonstration, il suffit alors d'indiquer que d'après le principe de récurrence, ces deux conditions prouvent la propriété $\((\forall n \in \mathbb{N})_{n \geq k},P(n)\)$.

Voici une illustration visuelle d'un raisonnement par récurrence :
Étape 1 : on montre que le premier domino tombe (k=1).
Étape 2 : on montre que la chute du domino n entraine la chute du domino n+1.
Étape 3 : on en déduit que tous les dominos tombent.

Image utilisateur

Le principe de récurrence

L'image des dominos ne doit pas vous poser de problème, et en maths ça donne quoi ?

Exemple :
Montrons que $\(\forall n \in \mathbb{N}^*, \sum_{p = 1}^{n} p = \frac{n(n+1)}{2}\)$

Pas de panique, ne vous laissez pas inquiéter par tous ces symboles mathématiques ! Il suffit de suivre les 3 étapes du raisonnement.

Étape 1 : Initialisation
Montrons que la propriété est vraie pour n=1.
On calcule séparément les deux termes de l'égalité.

$\(\sum_{p = 1}^{n} p = \sum_{p = 1}^{1} p = 1\)$ 

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

Donc l'égalité est vérifiée au rang n=1.

Étape 2 : Hérédi

On suppose que pour un certain n, $\(\sum_{p = 1}^{n} p = \frac{n(n+1)}{2}\)$ (c'est à dire que n vérifie notre égalité).
Montrons alors que $\(\sum_{p = 1}^{n+1} p = \frac{(n+1)(n+2)}{2}\)$ (c'est-à-dire que n+1 vérifie notre égalité).

Pour écrire la deuxième expression, il suffit de substituer n+1 à n dans la première expression.

Puis, on démontre l'égalité :

$\(\sum_{p = 1}^{n+1} p = \sum_{p = 1}^{n} p + (n+1)\)$ (d'après la définition de la somme)
$\(\sum_{p = 1}^{n+1} p = \frac{n(n+1)}{2} + (n+1)\)$(par hypothèse de récurrence)

$\(\sum_{p= 1}^{n+1} p = \frac{n(n+1)+2(n+1)}{2}\sum_{p= 1}^{n+1} p = \frac{(n+1)(n+2)}{2}\)$(on factorise) 

On obtient bien l'égalité demandée.

On en déduit que si n vérifie l'égalité, alors n+1 vérifie aussi l'égalité.

Étape 3 : Conclusion
On conclue que d'après le principe de récurrence, l'égalité est vérifiée pour tous les n différents de 0.

C'est à dire$\(\forall n \in \mathbb{N}^*\)$$\(\sum_{p = 1}^{n} p = \frac{n(n+1)}{2}\)$ 

Oui, c'est maousse costaud ! :-°
Je vous conseille de relire plusieurs fois cet exemple pour bien comprendre la démarche de résolution. Puis, c'est à vous de jouer !

Exercice 17 :

Démontrez par récurrence que $\(\forall n \in \mathbb{N}^* \sum_{p = 1}^{n} (2p - 1) = n^2\)$.

Correction :
Initialisation : pour n=1

$\(\sum_{p = 1}^{n} (2p - 1) = (2 \times 1 - 1) = 1\)$ 

$\(n^2 = 1^2 = 1\)$ 

Donc l'égalité est vérifiée pour n=1.

Hérédité :

On suppose que pour un certain n, $\(\sum_{p = 1}^{n} (2p - 1) = n^2\)$ 
Montrons alors que $\(\sum_{p = 1}^{n+1} (2p - 1) = (n+1)^2\)$ 

$\(\sum_{p = 1}^{n+1} (2p - 1) = \sum_{p = 1}^{n} (2p - 1) + 2(n+1) - 1\)$ (d'après la définition de la somme)
$\(\sum_{p = 1}^{n+1} (2p - 1) = \sum_{p = 1}^{n} (2p - 1) + 2n + 1\)$ (On développe)
$\(\sum_{p = 1}^{n+1} (2p - 1) = n^2 + 2n + 1\)$ (Par hypothèse de récurrence)
$\(\sum_{p = 1}^{n+1} (2p - 1) = (n+1)^2\)$ (On factorise)

On obtient l'égalité demandée.

Conclusion : d'après le principe de récurrence, $\(\forall n \in \mathbb{N}^*, \sum_{p = 1}^{n} (2p - 1) = n^2\)$ 

Vous voilà maintenant initiés aux bases de la logique mathématique ! Si vous souaitez approfondir ce sujet, il exite plusieurs systèmes de logique

  • Logique combinatoire

  • Logique floue

  • Logique intuitionniste (rejet de la règle ¬¬A ⇒ A ce qui rend par exemple impossible un raisonnement par l'absurde)

  • Logique substructurale

  • etc.

N’hésitez pas à poser toutes vos questions dans les commentaires du tutoriel, j'y répondrai avec grand plaisir.

À bientôt ^^

Exemple de certificat de réussite
Exemple de certificat de réussite