Análisis y síntesis de dispositivos lógicos. Métodos para minimizar funciones y circuitos lógicos. Métodos para minimizar funciones lógicas. Diagrama lógico del algoritmo en notación de Lyapunov.

Procedimiento de minimización

Para simular la deformación a temperatura cero, se utiliza un procedimiento de minimización que permite mantener el sistema cerca de un mínimo de energía local en todo momento. La deformación y la minimización se realizan simultáneamente. El algoritmo de minimización es un algoritmo MD modificado. Después de cada paso de tiempo, se calcula la MD para cada átomo. producto escalar entre impulso y fuerza. Para los átomos para los cuales el producto escalar es negativo, el momento desaparece, ya que estos átomos se mueven en la dirección en la que aumenta la energía potencial. Por lo tanto, la energía cinética de los átomos se elimina, mientras que la energía potencial se acerca a un mínimo de energía local a lo largo de la dirección del movimiento del átomo. Este procedimiento de minimización desplaza rápidamente el sistema a la vecindad de un mínimo de energía local, pero no se obtiene una convergencia completa, ya que la convergencia completa requiere un número de pasos de tiempo del orden del número de grados de libertad del sistema. Sin embargo, normalmente aumentar el número de pasos en el procedimiento de minimización conduce sólo a pequeños cambios en la evolución del sistema.

Cálculo de fuerza

Se requiere el mayor esfuerzo computacional para calcular las fuerzas que actúan entre los átomos. Por lo tanto, se debe dar la optimización del algoritmo de cálculo de fuerza. atención especial. Un paso en esta dirección es reemplazar las expresiones de fuerza difíciles de calcular (como las que contienen exponenciales) por expresiones fáciles de calcular (como los splines de tercer orden). El segundo paso es utilizar potenciales con un rango limitado o, como se indicó anteriormente, cortar la región sin importancia del potencial si el rango del potencial es infinito. En este caso, es necesario calcular solo las fuerzas que actúan desde los átomos más cercanos, es decir ubicado dentro de una esfera (círculo en el caso bidimensional) con un radio igual al radio de corte.

El tercer paso es optimizar el algoritmo para buscar los átomos más cercanos a un átomo determinado. El hecho es que una búsqueda sencilla de todos los átomos, calculando las distancias a ellos y descartando aquellos átomos cuya distancia excede el radio de corte requiere una cantidad de operaciones proporcional a dónde está el número de átomos en el sistema. En consecuencia, con el crecimiento, el número de operaciones requeridas aumenta rápidamente y, por lo tanto, la ejecución de los cálculos se ralentiza considerablemente y, para las más grandes, se vuelve casi imposible. Por lo tanto, para evitar esta desaceleración, necesitamos un algoritmo para el cual el número de operaciones requeridas crezca linealmente en lugar de cuadráticamente. En principio, este algoritmo es simple: no es necesario clasificar todos los átomos, sino sólo aquellos que están bastante cerca. Semejante afirmación es una tautología hasta que se especifique el concepto de átomos muy próximos entre sí. Para hacer esto, dividimos la celda de simulación en subceldas más pequeñas. Entonces, los que están cerca de un átomo dado serán átomos que están ubicados en subceldas adyacentes a la subcelda que contiene este átomo o en subceldas adyacentes a las vecinas.

Es conveniente dividir la celda de modelado en subceldas: paralelepípedos (rectángulos en el caso bidimensional). Debido a la fuerte repulsión a distancias cortas, los átomos no pueden acercarse entre sí. Por lo tanto, es posible elegir tamaños de subceldas de modo que cada una de ellas no contenga más de un átomo.

Por tanto, el algoritmo para buscar átomos ubicados a una distancia no mayor que el radio de corte de un átomo dado tiene el siguiente aspecto. Usando el número de átomo, encontramos las coordenadas del átomo y a partir de ellas la subcelda en la que se encuentra el átomo. Luego encontramos subcélulas que no están a más de una distancia de él. Los átomos ubicados en estas subcélulas serán los que busquemos (ver Fig. 1). Para encontrar el número de un átomo almacenado en una subcelda determinada, es conveniente introducir una matriz, cada elemento del cual corresponde a una subcelda específica. Este elemento de la matriz almacenará el número del átomo ubicado en esta subcelda, o cero si la subcelda está vacía. Los elementos de esta matriz se actualizan en cada paso de tiempo de MD. Está claro que el algoritmo descrito asegura un aumento lineal en el número de operaciones a medida que aumenta el número de átomos en el sistema. Se utilizan variaciones de este algoritmo en los programas MD “Gromex”, “MOLDY”, “DL_POLY”, etc.

Es posible otra organización de cálculos, que será conveniente para organizar computación paralela. Para calcular las fuerzas que actúan sobre un átomo dado se puede pasar de la suma de los átomos cercanos a la suma de las subceldas cercanas (ver Fig. 1). Nos moveremos secuencialmente a lo largo de las subceldas de la primera fila. Habiendo llegado al final de la primera fila, pasamos al comienzo de la segunda fila, etc.

Fig.1 Esquema de búsqueda de átomos más cercanos.

