Métodos para minimizar funciones lógicas. Minimización de funciones lógicas. Diagrama lógico del algoritmo en notación de Lyapunov.
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í:
Comparando el método del mapa de Karnaugh con otros métodos de minimización de funciones, podemos concluir que el primero es el más adecuado para la ejecución manual. El tiempo de trabajo manual se reduce significativamente (debido a representación visual implicantes adhesivos). Implementación de software Este método tiene sus propias dificultades. Por lo tanto, será muy difícil implementar elección óptima rectángulos regulares, especialmente para gran número argumentos.
1.3.5 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.
El sistema se muestra en la página siguiente.
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:
V = 1 VVVVVV = 1 VVV V VV = 1 V = 1 VVV = 1 VVVVVV = 1 VVV = 1 VVVVV = 1 VVV = 1Ahora, en cada línea debe seleccionar el coeficiente del rango mínimo y equipararlo a uno, y los coeficientes restantes a 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).
= 1 = 1 = 1 = 1 = 1Escribamos ahora las conjunciones correspondientes a coeficientes iguales a la unidad. Obtendremos el DNF mínimo.
F(X 1 X 2 X 3 X 4) = X 1 X 3 V X 2 X 3 V X 3 X 4 V X 1 X 2 X 4 V X 1 X 2 X 4 .
Entonces, obtuvimos el DNF mínimo de varias maneras. En todos los casos resultó ser el mismo, es decir, cualquiera de los métodos descritos se puede utilizar para minimizar la función. Sin embargo, estos métodos difieren significativamente entre sí tanto en el principio de búsqueda de MDNF como en el tiempo de ejecución. El método del mapa de Karnaugh es muy conveniente para cálculos manuales. Es visual y no requiere operaciones de rutina, y elegir la ubicación óptima de los rectángulos correctos no es difícil. Si bien la implementación mecánica de este método se complica por la necesidad de encontrar ubicación óptima rectángulos. Naturalmente, el uso de otros métodos (método de Quine, método de Quine-McCluskey, método de coeficientes indefinidos) para cálculos manuales es inadecuado. Son más adecuados para la implementación mecánica, ya que contienen una gran cantidad de operaciones simples repetidas.
Tarea 2.
2.1 Diagrama algorítmico del método de Quine
1. Comienzo.
2. Ingrese la matriz DSNF de la función original.
3. Verifique las líneas i-ésima (i=1,m-1: donde m es el número de líneas en el DSNF) y j-ésima (j=i+1, m) para pegar. Si las líneas están pegadas, vaya al paso 6; de lo contrario, vaya al paso 5.
4. Forme una matriz de implicantes simples, habiendo marcado previamente con el símbolo '*' la variable mediante la cual se unen estas cadenas.
5. Vaya al paso 2.
6. Escriba una línea que no se fusione con ninguna otra línea en la matriz final.
7. Vaya al paso 2.
8. Salida de la matriz resultante.
Diagrama lógico del algoritmo en notación de Lyapunov.
V H V 1 z 1 V 2 ¯ V 3 V 4 VK
VH – comienzo.
V 1 – ingrese la matriz DSNF de la función original.
V 2 – formar una matriz de implicantes simples, habiendo marcado previamente con el símbolo '*' la variable mediante la cual se unen estas cadenas.
V 3: una cadena que no se fusiona con ninguna otra cadena se escribe en la matriz final.
V 4 – salida de la matriz resultante.
Z 1: si las líneas están pegadas, vaya al paso 3; de lo contrario, vaya al paso 5.
VK – fin.
Diagrama gráfico del algoritmo.
 |
