ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №2
Минимизация функций алгебры логики методом квайна-мак-класки для четырех переменных
2.1. Теоретические сведения
Данный метод основывается на задании конституент единицы в виде условных двоичных чисел, называемых номерами соответствующих конституент. Кроме номера, каждой конституенте присваивается определенный индекс, под которым понимается число единиц в двоичном представлении номера конституенты. Например, конституенте соответствует номер 101 (5) и индекс II, конституенте – номер 111 (7) и индекс III. В результате реализации этого метода ФАЛ разлагается на простые импликанты. Под импликантой функции понимается такая другая функция, которая принимает единичное значение на всех наборах аргументов, что и исходная ФАЛ. Простой импликантой функции называется всякое элементарное произведение, являющееся ее импликантой, исключение из которого хотя бы одного аргумента уже не позволяет получить импликанту рассматриваемой ФАЛ.
Алгоритм Квайна-Мак-Класки формулируется следующим образом. Для того чтобы два числа m и n являлись номерами двух склеивающихся конституент единицы, необходимо и достаточно, чтобы их индексы отличались на единицу, сами числа отличались на степень двойки и число с большим индексом было больше числа с меньшим индексом.
Реализацию алгоритма рассмотрим на примере минимизации ФАЛ:
. (1)
На первом этапе минимизации определяем номера и индексы каждой конституенты единицы:
, (2)
1(I) 3(II) 5(II) 7(III) 9(II) 11(III) 15(IV). (3)
Группируем номера конституент, располагая их в порядке возрастания индексов (см. табл. 2.1).
Таблица 2.1
Минимизация фал методом Квайна-Мак-Класки
Индексы |
Номера |
Результат склеивания |
Импликанты |
|
І |
0001 (1) |
1,3 00_1 1,5 0_01 1,9 _001 |
1,3,5,7 0__1 1,3,9,11 _0_1 1,5,3,7 0__1 1,9,3,11 _0_1 |
|
ІІ |
0011 (3) 0101 (5) 1001 (9) |
3,7 0_11 3,11 _011 5,7 01_1 9,11 10_1 |
3,7,11,15 __11 3,11,7,15 __11 |
|
ІІІ |
0111 (7) 1011 (11) |
7,15 _111 11,15 1_11 |
|
|
ІV |
1111 (15) |
|
|
|
На следующем этапе производим склеивание различных чисел, руководствуясь приведенной выше формулировкой метода Квайна-Мак-Класки. Подлежащие склеиванию пары чисел в табл. 2.1 указаны стрелками. При склеивании осуществляется псевдологическое умножение чисел на пустое множество, в результате которого, несовпадающие в числах разряды отмечаются прочерком. Например, склеивание чисел 0001 и 0101 дает число 0_01, при склеивании 0001 и 0011 получаем 00_1 и т.д. Результат склеивания вписывается во второй столбец табл. 2.1, также разделяемый на строки, получаемые при объединении конституент соседних групп, с индексами, отличающимися на единицу.
После склеивания всех групп первого столбца таблицы переходят к ее второму столбцу, вписывая результат склеивания в третий столбец. При объединении чисел второго, третьего и последующих столбцов таблицы следует помнить, что склеивание возможно только между числами, содержащими символ “_” в одноименных разрядах. Процесс склеивания продолжается до тех пор, пока образование нового столбца станет невозможным.
По окончании склеивания приступают к построению импликантной таблицы (см. табл. 2.2). В данной таблице строки представляют собой простые импликанты минимизируемой функции, а столбцы – конституенты единицы. В качестве простых импликант выписываются наборы, содержащиеся в последнем столбце табл. 2.1 и наборы других столбцов этой таблицы, не принимавшие участия в склеивании. Если импликанта, содержащаяся в i-ой строке таблицы составляет некоторую часть конституеты j-го столбца, на пересечении i-ой строки и j-го столбца ставится символ “+”. Для получения минимальной формы ФАЛ нужно выписать минимальное число строк табл. 2.2, выбранное таким образом, чтобы для каждого столбца среди выбранных строк нашлась хотя бы одна содержащая в этом столбце символ “+”. При появлении в импликантной таблице хотя бы одного столбца без символа “+”, результат склеивания в табл. 2.1. является не верным и требует перепроверки.
Таблица 2.2