Escaleras. Grupo de entrada. Materiales. Puertas. Cerraduras. Diseño

Definición 1.Monomio conjuntivo (conjunción elemental) de variables es la conjunción de estas variables o sus negaciones.

Por ejemplo, es una conjunción elemental.

Definición 2.Monomio disyuntivo (disyunción elemental) de variables es la disyunción de estas variables o sus negaciones.

Por ejemplo, es una disyunción elemental.

Definición 3. Una fórmula que es equivalente a una fórmula de álgebra proposicional dada y es una disyunción de monomios conjuntivos elementales se llama forma normal disyuntiva(DNF) de esta fórmula.

Por ejemplo,– Abandono.

Definición 4. Una fórmula que es equivalente a una fórmula de álgebra proposicional dada y es una conjunción de monomios disyuntivos elementales se llama forma normal conjuntiva(CNF) de esta fórmula.

Por ejemplo, – KNF.

Para cada fórmula de álgebra proposicional se puede encontrar un conjunto de formas normales disyuntivas y conjuntivas.

Algoritmo para construir formas normales.

Usando las equivalencias del álgebra lógica, reemplaza todas las operaciones básicas en la fórmula: conjunción, disyunción, negación:

Deshazte de los dobles negativos.

Aplicar, si es necesario, las propiedades de las fórmulas de distributividad y absorción a las operaciones de conjunción y disyunción.

2.6. Formas normales disyuntivas perfectas y conjuntivas perfectas

Cualquier función booleana puede tener muchas representaciones en forma de DNF y CNF. Un lugar especial entre estas representaciones lo ocupan el DNF perfecto (SDNF) y el CNF perfecto (SCNF).

Definición 1. Forma normal disyuntiva perfecta(SDNF) es un DNF en el que cada monomio conjuntivo contiene cada variable del conjunto exactamente una vez, ya sea él mismo o su negación.

Estructuralmente, el SDNF para cada fórmula de álgebra proposicional reducida a un DNF se puede definir de la siguiente manera:

Definición 2. Forma normal disyuntiva perfecta(SDNF) de una fórmula de álgebra proposicional se llama DNF, que tiene las siguientes propiedades:

Definición 3. Forma normal conjuntiva perfecta(SCNF) es un CNF en el que cada monomio disyuntivo contiene cada variable del conjunto exactamente una vez, y aparece él mismo o su negación.

Estructuralmente, el SCNF para cada fórmula de álgebra proposicional reducida al CNF se puede definir de la siguiente manera.

Definición 4. Forma normal conjuntiva perfecta(SCNF) de una fórmula de álgebra proposicional dada se denomina CNF y satisface las siguientes propiedades.

Teorema 1. Cada función booleana de variables que no sea idénticamente falsa se puede representar en SDNF y de una manera única.

Métodos para encontrar SDNF

1er método

2do método

seleccione las líneas donde la fórmula toma el valor 1;

componemos una disyunción de conjunciones con la condición de que si una variable se incluye en la conjunción con un valor de 1, entonces escribimos esta variable si tiene un valor de 0, entonces su negación; Obtenemos SDNF.

Teorema 2. Cada función booleana de variables que no sea idénticamente verdadera se puede representar en SCNF y de una manera única.

Métodos para encontrar SCNF

1er método– utilizando transformaciones equivalentes:

2do método– usando tablas de verdad:

seleccione las líneas donde la fórmula toma el valor 0;

componemos una conjunción de disyunciones con la condición de que si una variable se incluye en la disyunción con un valor de 0, entonces escribimos esta variable si tiene un valor de 1, entonces su negación; Obtenemos SKNF.

Ejemplo 1. Construir funciones CNF.

Solución

Eliminemos el conectivo "" usando las leyes de transformación de variables:

= /leyes de Morgan y doble negación/ =

/leyes distributivas/ =

Ejemplo 2. Dale la fórmula a DNF.

Solución

Expresemos operaciones lógicas usando y:

= /clasifiquemos la negación como variables y reduzcamos los dobles negativos/ =

= /ley de distributividad/ .

Ejemplo 3. Escribe la fórmula en DNF y SDNF.

