Formas normales (Matemática)
| ||||||
Formas Normales (Matemática). La relación de equivalencia establece para cada fórmula, una clase de equivalencia. Dentro de cada una de estas clases, hay un conjunto de miembros (fórmulas) que poseen una estructura particular que las hace objeto de especial interés. La simplificación de fórmulas permite que a partir de una fórmula cualquiera se obtenga una forma normal disyuntiva mínima equivalente.
Sumario
Formas normales proposicionales
Antes de definir lo que es una forma normal proposicional, es preciso establecer el concepto de literal.
Un literal es una Variable proposicional (fórmula atómica) o su negación.
Existen dos tipos de formas normales, las disyuntivas y las conjuntivas. Las formas normales disyuntivas son disyunciones de conjunciones de literales, mientras las formas normales conjuntivas son conjunciones de disyunciones de literales.
Una fórmula A, está en forma normal disyuntiva (fnd) si es de la forma A1 ⅴ A2 ... ⅴ An donde n>=1 y A1, A2 , An son conjunciones de literales.
Una fórmula A, está en forma normal conjuntiva (fnc) si es de la forma A1 ᴧ A2 ... ᴧ An donde n>=1 y A1, A2 , An son disyunciones de literales.
Si A es un literal, puede ser considerado tanto disyunción de literales, como conjunción de literales.
Resumiendo:
- Denominaremos literal a cualquier fórmula compuesta por un único símbolo de proposición p (literal positivo) o su negación ᴧ¬p (literal negativo)
- Cláusula conjuntiva es cualquier conjunción de literales.
- Cláusula disyuntiva es cualquier disyunción de literales.
- Una fórmula se dice que está en Forma Normal Conjuntiva (fnc) si es una conjunción de cláusulas disyuntivas.
- Una fórmula se dice que está en Forma Normal Disyuntiva (fnd) si es una disyunción de cláusulas conjuntivas.
Ej: Las siguientes fórmulas se encuentran en forma normal disyuntiva:
- p
- ¬p ⅴ q
- (¬p ᴧ q) ⅴ q
- (q ᴧ r ᴧ ¬p) ⅴ (¬q ᴧ r) ⅴ (¬q ᴧ p)
Ej.: Las siguientes fórmulas se encuentran en forma normal conjuntiva.
- p ᴧ r
- p
- (¬p ⅴ q) ᴧ (r ⅴ q)
- (¬q ⅴ r) ᴧ p
Nótese que la fórmula atómica p se considera tanto fnc como fnd. En el primer caso puede ser vista como una conjunción de una sola disyunción de literales, con la particularidad de que esta disyunción es a su vez de un sólo literal. En el segundo caso puede verse como una disyunción de una sola conjunción de literales, con la particularidad de que esta conjunción es a su vez de un sólo literal.
Otra fórmula interesante es ¬p ⅴ q, esta también es fnc y fnd. En el primer caso se analiza como una conjunción de una sola disyunción de literales. En el segundo caso es vista como una disyunción de dos conjunciones de literales, con la particularidad de que cada conjunción es a su vez de un sólo literal. Algo parecido ocurre con p ᴧ r.
Formas normales completas
Aunque las formas normales, constituyen un Subconjunto de las fórmulas en general, dada una fórmula, la cantidad de formas normales que le son equivalentes es muy grande (de hecho es un conjunto infinito). Esto hace deseable contar con una forma más estándar, que sirva como una especie de representante de la clase de equivalencia. Estas formas estándares existen, y para cada clase de equivalencia se cuenta con dos de ellas, una conjuntiva y otra disyuntiva, ambas se conocen como formas normales completas.
Se conoce como forma normal disyuntiva completa (fndc) a una disyunción de conjunciones elementales.
Se conoce como forma normal conjuntiva completa (fncc) a una conjunción de disyunciones elementales.
Para completar estas definiciones, se hace preciso establecer dos conceptos:
- Conjunción elemental: conjunción de literales de la forma L1 ᴧ L2 ... ᴧ Ln, , donde n es el número de variables veritativas que contiene la fórmula y ninguna variable aparece en más de un literal.
- Disyunción elemental: disyunción de literales de la forma L1 ⅴ L2 ... ⅴ Ln, , donde n es el número de variables veritativas que contiene la fórmula y ninguna variable aparece en más de un literal..
Estas formas completas, además de constituir representantes distinguidos de sus clases de equivalencias, ofrecen la ventaja de que son muy fáciles de obtener a partir de sus tablas veritativas y viceversa.
Si se tiene una tabla veritativa, para obtener la fndc correspondiente, se toma cada combinación (fila) con valor 1 y se obtiene a partir de ella una conjunción elemental, donde las variables que en la fila aparecen con valor 0 serán literales negados, mientras las que aparecen con valor 1 serán literales positivos (sin negar). De esta manera se obtienen todas las conjunciones elementales y por tanto la fndc.
Un proceso similar permite obtener la fncc. Se toma cada combinación (fila) con valor 0 y se obtiene a partir de ella una disyunción elemental, donde las variables que en la fila aparecen con valor 1 serán literales negados, mientras las que aparecen con valor 0 serán literales positivos (sin negar). De esta manera se obtienen todas las disyunciones elementales y por tanto la fncc.
A continuación se ilustra como valerse del procedimiento explicado para obtener la fndc equivalente a la fórmula p ⇔ ( q ⅴ r ).
- En primer lugar es necesario construir la tabla de la verdad.
| p | q | r | Valor de fórmula |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
2. Luego se identifican todas las interpretaciones verdaderas, que en este caso son cuatro: 000, 101, 110 y 111.
3. A partir de estas interpretaciones se obtienen las conjunciones elementales:
¬p ᴧ ¬q ᴧ ¬r
p ᴧ ¬q ᴧ r
p ᴧ q ᴧ ¬r
p ᴧ q ᴧ r
4. Finalmente la fndc resultante es:
(¬p ᴧ ¬q ᴧ ¬r) ⅴ (p ᴧ ¬q ᴧ r) ⅴ (p ᴧ q ᴧ ¬r) ⅴ (p ᴧ q ᴧ r)
Simplificación de fórmulas
A pesar de las ventajas de las formas normales completas, con frecuencia estas son bastante grandes y se desea obtener una equivalente, pero lo más simple posible. Esto puede resolverse mediante el proceso de simplificación que se presenta a continuación, el que a partir de una fórmula cualquiera permite obtener una forma normal disyuntiva mínima equivalente.
Para hacer más comprensible la explicación, esta se basará en un ejemplo concreto.
Se desea minimizar A = (p ⇒ (r ᴧ p)) ⅴ (¬q ᴧ r) .
Teniendo una fórmula A, el primer paso para obtener una forma normal disyuntiva mínima equivalente consiste en construir su tabla veritativa. Para el ejemplo actual quedaría:
| p |
q |
r |
A |
| 0 |
0 |
0 |
1 |
| 0 |
0 |
1 |
1 |
| 0 |
1 |
0 |
1 |
| 0 |
1 |
1 |
1 |
| 1 |
0 |
0 |
0 |
| 1 |
0 |
1 |
1 |
| 1 |
1 |
0 |
0 |
| 1 |
1 |
1 |
1 |
El segundo paso consiste en desechar las filas falsas, quedándose solo con las verdaderas, que se agruparán de acuerdo a la cantidad de 1 que presenten, ordenándose estos grupos de manera ascendente según el mismo criterio.
- Filas desechadas: 100 y 110
- Filas del primer grupo (ningún 1) 000
- Filas del segundo grupo (un 1) 001 y 010
- Filas del tercer grupo (dos 1) 011 y 101
- Filas del cuarto grupo (tres 1) 111
A continuación, deben buscarse todos los pares de filas que difieran en sólo una posición, obteniéndose a partir de cada par una nueva fila donde la parte común se mantiene y la posición que difiere se sustituye por -. De este modo se obtienen:
00- (000 y 001) 0-0 (000 y 010) 0-1 (001 y 011)
-01 (001 y 101) 01- (010 y 011) -11 (011 y 111)
1-1 (101 y 111)
Las nuevas filas obtenidas, se agrupan siguiendo el mismo criterio inicial (el número de unos). Toda fila de los grupos del paso anterior, que haya dado lugar a una nueva, es excluida de estos nuevos grupos, si alguna de las filas originales no fue objeto de simplificación, por no diferir en sólo una posición con ninguna de las demás, entonces pasa en la nueva distribución al grupo que le corresponde (este caso no se presenta en el ejemplo).
- Filas del primer grupo (ningún 1) 00- y 0-0
- Filas del segundo grupo (un 1) 0-1, -01 y 01-
- Filas del tercer grupo (dos 1) -11 y 1-1
Se repite el proceso de simplificación de filas, quedando:
0-- (00- y 01-) 0-- (0-0 y 0-1) --1 (0-1 y 1-1)
--1 (-01 y -11)
- Filas del primer grupo (ningún 1) 0--
- Filas del segundo grupo (un 1) --1
Finalmente se ha llegado a un estado en que no son posibles más simplificaciones, cada fila de esta última agrupación representa una conjunción de literales de la fórmula simplificada, un 0 simboliza la variable de la posición correspondiente negada, el 1 simboliza la variable de la posición correspondiente positiva, mientras – significa que la variable correspondiente no aparece en la conjunción. De esta manera 0-- da lugar a ¬p, y --1 da lugar a r, obteniéndose la fórmula ¬p ⅴ r.
Las conjunciones obtenidas en el proceso explicado, son denominadas implicantes primos, el ejemplo anterior, dio como resultado un conjunto de dos implicantes primos y ningún subconjunto propio de este cumple que su disyunción sea lógicamente equivalente a la fórmula original. Esto suele ocurrir en conjunto pequeños, pero en general, entre los implicantes primos obtenidos se puede encontrar un subconjunto (o varios) cuya disyunción sea equivalente a la fórmula original, evidentemente el subconjunto de menor cardinal que se obtenga será el que dé lugar a la fórmula mínima. A continuación, mediante un ejemplo, se ilustra la manera de encontrar este subconjunto de menor cardinal.
Se desea simplificar la fórmula:
(p ᴧ q ᴧ ¬r ᴧ s) ⅴ (p ᴧ q ᴧ r ᴧ ¬s) ⅴ (¬p ᴧ q ᴧ ¬r ᴧ s) ⅴ (¬p ᴧ q ᴧ r ᴧ s) ⅴ (p ᴧ q ᴧ r ᴧ s) ⅴ (p ᴧ ¬q ᴧ r ᴧ ¬s) ⅴ (p ᴧ ¬q ᴧ ¬r ᴧ s)
Las interpretaciones verdaderas aparecen en la siguiente tabla:
| p |
q |
r |
s |
| 0 |
1 |
0 |
1 |
| 0 |
1 |
1 |
1 |
| 1 |
0 |
0 |
1 |
| 1 |
0 |
1 |
0 |
| 1 |
1 |
0 |
1 |
| 1 |
1 |
1 |
0 |
| 1 |
1 |
1 |
1 |
Como resultado de aplicar el proceso explicado se obtienen los implicantes primos:
-1-1 1-10 1-01 111-
Para encontrar el subconjunto óptimo se utiliza la siguiente tabla:
| IMPLICANTES PRIMOS |
CONJUNCIONES DE LITERALES | |||||||
| 0101 |
0111 |
1001 |
1010 |
1101 |
1110 |
1111 | ||
| A |
-1-1 |
X |
X |
X |
X | |||
| B |
1-10 |
X |
X |
|||||
| C |
1-01 |
X |
X |
|||||
| D |
111- |
X |
X | |||||
| PROYECCION DE A B C y D |
X |
X |
X |
X |
X |
X |
X | |
Puede apreciarse que en las casillas donde aparece X es porque el implicante de la fila ha sido obtenido directa o indirectamente de la conjunción que encabeza la columna. En la última fila se marcan con X las columnas que tienen al menos una X en las filas anteriores, que deben ser todas. Todo implicante cuya fila pueda ser eliminada sin que por esto desaparezca una X de la última fila, es redundante por lo que puede omitirse en la disyunción resultado.
Para el ejemplo que se analiza, A no puede ser omitido, pues desaparece la X de la primera columna, omitir B provocaría lo mismo en la cuarta columna, por su parte la falta de C afectaría la tercera columna, pero D puede ser omitido sin afectar ninguna columna, por lo que lo implicantes A B y C son suficientes. Este análisis debe repetirse luego de omitir cada implicante, hasta que ya no sean posibles más omisiones.
De acuerdo a lo planteado la fórmula mínima para este ejemplo es:
(q ᴧ s) ⅴ (p ᴧ r ᴧ ¬s) ⅴ (p ᴧ ¬r ᴧ s)