Si hay un átomo en una subcelda, entonces calculamos la fuerza que actúa sobre él a partir de los átomos más cercanos ubicados en subceldas cercanas. Si la subcelda está vacía, pase a la siguiente. Observemos que, por ejemplo, para un átomo ubicado en la subcelda 6 (ver Fig. 1), es necesario calcular la fuerza que actúa sobre la parte de los átomos ubicados en las subceldas 1, 2, 3, 7. Fuerzas que actúan sobre el parte de los átomos ubicados en las subceldas 5, 9, 10, 11, en virtud de la tercera ley de Newton, ya se conocen hasta el signo. Se calcularon calculando las fuerzas que actúan sobre los átomos ubicados en estas subcélulas. Por tanto, en una organización computacional determinada, es necesario considerar sólo la mitad de las subceldas cercanas. Además, al pasar a la subcelda 7 adyacente, no es necesario examinar todas las subceldas cercanas para buscar átomos muy cercanos ubicados en ellas. Solo es necesario explorar las celdas 4 y 8. Y a los átomos que se encuentran en ellas, agregar los átomos encontrados para la celda 6, con la excepción de los átomos ubicados en las subceldas 1 y 6. Por lo tanto, la información sobre los átomos más cercanos para una subcelda determinada no se pierde, pero se utiliza en la búsqueda de átomos más cercanos para una subcelda adyacente. Naturalmente, esto conduce a cálculos más rápidos.

Hay dispositivos lógicos combinacionales y secuenciales.

Dispositivos lógicos combinacionales- estos son dispositivos en los que los valores de las señales de salida dependen únicamente de la combinación señales de entrada V en este momento tiempo.

Dispositivos de lógica secuencial - Se trata de dispositivos cuyas señales de salida dependen de los valores de las señales de entrada no sólo en un momento determinado, sino también en momentos anteriores. Estos dispositivos necesariamente incluyen elementos de memoria: disparadores. Existen varios tipos de disparadores según la función de memoria elemental que implementen.

Al desarrollar un dispositivo lógico, primero se formula una descripción verbal de su algoritmo de acción. Luego componen una función lógica que satisface esta descripción. (síntesis abstracta) y luego desarrollar un diagrama lógico estructural del dispositivo. (síntesis estructural).

En el proceso de síntesis abstracta. se realiza una transición de una descripción verbal del TP (su curso normal y situaciones de emergencia) a la elaboración de un algoritmo de funcionamiento en forma de tabla, ciclograma, gráfico, etc. ciclograma es una serie de líneas horizontales igual al número de entradas y salidas de un dispositivo lógico. para compilar algoritmo lógico control de los equipos tecnológicos es necesario tener información completa sobre las especificaciones técnicas de cada operación tecnológica y los equipos utilizados. En esta etapa se aclara la secuencia de operaciones y los retrasos temporales necesarios para todos los modos de operación del objeto de control, se determinan los parámetros a monitorear y tener en cuenta durante el proceso; formular los requisitos del objeto gestionado para el dispositivo lógico. Estos requisitos se representan como valores. señales binarias, que debe presentarse a actuadores sistemas de control en función del estado del objeto controlado.

En el proceso de síntesis estructural. hay una transición de una función lógica que describe el algoritmo de funcionamiento a un diagrama de bloques de un dispositivo lógico.

Sin embargo, antes de comenzar a diseñar el circuito, debe intentar convertir la función lógica original al máximo. vista sencilla. Residencia en diagrama de bloques dispositivo lógico diseñarlo diagrama esquemático usando especifico base del elemento, por ejemplo, en base OR-HE o NAND. La etapa final en la creación de un circuito de dispositivo lógico es el desarrollo y coordinación de los nodos de comunicación del dispositivo con el operador y el objeto controlado, protección contra interferencias, etc.

Históricamente, los primeros dispositivos que utilizaron funciones lógicas para describir sus acciones fueron dispositivos fabricados con elementos de contacto de relé. Para diseñar tales dispositivos, se desarrolló la teoría de los circuitos de contacto de relé (TRC). Luego vino dispositivos sin contacto, destinado únicamente a transformaciones lógicas señales y representación de productos diseñados estructuralmente.

Los dispositivos de automatización, cuyo funcionamiento se describe mediante funciones lógicas elementales, suelen denominarse, de acuerdo con la operación lógica que implementan, elementos NO, Y, O, Y-NO, O-ÉL (ver Tabla 4.1).

Teniendo elementos necesarios, utilizando una función lógica, puede sintetizar un dispositivo lógico de cualquier complejidad. Sin embargo, el circuito construido puede resultar excesivamente complejo, requiriendo el uso gran número elementos lógicos, lo que puede afectar el costo y la confiabilidad del dispositivo. En muchos casos es posible simplificar una función lógica hasta el punto de que el circuito del dispositivo correspondiente resulte mucho más sencillo y realice la tarea.

Métodos de minimización funciones lógicas. Los métodos para simplificar dispositivos combinacionales se denominan métodos para minimizar funciones lógicas. El método de minimización se basa en la aplicación de las leyes del álgebra lógica o álgebra de Boole, que se detallan a continuación para el número mínimo de variables. La equivalencia de los lados izquierdo y derecho de las ecuaciones se indica con el signo igual. Al mismo tiempo, se representan los equivalentes de retransmisión de las leyes del álgebra lógica consideradas.

Ley de viajes. Para una suma y un producto lógicos, el orden de las variables es indiferente:

Ley de combinación.El resultado de la suma o multiplicación secuencial de variables no depende del orden de estas acciones:

Ley de absorción.Suma de una variable con la misma variable, multiplicado por otra variable, o multiplicar una variable por la suma de la misma variable y otra variable es igual a la primera variable:

Ley distributiva.El multiplicador general se puede sacar entre paréntesis., como en álgebra ordinaria:

Ley del pegado.La suma de los productos de la primera y segunda variable y la segunda variable y la inversa de la primera variable es igual a la segunda variable. El producto de la suma de dos variables y la suma de la inversa de la primera variable con la segunda variable es igual a la segunda variable:

Ley de inversión (ley de Morgan - Shannon).La negación de la suma lógica es equivalente al producto de las negaciones de los términos., Y, viceversa, la negación de la multiplicación lógica equivale a la suma de las negaciones de los factores:

Invertir una combinación arbitraria de variables binarias conectadas por un signo más o de multiplicación equivale a reemplazar los valores de las variables que contiene.

sus inversiones y al mismo tiempo cambiar el signo "más" por el signo de "multiplicación" y viceversa. Por ejemplo, x t x 2 +x 3 x 4 =(x l x 2)(x 3 x 4) = (x l +x 2)(x 3 +x 4). La ley de inversión se encuentra sólo en el álgebra de la lógica.

Así, la ley de inversión permite sustituir la operación O por la operación Y y, si es necesario, viceversa. Esto es especialmente importante, ya que con el uso generalizado de elementos lógicos integrales en la construcción. dispositivos lógicos Los elementos de las bases AND-NOT y OR-NOT son los más utilizados.

Las transformaciones de funciones lógicas realizadas utilizando la ley distributiva son el principal método de simplificación, ya que colocar el factor común entre paréntesis reduce el número total de variables de expresión y, por lo tanto, permite reducir el número de elementos en los circuitos de dispositivos lógicos.

Al realizar la minimización, también utilizan las consecuencias de las leyes del álgebra lógica, las principales de las cuales son las siguientes:

La última identidad a minimizar se obtiene mediante doble inversión de la expresión que se está simplificando. La primera inversión da

La segunda inversión da

Para pasar de la base Y, O, NO a la base O-ÉL, así como a la base Y-NO, también se realiza una transformación de fórmula lógica mediante doble negación. Consideremos un ejemplo de una transición para un circuito de relé en la Fig. 4.5, A, implementado en la base Y, O, NO (Fig. 4.5, b), en la base OR-HE (Fig. 4.5, V):

y en la base Y-NO (Fig. 4.5, GRAMO):

El número de guiones en la parte superior de las fórmulas es igual al número de elementos de negación, es decir Elementos OR-HE y NAND. Hay seis negativos en la primera fórmula y, en consecuencia, el diagrama de la Fig. 4.5, V contiene seis elementos OR-HE. La segunda fórmula contiene cinco negativos y, en consecuencia, el diagrama de la Fig. 4.5, GRAMO Contiene cinco elementos NAND.

Arroz. 45.

A - en elementos de relé; b - sobre los elementos O, Y, NO; V - sobre los elementos

O-ÉL; Elementos Sr. NAND

Ejemplo 4.1

Simplifica la expresión / = (INCÓGNITA + y)(x + z) y dibuje el equivalente del relevo antes y después de la simplificación. Aquí / está la señal de salida (estado del contacto normalmente abierto) elemento de relevo F.

Solución

Simplifiquemos la expresión dada de acuerdo con las leyes del álgebra lógica: Considerando que incógnita incógnita = INCÓGNITA, vamos a escribir

Teniendo en cuenta que 1 + en + z= 1, finalmente escribiremos /= incógnita + en z. Después de la simplificación, el equivalente del relé se ve así:

Simplifica la expresión f = xy + x yz +yz y dibuje el equivalente del relevo antes y después de la simplificación.

Solución

Antes de la simplificación, el equivalente del relé de acuerdo con la expresión dada se ve así:

Simplifiquemos la expresión dada de acuerdo con las leyes del álgebra lógica, sacando multiplicador común fuera de paréntesis:

El diagrama de relevos de esta expresión tomará la forma

Se tiene en cuenta aquí que x-z =x + z ia + a = 1, o x+z+x+z= 1, donde a = x + z; a = x+z. Por lo tanto, después de la transformación, la expresión simplificada tomará la forma

Después de simplificar la expresión, el equivalente del relé se ve así:

Comprobemos la exactitud de la transformación utilizando la tabla de estado (Tabla 4.2), que muestra todos posibles combinaciones dos variables incógnita y 2, y asegúrese de que la expresión x + g + xz siempre igual a uno.

Tabla 4.2

tabla de estado

		X+Z+X-Z

Consideremos un ejemplo del uso del álgebra de la lógica para crear un sistema. regulación automática nivel de agua en el tanque P (Fig. 4.6). El actuador IM suministra agua al depósito mediante apertura completa o cerrar la válvula de suministro A. El tanque tiene dos sensores de nivel de agua: sensor nivel superior B y sensor nivel inferior H. Cuando el nivel del agua alcanza o excede la posición del sensor, su señal se vuelve igual a uno. Si el nivel del agua cae por debajo del nivel del sensor, la señal en su salida se vuelve cero.

Arroz. 4.6.

Analicemos las condiciones laborales. sistema automático. Si el nivel del agua alcanza el nivel inferior H, entonces se debe abrir el suministro. Si el nivel del agua alcanza el nivel superior B, se debe cortar el suministro. Si el nivel de agua es intermedio entre B y H, entonces el suministro debe permanecer abierto si fue activado por el sensor H. Si el suministro fue cortado por el sensor B, entonces debe permanecer apagado. Diagrama de tiempo de señales de la salida de sensores y la señal de control. q mostrado en la Fig. 4.7.

Arroz. 4.7.

en la figura. 4.6

Condiciones de trabajo, es decir Todas las combinaciones de señales de entrada y señales de control se traducen al lenguaje del álgebra lógica y se presentan en la figura. 4,7 voltios mesa superior en forma de unos y ceros. La tabla indica en qué proporciones de señales de entrada hay o no hay señal. q en la salida del relé ACS. La señal de salida es el resultado. operaciones lógicas sobre las señales de entrada.