Solución

Utilizando las leyes de la lógica, reducimos esta fórmula a una forma que contiene sólo disyunciones de conjunciones elementales. La fórmula resultante será el DNF deseado:

Para construir el SDNF, creemos una tabla de verdad para esta fórmula:

Marcamos aquellas filas de la tabla en las que la fórmula (última columna) toma el valor 1. Para cada una de esas filas, escribimos una fórmula que sea verdadera para el conjunto de variables de esta fila:

línea 1: ;

línea 3: ;

línea 5: .

La disyunción de estas tres fórmulas tomará el valor 1 sólo en los conjuntos de variables de las líneas 1, 3, 5 y, por tanto, será la forma normal disyuntiva perfecta deseada (PDNF):

Ejemplo 4. Lleve la fórmula a SKNF de dos maneras:

a) utilizar transformaciones equivalentes;

b) usar una tabla de verdad.

Solución:

Transformemos la segunda disyunción elemental:

La fórmula se ve así:

b) elabora una tabla de verdad para esta fórmula:

Marcamos aquellas filas de la tabla en las que la fórmula (última columna) toma el valor 0. Para cada una de esas filas, escribimos una fórmula que sea verdadera para el conjunto de variables de esta fila:

línea 2: ;

línea 6: .

La conjunción de estas dos fórmulas tomará el valor 0 sólo en los conjuntos de variables de las líneas 2 y 6, y por tanto será la forma normal conjuntiva perfecta deseada (PCNF):

Preguntas y tareas para una solución independiente.

1. Usando transformaciones equivalentes, reduzca las fórmulas a DNF:

2. Usando transformaciones equivalentes, lleve las fórmulas a CNF:

3. Utilizando la segunda ley distributiva, convierta DNF a CNF:

A) ;

4. Convierta los DNF dados a SDNF:

5. Convierta el CNF dado a SCNF:

6. Para fórmulas lógicas dadas, construya SDNF y SCNF de dos maneras: usando transformaciones equivalentes y usando una tabla de verdad.

b) ;

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.

representan conjunciones de disyunciones elementales. Por tanto, se escriben en forma normal conjuntiva.

Una función lógica arbitraria, definida por una expresión analítica, se puede reducir a CNF ejecutando próximas operaciones:

Usar la regla de inversión si la operación de negación se aplica a una expresión lógica;

Usando el axioma de distributividad con respecto a la multiplicación:

Usos de la operación de absorción:

Excepciones en disyunciones de variables repetidas o sus negaciones;

Eliminando todas las disyunciones elementales idénticas excepto una;

Eliminando todas las disyunciones que incluyen simultáneamente una variable y su negación.

La validez de las operaciones enumeradas se deriva de los axiomas básicos y relaciones idénticas 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 realiza realizando las siguientes operaciones:

Adiciones a cada disyunción elemental de conjunciones de variables y sus negaciones, si no están incluidas en esta disyunción elemental;

Usando el axioma de distributividad;

Eliminando todas las disyunciones elementales idénticas excepto una.

En CNF perfecto se puede representar cualquier función lógica excepto

idénticamente igual a uno (). Propiedad distintiva 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 incluido en un CNF perfecto desaparece en un único conjunto de valores variables, que es el conjunto cero de la función. En consecuencia, el número de conjuntos de ceros de una función lógica coincide con el número de constituyentes cero incluidos en su CNF perfecto.

La función lógica constante de cero en CNF perfecto está representada por la conjunción 2nconstituyentes de cero. Formulemos una regla para compilar. SKNF lógico funciones según la tabla de correspondencias.

Para cada fila de la tabla de correspondencia en la que la función es igual a cero, se compila una disyunción elemental de todas las variables. En este caso, la disyunción incluye la propia variable si su valor es cero, o la negación si su valor es igual a uno. Las disyunciones elementales resultantes se combinan mediante un signo de conjunción.

Ejemplo 3.4. Para la función lógica z(x), dada por la tabla de correspondencias 2.2, definimos la forma conjuntiva perfecta.

