Алгебри булевих функцій

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

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

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

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

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

Розглянемо, ще один метод побудови скороченої ДНФ - метод Нельсона (R. Nelson). Цим методом зручно користуватись, якщо функція задана довільною кон'юнктивною нормальною формою.

Метод Нельсона обгрунтовує така теорема.

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

Для доведення достатньо переконатись, що у разі розкриття дужок у довільній кон'юнктивній нормальній формі булевої функції можна отримати будь-яку наперед задану просту імпліканту цієї

функції.

Приклад 28. Розглянемо булеву функцію , задану кон'юнктивною нормальною формою .

Розкриваючи дужки: .

Виконаємо поглинання й одержимо скорочену ДНФ булевої функції :

.

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

Властивості скороченої ДНФ

Скорочена ДНФ має деякі важливі властивості.

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

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

Теорема 30. Скорочена ДНФ монотонної функції не має заперечень змінних.

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

Наслідок. Скорочена ДНФ монотонної функції є одночасно й мінімальною ДНФ цієї функції.

2.6 Реалізація булевих функцій схемами з функціональних елементів

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

1) він має впорядкованих відростків зверху -входи і один відросток знизу -вихід;

2) на входи цього пристрою можна подавати сигнали, які мають значення 0 та 1;

3) для кожного набору сигналів на входах пристрій на виході у той самий момент, коли надійшли сигнали на входи, видає один з сигналів (0 або 1);

4) набір сигналів на входах однозначно визначає сигнал на виході, тобто, якщо у різні моменти на входи надійшли рівні набори сигналів, то в ці моменти на виході буде один і той самий сигнал. Кожному функціональному елементу з п входами ставлять у ні відповідність булеву функцію від п змінних у такий спосіб. Входу з номером і ставлять у відповідність змінну , а кожному набору значень змінних -- число яке дорівнює 0 або 1 залежно від сигналу, що видається на виході у разі подачі цього набору сигналів на входи функціонального

елемента. Щодо функції кажуть, що даний функціональний елемент її реалізує.

Рис. 9

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

Визначимо поняття схеми з функціональних елементів та її входи і вихід.

Кожний функціональний елемент є схемою з функціональних елементів з тими ж входами і виходом, що й у цього елемента.

Якщо - схема з функціональних елементів і два її входи з'єднані (рис. 10), то отримана конструкція є схемою з функціональних елементів. Входами схеми є всі не з'єднані входи і ще один вхід, який відповідає двом з'єднаним входам .

Рис. 10 Рис. 11

3. Якщо та - дві схеми з функціональних елементів, то конструкція , яку отримують з'єднанням деякого входу схеми з виходом схеми , також є схемою з функціональних елементів (рисю 11). Входами схеми є всі входи схеми , і всі входи схеми , за виключенням того, який з'єднаний з виходом схеми . Виходом схеми є вихід схеми .

4. Якщо в схемі з функціональних елементів її вхід з'єднати з виходом деякого функціонального елемента з без утворення циклу для будь-якого функціонального елемента (тобто вихід будь-якого функціонального елемента не повинен з'єднуватись з його входом, можливо, через інші елементи з ), то отримана конструкція є схемою з функціональних елементів (приклад такої конструкції наведено на рис. 12).

Рис. 12

Визначення схеми з функціональних елементів завершене. За цим означенням схема з функціональних елементів - математичний об'єкт. Зазначимо, що вона має різні технічні застосування.

Очевидно, що схема з функціональних елементів реалізує певну булеву функцію. Оскільки допустимими є з'єднання елементів, які відповідають суперпозиціям відповідних елементарних функцій, а система є функціонально повною, то будь-яку функцію можна реалізувати схемою з функціональних елементів, зображених на рис.9.

Під час побудови схем використовують викладені у параграфі (5) методи мінімізації булевих функцій.

Приклад 29. Побудувати схему з функціональних елементів, яка реалізує булеву функцію . За методом карт Карно знаходимо мінімальну ДНФ (див. приклад 29) . Відповідну схему показано на рис. 13.

Рис.13

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

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

Теорема 31. (теорема Шеннона-Лупанова). Для функції виконується

,

причому для довільного кількість булевих функцій , для яких , прямує до 0 з ростом п.

Зауваження. Функцію називають функцією Шеннона (на честь американського математика К. Шеннона). Символ ~ тут означає асимтотичну рівність: .Зміст другого твердження теореми полягає в тому, що з ростом п майже всі булеві функції реалізуються зі складністю, близькою до верхньої межі, тобто .

