Logique mathématique

COURS N°1 - Notions de logique

I. Proposition - Fonction propositionnelle - Les quantificateurs

A. Proposition

Définition : On appelle une proposition un énoncé mathématique (texte mathématique) qui a un sens pouvant être vrai ou faux (mais pas les deux en même temps). On note souvent une proposition par les lettres P, Q ou R.

Valeur de vérité d’une proposition :

• Si la proposition est vraie, on note V ou 1.
• Si la proposition est fausse, on note F ou 0.

Exemples :

• P : « 2 est un nombre pair » → proposition vraie
• Q : « 2 + 3 = 6 » → proposition fausse
• R : « ABCD est un parallélogramme alors que les diagonales se coupent en leur milieu » → proposition vraie

B. Fonction propositionnelle

Définition : Une fonction propositionnelle est un énoncé contenant une ou plusieurs variables (x, y, z,...) appartenant à des ensembles déterminés. On la note P(x), P(x, y, z)...

Remarque : Si l'on remplace les variables par des éléments de l'ensemble, la fonction devient une proposition.

Exemples :

• A(x) : pour tout x ∈ ℝ, √(x²) = x → fonction propositionnelle
• Si x = 2, alors √(4) = 2 → proposition vraie
• Si x = -3, alors √(9) = 3 ≠ -3 → proposition fausse
• A(x, y) : |x + y| = |x| + |y| → fonction propositionnelle
• Si x = 2 et y = 5 → proposition vraie
• Si x = -2 et y = 5 → proposition fausse

C. Les quantificateurs

1. Quantificateur universel

Exprime « pour tout x de E, Q(x) est vraie ». On le note : ∀x ∈ E, Q(x).

Exemple : ∀x ∈ ℝ : √(x²) = |x|

2. Quantificateur existentiel

Exprime « il existe un x dans E tel que Q(x) est vraie ». On le note : ∃x ∈ E, Q(x).

Exemple : ∃x ∈ ℝ : x + 4 = 3

Remarques :

• L’ordre des quantificateurs identiques (tous universels ou tous existentiels) ne change pas le sens.
• L’ordre des quantificateurs différents (universel puis existentiel) change le sens.
• La négation de ∀ est ∃ et la négation de ∃ est ∀.

Équivalences d'écriture :

• ¬(∀x ∈ E, P(x)) ⇔ ∃x ∈ E : ¬P(x)
• ¬(∃x ∈ E, P(x)) ⇔ ∀x ∈ E : ¬P(x)

COURS N°1 - NOTIONS DE LOGIQUE

I. PROPOSITION – FONCTION PROPOSITIONNELLE – LES QUANTIFICATEURS

A. Proposition

Définition :

On appelle une proposition un énoncé mathématique (texte mathématique) qui a un sens pouvant être vrai ou faux (mais pas les deux en même temps). On note souvent une proposition par les lettres P, Q ou R, etc.

Valeur de vérité d’une proposition :

• Si la proposition est vraie, on note V ou 1.
• Si elle est fausse, on note F ou 0.

Tableau de vérité d’une proposition :

Exemples :

• Q : 2 + 3 = 6 → Proposition fausse
• P : 2 est un nombre pair → Proposition vraie
• R : "ABCD est un parallélogramme alors les diagonales se coupent en leur milieu" → Proposition vraie

B. Fonction propositionnelle

Définition :

On appelle une fonction propositionnelle tout énoncé contenant une variable x (ou plusieurs variables x, y, z, ...) et qui appartient à des ensembles déterminés. On note P(x) ou P(x, y, z,...).

Remarque : Si on remplace les variables par un élément de ces ensembles, la fonction propositionnelle devient une proposition.

Exemples :

• A(x) : pour tout x ∈ ℝ, √x² = x → fonction propositionnelle.
  • Si x = 2, on obtient une proposition vraie.
  • Si x = -3, on obtient une proposition fausse.
• A(x, y) : pour tout x et y ∈ ℝ, |x + y| = |x| + |y| → fonction propositionnelle.
  • Si x = 2 et y = 5, on obtient une proposition vraie.
  • Si x = -2 et y = 5, on obtient une proposition fausse.

C. Les quantificateurs

a. Quantificateur universel

L’expression "pour tout x ∈ E, la proposition Q(x) est vraie" se note : ∀x ∈ E, Q(x).

Le symbole ∀ s’appelle quantificateur universel et se lit : pour tout... ou quel que soit...

Exemples :

• ∀x ∈ ℝ, √x² = |x|
• ∀x, y ∈ ℝ, |x + y| ≤ |x| + |y|

b. Quantificateur existentiel

L’expression "il existe un x ∈ E, tel que Q(x) est vraie" se note : ∃x ∈ E, Q(x).

Exemple :

• ∃x ∈ ℝ : x + 4 = 3

Remarques :

• L’ordre des quantificateurs identiques (tous universels ou tous existentiels) ne change pas le sens de la fonction propositionnelle.
• L’ordre des quantificateurs différents (universel et existentiel) change le sens de la fonction propositionnelle.
• La négation du quantificateur ∀ est le quantificateur ∃.
• La négation du quantificateur ∃ est le quantificateur ∀.
• Les écritures suivantes sont équivalentes :
  • ∀x ∈ E, ∀y ∈ E ou ∀x, y ∈ E
  • ∀(x, y) ∈ E × E
• Les écritures suivantes sont équivalentes :
  • ∃x ∈ E, ∃y ∈ E ou ∃(x, y) ∈ E × E

II. OPÉRATIONS SUR LES PROPOSITIONS

1. La négation d'une proposition

Définition :

La négation d'une proposition P est une nouvelle proposition notée ¬P (ou non P), qui est vraie lorsque P est fausse, et fausse lorsque P est vraie.