Обобщенный метод Куайна

Алгоритм основан на применении следующих законов алгебры логики, справедливых для пороговых функций, а, следовательно, и для нормальных форм рассматриваемого вида. Пусть имеется представление булевой функции f в виде некоторой нормальной формы f =F(j (x₁^a11 ,..., x_n^a1n), ...,j(x₁^ak1 ,..., x_n^akn)). Множества переменных, входящих во внутренние функции, обозначим через Х₁,..., Х_k .

Допустим, у внутренних функций формы есть два набора переменных X_p =(x₁^ap1,...,x_n^apn)и X_q =(x₁^aq1 ,...,x_n^aqn), соседних по переменной с номером r .У них a _p1 = a _q1 , ... ,a _p(r-1) = a _q(r-1), a _{p r} = Øa _{q r} , a _p(r+1) = a _q(r+1), . . . , a _pn =a _qn.

Для данной нормальной формы справедливы следующие обобщенные операции склеивания:

а) полное склеивание:

f = F(j(Х₁),...,j(Х_р),...,j(Х_q),...,j(X_k))=F(j(Х₁),...,j(Х_р\x_r^apr),...,

j(Х_q-1),j(Х_q+1),...,j (X _k)).

б) неполное склеивание (дополнение):

f=F(j(Х₁),...,j(Х_р),...,j(Х_q),...,j(X_k))=F(j(Х₁),...,j(Х_р),...,j(Х_q),...,j(X_k), j(Х_р\x_r^apr)).

В операции а) удаляется функция j(Х_q), а также переменная x_r^apr из j(Х_р). Воперации б) к существующему набору внутренних функций j (Х₁),...,j(Х_k)добавляется новая функция j(Х_р\x_r^apr), в которой отсутствует переменная с номером r.

Если набор с номером p отличается от набора с номером q отсутствием одной переменной x_r^apr (X_p = Х_q\ x_r^apr ), то для любой формы справедлива операция.

в) поглощения (удаления внутренней функции с расширенным набором переменных)

f = F(j(Х₁), ..., j(Х_р), ..., j(Х_q), ... ,j(X _k))= F(j(Х₁), ..., j(Х_р), ... ,j(Х_q-1), j(Х_q+1), ...,j(X_k)).

Если наборы переменных во внутренних функциях X_p и Х_q одинаковы (полностью совпадают), то справедлива операция

г) удаления дубликатов

f = F(j(Х₁), ... ,j(Х_р), ... ,j(Х_q), ... , j(X _k))=F(j(Х₁), ..., j(Х_р), ... ,j(Х_q-1), j(Х_q+1), ... ,j(X_k)).

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

Обобщенный алгоритм Куайна включает следующие операции:

1. Проведение в совершенной нормальной форме всех возможных операций неполного склеивания.

2. В полученной дополненной нормальной форме выполнение всех возможных операций полного склеивания.

3. Выполнение всех возможных операций поглощения и удаления дубликатов.

Полученная формула анализируется и, если возможно, к ней снова применяют операции 1) — 3) и т.д.

В результате получается нормальная форма, состоящая из простых наборов, то есть сокращенная нормальная форма рассмотренной функции.

Пример 2. Рассмотрим функцию из Примера 1 и построим для неё СкДНФ.

Решение. СДНФ функции: f =`x y`z Ú x`y`z Ú x`y z. Элементарные наборы: N<sub>1</sub>=(`x, y,`z), N<sub>2</sub>=(x,`y,`z), N<sub>3</sub>=(x,`y, z).

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

а) N₁и N₂ не соседние, поскольку у них отличие по двум переменным (x и y),

б) N₁и N₃ не соседние, отличие по всем трём переменным,

в) N₂и N₃ — соседние,т.к. отличаются ровно по одной переменной — z .

Применяем к этой паре операцию неполного склеивания (дополнения):

f =`x y`z Ú x`y`z Ú x`y z Ú x`y .

2. Применяем операцию поглощения. Вначале – к х`у`z и х`у: f = `х у`z Ú х`у z Ú х`у , затем – к х`у z и х`у : f = `х у`z Ú х`у.

Поскольку одинаковых наборов во внутренних конъюнкциях нет, то правило удаления дубликатов не используется.

Последняя полученная формула и будет искомой СкДНФ функции f = (00101100). Её простыми наборами являются P₁=(х, у,`z), P<sub>2</sub>= ( х,`у).

III. Формирование матрицы А покрытий множества простых наборов {P} = {P₁, ... ,P_s} элементарными наборами {N} = {N₁, ... , N_k}.

Допустим, на предыдущих шагах построены: множество простых наборов {P} = {P₁, ... , P_s}, входящих в сокращенную форму, и множество элементарных наборов {N} = {N₁ , ... , N_k}, входящих в совершенную форму. Строим матрицу А размером s ´ k покрытий простых наборов {P} элементарными наборами {N}по следующему правилу. Строки А соответствуют простым наборам P_i, столбцы – элементарным N_j. Элементы a_ij задаём следующим образом: a_ij = 1, если набор P_i входит в N_j , если не входит - то a_ij = 0. В итоге получаем матрицу А, содержащую единичные и нулевые элементы:

IV. Построение решеточного выражения В и упрощение его. Построение множества {Т} всех тупиковых нормальных форм функции.

Для каждого столбца j матрицы покрытий А, который соответствует элементарному набору N_j, выписываем номера строк i = i₁, ... , i_n , у которых a_ij = 1. Строим по ним дизъюнкцию D _j = (e_{i1, j} Ú ...Ú e_{inj, j}). Она показывает все возможные варианты вхождения простых наборов в элементарный N_j. Решеточное выражение записывают в виде конъюнкции всех D_i :

