Formas Normales del Cálculo Proposicional y Predicativo

En general la normalización de fórmulas al principio me pareció dificil, sobre todo el concepto que define el proceso para reducir una fbf a Forma Normal de Prenex (Paso 3), y el proceso para introducir constantes y funciones Skolem del lenguaje predicativo. A medida que veiamos ejemplos en clase y realizabamos ejercicios se hacía más fácil memorizar los pasos a seguir en todo el proceso de normalización y podiamos ver que el proceso Prenex no es tan complicado como su concepto lo define, puesto que solo consiste en ubicar todos los cuantificadores universales en cabeza.

Lo más importante que hay que identificar en las fórmulas escritas en forma normal, es que solo tienen la conectivas conjunción, disyunción y negador, que el negador solo afecta a fórmulas atómicas y que en la Forma Normal Conjuntiva (FNC) la conectiva principal es la conjunción, mientras que en la Forma Normal Disyuntiva y Forma Clausual la conectiva principal la disyunción.

El método de reducción a forma normal es el siguiente:

1. Reducción de Constantes Lógicas: Eliminar implicadores y coimplicadores, por sus equivalentes, de manera que la fórmula sólo contenga conjuntores, disyuntores y/o negadores.

2. Normalización del Negador: Interiorizar los negadores de manera que queden adosado una fórmula atómica.

3. Exteriorización de Conjuntores o Disyuntores: Implica utilizar la propiedad distributiva de la siguiente manera

FNC

FND

4. Simplificación y ordenación de resultados:

Veamos el ejemplo que hicimos en clase:
(p ∧ q) v r → ¬q v ¬r

1º Definición del Implicador
¬[(p ∧ q) v r] v ¬q v ¬r

2º De Morgan
[¬(p ∧ q) ∧ ¬r] v ¬q v ¬r = [¬p v ¬q) ∧ ¬r] v ¬q v ¬r

3º Exteriorización de Conjuntores
(¬p ∧ ¬r) v (¬q ∧ ¬r) v ¬q v ¬r

4º Simplificando
(¬p v ¬q v ¬r) ∧ (¬r v ¬q) FNC

El proceso es el mismo, solo que hay que quitar los cuatificadores.

Skolem quita el ∃xistencial reemplazandolo por una constante, por ejemplo:

Si el existencial se encuentra en el alcance de un cuantificador universal, todas las ocurrencias de esta variable son reemplazadas por una función skolem, cuyos argumentos son las variables del cuantificador universal, por ejemplo:

Prenex pasa los ∀nivesales a la cabeza de la fórmula, por ejemplo:

5. ¬Al(x) v T(x)
7. C1: ¬Al(x) v T(x)