Para la primera fila de la tabla, que corresponde al conjunto cero de la función 000, encontramos el constituyente de cero. Habiendo realizado operaciones similares para la segunda, tercera y quinta línea, determinamos la función CNF perfecta requerida:

Cabe señalar que para funciones cuyo número de conjuntos de unidades excede el número de conjuntos de ceros, es más compacto escribirlas en forma de SCNF y viceversa.

Ejemplo. Encuentra fórmulas CNF

~ ~

La forma normal disyuntiva perfecta del 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. Omitir términos idénticamente 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.

~

Para construir el SCNF, puede utilizar el siguiente esquema:

Ejemplo. Encuentra fórmulas SDNF.

~

Se sabe (Teoremas 2.11, 2.12) que SDNF y SCNF están definidos de forma única por la fórmula y, por lo tanto, pueden construirse utilizando la tabla de verdad de la fórmula.

A continuación se muestra el esquema para construir SDNF y SCNF según la tabla de verdad, 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 las expresiones booleanas. Simplifica las expresiones de tu variante tanto como sea posible utilizando las leyes lógicas de Boole. Luego usa tablas de verdad para comparar tu expresión simplificada con la original.

2.2.2. Aclare la cuestión de la equivalencia de f 1 y f 2 reduciéndolas a SDNF (Tabla 1).

2.2.3. Encuentre la función dual para f 3 usando el principio generalizado y booleano (Tabla 1). Compara los resultados.

№	f 1	f 2	f 3

2.3. Preguntas de control.

2.3.1. Definir una declaración.

2.3.2. Enumere las operaciones principales en una 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, omita los paréntesis “extra” y el signo “ ” en las fórmulas:

;

2.3.6. Usando transformaciones equivalentes, demuestre la verdad idéntica de las fórmulas:

2.3.7. Encuentra fórmulas duales:

)

2.3.8. Reduzca las siguientes fórmulas a la forma DNF perfecta (SDNF):

~

2.3.9. Reduzca las siguientes fórmulas a la forma perfecta de CNF (SCNF):

~

Trabajo de laboratorio № 3

Sujeto:“Minimización de funciones booleanas. Lógica"

Objetivo: Adquirir habilidades prácticas para trabajar con métodos de minimización de funciones booleanas.

3.1. Información teórica.

Formas mínimas

Como se mostró en, cualquier función booleana se puede representar en forma normal perfecta (disyuntiva o conjuntiva). Además, dicha representación es el primer paso en la transición de una especificación tabular de una función a su expresión analítica. En lo que sigue, procederemos de la forma disyuntiva y los resultados correspondientes para la forma conjuntiva se obtienen basándose en el principio de dualidad.

El problema canónico de sintetizar circuitos lógicos en base booleana se reduce a minimizar funciones booleanas, es decir a representarlas en forma normal disyuntiva, que contiene el menor número de letras (variables y sus negaciones). Estas formas se denominan mínimas. En síntesis canónica, se supone que tanto las señales como sus inversiones se suministran a las entradas del circuito.

La fórmula presentada en forma normal disyuntiva se simplifica mediante el uso repetido de la operación de pegado y la operación de absorción y (las identidades duales para la forma normal conjuntiva tienen la forma: y). Aquí, y puede entenderse como cualquier fórmula de álgebra booleana. Como resultado, llegamos a una expresión analítica en la que ya no son posibles más transformaciones, es decir obtenemos un formulario 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 un formulario sin salida determinado 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 términos y aplicando la operación de pegado, 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, debes adivinar para repetir un término en la fórmula original (esto siempre se puede hacer, desde ). En el primer caso, dicho miembro puede ser . Entonces . Sumando el término , obtenemos: . Habiendo pasado por todo opciones posibles, podemos comprobar 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 y símbolos gráficos y analíticos especialmente desarrollados para este propósito.

cubo multidimensional

Cada vértice de un cubo de dimensiones puede asociarse con un constituyente de una unidad. En consecuencia, el subconjunto de vértices marcados es una aplicación en el cubo -dimensional de una función booleana de variables en forma normal disyuntiva perfecta. En la Fig. 3.1 muestra dicha correspondencia para la función de la cláusula 3.7.

