Procedimientos de minimización. Análisis y síntesis de dispositivos lógicos. Métodos para minimizar funciones y circuitos lógicos. Funciones lógicas y su transformación.
Métodos de búsqueda de mínimos de funciones. La búsqueda de máximos se reduce a la búsqueda de mínimos cambiando el signo de la función. M.f. m es una rama de las matemáticas computacionales que juega un papel importante en aplicaciones como la selección óptima. Opciones en planificación, diseño e investigación de operaciones, tareas de gestión. procesos tecnológicos, control de movimiento objetos complejos etc. m también se utilizan para resolver sistemas de ecuaciones y desigualdades al encontrar el espectro de operadores, al resolver problemas de valores en la frontera, etc.
Los más estudiados son M. f. m - en relación con funciones definidas en todo el espacio euclidiano de dimensiones completas. Considerémoslos sin tocar los problemas de minimización discretos y discretos-continuos, así como los problemas de minimización en presencia de restricciones. Esto último en muchos casos puede reducirse al problema de la minimización incondicional (por ejemplo, utilizando funciones de penalización). No consideraremos métodos para encontrar el mínimo basado en el uso directo. condiciones necesarias extremo, ya que la solución de los sistemas resultantes de ecuaciones no lineales puede considerarse como el problema de minimizar la suma de residuos al cuadrado (o el módulo máximo de residuos). Posibilidad de aplicación y efectividad comparativa de varios M. f. m. está determinado en gran medida por la clase de funciones a las que se aplican. La mayoría de M. f. m permiten encontrar un mínimo local, y solo la información a priori sobre las propiedades de la función (convexidad, unimodalidad) nos permite considerar este mínimo global. Métodos que garantizan la búsqueda de un mínimo global con una precisión dada para un tiempo suficientemente clases generales Las funciones requieren mucha mano de obra. En
En la práctica, para encontrar el mínimo global se utiliza principalmente una combinación del método de Monte Carlo y uno de los métodos de minimización local.
Clase amplia M. f. m. se describe mediante el siguiente esquema computacional. Definamos la función a minimizar en un punto de partida elegido arbitrariamente. Supongamos que tiene derivadas parciales continuas hasta el orden inclusive, la consideraremos como una derivada de orden cero). para recibir aproximaciones sucesivas al mínimo local, se construye una secuencia de puntos de la siguiente forma:
donde denota el vector de derivadas parciales del orden de las funciones computables de sus argumentos. Se llama el orden de las derivadas parciales superiores calculadas para implementar la fórmula (1). orden del método. Básico Un grupo de métodos utilizados en la práctica tiene la particularidad de que la información necesaria para calcular el siguiente valor se expresa a través de un número limitado de parámetros calculados sobre este paso Y pasos previos proceso. El método se llama -paso si el esquema del algoritmo tiene, a partir de algunos, la siguiente estructura: en un paso calculamos los parámetros donde - algunos número natural, y un vector en términos de la siguiente forma:
(Los parámetros iniciales se calculan mediante procedimientos especiales). En los métodos de descenso ampliamente utilizados, el operador se especifica de la siguiente forma:
Dónde numero real, que se llama multiplicador de pasos, el vector determina la dirección de descenso. Entre los métodos de descenso destacan los métodos de descenso monótonos o métodos de relajación. El método es la relajación, si en k Beli es continuamente diferenciable, entonces la relajación del método (3) está asegurada cuando se forma la dirección de descenso ángulo agudo con la dirección del gradiente y es bastante pequeño. La teoría general de los procesos de relajación está más desarrollada para el caso de funciones convexas. como base parámetros que caracterizan el proceso, se consideran los ángulos de relajación entre ellos y la dirección del gradiente), así como los factores de relajación determinados por la igualdad
¿Dónde está el gradiente de la función (para una función cuadrática con el descenso más pronunciado)? Denotemos por el coeficiente reducido. relajación. Necesario y condición suficiente convergencia del proceso de relajación para una función fuertemente convexa:
Entre los métodos de relajación, los más famosos son los métodos de gradiente. Echemos un vistazo más de cerca a los métodos de gradiente de una sola etapa. Esquema general son los siguientes:
Dentro de este esquema se pueden distinguir las siguientes modificaciones:
A) descenso de gradiente con paso constante: matriz identidad;
b) descenso de pendiente más rápido: , donde se determina a partir de la condición mínima
c) Método de Newton-Raphson: , ¿dónde está el hessiano en el punto
d) circuitos intermedios: . Los métodos de gradiente de dos etapas más comunes incluyen métodos de gradiente conjugado; Un ejemplo de un esquema de dos etapas es el método del gradiente conjugado de Fletcher-Reeves:
Métodos a) y b) con suficiente condiciones generales(el primero, para una a suficientemente pequeña) converge a un mínimo local con una velocidad geom. progresión. El método c) en condiciones suficientemente generales converge desde una vecindad suficientemente pequeña del mínimo con una velocidad cuadrática. El esquema intermedio d) es más flexible y permite, con un cierto ajuste de las secuencias, obtener también una tasa de convergencia cuadrática a mayor requisitos débiles al planteamiento inicial.
La desventaja de los métodos c), d) es la necesidad de calcular el hessiano. Los métodos de gradiente conjugado y los llamados algoritmos de métrica variable, que tienen las propiedades de convergencia acelerada para funciones suficientemente suaves en las proximidades de un mínimo, están libres de este inconveniente. Los esquemas de algoritmos de métrica variable son, por naturaleza, una combinación del esquema de gradiente conjugado y el método de Newton-Raphson. Simultáneamente con el movimiento según un esquema como el de gradientes conjugados, se produce una aproximación iterativa de la matriz, que es la inversa de la hessiana en el punto mínimo. Después de cada n pasos del proceso hay un paso según el método de Newton-Raphson, donde en su lugar tiene lugar su aproximación.
Si el gradiente se rompe, los métodos anteriores no se aplican. Es por eso gran valor tener métodos para minimizar funciones convexas (no necesariamente diferenciables); Estos métodos se pueden dividir en 2 grupos: 1) métodos de tipo gradiente y 2) métodos de “plano de corte”. El grupo 1 incluye varias modificaciones del método del gradiente generalizado, así como esquemas con convergencia acelerada basados en estiramiento espacial. en la dirección del gradiente o de la diferencia de dos gradientes sucesivos. Los métodos del segundo grupo incluyen, por ejemplo, el método Kelly. Sea ZP un conjunto convexo (acotado) en el que se define una secuencia de puntos en los que se calcula el gradiente generalizado. Luego se encuentra como solución al problema: encontrar
El método de Kelly converge en el funcional para cualquier inicial. De los métodos de minimización habituales, cabe destacar, en particular, el método del barranco para minimizar funciones con hipersuperficies de nivel muy alargadas; coordinar métodos de búsqueda sistema de variables coordenadas; métodos de búsqueda aleatorios; métodos combinados de descenso rápido y búsqueda aleatoria, cuando la dirección de la función decreciente está determinada por el método de Monte Carlo; métodos de descenso diferencial, métodos de aproximación estocástica, etc. En problemas óptimos. de regulación, los métodos de búsqueda de orden cero son de gran importancia. Los algoritmos de minimización para este caso generalmente se basan en la idea de una aproximación lineal o cuadrática de la función que se minimiza o una aproximación en diferencias de las derivadas parciales correspondientes. Se han propuesto varios métodos para buscar el extremo global. Básico de los cuales: método Monte Carlo, una combinación del método Monte Carlo para determinar el punto de partida con uno de los algoritmos búsqueda local, métodos basados en la construcción de la envoltura inferior de una función dada, métodos de corte secuencial de subconjuntos, métodos de construcción de trayectorias que cubren densamente el dominio de definición de la función en todas partes y minimización a lo largo de estas trayectorias.
para resolver especial clases de problemas multiextremos, se utilizan métodos de programación dinámica.
Hoy en día se crean tiempos óptimos. Algoritmos para minimizar funciones de diferentes clases. Sea una clase de funciones definidas en el cubo y que tienen derivadas parciales hasta el orden s, que satisfacen la condición de Lipschitz con L constante. Cualquier algoritmo de minimización de , utilizando información sobre los valores de f y sus derivadas hasta el orden inclusive en no más de N puntos es equivalente (en el sentido del resultado) a algún algoritmo A para obtener una secuencia de iteraciones (1) y aproximar el valor deseado usando la operación final
¿Dónde hay alguna función computable? Introduzcamos la siguiente notación:
El algoritmo para el cual se logra el óptimo. Las condiciones significan optimización asintótica y optimización de orden del algoritmo, respectivamente. Se puede demostrar que.
Además, la elección de , afecta sólo a la constante en la estimación especificada. En un caso particular tenemos:
donde esta min. red en .
Otro enfoque para la construcción óptima. Los algoritmos de minimización están asociados con la generalización de ideas para soluciones estadísticas secuenciales. El algoritmo de minimización se considera como una secuencia controlada de experimentos, cada uno de los cuales da un resultado particular. Se determina una medida de probabilidad a priori en función del conjunto de resultados. Después de obtener un resultado específico del siguiente experimento, las probabilidades se redistribuyen según la fórmula de Bayes y se selecciona el siguiente experimento o se toma la decisión final. Los algoritmos se diferencian entre sí en la regla mediante la cual se selecciona el siguiente experimento, las reglas para detenerlo y elegir la solución final. La calidad de la solución está determinada por la función de pérdida, que se promedia de acuerdo con el resultado obtenido en en esta etapa distribución de probabilidad. En estos términos se plantea el problema de elegir el óptimo. Algoritmo como construcción de una regla bayesiana secuencial para encontrar soluciones. Esta formulación es interesante porque en su marco es posible tener en cuenta las propiedades estadísticas de la clase de problemas que se resuelven y comparar las pérdidas "promedio" asociadas con el error de la solución con los costos asociados con el refinamiento de la solución. Iluminado.: Lyubich Yu., Maistrovsky G. D. teoría general Procesos de relajación para funcionales convexos. “Avances en las Ciencias Matemáticas”, 1970, vol 25, siglo. 1; Mikhalevich V. S. Algoritmos de optimización secuencial y su aplicación. "Cibernética", 1965, N5 1-2; Ivanov V.V.Acerca de algoritmos optimos minimizando las funciones de algunas clases. "Cibernética", 1972, núm. 4; Salvaje D. Dk. Métodos para buscar el extremo. Por. del ingles M., 1967.
V. V. Ivanov, V. S. Mikhalevich, N. Z. Shor.
La operación más utilizada a la hora de minimizar funciones es la operación de pegado.
AB+ ВB=B (A+ В)=B.
Veamos los tres métodos de minimización más comunes.
1. Sea el número de conjuntos de cuatro variables sobre las que la función lógica toma un valor unitario: f (2,5,6,7,10,12,13,14)=1.
Expresemos esta función lógica en SDNF (no escribiremos el símbolo de conjunción):
F(0010,0101, 0110, 0111, 1010, 1100, 1101, 1110) =
En la primera etapa de minimización, el SDNF original se puede simplificar utilizando la ley de pegado, luego obtenemos:
Llamamos la atención sobre el hecho de que el mismo constituyente (implicante) puede unirse muchas veces con otros constituyentes (implicantes), ya que en la lógica de Boole se aplica la ley de idempotencia:
por lo tanto, cualquier constituyente se puede multiplicar.
En la segunda etapa utilizaremos la tabla de Quine (Tabla 8), según la cual este método La minimización recibió su nombre: el método de Quine. La tabla enumera todos los implicantes obtenidos en la primera etapa de simplificación verticalmente y los constituyentes iniciales horizontalmente. Unidad en tabla 8 se sitúa donde el implicante “cubre” al constituyente. El hecho es que el constituyente siempre puede ser reemplazado por un implicante o incluso por un término separado según la ley de absorción:
Tabla 8
Después de completar la tabla de Quine, terminamos con dos unidades en casi cada columna; Mientras tanto, basta con tener una unidad en el gráfico. Por lo tanto, siempre que sea posible, se deben eliminar las unidades redundantes. La elección de las unidades se realiza en función del número mínimo de términos (las unidades seleccionadas están sombreadas). Como resultado, resultó que podemos arreglárnoslas con sólo tres implicantes en lugar de seis:
Utilizando tablas de verdad, es fácil verificar que la función obtenida en el MNF reproduce todos los valores de la función original. Tenga en cuenta que en caso general Pueden existir varias soluciones basadas en el criterio de plazos mínimos.
2. No menos de manera eficiente La minimización de funciones lógicas es un método para combinar índices. Para presentarlo, hagamos una tabla. 9, en cuyas columnas se escriben posibles combinaciones de índices. La última columna contiene los valores de la función. El análisis de la tabla comienza desde la izquierda a lo largo de las columnas. El principio de exclusión de i, j_code es el siguiente. En la intersección de la columna i, por ejemplo, con una combinación de índices 23, y la fila j, por ejemplo, 3_th, está el código 10, que corresponde al implicante. Por lo tanto, en esta columna, dondequiera que aparezca el código 10, es decir, en las líneas 2, 3, 10 y 11, estos códigos quedan excluidos, ya que el valor de la función en la 3ª línea es cero. Ahora tomemos una columna con una combinación de índices 124. Aquí, los códigos 010 se dejan en las líneas 2 y 6, y el código 011 en las líneas 10 y 14. Esto se hace porque estos códigos se encuentran solo en líneas con un valor de función. igual a uno. Por el contrario, el código 110 de la misma columna aparece tanto con valores de función única como con valores cero.
Tabla 9
Entonces, todos los códigos están en líneas que terminan valores cero Las funciones se excluyen automáticamente. Si estos códigos se encuentran en líneas que terminan con un único valor de función, tampoco se tienen en cuenta. Sólo quedan aquellos códigos que se encuentran en líneas con un único valor de función (estos códigos están oscurecidos).
Luego sigue la siguiente regla. Para que una función tome un valor, igual a uno, basta con que sólo un implicante de la recta tome el valor unitario. En primer lugar, dejamos el implicante mínimo, que se superpone a los de las líneas 2, 6, 10 y 14. Luego, por supuesto, pasamos a la línea 12. Aquí dejamos el único código de la línea, 011, que corresponde al implicante. El mismo implicante es responsable de la línea 13, que también termina en una unidad. Queda por considerar las líneas quinta y séptima. Lo que tienen en común es el implicante: . Así, con tres implicantes cubrimos todos los valores individuales de la función, lo que coincide con el resultado obtenido a partir de las tablas de Quine.
3. Existe método gráfico pegado, que se denomina método del mapa de Karnaugh (presentado en la Tabla 10). Seleccionamos unidades adyacentes, estos serán los términos de nuestra función.
Tabla 10
Tenemos dos términos
aunque mesa 9 es más engorroso que la mesa. 8, el método de combinación de índices no se considera más complejo que el método de Quine, si recordamos que antes de compilar las tablas de Quine es necesario realizar numerosas concatenaciones de constituyentes e implicantes. Implementar el algoritmo del método de combinación de índices en una computadora resulta relativamente simple. Por el contrario, la simplicidad externa y la claridad del tercer método para minimizar funciones lógicas utilizando mapas de Karnaugh resultan ser programa complejo al implementar el algoritmo en una computadora.
Tabla 11
Tabla 12
El mapa de Karnaugh para cuatro variables se presenta en forma de tabla. 11. Cada celda del mapa corresponde a un constituyente. El mapa completo se presenta en la Tabla. 12 (la función es la misma que en los dos primeros métodos). Según la ley de pegado, siempre se pueden combinar dos constituyentes adyacentes con valores unitarios para obtener el implicante correspondiente. Además, aquellos que se encuentran en los límites del mapa también se consideran adyacentes. Qué unidades deben combinarse para obtener un implicante adecuado se pueden determinar fácilmente visualmente. También hay que recordar que de acuerdo con la ley de idempotencia, la misma unidad de la tabla. 12 se pueden pegar a dos o tres unidades adyacentes.
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 coste del circuito que la implementa, es proporcional al número operaciones lógicas y el 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 métodos algorítmicos especiales de minimización que permitan simplificar la 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 rutinaria, 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
El mapa de Karnaugh es una forma gráfica de minimizar las funciones de conmutación (booleanas), lo que proporciona relativa facilidad para trabajar con expresiones grandes y elimina carreras potenciales. 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 de función tres variables Tienes que lidiar 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 un valor booleano. funciones de tres variables y el 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 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 facilitar el trabajo con funciones booleanas gran número 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. .
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, combinamos variables que no cambian dentro de una región en disyunciones (ponemos inversiones sobre variables unitarias) y combinamos las disyunciones de regiones 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:
Todas las funciones lógicas se especifican como fórmula o como tabla de valores. A veces es necesario determinar forma más simple registrar esta función con un número mínimo de funciones lógicas elementales Y, O, NO para facilitar su uso. Para ello se utilizan todas las operaciones consideradas a partir del No. 4 y los métodos de Quine y Veitch.
El método de Quine le permite encontrar la forma disyuntiva normal más simple de una expresión lógica, es decir, anotar expresión lógica en forma de disyunción o conjunción, mientras que el signo de inversión puede aparecer sólo sobre un argumento o no aparecer en absoluto. El algoritmo se proporciona en literatura especializada.
Método Veitch (mapas de Karnaugh)
En este método, para representar una función de n variables, se dibuja una tabla especial que contiene 2n celdas. Cada celda corresponde a uno de los conjuntos de n variables. La celda registra el valor aceptado por la función para este conjunto de argumentos. Todas las celdas correspondientes a conjuntos que contienen alguna variable sin el signo de inversión forman un área de 2 n -1 celdas. Esta zona se llama área de una variable dada(por ejemplo, el alcance de la variable x). Las celdas restantes forman la región de esta variable inversa. Los posibles conjuntos de argumentos se distribuyen entre las celdas de tal manera que los límites de las áreas de todas las variables y sus inversiones sean claros, y la pertenencia de cualquier celda a un área particular se identifique visualmente fácilmente.
1) Función de una variable:
2) Función de dos variables:
3) Diagrama de disyunción:
4) Diagrama de conjunción:
5) Por tres argumentos:
6) Por cuatro argumentos:
Puede minimizar una expresión booleana determinada agrupando parado cerca unidades y al mismo tiempo excluir la variable que pasa del estado directo al inverso. Puede combinar no solo vertical y horizontalmente, sino también a lo largo de los bordes, ya que en el caso general el mapa de Karnaugh forma un toro. Ejemplo:
b) 
8.3. Métodos analíticos minimizar las funciones de conmutación
El método de Quine..
El método se basa en la comparación por pares y en la unión, si es posible, de todos los constituyentes (miembros del SDNF). Para ello, se compara cada constituyente con los siguientes, lo que conduce a la obtención de un implicante. Los implicantes resultantes se comparan nuevamente y, si es posible, se pegan entre sí, etc. hasta que los implicantes restantes ya no puedan unirse. Estos son implicantes simples; su disyunción es un DNF abreviado.
Para ordenar, es aconsejable dividir los constituyentes en grupos según el número de variables no invertidas. En este caso, cada constituyente sucesivo, comenzando desde arriba, se compara sólo con los constituyentes del grupo adyacente debajo, con el número de variables no invertidas uno más.
Sea una función de conmutación definida por SDNF:
Dividamos los constituyentes en grupos según el número de variables no invertidas.
El número romano del número de grupo corresponde al número de variables no inversas. Dibujemos líneas que indiquen los componentes que se van a pegar. El resultado del pegado es siempre una conjunción elemental, que es parte común Conjunciones originales (en particular, constituyentes).
Los implicantes resultantes también permiten pegarlos, y el resultado es el mismo implicante. 
.
Es imposible seguir pegando, por lo que los implicantes resultantes son simples y el DNF abreviado tiene la forma:
Se completa la primera etapa. En la segunda etapa, es necesario eliminar los implicantes primos innecesarios. Esto se hace utilizando una mesa de implicantes de Quine especial (mesa de cobertura). Las filas de la tabla están marcadas con implicantes simples de la función de conmutación, es decir miembros del DNF abreviado, y las columnas son constituyentes de la unidad, es decir miembros de la función de conmutación SDNF.
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 tabla de implicantes en la intersección de la fila de un implicante simple dado y las columnas con los constituyentes de la unidad está marcada, por ejemplo, con un signo "+". Los DNF mínimos se construyen utilizando la tabla de implicantes de la siguiente manera:
1) se buscan las columnas de la tabla de implicantes que tienen una sola cruz; los implicantes simples correspondientes a estas cruces se denominan básicos y forman el llamado núcleo de la función de conmutación. El núcleo está necesariamente incluido en el DNF mínimo;
2) se consideran varias opciones para elegir un conjunto de implicantes simples que cubrirán con cruces las columnas restantes de la matriz de implicantes, y se seleccionan opciones con el número total mínimo de letras.
El núcleo de nuestra función (Tabla 35) son los implicantes 
y x 1 x 2 x 3, es decir la función tiene un punto muerto único y un DNF mínimo:
Tabla 35
Tabla de implicantes de Quine
|
Electores 1 (miembros del SDNF) |
|||||||
|
implicantes |
|
|
|
|
|
|
|
|
| |||||||
Se puede ver que el implicante x 2 x 3 x 4 es redundante, ya que cubre constituyentes ya cubiertos por implicantes 
, x 1 x 2 x 3 .
El número de cruces en una línea es una potencia de 2; Además, puedes asegurarte de que sea igual a N=2 n - k, donde k es el número de letras de un implicante simple, n es el número de variables de las que depende la función.
Si el SDNF no se especifica al principio, entonces debe obtenerse utilizando, por ejemplo, métodos que ya conocemos.
Está claro que para tablas de implicantes grandes es difícil identificar visualmente opciones con un número mínimo de letras. Por lo tanto, se utiliza el método de Petrik, que permite obtener todos los DNF sin salida de una tabla de implicantes mediante la construcción de su denominada representación conjuntiva. Para hacer esto, todos los implicantes simples se denotan con letras diferentes (A, B, C en la Tabla 35), y luego, para cada columna, se construye una disyunción de todas las letras que denotan filas de la tabla, cuya intersección con una columna determinada es marcado con una cruz. La representación conjuntiva de la matriz implicante se forma como una conjunción de las disyunciones construidas para todas las columnas. Todas las relaciones del álgebra de Boole de funciones de conmutación se pueden aplicar a la representación conjuntiva de la tabla de implicantes para simplificarla. Después de abrir los paréntesis y realizar todas las absorciones posibles, obtenemos una disyunción de conjunciones, cada una de las cuales contiene todos los implicantes del callejón sin salida DNF.
Esto significa que un DNF sin salida contiene dos implicantes principales ( 
y al mismo tiempo C=x 1 x 2 x 3) y tiene la forma:
Método de Quine-McCluskey.
El método es una formalización del método de Quine, orientado al uso de ordenadores. La formalización consiste en registrar los constituyentes de la unidad (miembros del SDNF) con sus números binarios. Todos los números se dividen en grupos disjuntos según el número de unos en el número binario. Los enlaces se realizan sólo entre grupos adyacentes. La categoría a eliminar se indica con el signo “–” (“guión”). A partir de los implicantes resultantes se forman otros grupos teniendo en cuenta la misma ubicación del guión. Esta designación de implicantes se denomina códigos generalizados. Sea dada una función lógica
111101001000110.
Agrupemos estos constituyentes de una unidad por el número de unidades:
Ya no es posible pegar más. Los DNF mínimos se encuentran luego usando la tabla de implicantes (Tabla 36):
Esto significa que los DNF sin salida contienen tres implicantes principales y tienen la forma:
(dos inversiones);
(tres inversiones).
Tabla 36
Tabla de implicantes de Quine-McCluskey
|
implicantes |
Componentes de unidades |
|||||||
Tenga en cuenta que pegar dos implicantes con un guión sólo es posible si están colocados apropiadamente, por ejemplo:
|
|
|
|
|
Puede elegir cualquiera de los TDNF obtenidos y, teniendo en cuenta el menor número de inversiones, la primera.
Método de Blake-Poretsky.
El método permite obtener un DNF reducido de una función booleana a partir de su DNF arbitrario, y no del SDNF, como en los métodos de Quine y Quine-McCluskey, utilizando la ley de pegado generalizado. El método se basa en la siguiente afirmación: si en un DNF arbitrario de una función booleana se realizan todas las operaciones posibles inversas al pegado generalizado y luego se realizan todas las absorciones, entonces el resultado es un DNF reducido de la función.
Sea la función DNF:
Se puede observar que la ley de pegado generalizado con respecto a la variable x 1 se puede aplicar a la primera y segunda conjunciones; obtenemos:
Lo mismo para la primera y tercera conjunciones:
aquellos. ¡Todo sigue como está!
La segunda y tercera conjunciones admiten un pegado generalizado a lo largo de x2:
Pasemos al DNF:
Luego de aplicar la ley de idempotencia (repetición) y absorción obtenemos:
Los intentos de seguir utilizando la unión y la absorción generalizadas no dan resultados. En consecuencia, se obtiene una función DNF reducida.
Tabla 37
Tabla implicante para ilustrar el método de Blake-Poretsky
|
implicantes |
Conjuntos de funciones y sus significados |
|||||||||
Por lo tanto, los conjuntos de trabajo (unitarios) pueden estar cubiertos por tres implicantes principales, p. 
,
,
. El núcleo incluye implicantes. 
,
. Entonces los DNF de punto muerto tienen la forma:
(mejor en términos del número de inversiones).
