Обобщенный метод Куайна
Алгоритм основан на применении следующих законов алгебры логики, справедливых для пороговых функций, а, следовательно, и для нормальных форм рассматриваемого вида. Пусть имеется представление булевой функции 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 = Øa 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 Ú x`y`z Ú 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 Ú x`y`z Ú x`y z Ú x`y .
2. Применяем операцию поглощения. Вначале – к х`у`z и х`у: f = `х у`z Ú х`у z Ú х`у , затем – к х`у z и х`у : f = `х у`z Ú х`у.
Поскольку одинаковых наборов во внутренних конъюнкциях нет, то правило удаления дубликатов не используется.
Последняя полученная формула и будет искомой СкДНФ функции f = (00101100). Её простыми наборами являются P1=(х, у,`z), P2= ( х,`у).
III. Формирование матрицы А покрытий множества простых наборов {P} = {P1, ... ,Ps} элементарными наборами {N} = {N1, ... , Nk}.
Допустим, на предыдущих шагах построены: множество простых наборов {P} = {P1, ... , Ps}, входящих в сокращенную форму, и множество элементарных наборов {N} = {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 Ú ...Ú einj, j). Она показывает все возможные варианты вхождения простых наборов в элементарный Nj. Решеточное выражение записывают в виде конъюнкции всех Di :
В = & 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} элементарных наборов, на которых функция равна единице, имеет вид: N1 = (x,`y, z); N2 = (x, y,`z); N3= (x,`y, z); N4= ( x, y,`z ); N5= ( 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}имеет вид:
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), то выражение принимает следующий вид:
В =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.
Таким образом, функция имеет две ТДНФ, в которые входят простые наборы (Р1, Р2, Р3) и (Р1, Р2, Р4):
Т1= `y z Ú y`z Ú x z , Т2= `y z Ú y`z Ú x y .
Так как в обеих формах по 6 символов переменных, то они обе являются искомыми МДНФ рассмотренной функции.
Пример 4. Построить МВНФ функции из Примера 3 с использованием базисных наборов {Ø, ¯}и {¯}.
Решение.
1. Элементарные наборы, на которых внутренние функции СВНФобразуют конституенты единицы, являются инвертированными по отношению к наборам из ДНФ и имеют вид:
N1 = (x, y,`z); N2 = (x,`y, z); N3= (x, y,`z); N4= (x,`y, z); N 5= (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}имеет вид:
P1= (y, z), P2= (y, z), P3= (х,`z), P4= (x,`y).
3.Построение матрицы покрытий, решеточного выражения и его преобразования выполняются аналогично Примеру 3.
Полученные в итоге ТВНФ в базисе {Ø, ¯}имеют вид:
Т1= د(¯(y,`z); ¯(y, z); ¯(x,`z)),
Т2= د(¯(y,`z ); ¯(y, z); ¯(x,`y)).
Обе формы будут минимальными.
Переход к однофункциональном набору {¯}осуществляем с использованием правила ØА = ¯ (А,0). Тождественный нуль формально является функцией, однако на практике его получают, заземляя соответствующий вход элемента {¯}. После замены получим:
Т1= ¯(¯(¯(y,¯(z, 0)); ¯(¯(у, 0), z); ¯(¯(х, 0), ¯(z, 0))), 0),
Т2= ¯(¯(¯(y, ¯(z, 0)); ¯(¯(у, 0), z); ¯(¯(х, 0), ¯(у, 0)) ), 0).
Дата добавления: 2015-10-05; просмотров: 750;