Définition

Introduction

La logique du premier ordre, c'est quoi en fait ?

D'abord, imaginons un monde où il existe des choses qui sont soit vraies, soit fausses. On appellera ces choses des propositions. On peut définir des opérations sur ces dernières, dont la mise en application est elle-même une proposition.

• a ET b : est vraie si a est vraie et si b est vraie
• a OU b : est vraie si a est vraie ou si b est vraie, ou les deux
• a → ("implique") b : est vraie si quand a est vraie alors b est vraie (ou si a est fausse)
• a ⇔ ("est équivalent à") : est vraie si a implique b et b implique a
• NON a : est vraie si a est fausse

Syntaxe

fonction := f, g, h, ...

paramètres := '(' terme [ ',' terme ]* ')' (ex: (x, y, z))

terme :=

• terme {+,-,*,/,^} terme (ex: 2+2)
• -terme
• littéral (ex: 123, 0, ...)
• variable (ex: a, b, ...)
• fonction paramètres (ex: f(x))

proposition :=

• terme {=,<,>,≤,≥} terme (ex: x≥y)
• proposition {ET,OU,→,⇔} proposition (ex: a>8 ET f(b)=6)
• NON proposition (ex: NON c=d)

Ça casse pas trois pattes à un canard, mais ça fonctionne.

Le monde que nous venons de décrire s'appelle le calcul propositionnel.

Et si...

Imaginons maintenant que nous rajoutions une chose appelée prédicat. Un prédicat, mathématiquement, c'est une fonction qui à une valeur associe un booléen (par opposition aux fonctions "normales" qui à une valeur associent une autre valeur). Par exemple, f(x) = x² est une fonction mais P = x>0 OU x<10 est un prédicat.

Nous pouvons rajouter des choses à notre syntaxe :

prédicat := P, Q, R, ...

atome := prédicat paramètres (ex: P(x))

proposition :=

• ...
• atome

Voire même...

Nous allons également rajouter un autre type de proposition, qui permettra d'énoncer des vérités qui portent sur un ensemble de choses. Par exemple énoncer que toutes les valeurs possédant la caractéristique A possèdent également la caractéristique B.

Nous appellerons cela le quantificateur universel noté ∀ ("pour tout"). Notre exemple se notera : ∀x A(x)→B(x). Voici la syntaxe :

proposition :=

• ...
• ∀ variable formule (ex: ∀x P(x))

Nous allons aussi rajouter (encore un) un autre type de proposition, qui permettra quant à lui d'énoncer l'existence de valeurs validant une condition. Par exemple énoncer qu'il existe au moins une valeur x telle que P(x) et x>5.

Nous appellerons cela le quantificateur existentiel noté ∃ ("il existe"). Notre exemple se notera : ∃x P(x) ET x>5. La syntaxe :

proposition :=

• ...
• ∃ variable formule (ex: ∀x P(x))

Nous venons donc de munir notre calcul propositionnel de plusieurs concepts intéressants :

• les prédicats (P(x), Q(y))
• les quantificateurs (∀x, ∃y)

Le résultat

Le résultat obtenu s'appelle le calcul des prédicats, calcul des relations, logique quantificationnelle, mais son nom le plus connu est : logique du premier ordre.

Suit maintenant la syntaxe "complète" de notre logique.

Syntaxe de la logique du premier ordre

*note: ici, j'utilise des termes numériques, mais en soi ce qui est ici fonctionne même avec d'autres types de valeurs. La logique du premier ordre se fout pas mal de quel type de valeurs on manipule, on pourrait travailler avec des ensembles (et les opérations ∪, ∩, ⊂, ∈, ×), les fonctions (∘, ∂, ∫, ∇, , ℒ, ℱ), les matrices (⋅, ∘, ⊘, ⊗, ⊺, |, ‖), etc.**

fonction := f, g, h, ...

paramètres := '(' terme [ ',' terme ]* ')' (ex: (x, y, z))

terme :=

• terme {+,-,*,/,^} terme (ex: 2+2)
• -terme
• littéral (ex: 123, 0, ...)
• variable (ex: a, b, ...)
• fonction paramètres (ex: f(x))

prédicat := P, Q, R, ...

atome := prédicat paramètres (ex: P(x))

proposition :=

• terme {=,<,>,≤,≥} terme (ex: x≥y)
• proposition {ET,OU,→,⇔} proposition (ex: x>8 ET P(y))
• NON proposition (ex: NON P(x))
• {∀,∃} variable proposition (ex: ∀x x>5, ∃y ∀x P(x, y))
• atome

nb: proposition est synonyme de formule

analogie avec la prog

valeur : int // (par exemple)
booléen : bool

int a, b; // valeurs

int fonction(int param)
{
    return param + 1;
}

bool predicat(int param)
{
    return param % 2 == 0; // "param est pair"
}

int resultat = fonction(predicat(a)); // syntax error, prédicat renvoie bool et fonction prend int

équivalent à dire que la formule f(P(a)) est invalide en logique du premier ordre, ou, plus proprement, que f(P(a)) n'est pas une formule en logique du premier ordre.