Introduzcamos el concepto de disyunción elemental.
Una disyunción elemental es una expresión de la forma
La forma normal conjuntiva (CNF) de una función lógica es la conjunción de cualquier conjunto finito de disyunciones elementales distintas por pares. Por ejemplo, funciones lógicas.
son conjunciones de disyunciones elementales. Por lo tanto, se escriben en forma normal conjuntiva.
Una función lógica arbitraria dada por una expresión analítica se puede reducir a CNF realizando las siguientes operaciones:
Usar la regla de inversión si la operación de negación se aplica a una expresión lógica;
Usos del axioma de distributividad con respecto a la multiplicación:
Usando la operación de absorción:
Excepciones en disyunciones de variables repetidas o sus negaciones;
Eliminación de todas las disyunciones elementales idénticas, excepto una;
Borrar todas las disyunciones que incluyan simultáneamente una variable y su negación.
La validez de las operaciones enumeradas se deriva de los axiomas básicos y las relaciones de identidad del álgebra lógica.
Una forma normal conjuntiva se llama perfecta si cada disyunción elemental incluida en ella contiene en forma directa o inversa todas las variables de las que depende la función.
La transformación de CNF a CNF perfecto se lleva a cabo realizando las siguientes operaciones:
Las adiciones a cada disyunción elemental de conjunciones de variables y sus negaciones, si no están comprendidas en esta disyunción elemental;
Uso del axioma de distributividad;
Eliminación de todas las disyunciones elementales idénticas, excepto una.
Cualquier función lógica se puede representar en un CNF perfecto excepto
idénticamente igual a uno (). Una propiedad distintiva de un CNF perfecto es que la representación de una función lógica en él es única.
Las disyunciones elementales incluidas en una función CNF perfecta se denominan constituyentes cero. Cada componente cero en un CNF perfecto desaparece en el único conjunto de valores variables, que es el conjunto cero de la función. En consecuencia, el número de conjuntos cero de una función lógica coincide con el número de componentes cero incluidos en su CNF perfecto.
La función lógica cero constante en CNF perfecto está representada por la conjunción 2n constituyente de cero. Formulemos una regla para compilar el SKNF de una función lógica según la tabla de correspondencia.
Para cada línea de la tabla de correspondencias en la que la función es igual a cero, se compila una disyunción elemental de todas las variables. La disyunción incluye la propia variable, si su valor es igual a cero, o la negación, si su valor es igual a uno. Las disyunciones elementales resultantes se combinan mediante el signo de la conjunción.
Ejemplo 3.4. Para la función lógica z(x) dada por la tabla de búsqueda 2.2, definimos la forma conjuntiva perfecta.
Para la primera fila de la tabla, que corresponde al conjunto de funciones cero 000, encontramos el componente nulo. Realizando operaciones similares para la segunda, tercera y quinta filas, determinamos la función CNF perfecta deseada:
Cabe señalar que para funciones cuyo número de conjuntos de unidades excede el número de conjuntos de cero, es más compacto escribirlos en forma de SKNF y viceversa.
base estándar. Las fórmulas elementales son literales. Conjunción elemental (disyunción). Forma normal disyuntiva (conjuntiva) y forma perfecta. Teorema: cualquier función booleana distinta de 0 (de 1) se puede representar como SDNF (SKNF). Completitud de la base estándar. Ejemplos de bases completas: base de Zhegalkin, trazo de Sheffer, flecha de Pierce.
Base estándar es un conjunto de tres operaciones iniciales de álgebra booleana: suma (unión), multiplicación (intersección) y negación.
Aquí llamaremos literal variable x o su negación x y denotamos xˆ. Intersección booleana de múltiples literales definidos por diferentes variables, es decir expresión de la forma X = xˆ 1 xˆ 2 . . . xˆ l, se llama conjunción elemental . El requisito de que todas las variables sean diferentes se debe a lo siguiente. Si una conjunción contiene varios literales idénticos, entonces debido a la conmutatividad, asociatividad e idempotencia de la conjunción, pasando a una fórmula equivalente, podemos dejar solo un literal (por ejemplo, x 1 x 1 = x 1). Si la conjunción incluye una variable y su negación, entonces la fórmula es equivalente a la constante 0, ya que x x = 0 y para cualquier fórmula Y tenemos Y x x = 0.
La disyunción de varias conjunciones elementales se llama forma normal disyuntiva , o DNF . Por ejemplo,
X 1 X 3 + X 2 X 3 X 4 + X 1 X 2 X 3 X 5 .
Si la composición de variables en cada conjunción elemental de un DNF dado es la misma, entonces el DNF se llama Perfecto . El ejemplo dado es un DNF que no es perfecto. Por el contrario, la fórmula
x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4
es la forma perfecta.
Dado que en el álgebra booleana la suma y la multiplicación son operaciones simétricas y uno siempre puede interpretar la suma como multiplicación y la multiplicación como suma, también existe un concepto dual: forma normal conjuntiva (KNF ), que es una conjunción de disyunciones elementales, y forma conjuntiva perfecta (SKNF ). Del principio de dualidad para semianillos simétricos se sigue que cualquier enunciado sobre DNF corresponde a un enunciado dual sobre CNF, que se obtiene reemplazando la suma (disyunción) por multiplicación, la multiplicación (conjunción) por suma, constante 0 por constante 1, constante 1 por constante 0, relaciones de orden por dual (inverso) en orden. Por lo tanto, más adelante nos centraremos en estudiar solo DNF.
Teorema 1.4. Cualquier función booleana que no sea la constante 0 se puede representar como un SDNF.
◀Convengamos en que x σ significa la fórmula x si σ = 1 y la fórmula x si σ = 0. Sea la función f(y 1 , . . . , yn) el valor 1 en el vector (t 1 , . . . , tn ) (tal vector se llama unidad constituyente ). Entonces, la conjunción elemental también toma el valor 1 en este conjunto, pero desaparece en todos los demás vectores booleanos de n dimensiones. Considere la fórmula
en el que la suma (unión) se extiende sobre todos aquellos conjuntos (t 1 , . . . , t n) de valores argumentales sobre los que función dada toma el valor 1. Tenga en cuenta que el conjunto de tales conjuntos no está vacío, por lo que la suma contiene por lo menos un término.
Es fácil ver que la fórmula Φ se convierte en 1 para aquellos, y solo para aquellos valores de las variables, para los cuales la función considerada se convierte en 1. Por lo tanto, la fórmula Ψ representa la función f.
Corolario 1.1. La base estándar está completa.
◀ De hecho, si una función no es un 0 constante, entonces puede representarse como un SDNF, que es una fórmula sobre una base estándar. La constante 0 se puede representar, por ejemplo, mediante la fórmula f(x 1 , x 2 , . . . , x n) = x 1 x 1 .
Ejemplo 1.2. Considere una función de tres variables m(x 1 , x 2 , x 3) (Tabla 1.4), llamada función mayoritaria ̆. Esta función se evalúa como 1 si más de la mitad de sus argumentos tienen el valor 1. Por lo tanto, a menudo se la llama función de votación. Construyamos un SDNF para ello.
La integridad de la base estándar permite seleccionar otros sistemas completos de funciones. La completitud del conjunto F se puede establecer a partir de las siguientes consideraciones. Suponga que cada una de las tres funciones buzzis estándar se puede representar mediante una fórmula sobre F . Entonces, en virtud del Teorema 1.3, la otredad de F será completa.
Ejemplo 1.3. El conjunto de operaciones módulo 2 suma, multiplicación y constante 1 se llama la base de Zhegalkin . Módulo 2 La suma y la multiplicación son las operaciones básicas del anillo Z2, las expresiones compuestas con su ayuda son polinomios sobre el anillo Z2. La constante 1 en este caso es necesaria para escribir el miembro libre. Como xx \u003d x, todos los factores en el polinomio tienen un grado 1. Por lo tanto, al escribir un polinomio, puede prescindir del concepto de grado. Ejemplos de fórmulas sobre la base de Zhegalkin:
xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.
Cualquier fórmula de este tipo se denomina polinomio de Zhegalkin. De hecho, el polinomio de Zhegalkin es un polinomio sobre el anillo Z2.
Es fácil construir fórmulas sobre la base de Zhegalkin, representando las operaciones de suma y negación de la base estándar (la multiplicación de dos bases es común):
x+y=x⊕y⊕xy, x=x⊕1.
Por lo tanto, la base de Zhegalkin es un conjunto completo.
Se puede demostrar que para cualquier función booleana el polinomio de Zhegalkin está definido de forma única
(más precisamente, hasta el orden de los términos). Los coeficientes del polinomio de Zhegalkin con un pequeño número de variables se pueden encontrar por el método de coeficientes indeterminados.
Ejemplo 1.4. Considere un conjunto de una sola función: el trazo de Schaeffer*. Este conjunto está completo, que se deriva de las siguientes identidades fácilmente verificables:
x=x|x, xy=x|y=(x|y)|(x|y), x+y=x |y=(x|x)|(y|y).
Ejemplo 1.5. La base que consta de una sola función, la flecha Pierce, también está completa. La verificación de esto es similar al caso del ictus de Schaeffer. Sin embargo, esta conclusión también puede extraerse sobre la base del principio de dualidad para semianillos simétricos.
*El trazo de Schaffer es una operación binaria, pero no asociativa. Por lo tanto, al usar la forma infija, debe tener cuidado: el resultado depende del orden en que se realizan las operaciones. En este caso, se recomienda especificar explícitamente el orden de las operaciones usando paréntesis, por ejemplo, escriba (x | y) | z, no x | y | z, aunque ambas formas son equivalentes.
Ejemplo. Encuentra fórmulas CNF 
~ 
~
La forma normal disyuntiva perfecta de SDNF se puede construir utilizando el siguiente algoritmo:
1. = 1. Algoritmo DNF
2. = 2. Algoritmo DNF
3. = 3. Algoritmo DNF
4. = 4. Algoritmo DNF
5. Omita términos idénticos falsos, es decir, términos de la forma
6. Completa los términos restantes con las variables que faltan
7. Repita el punto 4.
Ejemplo. Encuentra fórmulas sdnf.
~
El siguiente esquema se puede utilizar para construir el SKNF:
Ejemplo. Encuentra fórmulas sdnf.
~
Se sabe (Teoremas 2.11, 2.12) que SDNF y SKNF están definidos únicamente por la fórmula y, por lo tanto, pueden construirse de acuerdo con la tabla de verdad de la fórmula.
El esquema para construir SDNF y SKNF de acuerdo con la tabla de verdad se da a continuación, para la fórmula ~ :
 ~
