Tema 4 Formas normales

Hoy repartió los exámenes realizados la semana anterior y terminamos el bloque 1 con el tema 4. Hicimos ejercicios sobre el tema 4.

Resumen tema 4: Formas normales

Características de las fbf escritas en forma normal

1º - Sólo conectivas: Conjunción (∧), Disyunción (∨) y Negación (¬).

2º - El negador sólo afecta a fbf atómicas.

3º - Si conectiva principal la conjunción: Forma Normal Conjuntiva (FNC).

Si conectiva principal la disyunción: Forma Normal Disyuntiva (FND).

Forma normal conjuntiva (FNC)

Forma normal disyuntiva (FND)

Método de reducción a forma normal

1º) Eliminar implicador: A →B ≡ ¬A ∨B ≡ ¬(A ∧ ¬B).

2º) Normalizar negador: ¬(A ∨ B) ≡ (¬A ∧ ¬B)

¬(A ∧ B) ≡ (¬A ∨ ¬B)

¬¬A ≡ A

3º) Exteriorizar conjuntores FNC A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)

(A ∧ B) ∨ C ≡ (A ∨ C) ∧ (B ∨ C)

disyuntores FND A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C)

(A ∨ B) ∧C ≡ (A ∧ C) ∨ (B ∧ C)

4º) Simplificar y ordenar:

A ∨B ≡ B ∨ A A ∧B ≡ B ∧ A

A ∨A ≡ A A ∧A ≡ A

A ∧ (A ∨ B) ≡ A A ∨ (A ∧ B) ≡ A

Forma clausal

Cláusula : disyunción de literales.

Cl1 = D1

Cl2 = D2,

. . .

Cln = Dn

Proceso para calcular la FC de una fbf cuantificada

1º.- Normalizar la fbf

2º .- Renombrar variables.

3º.- Aplicar Skolem (eliminar existenciales).

4º.- Aplicar Prenex.

5º.- Prescindir de cuantificadores universales.

6º.- Obtener la FNC de la matriz de la fbf.

7º.- Extraer las cláusulas.

8º.- Renombrar las variables.

· Con Skolem Eliminamos los cuantif. existenciales

Existencial no está en el alcance de un universal: Sustituir la variable por una constante: Constante de Skolem.

Existencial si está en el alcance de un universal: Sustituir la variable por una función: Función de Skolem.

· Con Prenex manipulamos los cuantif. Universales

- 1º.- La fórmula parcial no contiene la variable cuantificada.

- 2º.- La fórmula parcial si contiene a la variable cuantificada.

Ejercicios de clase

FNC n=3(con 3 disyunciones)

D1 D2 D3

m=1 m=1 m=1

FND

C1 C2 C3

m=1 m=1 m=1

FND

Morgan

¬¬A=A