Смекни!
smekni.com

Системи булевих функцій (стр. 2 из 5)

З табл.1 бачимо, що φ1 = f7не зберігає константу 1 і не є монотонної, φ2=f8 - нелінійна й функція, φ3 = f16 не зберігає константу 0. Отже, всі умови теореми Поста виконані, і задана система

є повною.

Приклад 3. Довести, що система {|} є базисом.

Рішення. Розглянута система складається з однієї функції f15 (функції Шефера). З табл.1 бачимо, що f15 - функція, що не зберігає 0 і 1, немонотонна (монотонність порушується на наборах (1, 0) і (1, 1),, тому що

, a двоїста функція
нелінійна, тому що багаточлен Жегалкина для цієї функції має вигляд: 1 + X1X2. Отже, система {f15} = {|} задовольняє всім умовам теореми Поста і є базисом.

Таким чином, для аналітичного завдання булевої функції можна використовувати різні мови формул. Критерієм повинен служити характер розглянутої задачі.

2. Скорочені й тупикові диз'юнктивні нормальні форми

Відомо [4], що всяку булеву функцію можна записати, причому єдиним образом, у ДНФ, тобто у вигляді диз'юнкції елементарних кон'юнкцій (суми добутків). У зв'язку із цим можна порушувати питання про відшукання для заданої функцій такий ДНФ, що була б найбільш простий у порівнянні з її іншими ДНФ.

ДНФ називається мінімальної, якщо вона містить у порівнянні з іншими еквівалентними їй формами мінімальна кількість букв (при підрахунку враховується кожне входження букви у формулу).

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

Елементарну кон'юнкцію φдо назвемо імплікантоюбулевої функції f, якщо не існує такого двійкового набору змінних, при якому функція φдо приймає значення 1, а функція f - значення 0, то ecть φk Ú f = f.

Для того щоб перевірити чи є задана елементарна кон'юнкція функції f, треба всім змінним, які входять у цю кон'юнкцію без знака заперечення, додати значення 1, а тим змінним, які входять із запереченням - значення 0. Тоді елементарна кон'юнкція буде мати значення 1. Після цього треба, перевірити, чи приймає функція f значення 1 при будь-яких значеннях інших змінних. Надалі для спрощення записи булевих функцій знаки кон'юнкції будемо заміняти знаками множення або просто опускати.

Приклад 4. Перевірити, чи є одночлени

й
імплікантами булевої функції

.

Рішення. Думаючи в першому випадку Х1 = 1, X2 = 1, маємо φ1 = l і φ2 = l і

,

отже, φ2 - імпліканта заданої функції.

У другому випадку думаємо X1 = 0, X2 = l. Тоді

φ2 = 1, а

,

отже, φ2 не є імплікантою функції f.

Справедливі наступні твердження:

1. Якщо

імпліканти булевої функції f, то
й
також є її імплікантами.

2. Якщо функція

є імпліканта функції f, то функції
також є імплікантами функції f.

Елементарна кон'юнкція, що входить у ДНФ булевої функції, називається її простий імплікантою, якщо ніяка її частина не є імплікантою цієї функції.

Скороченої ДНФ даної булевої функції називається її ДНФ, складена тільки із простих імплікант.

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

.

Наприклад,

Для будь-якої заданої функції скорочена ДНФ є єдиною. Однак вонa може бути надлишкової внаслідок тогo, що деякі прості імпліканти цієї суми покриваються сукупностями інших доданків. Такі імпліканти називають зайвими, і вони можуть бути вилучені без порушення формул.

Скорочена ДНФ, з якої вилучені всі зайві імпліканти, називається тупикової ДНФ

Виключення зайвих імплікант зі скороченої ДНФ проводиться за допомогою правила поглинання: диз'юнкцію двох елементарних кон'юнкцій, з яких одна повністю втримується й інший, можна замінити кон'юнкцією, що має менший ранг, наприклад, X Ú XF = X,

.

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

Приклад 5. Спростити булеву функцію

.

Рішення. Ця функція містить тільки прості імпліканти, тобто є скороченою Однак вона надлишкова, тому що одночлен Х1X2 можна видалити. Після цього одержимо функцію:

.

Приклад 6. Знайти мінімальну ДНФ для функції

.

Рішення. Склеюючи перший і третій одночлени по змінною Х2, одержимо Х1X3X4. З першого й четвертого, а потім із друг і третього складаються після склеювання одержимо відповідно X1X2X3,

і т.д. Остаточний список імплікант має вигляд

У цьому списку є два одночлени X1X3 і Х2Х3Х4, які не поглинають інших одночленів із цього списку, отже, є простими імплікантами. Тому скорочена ДНФ має вигляд

, на ж є й мінімальної.

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

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

3. Алгоритм Квайна й Мак-Класки мінімізації булевої функції

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

1. Привести булеву функцію до СДНФ.

2. У СДНФ зробити всі можливі склеювання Отримана після цього ДНФ є скороченої, але серед простих імплікант можуть виявитися зайві.

3. Перейти від скороченої ДНФ до мінімального, тобто виключити зайві імпліканти. Для цього рекомендується скористатися імплікантою матрицею, у якій кожному рядку відповідає проста імпліканта, а кожному стовпцю - елементарна кон'юнкція, що містить всі змінні. СДНФ заданої функції Ця матриця заповнюється в такий спосіб під конституентами, у які входить дана проста імпліканта, ставиться мітка "1" Для знаходження мінімального покриття функції необхідно видалити з таблиці деякі зайві прості імпліканти Із цією метою реалізується наступний алгоритм.

1. Виділення ядра Квайна. Якщо в якому-небудь стовпці матриці є тільки одна 1, то імпліканта, що перебуває у відповідному стовпці, не є зайвою й повинна бути включена в мінімальне покриття функції. Такі імпліканти називаються істотними, а їхню сукупність називають ядромКвайна.