Метод Квайна

Теорема Квайна. Для получения минимальной формы логической функции необходимо в СДНФ произвести все возможные склеивания и поглощения, так чтобы в результате была получена сокращенная ДНФ. Сокращенная ДНФ в общем случае может содержать лишние простые импликанты, которые необходимо выявить на втором этапе минимизации.

На первом этапе выполняется переход от функции, заданной в форме СДНФ, к сокращенной ДНФ. Это основано на использовании следующих соотношений:

1) соотношение неполного склеивания

, где и - две конъюнкции, а F - любое элементарное произведение;

2) соотношение поглощения

.

Справедливость обоих соотношений легко проверяется. Суть метода заключается в последовательном выполнении всех возможных склеиваний и затем всех поглощений, что приводит к сокращенной ДНФ. Метод применим к совершенной ДНФ. Из соотношения поглощения следует, что произвольное элементарное произведение поглощается любой его частью. Для доказательства достаточно показать, что произвольная простая импликанта р = x_i1x_i2 ... x_in может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания)

по всем недостающим переменным x_ik, ..., x_im исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f, поскольку р - ее импликанта.

В результате выполнения склеивания получается конъюнкция n-1 ранга, а конъюнкции и остаются в исходном выражении и участвуют в сравнении с другими членами СДНФ. Таким образом, удается снизить ранг термов.

Склеивание и поглощение выполняются до тех пор, пока имеются члены, не участвовавшие в попарном сравнении. Термы, подвергшиеся операции склеивания, отмечаются. Неотмеченные термы представляют собой простые импликанты и включаются в сокращенную ДНФ. Все отмеченные конъюнкции ранга n-1 подвергаются вновь операции склеивания до получения термов n-2 ранга и так далее до тех пор, пока количество неотмеченных конъюнкций больше 2. В результате выполнения первого этапа получена сокращенная ДНФ.

Полученное логическое выражение не всегда оказывается минимальным. На втором этапе переходят от сокращенной ДНФ к тупиковым ДНФ и среди них выбирают МДНФ.

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

Из общего числа простых импликант необходимо отобрать их минимальное число, исключив лишние. Формирование тупиковых форм и выбор минимального покрытия начинается с выявления обязательных простых импликант, то есть таких, которые (и только они) покрывают некоторый исходный набор. Рассмотрим пример минимизации методом Квайна логической функции:

f_СДНФ= V (1,2,5,6,7)=x₁x₂x₃+ x₁x₂x₃+ x₁x₂x₃+ x₁x₂x₃+ x₁x₂x_3.

^{1 2 3 4 5}

Выполним операцию склеивания:

1 – 3 (x₁) x₂x₃ 1

2 – 4 (x₁) x₂x₃ 2

3 – 5 (x₂) x₁x₃ 3

4 – 5 (x₃) x₁x₂ 4

В результате выполнения первого шага склеивания получаем четыре новые конъюнкции, простых импликант не выявлено. Полученные конъюнкции более не склеиваются и образуют сокращенную ДНФ.

f_{сокр СДНФ}=x₂x₃+ x₂x₃+ x₁x₃+ x₁x₂ .

Для выявления обязательных простых импликант и формирования на их основе минимального покрытия строится импликантная таблица (табл. 13). В строках импликантной таблицы записываются простые импликанты, а в столбцах − конституенты единицы. Звездочка ставится, если простая импли-канта покрывает конституенту.

Таблица 13

Простые импликанты являются обязательными, так как только они покрывают конституентыи включаются в минимальное покрытие. Остается одна непокрытая конституента x₁x₂x_3, которая может быть покрыта одной из двух оставшихся простых импликант. Это приводит к получению двух тупиковых форм: