Упрощение логических функций
Упрощение логических функций с помощью основных законов алгебры логики
Если сравнить в смысле минимальности различные формы представлений ФАЛ, станет ясно, что нормальные формы экономичнее совершенных нормальных форм. Но, с другой стороны, нормальные формы не дают однозначного представления.
Минимальная форма представления ФАЛ – форма представления ФАЛ, которая содержит минимальное количество термов и переменных в термах (т. е. минимальная форма не допускает никаких упрощений).
Например, функция f(x1, х2,..., хn) = 1+2является минимальной формой и, наоборот, функция 1+12может быть упрощена, если к этому выражению применить распределительный закон, т.е. 1+12=(1+1)( 1+2)= 1+2.
Следовательно, упрощение сложных логических выражений может быть осуществлено по основным законам и аксиомам, изложенным выше.
Пример. Упростить функцию f(A,В,С) = АВ + ВС + ВС + АВ в базисе 1.
Решение. Сначала примем правило а затем упростим функцию.
.
Ответ: .
Пример. Упростить функцию f(A, В, С, D) = АВ + С + A CD + BCD в базисе 1.
Решение. Нетрудно доказать, что . Используя также теорему де Моргана, получим .
Тогда .
Следовательно:
.
Ответ. .
Метод минимизирующих карт
Для функций, содержащих не более четырех переменных, удобно проводить минимизацию, пользуясь диаграммами Вейча (картами Карно). При использовании диаграммы Вейча функцию предварительно следует привести к нормальной дизъюнктивной форме (ДНФ).
После того как исходная функция представлена в ДНФ и произведены очевидные упрощения, следует заполнить прямоугольную таблицу, в которой число клеток равно числу возможных минтермов. Каждой клетке таблицы ставится в соответствие определенная конъюнкция, причем делается это таким образом, чтобы в соседних клетках (снизу и сверху, слева и справа) конъюнкции отличались не более чем одним сомножителем. При заполнении таблицы в соответствующую клетку ставится 1, если минимизируемая функция при данном наборе аргументов равна единице, т. е. в том случае, когда равенство единице конъюнкции, соответствующей данной клетке, означает равенство единице минимизируемой исходной функции. В остальные клетки таблицы вписываются нули.
В заполненной таблице обводят прямоугольными контурами все единицы и затем записывают минимизированную функцию в виде суммы логических произведений, описывающих эти контуры.
При проведении контуров придерживаются следующих правил:
– контур должен быть прямоугольным;
– внутри контура должны быть только клетки, заполненные единицами;
– число клеток, находящихся внутри контура, должно быть целой степенью числа 2, т. е. может быть равно 1, 2, 4, 8, 16;
– одни и те же клетки, заполненные единицами, могут входить в несколько контуров;
– при проведении контуров самая нижняя и самая верхняя строки таблицы считаются соседними, то же – для крайнего левого и крайнего правого столбцов;
– число контуров должно быть как можно меньшим, а сами контуры как можно большими.
Рассмотрим минимизацию с помощью диаграмм Вейча на примере.
Пример. Минимизировать функцию
.
Решение. Приводим функцию к ДНФ, пользуясь правилами де Моргана:
.
Диаграмма Вейча для функции двух переменных показана на рисунке 1, a. В клетки таблицы вписаны соответствующие им конъюнкции. Заполняем таблицу для данной функции (рис. 1, б). Минимизируемая функция равна единице, если равно единице одно из следующих произведений: b, a, . Поэтому при заполнении диаграммы вписываем единицу в три клетки, соответствующие этим произведениям, а в четвертую клетку, соответствующую произведению ab, вписываем нуль. Затем проводим два контура, охватывающие единицы так, как это показано на рисунке 1, б.
Рис. 1. Диаграмма Вейча
Для того чтобы найти логическое выражение (простую конъюнкцию), которое описывает в диаграмме Вейча контур, охватывающий единицы, можно вначале выяснить, от каких переменных не зависит данный контур. Так, если на рис 1, б вертикальный контур охватывает строки a и , то, следовательно, в его обозначение переменная a не войдет. Точно так же горизонтальный контур не зависит от переменной b. Соответственно горизонтальный контур описывается выражением a (так же, как и вторая строка таблицы), а обозначение вертикального контура совпадает с обозначением второго столбца.
Ответ. Минимизированное выражение исходной функции будет следующим:
F=+.
Метод Квайна – Мак-Класки
Минимизацию логических функций можно проводить с помощью метода Квайна – Мак-Класки, который состоит из четырех шагов:
1. Представим наборы, на которых функция истинна, в виде двоичных эквивалентов.
2. Упорядочим двоичные эквиваленты по ярусам и проведем склейку наборов в соседних ярусах, получая максимальные интервалы до тех пор, пока это возможно, помечаем каждый набор, участвовавший в склейке.
Склеиваются только те наборы или интервалы, различие в которых заключается только в значении одного разряда 001 и 000, 001- и 101- и т.д.
3. Построим таблицу Квайна, столбцы которой соответствуют двоичным наборам истинности функции, а строки – максимальным интервалам. Если i-й набор покрывается j-м интервалом, то ставим 1 на пересечении соответствующих строки и столбца, в противном случае ставим 0 или не ставим ничего.
4. Находим минимальное покрытие таблицы Квайна, состоящее из минимального количества максимальных интервалов, включающих в себя (покрывающих) все наборы, на которых функция истинна.
Рассмотрим функцию f(x1, x2, x3, x4), которая истинна на наборах {1, 3, 5, 7, 11, 13, 15}. СНДФ данной функции такова:
fСНДФ(x1,x2,x3,x4) = 1 234+1234+1 234+ +1234+1 234+1234+1 234+1 234+ +1 234+1 234.
Двоичные эквиваленты истинных наборов следующие:
Упорядочим двоичные наборы по ярусам и проведем склейки до тех пор, пока это возможно:
Затем строим таблицу Квайна:
В нашей таблице наборы 0001, 1101 и 1011 покрываются единственно возможным образом; следовательно, покрывающие их минимальные интервалы называются обязательными и образуют ядро покрытия, так как должны входить в любое покрытие. В таблице соответствующие единицы подчеркнуты, интервалы {0--1, --11, -1-1} образуют не только ядро покрытия, но и покрывают всю таблицу Квайна.
Таким образом, мы получили минимальную форму исследуемой функции в виде
f(x1,x2,x3,x4) ={0--1,--11,-1-1}= 14+ 34+ 24.