Fig. 3.1 Visualización de una función presentada en SDNF en un cubo tridimensional

Para visualizar 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.

Un minitérmino de rango (-1) puede considerarse como el resultado de unir dos minitérminos de rango (constituyente de la unidad), es decir , En un cubo de dimensiones, 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 sobre ella). Por lo tanto, los minitérminos de orden (-1) corresponden a las aristas del cubo de dimensiones. De manera similar, la correspondencia de minitérminos de orden (-2) se establece con las caras de un cubo de dimensiones, cada una de las cuales cubre cuatro vértices (y cuatro aristas).

Los elementos de un cubo de dimensiones caracterizados por dimensiones se denominan cubos. Por lo tanto, los vértices son 0 cubos, las aristas son 1 cubos, las caras son 2 cubos, etc. Generalizando el razonamiento anterior, podemos suponer que un minitérmino de rango ()-ésimo en forma normal disyuntiva para una función de variables está representado por un -cubo, y cada -cubo cubre todos aquellos -cubos de dimensión inferior que están asociados con su vértices. Como ejemplo en la Fig. 3.2 muestra una función de tres variables. Aquí los minitérminos corresponden a 1 cubos (), y el minitérmino está representado por un 2 cubos ().

Fig.3.2 Cobertura de funciones

Entonces, cualquier forma normal disyuntiva se asigna a un cubo -dimensional mediante un conjunto de -cubos que cubren todos los vértices correspondientes a los constituyentes de la unidad (0-cubos). La afirmación inversa también es cierta: si un determinado conjunto de -cubos cubre el conjunto de todos los vértices correspondientes a los valores unitarios de una función, entonces la disyunción de los minitérminos correspondientes a estos -cubos es una expresión de esta función en normal disyuntiva forma. Se dice que tal colección de -cubos (o sus minitérminos correspondientes) forma una cobertura de una función.

El deseo de una forma mínima se entiende intuitivamente como la búsqueda de una cubierta cuyo número de cubos sea menor y sus dimensiones 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 cumple con 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 de dimensiones es clara y sencilla cuando . Un cubo de cuatro dimensiones se puede representar como se muestra en la Fig. 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 de carnot

Otro método para mostrar gráficamente funciones booleanas utiliza mapas de carnot, que son tablas de correspondencia especialmente organizadas. Las columnas y filas de la tabla corresponden a todos los conjuntos posibles de valores de no más de dos variables, y estos conjuntos están ordenados de tal manera que cada uno posterior difiere del anterior en el valor de solo una de las variables. . Gracias a esto, las celdas vecinas de la tabla difieren horizontal y verticalmente 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. La figura 3.5 muestra mapas de Karnaugh para dos, tres, cuatro variables.

Arroz. 3.5 Mapas de Carnaugh 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 un mapa de Karnaugh para una función, cuya visualización en un cubo de cuatro dimensiones se muestra en la Fig. 3.4. Para simplificar las cosas, las filas y columnas correspondientes a los valores de 1 para una variable se resaltan con una llave que indica esa variable.

Arroz. 3.6 Visualización de una función de cuatro variables en un mapa de Carnaugh

(a) y su cobertura mínima (b)

Entre asignaciones de funciones a norte-Cubo dimensional y el mapa de Carnot existe una correspondencia uno a uno. En el mapa de Carnot s-un 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 anteriormente (ver párrafo. cubo multidimensional), son válidos para mapas de Karnaugh. Así, en la Fig. 3.6, b muestra la cobertura de unidades de mapa correspondientes a la forma disyuntiva mínima la función en cuestión.

La lectura de minitérminos del mapa de Karnaugh se realiza utilizando regla simple. Células formándose s-cubo, dale miniter (n – s)-ésimo rango, que incluye aquellos (n – s) variables que ahorran 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 durante s-cubo, están ausentes en el minitérmino. Varias maneras Las lecturas dan como resultado diferentes representaciones de la función en forma normal disyuntiva (la del extremo derecho es mínima) (Figura 3.7).

