double arrow

Алгоритм для ДНФ


1. Для кожного елемента mÎM1 розраховується число k сусідніх елементів множини M1ÈMх.

2. Вибирається елемент mÎM1 з меншим значенням k, якщо таких елементів декілька, то для визначеності алгоритму вибирається перший.

3. Перебувають максимальні інтервали, що містять елемент m, і серед них вибирається один, котрий покриває найбільше число елементів, що залишилися в множині M1 (уточнюючі правила вибору наведені нижче в зауваженнях).

4. Кон’юнкція, що відповідає обраному максимальному інтервалу, записується в результуючу ДНФ. Всі елементи безлічі M1, покриті обраним інтервалом, переводяться в Mх (заміняються на «×»).

5. Якщо в матриці ще є елементи множини M1, то виконується п. 2. Інакше виконується пункт 6.

6. На матрицю наносяться всі інтервали, обрані при побудові спрощеної ДНФ, і якщо хоча б для одного з них усі точки покриті іншими обраними інтервалами, то такий інтервал видаляється й викреслюється відповідна кон’юнкція ДНФ. Перевірка безнадмірності сукупності інтервалів, що залишилася, проводиться доти, поки в кожному інтервалі не виявиться хоча б по одній точки, покритої тільки цим інтервалом. Ця процедура гарантує безнадмірність побудованої ДНФ.

Зауваження до алгоритму для ДНФ:

a) Про самоперевірку. Процедура п. 6 алгоритму дозволяє перевірити правильність розв’язання, побудована ДНФ повинна представляти функцію, тобто всі елементи множини M1 (або точки) покриті хоча б одним з інтервалів, жоден з елементів множини M0 (або порожні елементи матриці) не покритий жодним з інтервалів.

b) Про точність. Точний метод Квайна-МакКласки використовує для гарантії побудови оптимальних розв’язань таблицю покриттів.

Алгоритм для КНФ відрізняється від алгоритму для ДНФ тільки у п.п. 4 та 6, які у такому випадку вмають вигляд відповідно 4’ і 6’:

4’. Диз'юнкція, що відповідає обраному максимальному інтервалу, записується в ітогову КНФ. Всі елементи множини M1, що покриті обраним інтервалом, переводяться в Mх (заміняються на «×»).

6’. На матрицю наносяться всі інтервали, обрані при побудові спрощеної КНФ, і якщо хоча б для одного з них усі точки покриті іншими обраними інтервалами, то такий інтервал видаляється й викреслюється відповідна диз'юнкція КНФ. Перевірка безнадмірності сукупності інтервалів, що залишилася, проводиться доти, поки в кожному інтервалі не виявиться хоча б по одній точки, покритій тільки цим інтервалом. Ця процедура гарантує безнадмірність побудованої КНФ.

30.3. Метод Блейка

При мінімізації функції методом Квайна-МакКласки потрібно попередньо представити її в СДНФ, що часто пов'язано з додатковими перетвореннями функції.

Якщо виходити з довільної ДНФ, то для одержання проміжної скороченої ДНФ можна застосувати прямий метод Блейка, заснований на тотожності операцій узагальненого склеювання й поглинання.

acÚb`c = acÚb`cÚab; (aÚc)Ù(bÚ`c) = (aÚc)Ù(bÚ`c)Ù(aÚb);

acÚa=a; (aÚc)Ùa=a.

Передбачається, що операції виконуються з ліворуч на праворуч. Звичайно на першому етапі виконується операція узагальненого склеювання поки це можна, на другому етапі виконується операція поглинання.

