P8

Instituto de Computación - Facultad de Ingeniería - 2009

Lógica - Práctico 8 (Deducción Natural e Identidad - Lógica de Predicados) Ejercicio 1. Sean ϕ,ψ fórmulas de FORM. Construya derivaciones que demuestren las siguientes afirmaciones. Justifique cuando corresponda que las restricciones se cumplen al aplicar las reglas. a) ∀x (ϕ → ψ) | (∀x ϕ → ∀x ψ) b) ∀x ϕ | ¬∀x (¬ϕ) c) ∀x ϕ | ∀z ϕ[z / x] , donde z no ocurre en ϕ d) ∀x ∀y ϕ | ∀y ∀x ϕ e) ∀x ∀y ϕ | ∀x ϕ [x / y], donde x ∉ BV (ϕ) f) ∀x (ϕ ∧ ψ) | ∃x ϕ ∧ ∃x ψ g) ∃x ϕ , ∀x (ϕ → ψ) | ∃x ψ

Ejercicio 2. Sean ϕ,ψ fórmulas de FORM. Construya derivaciones para los siguientes teoremas del cálculo de predicados. Justifique cuando corresponda que las restricciones se cumplen al aplicar las reglas. a) | ∀x (ϕ ∧ ψ) ↔ (∀x ϕ ∧ ∀x ψ) b) | ∀x (ϕ → ψ) ↔ (ϕ → ∀x ψ) , donde x ∉ FV (ϕ) c) | ∃x (ϕ ∧ ψ) ↔ ∃x ϕ ∧ ψ , donde x ∉ FV (ψ) d) | ∀x (ϕ ∨ ψ) ↔ ∀x ϕ ∨ ψ , donde x ∉ FV (ψ) e) | ∀x ϕ ↔ ¬∃x (¬ϕ) f) | ¬∀x ϕ ↔ ∃x (¬ϕ) g) | ¬∃x ϕ ↔ ∀x (¬ϕ) h) | ∃x (ϕ → ψ) ↔ (∀x ϕ → ψ) , donde x ∉ FV (ψ) i) | ∃x (ϕ → ψ) ↔ (ϕ → ∃x ψ) , donde x ∉ FV (ϕ) j) | ∃x ∃y ϕ ↔ ∃y ∃x ϕ k) | ∃x ϕ ↔ ϕ , donde x ∉ FV (ϕ)

Página 1 de 3

Instituto de Computación - Facultad de Ingeniería - 2009

Ejercicio 3. Considere las reglas de derivación correspondientes a los axiomas de identidad : x =’ x

(RI1)

x1 =’ y1 ..... xn =’ yn t [x1...xn / z1...zn] =’ t [y1...yn / z1...zn]

(RI4)

x =’ y y =’ x

x1 =’ y1 ..... xn =’ yn ϕ[x1...xn / z1...zn] (RI4)(*) ϕ[y1...yn / z1...zn]

(RI2)

x =’ y y =’ z x =’ z

(RI3)

(*) si xi, yi son libres para zi en ϕ (i = 1..n).

Demuestre que : a) b) c) d) e)

| | | | |

∀z (z =’x ↔ z =’y) → (x =’y) ∀x ∃y (x =’y) ∀x ∀y ∀z (¬(x =’y) → ¬(x =’z) ∨ ¬(y =’z)) ∀x (ϕ ↔ ∀y ( x =’y → ϕ[y / x])) , donde y no ocurre en ϕ ∀x (ϕ ↔ ∃y ( x =’y ∧ ϕ[y / x])) , donde y no ocurre en ϕ

Ejercicio 4. Considere un lenguaje de primer orden del tipo 〈 2 ; – ; 0 〉 con un símbolo P de predicado binario. Sea M = < A,R > una estructura del mismo tipo, donde A es un conjunto de elementos y R ⊆ AxA. Considere las siguientes fórmulas de dicho lenguaje: σ1 ≡ ∀x P(x,x) σ2 ≡ ∀x ∀y ( P(x,y) → P(y,x) ) σ3 ≡ ∀x ∀y ∀z ( P(x,y) ∧ P(y,z) → P(x,z) ) a) Pruebe que si M |= σ1 ∧σ2 ∧σ3 entonces R es una relación de equivalencia. b) Considere además la siguiente fórmula del lenguaje : σ4 ≡ ∀x ∀y ∀z ( P(x,y) ∧ P(x,z) → P(y,z) ) Demuestre que : σ1 , σ4 | σ2 ∧σ3

Ejercicio 5. a) Demuestre | ∀x∃y ¬P(x, y) →¬∀x∀y P(x, y). b) Demuestre que | ¬∀x∀y P(x, y) →∀x∃y ¬P(x, y). c) Indique por qué la siguiente derivación no es correcta:

Página 2 de 3

Instituto de Computación - Facultad de Ingeniería - 2009 P(x, y) ∀y P(x, y) ¬∀x∀y P(x, y).

∀x∀y P(x, y). ⊥ ¬P(x, y). ∃y ¬P(x, y). ∀x∃y ¬ P(x, y)

Ι∀ Ι∀ E¬

I¬ Ι∃ Ι∀

Página 3 de 3