Назад (Информатика).

Метод Куайна-Маккласки

Метод минимизации логических функций Куайна-Маккласки основан на том факте, что вынос общего множителя за скобки в формуле эквивалентен объединению двух строк в одну в таблице истинности. В комбинируемых строках должны совпадать все значения переменных, кроме одной - сравниваемые строки отличаются на одну единицу. Значение "не совпавшей" переменной безразлично и может быть обозначено звездочкой "*". Например, указанные ниже две строки

x1x2x3f
1011
1111

можно заменить одной строкой:

x1x2x3f
1*11

т. к. в этой строке значение переменной x2 не влияет на значение функции.

Познакомимся с этим методом на примере минимизации логической функции, заданной таблицей истинности:

x1x2x3f
10000
20010
30101
40111
51000
61010
71101
81111

Запишем еще раз таблицу истинности для функции f с указанием для единичных наборов количества единиц в значениях переменных:

x1x2x3fед.
10000
20010
301011
401112
51000
61010
711012
811113

Разобьем таблицу на группы строк с одинаковым количеством единиц, удалив из таблицы строки с нулевым значением функции:

x1x2x3fед.
301011
401112
711012
811113

Сравним наборы значений переменных каждой предыдущей группы с последующей и объединим строки с общим множителем:

x1x2x3fед.
3,401*11
3,7*1111
4,8*1012
7,811*12

Объединим строки с совпадающими позициями "крестиков":

x1x2x3fед.
3,4,7,8*1*11
3,7,4,8*1*11

Из двух идентичных строк оставляем только одну:

x1x2x3fед.
3,4,7,8*1*11

В результате минимальная формула логической функции f будет иметь вид: f = x2.