| ||||
| 1 0 1 0 1 1 0 1 | SDNF; SKNF. |
2.2. Ejercicio.
2.2.1 A continuación se muestran expresiones lógicas. Simplifique las expresiones de su opción tanto como sea posible utilizando las leyes de la lógica de Boole. Luego, usando tablas de verdad, compare su expresión simplificada con la original.
2.2.2. Averigüe la cuestión de la equivalencia de f 1 y f 2 reduciéndolos a SDNF (Tabla 1).
2.2.3. Encuentre la función dual para f 3 según el principio generalizado y booleano (Tabla 1). Compara los resultados.
| № | f1 | f2 | F 3 |
 | |||
 |
|||
 | |||
 | |||
 | |||
 |  |
||
 |  |
||
 |
|||
 | |||
 | |||
 |
|||
 | |||
 |  |
||
 | |||
 |
2.3. Cuestiones de control.
2.3.1. Defina una declaración.
2.3.2. Enumere las operaciones básicas en la declaración.
2.3.3. ¿Qué es una tabla de verdad?
2.3.4. Cree tablas de verdad para las siguientes fórmulas:
~ ~ 
~ ;
2.3.5. Teniendo en cuenta las convenciones sobre el orden de las operaciones, omitir los corchetes "extra" y el signo "" en las fórmulas:
;
2.3.6. Aplicando transformaciones equivalentes, demuestre la idéntica verdad de las fórmulas:
2.3.7. Encuentra fórmulas duales:
)
2.3.8. Reduzca las siguientes fórmulas a la forma perfecta DNF (SDNF):
~
2.3.9. Convierta las siguientes fórmulas a la forma perfecta CNF (SKNF):
~
Tema:"Minimización funciones booleanas. Lógica"
Objetivo: Adquisición de habilidades prácticas en el trabajo con métodos de minimización de funciones booleanas.
3.1. Información teórica.
Formularios Mínimos
Como se muestra en , cualquier función booleana se puede representar en forma normal perfecta (disyuntiva o conjuntiva). Además, tal representación es el primer paso en la transición de una definición tabular de una función a su expresión analítica. En el futuro, partiremos de la forma disyuntiva, y los resultados correspondientes para la forma conjuntiva se obtienen sobre la base del principio de dualidad.
El problema canónico de sintetizar circuitos lógicos en base booleana se reduce a minimizar las funciones booleanas, es decir a representarlos en forma normal disyuntiva, que contiene el menor número de letras (variables y sus negaciones). Tales formas se llaman mínimas. En la síntesis canónica, se supone que ambas señales y sus inversiones se alimentan a las entradas del circuito.
La fórmula presentada en la forma normal disyuntiva se simplifica mediante la aplicación repetida de la operación de pegado y la operación de absorción y (las identidades duales para la forma normal conjuntiva son: y). Aquí, por y puede entenderse cualquier fórmula del álgebra booleana. Como resultado, llegamos a tal expresión analítica cuando ya no son posibles más transformaciones, es decir obtenemos un formulario de callejón sin salida.
Entre las formas sin salida también hay una forma disyuntiva mínima, y puede que no sea única. Para asegurarse de que este formulario sin salida sea mínimo, debe encontrar todos los formularios sin salida y compararlos por la cantidad de letras que contienen.
Sea, por ejemplo, la función dada en forma disyuntiva normal perfecta:
Agrupando los miembros y aplicando la operación de encolado, tenemos .
Con otro método de agrupación, obtenemos:
Ambas formas de callejón sin salida no son mínimas. Para obtener la forma mínima, debe adivinar para repetir un término en la fórmula original (esto siempre se puede hacer, ya que). En el primer caso, dicho miembro puede ser . Entonces . Sumando el término , obtenemos: . Después de revisar todas las opciones posibles, podemos asegurarnos de que las dos últimas formas son mínimas.
Trabajar con fórmulas a este nivel es como vagar en la oscuridad. El proceso de búsqueda de formas mínimas se vuelve más visual y útil si se utilizan algunas representaciones gráficas y analíticas y símbolos especialmente diseñados para este propósito.
Cubo multidimensional
A cada vértice de un cubo bidimensional se le puede asignar una unidad constituyente. Por lo tanto, el subconjunto de vértices marcados es un mapeo en el cubo bidimensional de una función booleana de variables en forma normal disyuntiva perfecta. En la fig. 3.1 muestra tal mapeo para la función de la Sección 3.7.
Fig.3.1 Visualización en un cubo tridimensional de una función presentada en SDNF
Para desplegar una función de variables presentada en cualquier forma normal disyuntiva, es necesario establecer una correspondencia entre sus minitérminos y los elementos del cubo -dimensional.
El minitérmino de rango (-1) se puede considerar como el resultado de pegar dos minitérminos de rango -ésimo (componente de la unidad), es decir 
, En un cubo bidimensional, esto corresponde a reemplazar dos vértices, que difieren solo en los valores de la coordenada que conecta estos vértices, con una arista (se dice que la arista cubre los vértices incidentes a ella). Así, los minitérminos de orden (-1) corresponden a las aristas del cubo bidimensional. De manera similar, los minitérminos de (-2) orden corresponden a las caras del cubo -dimensional, cada una de las cuales cubre cuatro vértices (y cuatro aristas).
Los elementos de un cubo -dimensional caracterizados por dimensiones se denominan -cubos. Así, los vértices son 0-cubos, las aristas son 1-cubos, las caras son 2-cubos, y así sucesivamente. Generalizando el razonamiento anterior, podemos suponer que un minitérmino de rango ()-ésimo en forma normal disyuntiva para una función de variables está mapeado por un -cubo, y cada -cubo cubre todos aquellos -cubos de menor dimensión que están asociados con sus vértices. Como ejemplo, en la fig. 3.2 muestra el mapeo de una función de tres variables. Aquí los minitérminos y corresponden a 1-cubos (), y los minitérminos están representados por 2-cubos ().
Fig.3.2 Cobertura de funciones 
Entonces, cualquier forma normal disyuntiva se muestra en un cubo -dimensional por un conjunto de -cubos que cubren todos los vértices correspondientes a los constituyentes de la unidad (0-cubo). La afirmación inversa también es cierta: si una cierta colección de -cubos cubre el conjunto de todos los vértices correspondientes a valores unitarios de una función, entonces la disyunción de minitérminos correspondientes a estos -cubos es una expresión de esta función en forma normal disyuntiva . Se dice que tal colección de -cubos (o minitérminos correspondientes a ellos) forma una cubierta de una función.
El deseo de una forma mínima se entiende intuitivamente como una búsqueda de tal cubierta, cuyo número de cubos sería menor y sus dimensiones serían mayores. La cobertura correspondiente a la forma mínima se denomina cobertura mínima. Por ejemplo, para la función de cobertura de la Fig. 3.3 corresponde a las formas mínimas 
y 
.
Arroz. 3.3 Coberturas de funciones.
izquierda – ; a la derecha –
La visualización de una función en un cubo bidimensional es clara y sencilla cuando . Se puede dibujar un cubo de cuatro dimensiones como se muestra en la figura. 3.4, que muestra una función de cuatro variables y su cobertura mínima correspondiente a la expresión 
. El uso de este método requiere construcciones tan complejas que se pierden todas sus ventajas.
Arroz. 3.4 Visualización de funciones en un cubo de cuatro dimensiones
Mapas Karnot
Otro método para graficar funciones booleanas utiliza cartas de carnot, que son tablas de búsqueda especialmente organizadas. Las columnas y filas de la tabla corresponden a todos los conjuntos posibles de valores para dos variables como máximo, y estos conjuntos están dispuestos en tal orden que cada conjunto subsiguiente difiere del anterior en el valor de una sola de las variables. Debido a esto, las celdas adyacentes de la tabla, tanto horizontal como verticalmente, difieren en el valor de una sola variable. Las celdas ubicadas en los bordes de la tabla también se consideran adyacentes y tienen esta propiedad. En la fig. 3.5 muestra mapas de Karnaugh para dos, tres, cuatro variables.
 |