El uso de mapas de Karnaugh requiere construcciones más simples en comparación con el mapeo en norte-Cubo dimensional, especialmente en el caso de cuatro variables. Para mostrar funciones de cinco variables, se utilizan dos mapas de Karnaugh para cuatro variables, y para una función de seis variables, se utilizan cuatro mapas de este tipo. Con un mayor aumento en el número de variables, los mapas de Karnaugh se vuelven prácticamente inutilizables.

Famoso en la literatura. Tarjetas de veitch Se diferencian únicamente en el orden diferente de los conjuntos de valores de variables y tienen las mismas propiedades que los mapas de Karnaugh.

complejo de cubos

La inconsistencia de los métodos gráficos con una gran cantidad de variables se compensa con varios métodos analíticos representaciones de funciones booleanas. Una de esas representaciones es complejo de cubos, utilizando la terminología de un espacio lógico multidimensional en combinación con un simbolismo especialmente desarrollado.

). Los cubos 0 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 la grabación.

Arroz. 3.8 Complejo de cubos de una función de tres variables ( A) y su representación simbólica ( b)

Se forma el complejo de cubos. cobertura máxima de funciones. Excluyendo de ella a todos aquellos s-cubos que están recubiertos por cubos de mayor dimensión, obtenemos recubrimientos correspondientes a formas sin salida. Entonces, para el ejemplo considerado (Fig. 3.8), tenemos una cubierta sin salida.

,

que corresponde a la función . EN 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 corresponde a la intersección de sus complejos cúbicos. La negación de una función corresponde al complemento 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. Por tanto, existe una correspondencia uno a uno (isomorfismo) entre el álgebra de Funciones booleanas y conjuntos booleanos que representan complejos de cubos.

Representar 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 información cuando se utilizan computadoras.

Minimizar funciones booleanas

Formulación del problema. Minimizar un circuito en forma booleana se reduce a encontrar la forma disyuntiva mínima que corresponde a la cobertura mínima. El número total de cartas incluidas en forma normal se expresa por el costo de la cobertura. , donde es el número de cubos que forman una cobertura de una función dada de n variables. La cobertura mínima se caracteriza valor más bajo sus precios.

Normalmente, el problema de minimización se resuelve en dos pasos. En primer lugar, buscamos una cubierta reducida que incluya todos los cubos de máxima dimensión, pero que no contenga un solo 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 una función determinada, la cobertura reducida es única, pero puede ser redundante debido al hecho de que algunos de los cubos están cubiertos por conjuntos de otros cubos.

En el segundo paso, se realiza una transición desde formas normales disyuntivas reducidas a formas sin salida, de las cuales se seleccionan formas mínimas. Las formas sin salida se forman excluyendo de la cobertura reducida todos los cubos redundantes, sin los cuales el conjunto restante de cubos todavía forma una cobertura de una función determinada, pero con la exclusión adicional de cualquiera de los cubos, ya no cubre el conjunto de todos los vértices corresponden a valores únicos de la función, es decir, deja de ser una cobertura.

Un cubo de cobertura reducida que cubra vértices de una función determinada que no esté cubierto por ningún otro cubo no puede ser redundante y siempre se incluirá en la cobertura mínima. Tal cubo, al igual que su implicante correspondiente, se llama extremo (implicante esencial) y los vértices que cubre se llaman vértices cancelados. El conjunto de extremos forma el núcleo de la cobertura; está claro que al pasar de una cobertura reducida a una mínima, en primer lugar se deben aislar todos los extremos. Si el conjunto de extremos no forma una cubierta, entonces se complementa con 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.9, b) se expresan de la siguiente manera.

Formas normales disyuntivas y conjuntivas de álgebra proposicional. Para cada función lógica proposicional, se puede construir una tabla de verdad. El problema inverso también siempre tiene solución. Introduzcamos varias definiciones.

Conjunciones elementales (conjunciones) se llaman conjunciones de variables o sus negaciones en las que cada variable ocurre como máximo

una vez.

Forma normal disyuntiva(DNF) es una fórmula que tiene la forma de una disyunción de conjunciones elementales.

Disyunciones elementales (disyunciones) se llaman disyunciones de variables con o sin negaciones.