Дійсно, acÚb`c = (acÚabc)Ú(b`cÚab`c) = acÚb`cÚab(cÚ`c) = acÚb`cÚab. Вхідні в тотожність букви можуть представляти будь-які булевы формули, зокрема кон’юнкції змінних.

Тотожність узагальненого склеювання застосовують доти, поки не перестануть з'являтися нові елементарні кон’юнкції, після цього застосовують тотожність поглинання (порядок виконання тотожностей насправді не дуже суттєвий). Можна показати, що довільна ДНФ приводиться до скороченої ДНФ застосуванням всіх можливих узагальнених склеювань із наступним усуненням мінтермів на основі операції поглинання aÚab = a. При цьому можливі такі випадки:

1. Кон’юнкція а містить змінну xj, кон’юнкція b – заперечення цієї ж змінної `xj (або навпаки). Тоді ab=0 й у результаті операції узагальненого склеювання не виходять нові мінтерми. Таким чином, слід піддавати цієї операції тільки ті пари мінтермів, у яких загальна змінна представлена як
xj і `xj.

2. Кон’юнкція а містить змінні, які входять у кон’юнкцію b (або навпаки), тобто b = ас. Тоді axiÚb`xi = axiÚac`xi = axiÚac`xiÚac = axiÚac = axiÚb, тобто мінтерм вихідної ДНФ поглинається мінтермом, утвореним у результаті узагальненого склеювання.

Приклад. Нехай функція задана покриттям, що відповідає ДНФ

y=`x1`x2 `x3 Ú `x1` x2 x3 Ú `x1 x2`x3 Ú x1`x2 x3 Ú x1 x2 x3.

Після узагальненого склеювання будуть отримані нові мінтерми

y= `x1`x2 Ú`x1`x3 Ú `x2x3 Ú x1x3.

Після поглинання виходить

y=`x1`x2 `x3 Ú `x1` x2 x3 Ú `x1 x2`x3 Ú x1`x2 x3 Ú x1 x2 x3 Ú `x1`x2Ú Ú`x1`x3 Ú `x2x3 Ú x1x3 = `x1`x2 Ú`x1`x3 Ú `x2x3 Ú x1x3.

Отже, скорочена ДНФ дорівнюватимє

y= `x1`x2 Ú`x1`x3 Ú `x2x3 Ú x1x3.

Представлення прикладу комплексами кубів, що допускають алгоритмічну реалізацію, має такий вигляд:

Кa= 000 Кb= 000 Кс=

001 001

010 010

101 101

111 111

(Нові куби першого кроку )

00´ 00´

0´0 0´0

´01 ´01

1´1 1´1

Тут Кa – вихідна ДНФ, Кb – вихідна ДНФ плюс нові куби, отримані в результаті узагальненого склеювання,
Кс – підсумкова скорочена форма, що складається з кубів {00´, 0´0, ´01, 1´1}, утворена в результаті поглинання. Їй і відповідає скорочена ДНФ

y= `x1`x2 Ú`x1`x3 Ú `x2x3 Ú x1x3.

Приклад. Нехай функція задана за допомогою ДНФ

y=x2`x3`x4 Úx1x2`x3Úx1`x2x4Ú`x1x2x4Ú`x1`x2x3x4.

Застосування операції узагальненого склеювання до пар (x2`x3`x4, `x1x2x4), (x1x2`x3, x1`x2x4), (x1x2,`x3 `x1x2x4), (x1`x2x4, `x1`x2x3x4) і облік того, що у двох останніх парах відбувається поглинання мінтермів, дає

y=(x2`x3`x4Ú`x1x2x4Ú`x1x2`x3)Ú(x1x2`x3Úx1`x2x4Úx1`x3x4
Ú(x1x2`x3Ú`x1x2x4Úx2`x3x4)Ú(x1`x2x4Ú`x2x3x4)Ú(`x1x2x4Ú `x1x3x4).

Видалення однакових членів aÚ a=a й угруповання старих і нових мінтермів дозволяє одержати

y=(x2`x3`x4Ú`x1x2x4Úx1x2`x3Úx1`x2x4)Ú(`x1x2`x3Úx1`x3x4Ú x2`x3x4Ú`x2x3x4Ú`x1x3x4).

При подальшому узагальненому склеюванні має сенс розглядати тільки пари, утворені новими мінтермами з усіма мінтермами отриманої ДНФ. Такими парами є (x2`x3`x4, x1`x3x4), (x2`x3`x4, x2`x3x4), (`x1x2x4, x1`x3x4), (`x1x2x4, `x2x3x4), (x1x2`x3, `x1x2`x3), (x1`x2x4, x2`x3x4), (x1`x2x4, `x1x3x4), (`x1x2`x3, x1`x3x4), (`x1x2`x3, `x1x3x4), (x1`x3x4, `x2x3x4), (x2`x3x4, `x1x3x4).

Застосування до кожної пари кон’юнкцій операції узагальненого склеювання й поглинання відповідно до наведених правил дає такий вираз:

y=`x1x2x4Úx1`x2x4Úx1`x3x4Ú`x2x3x4Ú`x1x3x4Úx2`x3.

Єдиний новий мінтерм x2`x3 у парі з кожним з інших мінтермів не приводить до появи нових мінтермів, тому отримана форма є скороченою ДНФ.

Представлення прикладу модифікованими комплексами кубів має такий вигляд:

Кa= ´100 Кb= ´100 Кс= ´100

110´ 110´ 110´

10´1 10´1 10´1

01´1 01´1 01´1

(Нові куби першого кроку)

1´01 1´01

´101 ´101

´011 ´011

0´11 0´11

010´ 010´

(Нові куби другого кроку)

´10´

У підсумку комплекс Кс утворює скорочене покриття.

Діючи аналогічно, можна застосувати метод Блейка й для одержання скороченої КНФ.

Приклад. Нехай функція задана покриттям, що відповідає КНФ (часткове склеювання Блейка)

y= (x1Úx2)Ù(`x1Úx2Úx3).

Після узагальненого склеювання буде отриманий вираз, що має вигляд

y= (x1Úx2)Ù(`x1Úx2Úx3)Ù(x2Úx3).

Після виконання поглинання буде отриманий вираз

y= (x1Úx2)Ù(x2Úx3).

Представлення прикладу модифікованими комплексами кубів має такий вигляд:

Кa= 00´ Кb= 00´ Кс= 00´

100 100

(Нові куби першого кроку )

´00 ´00

Комплекс Кс, що складається із двох кубів {00´, ´00}, утворює скорочене покриття.

Контрольні запитання

1. Які дії припускає перший крок алгоритму побудови максимальних інтервалів для заданої точки?

2. Які дії припускає другий крок алгоритму побудови максимальних інтервалів для заданої точки?

3. Які дії припускає третій крок алгоритму побудови максимальних інтервалів для заданої точки?

4. Як працює алгоритм побудови максимальних інтервалів для ДНФ?

5. Які зміни необхідні для алгоритму побудови максимальних інтервалів для КНФ?

6. Які властивості застосовуються в методі Блейка?

7. У чому різниця між методами Блейка і Квайна-МакКласкі?

8. Виконання яких кроків припускає метод Блейка?

9. Які зміни необхідні для застосування методу Блейка для КНФ?


Сейчас читают про: