Disyuntiva perfecta forma normal

La forma normal disyuntiva perfecta (PDNF) es una de las formas de representar una función del álgebra de la lógica (función booleana) en forma de expresión lógica. Es un caso especial de DNF que cumple las siguientes tres condiciones [1] :

no tiene términos idénticos (conjunciones elementales);
no hay variables repetitivas en cada término;
cada término contiene todas las variables de las que depende la función booleana (cada variable se puede incluir en el término en forma directa o inversa).

Cualquier fórmula booleana que no sea idénticamente falsa puede reducirse a SDNF, y de manera única, es decir, para cualquier función satisfacible del álgebra lógica, existe su propio SDNF, y el único [2] .

Breve teoría

DNF es la "suma de productos", y la operación AND (conjunción) actúa como la operación de "multiplicación", y la operación OR (disyunción) actúa como la operación de "suma". Los factores son diversas variables, y se pueden incluir en el producto tanto en forma directa como inversa.

A continuación se muestra un ejemplo de un DNF:

$F(A,B,C,D,E)={\bar {A}}B+A{\bar {B}}E+B{\bar {C}}D.$

En términos generales, un DNF puede contener términos repetidos y cada término puede contener factores repetidos, por ejemplo:

$F(A,B,C,D,E)={\bar {A}}B{\bar {B}}+A{\bar {B}}EA+B{\bar {C}} D+B{\bar {C}}D.$

Desde un punto de vista matemático, tal clonación no tiene sentido, ya que en el álgebra de Boole, multiplicar cualquier expresión por sí misma y sumar la expresión a sí misma no cambia el resultado ( ), pero sumar una expresión con su propio inverso y multiplicar por su propia inversión da constantes ( ). En la última expresión, puede eliminar los términos y factores repetidos de la siguiente manera: $x+x=x;x\cdot x=x$ $x+{\bar {x}}=1;x\cdot {\bar {x}}=0$

$F(A,B,C,D,E)={\bar {A}}B{\bar {B}}+A{\bar {B}}EA+B{\bar {C}} D+B{\bar {C}}D={\bar {A}}\cdot (B{\bar {B)))+(AA)\cdot {\bar {B}}E+B{\bar {C}}D={\bar {A}}\cdot 0+A{\bar {B}}E+B{\bar {C}}D=A{\bar {B}}E+B{\ barra{C}}D.$

Por esta razón, los DNF con términos y factores repetidos generalmente se usan solo con fines auxiliares, por ejemplo, en la transformación analítica de expresiones.

SDNF es la forma canónica de representar una función booleana como DNF, en la que están prohibidas las repeticiones de términos y factores. Además, cada término debe contener todas las variables (en forma directa o inversa).

A continuación se muestra un ejemplo de SDNF:

$F(A,B,C,D,E)={\bar {A}}BCDE+A{\bar {B}}C{\bar {D}}E+AB{\bar {C} }D{\bar{E}}.$

El significado de SDNF es que

para cada función específica, su SDNF es único e inequívoco;
SDNF tiene una correspondencia uno a uno con la tabla de verdad de una función. Cada término en el SDNF corresponde a una fila en la tabla de verdad, donde la función es igual a uno. Así, el número de términos en SDNF es igual al número de valores unitarios que toma una función booleana en su dominio de definición;
SDNF se obtiene elementalmente de la tabla de verdad de la función;
SDNF es conveniente como expresión base para minimizar una función; es especialmente fácil encontrar términos adecuados para "pegarlos".

Ejemplo de búsqueda de SDNF

Para obtener el SDNF de una función, se requiere compilar su tabla de verdad . Por ejemplo, tome una de las tablas de verdad:

$x_{1}$	$x_{2}$	$x_{3}$	$f(x_{1},x_{2},x_{3})$
0	0	0	una
0	0	una	una
0	una	0	una
0	una	una	0
una	0	0	0
una	0	una	0
una	una	0	una
una	una	una	0

En las celdas del resultado , solo se marcan aquellas combinaciones que llevan la expresión lógica al estado de uno. Además, se consideran los valores de las variables, en los que la función es igual a 1. Si el valor de una variable es igual a 0, entonces se escribe con inversión. Si el valor de la variable es 1, entonces no hay inversión. $f(x_{1},x_{2},x_{3})$

La primera línea contiene 1 en el campo especificado. Se anotan los valores de las tres variables, estos son:

$x_{1}=0$
$x_{2}=0$
$x_{3}=0$

Los valores cero, aquí todas las variables están representadas por ceros, se escriben en la expresión final por el inverso de esta variable. El primer miembro del SDNF de la función considerada se ve así: ${\sobrelínea {x_{1}}}\cdot {\sobrelínea {x_{2}}}\cdot {\sobrelínea {x_{3}}}$

Variables de segundo miembro:

$x_{1}=0$
$x_{2}=0$
$x_{3}=1$

$x_{3}$ en este caso se representará sin inversión: ${\sobrelínea {x_{1}}}\cdot {\sobrelínea {x_{2}}}\cdot x_{3}$

Таким образом анализируются все ячейки . Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов ( элементарный ). $f(x_{1},x_{2},x_{3})$

El DNF perfecto de esta función es:

$f(x_{1},x_{2},x_{3})=({\overline {x_{1))}\land {\overline {x_{2))}\land {\overline { x_{3}}})\vee ({\overline {x_{1}}}\land {\overline {x_{2}}}\land x_{3})\vee ({\overline {x_{1} }}\land x_{2}\land {\overline {x_{3}}})\vee (x_{1}\land x_{2}\land {\overline {x_{3}}})$

Véase también

Notas

↑ Vinogradova MS, Tkachev S.B. Funciones booleanas. - M. : Editorial de MSTU im. NORDESTE. Bauman, 2007. - 32 págs.
↑ Lógica matemática . - Perm: Editorial de PSTU, 1998. - 17 p. Archivado el 9 de abril de 2016 en Wayback Machine .

$x_{1}$	$x_{2}$	$x_{3}$	$f(x_{1},x_{2},x_{3})$
0	0	0	una
0	0	una	una
0	una	0	una
0	una	una	0
una	0	0	0
una	0	una	0
una	una	0	una
una	una	una	0

$x_{1}$	$x_{2}$	$x_{3}$	$f(x_{1},x_{2},x_{3})$
0	0	0	una
0	0	una	una
0	una	0	una
0	una	una	0
una	0	0	0
una	0	una	0
una	una	0	una
una	una	una	0

$x_{1}$	$x_{2}$	$x_{3}$	$f(x_{1},x_{2},x_{3})$
0	0	0	una
0	0	una	una
0	una	0	una
0	una	una	0
una	0	0	0
una	0	una	0
una	una	0	una
una	una	una	0