6. Calcul des prédicats

6. Calcul des prédicats

6.1 Pourquoi aller plus loin

La proposition p représente un énoncé complet sans exposer sa structure interne. Le calcul des prédicats permet de dire qui possède une propriété, quels objets sont liés et comment les objets dépendent les uns des autres. Le cours utilise la logique du premier ordre.

6.2 Vocabulaire

• Constante : désigne un objet particulier, par exemple Pierre, a, 38.
• Variable : représente un objet arbitraire, par exemple x, y, z.
• Fonction : construit un terme à partir d'autres termes, par exemple f(x) ou couleur(x).
• Prédicat : propriété ou relation qui devient vraie ou fausse une fois ses arguments fournis. Son arité est son nombre d'arguments : chat(x) est unaire, aime(x,y) binaire.
• Formule atomique : application d'un prédicat à des termes, par exemple parent(Paul,Julien).

Les connecteurs propositionnels restent disponibles et deux quantificateurs s'ajoutent :

• ∀x P(x) : pour tout x, P(x);
• ∃x P(x) : il existe au moins un x tel que P(x).

6.3 Traduire et lire les quantificateurs

Exemples :

• Pierre aime Nathalie : aime(Pierre,Nathalie);
• tout le monde aime quelqu'un : ∀x∃y aime(x,y);
• tout le monde aime tout le monde : ∀x∀y aime(x,y);
• quelqu'un aime tout le monde : ∃x∀y aime(x,y);
• toutes les pommes sont rouges : ∀x(pomme(x)→rouge(x)).

L'ordre est essentiel. Dans ∀x∃y aime(x,y), la personne y peut dépendre de x. Dans ∃y∀x aime(x,y), un seul même y doit convenir à tout x.

Les négations correctes sont :

• ¬∀x P(x) ≡ ∃x ¬P(x);
• ¬∃x P(x) ≡ ∀x ¬P(x).

Autrement dit, nier un quantificateur change le quantificateur et nie la formule interne.

Quantification et connecteurs :

• ∀x(P(x)∧Q(x)) ≡ (∀xP(x))∧(∀xQ(x));
• ∃x(P(x)∨Q(x)) ≡ (∃xP(x))∨(∃xQ(x));
• les formes analogues avec ∀ sur ∨ ou ∃ sur ∧ ne sont pas valides en général;
• deux universels consécutifs peuvent permuter, tout comme deux existentiels;
• un universel et un existentiel ne peuvent pas être intervertis en général.