Diferencia entre revisiones de «Formas normales (Matemática)»
(Página creada con '{{Desarrollo}}{{Materia}} '''Formas Normales''': La relación de equivalencia establece para cada fórmula, una clase de equivalencia. Dentro de cada una de e...') |
|
(Sin diferencias)
| |
Revisión del 12:03 27 mar 2011
| ||
Formas Normales: 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.
Formas normales proposicionales.
Antes de definir lo que es una forma normal proposicional, es preciso establecer el concepto de literal.
definición. 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.
definición. 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.
definición. 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:
1.p
2.¬p ⅴ q
3.(¬p ᴧ q) ⅴ q
4. (q ᴧ r ᴧ ¬p) ⅴ (¬q ᴧ r) ⅴ (¬q ᴧ p)
Ej.: Las siguientes fórmulas se encuentran en forma normal conjuntiva.
1.p ᴧ r
2.p
3.(¬p ⅴ q) ᴧ (r ⅴ q)
4.(¬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.
definición. Se conoce como forma normal disyuntiva completa (fndc) a una disyunción de conjunciones elementales.
definición. Se conoce como forma normal conjuntiva completa (fndc) 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 ).
1.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:
Enlaces externos
http://www.buenastareas.com/temas/forma-normal-disyuntiva/0