Descripción máquina procedimientos
Procedimiento atascado (S1, S2: Diz; IndexS1, IndexS2: byte);
Este procedimiento une las dos disyunciones que se le pasan. Las cláusulas se especifican en los parámetros S1, S2. Los índices IndexS1, IndexS2 determinan los índices de estas cláusulas en la matriz de trabajo principal. El algoritmo del procedimiento es el siguiente: primero se busca el número de caracteres que están pegados. Si hay 0 de ellos, entonces son iguales y solo uno de ellos se escribe en la matriz final. Si es 1, entonces la ubicación del símbolo está determinada por el cual estas dos disyunciones se unen, y reemplazamos este símbolo con '*'. Todos los resultados obtenidos se ingresan en la matriz REZ.
Todas las demás funciones y procedimientos del programa están relacionados con acciones sobre matrices, es decir, no están directamente relacionados con este método de búsqueda de MDNF. Por tanto, no tiene sentido describirlos.
2.2 Diagrama algorítmico del método de Petrik
1. Comienzo.
2. Ingrese la matriz DSNF de la función original y los implicantes simples obtenidos en el método de Quine.
3. Crea una tabla de etiquetas.
4. Utilizando la tabla de etiquetas, construya una conjunción de disyunciones, cada una de las cuales sea un conjunto de los implicantes que están en esta columna tener marcas.
trabajar en el tema
MÉTODOS DE MINIMIZACIÓN
FUNCIONES LÓGICAS
Conceptos clave: expresiones lógicas, funciones lógicas, métodos de minimización, inversión, conjunción, disyunción, implicación, equivalencia.
Contenido
Introducción
Las personas que están alejadas de la tecnología suelen mirar las computadoras y otros dispositivos digitales. dispositivos electronicos como algo misterioso e incomprensible. Sin embargo, todos estos dispositivos funcionan estrictamente de acuerdo con leyes lógicas claras. Conocer y comprender estas leyes ayuda a comunicarse con una computadora y otros dispositivos digitales.
Los principios de construcción de un circuito de dispositivo digital están determinados por funciones lógicas. 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 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.
Una función simplificada contendrá menos operaciones y combinaciones de argumentos, lo que significa que el circuito que implementa la función contendrá menos elementos, es decir Será más barato y más confiable.
En este sentido, minimizar funciones lógicas es especialmente relevante.
Objetivo El trabajo consiste en estudiar métodos para minimizar funciones de álgebra lógica.
Objeto El trabajo implicó el proceso de minimización de funciones lógicas.
Artículo investigación: métodos para minimizar funciones lógicas y métodos para enseñar este tema en clases especializadas.
Tareas investigación:
aprender los elementos básicos lógica matemática;
explorar métodos para minimizar funciones lógicas;
seleccionar tareas para el trabajo independiente;
resolver los problemas seleccionados utilizando los métodos descritos.
El trabajo consta de una introducción, dos apartados, una conclusión y una lista de referencias.
La introducción fundamenta la relevancia del tema y define el propósito y los objetivos del estudio.
La primera sección analiza los fundamentos lógicos del funcionamiento de una computadora.
La segunda sección revela métodos para minimizar funciones lógicas y proporciona ejemplos de resolución de problemas utilizando los métodos descritos.
En conclusión, se resumen los resultados generales del estudio.
Conceptos básicos de lógica funcionamiento de la computadora
Elementos de la lógica matemática.
Las computadoras son dispositivos automáticos, cuyos principios operativos se basan en las leyes elementales de la lógica binaria.
Computadoras de todas las generaciones consistió y consta de elementos lógicos y elementos de memoria que toman dos valores (bits) 0 y 1. Todo el procesamiento de información en una computadora de todos sus bloques lógicos, circuitos lógicos y dispositivos se basó y se basará en las leyes y Principios de la lógica matemática.
La lógica (del griego antiguo logos, que significa "palabra, pensamiento, concepto, razonamiento, ley") es una ciencia antigua que estudia la exactitud de los juicios, el razonamiento y la evidencia.
La lógica matemática es una disciplina matemática que estudia la técnica de la prueba.
El fundador de la lógica matemática es el gran matemático alemán Gottfried Wilhelm Leibniz (1646 – 1716). Propuso la idea de utilizar el simbolismo matemático en lógica y construir cálculos lógicos, y planteó el problema. razón fundamental matemáticas, jugado papel importante en la historia de la creación de computadoras electrónicas: propuesto para su uso con fines de matemáticas computacionales sistema binario Estimación. Sobre los cimientos puestos por Leibniz, el matemático irlandés George Boole construyó un edificio nueva ciencia– la lógica matemática, – que, a diferencia del álgebra ordinaria, no opera con números, sino con enunciados. En honor a D. Boole, las variables lógicas en el lenguaje de programación Pascal se denominaron posteriormente booleanas.
La lógica matemática estudia la aplicación de métodos matemáticos para resolver problemas lógicos y construir circuitos lógicos que subyacen al funcionamiento de cualquier computadora. Los juicios en lógica matemática se denominan enunciados o expresiones lógicas.
Un enunciado es cualquier enunciado sobre el cual se puede decir si es verdadero o falso, es decir. si corresponde o no a la realidad; Se trata de una notación simbólica que consta de cantidades lógicas (constantes o variables) unidas por operaciones lógicas (conectivas).
Varias expresiones lógicas (declaraciones) sólo pueden tener dos significados: "verdadero" o "falso". Cada variable booleana sólo puede tomar un valor. Hay diferentes opciones denotaciones de verdad y falsedad:
Verdadero
Y
Verdadero
t
1
Mentir
l
FALSO
F
0
Las declaraciones pueden ser simples o complejas. Las simples corresponden a variables algebraicas y las complejas son análogas a las funciones algebraicas. Las funciones se pueden obtener combinando variables mediante acciones lógicas (operaciones).
Consideremos operaciones lógicas con las que puedes escribir cualquier expresión lógica.
La operación lógica más simple es la operación NOT (en otras palabras, a menudo se la llama negación, suma o inversión y se denota ). El resultado de una negación es siempre lo contrario del significado del argumento. Otros palabras simples, esta operación significa que la partícula “no” o las palabras “no es cierto que” se agregan a la expresión lógica original.
Así, por negación alguna declaración es una afirmación que es verdadera cuando falso y falso cuando verdadero.
La operación lógica NO es unaria, es decir tiene un solo operando. La definición de una negación se puede escribir utilizando la llamada tabla de verdad, que especifica qué valores de verdad (1, 0) toma la negación. dependiendo de los valores de verdad del enunciado original :
1
0
0
1
El AND lógico (multiplicación o conjunción lógica) es una expresión lógica compleja que se considera verdadera si y solo si ambas expresiones simples son verdaderas, en todos los demás casos esto expresión compleja FALSO. Conjunción de declaraciones y denota: , y a veces simplemente escriben . Las declaraciones en conjunción están conectadas por la conjunción "y". La definición de conjunción se puede escribir como una tabla de verdad, en la que para cada uno de los cuatro posibles conjuntos de valores de los enunciados originales Y se establece el significado correspondiente de la conjunción :
1
1
1
1
0
0
0
1
0
0
0
0
La definición de conjunción de dos enunciados se extiende naturalmente a cualquier número finito de componentes: conjunción A 1 &A 2 &A 3 &...& A norte verdadero si y solo si todas las afirmaciones son verdaderas A 1 , A 2 , A 3 , ...A norte(y, por tanto, falsa cuando al menos una de estas afirmaciones es falsa).
OR lógico (suma o disyunción lógica) es una expresión lógica compleja que es verdadera si al menos una de las expresiones lógicas simples es verdadera y falsa si y solo si ambas expresiones lógicas simples son falsas. Disyunción de declaraciones Y denotamos por el símbolo y leeremos: o . La definición de disyunción se puede escribir como una tabla de verdad:
1
1
1
1
0
1
0
1
1
0
0
0
La definición de disyunción de dos enunciados se extiende naturalmente a cualquier número finito de componentes: disyunciónA 1 A 2 A 3 ... A norte Verdadero si y sólo si al menos una de las afirmaciones es verdadera.A 1 , A 2 , A 3 , ..., A norte (y por tanto falso cuando todas estas afirmaciones son falsas).
Las operaciones Y, O y NO forman sistema completo operaciones lógicas, a partir de las cuales se puede construir una expresión lógica arbitrariamente compleja. Pero además de ellas, existen otras operaciones lógicas.
La implicación lógica (implicación) es una expresión lógica compleja que es verdadera en todos los casos, excepto cuando una mentira se deriva de la verdad. Es decir, esta operación lógica conecta dos expresiones lógicas simples, de las cuales la primera es una condición (), y el segundo ( ) es una consecuencia. Denotemos la implicación por el símbolo. y la entrada " "leeremos: "De sigue."
Escribamos esta definición en forma de tabla de verdad:
1
1
1
1
0
0
0
1
1
0
0
1
La afirmación "Si, entonces" desde un punto de vista lógico tiene el mismo significado que la afirmación "no es cierto lo que es verdadero y falso". Esto significa que la función de implicación puede sustituirse por una combinación de dos funciones (negación y conjunción).
Una identidad lógica (equivalencia) es una expresión lógica compleja que es verdadera si y sólo si ambas expresiones lógicas simples tienen la misma verdad. La equivalencia se indica con el símbolo y la entrada “” se lee “equivalentemente”, o “equivalentemente”, o “ , si y sólo si », « entonces y sólo si " La definición de equivalencia se puede escribir como una tabla de verdad:
1
1
1
1
0
0
0
1
0
0
0
1
Funciones lógicas y su transformación.
Una función lógica es una función de variables lógicas que sólo puede tomar dos valores: 0 o 1. A su vez, la propia variable lógica (el argumento de una función lógica) también sólo puede tomar dos valores: 0 o 1.
Cada función lógica se puede especificar. un gran número funciones de diversos tipos. Pero incluso cualquier función lógica bastante compleja se puede implementar con un conjunto relativamente simple de operaciones lógicas básicas. La base más conocida es un conjunto de funciones "y", "o", "no".
Para las operaciones de conjunción, disyunción e inversión se han definido leyes que permiten transformaciones idénticas (equivalentes) de expresiones lógicas:
;
.
Basándose en las leyes, es posible simplificar expresiones lógicas complejas.
Por razones de conveniencia de transformaciones posteriores, se toman como puntos de partida los dos siguientes: formas canónicas representaciones de funciones: forma normal disyuntiva perfecta (PDNF) y forma normal conjuntiva perfecta (PCNF).
Antes de pasar a SDNF y SKNF, introduzcamos algunos conceptos.
Una conjunción elemental es una conjunción de varias variables, tomadas con o sin negación, y entre las variables puede haber otras idénticas.
Una disyunción elemental es la disyunción de varias variables, tomadas con o sin negación, y entre las variables puede haber otras idénticas.
Cualquier disyunción de conjunciones elementales se denomina forma normal disyuntiva, es decir, DNF.
Por ejemplo, la expresión es abandono.
Cualquier conjunción de disyunciones elementales se denomina forma normal conjuntiva, es decir, CNF.
Por ejemplo, la expresión es KNF.
Un DNF perfecto (PDNF) es un DNF en el que no hay conjunciones elementales iguales y todas contienen las mismas variables, con cada variable solo una vez (posiblemente con negación).
Por ejemplo, la expresión es DNF, pero no SDNF; expresión es SDNF.
Un CNF perfecto (SCNF) es un CNF en el que no hay disyunciones elementales iguales y todas contienen las mismas variables, con cada variable solo una vez (posiblemente con negación).
Por ejemplo, la expresión .
Daré algoritmos para transiciones de una forma a otra. Naturalmente, en casos concretos (para un determinado enfoque creativo) el uso de algoritmos puede requerir más mano de obra que transformaciones simples utilizando un tipo específico de este formulario:
transición de la asignación de función arbitraria a DNF
Esta transición se reduce a omitir inversiones comunes para varias variables, abrir paréntesis y combinar, si surgen, términos idénticos utilizando las leyes:
Por ejemplo:
transición de DNF a KNF
El algoritmo para esta transición es el siguiente: ponemos dos negaciones encima del DNF y, usando las reglas de De Morgan (sin tocar la negación superior), reducimos la negación del DNF de nuevo a DNF. En este caso, hay que abrir los corchetes utilizando la regla de absorción. La negación (superior) del DNF resultante (nuevamente según la regla de Morgan) nos da inmediatamente el CNF:
La segunda forma de pasar de DNF a CNF es utilizar la ley distributiva:
transición de KNF a DNF
Esta transición se logra simplemente abriendo los paréntesis (usando nuevamente la regla de absorción):
transición de KNF a SKNF
Esta transición se realiza de forma similar a la anterior: si a una disyunción simple le falta alguna variable, por ejemplo,z , luego agrégale la expresión (esto no cambia la disyunción en sí), después de lo cual abrimos los corchetes usando la ley de distribución:
transición de DNF a SDNF
Si a alguna conjunción simple le falta una variable, por ejemplo,z , luego multiplicamos la conjunción incompleta por una expresión de la forma , después de lo cual abrimos los corchetes (no escribimos términos disjuntos repetidos). Por ejemplo:
Para obtener SDNF y SCNF a partir de tablas de verdad, debes realizar los siguientes 4 puntos del algoritmo:
SDNF
SKNF
La construcción de SDNF y SKNF comienza con una tabla de verdad.
Marquemos aquellas filas de la tabla cuyas salidas son iguales
1
0
Para cada línea marcada, escribimos una combinación de variables usando el signo
conjunción (&)
disyunción (V)
Ordenamos los signos de la operación de negación de la siguiente manera:
si una variable es igual a 1, entonces escribimos esta variable; si es igual a 0, entonces escribimos su negación.
si una variable es igual a 0, entonces escribimos esta variable; si es igual a 1, entonces escribimos su negación.
Conectamos todas las expresiones resultantes con la operación.
disyunciones
conjunciones
Habiendo recibido SDNF o SKNF, puede compilar circuito electronico, implementando esta función lógica. Para construirlo se requieren 3 elementos lógicos:
inversor
conjunto
disyuntor
Pero la mayoría de las veces el SDNF contiene muchos términos y la tarea es reducir su número y simplificar la expresión lógica. Para simplificar funciones lógicas, puede utilizar las leyes de la lógica indicadas anteriormente. Para el mismo propósito, se han desarrollado métodos especiales, que se discutirán en la siguiente sección.
Minimizar funciones lógicas
Como se señaló en el capítulo anterior, una función lógica se puede representar como una tabla de verdad o como PDNF (forma normal disyuntiva perfecta) o CKNF (forma normal conjuntiva perfecta) y se puede utilizar para obtener el circuito lógico de un dispositivo. Sin embargo, el circuito lógico resultante generalmente no será óptimo. Es por eso etapa importante La síntesis de circuitos lógicos es la minimización de funciones lógicas.
La minimización es la transformación de funciones lógicas para simplificar su representación analítica.
Hay dos direcciones para la minimización:
La forma más corta de notación (esto produce las formas más cortas KDNF, KKNF, KPNF);
Obtener el formulario de grabación mínimo (obtener el número mínimo de caracteres para escribir la función completa a la vez).
Pero cabe señalar que ninguno de los métodos de minimización es universal.
Se han desarrollado varios métodos para minimizar funciones de álgebra lógica:
método de transformaciones directas de funciones lógicas;
método para minimizar funciones lógicas utilizando mapas de Karnaugh;
método de Quine-McCluskey;
método de Blake-Poretsky;
El método de Petrik y otros.
Detengámonos con más detalle en los dos primeros métodos.
Método de transformaciones directas de funciones lógicas.
uno de métodos simples La minimización es un método de transformaciones directas, que se lleva a cabo utilizando los teoremas básicos del álgebra lógica.
Al utilizar este método:
Las funciones lógicas SDNF están escritas,
La forma se transforma y simplifica utilizando los axiomas del álgebra lógica y, en particular, se identifican los términos vecinos (miembros) en el SDNF original, en el que hay una variable no coincidente.
La ley del pegado se aplica a los términos vecinos.
Los términos formados al pegar se llaman implicantes.
Los implicantes obtenidos después del encolado se pegan entre sí, si es posible, hasta que el encolado resulte imposible.
La función obtenida como resultado de la minimización se llama función sin salida.
Sea dada la función
Lo minimizamos utilizando el método descrito anteriormente. Para hacer esto, agregamos un término más. y utilizar las leyes del pegado.
Tenemos la función mínima.
El método considerado de minimización mediante transformaciones directas es bastante simple, especialmente cuando un pequeño número variables. La desventaja del método es que no indica una ruta de minimización estrictamente formalizada. Con una gran cantidad de variables, los minitérminos se pueden agrupar de manera diferente, lo que da como resultado diferentes formas simplificadas. función dada. Sin embargo, no se puede estar seguro de que alguna de estas formas sea mínima. Es posible que se haya obtenido alguna de las formas sin salida, que ya no está simplificada, sin ser mínima.
Método para minimizar funciones lógicas usando mapas de Karnaugh.
Mapa de Carnaugh o mapa de Veitch (diagrama) – método gráfico minimizar funciones de álgebra lógica.
Los mapas de Karnaugh son útiles cuando hay una pequeña cantidad de variables.
Los mapas de Carnaugh representan una tabla de verdad específica, generalmente para dos, tres y cuatro variables, y difieren entre sí en la forma en que designan las filas y columnas de las tablas de verdad.
En la figura. 1 muestra mapas de Veitch para dos, tres y cuatro variables, respectivamente.
arroz. 1
Ubicación de grupos de variables. incógnita No importa, sólo es necesario que cada celda se diferencie de cualquier celda vecina en una sola variable. Según la forma aceptada de construir mapas, las celdas de la primera y última fila, y las celdas de la primera y última columna también se consideran adyacentes. El número de celdas del mapa es igual al número de combinaciones posibles de valores de variables (términos) y en cada celda se escribe el valor de una función lógica correspondiente a un conjunto dado de variables. Si alguna de las combinaciones posibles está presente en una disyuntiva perfecta forma normal(SDNF), luego se coloca “1” en la celda correspondiente del mapa de Karnaugh. Si no hay ningún término en la función resultante, entonces se coloca "0" en la celda correspondiente del mapa de Carnaugh.
Por ejemplo, la función considerada en el ejemplo anterior.
dado por la mesa La verdad (Fig. 2 a) también se puede minimizar utilizando mapas de Karnaugh. El mapa de Karnaugh tendrá la forma que se muestra en la Fig. 2b.
arroz. 2
En el mapa de Carnaugh hay lógicas. 1 , escrito en celdas adyacentes, indican que correspondientes a estas 1 las conjunciones (productos) se diferencian sólo en una variable, que se complementan entre sí y pueden omitirse.
Entonces, en la primera línea del mapa de Karnaugh (ver Fig. 2 b) la variable incógnita , ocurre en combinación con incógnita 1 Y incógnita 2 , que se complementan entre sí:
Por lo tanto, al agrupar dos celdas adyacentes en línea superior(contorno en la Fig. 2 b), se puede excluir una variable: incógnita 1 .
De manera similar, al agrupar dos celdas adyacentes en la columna de la izquierda (contorno en la Fig. 2 b) y excluir variables diferentes, obtenemos una expresión simplificada: incógnita 2 .
Las expresiones simplificadas resultantes se combinan mediante la operación O.
De esta forma, las celdas adyacentes en un mapa de Karnaugh se pueden agrupar para eliminar una variable. El número de células agrupadas puede ser superior a dos, pero su número debe ser par y deben estar en contacto (vecinas) entre sí.
También es posible tener varios grupos de celdas superpuestas, como en el ejemplo que acabamos de comentar.
Las celdas de la primera y última fila, la primera y la última columna también se pueden agrupar, es decir, el mapa se puede enrollar formando un cilindro tanto a lo largo del eje vertical como del horizontal.
excluir norte variables, el número total de celdas agrupadas debe ser igual a 2 norte. Por lo tanto, para excluir una variable, es necesario combinar dos celdas vecinas, y para excluir tres variables, ya es necesario combinar ocho celdas vecinas.
Por lo tanto, para obtener una función lógica minimizada, es necesario agrupar todas las celdas vecinas del mapa de Carnaugh que contienen 1 y luego combinar los grupos resultantes mediante la operación OR. Las celdas que contienen 1, que no se pueden combinar con otras celdas, forman términos independientes en la función lógica minimizada, cada una de las cuales contiene todas las variables.
Veamos varios ejemplos de mapas de Veitch y formas de construir contornos para agrupar celdas vecinas para obtener una función lógica simplificada.
Por tanto, el mapa de Veitch para la función lógica
se muestra en la Figura 3.
arroz. 3
Esta imagen muestra la manera correcta combinando celdas vecinas, es decir, el mapa de Veitch está, por así decirlo, plegado en un cilindro ubicado verticalmente.
Una expresión simplificada para una función lógica es
Así, al agrupar celdas vecinas en un solo cuadrado, fue posible eliminar dos variables ( incógnita 1 Y incógnita 2 ) y obtener una expresión simple para la función lógica.
Consideremos un ejemplo de cómo minimizar una función lógica.
El mapa de Karnaugh para esta función se muestra en la Figura 4:
arroz. 4
Las celdas que se van a agrupar están rodeadas por dos contornos. El contorno inferior permite eliminar una variableincógnita 3 y después de eso un miembro permanece en él.
En el bucle superior se pueden eliminar dos variables (incógnita 2 Y incógnita 4 ) y después de eso el miembro permanece en él. Una expresión booleana simplificada para una función lógica es
Consideremos la minimización de una función lógica, cuyo mapa de Veitch se muestra en la Fig. 5.
arroz. 5
La expresión booleana para esta función es
Las cuatro celdas de las esquinas se pueden combinar en un grupo. Esta unión elimina dos variables (incógnita 1 Y incógnita 2 ) y conseguir un miembro.
Los dos unos de la primera fila se pueden combinar con los dos unos de la fila inferior para crear un grupo de cuatro celdas que permita eliminar las dos variables (incógnita 1 Y incógnita 3 ) y conseguir un miembro.
Finalmente, el único 1 restante (de la segunda fila y la última columna) se puede combinar con la celda de arriba, eliminando una variable (incógnita 4 ) y conseguir un miembro.
Por tanto, obtenemos la función lógica minimizada.
El método de mapas de Karnaugh (diagramas de Veitch), esencialmente, simplifica la búsqueda de conjunciones pegadas en el SDNF de la función lógica original.
Minimización de funciones de álgebra lógica utilizando los métodos descritos.
Este capítulo presenta las funciones que seleccionamos y ejemplos de su minimización utilizando los métodos discutidos anteriormente.
Simplifique el uso de mapas de Carnaugh para una función de 2 variables:
El mapa de Karnaugh (diagrama de Vaitch) para esta función se verá así:
En la primera línea puedes excluir la variable. incógnita 2 y obtener una expresión simplificada incógnita 1 .
En la segunda columna puedes excluir la variable.incógnita 1
Por tanto, una expresión simplificada de la función lógica se verá así
En la primera columna puedes excluir la variable. incógnita 1 y obtener una expresión simplificada incógnita 2 .
En la segunda línea, puedes eliminar la variable y obtener una expresión simplificada.
Conectamos las expresiones simplificadas resultantes mediante la operación O.
Por tanto, una expresión simplificada de la función lógica se verá así
Simplifique el uso de mapas de Carnaugh para una función de 3 variables:
El diagrama de Veitch para esta función se verá así:
incógnita 3 y obtener una expresión simplificada.
incógnita 3 y obtener una expresión simplificada.
En la última columna puedes excluir la variable.incógnita 1 y obtener una expresión simplificada.
Conectamos las expresiones simplificadas resultantes mediante la operación O.
Por tanto, una expresión simplificada de la función lógica se verá así
El diagrama de Veitch para esta función se verá así:
En la primera línea puedes excluir la variable.incógnita 3 y obtener una expresión simplificada y una variableincógnita 2 y obtener una expresión simplificada.
Conectamos las expresiones simplificadas resultantes mediante la operación O.
Por tanto, una expresión simplificada de la función lógica se verá así
También encontramos una segunda forma de minimizar esta función.
Entonces el diagrama de Veitch para esta función se verá así:
En la primera línea puedes excluir la variable.incógnita 3 y obtener una expresión simplificada.
La primera línea contiene la expresión. .
Conectamos las expresiones resultantes mediante la operación O.
Por tanto, una expresión simplificada de la función lógica se verá así
Evidentemente la función resultante no es mínima, por lo que utilizaremos el método de transformaciones directas de funciones lógicas. Saquemos la variable de paréntesis.incógnita 1 y para la expresión entre paréntesis aplicamos la regla de convolución. Recibió el mismo resultado que en el primer caso.
Esto significa que las celdas vecinas se pueden agrupar de diferentes maneras, lo principal es no olvidar la regla básica: excluir norte variables, el número total de celdas agrupadas debe ser igual a 2 norte .
El diagrama de Veitch para esta función se verá así:
la primera línea puede excluir la variable incógnita 3 y obtener una expresión simplificada.0 1 0 0
Sobre la segunda columna puedes excluir la variable. incógnita 1 .
Conectamos las expresiones simplificadas resultantes mediante la operación O.
Por tanto, una expresión simplificada de la función lógica se verá así
El diagrama de Veitch para esta función se verá así:
En la primera línea puedes excluir la variable.incógnita 3 y obtener una expresión simplificada.
En la segunda línea puedes excluir la variable.incógnita 3 y obtener una expresión simplificada.
Conectamos las expresiones simplificadas resultantes mediante la operación O.
Por tanto, una expresión simplificada de la función lógica se verá así
El diagrama de Veitch para esta función se verá así:
Puede excluir variables en la primera y última columna.incógnita 1 Y incógnita 2 y obtener una expresión simplificada.
En la segunda línea puedes excluir la variable.incógnita 2 y obtener una expresión simplificada. ACERCA DE .
Conectamos las expresiones simplificadas resultantes mediante la operación O.
Por tanto, una expresión simplificada de la función lógica se verá así
Este capítulo presentó funciones de dos, tres y cuatro variables que se minimizaron utilizando diagramas de Veitch. He demostrado y descrito claramente las características del uso de este método de minimización en varias funciones, incluso en combinación con el método de transformación directa de funciones de álgebra lógica.
Conclusión
El trabajo presentado está dedicado a métodos para minimizar funciones de álgebra lógica. Durante el trabajo estuvieron:
se han estudiado los elementos básicos de la lógica matemática;
se han estudiado métodos para minimizar funciones lógicas;
tareas seleccionadas para el trabajo independiente;
Los problemas seleccionados se resolvieron utilizando los métodos descritos.
Examiné en detalle 2 métodos para minimizar funciones lógicas:
método de transformaciones directas de funciones lógicas, realizado utilizando teoremas de álgebra lógica;
Método de minimización mediante diagramas de Veitch (mapas de Karnaugh).
El primer método se ha generalizado incluso en los libros de texto escolares de informática (por ejemplo, libros de texto para los grados 10-11 de N. Ugrinovich, L. Shchautsukova), ya que es uno de los métodos simples para simplificar funciones de álgebra lógica. Las tareas presentadas en los libros de texto de estos autores son bastante diversas:
simplificar una fórmula lógica utilizando las leyes del álgebra lógica;
construir un circuito lógico basado en una función determinada;
simplificar el circuito de conmutación;
demostrar una expresión lógica utilizando una tabla de verdad;
Construya una tabla de verdad para esta función.
El segundo método permite eliminar rápida y fácilmente diferentes variables y obtener una expresión simplificada que no siempre puede ser mínima. Es por eso este método debe considerarse junto con el método de transformaciones directas de funciones lógicas.
este tema tiene significado práctico en microelectrónica. Además, el Examen Estatal Unificado de Informática y TIC contiene una serie de tareas relacionadas con el álgebra lógica, que dividimos en 4 grupos.
El primer grupo son tareas que requieren que usted indique una expresión lógica equivalente a la dada.
El segundo grupo son tareas para encontrar fragmentos de tablas de verdad correspondientes a una expresión determinada.
El tercer grupo incluye tareas para encontrar la verdad de declaraciones para cualquier valor de variable. incógnita Y en .
Y el cuarto grupo son las tareas para determinar la fórmula estructural correspondiente a un diagrama lógico determinado.
No me encontré con ninguna tarea específicamente relacionada con la minimización de funciones lógicas, pero las tareas disponibles en las pruebas requieren un conocimiento bastante profundo en el campo del álgebra lógica.
Debido a la creciente complejidad de las pruebas de acceso a la educación superior instituciones educativas Se puede suponer que pronto aparecerán tareas de simplificación y minimización de funciones lógicas en las pruebas y, por tanto, en los programas educativos.
Referencias
Gavryukova G. A. Lógica en informática [ recurso electrónico]. – Modo de acceso: Oct. 2010).
Ivin A. A. Lógica: Tutorial. – 2ª ed. – M.: Conocimiento, 1998. – 233 p.
Igoshin V.I. Lógica matemática y teoría de algoritmos: libro de texto para estudiantes. más alto libro de texto establecimientos. – 2ª ed., borrada. – M.: Academia, 2008. – 448 p.
Informática y TIC. Preparación para el Examen del Estado Unificado 2009. Pruebas de ingreso. / Ed. F. F. Lysenko. – Rostov s/f: Legión-M, 2009. – 208 p.
Ciencias de la Computación: Libro de texto / B.V. Sobol [etc.]. – 3ª ed., añadir. y procesado – Rostov s/f: Phoenix, 2007. – 446 p.
Informática: libro de texto / A. V. Mogilev, N. I. Pak, E. K. Henner. – 3ª edición. – M.: Academia, 2004. – 848 p.
Kalabekov B.A. Dispositivos digitales y sistemas de microprocesadores: Libro de texto para escuelas técnicas de comunicación. – M.: Línea directa– Telecomunicaciones, 2000. – 336 p.
Kaimin V. A. Ciencias de la Computación: Libro de texto. – 2ª ed., revisada. y adicional – M.: INFRA-M, 2001. – 272 p.
Kovalenko A. A, Petropavlovsky M. D. Fundamentos de microelectrónica: libro de texto. – M.: Academia, 2006. – 240 p.
Lvovsky M. B. manual metódico en informática para estudiantes de 9.º a 11.º grado que estudian IBM PC [recurso electrónico]. – Modo de acceso: septiembre. 2010).
Fundamentos matemáticos de la informática. Curso optativo: Libro de texto / E. V. Andreeva, L. L. Bosova, I. N. Falina. – M.: BINOM. Laboratorio de Conocimiento, 2005. – 328 p.
Minimización de funciones lógicas [Recurso electrónico]. – Modo de acceso: Ago. 2010).
Fundamentos de microelectrónica: libro de texto para universidades / N. A. Avaev, Yu. E. Naumov, V. T. Frolkin. – M.: Radio y Comunicaciones, 1991. – 288 p.: ill.
Taller sobre informática y tecnologías de la información / N. D. Ugrinovich, L. L. Bosova, N. I. Mikhailova. – 2ª ed., rev. – M.: BINOM. Laboratorio del Conocimiento, 2004. – 394 p.
Matemáticas aplicadas: Manual / I. N. Revchuk, V. K. Pchelnik. – Grodno: Universidad Estatal de Grodno que lleva su nombre. Ya Kupala, 2007. – 128 p.
Rabkin E. L., Farforovskaya Yu. matemáticas discretas: funciones booleanas y elementos de la teoría de grafos: Pautas Y tareas de control[Recurso electrónico]. – Modalidad de acceso: 7 agosto 2010).
Savelyev A. Ya. Fundamentos de la informática: libro de texto para universidades. – M.: MSTU im. N. E. Bauman, 2001. – 328 p., enfermo.
Stepanenko I.P. Fundamentos de microelectrónica: libro de texto para universidades. – 2ª ed., revisada. y adicional – M.: Laboratorio Conocimientos básicos, 2001. – 488 p.
Teoría y metodología de la enseñanza de la informática: Libro de texto / [M. P. Lapchik, I. G. Semakin, E. K. Henner, M. I. Ragulina y otros]; editado por M. P. Lapchik. – M.: Academia, 2008. – 592 p.
Ugrinovich N.V. Informática y TIC. Décimo grado. Nivel de perfil. – 3ª ed., rev. – M.: Binomio. Laboratorio de Conocimiento, 2008. – 387 p.
Ugrinovich N.V. Informática y tecnologías de la información: Libro de texto para los grados 10-11. – M.: BINOMIO. Laboratorio del Conocimiento, 2003. – 512 p.
Shautsukova L.Z. Informática 10 – 11. – M.: Educación, 2004. – 420 p.
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).
Álgebras de lógica
3.3.1. Minimizando FAL usando la matriz de Carnot
La matriz de Carnot es una especie de tabla de verdad FAL, que se divide en celdas. El número de celdas de la matriz es 2. norte, Dónde norte– número de argumentos FAL. Las columnas y filas de una matriz se designan mediante conjuntos de argumentos. Cada celda de la matriz corresponde a un constituyente de la unidad FAL (número binario). El número binario de una celda consta de un conjunto de argumentos de fila y columna. La matriz de Carnot para FAL, que depende de dos argumentos, se presenta en forma de tabla 3.3., a partir de tres argumentos en la tabla 3.4. y de cuatro argumentos cuadro 3.5.
Tabla 3.3.
Tabla 3.5.
| incógnita 3 incógnita 4 incógnita 1 incógnita 2 | ||||
| 0 0 0 0 | 0 0 0 1 | 0 0 1 1 | 0 0 1 0 | |
| 0 1 0 0 | 0 1 0 1 | 0 1 1 1 | 0 1 1 0 | |
| 1 1 0 0 | 1 1 0 1 | 1 1 1 1 | 1 1 1 0 | |
| 1 0 0 0 | 1 0 0 1 | 1 0 1 1 | 1 0 1 0 |
Las celdas de las matrices (Tablas 3.3., 3.4. y 3.5.) están numeradas con equivalentes decimales de los números binarios de las celdas. Las celdas de la matriz adyacentes, tanto horizontal como verticalmente, contienen números binarios adyacentes. Además, los números binarios adyacentes se encuentran en todas las columnas de las filas superior e inferior, así como en todas las filas de las columnas más externas.
El proceso de minimizar FAL utilizando la matriz de Carnot se basa en la ley de pegar números binarios adyacentes. Puede pegar números binarios de celdas adyacentes, pero se recomienda pegar conjuntos de argumentos que indiquen las filas y columnas de las matrices. Consideremos pegar los números binarios de las celdas de la primera columna de la matriz (Tabla 3.5.).
Celdas 0 y 4, números binarios 0000 y 0100, respectivamente, el resultado del pegado es 0-00.
Celdas 8 y 12, números binarios 1000 y 1100, resultado 1-00. Los implicantes resultantes están pegados entre sí, porque El guión está en el mismo lugar y los números binarios implicantes son adyacentes, el resultado final es - 00.
Celdas 8 y 12
Por lo tanto, si todos los números binarios de una columna se pegan, los bits que indican las filas desaparecen. De manera similar, si todos los números binarios de una fila están pegados, por ejemplo 4, 5, 7, 6, entonces todos los dígitos que indican las columnas desaparecen, es decir. el resultado será el siguiente 01- -.
Si los números binarios de solo dos celdas cualesquiera están pegados, entonces se coloca un guión en lugar de ese dígito de los números binarios de una fila o columna que cambiará cuando las celdas se muevan de una línea a otra (o de una columna a otra). . Por ejemplo, si pegamos los números de las celdas 5 y 13, obtenemos el resultado -101, o las celdas 7 y 6, el resultado es 011-.
Al pegar números binarios de ocho celdas adyacentes, desaparecen tres variables, por ejemplo, para las celdas 3, 7, 15, 11, 2, 6, 14, 10, las variables desaparecen incógnita 1 , incógnita 2 , incógnita 3. variables incógnita 1 , incógnita 2 desaparecen porque todas las celdas de las columnas están pegadas entre sí, y incógnita 3 porque las dos últimas columnas están pegadas.
Antes de considerar ejemplos de minimización de FAL utilizando la matriz de Carnot, es necesario clasificar los conjuntos de argumentos con cuya ayuda se determinan las funciones del álgebra lógica.
Se sabe que para cada FAL existen 2 conjuntos de argumentos norte, Dónde norte– el número de argumentos de los que depende una función o expresión lógica.
Los conjuntos de argumentos se dividen en tres tipos.
1. Los conjuntos de argumentos en los que la función es igual a uno se denominan de trabajo.
2. Los conjuntos de argumentos en los que la función es igual a cero se denominan prohibidos.
3. Los conjuntos de argumentos para los cuales una función puede ser igual a uno o a cero se denominan indiferentes.
Si un FAL dado no tiene conjuntos indiferentes, entonces se puede representar en expresión literal en forma de SDNF. Si existen conjuntos indiferentes en un FAL determinado, su representación puede tener la siguiente forma.
¿Dónde están los equivalentes decimales? conjuntos de trabajo,
– equivalentes decimales de lances prohibidos.
Los conjuntos de argumentos que no se encuentren entre los válidos y los prohibidos serán indiferentes.
Ejemplo 3.3. Minimice el FAL dado en forma de SDNF usando la matriz de Carnot.
Por lo tanto, la función se especifica únicamente mediante conjuntos de trabajo. El resto estará prohibido. La función depende sólo de tres argumentos. Construimos una matriz de Carnot y colocamos unos en sus celdas que corresponden a los conjuntos de trabajo, y ceros en las celdas restantes.
Tabla 3.5.
| incógnita 2 incógnita 3 incógnita 1 | ||||
| 0 | ||||
Para minimizar, las celdas de la matriz que contienen unos se combinan en contornos. El circuito puede incluir dos celdas, cuatro o las ocho. EN en este ejemplo el contorno incluye cuatro celdas adyacentes de la misma fila. El implicante del contorno dado será 1 - -. El resultado de la minimización es el siguiente, es decir hubo una reducción de la función dada en SDNF en 11 letras.
Ejemplo 3.4. Minimizar la expresión booleana dada por los conjuntos de trabajo y prohibidos utilizando la matriz de Carnot.
Construimos una matriz de Carnot para cuatro variables y llenamos las celdas con unos y ceros, respectivamente, para los conjuntos de trabajo y prohibidos.
Tabla 3.6.
| incógnita 3 incógnita 4 incógnita 1 incógnita 2 |
 00
