Лекция №4. Минимизация булевых функций
 Скачать 400.29 Kb.
|
|
1 Лекция №4 по математической логике и теории алгоритмов Тема: Минимизация булевых функций методом Квайна−Мак-Класки. Данный метод применяется для любого числа переменных (практически не более 10), допускает возможность построения компьютерной программы минимизации. Рассмотрим вначале случай, когда функция представлена в виде множества единичных наборов, каждая конъюнкция которой переведена в двоичные вектора. Напомним, что «склеивание» можно проводить только между наборами, которые отличаются между собой только одной переменной, а, значит, число единиц в этих наборах будет отличаться только на единицу. Например, набору t z xy соответствует вектор 1101 , в котором 3 единицы, а соседнему с ним по переменной x набору t z y x соответствует вектор 0101 с числом единиц 2. Метод Квайна−Мак-Класки делится на два этапа. На первом этапе разделим все наборы на группы по числу единиц в них. Определение. Индексом двоичного набора называется число единиц в нем. Так как склеиваться могут только наборы из соседних групп, то последовательно проводим все склеивания, которые только возможно. В результате этой операции на втором уровне получаем вектора, в которых используется символ «−» как символ неопределенного значения. Так после склеивания рассмотренных выше наборов, на втором уровне получим вектор t z y В результате проведенных склеиваний на втором уровне после склеивания наборов, содержащих i и ) 1 ( i единиц, получим группу, все элементы которой содержат i единиц. Затем снова сравниваем вектора из соседних групп, склеиваем отличающиеся только в одной позиции вектора. Это отличие может быть только в том, что в некотором разряде одного вектора стоит 0, в том же разряде второго вектора стоит 1, а все остальные разряды совпадают полностью, с учетом и символов «−». Так, если на втором уровне в группе с тремя единицами получили вектор 1011 , а в группе с числом единиц два получили вектор 1010 , то их склеиваем и получаем на третьем уровне в группе с двумя единицами вектор 101 . Эту операцию продолжаем 2 до тех пор, пока возможно. В результате на r-м уровне получим вектора, число символов «−» в которых равно (r-1). Такую операцию проводим, пока возможно. Пример. Функция от четырех переменных представлена как 0011, 0100, 0101, 0111, 1001, 1101, 1110, 1111. Решение. Разобьем конъюнкции, представленные двоичными наборами, на группы в зависимости от числа единиц в представлении: Первый уровень: Индекс Набор 1 0100 2 0011 0101 1001 3 0111 1101 1110 4 1111 Второй уровень: Набор 1-2 010- 2-3 0-11 01-1 -101 1-01 3-4 -111 11-1 111- Третий уровень: Набор 1-2 010- 2-3 0-11 1-01 3-4 111- 2-3-3-4 -1-1 -1-1 3 На втором этапе строим таблицу покрытия (таблица Квайна для исходной функции). Столбцы таблицы составляют векторы исходной функции. Строки таблицы – это полученные наборы. Для рассматриваемого примера таблица имеет вид: 0011 0100 0101 0111 1001 1101 1110 1111 010- * * 0-11 * * 1-01 * * 111- * * -1-1 * * * * Суть второго этапа заключается в том, чтобы выбрать минимальное число строк, покрывающих все столбцы. Начинается решение задачи с выбора столбцов, содержащих единственную отметку (звездочку). Конъюнкции, которые им соответствуют являются существенными, они остаются в решении. Таким, например, является столбец 0011: в решении необходимо взять конъюнкцию 0-11, иначе конъюнкция 0011 покрыта не будет (не войдет в решение). Но выбор конъюнкции 0-11 покрывает и конъюнкцию 0111, поэтому отмечаем эти два столбца. Таким же образом поступаем с конъюнкцией 0100, 1001 и 1110, которые требуют в решение, соответственно, конъюнкции 010-, 1-01 и 111-. Но первая покрывает еще и 0101, вторая – 1101, третья – 1111. В результате все исходные конъюнкции оказываются покрытыми. Решение найдено, функция будет иметь минимальную ДНФ в виде: xyz t z x z y x zt x f Заметим, что в этом примере самая короткая конъюнкция -1-1, покрывающая наибольшее число исходных конъюнкций, в решение не вошло. Различие методов Карно и Квайна – Мак-Класки: 1. Метод Карно позволяет минимизировать логические функции с относительно малым числом переменных ( 6 n ). В методе Квайна – Мак-Класки отсутствуют ограничения на число переменных логической функции. 2. Метод Карно является визуальным и сложным для алгоритмизации. Метод минимизации Квайна – Мак-Класки является систематичным и его легко алгоритмизировать. 4 Сходство методов Карно и Квайна – Мак-Класки: 1. Векторы соседних клеток карты Карно соответствуют векторам соседних секций таблицы склеивания метода Квайна – Мак-Класки. 2. Объединение в контуры на карте Карно соответствуют склеиванию в методе Квайна – Мак-Класки. Пример. Дана функция xyzt t xyz yzt x t z y x t yz x t z y x t z y x t z y x t z y x f Получить МДНФ методом Квайна – Мак-Класки и методом Карно. Решение. 1. Запишем функцию в двоичном виде и разделим двоичные векторы на секции по числу единиц. Составим таблицу интервалов, используя правило склеивания. Склеивать между собой можно только соседние векторы, которые могут находиться только в соседних секциях таблицы. Первый уровень: Индекс Набор 0 0000 1 0010 1000 2 0101 0110 1001 3 0111 1110 4 1111 Второй уровень: Набор 0-1 00-0 -000 1-2 0-10 100- 2-3 01-1 011- -110 3-4 -111 111- 5 Третий уровень: Набор 0-1 00-0 -000 1-2 0-10 100- 2-3 01-1 2-3-3-4 -11- -11- Дальнейшее склеивание невозможно. Построим таблицу покрытия (таблица Квайна для исходной функции): 0000 0010 0101 0110 0111 1000 1001 1110 1111 00-0 * * -000 * * 0-10 * * 100- * * 01-1 * * -11- * * * * Так как элементарные конъюнкции, которые соответствуют 4-6 строкам таблицы покрывают не все столбцы (1 и 2 столбцы остались без покрытия), то из 1-3 строк необходимо выбрать, те элементарные конъюнкции, которые минимально покрывают эти столбцы. Такой элементарной конъюнкцией является первая 0 00 Запишем МДНФ: yz yt x z y x t y x f 2. Составим карту Карно для исходной функции: t z t z zt t z y x 1 1 y x 1 1 1 xy 1 1 y x 1 1 В результате получаем МДНФ: yz t y x yt x z y x f |