Download 2. Tec. Demostración 1

Técnicas de Estudio de Validez
Proposicional
Introducción
Existen diferentes alternativas matemáticas para evaluar
fórmulas en lógica proposicional
Tablas de Verdad
Árboles semánticos
Demostración por contradicción
Resolución proposicional
Tablas de verdad
Una tabla de verdad es una representación en la que de
forma tabular se presentan todas las interpretaciones
posibles para una fórmula
Tablas de Verdad
P.E. sea F = p q ↔ ¬p ∨ q
Nota: el número de interpretaciones de una fórmula F es
2n donde n es el número de variables en F
Ejercicio
Construir las tablas de verdad de las siguientes fórmulas:
((p q) r) ↔ ¬p ∨ q
(p q) ↔ ¬q∨ ¬ p
(¬p ∨ q) p ∧ q (r p ∨ q)
Árboles Semánticos
Técnica similar a las tablas de verdad. Sea F una fórmula y
LP conjunto de letras proposicionales de F, se genera un
árbol con un nodo raíz, entonces:
Se intenta evaluar F en el nodo actual. Si es posible asignar a
F una valor {V, F}, se etiqueta el nodo con dicho valor y se
finaliza
En caso contrario
1.
2.
1.
2.
3.
Se selecciona la primera letra proposicional (sea “p”) de LP y se
elimina de dicho conjunto
Se deriva del nodo actual dos ramas, donde “p” es interpretada
como V y “¬p” como F
Repetir el procedimiento desde el paso 1 para cada uno de nos
nodos del nuevo árbol
Árboles Semánticos
Por ejemplo, considere la fórmulas siguientes
pq
(p q) (¬p ¬q)
Construir los árboles semánticos para dichas expresiones
Demostración por contradicción
Para demostrar que F es válida, por contradicción se realiza lo
siguiente:
Se supone que existe una interpretación I tal que vi(F) = F y se
intenta calcular los diversos valores de la fórmula
Si se llega a una contradicción:
Entonces: ¬∃ I: vi(F) = F ⇒ ∀I: vi(F) = V es válida
En caso contrario: ∃ I: vi(F) = F ⇒ ∀I: vi(F) no es válida
Nota que en esta estrategia de demostración, lo que se busca
es encontrar un caso en donde la fórmula no sea válida. Si no
se encuentra (contradicción), entonces la fórmula es válida. En
ocasiones es más fácil encontrar un contraejemplo que
demostrar directamente lo que se quiere demostrar!!!
Demostración por contradicción
Demuestre la validez de las siguientes fórmulas:
¬p ∨ ¬q ¬(p ∧ q)
(a ↔ b) ∧ (b ↔ c) → (a ↔ c)