Guille

Definiciones
Tautología: Son aquellas fórmulas que son ciertas para cualquier valoración de los símbolos proposicionales que contiene.
ϕ ∈ LΣ ϕ tautología ⇔ ∀ V [ϕ]V = 1 (o V ϕ )

1.4Tautologías, contradicciones y contingencias
Lógica

Contradicción: Son aquellas fórmulas que son falsas para cualquier valoración de los símbolos proposicionales que contiene.
ϕ ∈ LΣ ϕ contradicción ⇔ ∀ V[ϕ]V = 0 (o V  ϕ )

Contigencia: Son aquellas fórmulas cuyo valor de verdad o falsedad depende de la valoración de los símbolos proposicionales que contiene.
1.4 Tautologías, contradicciones ycontingencias 2

Ejemplo
Teorema: Demostrad que  = (p → q) ∧ p ∧ ¬q es una contradicción
• Reducción al absurdo:
Supongamos que existe valoración V tal que V  Entonces V  p → q, V p, V  ¬q Perono es posible [p → q]V = 1 con V(p) = 1 y V(q) = 0

Teorema
Existe un método efectivo para decidir si una fórmula dada ϕ ∈ LΣ es tautología, contradicción o contingencia.

Ejemplo:
 = (p → r) ∧(q → r) → (p ∨ q → r) p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p → r q → r (p → r) ∧ (q → r) p ∨ q 0 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 p∨q→r 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1
4

1.4 Tautologías, contradicciones y contingencias

3

1.4 Tautologías, contradicciones y contingencias

1

Sustituciones
Definición:
Sea una fórmula ψ ∈ LΣ quecontiene al menos los símbolos proposicionales p1, p2, ... pn ∈ Σ, y sean ϕ1, ϕ2, ... ϕn fórmulas arbitrarias de LΣ ψ’ = ψ[p1/ϕ1, p2/ϕ2, ... pn/ϕn] designa a la fórmula resultante de sustituir en ψ todas lasapariciones de p1, p2, ... pn por ϕ1, ϕ2, ... ϕn respectivamente.

Teorema
Teorema:
ϕ es tautología ⇔ Todo caso particular de ϕ (ϕ’) es tautología

Ejemplo:
φ ∧ ψ → φ tautología paracualesquiera fórmulas φ, ψ ∈ LΣ Por el teorema anterior ya que p ∧ q → p es tautología

Ejemplo: (p →¬q∧r)→(p↔s) [p/(s∧t),q/(¬t)] ⇒ ((s∧t) →¬(¬t)∧r)→((s∧t) ↔s) Definición:
La fórmula ψ’ obtenida a...