TP 5 : Substitutions et Modèles

On considère le langage ℒ donc les symboles de fonctions sont {f(1), g(2)}, avec un prédicat R(2) et les constantes {c, d} et soit F = ∀x(R(f(x),g(c,y))).

1. Quelles sont les variables libres de F ?
2. Que vaut F[y:=f(d)] ? Quelles sont ses variables libres ?
3. Que vaut F[y:=g(x,x)] ? Quelles sont ses variables libres ?
4. Que vaut F[y:=g(x,z)][z:=g(x,y)] ? Quelles sont ses variables libres ?

On définit le langage ℒ = (𝒞,ℱ,𝒫) avec:

• 𝒞 = {0, 1}
• ℱ = {f(1), g(2)}
• 𝒫 = { ≺ }

On considère les formules suivantes :

• ϕ₁ = ∀x(∃y(f(x)≺g(x,y)))
• ϕ₂ = ∀x(∀y(g(x,y)≺f(x)))
• ϕ₃ = ∀x(∀y(g(x,y)≺f(x)∧g(x,y)≺f(y)))
• ϕ₄ = ∀x(∀y(g(x,y)=g(y,x)))

Et les interprétations suivantes :

• I: domaine ℕ, f_I(a) = max (0,1−a), g_I(a,b) = max (0,a−b), ≺_I = <
• J: domaine 𝒫(ℕ), f_J(a) = ℕ \ a, g_J(a,b) = a ∩ b, ≺_J = ⊆
• K: domaine 𝒫(ℕ), f_K(a) = ℕ \ a, g_K(a,b) = ℕ \ (a∩b), ≺_K = ⊇

1. Calculez la valeur de chaque formule pour chaque interprétation.
2. Est-ce que ϕ₁ ∧ ϕ₂ est contradictoire?
3. Est-ce que  ⊨ (ϕ₂∧ϕ₄) ⇒ ϕ₃?

On considère la formule propositionnelle suivante : F = (p⇒q) ⇒ (q∧p). On considère le langage du premier ordre ℒ sans constante ni symboles de fonction mais avec prédicat {P(0), Q(0)} et la formule du premier ordre Φ_F = (P⇒Q) ⇒ (Q∧P).

1. Quels sont les modèles de F ? Combien y en a-t-il ?
2. Soit I, J deux interprétations de ℒ tel que P_I = P_J et Q_I = Q_J. Montrez que val(Φ_F,I) = val(Φ_F,J).
3. Combien Φ_F a-t-elle de modèles ?