Esta clase fue bastante densa, ya que era la clase antes del examen. En ella se explicó básicamente, la normalización de fórmulas, este tema corresponde al capítulo 7 del libro, y es fundamental para el examen del día 6, ya que los examinadores del campus trata bastante este tema.
Aquí esta expuestas las principales equivalencias para la normalización de fórmulas:
¬(A ^ B) = ¬A v ¬B
¬(A v B) = ¬A ^ ¬B
A –> B = ¬A v B
A <–> B = (A –> B) ^ (B –> A)
EN LA CLASE SE RESOLVIERON ESTAS EQUIVALENCIAS:
1º ¬(A ^ B) = ¬A v ¬B = A –> ¬B
2º ¬(A v B) = ¬(¬A –> B) = A v B
3º ¬(A –> B) = ¬(¬A v B) = A ^ ¬B
4º ¬(A –> ¬B) = ¬(¬A v ¬B) = A ^ B
5º (A1 ^ A2 –> ¬B) = ¬(A1 ^ A2 v ¬B) = ¬A1 v ¬A2 v ¬B = ¬(A1 ^ A2 ^ B)
6º (A1 –> (¬A2 –> B)) = A1 –> (A2 v B) = ¬A1 v A2 v B = ¬(A1 ^ ¬A2 ^ ¬B)
EQUIVALENCIAS CON CUANTIFICADORES
∀x[A(x) --> B(x)] = ∀x[¬(A(X) ^ ¬B(x))] = ∀x ¬[A(x) ^ ¬B(x)] = ¬∃x[A(x) ^ ¬B(x)]
∃x[A(x) ^ ¬B(x)] = ¬∀x[A(x) --> B(x)]
FORMAS NORMALES
La formas normales, sólo podrán estar formadas por ¬,^,v. Hay tres tipos de formas normales:
- Forma normas conjuntiva: los conjuntores “^” se quedan fuera de los paréntesis, y los disyuntores “v” dentro.
- Forma normal disyuntiva: los disyuntores “v” se quedan fuera de los paréntesis, y los conjuntores “^” dentro.
- Forma normal clausal: esta es la usada en programación lógica, según la wikipedia
* P v ¬q es una forma normal conjuntiva, y no tiene ningún conjuntor.
Un ejemomplo para pasar un FND (forma normal disyuntiva) a FNC (forma normal conjuntiva), sería el siguiente:
(P ^ ¬q) v R = (P v R) ^ (¬q v R)
En el libro, hay un método para reducir a forma normal, se hablamos del lenguaje preposicional. Ahora os dejo un ejemplo que resolvió en profesor en clase, paso por paso.
(p ^ q) v R –> q v ¬R a forma normal
1º eliminamos el implicador
¬[(p ^ q ) v R] v [¬q v ¬R]
2º normalizamos el negador (Morgan)
[¬(p ^ q) v R] v ¬q v ¬R
2º volvemos a normalizar el negador (Morgan)
[(¬p v ¬q)^ ¬R] v ¬q v ¬R
3º exteriorizar conjuntores o disyuntores
para la FNC hacemos:
(¬p v ¬q v ¬q v ¬R) ^ (¬R v ¬q v ¬R)
* Podemos agrupar en ploques, que sean A, B, C… para que sea más sencillo reducir la fórmula al aplicar las esquivalencias.
4º simplificamos
(¬p v ¬q v ¬R) ^ (¬q v ¬R) FNC
EXISTEN UN MÉTODO PARA ELIMINAR EXISTENCIALES, LLAMADO SKOLEM, Y OTRO PARA ELIMINAR CUANTIFICADORES UNIVERSALES, LLAMADO PRENEX.
SKOLEM
Si el existencial está afectado por un universal, se sustituye su variable por una función. Por ejemplo:
∀x∃y M(x,y) = ∀x M(x,f(y))
Si el existencial no está afectado por un universal, se sustituye su variable por una constante. Por ejemplo:
∃x P(x) ^ ∃y q(y) = P(a) ^ q(b)
PRENEX
Este método consiste en pasar los universales a la cabeza de la fórmula, si no lo están.
-Si la fórmula no contiene la variable cuantificada, hacemos:
A ^ ∀x P(x) = ∀x(P(x) ^ A)
-Si la fórmula contiene la variable cuantificada, hacemos:
A(x) ^ ∀x P(x) = ∀y(A(x) ^ P(y))