| |||
| (1) | ||||
| (1) | (1) | |||
Al combinar celdas con unidades en contornos, es deseable que cada contorno incluya el mayor número posible de celdas. Para hacer esto, utilizamos las celdas de algunos conjuntos indiferentes como celdas de conjuntos de trabajo, sustituyéndolas por las que están entre paréntesis. Como resultado, obtenemos tres contornos que contienen 4 celdas cada uno. En el código de circuito generalizado, que incluye todas las celdas de una línea, las variables desaparecen. incógnita 2 incógnita 3 (10 - -). En el código de circuito generalizado, que incluye todas las celdas de una columna, las variables desaparecen. incógnita 1 incógnita 2 (- - 11) y para un contorno que contiene dos celdas de dos líneas, las variables desaparecen incógnita 2 (al pasar de una línea a otra en un contorno) y incógnita 3 (al pasar de una columna a otra). Como resultado, obtenemos el DNF mínimo de la siguiente forma
Posibles opciones La combinación de celdas de la matriz de Carnot en contornos se muestra en la Figura 3.4.
 incógnita 3 incógnita 4
incógnita 1 incógnita 2
| ||||||||||||||||
| Un = 0 - 0 - | Z = - 0 - 0 | |||||||||||||||
| norte | B = 1 - 1 - | k = - - - 1 | ||||||||||||||
| B = - - 0 0 | L = - 1 - - | |||||||||||||||
| Г = 1 0 - - | METRO = - - - 0 | |||||||||||||||
| D = - 0 0 1 | H = - 0 - - | |||||||||||||||
| mi = - 0 1 - | ||||||||||||||||
| F = - 1 - 1 |
Arroz. 3.1. Posibles opciones para combinar celdas de la matriz de Carnot en contornos
3.3.2. Minimizar funciones de álgebra lógica usando una matriz de cinco variables
La matriz de minimización para cinco variables se construye de manera similar a la matriz de Carnot, es decir En esta matriz, las columnas y filas adyacentes deben designarse mediante números binarios adyacentes de conjuntos de variables.
En una matriz de cinco variables (Tabla 3.7.), las filas corresponden a conjuntos de variables incógnita 1 incógnita 2 incógnita 3, y las columnas son conjuntos de variables. incógnita 4 incógnita 5. Cada celda de la matriz corresponde a un número de cinco dígitos. número binario. Las celdas de la matriz (Tabla 3.7.) contienen los equivalentes decimales de los números binarios correspondientes.
Tabla 3.7.
| incógnita 4 incógnita 5 incógnita 1 incógnita 2 incógnita 3 | ||||
Minimizar FAL utilizando una matriz de cinco variables consiste en combinar celdas con conjuntos de trabajo (incluidas, si es necesario, celdas con conjuntos indiferentes) en contornos y obtener códigos generalizados correspondientes a estos contornos.
La peculiaridad aquí es que en las columnas de una matriz de cinco variables, se pueden combinar cuatro celdas en contornos solamente, o cuatro celdas en la parte superior, o cuatro celdas en la parte inferior, o cuatro celdas en el medio. Por ejemplo, para la última columna de la matriz, los contornos pueden consistir en las celdas 2, 6, 14, 10 o 26, 30, 22, 18 o 14, 10, 26, 30.
Ejemplo 3.6. Utilice una matriz de cinco variables para minimizar la siguiente expresión lógica
Construimos una matriz de cinco variables y llenamos las celdas de los conjuntos de trabajo con unos y las celdas de los conjuntos prohibidos con ceros.
Combinamos celdas con conjuntos de trabajo en contornos, incluidas las celdas necesarias de conjuntos indiferentes. Para cada circuito definimos un código generalizado.
Tabla 3.8.
incógnita 4 incógnita 5
 incógnita 1 incógnita 2 incógnita 3