Si, según los datos de la tabla, intentamos anotar las condiciones de funcionamiento en forma de funciones lógicas, encontraremos que la señal de control encendida corresponde a dos relaciones diferentes de señales de entrada. Lo mismo se aplica a la señal de control desconectada. El resultado es una ambigüedad en la señal de salida dependiendo de la combinación de señales de entrada. En B = 0 y H = 1 hay una situación en la que q = 0 es la posición cuando Q=l. Esto significa que el circuito debe tener un elemento de memoria, que se puede utilizar como el ya familiar flip-flop RS T. Para activar el disparador, utilizamos la aparición de una señal cero en la salida 11 (II = 0). Esta señal se invierte y se suministra a la entrada de configuración S del disparador T. Dado que la señal B no cambia, no la tendremos en cuenta y escribiremos la condición para encender S = H. Escribimos las condiciones para restablecer el disparador y eliminar la señal de control como R = B.

Los sistemas para regular la temperatura durante el enfriamiento se construyen utilizando el mismo principio. maquinas electricas y transformadores, así como plantas de energía coches y tractores mediante ventiladores. El circuito también se puede utilizar para mantener automáticamente la temperatura mediante calefacción en locales residenciales y ganaderos.

Consideremos otro ejemplo del uso del álgebra lógica para crear protección de relé lógica de objetos eléctricos usando el ejemplo de protección de relé. transformador de potencia mostrado en la Fig. 4.8.

Las reglas de instalación eléctrica proporcionan protección primaria y de respaldo para instalaciones críticas. La protección principal debe apagar el objeto sin demora, y la protección de respaldo, con demora.

Arroz. 4.8.

A -circuito de potencia;b -diagrama del circuito de protección

La principal protección del transformador T1 en caso de un cortocircuito en el transformador (cortocircuito en el punto K1) es la protección diferencial del relé (no se muestra en el diagrama). La protección de respaldo en caso de cortocircuito en los buses de salida de la subestación detrás del interruptor Q2 (cortocircuito en el punto K2) es la protección de corriente máxima que opera cuando se activan los relés de corriente KL1-K AZ. Cortocircuito en el transformador T1 debe desconectarse mediante el interruptor Q1 de la acción protección de respaldo sin demora, es decir "instantáneamente." Un cortocircuito en el punto K2 debe desconectarse sin retardo mediante el interruptor Q2 (la protección del interruptor Q2 no se muestra en el diagrama). Si por alguna razón la protección que actúa sobre el interruptor Q2 o el propio interruptor Q2 no funciona, entonces la protección de respaldo con retardo de tiempo debe disparar el interruptor Q1.

Consideremos cómo podemos aumentar el rendimiento de la protección de respaldo en cuestión si ocurre un cortocircuito en el transformador y la protección principal no funciona. Para ello, se colocan elementos de medición en la entrada y salida del transformador T1. Realizan la función de determinar la ubicación de la falla: en el objeto protegido o en el sitio. red externa. En caso de cortocircuito en el objeto protegido (cortocircuito en la zona principal), permiten el funcionamiento de la protección de respaldo sin demora, y en caso de cortocircuito externo, bloquean el circuito. apagado instantáneo, y la protección funciona como respaldo con un retardo de tiempo.

La determinación de la ubicación del cortocircuito se realiza de la siguiente manera. Durante un cortocircuito en T1 (punto K1), la corriente de cortocircuito hace circular los transformadores de corriente TA 1-TAZ y se activa el relé de corriente KA1-KAZ. Los transformadores de corriente TA4-TA5 en la salida del transformador T1 no están sujetos a corriente de cortocircuito. Los relés de corriente KA4 y KA5 no funcionan, sus contactos de apertura están cerrados. En tal situación, la protección debería actuar sin demora. El relé intermedio KL envía una señal para abrir el interruptor Q1.

Las condiciones de funcionamiento del relé intermedio KL para la desconexión sin retardo se pueden formular verbalmente de la siguiente manera: el relé KL funcionará si el relé KL1 funciona, O el relé KA2 funciona O, el relé KAZ funciona Y el relé KA4 Y el KA5 El relé NO funciona.

En simbolos lógica matemática la condición de activación del relé KL se escribe de la siguiente manera:

Durante un cortocircuito en una sección de la red externa (punto K2), los transformadores de corriente TA4 y TA5 son arrastrados por la corriente de cortocircuito, lo que provoca el funcionamiento de los relés de corriente KA4 y KA5 y la apertura de sus interruptores. contactos en el circuito de protección del relé sin retardo de tiempo. De este modo se bloquea el funcionamiento de la protección sin retardo. La protección de respaldo para cortocircuito en el punto K2 funciona con un retardo de tiempo.

La condición para el funcionamiento del relé de tiempo de protección de respaldo se formula verbalmente de la siguiente manera: el relé de tiempo KT funcionará si funciona el relé KA1, O si funciona el relé KA2, O si funciona el relé KAZ.

En símbolos de lógica matemática, la condición de activación de un relé de tiempo se escribe como

El estado de funcionamiento completo del relé intermedio KL, que apaga el interruptor Q1 sin retardo y con retardo de tiempo, se escribe de la siguiente manera:

Esquema en la Fig. 4.8, b construido de acuerdo con las ecuaciones (4.13) y (4.14). La activación de la protección sin retardo (protección lógica) es registrada por el relé indicador KN1. El funcionamiento de la protección retardada es registrado por el relé indicador KN2.

Hay dos direcciones para la minimización:

