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

Алгоритм основан на применении следующих законов алгебры логики, справедливых для пороговых функций, а, следовательно, и для нормальных форм рассматриваемого вида. Пусть имеется представление булевой функции 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; просмотров: 743;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.027 сек.