Forma normal conjuntiva(CNF) es una fórmula que tiene la forma de una conjunción de disyunciones elementales.

Para cada función de álgebra proposicional se puede encontrar un conjunto de formas normales disyuntivas y conjuntivas.

Algoritmo para construir DNF:

1. Vaya a operaciones booleanas utilizando fórmulas de transformación equivalentes.

2. Vaya a fórmulas con negaciones cercanas, es decir, a una fórmula en la que las negaciones se encuentren no más arriba de las variables; aplique las leyes de De Morgan.

3. Abra los corchetes: aplique las leyes de la distributividad.

4. Tome los términos repetidos una vez a la vez: la ley de idempotencia.

5. Aplicar las leyes de la absorción y la media absorción.

Ejemplo 6. Encuentra fórmulas DNF: .

En álgebra booleana es cierto principio de dualidad. Es el siguiente.

La función se llama doble a la función si. Aquellos. Para encontrar una función dual a una dada, es necesario construir la negación de la función a partir de las negaciones de los argumentos.

Ejemplo 7. Encuentra la función dual a .

Entre funciones elementalesálgebra de lógica 1 es dual con 0 y viceversa, x es dual con x, dual con , dual y viceversa.

Si en la fórmula F 1 que representa la función reemplazamos todas las conjunciones

en disyunción, disyunción en conjunción, 1 en 0, 0 en 1, entonces obtenemos la fórmula F * que representa la función * dual a.

La forma normal conjuntiva (CNF) es un concepto dual de DNF, por lo que se puede construir fácilmente según el siguiente esquema:

Ejemplo 8. Encuentre la fórmula CNF: .

Usando el resultado del Ejemplo 6, tenemos

Formas normales disyuntivas perfectas y conjuntivas perfectas. En cada uno de los tipos de formas normales (disyuntiva y conjuntiva), se puede distinguir una clase de formas perfectas SDNF y SCNF.

Una conjunción elemental perfecta es el producto lógico de todas las variables con o sin negación, y cada variable aparece en el producto sólo una vez.

Cualquier DNF se puede reducir a un SDNF dividiendo las conjunciones que no contienen todas las variables, es decir sumando la variable faltante x i se multiplica usando la ley distributiva

Ejemplo 9. Encuentre el SDNF para el DNF del ejemplo 6

Disyunción elemental perfecta es la suma lógica de todas las variables con o sin negaciones, y cada variable se incluye en la suma solo una vez.

Cualquier CNF se puede reducir a SCNF agregando un término de conjunción que no contenga ninguna variable X i por la conjunción y aplicando la ley distributiva

Ejemplo 10. Llevar KNF a SKNF:

Para construir el SCNF, puede utilizar el diagrama.

Ejemplo 11. Encuentre el SCNF para la fórmula del ejemplo 6.

Cada función tiene un SDNF y, además, uno único. Cada función tiene un SCNF y, además, uno único.

Porque SDNF y SKNF se definen únicamente mediante fórmulas; se pueden construir utilizando la tabla de verdad de la fórmula.

Para construir un SDNF, es necesario seleccionar las filas en las que F toma el valor 1 y escribir conjunciones elementales perfectas para ellas. Si el valor de una variable en la fila deseada de la tabla de verdad es igual a uno, entonces en conjunción perfecta se toma sin negación, si es cero, entonces con negación. Luego, las conjunciones perfectas (su número es igual al número de unidades en la tabla) se conectan mediante signos de disyunción.

Para construir un SCNF usando una tabla de verdad, es necesario seleccionar las filas donde F = 0, escribir disyunciones elementales perfectas y luego conectarlas con signos de conjunción. Si en la fila requerida de la tabla de verdad (F=0) el valor de la variable corresponde a cero, entonces en la cláusula perfecta se toma sin negación, si es uno, entonces con negación.

Ejemplo 12. Encuentre SDNF y SCNF usando la tabla de verdad para la fórmula del ejemplo 6.

La tabla 14 muestra sólo valor final F=10101101. Debe verificar usted mismo la validez de esta afirmación construyendo una tabla de verdad detallada.

Tabla 14

