2.3. Методы построения сокращенных днф

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

Метод позволяет получить сокращенную ДНФ функции f( ,…, ) из ее совершенной ДНФ и основан на использовании операции поглощения

=

и операции простого склеивания

= .

ДНФ, сопоставляемая покрытию множества всеми максимальными интервалами, является сокращенной ДНФ функции f. Очевидно, что сокращенная ДНФ единственна для f.

Теорема 2.4 (теорема Квайна). Сокращенная ДНФ булевой функции f( ,…, ) получается из ее совершенной ДНФ путем выполнения всевозможных операций склеивания и поглощения конъюнкций.

Доказательство. Очевидно, поглощаемые конъюнкции не могут присутствовать в сокращенной ДНФ, поскольку не являются простыми импликантами булевой функции f( ,…, ). Покажем, что простые импликанты сокращенной ДНФ могут быть получены из совершенной ДНФ путем многократного выполнения операции простого склеивания.

Выберем некоторую простую импликанту K функции f( ,…, ), представим ее в виде совершенной ДНФ, применяя в обратном порядке операцию простого склеивания. Например, K = , n = 4. Применив операцию простого склеивания по переменной , получим

 .

Далее с целью получения совершенной ДНФ применим в обратном порядке операцию простого склеивания к каждой из полученных конъюнкций:

   .

Имея совершенную ДНФ конъюнкции K и выполнив простые склеивания обычным образом, получим простую импликанту K. Склеиваем первую и вторую конъюнкции совершенной ДНФ, а затем – третью и четвертую:

 .

Выполнив простое склеивание над оставшимися конъюнкциями по переменной , получим простую импликанту K. Принимая во внимание, что все конъюнкции совершенной ДНФ, построенной для простой импликанты K, содержатся среди конъюнкций совершенной ДНФ функции f( ,…, ), приходим к заключению: простая импликанта сокращенной ДНФ получается из совершенной ДНФ путем выполнения, в общем случае многократного, операции склеивания. Ч.Т.Д.

Теорема указывает способ получения сокращенной ДНФ функции f( ,…, ) из ее совершенной ДНФ.

Для изложения, основанного на ней алгоритма, известного как алгоритм Квайна–МакКласки, воспользуемся представлением конъюнкций троичными векторами.

2.3.1.1. Представление конъюнкций троичными векторами

Каждой конъюнкции K булевой функции n переменных можно сопоставить n-компонентный троичный вектор следующим образом.

Если в конъюнкции i-я переменная присутствует со знаком инверсии, то i-й компоненте вектора приписывается значение 0, если без инверсии – значение 1. Если i-я переменная в конъюнкции отсутствует, то i-й компоненте сопоставляется значение “–“.

Например, конъюнкции функции 5 переменных сопоставляется вектор 1–01–.

Компоненты со значениями 0, 1 будем называть определенными компонентами троичного вектора, а компоненты со значением “–“ неопределенными.

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

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

Например, α = – –1–0, β = 0–110, .

Для троичных векторов α, β выполняется операция простого склеивания, и результат ее представляется вектором γ, если α, β отличаются друг от друга одной, определенной, например, i-й компонентой. Вектор γ имеет в этой компоненте значение “–“, его остальные компоненты принимают те же значения, что и компоненты векторов α, β.

Пусть α = 01–1–, β = 00–1–, тогда γ = 0– –1–.

Будем считать весом троичного вектора число его единичных компонент. Векторы, веса которых отличаются на единицу, будем называть соседними по весу.

Очевидно, двоичный вектор – это частный случай троичного вектора. Для двоичного вектора множество компонент со значением “–“ пусто.

Перейдем непосредственно к описанию алгоритма Квайна–МакКласки.