• Ш La forma más corta de notación (el objetivo es minimizar el rango de cada término);
• Ш Obtención de la forma mínima de grabación (el objetivo es obtener el número mínimo de caracteres para escribir la función completa de una vez).
• 1. Método de transformaciones equivalentes

El método de minimizar funciones booleanas mediante transformaciones equivalentes se basa en el uso coherente de las leyes del álgebra booleana. Es aconsejable utilizar el método de transformaciones equivalentes sólo para funciones simples y para el número de variables lógicas no más de 4. En más variables y función compleja aumenta la probabilidad de errores durante la conversión.

2. El método de Quine.

Al minimizar utilizando el método de Quine, se supone que la función lógica a minimizar se proporciona en forma de SDNF. Aquí se utiliza la ley del enlace incompleto. La minimización se lleva a cabo en dos etapas: encontrar implicantes simples, colocar etiquetas y determinar implicantes esenciales.

Los términos no etiquetados se denominan implicantes primos. Recibió expresión lógica no siempre resulta ser mínimo, por lo que se explora la posibilidad de una mayor simplificación.

Para hacer esto:

• Ш Se compilan tablas, en cuyas filas se escriben los implicantes primarios encontrados, y en las columnas se indican los términos del FAL primario.
• Ш Las celdas de esta tabla están marcadas si el implicante primario es parte de algún término primario.
• Ш El problema de simplificación se reduce a encontrar el número mínimo de implicantes que cubran todas las columnas.

Algoritmo del método Quine (pasos):

• 1. Encontrar los implicantes principales (los términos originales de DNF están escritos en una columna y pegados de arriba a abajo, los implicantes sin etiquetar entran en funciones en este paso).
• 2. Organizar etiquetas de redundancia (se compila una tabla en la que las filas son los implicantes principales, las columnas son los términos originales, si algún término mínimo contiene el implicante principal, entonces colocamos una etiqueta en la intersección de la fila y la columna) .
• 3. Encontrar implicantes esenciales (si solo hay una etiqueta en cualquier columna, entonces el implicante principal de la fila correspondiente es esencial).
• 4. Se tachan la fila que contiene el implicante esencial y las columnas correspondientes (si, como resultado de eliminar las columnas, aparecen filas de implicantes primarios que no contienen etiquetas o contienen etiquetas idénticas en las filas, entonces se tachan dichos implicantes primarios y en este último caso queda uno de menor rango).
• 5. Seleccionar la cobertura mínima (de la tabla obtenida en el paso 3, seleccione un conjunto de implicantes primarios que incluya etiquetas en todas las columnas con al menos una etiqueta en cada una, con varias opciones posibles se da preferencia a la cobertura con el mínimo número total de elementos en los implicantes que forman la cobertura).
• 6. El resultado se escribe como una función.

Sea la función dada:

Para facilitar la presentación, marquemos cada componente de la unidad de la función F SDNF con algún número decimal (arbitrariamente). Realizamos pegado. El constituyente 1 está pegado sólo con el constituyente 2 (por la variable x3) y con el constituyente 3 (por la variable x2) del constituyente 2 con el constituyente 4, etc. Como resultado, obtenemos:

Tenga en cuenta que el resultado del pegado es siempre un producto elemental, que es parte común componentes pegados.

con apariencia de la misma obra elemental. Ya no es posible pegar más. Habiendo realizado absorciones (del DNF resultante eliminamos todos los productos elementales absorbidos), obtenemos un DNF reducido:

Pasemos a siguiente etapa. Para obtener un DNF mínimo, es necesario eliminar todos los implicantes primos innecesarios del DNF reducido. Esto se hace utilizando una matriz implicante especial de Quine. Las filas de dicha matriz están marcadas por implicantes simples de la función booleana, es decir, términos del DNF abreviado, y las columnas están marcadas por constituyentes de la unidad, es decir, términos del SDNF de la función booleana.

La matriz implicante tiene la forma ver tabla. 1.1

Tabla 1.1 Matriz implicante

Como ya se señaló, un implicante simple absorbe algún constituyente de una unidad si es su propia parte. La celda correspondiente de la matriz de implicantes en la intersección de la fila (con el implicante simple considerado) y la columna (con el constituyente de la unidad) está marcada con una cruz (Tabla 1). Los DNF mínimos se construyen a partir de la matriz implicante de la siguiente manera:

• 1. Se buscan columnas de la matriz de implicantes que tengan una sola cruz. Los implicantes simples correspondientes a estos cruces se denominan básicos y forman el llamado núcleo de la función booleana. El kernel está necesariamente incluido en el DNF mínimo.
• 2. están siendo considerados varias opciones seleccionar un conjunto de implicantes simples que cubrirán las columnas restantes de la matriz de implicantes con cruces, y seleccionar opciones con el número total mínimo de letras en dicho conjunto de implicantes.

Por lo tanto la función queda así:

3. Método Quine-McCluskey.

El método es el método de Quine formalizado en la etapa de encontrar implicantes simples. La formalización se realiza de la siguiente manera:

• 1. Todos los componentes unitarios del SDNF de la función booleana F se escriben mediante sus números binarios.
• 2. Todos los números se dividen en grupos disjuntos. Signo de la formación del i-ésimo grupo: i unidades en cada número binario son constituyentes de uno.
• 3. El pegado se realiza únicamente entre varios grupos adyacentes. Los números que se pegan están marcados con algún tipo de signo (tachado, asterisco, etc.).
• 4. Se realizan todo tipo de pegados, como en el método Quine. Los números que no están marcados después de pegar son implicantes simples.

Formamos grupos de números binarios. Un signo de la formación del i-ésimo grupo son i unidades en el número binario de la unidad constituyente (Tabla 1.2).

Tabla 1.2 Grupos de números binarios

Peguemos números de grupos vecinos de la mesa. 1.3 Sólo se pueden fusionar números que tengan guiones en las mismas posiciones. Marquemos los números que se están pegando. Introduciremos los resultados del pegado en la tabla. 1.4.

Tabla 1.4 Resultados de unión 2

Según la tabla 5. Determinamos el conjunto de implicantes simples - 0--1 y 111-, correspondientes al DNF mínimo. Para restaurar la forma literal de un implicante simple, basta con anotar los productos de aquellas variables que corresponden a los dígitos binarios restantes:

Dividir los componentes en grupos le permite reducir el número de comparaciones por pares al pegar.

4. Método del diagrama de Veitch.

El método le permite obtener rápidamente DNF mínimos de una función booleana f pequeño número variables. El método se basa en especificar funciones booleanas mediante diagramas de algún tipo especial, llamados diagramas de Veitch. Para una función booleana de dos variables, el diagrama de Veitch se parece a (Figura 1).

Fig.1.

Cada celda del diagrama corresponde a un conjunto de variables de función booleana en su tabla de verdad. En la (Figura 1) se muestra esta correspondencia; una celda en el diagrama de Veitch se marca con uno si la función booleana toma un valor unitario en el conjunto correspondiente. Valores nulos Las funciones booleanas no están incluidas en el diagrama de Veitch. Para una función booleana de tres variables, el diagrama de Veitch tiene siguiente vista(Figura 2).

Fig.2.

Al agregarle la misma tabla se obtiene un diagrama para una función de 4 variables (Fig. 3).

Fig.3.

De la misma manera, es decir, agregando otro diagrama de 3 variables al que acabamos de considerar, se puede obtener un diagrama para una función de 5 variables, etc., pero rara vez se utilizan diagramas para funciones con más de 4 variables.

5. Mapas de Carnot.

El método del mapa de Karnaugh es uno de los métodos gráficos minimizando la función. Estos métodos se basan en el uso de características de la percepción visual, ya que con su ayuda se pueden reconocer casi instantáneamente ciertas configuraciones simples.

Construyamos una tabla para el método del mapa de Karnaugh (Tabla 1.6).

Tabla 1.6 Mapas de Carnot

Ahora contemos la totalidad de todos los cruces con etiquetas con un número mínimo de cruces. En nuestro caso, habrá 5 cruces de este tipo: tres de cuatro celdas y dos de dos celdas. Estos cruces corresponden a los siguientes implicantes simples:

para el primero - X 3 X 4;

para el segundo - X 1 X 3;

para el tercero - X 2 X 3;

para el cuarto - X 1 X 2 X 4;

para el quinto - X 1 X 2 X 4;

Un DNF mínimo se vería así:

6. Método coeficientes inciertos.

Este método se puede utilizar para cualquier número de argumentos. Pero como este método es bastante engorroso, se utiliza sólo en los casos en que el número de argumentos no supera los 5-6.

El método de coeficientes indefinidos utiliza las leyes de los conjuntos universales y nulos y las leyes de la repetición. Al principio, todos los coeficientes son inciertos (de ahí el nombre del método).

Construyamos una matriz de coeficientes inciertos para cuatro argumentos. En este caso tendremos un sistema de 16 ecuaciones.

Igualemos todos los coeficientes a 0 en aquellas filas que corresponden a 0 en la columna del vector. Luego igualamos los coeficientes correspondientes en otras filas a 0. Después de estas transformaciones, el sistema tomará la siguiente forma (Fig.4):

Fig.4.

Ahora, en cada línea debe seleccionar el coeficiente de rango mínimo y establecerlo en uno, y los coeficientes restantes en 0. Después de eso, tache líneas idénticas, dejando uno de ellos (también se tachan aquellas líneas para las que todos los coeficientes son iguales a 0).

Anotemos ahora las conjunciones correspondientes a los coeficientes, igual a unidades. Obtendremos el DNF mínimo.

El método es aplicable para funciones de cualquier número de variables, pero lo consideraremos para funciones de 3 variables.

Representémoslo como un DNF con coeficientes indeterminadossk:

(**)

Este DNF presenta todas las conjunciones elementales posibles que se pueden incluir en la función, y los coeficientes k pueden tomar los valores 0 o 1. Los valores de los coeficientes deben elegirse de manera que este DNF sea mínimo.

Consideraremos la función que se nos da en todos los conjuntos y equipararemos la expresión (**) en cada uno de los conjuntos (descartando las conjunciones cero) al valor correspondiente de la función. Obtenemos un sistema de ecuaciones de la forma:

Si en cualquiera de estas ecuaciones el lado derecho es igual a 0, entonces todos los términos del lado izquierdo también son iguales a 0. Estos coeficientes se pueden eliminar de todas las ecuaciones cuyos lados derechos sean iguales a 1. En estas ecuaciones se debe asignar el valor 1 al coeficiente que corresponde a la conjunción de menor rango. Estos coeficientes determinarán el MDNF.

Ejemplo

El sistema lo componemos usando la expresión (**).

Después de eliminar los términos cero obtenemos

Suponemos que los coeficientes restantes se consideran cero. Obtenemos MDNF:

2.2. Método Quine-Mack-Clasky

El método considerado de coeficientes indefinidos es efectivo si el número de argumentos de la función no es más de 5 a 6. Esto se debe al hecho de que el número de ecuaciones es 2n. Es más eficaz anotar no todas las conjunciones posibles para una función, sino sólo aquellas que puedan estar presentes en el DNF de una función determinada. En esto se basa el método de Quine. Se supone que la función se especifica en forma de SDNF. En este método, las conjunciones elementales de rango n incluidas en el DNF se denominan minitérminos de rango n. El método de Quine consiste en realizar secuencialmente los siguientes pasos.