X	y	z

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 en forma de SDNF (SCNF). Integridad de la base estándar. Ejemplos de bases completas: base de Zhegalkin, trazo de Schaeffer, flecha de Peirce.

Base estándar es un conjunto de tres operaciones originales del álgebra de Boole: suma (unión), multiplicación (intersección) y negación.

aquí llamaremos literal variable x o su negación x y denota xˆ. Intersección booleana de varios literales definidos por diferentes variables, es decir expresión de la forma X = xˆ 1 xˆ 2 . . . xˆ l, llamado conjunción elemental . El requisito de que todas las variables sean diferentes está determinado por lo siguiente. Si la conjunción incluye varios literales idénticos, entonces debido a la conmutatividad, asociatividad e idempotencia de la conjunción, es posible, pasando a la fórmula equivalente, 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 equivale 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 abandonar . 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

hay una forma perfecta.

Dado que en el álgebra de Boole la suma y la multiplicación son operaciones simétricas y siempre se puede interpretar la suma como multiplicación y la multiplicación como suma, 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 semirings simétricos se deduce que cualquier afirmación relativa a DNF se responde con una afirmación dual relativa a CNF, que se obtiene reemplazando la suma (disyunción) por la multiplicación, la multiplicación (conjunción) por la suma, constante 0 por constante 1, constante 1 con constante 0, relación de orden con orden dual (inverso). Por lo tanto, nos centraremos más en estudiar únicamente DNF.

Teorema 1.4. Cualquier función booleana distinta de la constante 0 se puede representar como SDNF.

◀ Convengamos que por x σ nos referimos a la fórmula x si σ = 1, y a la fórmula x si σ = 0. Sea la función f(y 1 , . . . , y n) que tome el valor 1 en el vector (t 1 , . , t n ) (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 a todos aquellos conjuntos (t 1, . . . , t n) de valores de argumentos en los que función dada toma el valor 1. Tenga en cuenta que el conjunto de dichos conjuntos no está vacío, por lo que la suma contiene al menos un término.

Es fácil ver que la fórmula Φ se convierte en 1 para aquellos y sólo para aquellos valores de las variables para los cuales la función en cuestión se convierte en 1. Esto significa que 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 una constante 0, entonces se puede representar en forma de 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 le permite seleccionar otros sistemas completos funciones. La integridad del conjunto F se puede establecer a partir de las siguientes consideraciones. Supongamos que cada una de las tres funciones busis estándar se puede representar mediante una fórmula sobre F . Entonces, según el teorema 1.3, la identidad F será completa.

Ejemplo 1.3. El conjunto de operaciones módulo 2 suma, multiplicación y constante 1 se llama base de Zhegalkin . La suma módulo 2 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 término libre. Como xx = x, entonces todos los factores del polinomio tienen grado 1. Por lo tanto, al escribir un polinomio, puedes 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 llama polinomio de Zhegalkin. De hecho, el polinomio de Zhegalkin es un polinomio sobre el anillo Z2.

No es difícil construir fórmulas sobre la base de Zhegalkin, que representen las operaciones de suma y negación de la base estándar (la multiplicación de las dos bases es común):

x+y=x⊕y⊕xy, x =x⊕1.

Por 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). Coeficientes del polinomio de Zhegalkin en pequeña cantidad Las variables se pueden encontrar mediante el método de coeficientes indefinidos.

Ejemplo 1.4. Consideremos un conjunto de una sola función: el trazo de Schaeffer*. Este conjunto está completo, como se desprende 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. También se completa una base formada por una única función, la flecha de Peirce. La prueba para esto es similar al caso del derrame cerebral de Schaeffer. Sin embargo, también se puede llegar a esta conclusión basándose en el principio de dualidad para semianillos simétricos.

*El trazo de Schaeffer es una operación binaria, pero no asociativa. Por lo tanto, al utilizar la forma infija, debes tener cuidado: el resultado depende del orden de las operaciones. En este caso, se recomienda indicar explícitamente el orden de las operaciones mediante paréntesis, por ejemplo, escriba (x | y) | z, no x | y | z, aunque ambas formas son equivalentes.