Logique mathématique - Définition

Quelques systèmes déductifs

• Les systèmes à la Hilbert ;
• La déduction naturelle ;
• Le calcul des séquents ;

Le calcul des prédicats

Substitution

Il est également possible de construire à partir d’une proposition P, d’autres propositions en remplaçant un objet mathématique indéterminé x dans la proposition partout où il intervient, par un autre objet mathématique a.

Par exemple, la proposition P : « 8 est un nombre pair », peut être représentée sous la forme P{8}, où P est le prédicat « est un nombre pair », et 8 est son argument.
Ou par exemple, la proposition « Les droites D et D’ sont parallèles » peut être représentée sous la forme P{D, D’} où P est le prédicat « sont parallèles » et les droites D et D’ sont les arguments.

Si P est une proposition, x un objet indéterminé, et a un objet mathématique, l’assemblage obtenu en remplaçant x par a dans P est encore une proposition notée

(a|x)P

et s’appelle proposition obtenue par substitution de x par a dans P.

Pour mettre en évidence un objet indéterminé x dans une proposition P, on écrit la proposition sous la forme P{x} ; et on note P{a} la proposition (a|x)P.

Soit P une proposition, x un objet indéterminé, et a un objet mathématique donné. Si P est vraie, alors P{a} est vraie.

Et tout cela se généralise au cas de plusieurs objets indéterminés.

Les quantificateurs

Il existe encore un autre procédé logique, permettant de construire d’autres propositions à partir d’une proposition.

Soit une proposition P et x un objet indéterminé. Nous pouvons considérer la proposition :

il existe un objet a, tel que (a|x)P soit vraie

c'est-à-dire

il existe un objet a, tel que P{a} soit vraie

« il existe un objet » signifie intuitivement « nous pouvons trouver au moins un objet ».

Symboliquement, nous écrivons :

∃ a P

ou

∃ a P{a}

ce qui se lit :

« il existe a tel que P »

Ce signe ∃ s’appelle le quantificateur existentiel.

Nous définissons, à partir de ∃ le symbole ∀  :

Soit P une proposition et x un objet indéterminé, la proposition notée ∀ x P est la proposition

¬( ∃x ¬P )

et se lit « pour tout x, P »
ou « quel que soit x, on a P vraie »

∀ s’appelle le quantificateur universel.

Évidemment, la proposition (∀ x P) est fausse si et seulement si (∃ x ¬ P) est vraie.

Utilisation des quantificateurs

Propriétés élémentaires

Soient P et Q deux propositions et x un objet indéterminé.

• ¬(∃ x P) ⇔ (∀ x ¬ P)
• (∀ x) (P∧Q) ⇔ ( (∀ x) P ∧ (∀ x) Q )
• (∀ x) P ∨ (∀ x) Q ⇒ (∀ x) (P ∨ Q )
  (Implication réciproque fausse en général)
• (∃ x) (P∨Q) ⇔ ( (∃ x) P ∨ (∃ x) Q )
• (∃ x) (P∧Q) ⇒ ( (∃ x) P ∧ (∃ x) Q )
  (Implication réciproque fausse en général)

Propriétés utiles

Soient P une proposition et x et y des objets indéterminés.

• (∀ x) (∀ y) P ⇔ (∀ y) (∀ x) P
• (∃ x) (∃ y) P ⇔ (∃ y) (∃ x) P
• (∃ x) (∀ y) P ⇒ (∀ y) (∃ x) P
  (Implication réciproque fausse en général)

La dernière implication dit que s’il existe un x, tel que pour tout y, on ait P vraie, alors pour tout y, il existe bien un x (celui obtenu avant) tel que P soit vraie.

Intuitivement, l’implication réciproque est fausse en général, parce que si pour chaque y, il existe un x tel que P soit vraie, ce x pourrait dépendre de y et varier suivant y. Ce x pourrait donc ne pas être le même pour tout y tel que P soit vraie.