ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №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