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

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

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

x1	x2	x3	f
1	0	1	1
1	1	1	1

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

x1	x2	x3	f
1	*	1	1

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

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

№	x1	x2	x3	f
1	0	0	0	0
2	0	0	1	0
3	0	1	0	1
4	0	1	1	1
5	1	0	0	0
6	1	0	1	0
7	1	1	0	1
8	1	1	1	1

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

№	x1	x2	x3	f	ед.
1	0	0	0	0
2	0	0	1	0
3	0	1	0	1	1
4	0	1	1	1	2
5	1	0	0	0
6	1	0	1	0
7	1	1	0	1	2
8	1	1	1	1	3

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

№	x1	x2	x3	f	ед.
3	0	1	0	1	1
4	0	1	1	1	2
7	1	1	0	1	2
8	1	1	1	1	3

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

№	x1	x2	x3	f	ед.
3,4	0	1	*	1	1
3,7	*	1	1	1	1
4,8	*	1	0	1	2
7,8	1	1	*	1	2

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

№	x1	x2	x3	f	ед.
3,4,7,8	*	1	*	1	1
3,7,4,8	*	1	*	1	1

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

№	x1	x2	x3	f	ед.
3,4,7,8	*	1	*	1	1

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