La logique

Logique de 1er ordre

Déjà en 1879, le mathématicien allemand Gottlob Frege avait bouleversé la logique qui semblait immuable depuis Aristote. Mais à partir de 1884, année de parution des Fondements de l’arithmétique, suivi des deux volumes des Lois fondamentales de l’arithmétique, il montra que l’ensemble des mathématiques ne pouvait reposer que sur la logique et non sur la géométrie comme on le pensait à la suite d’Euclide. Révolutionnaire.

Si les règles de logique sont aujourd’hui enseignées, c’est souvent pour conduire à l’algèbre de Boole puis à ses applications en informatique.

Pour vous initier, c’est par ici…

 

Logique mathématique du premier ordre

La logique du premier ordre, ou logique des prédicats, comprend les connecteurs classiques tels que la négation, le caractère conjonctif (et), le disjonctif (ou), l’implication (si… alors) et l’équivalence (si et seulement si).

Une proposition mathématique est soit vraie soit fausse. Par exemple, \(2 + 5 = 7\) est une proposition vraie.

 

Symboles

Une proposition est notée avec une lettre majuscule : \(A,\) \(B,\) \(C…\) Les symboles à connaître sont les suivants :

Non \(\neg\)
Implique \(\to\)
Équivalent à \(\leftrightarrow\)
Et \(\wedge\)
Ou \(\lor\)

Notez que le « ou » est inclusif. L’exclusif (XOR) ne sera pas vu ici.

 

Tables de vérité

La plus simple : si une proposition \(A\) est vraie, alors « non \(A\) » est fausse et inversement.

\(A\) \(\neg A\)
V F
F V

Désormais, non utiliserons 1 pour « vrai » et 0 pour « faux ».

\(A\) \(B\) \(A \wedge B\)
1 1 1
1 0 0
0 1 0
0 0 0

\(A\) \(B\) \(A \lor B\)
1 1 1
1 0 1
0 1 1
0 0 0

Jusqu’ici les choses sont très simples. Elles doivent vous rappeler votre découverte des probabilités (voir la page d'initiation aux probabilités).

\(A\) \(B\) \(A \to B\)
1 1 1
1 0 0
0 1 1
0 0 1

\(A\) \(B\) \(A \leftrightarrow B\)
1 1 1
1 0 0
0 1 0
0 0 1

Nous n’irons pas plus loin dans la théorie. Démontrons que si \(A\) implique \(B\) et \(B\) implique \(A\) alors \(A\) est équivalent à \(B.\) En d’autres termes, \(A\) est une condition nécessaire et suffisante pour \(B.\)

\(A\) \(B\) \(A \to B\) \(B \to A\) \((A \to B) \wedge (B \to A)\) \(A \leftrightarrow B\)
1 1 1 1 1 1
1 0 0 1 0 0
0 1 1 0 0 0
0 0 1 1 1 1

Les deux dernières colonnes sont identiques. La démonstration est faite.

 

Exercices

  1. Démontrer que \((A \to B) \iff (\neg A \lor B)\)
  2. Donner la table de vérité de l’implication \([A \wedge (A \to B)] \to B.\)

Corrigés

1- Table de vérité

\(A\) \(B\) \(A \to B\) \(\neg A\) \(\neg A \lor B\)
1 1 1 0 1
1 0 0 0 0
0 1 1 1 1
0 0 1 1 1

Les colonnes 3 et 5 sont identiques. La démonstration est faite (on peut aussi ajouter une sixième colonne avec pour intitulé l’équivalence de l’énoncé et ne comportant que des 1).

2- Table de vérité

\(A\) \(B\) \(A \to B\) \(A \wedge (A \to B)\) \([A \wedge (a \to B)] \to B\)
1 1 1 1 1
1 0 0 0 1
0 1 1 0 1
0 0 1 0 1

 

Fonction propositionnelle

Et voici l’occasion de retrouver les quantificateurs !

\(P(x)\) est une fonction propositionnelle, avec \(x\) appartenant à un ensemble \(E.\)

  • \(\forall x, x \in A, P(x)\) est vraie si \(P(x)\) est vraie pour toutes les valeurs de \(X\) et fausse pour au moins une valeur de \(x.\)

  • \(\exists x, x \in A, P(x)\) est vraie s’il existe au moins une valeur de \(x\) pour laquelle \(P(x)\) est vraie et fausse si \(P(x)\) est fausse pour toutes les valeurs de \(x.\)