1. Encontrar implicantes primarios

Revisamos cada minitérmino de la función secuencialmente y lo fusionamos con todos los minitérminos con los que esto es posible. Como resultado de unir minitérminos de rango n, obtenemos minitérminos de rango (n-1). Marcamos los minitérminos de rango n que participaron en la operación de pegado. Luego consideramos minitérminos de rango (n-1) y les aplicamos la operación de pegado. Marcamos los minitérminos pegados de rango (n-1) y anotamos los minitérminos resultantes de rango (n-2), etc. La etapa finaliza si los minitérminos recién obtenidos yo-ésimo rango ya no se mantienen unidos. Todos los minitérminos no marcados se denominan implicantes primos. Su disyunción es Abbr. Funciones DNF.

Pegamos minitérminos del cuarto rango y marcamos los minitérminos pegados con asteriscos

Formamos minitérminos de segundo rango:

Los implicantes primarios (simples) son:

2. Colocación de marcas

Para esta función Abr. DNF tiene la forma:

Para construir DNF y Abbr. DNF necesita desechar los intervalos adicionales. Construimos una tabla cuyas filas corresponden a los implicantes principales y las columnas corresponden a los minitérminos de SDNF. Si uno de los minitérminos incluye uno de los implicantes, entonces se coloca una marca en la intersección de la fila y columna correspondientes, por ejemplo, 1.

Continuación del ejemplo.

3. Encontrar implicantes esenciales

Si una columna contiene solo un 1, entonces el implicante principal que define esa fila se llama esencial. Por ejemplo, el implicante esencial es. El implicante esencial no puede eliminarse del Abbr. DNF, ya que sólo es capaz de cubrir algunos minitérminos de SDNF. Por lo tanto, excluimos de la tabla las filas correspondientes a estos implicantes y las columnas que tienen algunos en estas filas.

En este ejemplo, excluimos la fila y las columnas.

Como resultado obtenemos la tabla.

4. Tachar columnas y filas adicionales

Si la tabla resultante tiene columnas idénticas, tache todas menos una. Si después de esto aparece la tabla lineas vacias, luego los tachamos.

5. Selección de cobertura mínima con intervalos máximos

En la tabla resultante, seleccione un conjunto de filas que contenga unidades en todas las columnas. Teniendo en cuenta varias opciones posibles para tal elección, se da preferencia a la opción con el número mínimo de letras en las líneas que forman la cobertura.

Continuación del ejemplo.

La cobertura mínima de la tabla está formada por las filas correspondientes a los implicantes. Entonces MDNF tiene la forma:

El método de Quine tiene un inconveniente importante asociado con la necesidad de una comparación completa por pares de minitérminos en la etapa de construcción de Abbr. No abandonar. En 1956, McCluskey propuso una modernización de la primera etapa del método de Quine, lo que resultó en una reducción significativa en el número de comparaciones de minitérminos.

La idea del método McCluskey es la siguiente. Todos los minitérminos se escriben en forma de números binarios, por ejemplo, 1010. Estos números se dividen en grupos según la cantidad de unidades en el número, es decir, el i-ésimo grupo incluye números que tienen i unidades en su notación. La comparación por pares se realiza solo entre grupos adyacentes en número, ya que los minitérminos adecuados para pegar se diferencian entre sí en un solo dígito. Cuando se forman minitérminos con rango superior a cero, se coloca un guión en los dígitos correspondientes a las variables excluidas.

Ejemplo

Encontremos el MDNF para la función:

Minitérminos de 4º rango por grupos

Minitérminos de tercer rango

Miniterms 2do rango

Minitérminos sin etiquetar o implicantes primos

Construyendo una tabla de etiquetas

Ambos implicantes primarios son esenciales y determinan la cobertura mínima, es decir, MDNF tiene la forma.

Minimizar funciones lógicas es una de las tareas tipicas en el proceso de aprendizaje del diseño de circuitos. Por eso creo que un artículo así tiene cabida, espero que os guste.

¿Por qué es esto necesario?

La complejidad de una función lógica, y por tanto la complejidad y costo del circuito (circuito) que la implementa, es proporcional al número de operaciones lógicas y al número de apariciones de variables o sus negaciones. En principio, cualquier función lógica se puede simplificar directamente utilizando axiomas y teoremas de la lógica, pero, por regla general, tales transformaciones requieren cálculos engorrosos.

Además, el proceso de simplificación de expresiones booleanas no es algorítmico. Por tanto, es más recomendable utilizar especiales. métodos algorítmicos Minimizaciones que permiten realizar la simplificación de una función de forma más sencilla, rápida y sin errores. Dichos métodos incluyen, por ejemplo, el método de Quine, el método del mapa de Karnaugh, el método de prueba de implicantes, el método de matriz de implicantes, el método de Quine-McCluskey, etc. Estos métodos son los más adecuados para la práctica común, especialmente la minimización de una función lógica. utilizando mapas de Karnaugh. El método del mapa de Karnaugh conserva la claridad cuando el número de variables no supera las seis. En los casos en que el número de argumentos sea superior a seis, se suele utilizar el método Quine-McCluskey.

En el proceso de minimizar una función lógica particular, generalmente se tiene en cuenta sobre qué base sería más eficiente implementar su forma mínima utilizando circuitos electrónicos.

Minimizar funciones lógicas utilizando mapas de Karnaugh