|||||
 |
|||||
 |
|||||
Arroz. 3.5 Mapas de Karnot para dos, tres y cuatro variables
Como en las tablas de verdad ordinarias, las celdas de los conjuntos en los que la función toma el valor 1 se rellenan con unos (los ceros no suelen caber, corresponden a celdas vacías). Por ejemplo, en la fig. 3.6, a muestra el mapa de Karnaugh para la función, cuya visualización en un cubo de cuatro dimensiones se da en la fig. 3.4. Para simplificar, las filas y columnas correspondientes a los valores 1 para alguna variable se resaltan con una llave con la designación de esta variable.
 |
|||
 |
|||
Arroz. 3.6 Visualización en el gráfico de Carnot de una función de cuatro variables
(a) y su cobertura mínima (b)
Entre asignaciones de funciones en norte cubo bidimensional y en el mapa de Karnaugh hay una correspondencia biunívoca. En el mapa de Carnot s-cubo corresponde a un conjunto de 2 celdas vecinas colocadas en una fila, columna, cuadrado o rectángulo (teniendo en cuenta la proximidad de los bordes opuestos del mapa). Por lo tanto, todas las disposiciones establecidas en el párrafo anterior (ver párrafo cubo multidimensional) son válidos para mapas de Carnot. Entonces, en la fig. 3.6, B se muestra la cobertura de unidades de mapa correspondientes a la forma disyuntiva mínima 
la función en cuestión.
La lectura de los minitérminos del mapa de Karnot se realiza de acuerdo con una regla simple. Las células que forman s-cubo, dar miniter (n–s) rango, que incluye aquellos (n–s) variables que mantienen los mismos valores en este s-cubo, donde el valor 1 corresponde a las propias variables, y el valor 0 corresponde a sus negaciones. Variables que no conservan sus valores en s-cubo, están ausentes en el minitherm. Diferentes formas de lectura conducen a diferentes representaciones de la función en forma normal disyuntiva (la más a la derecha es mínima) (Fig. 3.7).
 |  |