Теорема 31 свідчить, що більшість булевих функцій (у разі ) має складні мінімальні схеми. Це означає, що практичну цінність, з огляду на побудову схем, має достатньо вузький клас булевих функцій. Тому поряд з універсальними методами побудови схем [6] необхідно мати методи, пристосовані для певних класів булевих функцій, які більшою мірою враховують їхні властивості. Далі ознайомимось з одним підходом до реалізації достатньо вузького класу функцій.

Покажемо, як схеми з функціональних елементів можна використати для додавання двох цілих додатних чисел у двійковій системі числення. Спочатку побудуємо схему, яка обчислює х+у, де х та у - біти. Входи схеми - це х та у; на кожний із них може бути поданий сигнал 0 або 1. Конструкція буде об'єднанням двох схем (матиме два виходи). Вихід дає суму бітів у даному розряді, а вихід с використовують для біту перенесення у наступний розряд. У табл.10 наведені значення на входах і виходах схеми, яку називають півсуматором. Саму схему наведено на рис. 14. Зазначимо, що з табл.10 маємо:

.

Таблиця 10

Для того, щоб врахувати біт перенесення с, використовують схему,

Рис. 14 Рис.15

яку називають повним суматором . Входи цієї схеми такі: х, у та біт перенесення з попереднього розряду . Виходів два: сума у даному розряді і нове перенесення (у наступний розряд). Відповідні булеві функції задані у табл.11.

Зобразимо функції та у досконалій диз'юнктивній нормальній формі:

; .

Таблиця 11

Але замість того, щоб будувати повні суматори безпосередньо за вказаними формулами, використовують півсуматори. Схему повного суматора з використанням півсуматорів наведено на рис.15.

Нарешті, на рис.16 показано, як повні суматори і півсуматор використовують для додавання трирозрядних цілих чисел та у двійковій системі числення. Результат - двійкове число . Зазначимо, що (старший розряд суми) збігається з . Аналогічно будують схему для додавання п-розрядних двійкових чисел та .

Висновки

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

Існує три способи задання булевих функцій вебральний (словесний), аналітичний і табличний. Найбільш зручним є аналітичний спосіб.

Множину булевих функцій разом із уведеною на ній системою операцій називають алгеброю булевих функцій. Найбільш поширенішими є алгебра Буля (операціями якої є заперечення, кон'юнкція, диз'юнкція) та алгебра Жегалкіна, (операціями якої є кон'юнкція й додавання за mod 2).

Спеціальними формами зображення булевих функційв алгебрі Буля є диз'юнктивні нормальні та кон'юнктивні нормальні форми, а в алгебрі Жегалкіна - поліном Жегалкіна. Будь-яку булеву функцію, відмінну від нуля (одиниці) можна єдиним способом зобразити у ДДНФ (ДКНФ) та у формі полінома Жегалкіна.

Важливу практичну роль відіграють функціонально повні системи булевих функцій. Ефективний критерій функціональної повноти був встановлений у 1921 році Е.Постом.

Під мінімізацією булевих функцій розуміють знаходження найпростішого її зображення у вигляді суперпозиції функцій деякої функціонально повної сисеми. Розроблено ряд ефективних алгоритмів мінімізації, зокрема побудову скороченої ДНФ можна здійснити за алгоритмами Куайна, Мак-Класкі та методами Блейка і Нельсона. Тупикові ДНФ шукають за допомогою імплікантної таблиці Куайна. Для знаходження мінімальних ДНФ фуекцій невеликої кількості змінних (не більше шести) можна використовувати метод карт Карно.

Література

1. Єкимов О.Є. Дискретная математика, логика, группи, графи.- М.:Мир,2001

2. Новиков Ф.А.Дискретная математика для програмистов

3. Бардачок Ю.В. Дискретна математика с.205-227

4. Нікольський Ю.В. Дискретна математика с.328-387

5. Капітонова Ю.В. Основи дискретної математики.

6. Андерсен Д. Дискретна математика і комбінаторика. -СПб.: Вільямс,2003.

7. Рабкин Е.Л.,Фарфоровская Ю.Б. Дискретная математика

8. Бардачок Ю. М., Соколова Н. А. Дискретна математика- К.: Вища шк.,. 2002. - 287 с.

9. Алексеев В.Б. «Дискретная математика», 2002.

10. Владимиров Д. А. Булеви алгебры. -- Наука, 1969. -- 318 с

Размещено на Allbest.ru