Метод основан на применении следующих законов алгебры логики, честных для пороговых функций, а, следовательно, и для обычных форм разглядываемого вида. Пускай имеется представление булевой функции f в виде некоей обычной формы f =F(j (x1a11 ,…, xna1n), …,j(x1ak1 ,…, xnakn)). Множества переменных, входящих во внутренние функции, обозначим через Х1,…, Хk .
Допустим, у внутренних функций формы имеется два комплекта переменных Xp =(x1ap1,…,xnapn)и Xq =(x1aq1 ,…,xnaqn), соседних по переменной с номером r .У них a p1 = a q1 , … ,a p(r-1) = a q(r-1), a p r = Oa q r , a p(r+1) = a q(r+1), . . . , a pn =a qn.
Для данной обычной формы честны следующие обобщенные операции склеивания:
а) полное склеивание:
f = F(j(Х1),…,j(Хр),…,j(Хq),…,j(Xk))=F(j(Х1),…,j(Хрxrapr),…,
j(Хq-1),j(Хq+1),…,j (X k)).
б) неполное склеивание (дополнение):
f=F(j(Х1),…,j(Хр),…,j(Хq),…,j(Xk))=F(j(Х1),…,j(Хр),…,j(Хq),…,j(Xk), j(Хрxrapr)).
В операции а) удаляется функция j(Хq), и переменная xrapr из j(Хр). Воперации б) к существующему комплекту внутренних функций j (Х1),…,j(Хk)добавляется новая функция j(Хрxrapr), в которой отсутствует переменная с номером r.
В случае если комплект с номером p отличается от комплекта с номером q отсутствием одной переменной xrapr (Xp = Хq xrapr ), то для любой формы честна операция.
в) поглощения (удаления внутренней функции с расширенным комплектом переменных)
f = F(j(Х1), …, j(Хр), …, j(Хq), … ,j(X k))= F(j(Х1), …, j(Хр), … ,j(Хq-1), j(Хq+1), …,j(Xk)).
В случае если комплекты переменных во внутренних функциях Xp и Хq однообразны (всецело совпадают), то честна операция
г) удаления дубликатов
f = F(j(Х1), … ,j(Хр), … ,j(Хq), … , j(X k))=F(j(Х1), …, j(Хр), … ,j(Хq-1), j(Хq+1), … ,j(Xk)).
Справедливость введенных операций, каковые являются правилами преобразования обычных форм, направляться из особенностей пороговых функций.
Обобщенный метод Куайна включает следующие операции:
1. Проведение в идеальной обычной форме всех вероятных операций неполного склеивания.
2. В взятой дополненной обычной форме исполнение всех вероятных операций полного склеивания.
3. Исполнение всех удаления дубликатов и возможных операций поглощения.
Полученная формула анализируется и, в случае если быть может, к ней опять используют операции 1) — 3) и т.д.
В следствии получается обычная форма, складывающаяся из несложных комплектов, другими словами сокращенная обычная форма рассмотренной функции.
Пример 2. Разглядим функцию из Примера 1 и выстроим для неё СкДНФ.
Ответ. СДНФ функции: f =`x y`z U x`y`z U x`y z. Элементарные комплекты: N1=(`x, y,`z), N2=(x,`y,`z), N3=(x,`y, z).
1.Производим в СДНФ все операции неполного склеивания. Для этого разглядываем в ней все вероятные пары элементарных комплектов и к тем из них, каковые являются соседними (отличающимися ровно по одной переменной), используем операцию неполного склеивания:
а) N1и N2 не соседние, потому, что у них отличие по двум переменным (x и y),
б) N1и N3 не соседние, отличие по всем трём переменным,
в) N2и N3 — соседние,т.к. отличаются ровно по одной переменной — z .
Используем к данной паре операцию неполного склеивания (дополнения):
f =`x y`z U x`y`z U x`y z U x`y .
2. Используем операцию поглощения. Сначала – к х`у`z и х`у: f = `х у`z U х`у z U х`у , после этого – к х`у z и х`у : f = `х у`z U х`у.
Потому, что однообразных комплектов во внутренних конъюнкциях нет, то правило удаления дубликатов не употребляется.
Последняя полученная формула и будет искомой СкДНФ функции f = (00101100). Её несложными комплектами являются P1=(х, у,`z), P2= ( х,`у).
III. Формирование матрицы А покрытий множества несложных комплектов {P} = {P1, … ,Ps} элементарными комплектами {N} = {N1, … , Nk}.
Допустим, на прошлых шагах выстроены: множество несложных комплектов {P} = {P1, … , Ps}, входящих в сокращенную форму, и множество элементарных комплектов {светло синий} = {N1 , … , Nk}, входящих в идеальную форму. Строим матрицу А размером s ´ k покрытий несложных комплектов {P} элементарными комплектами {N}по следующему правилу. Строки А соответствуют несложным комплектам Pi, столбцы – элементарным Nj. Элементы aij задаём следующим образом: aij = 1, в случае если комплект Pi входит в Nj , если не входит — то aij = 0. В итоге приобретаем матрицу А, содержащую единичные и нулевые элементы:
| N 1 | N 2 | … | Nk | |
| P1 | a 11 | a 12 | … | a 1k |
| … | … | … | … | … |
| Ps | a s1 | a s2 | … | a sk |
IV. Построение решеточного выражения В и упрощение его. Построение множества {Т} всех тупиковых обычных форм функции.
Для каждого столбца j матрицы покрытий А, что соответствует элементарному комплекту Nj, выписываем номера строчков i = i1, … , in , у которых aij = 1. Строим по ним дизъюнкцию D j = (ei1, j U …U einj, j). Она показывает все вероятные варианты вхождения несложных комплектов в элементарный Nj. Решеточное выражение записывают в виде конъюнкции всех Di :
В = D j .
В решёточном выражении В раскрывают все скобки, представив его в виде дизъюнкции элементарных конъюнкций:
В =U (е s 1 е s 2 … е s ps) .
В взятой дизъюнкции В производим все операции удаления дублирующих участников и все операции поглощения. В том случае, в то время, когда операции использовались, возьмём новый упрощенный вид дизъюнкции В:
В¢ =U (е l 1 е l 2 … е l pl ) .
Любая элементарная дизъюнкция еl1 еl2 … еl pl , входящая в В¢,обрисовывает тупиковую обычную форму функции f следующим образом: любой комплект переменных еli есть комплектом переменных во внутренней функции формы. К примеру, в ДНФ — комплекты переменных входят во внутренние конъюнкции, а полная ТДНФ образуется в следствии их логического сложения: f = K l,1U K l,2U … U K l,pl.
По окончании построения множества {Т} всех тупиковых форм из них выбирается самая маленькая (с мельчайшим числом переменных), которая и будет искомой минимальной обычной формой.
Пример 3. Выстроить МДНФ функции, заданной вектором истинности: f =(01100111).
Ответ. Переменные обозначим x, y, z.
1.Множество {N} элементарных комплектов, на которых функция равна единице, имеет форму: N1 = (x,`y, z); N2 = (x, y,`z); N3= (x,`y, z); N4= ( x, y,`z ); N5= ( x, y, z).При умножении этих комплектов приобретаем конституенты единиц функции.
СДНФ имеет форму: f =`x`y z U `x y`z U x`y z U x y`z U x y z.
2. СкДНФ определяем по методу Куайна:
а) неполное склеивание в СДНФ:
f =`x `y z U `x y`z U x`y z U x y`z U x y z U `y z U y`z U x z U x y ,
б) полное склеивание:
f = `y z U y`z U x z U x y .
Полученная форма есть искомой СкДНФ. Множество несложных комплектов {P}имеет форму:
P1= (y, z), P2= (y,`z ), P3= (х, z), P4= (x, y).
3. Строим матрицу покрытий А:
| N1 | N2 | N3 | N4 | N5 | |
| Р1 | |||||
| Р2 | |||||
| Р3 | |||||
| Р4 |
4. Строим решёточное выражение. Потому, что элементарный комплект N1 покрывается несложным комплектом Р1, N2 – Р2, N3 – (Р1 и Р3), N4 – (Р2 и Р4), N5 – (Р3 и Р4), то выражение принимает следующий вид:
В =12 (1U3) (2U4) (3U4).
5. Поочередно раскрываем скобки в конъюнкции В, ликвидируя повторные сомножители в слагаемых и используя правило поглощения:
В = (121 U 123) (2 U 4) (3 U 4) = (12 U 123) (2 U 4) (3 U 4) = 12 (2 U 4) (3 U 4) = (122 U 124) (3 U 4) = 12 (3 U 4) = 123 U 124.
Так, функция имеет две ТДНФ, в каковые входят простые комплекты (Р1, Р2, Р3) и (Р1, Р2, Р4):
Т1= `y z U y`z U x z , Т2= `y z U y`z U x y .
Так как в обеих формах по 6 знаков переменных, то они обе являются искомыми МДНФ рассмотренной функции.
Пример 4. Выстроить МВНФ функции из Примера 3 с применением базовых комплектов {O, ¯}и {¯}.
Tipo
