Logique du premier ordre

Un syllogisme

• SI Tous les chiens savent nager (P)
• ET Médor est un chien (Q)
• ALORS Médor sait nager (R)

Un encodage peu fidèle

• SI Tous les chiens savent nager (P)
• ET Médor est un chien (Q)
• ALORS Médor sait nager (R)

Un nouvel encodage

Limite de cet encodage

• Trois animaux Médor, Rex, Pat.
• Mêmes variables propositionnelles (avec C_Pat, N_Pat)

((C_Rex⇒N_Rex)∧(C_Médor⇒N_Médor)∧(C_Pat⇒N_Pat)∧C_Médor) ⇒ N_Médor

Une formulation au premier ordre

• Tout les chiens savent nager: ∀x(Chien(x) ⇒ Nage(x)).
• Médor est un chien: Chien(Médor)

(∀x(Chien(x) ⇒ Nage(x)) ∧ Chien(Médor)) ⇒ Nage(Médor).

Un autre exemple

Il existe des chats plus grands que certains chiens et il existe des chiens plus grands que certains chats.

Des quantificateurs

Des prédicats

Des connecteurs logiques

La syntaxe

On dispose d’un langage ℒ = (𝒞,𝒫,ℱ) avec :

• des symboles 𝒞 de constantes c₁, …, c_n
  • ex: “Médor”, “Rex”
• des symboles 𝒫 de prédicats avec leurs arités : P₁(i₁), …, P_m(i_m)
  • ex: Chien(1), Nage(1), Plusgrand(2), <(2)
  • arité : nombre d’éléments mis en relation dans le prédicat
  • on suppose souvent qu’on a un prédicat particulier “=” d’arité 2.
• des symboles ℱ de fonctions avec leurs arités : f₁(j₁), …, f_k(j_k)
  • ex: cos (1),  + (2),  × (2)
  • Permettent de former des termes : cos (x+(4×z))

Les termes

On fixe ℒ = (𝒞,𝒫,ℱ) et un ensemble de variables X.

Sont des termes (déf inductive) :

• les variables x ∈ X
• les constantes c ∈ 𝒞
• f(t₁,…,t_k) pour
  • f ∈ ℱ un symbole de fonction d’arité k
  • t₁, …, t_k sont des termes.

Les atomes

On forme les atomes : P(t₁,…,t_k)

• P ∈ 𝒫 un symbole de prédicat
• t₁, …, t_k des termes.

Les formules

On construit inductivement les formules :

• un atome P(t₁,…,t_k) est une formule
• Combiner des formules F₁, F₂ avec des connecteurs logiques
  • F₁ ∧ F₂,
  • F₁ ∨ F₂,
  • ¬F₁,
  • F₁ ⇒ F₂
• Quantification pour x ∈ X une variable et F une formule :
  • ∀x(F)
  • ∃x(F)

Variables libres et liées

Un quantificateur a une portée : ∀x(F).

• Entre ( et ), la variable x est dite liée.
• Sinon, une variable est dire libre.

• ∀x(A(x,y)) : y est libre.
• ∀x(A(x) ∧ ∃y(B(x,y))) : aucune variabe libre (formule close).

Interprétation

Étant donné un langage ℒ = (𝒞,𝒫,ℱ), une ℒ-interprétation ℐ est :

• un ensemble non-vide U appelé le domaine,
• pour chaque constante c ∈ 𝒞, un élément c_ℐ ∈ U du domaine
• pour chaque prédicat P ∈ 𝒫 d’arité k (sauf =), une relation P_ℐ ⊆ U^k.
• pour chaque fonction f ∈ ℱ d’arité k, une fonction f_ℐ : U^k → U.

Valeur d’un terme

Soit ℒ = (𝒞,𝒫,ℱ) un langage, et ℐ une ℒ-interprétation sur le domaine U.

On suppose qu’on a une fonction e : X → U qui donne une valeur aux variables. On l’appelle : l’environnement.

La valeur d’un terme t est définie inductivement :

• si t est un symbole de constante c ∈ 𝒞: val(t,e,ℐ) = c_ℐ

• si t est une variable x: val(t,e,ℐ) = e(x)

• si t est de la forme f(t₁,…,t_k) alors val(t,ℐ) = f_ℐ(val(t₁,ℐ),…,val(t_k,ℐ))

Valeur d’une formule

On définit inductivement la valeur val(Φ,e,I) d’une formule Φ par rapport à une interprétation ℐ et un environnement e

• Atomes
  • val(P(t₁,…,t_k),e,ℐ) = 1 si (val(t₁,e,ℐ),…,val(t_k,e,ℐ)) ∈ P_ℐ. Sinon val(P(t₁,…,t_k),e,ℐ) = 0.
• Connecteurs logiques
  • val(F∧G,e,ℐ) = 1 ssi val(F,e,ℐ) = 1 et val(G,e,ℐ) = 1
  • val(F∨G,e,ℐ) = 1 ssi val(F,e,ℐ) = 1 ou bien val(G,e,ℐ) = 1
  • val(¬F,e,ℐ) = 1 ssi val(F,e,ℐ) = 0
  • val(F⇒G,e,ℐ) = 1 ssi val(F,e,ℐ) = 0 ou bien val(G,e,ℐ) = 1.
• Quantificateurs
  • val(∀x(F),e,ℐ) = 1 ssi val(F,e[x:=a],ℐ) = 1 quelque soit a ∈ U
  • val(∃x(F),e,ℐ) = 1 ssi val(F,e[x:=a],ℐ) = 1 pour au moins un a ∈ U.

Modèle et validité

On a les mêmes notions qu’en logique propositionnelle :

• Une ℒ-interprétation ℐ est un modèle de Φ si val(Φ,ℐ) = 1. On notera ℐ ⊨ Φ
• Une formule Φ est valide si pour toute ℒ-interprétation ℐ, ℐ ⊨ Φ. On notera  ⊨ Φ.
• Φ est une conséquence logique de Ψ si pour tout ℐ tel que ℐ ⊨ Ψ on a ℐ ⊨ Φ. On notera Ψ ⊨ Φ.

Logique propositionnelle et premier ordre

Définir logique propositionnelle comme un fragment du premier ordre.