Минимизация методом Квайна-Мак-Класки

Метод минимизации Квайна-Мак-Класки является одним из систематических методов, основанных на формализованном порядке упрощения формул. Метод описывается строгим алгоритмом, поддается программированию и его применение дает возможность использовать ЭВМ, что неизбежно при минимизации ФАЛ большого числа переменных.

При минимизации функций алгебры логики по этому методу последовательно выполняются два этапа преобразования выражения функции: на первом переходят от канонической формы к сокращенной, на втором - от сокращенной формы логического выражения к минимальной.

Процедуру минимизации в соответствии с этим методом обычно выполняют по десятичным или двоичным эквивалентам конституент заданной функции.

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

f = {0,1,2,3,4,5,6,7,8,9,11,15} _{X 1 X 2 X 3 X 4},

что соответствует аналитическому заданию функции алгебры логики

Наборы разбиваются на группы так, чтобы члены любой группы в своем двоичном представлении имели одинаковое число единиц (табл.4.12). Число единиц в двоичном коде можно назвать его весом, тогда все члены одной группы будут иметь одинаковый вес.

Каждый член группы, начиная с первого набора первой группы, сравниваем последовательно со всеми членами следующей группы, в результате чего будет происходить исключение одной переменной, на месте которой будем ставить прочерк.

Таблица 4.12

Номер группы	X1	X2	X3	X4

Результаты сравнения приведены в табл.4.13. Каждый член, участвующий в сравнении, отмечен.