Mapa de Carnot - método gráfico minimización de funciones de conmutación (booleanas), lo que proporciona relativa facilidad para trabajar con expresiones grandes y elimina posibles carreras. Representa las operaciones de pegado incompleto por pares y absorción elemental. Los mapas de Karnaugh se consideran la tabla de verdad de una función reorganizada en consecuencia. Los mapas de Carnaugh pueden considerarse como un desarrollo plano específico de un cubo booleano de n dimensiones.

Los mapas de Carnot fueron inventados en 1952 por Edward W. Veitch y mejorados en 1953 por Maurice Carnot, físico de Bell Labs, y estaban destinados a ayudar a simplificar los circuitos electrónicos digitales.

En un mapa de Carnaugh, las variables booleanas se transfieren de la tabla de verdad y se ordenan mediante el código Gray, en el que cada número siguiente difiere del anterior en solo un dígito.

El método principal para minimizar funciones lógicas presentadas en forma de SDNF o SCNF es la operación de pegado incompleto por pares y absorción elemental. La operación de pegado por pares se lleva a cabo entre dos términos (miembros) que contienen variables idénticas, cuyas apariciones (directas e inversas) coinciden para todas las variables excepto una. En este caso, todas las variables excepto una se pueden quitar de los corchetes y las apariciones directas e inversas de una variable que queda entre corchetes se pueden pegar. Por ejemplo:

La posibilidad de absorción se deriva de las igualdades obvias.

De este modo, tarea principal Al minimizar SDNF y SCNF, es necesario buscar términos adecuados para el pegado con posterior absorción, lo que para formas grandes puede resultar una tarea bastante difícil. Los mapas de Carnaugh proporcionan una forma visual de encontrar dichos términos.

Como se sabe, funciones booleanas N variables presentadas en forma de SDNF o SCNF pueden contener 2N términos diferentes. Todos estos términos constituyen una determinada estructura, topológicamente equivalente a un cubo de N dimensiones, y dos términos cualesquiera conectados por un borde son adecuados para el pegado y la absorción.

La imagen muestra mesa sencilla valor de verdad para una función de dos variables, un cubo (cuadrado) bidimensional correspondiente a esta tabla, así como un cubo bidimensional con la designación de términos SDNF y una tabla equivalente para agrupar términos:

En caso funciones de tres variables que tienes que tratar con un cubo tridimensional. Esto es más complicado y menos visual, pero técnicamente posible. La figura muestra un ejemplo de tabla de verdad para una función booleana. tres variables y su cubo correspondiente.

Como puede verse en la figura, para el caso tridimensional son posibles configuraciones de términos más complejas. Por ejemplo, cuatro términos que pertenecen a una cara de un cubo se combinan en un solo término con dos variables absorbidas:

EN caso general podemos decir que 2K términos que pertenecen a una cara K-dimensional de un hipercubo se pegan en un término y K variables se absorben.

Para simplificar el trabajo con funciones booleanas de una gran cantidad de variables, se propuso la siguiente técnica conveniente. El cubo, que representa la estructura de términos, se despliega sobre un plano como se muestra en la figura. Esto permite representar funciones booleanas con más de dos variables en forma de tabla plana. Cabe recordar que el orden de los códigos de términos en la tabla (00 01 11 10) no corresponde al orden números binarios, y las celdas ubicadas en las columnas extremas de la tabla están adyacentes entre sí.

De manera similar puedes trabajar con funciones de cuatro, cinco o más variables. En la figura se muestran ejemplos de tablas para N=4 y N=5. Para estas tablas conviene recordar que las celdas vecinas son las ubicadas en las celdas correspondientes de las columnas exteriores y las celdas correspondientes de la fila superior e inferior. Para tablas de 5 o más variables, también debes tener en cuenta que los cuadrados de 4x4 están prácticamente ubicados uno encima del otro en la tercera dimensión, por lo tanto, las celdas correspondientes de dos cuadrados de 4x4 adyacentes son adyacentes y los términos correspondientes se pueden pegar entre sí. .

Se puede compilar un mapa de Karnaugh para cualquier número de variables, pero es conveniente trabajar con no más de cinco variables. Básicamente, un mapa de Karnaugh es una tabla de verdad compilada en forma bidimensional. Gracias al uso del código Gray en él. línea superior es adyacente a la inferior, y la columna derecha es adyacente a la izquierda, es decir Todo el mapa de Carnot está colapsado en una figura de toro (dona). En la intersección de una fila y una columna, se inserta el valor correspondiente de la tabla de verdad. Una vez que la Tarjeta esté llena, puede comenzar a minimizar.

Si es necesario obtener el DNF mínimo, entonces en el Mapa consideramos solo aquellas celdas que contienen unos; si se necesita un CNF, entonces consideramos aquellas celdas que contienen ceros; La minimización en sí se lleva a cabo de acuerdo con las siguientes reglas (usando el ejemplo de DNF):

A continuación, tomamos la primera área y observamos qué variables no cambian dentro de esta área, escribimos la conjunción de estas variables, si la variable que no cambia es cero, le ponemos una inversión. Tome la siguiente área, haga lo mismo que con la primera y así sucesivamente con todas las áreas. Combinamos conjunciones de regiones por disyunción.
Por ejemplo (para mapas con 2 variables):

Para CNF, todo es igual, solo que consideramos celdas con ceros, las variables que no cambian dentro de una región se combinan en disyunciones (ponemos inversiones sobre variables unitarias) y las disyunciones de regiones se combinan en una conjunción. En este punto, la minimización se considera completa. Entonces, para el mapa de Karnaugh en la Fig. 1, la expresión en formato DNF se verá así:

En formato CNF: