Introduction à la logique mathématique Online

À 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 !

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.

$\(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\)$.

On utilise ici un contre exemple pour prouver que la proposition $\(C'\)$ est fausse.
Ce type de raisonnement sera approfondi dans la dernière partie.

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).

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 ».

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.

Pour ceux qui font de la programmation, l'opérateur « NON » (noté ¬ en maths) est souvent noté « ! » en informatique.

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

Il est important de bien comprendre comment construire une table de vérité, nous nous en servirons de nombreuses fois dans ce cours.

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).

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

En informatique cet opérateur est souvent noté &&.

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.

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 !).

En informatique, on utilise souvent la notation ||.

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.

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