||||||||
 |
|||||||||
El uso de mapas de Karnaugh requiere construcciones más simples en comparación con la visualización en norte-cubo dimensional, especialmente en el caso de cuatro variables. Para mostrar funciones de cinco variables, se usan dos mapas de Karnot para cuatro variables, y para una función de seis variables, se usan cuatro de esos mapas. Con un mayor aumento en el número de variables, los mapas de Karnot se vuelven prácticamente inutilizables.
conocido en la literatura las cartas de veitch difieren solo en un orden diferente de los conjuntos de valores de las variables y tienen las mismas propiedades que los mapas de Karnaugh.
complejo de cubos
El fracaso de los métodos gráficos para un gran número de variables se compensa con varios métodos analíticos para representar funciones booleanas. Una de estas representaciones es complejo de cubos, que utiliza la terminología de un espacio lógico multidimensional en combinación con un simbolismo especialmente diseñado.
). Los 0-cubos correspondientes a los constituyentes de la unidad están representados por conjuntos de valores variables en los que la función es igual a la unidad. obviamente en el registro
Arroz. 3.8 Complejo de cubos de funciones de tres variables ( a) y su representación simbólica ( B)
El complejo de formas de cubos máxima cobertura de funciones. excluyendo todos aquellos s-cubos que son cubiertos por cubos de mayor dimensión, obtenemos recubrimientos correspondientes a formas sin salida. Entonces, para el ejemplo bajo consideración (Fig. 3.8), tenemos una tapa sin salida
,
que corresponde a la función 
. En este caso, esta cobertura también es mínima.
Para dos funciones booleanas, la operación de disyunción corresponde a la unión de sus complejos cúbicos y la operación de conjunción a la intersección de sus complejos cúbicos. La negación de una función corresponde a la suma de un complejo de cubos, es decir, y está determinada por todos los vértices en los que la función toma el valor 0. Así, existe una correspondencia biunívoca (isomorfismo) entre el álgebra de Funciones booleanas y conjuntos booleanos que representan complejos de cubos.
La representación de una función en forma de complejos de cubos es menos visual, pero sus ventajas más importantes son que se eliminan las restricciones en el número de variables y se facilita la codificación de la información al utilizar computadoras.
Minimizar funciones booleanas
Formulación del problema. La minimización de un esquema en base booleana se reduce a encontrar la forma disyuntiva mínima, que corresponde a la cobertura mínima. El número total de letras incluidas en el formulario normal se expresa por el precio de cobertura 
, donde es el número de - cubos que forman la cobertura de la función dada en n variables. La cobertura mínima se caracteriza por el valor más bajo de su precio.
Por lo general, el problema de minimización se resuelve en dos pasos. En primer lugar, se busca una cubierta reducida que incluya todos los cubos de máxima dimensión, pero que no contenga ningún cubo cubierto por ningún cubo de esta cubierta. La forma normal disyuntiva correspondiente se llama reducida, y sus minitérminos se llaman implicantes simples. Para esta función, la cobertura reducida es la única, pero puede resultar redundante debido a que algunos de los cubos están cubiertos por colecciones de otros cubos.
En el segundo paso, se lleva a cabo la transición de formas normales disyuntivas reducidas a sin salida, de las cuales se eligen formas mínimas. Las formas sin salida se forman excluyendo todos los cubos redundantes de la cubierta reducida, sin la cual el conjunto restante de cubos todavía forma una cubierta de una función dada, pero con la exclusión adicional de cualquiera de los cubos, ya no cubre el conjunto de todos. vértices correspondientes a valores unitarios de la función, es decir, deja de ser una tapa.
Un cubo de cobertura reducida que cubre vértices de una función dada que no están cubiertos por ningún otro cubo no puede ser redundante y siempre estará incluido en la cobertura mínima. Tal cubo, así como el implicante que le corresponde, se llama extremal (implicante esencial), y los vértices cubiertos por él se llaman vértices cancelados. El conjunto de extremos forma el núcleo de la cobertura, es claro que al pasar de una cobertura reducida a una cobertura mínima, en primer lugar, se deben seleccionar todos los extremos. Si el conjunto de extremos no forma una cubierta, entonces se complementa con una cubierta por cubos de la cubierta reducida.
Las definiciones dadas se ilustran en la fig. 3.9, donde la cobertura reducida (ver Fig. 3.9a, ) y las coberturas mínimas (Fig. 3.9b) y (ver Fig. 3.9b) se expresan de la siguiente manera.
forma normal fórmula lógica no contiene signos de implicación, equivalencia y negación de fórmulas no elementales.
La forma normal existe en dos formas:
forma normal conjuntiva (CNF)-- conjunción de varias disyunciones, por ejemplo, $\left(A\vee \overline(B)\vee C\right)\wedge \left(A\vee C\right)$;
forma normal disyuntiva (DNF)-- disyunción de varias conjunciones, por ejemplo, $\left(A\wedge \overline(B)\wedge C\right)\vee \left(B\wedge C\right)$.
SKNF
Forma normal conjuntiva perfecta (SKNF) es un CNF que cumple tres condiciones:
no contiene disyunciones elementales idénticas;
ninguna de las disyunciones contiene las mismas variables;
cada disyunción elemental contiene todas las variables en el CNF dado.
Cualquier fórmula booleana que no sea idénticamente verdadera se puede representar en SKNF.
Reglas para construir SKNF de acuerdo con la tabla de verdad
Para cada conjunto de variables para las que la función es 0, se registra la suma, y las variables que tienen un valor de 1 se toman con una negación.
SDNF
Forma normal disyuntiva perfecta (PDNF) es un DNF que cumple tres condiciones:
no contiene conjunciones elementales idénticas;
ninguna de las conjunciones contiene las mismas variables;
cada conjunción elemental contiene todas las variables del DNF dado, además, en el mismo orden.
Cualquier fórmula booleana que no sea idénticamente falsa se puede representar en SDNF, además, de forma única.
Reglas para construir SDNF según la tabla de verdad
Para cada conjunto de variables en el que la función es igual a 1, se escribe el producto, y las variables que tienen valor 0 se toman con negación.
Ejemplos de búsqueda de SKNF y SDNF
Ejemplo 1
Escribe una función lógica según su tabla de verdad:
Foto 1.
Solución:
Usemos la regla para construir SDNF:
Figura 2.
Obtenemos SDNF:
Usemos la regla de construcción SKNF.
La forma normal conjuntiva es conveniente para las demostraciones automáticas de teoremas. Cualquier fórmula booleana se puede reducir a CNF. Para ello, puedes utilizar: la ley de la doble negación, la ley de de Morgan, la distributividad.
YouTube enciclopédico
-
1 / 5
Fórmulas en KNF:
¬ UN ∧ (B ∨ C) , (\displaystyle \neg A\cuña (B\vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E) , (\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge ( D\vee\neg E),) A ∧ B . (\displaystyle A\cuña B.)Fórmulas no en KNF:
¬ (B ∨ C), (\displaystyle \neg (B\vee C),) (A ∧ B) ∨ C , (\displaystyle (A\wedge B)\vee C,) UN ∧ (B ∨ (D ∧ E)) . (\displaystyle A\cuña (B\vee (D\cuña E)).)Pero estas 3 fórmulas no son equivalentes en CNF a las siguientes fórmulas en CNF:
¬ B ∧ ¬ C , (\displaystyle \neg B\cuña \neg C,) (A ∨ C) ∧ (B ∨ C) , (\displaystyle (A\vee C)\cuña (B\vee C),) UN ∧ (segundo ∨ re) ∧ (segundo ∨ mi) . (\displaystyle A\cuña (B\vee D)\cuña (B\vee E).)Construcción de CNF
Algoritmo para construir CNF
1) Deshágase de todas las operaciones lógicas contenidas en la fórmula, reemplazándolas por las principales: conjunción, disyunción, negación. Esto se puede hacer usando fórmulas equivalentes:
UN → segundo = ¬ UN ∨ segundo , (\displaystyle A\rightarrow B=\neg A\vee B,) UN ↔ segundo = (¬A ∨ segundo) ∧ (UN ∨ ¬B) . (\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \neg B).)2) Reemplazar el signo de negación, referido a la expresión completa, por signos de negación, relacionados con enunciados de variables individuales, con base en las fórmulas:
¬ (A ∨ B) = ¬ A ∧ ¬ B , (\displaystyle \neg (A\vee B)=\neg A\cuña \neg B,) ¬ (UN ∧ segundo) = ¬ UN ∨ ¬ segundo . (\displaystyle \neg (A\cuña B)=\neg A\vee \neg B.)3) Deshazte de los signos negativos dobles.
4) Aplicar, en su caso, a las operaciones de conjunción y disyunción las propiedades de distributividad y fórmulas de absorción.
Un ejemplo de construcción de un CNF
Reduzcamos la fórmula a CNF
F = (X → Y) ∧ ((¬Y → Z) → ¬X) . (\displaystyle F=(X\rightarrow Y)\wedge ((\neg Y\rightarrow Z)\rightarrow \neg X).)Transformemos la fórmula F (\ estilo de visualización F) a una fórmula que no contiene → (\ estilo de visualización \ flecha derecha):
F = (¬X ∨ Y) ∧ (¬ (¬Y → Z) ∨ ¬X) = (¬X ∨ Y) ∧ (¬ (¬ ¬Y ∨ Z) ∨ ¬X) . (\displaystyle F=(\neg X\vee Y)\cuña (\neg (\neg Y\rightarrow Z)\vee \neg X)=(\neg X\vee Y)\cuña (\neg (\neg \ neg Y\vee Z)\vee \neg X).)En la fórmula resultante, trasladamos la negación a las variables y reducimos las dobles negaciones:
F = (¬X ∨ Y) ∧ ((¬Y ∧ ¬Z) ∨ ¬X) . (\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X).)Por ejemplo, la siguiente fórmula está escrita en 2-CNF:
(A ∨ B) ∧ (¬B ∨ C) ∧ (B ∨ ¬C) . (\displaystyle (A\lor B)\land (\neg B\lor C)\land (B\lor \neg C).)- En contacto con 0
- Google Mas 0
- OK 0
- Facebook 0
