Минимизация логических функций

Лекция 3

Аналитические методы

Логическую функцию, заданную таблично в виде таблицы истинности, можно записать либо в виде СДНФ, либо СКНФ. Например.

у	х3	х2	х1

Для записи СДНФ выбираем все строки, где у=1 и записываем в виде суммы конъюнкций элементов х, равных 1, или их отрицаний, если соответствующий х равен 0. . (1.3)

Для записи СКНФ выбирают строки с нулевыми значениями у

и записывают дизъюнкции элементов, имеющих нулевые значения, и отрицания элементов с единичными значениями:

. (2.3)

В выражении (1.3) у будет иметь единичное значение если хотя бы одна элементарная конъюнкция будет равна 1, в противном случае имеем у=0. В выражении (2.3) у=0 если хотя бы одна элементарная дизъюнкция будет равна 0.

При минимизации СДНФ проводят последовательно операции склеивания конъюнкций, отличающихся состоянием только одного элемента, и поглощения. При необходимости любую конъюнкцию или дизъюнкцию можно раздвоить, т.к. , .

Для (1.3) .

Склеивая два последних элемента, получим

.

По формуле обобщенного склеивания последняя функция преобразуется к виду .

Аналогично для (2.3) .

В соответствии с дистрибутивным законом , последнее выражение можно записать как.

Проблема заключается в том, что склеивать можно различные соседние конъюнкции и результат может получиться различный. Для упорядочения последовательностей операций при минимизации применяют методы Двайна, Мак-Класки и др.

При ручной минимизации для небольшого количества входных переменных наиболее эффективно применения диаграмм Вейча или матриц Карно, что почти одно и то же.

Исходной для минимизации является логическая функция в виде СДНФ. Если функция содержит n переменных, то СДНФ может содержать не более чем конъюнкций. Матрица Карно содержит клеток, каждая из которых предназначена для записи результата соответствующей конъюнкции. Адресация клеток выполняется таким образом, что конъюнкции соседних по вертикали или горизонтали клеток отличаются состоянием только одного элемента. Для двух переменных матрица Карно имеет вид. Если в соответствии с логической функцией имеются единицы в соседних по вертикали или горизонтали клетках, то эти клетки объединяются (склеиваются) и переменная, имеющая различные значения для этих клеток, исчезает.

Пусть . Матрица Карно для этой функции содержит единицы в первой колонке, соответствующей х2=1. В результате склеивания соседних клеток первой колонки получаем у=х2.

При получении минимальной нормальной дизъюнктивной формы (МДНФ) для числа переменных больше 2-х необходимо составить матрицу Карно и накрыть все единичные клетки минимальным количеством как можно больших прямоугольников с количеством клеток, равным, но без нулевых клеток. Перекрытие прямоугольников допустимо. Количество конъюнкций в МДНФ будет равно числу прямоугольников, количество элементов в i-ой конъюнкции равно .

Для трех переменных матрица Карно имеет вид:

При такой адресации соседними являются клетки находящиеся на границах матрицы, в частности, на правой и левой границах, т. к. они отличаются только состоянием х3. Фактически матрица сворачивается в цилиндр с вертикальной осью.

Для рассмотренного ранее примера с логической функцией (1.3) матрица Карно представлена ниже. Все единицы объединяются двумя прямоугольниками с m=1 и m=2. Соответственно, логическая функция может быть записана как

.

Для четырех переменных адресация осуществляется таким образом, что матрица Карно при сворачивании в тор обеспечивает соседство клеток по обоим осям. На рисунке в клетках указаны десятичные адреса, полученные из соответствующей двоичной кодировки трок и столбцов матрицы входными элементами.

Для пяти входов и более склеивание элементов существенно усложняется. Матрица для пяти входов составляется из двух четырехвходовых матриц. Номера соответствующих клеток двух матриц отличаются на 16. Поэтому клетки с номерами 0 и 16, 1 и 17, 2 и 18,..., 15 и 31 также являются соседними и могут быть склеены, если в них записаны единицы. Но клетки 8 и 16, 9 и 17, 10 и 18, 11 и 19 не являются соседними, т. к. они отличаются состоянием двух разных разрядов.

Дата добавления: 2014-01-07