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

Если в СДНФ какой-либо переключательной функции выполнить все возможные операции неполного попарного склеивания и элементарного поглощения, то в результате получится СкДНФ(сокращенная дизъюнктивная нормальная форма), эквивалентная исходной функции.

Используется итерационный алгоритм. Задача в нахождении по полной системе импликант (конституэнт еденицы) полной системы простых импликант.

В общем случае процедура выглядит следующим образом:

- Исходным является множество конституэнт единицы функции - импликанты нулевого ранга;

- Выполняются все возможные операции неполного попарного склеивания для элементарных конъюнкций длины n. (где n-кол-во аргументов);

- Согласно соотношениям "a." и "b." результат - дополнительная импликанта p.

- Выполняются все возможные операции элементарного поглощения для элементарных конъюнкций длины n-1. (общая часть "p" имеет длину n-1);

- В результате получилось множество элементарных конъюнкций, разделяемых на два подмножества(по длине):

§ подмножество элементарных конъюнкций длины n (оставшиеся);

§ подмножество элементарных конъюнкций длины n-1;

- Элементарные конъюнкции длины n не участвовали в склеивании, а, следовательно, и в поглощении (т.к. поглощаются собственной частью тех, которые участвовали в склеивании). Следовательно, подмножество элементарных конъюнкций длины n входит в множество простых импликант (импликант нулевого ранга);

- Если множество элементарных конъюнкций длины n-1 не пусто, то выполняются шаги со второго для конъюнкций длины n-1 и т.д.

Алгоритм завершается, когда подмножество является пустым, либо нельзя выполнить ни одной операции неполного попарного склеивания. Таким образом, получается система простых импликант функции.