Преобразование и минимизация логических выражений
При использовании аналитических форм преобразования логических функций обычно стремятся к их упрощению, выражая сложные логические функции через более простые.
Система логических функций называется функционально полной, или базисом, если любую логическую функцию можно представить в аналитической форме через эти функции, взятые в любом конечном числе экземпляров каждая.
Возможность представления любой логической функции в ДСНФ или КСНФ означает, что логические функции конъюнкции, дизъюнкции и отрицания (И, ИЛИ, НЕ) образуют функционально полную систему, или основной базис.
Базис И, ИЛИ, НЕ является избыточным, так как из него всегда можно исключить, используя формулу де Моргана, либо функцию И, заменяя ее на ИЛИ и НЕ:
х & у = х ? у,
либо функцию ИЛИ, заменяя ее на И и НЕ:
х ? y = х & у.
Базисы функции И, НЕ и ИЛИ, НЕ называются нормальными базисами. При удалении из них хотя бы одной функции функционально полная система становится неполной.
Функциональной полнотой обладают также системы, состоящие из одной логической функции: отрицания конъюнкции х & у (И - НЕ), названной операцией Шеффера, или отрицания дизъюнкции х ? у (ИЛИ - НЕ), названной операцией Пирса. С помощью любой из этих функций, образующих универсальный базис, можно выразить основные логические функции: конъюнкцию, дизъюнкцию и отрицание, а следовательно - и любую другую логическую функцию.
Процесс упрощения аналитического выражения логических функций называют минимизацией. В результате минимизации сокращаются затраты оборудования в процессе технической реализации. Помимо минимизации, числа логических функций, участвующих в исходном выражении, стремятся к их однородности (однотипности).
Существуют различные методы минимизации, из которых мы рассмотрим два метода: метод непосредственных преобразований логического выражения и метод минимизирующих карт Карно.
Метод непосредственных преобразований основан на последовательном исключении переменных исходного выражения с использованием законов алгебры логики.
С этой целью в ДСНФ исходной логической функции выявляются соседние минтермы, т.е. такие, в которых имеется по одной несовпадающей переменной, например, х1 & х2 & х3 и х1 & х2 & х3;
113
х1 & х2 & х3 и х1 & х2 & х3. При вынесении за скобки общих множителей в
таких минтермах происходит исключение одной переменной, и они склеиваются в одну конъюнкцию. Например:
x1 & x2 & x3 ? x1 & x2 & x3 = x1 & x3 & (x2 ? x2) = x1 & x3.
Конъюнкции, образованные в результате склеивания, называются импликантами. Полученные после склеивания импликанты склеиваются повторно и так до тех пор, пока склеивание возможно. Например:
Проиллюстрируем метод непосредственных преобразований еще одним примером. Пусть задана логическая функция трех переменных F(х, у, z)табл. 5.3.
Таблица 5. 3
Логическая функция трех переменных
| x | y | z | F | x | y | z | F |
| 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
F = х & у & z ? х & у & z ? х & у & z ? х & у & z
Здесь первая и вторая, а также третья и четвертая конъюнкции являются соседними. Склеивая эти конъюнкции, получим:
F = x & y & (z ? z) ? x & y (z ? z) = x & y ? x & y.
К полученным импликантам применим повторное склеивание:
F = x & y ? x & y = x & (y ? y) = x.
Таким образом, в результате выполнения преобразований исходная функция трех переменных оказалась инверсией лишь одной переменной х. В этом также можно убедиться, проанализировав табл. 5.3.
Рассмотренный метод минимизации путем непосредственных преобразований достаточно прост, особенно при небольшом числе переменных. Недостатком метода является то, что он не указывает строго формализованный путь минимизации. При большом числе переменных минтермы могут группироваться по - разному, в результате чего можно получить различные упрощенные формы заданной функции. При этом мы не можем быть уверены в том, что какая - то из этих форм является минимальной.
Возможно, что получена одна из тупиковых форм, которая больше не упрощается, не являясь при этом минимальной.
114
Более строгим является метод минимизации, основанный на применении карт Карно. Карты Карно представляют собой таблицы, разделенные на клетки. Число клеток равно числу различных наборов аргументов, каждая клетка соответствует определенному набору этих аргументов.
На рис. 5.5 показаны карты Карно для двух, трех и четырех аргументов, содержащие соответственно 4, 8 и 16 клеток.
Рис. 5.5. Карты Карно для двух (а), трех (б) и четырех (в) аргументов
В клетки карты Карно, соответствующие тем наборам аргументов, для которых минимизируемая функция в соответствии с заданной таблицей принимает единичное значение, заносятся единицы. При этом две конъюнкции, находящиеся в соседних клетках карты, могут быть заменены одной конъюнкцией, содержащей на одну переменную меньше. Если соседними являются две пары конъюнкций, то такая группа из четырех конъюнкций может быть заменена конъюнкцией, которая содержит на две переменные меньше. В общем случае наличие минтермов в 2n соседних клетках позволяет исключить n переменных.
Правила применения карт Карно состоят в следующем.
1. Если единица находится в двух соседних клетках строки, столбца или на противоположных концах любой строки или столбца, то соответствующие
115
этим единицам конъюнкции заменяются одной конъюнкцией на ранг ниже, причем в нее включаются переменные с одинаковыми показателями инверсии.
2. Если четыре клетки составляют большой квадрат, строку или столбец, то соответствующие им конъюнкции заменяются одной на два ранга ниже, в которую включены переменные с одинаковыми показателями инверсии.
3. Конъюнкции, соответствующие оставшимся единицам, сохраняются без изменения.
Рассмотрим применение карт Карно на примерах.
Для функции F(x1, х2, x3), заданной таблицей 5.4, ДСИФ имеет вид:
F(x1, x2, x3) = x1 & x2 & x3 ? x1 & x2 & x3 ? x1 & x2 & x3 ? x1 & х2 & х3.
Таблица 5.4
Значение функции трех аргументов
| x1 | x2 | x3 | F(x1, x2, x3) | x1 | x2 | x3 | F(x1, x2, x3) |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Рис. 5.6. Карты Карно для функции трех аргументов
В правом крайнем столбце этой карты соседним единицам соответствуют конъюнкции х1 & х2 & х3 и х1 & x2 & х3 которые заменяются одной конъюнкцией на ранг меньше с одинаковыми показателями инверсии переменных, т.е. х1 & х2. Две оставшиеся единицы находятся в соседних клетках второй строки, поэтому соответствующие им конъюнкции х1 & х2 & х3 и х1 & х2 & x3. заменяются одной х2 & x3 В результате минимизированная ДСНФ исходной функции примет вид:
F(x1, х2, х3) = х1 & х2 ? х2 & х3,
116
который значительно проще первоначальной ДСНФ, имеющий в соответствии с табл. 5.4 вид:
F(x1, x2, x3) = x1 & x2 & x3 ? x1 & x2 & x3 ? x1 & x2 & x3 ? x1 & x2 & x3.
Рассмотрим теперь пример минимизации функции четырех аргументов, ДСНФ которой задана в виде:
F(x1, x2, x3, x4) = x1 & x2 & x3 & x4 ? x1 & x2 & x3 & x4 ? x1 & x2 & x3 & x4 ? x1 & x2 & x3 & x4 ? x1 & x2 & x3 & x4 ? x1 & x2 & x3 & x4 ? x1 & x2 & x3 & x4.
По карте Карно (рис. 5.7) конъюнкции, образовавшие большой квадрат, понижаются на два ранга, конъюнкции, находящиеся в двух соседних клетках, понижаются на один ранг, а одиночная конъюнкция остается без изменения.
Рис. 5.7. Карты Карно для функции четырех аргументов
В результате получим:
F(x1, x2, x3, x4) = x1 & x2 ? x2 & x3 & x4 ? x1 & x2 & x3 & x4.
В заключение отметим, что метод карт Карно упрощает нахождение склеиваемых конъюнкций в ДСНФ исходной логической функции.
117
113 :: 114 :: 115 :: 116 :: 117 :: Содержание