| ||||
| (1) | (1) | (1) | ||
| (1) | ||||
| (1) | (1) | |||
| (1) | (1) | |||
| (1) | (1) | |||
| (1) | ||||
| (1) | (1) | |||
Obtenemos el DNF mínimo
1. Defina el DNF abreviado.
2. ¿Qué es un DNF sin salida?
3. ¿Cómo se selecciona el DNF mínimo entre los DNF sin salida?
4. ¿Para qué se utiliza la tabla de implicantes y cómo se construye?
5. Explique el método analítico para minimizar el FAL de Quine-McClassky.
6. ¿Cómo se construye la matriz de Carnot para tres y cuatro variables?
7. Minimizar analíticamente las siguientes expresiones lógicas dadas únicamente por conjuntos de trabajo
8. Utilizando la matriz de Carnaugh, minimice las expresiones lógicas especificadas por los conjuntos de trabajo y prohibidos.
Información relacionada.
Hay dispositivos lógicos combinacionales y secuenciales.
Dispositivos lógicos combinacionales- Se trata de dispositivos en los que los valores de las señales de salida dependen únicamente de la combinación de señales de entrada en un momento dado.
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 utilizando una base de elementos específica, por ejemplo, en la 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 y requerir el uso de una gran cantidad de 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 para minimizar 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 dibujar equivalente de relé Antes y después de la simplificación. Aquí/ está la señal de salida (estado del contacto de cierre) del elemento de relé 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 tanque 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 de 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 puede usarse como el ya familiar disparador RS T. Para activar el disparador, usamos 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 quitar 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 el interruptor Q1 debe dispararse desde la protección de respaldo con retardo de tiempo.
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 una sección de la 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 símbolos de lógica matemática, la condición de funcionamiento 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.
