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