Системи булевих функцій (стр. 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, то імпліканта, що перебуває у відповідному стовпці, не є зайвою й повинна бути включена в мінімальне покриття функції. Такі імпліканти називаються істотними, а їхню сукупність називають ядромКвайна.