mdl2 teorico1 comp

1

5 - Propiedades simples de la L´
ogica de Predicados
Consideramos sentencias.
Consideramos un α arbitrario por lo que las pruebas valen para todo α.

Teorema 5.1
1. ¬∀xφ ↔ ∃x¬φ.
Demostremos α |=¬∀xφ ⇒ α |= ∃x¬φ.
Dem. no para todo a φ[a/x] entonces existe un a ¬φ[a/x].
Reciproco: similar.
2. ¬∃xφ ↔ ∀x¬φ.
Demostremos α |= ¬∃xφ ⇒ α |= ∀x¬φ.
Dem. no hay ning´
un a que cumpla φ entonces para todo ase cumple
¬φ.
Reciproco: similar.
3. ∀xφ ↔ ¬∃x¬φ.
Demostremos α |= ∀xφ ⇒ α |= ¬∃x¬φ.
Dem. Si para todo a se cumple φ no existe ning´
un a que cumpla ¬φ.
Reciproco: similar.
4. ∃xφ ↔ ¬∀x¬φ.
Demostremosα |= ∃xφ ⇒ α |= ¬∀x¬φ.
Dem. hay un a que cumple φ entonces no para todo a se cumple ¬φ.
Reciproco: similar.

2

Teorema 5.2
1. ∀x∀yφ ↔ ∀y∀xφ.
Demostremos α |= ∀x∀yφ ⇔ α |= ∀y∀xφ.
Dem. para todo a secumple que para todo b se cumple φ. a y b
representan constantes cualesquiera. Es lo mismo que poner: para
todo b se cumple que para todo a se cumple φ.
2. ∃x∃yφ ↔ ∃y∃xφ.
Demostremos α |= ∃x∃yφ ⇔ α |=∃y∃xφ.
Dem. existe un a y existe un b tal que se cumple φ[a, b]. Es lo mismo
que decir : existe un b y existe un a tal que se cumple φ[a, b].
3. ∀xφ ↔ φ cuando x ̸∈ F V (φ).
Demostremos α |= ∀xφ ⇔ α |=φ.
Dem. Si a no ocurre en F V (φ), φ[a/x] = φ. Luego si se cumple φ se
cumple ∀xφ y viceversa.
4. ∃xφ ↔ φ cuando x ̸∈ F V (φ).
Demostremos α |= ∃xφ ⇔ α |= φ.
Dem. Si a no ocurre en F V (φ), φ[a/x] = φ.Luego si se cumple φ se
cumple ∃xφ y viceversa.

Teorema 5.3
1. ∀x(φ ∧ ψ) ↔ (∀xφ ∧ ∀xψ).
Demostremos α |= ∀x(φ ∧ ψ) ⇔ α |= (∀xφ ∧ ∀xψ).

3
Dem. Para todo a se cumple φ y ψ. Entonces para todo a secumple
φ y para todo a se cumple ψ.
Reciproco. Si para todo a se cumple φ y para todo a se cumple ψ
para todo a se cumplen ambos.
2. ∃x(φ ∨ ψ) ↔ (∃xφ ∨ ∃xψ).
Demostremos α |= ∃x(φ ∨ ψ) ⇔ α |= (∃xφ ∨∃xψ).
Dem. hay un a que cumple φ o ψ. Supongo cumple φ entonces hay
un a que cumple φ, supongo cumple ψ entonces hay un a que cumple
ψ.
Reciproco. Supongo (∃xφ ∨ ∃xψ). Entonces se cumple alguno...