В = & D _j .

В решёточном выражении В раскрывают все скобки, представив его в виде дизъюнкции элементарных конъюнкций:

В =Ú (е _{s 1}& е _{s 2}& ... & е _{s ps}) .

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

В¢ =Ú (е _{l 1} & е _{l 2}& ...& е _{l pl} ) .

Каждая элементарная дизъюнкция е_l1& е_l2& ...& е_{l pl} , входящая в В¢,описывает тупиковую нормальную форму функции f следующим образом: каждый набор переменных е_li является набором переменных во внутренней функции формы. Например, в ДНФ - наборы переменных входят во внутренние конъюнкции, а полная ТДНФ образуется в результате их логического сложения: f = K _l,1Ú K _l,2Ú … Ú K _l,pl.

После построения множества {Т} всех тупиковых форм из них выбирается самая короткая (с наименьшим числом переменных), которая и будет искомой минимальной нормальной формой.

Пример 3. Построить МДНФ функции, заданной вектором истинности: f =(01100111).

Решение. Переменные обозначим x, y, z.

1.Множество {N} элементарных наборов, на которых функция равна единице, имеет вид: N₁ = (x,`y, z); N<sub>2</sub> = (x, y,`z); N₃= (x,`y, z); N<sub>4</sub>= ( x, y,`z ); N₅= ( x, y, z).При умножении этих наборов получаем конституенты единиц функции.

СДНФ имеет вид: f =`x`y z Ú `x y`z Ú x`y z Ú x y`z Ú x y z.

2. СкДНФ определяем по алгоритму Куайна:

а) неполное склеивание в СДНФ:

f =`x `y z Ú `x y`z Ú x`y z Ú x y`z Ú x y z Ú `y z Ú y`z Ú x z Ú x y ,

б) полное склеивание:

f = `y z Ú y`z Ú x z Ú x y .

Полученная форма является искомой СкДНФ. Множество простых наборов {P}имеет вид:

P₁= (y, z), P₂= (y,`z ), P₃= (х, z), P₄= (x, y).

3. Строим матрицу покрытий А:

4. Строим решёточное выражение. Поскольку элементарный набор N₁ покрывается простым набором Р₁, N₂ – Р₂, N₃ – (Р₁ и Р₃), N₄ – (Р₂ и Р₄), N₅ – (Р₃ и Р₄), то выражение принимает следующий вид:

В =1&2& (1Ú3)& (2Ú4)& (3Ú4).

5. Поочередно раскрываем скобки в конъюнкции В, устраняя повторные сомножители в слагаемых и применяя правило поглощения:

В = (121 Ú 123) & (2 Ú 4) & (3 Ú 4) = (12 Ú 123) & (2 Ú 4) & (3 Ú 4) = 12 && (2 Ú 4) & (3 Ú 4) = (122 Ú 124) & (3 Ú 4) = 12 & (3 Ú 4) = 123 Ú 124.

Таким образом, функция имеет две ТДНФ, в которые входят простые наборы (Р₁, Р₂, Р₃) и (Р₁, Р₂, Р₄):

Т₁= `y z Ú y`z Ú x z , Т₂= `y z Ú y`z Ú x y .

Так как в обеих формах по 6 символов переменных, то они обе являются искомыми МДНФ рассмотренной функции.

Пример 4. Построить МВНФ функции из Примера 3 с использованием базисных наборов {Ø, ¯}и {¯}.

Решение.

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

N₁ = (x, y,`z); N<sub>2</sub> = (x,`y, z); N₃= (x, y,`z); N<sub>4</sub>= (x,`y, z); N ₅= (x,`y,`z).

СВНФ для базисного набора {Ø , ¯ }имеет вид:

f = Ø ¯ (¯(x, y,`z); ¯(x,`y, z); ¯(x, y,`z); ¯(x,`y, z); ¯(x,`y,`z)).

2.СкВНФ определяем по алгоритму Куайна:

а) неполное склеивание в СBНФ:

f = د( ¯(x, y,`z); ¯(x,`y, z); ¯(x, y,`z); ¯(x,`y, z); ¯(x,`y,`z);¯(y,`z); ¯(y, z); ¯(x,`z); ¯(x,`y)).

б) полное склеивание:

f = د(¯(y,`z ); ¯(y, z); ¯(x,`z); ¯(x,`y)).

Полученная форма является искомой СкВНФ. Множество простых наборов {P}имеет вид:

P₁= (y, z), P₂= (y, z), P₃= (х,`z), P<sub>4</sub>= (x,`y).

3.Построение матрицы покрытий, решеточного выражения и его преобразования выполняются аналогично Примеру 3.

Полученные в итоге ТВНФ в базисе {Ø, ¯}имеют вид:

Т₁= د(¯(y,`z); ¯(y, z); ¯(x,`z)),

Т₂= د(¯(y,`z ); ¯(y, z); ¯(x,`y)).

Обе формы будут минимальными.

Переход к однофункциональном набору {¯}осуществляем с использованием правила ØА = ¯ (А,0). Тождественный нуль формально является функцией, однако на практике его получают, заземляя соответствующий вход элемента {¯}. После замены получим:

Т₁= ¯(¯(¯(y,¯(z, 0)); ¯(¯(у, 0), z); ¯(¯(х, 0), ¯(z, 0))), 0),

Т₂= ¯(¯(¯(y, ¯(z, 0)); ¯(¯(у, 0), z); ¯(¯(х, 0), ¯(у, 0)) ), 0).