DEV Community

Alison Orellana Rios
Alison Orellana Rios

Posted on

FND y FNC paso a paso: formas normales en lógica proposicional

Si llevas Lógica en primer año de informática o sistemas, tarde o temprano te piden "llevar una fórmula a FND" o "a FNC". Es uno de los temas que más dudas genera, y casi siempre por lo mismo: se mezclan las reglas de una forma con las de la otra.

En este artículo vas a ver qué es cada forma, dos métodos para obtenerlas y los errores más comunes. Al final hay tres ejercicios con respuesta.

Notación: ¬ es negación, ∧ es "y", ∨ es "o", → es el condicional y ↔ el bicondicional. V es verdadero y F es falso.

Qué son la FND y la FNC

Primero, un literal es una variable o su negación: p, ¬p, q, ¬q.

  • FND (forma normal disyuntiva): una disyunción de conjunciones de literales. Por fuera hay ∨, por dentro solo ∧.

Ejemplo: (p ∧ ¬q) ∨ (¬p ∧ r)

  • FNC (forma normal conjuntiva): una conjunción de disyunciones de literales. Por fuera hay ∧, por dentro solo ∨.

Ejemplo: (p ∨ ¬q) ∧ (¬p ∨ r)

Para reconocerlas, mira el conectivo principal. Si es ∨ y dentro de los paréntesis solo hay ∧, es FND. Si es ∧ y dentro solo hay ∨, es FNC.

Lo importante: toda fórmula tiene una FND y una FNC equivalentes. Por eso sirven como forma estándar de escribir cualquier fórmula.

Método 1: desde la tabla de verdad

Es el método más mecánico. Solo necesitas la tabla.

Para la FND:

  1. Toma las filas donde la fórmula vale V.
  2. En cada una escribe una conjunción: la variable tal cual si vale V, negada si vale F.
  3. Une todas las conjunciones con ∨.

Para la FNC:

  1. Toma las filas donde la fórmula vale F.
  2. En cada una escribe una disyunción: la variable tal cual si vale F, negada si vale V.
  3. Une todas las disyunciones con ∧.

Ejemplo: p → q

p q p → q Aporta
V V V p ∧ q (FND)
V F F ¬p ∨ q (FNC)
F V V ¬p ∧ q (FND)
F F V ¬p ∧ ¬q (FND)
  • FND: (p ∧ q) ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q)
  • FNC: ¬p ∨ q

Fíjate en la FNC: salió ¬p ∨ q, que es justo la equivalencia conocida del condicional.

Método 2: con álgebra de proposiciones

Cuando la fórmula tiene muchas variables, la tabla se vuelve larga y conviene transformar la fórmula con leyes.

  1. Elimina → y ↔ usando p → q ≡ ¬p ∨ q.
  2. Lleva las negaciones hacia adentro con las leyes de De Morgan y la doble negación.
  3. Aplica la ley distributiva: para la FND distribuye ∧ sobre ∨; para la FNC distribuye ∨ sobre ∧.

Ejemplo: (p → q) ∧ r

Paso Ley
(¬p ∨ q) ∧ r Condicional. Ya está en FNC.
(¬p ∧ r) ∨ (q ∧ r) Distributiva. Esta es la FND.

En dos pasos salieron las dos formas.

Un detalle: con álgebra normalmente obtienes la forma simplificada, y desde la tabla obtienes la forma completa (cada término con todas las variables). Las dos son correctas; revisa cuál pide tu docente.

El problema inverso: de la tabla a la fórmula

A veces el ejercicio viene al revés: te dan solo la tabla y tienes que encontrar una fórmula que la cumpla. Se resuelve con el método 1.

Supón que la columna final es F, V, V, F:

p q A
V V F
V F V
F V V
F F F
  • Con las filas V, la FND es (p ∧ ¬q) ∨ (¬p ∧ q)
  • Con las filas F, la FNC es (¬p ∨ ¬q) ∧ (p ∨ q)

Las dos fórmulas dicen lo mismo: "p o q, pero no ambas".

Un consejo práctico: si la tabla tiene pocas filas V, usa la FND; si tiene pocas filas F, usa la FNC. Te sale una fórmula más corta.

Errores comunes

  • Usar las filas equivocadas. La FND sale de las filas V; la FNC, de las filas F.
  • No invertir en la FNC. En la FNC se niega lo que vale V. Es al revés que en la FND.
  • Distribuir antes de eliminar el condicional. Primero quita → y ↔, después distribuye.
  • Dejar una negación fuera de un paréntesis. ¬(p ∧ q) no es un literal: hay que aplicar De Morgan para que quede ¬p ∨ ¬q.

Ejercicios

  1. Obtén la FND y la FNC de p ∧ ¬q desde su tabla de verdad.
  2. Obtén con álgebra la FNC de p → (q ∧ r).
  3. Encuentra una fórmula con dos variables cuya columna final sea V, V, F, F, y simplifícala.

Respuestas

  1. La columna final es F, V, F, F. FND: p ∧ ¬q. FNC: (¬p ∨ ¬q) ∧ (p ∨ ¬q) ∧ (p ∨ q).
  2. ¬p ∨ (q ∧ r) por la ley del condicional, y luego (¬p ∨ q) ∧ (¬p ∨ r) por la distributiva.
  3. FND: (p ∧ q) ∨ (p ∧ ¬q). Sacando factor común queda p ∧ (q ∨ ¬q), que es simplemente p.

La clase en video

Si prefieres verlo resuelto en pizarra, en esta clase resuelvo ejercicios de FND, FNC y formalización paso a paso:

El resto de las clases del curso de Lógica está en esta lista de reproducción: https://www.youtube.com/playlist?list=PLP496G-vkbzcTyl8v0oO9WSwLaOUs-NFX

En el próximo artículo de la serie: tableaux semánticos, o cómo saber si una fórmula es válida sin hacer la tabla completa.

Top comments (0)