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

Размещено на http://www.allbest.ru/

Дипломна робота

Тема “Алгебри булевих функцій”

Зміст

Вступ

Розділ І. Булеві функції

1.1.Основні поняття та означення

1.2.Елементарні булеві функції

Розділ ІІ. Булеві алгебри

2.1.Алгебра Буля та алгебра Жегалкіна

2.2.Спеціальні форми зображення булевих функційв алгебрах Буля і Жегалкіна

2.2.1.Диз'юктивні нормальні форми

2.2.2.Кон'юктивні нормальні форми

2.2.3.Поліном Жегалкіна

2.3.Повнота і замкненість

2.3.1.Функціонально повні системи

2.3.2.Замкнені класи

2.3.3.Критерій функціональної повноти системи булевих функцій

2.3.4.Послаблена функціональна повнота

2.4.Мінімізація булевих функцій

2.5.Метод побудови скороченої ДНФ

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

Висновки

Література

Додатки

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

Вступ

Основи теорія булевої функції закладені в праці видатного англійського математика Джорджа Буля “З досліджень законів мислення, на яких засновані математичні теорія логіки і теорія ймовірностей” (1854). Мету і завдання книги автор сформулював так: „У запропонованому для розгляді трактаті ми намагаємося наслідувати фундаментальні закони тих операцій, які здійснює розум під час міркування, щоб висловити їх на символьній мові обчислення і на цій основі побудувати науку логіки і її метод”. Апарат двійкової логіки, який уперше виклав Джордж Буль, має велике значення у комп'ютерній техніці, при розв'язанні найрізноманітніших задач обробки інформації.

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

Великий внесок у розвитку теорії булевих функцій внесли математики І.Жегалкін, Е. Пост (E. Post), В. Куайн (W. Quine), Мак-Класкі (McCluskey), А. Блейк (A. Blake), Р. Нельсон (R. Nelson), М. Карно (M. Karnaugh), Е. Вейч (E. Veitch) та інші.

Мета дипломної роботи -вивчити основні теоретичні положення теорії булевих функцій та показати їх практичне застосування.

Завдання дослідження:

1.Означити основні поняття теорії булевих функцій, проілюструвати їх на прикладах і навести зразки задач, які зводяться до встановлення тих чи інших властивостей булевих функцій.

2.Дати означення алгебри Жегалкіна та алгебри Буля та розглянути спеціальні форми зображення булевих функцій в цих алгебрах.

3.Розкрити поняття функціональної повноти системи булевих функцій.

4.Узагальнити різні методи мінімізації булевих функцій.

5.Розглянути задачу реалізації булевих функцій схемами з функціональних елементів.

6.Дослідити історичні аспекти розвитку теорії булевих функцій.

Предмет дослідження- алгебра Буля та алгебра Жегалкіна.

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

Наукова новизнаі практична значущість роботи. Результати досліджень дипломної роботи можуть бути використані студентами для поглибленого вивчення матеріалу з дискретної математики.

Апробація результатів дослідження. Результати дипломної роботи доповідалися на звітній науковій конференції викладачів і студентів Волинського національного університету імені Лесі Українки (травень 2010р.).

Структура дипломної роботи. Робота склалається з вступу, двох розділів, висновків, списку використаної літератури та додатків.

Розділ І. Булеві функції

1.1 Основні поняття та означення

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

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

Нормою набору називають число , що дорівнює кількості його одиничних компонент. «^=|

Віддаллю Хемінга між наборами та називають число

.

Це число рівне кількості компонент, у яких набори та різні. Набори та називають сусідніми, якщо і протилежними, якщо . Отже, сусідні набори відрізняються в одній компоненті, а протилежні - в усіх n компонентах. Наприклад, набори (0100) та (1100) - сусідні, а (0100) і а (1011)-протилежні.

Скінченність області визначення довільної булевої функції дає змогу задавати таку функцію таблицею. Розташуємо всі набори значень змінних у стовпчик у лексикографічному порядку і вкажемо значення функції на кожному з них. Одержимо таблицю булевої функції (див. табл.1).

Таблиця 1

0 0 . . . 0 0 0 0 . . . 0 1 0 0 . . . 1 0 … … … … … 1 1 . . . 1 1	… … … … …

Правий стовпчик цієї таблиці (стовпчик значень функції) складається з нулів та одиниць. Отже, n-місних булевих функцій існує стільки, скільки існує наборів довжини з 0 та 1. Тому справедливе наступне твердження.

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

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

Множину наборів значень змінних, на яких булева функція приймає значення 1, позначають :

.

Множина , очевидно, повністю визначає функцію f.

Змінну функції називають істотною, якщо існує такий набір значень змінних, що .

Змінну, яка не є істотною, називають неістотною, або фіктивною. Отже, змінна функції неістотне (фіктивна), якщо

для довільних значень змінних. Це означає, що зміна значення в довільному наборі значень не змінює значення функції. У цьому випадку функція залежить від (п-1) змінної, тобто є функцією . У такому випадку говорять, що функція g отримана із функції f вилученням фіктивної змінної, а функція f отримана із g уведенням фіктивної змінної.

Функції f та g називають рівними, якщо функцію g можна отримати з f шляхом уведення або вилучення фіктивних змінних.

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

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

Таблиця 2

X	0	1	x
0 1	0 0	1 1	0 1	1 0

Таблиця 3

				~
0 0 0 1 1 0 1 1	0 0 0 1	0 1 1 1	1 1 0 1	1 0 0 1	0 1 1 0	1 1 1 0	1 0 0 0

2.1 Елементарні булеві функції

Розглянемо аналітичний метод задання булевих функцій. За допомогою табл. 2 та 3 визначимо функції, які називають елементарними:

1. =0 - константа 0.

=1 --константа 1.

=х - тотожна функція.

- заперечення х.

- кон `юнкція.

- диз `юнкція.

-імплікація.

= ~- еквівалентність.

-додавання за mod2.

-штрих Шеффера.

11. - стрілка Пірса.

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

Приклад 1.1. Тримісна булева функція задана формулою. Вона є суперпозицією функцій

, , .

Формулу, яка містить лише змінні, дужки й символи функцій із множини , називають формулою над .

Приклад 1.2. Нехай , тоді вираз є формулою над .

З метою зменшення кількості дужок у формулах уводять пріоритет операцій, які визначені відповідними функціями:

1) заперечення;

2) кон'юнкція;

3) усі інші операції.

Приклад 1.3. Функція задана формулою . Задамо її таблицею. Процес розв'язування цієї задачі наведено у табл.4.



Таблиця 1.4

x y z	xz	yxz
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	0 0 0 0 0 1 0 1	0 0 1 1 0 1 1 0	1 0 1 0 1 0 1 0	0 1 1 0 0 0 1 1	1 1 1 1 0 0 0 0	0 1 1 0 1 1 1 1

Про формулу, яка задає функцію, кажуть також, що вона реалізує або зображає цю функцію.

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

Приклад 1.4. Формули та еквівалентні:= . Щоб переконатись потрібно побудувати таблиці відповідних булевих функцій. Очевидно, змінна z у другій формулі є фіктивною.

Крім побудови таблиць, можна використати метод доведення еквівалентності формул - рівносильні (еквівалентні) перетворення.

Розділ ІІ. Булеві алгебри

2.1 Алгебра Буля та алгебра Жегалкіна

Множину булевих функцій разом із уведеною на ній системою операцій називають алгеброю булевих функцій.

Розглянемо дві алгебри. Алгебру , операціями якої є заперечення , кон'юнкція та диз'юнкція, називають алгеброю Буля.

Алгебру , операціями якої є кон'юнкція й додавання за mod2, називають алгеброю Жегалкіна.

Формули алгебри Буля та алгебри Жегалкіна будують із знаків операцій відповідної алгебри, круглих дужок, символів змінних і констант 0 та 1.

Порядок виконання операцій у разі відсутності дужоку булевій алгебрі такий: заперечення, кон'юнкція, диз'юнкція. В алгебрі Жегалкіна спочатку виконують кон'юнкція, а потім - додавання за mod2. У разі наявності дужок спочатку повинні виконувати операції всередині них. У булевій алгебрі роль дужок у разі заперечення складних виразів відіграє сам символ заперечення.

Приклад 5. Замість можна написати , а замість записують .

Закони алгебри Буля.

Закони асоціативності

, .

Закон комутативності

, .

Дистрибутивний закон для кон'юнкції відносно диз'юнкції

.

Дистрибутивний закон для диз'юнкції відносно кон'юнкції

.

Закон подвійного заперечення

.

Закони де Моргана

, .

Закони ідемпотентності

, .

Закони поглинання

, .

Співвідношення для констант

, , , , , .

Закон виключеного третього

.

Закон протиріччя

.

Закони алгебри Жегалкіна.

Закони асоціативності

, .

Закон комутативності

, .

Дистрибутивний закон для кон'юнкції відносно додавання за mod2

.

Співвідношення для констант

, , .

Закони ідемпотентності для ко'нюнкції

.

Закон зведення подвбних членів у разі додавання за mod2

.

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

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

Закони алгебр Буля та Жегалкіна дають змогу доводити нові еквівалентності вже без таблиць, на основі тотожних перетворень.

Приклад 6. Доведемо, що

а);

б) .

Двічі використовуючи закони дистрибутивності, одержимо

а) ;

б) .

Приклад 7. Доведемо, що . Використовуючи закони де Моргана, подвійного заперечення та асоціативності, можемо записати

.

Наведемо еквівалентності, які дозволяють перетворити будь-яку формулу булевої алгебри у рівносильну їй формулу алгебри Жегалкіна та навпаки:

;

;

.

Зазначимо, що за допомогою законів алгебр Буля та Жегалкіна
можна спрощувати різні формули в цих алгебрах.

Приклад 8. Перетворити формули у рівносильну формулу алгебри Жегалкіна. Отриману формулу спростити.

а);

б);

в).

Розв'язання

а)

;

б)

;

в).

Приклад 9. Перетворити формули у рівносильну формулу алгебри Буля і спростити її.

а);

б);

в).

Розв'язання

а);

б)

;

в)

.

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

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

Теорема 2. Якщо

,

.

Доведення.

.

З теореми випливає таке твердження.

Принцип двоїстості. Якщо у формулі , яка реалізує функцію , усі символи функцій замінити, відповідно, на символи двоїстих функцій, то отримана формула реалізує функцію , двоїсту до .

В алгебрі Буля принцип двоїстості має простіший вигляд.

Принцип двоїстості в алгебрі Буля. Якщо у формулі , яка реалізує функцію , усі кон'юнкції замінити на диз'юнкції, диз'юнкції - на кон'юнкції, 1 замінити на 0, 0 - на 1, то отриманії формула реалізує функцію, двоїсту до .

Приклад 10. Знайти функцію, двоїсту до

.

Розв'язання

За принципом двоїстості матимемо

..

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

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

Приклад 10. Булева функція задана таблицею. Побудувати двоїсту функцію .

Розв'язання

Використаємо інвертування стовпчика значень функції і перевернемо його.

0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 1 1 0 1 1 0 0	1 1 0 0 1 0 0 1

2.2 Спеціальні форми зображення булевих функцій в алгебрах Буля і Жегалкіна

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

2.2.1 Диз'юнктивні нормальні форми

Введемо позначення , де - параметр, який дорівнює 0 або 1. Очевидно, що

Зазначимо, що .

Зафіксуємо множину змінних .

Елементарною кон'юнкцією називають формулу , де змінні з множини X, причому всі різні. Число r називають рангом кон'юнкції. У випадку коли r=0 кон'юнкцію називають порожньою і покладають рівною 1.

Приклад 11. Елементарними кон'юнкціями є 1, , а формули 0, , , елементарними кон'юнкціями не є.

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

Диз'юнктивною нормальною формою (ДНФ) називають диз'юнкцію елементарних кон'юнкцій , у якій (j=1,2,…,5) попарно різні.

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

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

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

Приклад 12. Звести до диз'юнктивної нормальної форми. Використовуючи сформульований алгоритм отримаємо.

ДНФ булевої функції не єдина, наприклад,

.

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

Теорема 3. Будь-яку булеву функцію можна єдиним способом зобразити в досконалій диз'юнктивній нормальній формі.

Доведення. Нехай задано деяку функцію . Кожному двійковому набору значень змінних відповідає єдина конституента одиниці, яка перетворюється на цьому наборі в 1 і визначена так: . Усі інші конституенти одиниці на даному наборі перетворюються в 0.

Нехай - значення функції, яке вона приймає на i-му двійковому наборі (i=0,1,…,), - конституента одиниці, що відповідає i-му набору. Доведемо рівність

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

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

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

Приклад 13. Побудувати ДДНФ для функції, заданої табл. 5.

Таблиця 5

0 0 0 1 0 0 1 1	1 0 0 1

Функція приймає значення 1 на наборах 00 та 11. Отже,

.

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

.

Приклад 14. Перетворити диз'юнктивну нормальну форму у досконалу.

Застосовуючи розщеплення для кон'юнкції і закон ідемпотентності для диз'юнкції, одержимо



Якщо із формули деякими тотожними перетвореннями можна отримати формулу , то можна отримати із , використовуючи ті самі тотожні перетворення.

Теорема 4. Для довільних рівносильних формул алгебри Буля та існує еквівалентне перетворення в за допомогою основних законів цієї алгебри.

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

Важливість цієї теореми в тому, що основних законів алгебри Буля є достатньо для довільних еквівалентних перетворень у цій алгебрі.

2.2.2 Кон'юнктивні нормальні форми

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

Зафіксовано множину . Елементарною диз'юнкцією називають вираз , у якому всі різні. Число r називають рангом диз'юнкції. У разі r= 0 диз'юнкцію називають порожньою і вважають рівною 0. Приклади елементарних диз'юнкцій: , 0, .

Кон 'юнктивною нормальною формою (КНФ) називають кон'юнкцію елементарних диз'юнкцій , у якій всі різні.

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

Приклад 15. Знайти КНФ для формули .

Використовуючи сформульований алгоритм, одержимо

.

Елементарну диз'юнкцію рангу п називають конституентою нуля. Іншими словами, конституента нуля - це елементарна диз'юнкція, у яку входять всі змінні з множини X.

Кожному двійковому набору взаємно однозначно відповідає конституента нуля , яка перетворюється на ньому в 0. Усі інші конституенти нуля на цьому наборі перетворюються в 1. Наприклад, набору 0111 відповідає конституента .

Досконалою кон 'юнктивною нормальною формою (ДКНФ) називають КНФ, у якої кожна елементарна диз'юнкція є конституентою нуля.

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

Візьмемо тотожність для двоїстих формул

.

Ліва частина дорівнює , а праву перетворюємо далі

=.

Отже,

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

Приклад 16. Побудувати ДКНФ функції, заданої табл.5.

Функція приймає значення 0 на наборах 01 та 10. Отже,

.

На основі тотожних перетворень будь-яку КНФ мож на перетворити у ДКНФ. Якщо в деяку елементарну диз'юнкцію d не входить змінна x, то потрібно записати рівносильний вираз і використати дистрибутивний закон:

. Після тривіальних перетворень отримаємо ДКНФ.

Приклад 17. Перетворити КНФ у досконалу КНФ. Використовуючи розщеплення диз'юнкцій, запишемо

2.2.3. Поліном Жегалкіна

Елементарну кон'юнкцію називають монотонною, якщо вона не містить заперечень змінних. Наприклад, , 1 -монотонні кон'юнкції.

Формулу

де - попарно різні монотонні кон'юнкції змінних із множини , називають поліномом Жегалкіна. Найбільший із рангів елементарних кон'юнкцій, що входять у поліном, називають степенем полінома.

Приклад 18. Формули x, 1, - поліноми Жегалкіна, а формули хх, не є поліномами Жегалкіна.

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

Теорема 5. Будь-яку булеву функцію можна єдиним способом зобразити у формі полінома Жегалкіна.

Доведення. Нехай - довільна булева функція. Достатньо провести доведення для функцій, відмінних від констант, тому що 1 та 0 є поліномами Жегалкіна. Задамо функцію f досконалою диз'юнктивною нормальною формою, тобто деякою диз'юнкцією конституент одиниці . Замінемо знак знаком і одержимо . Покажемо, що функції f та g рівні. На жодному наборі () значень змінних дві різні конституенти одиниці не можуть одночасно перетворитись в 1, оснільки і- а конституента одиниці перетворюється в 1 лише на і-му наборі. Отже, під час обчислення значень функцій f та g потрібно знайти значення диз'юнкції або, відповідно, суми за mod2 членів, із яких лише один може дорівнювати одиниці, решта-обов'язково нулі. Але у такому випадку диз'юнкція та додавання за mod2 приводить до одного й того ж результату, (до нуля, якщо всі члени ДОРІВНЮЮТЬ нулю, і ДО ОДИНИЦІ, ЯКЩО ОДИН І ЛИШе ОДИН член дорівнює одиниці).

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

Доведемо, що таке зображення єдине. Для цього підрахуємо кількість поліномів Жегалкіна від п змінних . Кількість кон'юнкцій вигляду дорівнює кількості підмножин множини {1,2, ..., п}, тобто . Кожна з цих кон'юнкцій може входити в поліном із коефіцієнтом 0 або 1. Отже, кількість поліномів Жегалкіна від п змінних дорівнює кількості кортежів довжини , елементами яких є 0 або 1, тобто , що дорівнюють

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

Побудова полінома Жегалкіна (метод невизначених коефіцієнтів).

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

Приклад 19. Побудуємо поліном Жегалкіна для функції

а).

Загальний вигляд полінома від двох змінних з невизначеними коефіцієнтами такий:

.

Прирівняємо значення функції і полінома на всіх чотирьох наборах значень змінних і одержимо систему рівнянь

,

,

,

.

Звідси визначаємо , ,,. Отже, .

б)

Загальний вигляд полінома від трьох змінних:



Прирівняємо значення функції і полінома на всіх восьми наборах значень змінних

, ,

, ,

, ,

,,

, ,

,

Отже

Побудова полінома Жегалкіна на основі тотожних перетворень.

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

Приклад 20. Побудуємо поліном Жегалкіна для функції

а).

.

б)

Побудова полінома Жегалкіна за досконалою ДНФ булевої функції. Цю побудову здійснюють за схемою доведення теореми 5. Такий спосіб доцільно застосовувати, коли функція задана досконалою ДНФ, або якщо цю форму легко знайти.

Приклад 21. Побудувати зазначеним методом поліном Жегалкіна для функції .

Спочатку перетворимо ДНФ у досконалу:

Повторюючи схему доведення теореми 5, отримаємо

.

Теорема 6.. Булева функція має істотними всі змінні, які входять у її поліном Жегалкіна.

Доведення. Нехай змінна входить у поліном Жегалкіна функції . Згрупуємо члени, які містять , і винесемо за дужки:

.

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

2.3 Повнота і замкненість

2.3.1 Функціонально повні системи

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

Приклад 22. Розглянемо деякі повні системи.

1. Система - повна, бо довільну булеву функцію можна зобразити у ДДНФ.

2. Система - повна. Дійсно, якщо функція , то зобразимо її поліномом Жегалкіна; якщо , то .

Не кожна система булевих функцій є повною.

Наприклад, система - неповна; через неї не можна зобразити функцію двох змінних.

Дослідження повноти одних систем можна звести до дослідження повноти інших систем.

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

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

Приклад 23.

1.Система - повна, бо повною є система 1 і .

2.Система - повна, тому що повною є система 1 і

.

Система є повною, тому що повною є система 3 і .

2.3.2. Замкнені класи

Множину К булевих функцій називають замкненим класом, якщо довільна суперпозиція функцій із К знову належить К. Будь-яка система булевих функцій породжує деякий замкнений клас. Цей клас складається з усіх функцій, які можна отримати суперпозиціями функцій із , його називають замиканням . Замикання позначають []. Очевидно, що якщо К- замкнений клас [К]=К, а якщо - функціонально повна система, то [].

Існує п'ять найважливіших замкнених класів:

клас функцій, що зберігають 0;

клас функцій, що зберігають 1;

клас самодвоїстих функцій;

клас М монотонних функцій;

клас лінійних функцій.

Клас функцій, що зберігають 0. Булеву функцію називають функцією, яка зберігає 0, якщо .

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

Теорема 8. - замкнений клас. Іншими словами, із функцій, що зберігають 0, суперпозицією можна одержати лише функції, що зберігають 0.

Доведення. Клас містить тотожну функцію. Отже, досить довести, що функція

зберігає 0, якщо функції зберігають 0. Справді .

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

Клас функцій, що зберігають 1. Булеву функцію називають функцією, яка зберігає 1, якщо.

Наприклад, функції належить класу , а функції не належать .

Теорема 9. - замкнений клас.

Доведення. містить тотожну функцію. Отже, достатньо довести, що функція

 зберігає 1, якщо функція

зберігають 1. Справді,

.

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

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

, а .

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

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

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

Теорема 10. Клас самодвоїстих функцій замкнений.

Доведення.Оскільки тотожна функція належить класу , достатньо довести, що функція

є самодвоїстою, якщо функції самодвоїсті. Використовуючи принцип двоїстості, отримаємо:

.

Наслідок. Повна система булевих функцій повинна містити хоча б одну несамодвоїсту функцію.

Теорема 11 (лема про несамодвоїсту функцію). Із несамодвоїстих функцій підстановкою функцій таможна отримати несамодвоїсту функцію однієї змінної, тобто константу.

Доведення. Нехай . Отже, існує принаймні один такий набір значень змінних, що

.

За набором визначимо допоміжні функції ,:

Легко переконатись, що ці функції мають властивість ,

.

Розглянемо функцію .Ця функція отримана з функції підстановкою та. Функція - константа, оскільки

.

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

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

Теорема 12. Нехай - монотонна функція. Якщо не зберігає 0, то вона тотожно дорівнює 1. Якщо не зберігає 1, то вона тотожно дорівнює 0.

Доведення. Для будь-якого набору виконується . Далі, .Отже, для довільного набору , тобто є константою 1. Друге твердження теореми доводять аналогічно.

Наслідок. Якщо функція і не є константою, то вона немонотонна.

Отже, всі монотонні функції, окрім констант 0 та 1, належать . Існують функції, які належать , але не є монотонними, наприклад, .

Теорема 13. Клас М монотонних функцій замкнений.

Доведення. Оскільки тотожна функція належить класу М, то для доведення замкненості М досить показати, що функція

монотонна, якщо функції монотонні. Нехай , тоді для всіх . Звідси

.

Отже .

Наслідок. Повна система булевих функцій повинна містити хоча б одну монотонну функцію.

Теорема 14 (лема про немонотонну функцію). Із немонотонної фунлції підстановкою констант 0, 1 та функції х можна отримати функцію .

Доведення. Нехай , отже, існує два набори , значень змінних такі, що , але , тобто , .

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

Підставимо у функцію замість змінних, яким у наборах та відповідають однакові значення, просто ці значення, а не місце решти змінних - функцію х. Тоді отримаємо функцію однієї змінної . Враховуючи, що , , одержимо , . Отже, .

Клас L лінійних функцій. Булеву функцію називають лінійною, якщо її поліном Жегалкіна має вигляд

.

Це поліном першого степеня, або лінійний поліном. Він не має багатомісних кон'юнкцій.

Коефіцієнти лінійного полінома утворюють довільний набір значень із нулів та одиниць. Через єдиність полінома Жегалкіна різним наборам коефіцієнтів відповідають різні булеві функції. Отже, є рівно лінійних булевих функцій від змінних. Прикладами лінійних булевих функцій є 0, 1,х,, а функції - нелінійні.

Серед лінійних функцій самодвоїстими є ті, у яких поліном Жегалкіна містить непарну кількість змінних, а несамодвоїстими ті, у яких поліном Жегалкіна містить парну кількість змінних. Наприклад, функції двоїсті, а функції - несамодвоїсті.

Серед лінійних функцій монотонними є лише 0, 1, х.

Теорема 15. Клас L лінійних функцій замкнений.

Доведення. Множина L усіх лінійних функцій є замкнутим класом, оскільки підстановка формул вигляду у формулу такого ж вигляду знову дає формулу того самого вигляду.

Наслідок. Повна система булевих функцій повинна містити хоча б одну нелінійну функцію.

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

Доведення. Нехай . Тоді її поліном Жегалкіна містить кон'юнкції змінних. Виберемо серед них кон'юнкцію найменшого рангу, нехай це буде

.

Покладемо а для всіх , які не входять в , покладемо . Підстановка цих констант у поліном перетворить в , а решту кон'юнкцій - в 0. При цьому функція набере вигляду

, де - коефіцієнти, що дорівнюють 0 або 1 і залежать від конкретної функції .

Розглянемо функцію

.

Отже, .

Цю функцію отримано суперпозицією констант 0 та 1, заперечення та функції . Якщо , то . Якщо ,то .

2.3.3 Критерій функціональної повноти системи булевих функцій

Теорема про функціональну повноту системи булевих функцій Буля, доведена Е. Постом (E. Post) у 1921 p.

Теорема 17. Для того, щоб система булевих функцій була функціонально повною, необхідно й достатньо, щоб вона містила

1) функцію, що не зберігає 0;

2) функцію, що не зберігає 1;

3)несамодвоїсту фуикцію;

4) немонотонну функцію;

5) нелінійну функцію.

Іншими словами, для повноти системи необхідно й достатньо, щоб вона повністю не містилась у жодному із п'яти замкнених класів .

Доведення. Необхідність. Вона випливає із замкненості кожного з п'яти розглянутих класів (наслідки зі теорем 8, 9, 10,13,15).

Достатність. Уведемо позначення для функцій із системи :

-функція, що не зберігає 0;

-функція, що не зберігає 1;

-несамодвоїста функція;

-немонотонна функція

-нелінійна функція.

Доведення виконаємо в 2 етапи.

Перший етап. На цьому етаті одержимо константи 0 та 1. Розглянемо функцію (не зберігає 0): . Можливі два випадки.

1) , тоді фуцнкція тотожно дорівнює 1, бо , .

Із функції (не зберігає 1) у цьому випадку можна одержати константу 0, тому що .

2) . Тоді функція є запереченням: , оскільки , .

Із несамодвоїстої функції і побудованої функції за лемою про несамодвоїсту функцію ( теорема 11) одержимо константу. Другу константу одержимо, використовуючи , оскільки , . Отже, у випадках 1) та 2) одержимо функції 0 та 1.

Другий етап . Використовуючи константи 0, 1 і немонотонну функцію за лемою про немонотонну іункцію ( теорема 14) одержимо . Далі, використовуючи константи 0, 1 і функції та за лемою про нелінійну функцію ( теорема 16) одержимо кон'юнкцію двох функцій .

Отже, через функції системи виразили та . Але система -повна. Отже, за теоремою 7 і система повна.

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

У клітках таблиці Поста ставлять знак «+» або «-» залежно від того, належить, чи неналежить функція замкненому класу. Для повноти системи функцій необхідно і достатньо, щоб у кожному стовпчику таблиці Поста був хоча б один «-».

Приклад 24. Дослідити, чи є функціонально повною система . Побудувавши таблиці Поста (табл.6), переконуємось чи ця система є функціонально повною.

	-	+	-	-	-
0	+	-	-	+	+

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

Теорема 18. Максимальна кількість функцій базису дорівнює 4.

Доведення. Функція або несамодвоїста: (випадок 1 доведення теореми 17), або не зберігає 1 і немонотонна (випадок 2 доведення теореми 17).

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

2.3.4. Послаблена функціональна повнота

Систему булевих функцій називають послаблено функціонально повною, якщо довільну булеву функцію можна зобразити формулою над множиною , тобто суперпозицією констант 0,1 та функцій із системи .

Теорема 19. Для того, щоб система булевих функцій була послаблено функціонально повною, необхідно й достатньо, щоб ця система містила хоча б одну нелінійну функцію і хоча б одну немонотонну функцію.

Доведення. За наявності констант 0 та 1 маємо функцію, що не зберігає 0 (функція 1), функція, що не зберігає 1 (функція 0) і несамодвоїста функція (кожна з функцій 0 та 1). Разом з тим, константи 0 і 1 є, очевидно, лінійними і монотонними. Застосування теореми Поста завершує доведення.

2.3.5 Передповні класи

Замкнені класи, відмінні від порожнього класу і від множини всіх булевих функцій , називають власними замкненими класами.

Власний замкнений клас називають передповним, якщо він не міститься в жодному замкненому класі, відмінному від самого себе і від класу всіх булевих функцій. Розглянемо тепер дскілька систем функцій (див. табл. 7).

Таблиця 7

I	0	+ + +	- + +	- - +	+ + +	+ - +
II	1	- + +	+ + +	- - +	+ + -	+ - +
III		-	-	+	-	-
IV	0 1	+ - +	- + +	- - -	+ + +	+ + -
V	0 1	+ - +	- + -	- - -	+ + -	+ + +

Всі системи I-V неповні, оскільки для кожної з них у табл. 7 є стовпець, який повністю складається з плюсів. Зазначимо, що в кожній системі є точно один такий стовпець і в різних системах ці стовпці різні. Звідси випливає, що в умові теореми Поста не можна відкинути жодного з п'яти класів. Справді, для кожного із класів можна вказати систему функцій, яка в ньому міститься (а отже неповна), і в якій для кожного із решти чотирьох класів є функція, яка йому не належить.

Теорема 20. Жоден із класів ,М не міститься в іншому.

Доведення. Якщо який-небудь із перелічених класів містився б в іншому, то у формулюванні теореми Поста цей клас можна було б відкинути, що суперечить попереднім міркуванням.

Теорема 21. Будь-який власний замкнений клас міститься в одному з класів .

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

Теорема 22. Замкнені класи є передповними і інших передповних класів немає.

Доведення. За теоремою 21 інші замкнені класи не можуть бути передповними. За теоремою 20 кожний із п'яти перелічених класів є передповним.

2.4. Мінімізація булевих функцій

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

Розглянемо спрощення диз'юнктивних нормальних форм. За принципом двоїстості із методів спрощення ДНФ можна отримати методи спрощення КНФ.

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

Елементарну кон'юнкцію називають імплікантою булевої функції , якщо на довільному наборі значень змінних, на якому перетворюється в 1, значення функції також дорівнює 1. Іншими словами, - імпліканта функції якщо функція тотожно дорівнює 1 (тобто виключено випадок ) Тут -деякі змінні з множини {х_х,...^_п}.

Приклад 25. Елементарна кон'юнкція є імплікантою функції , оскільки у разі значення функції обов'язково дорівнюватиме 1.

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

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

Теорема 23. СДНФ булевої функції задає цю функцію, тобто .

Доведення. Якщо , то ,очевидно, не має жодної простої імпліканти. Але диз'юнкція порожньої множини дорівнює 0.

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

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

Отже, значення та на будь-якому наборі значень змінних збігаються.

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

Зв'язок між мінімальною і скороченою ДНФ дає наступна теорема.

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

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

Диз'юнктивну нормальну форму Т, яка задає функцію (отже, ) називають тупиковою ДНФ цієї функції, якщо:

1) кожна елементарна кон'юнкція з Т є простою імплікантою ;

2) вилучення з Т довільного диз'юнктивного члена приводить до ДНФ , яка не задає , тобто .

Теорема 25. Мінімальна ДНФ булевої функції є її тупиковою ДНФ.

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

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

Із теореми 24 та 25 випливає, що знаходження мінімальної ДНФ можна виконати у два етапи.

Перший етап полягає у побудові скороченої ДНФ.

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

2.5 Методи побудови скороченої ДНФ

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

неповне склеювання ;

поглинання (члена ) ,

де -елементарна кон'юнкція, -змінна. Кажуть, що члени та склеюються по и і в результаті дають . Склеювання називають неповним, оскільки члени та залишаються у правій частині.

Алгоритм Куайна.

Крок 1. Булеву функцію , яку потрібно мінімзувати, записати у досконалій ДНФ, позначити її . Виконати

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

Крок 3. Виконати і:=і+1 і перейти до кроку 2.

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

Алгоритм Куайна обґрунтовує така теорема.

Теорема 26. Для будь-якої булевої функції результатом застосування алгоритму Куайна до досконалої ДНФ цієї функції є скорочена ДНФ функції .

Приклад 25. Побудуємо скорочену ДНФ для булевої функції, яку задано досконалою ДНФ:

.

Виконаємо і:=0. Застосовуючи неповне склеювання до членів 1та 2, 2 та 5, 3 та 4, 4 та 5, одержимо

.

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

.

Виконаємо і:=1. Оскільки жодне неповне склеювання не може бути застосоване, то дістали кінцевий результат і - скорочена ДНФ.

Мак-Класкі (МсСluskey) удосконалив алгоритм Куайна.

Алгоритм Мак-Класкі.

Крок 1. Булеву функцію, яку потрібно мінімізувати, записати у досконалій ДНФ.

Крок 2. Упорядкувати змінні й записати їх у кожній елементарній кон'юнкції у вибраному порядку. Після цього зобразити кожну елементарну кон'юнкцію послідовністю з 1, 0 та - (риска). На і-й позиції записати 1, якщо і-а змінна входить до елементарної кон'юнкції без заперечення, 0, якщо входить із запереченням, і риску, якщо зовсім не входить. Наприклад, елементарні кон'юнкції , , записують, відповідно, у вигляді 111-, 1-0-, 1--0.

Крок 3. Розбити двійкові вирази, які відповідають елементарними кон'юнкціям, на класи за кількістю одиниць, і розташувати списки цих класів у порядку зростання кількості одиниць. Для досконалої ДНФ

із прикладу 25 отримаємо писок із п'яти елементів, розбитих на три класи.

Крок 4. Виконати всі можливі склеювання . Склеювання можна застосувати лише до елементів списку, які містяться у сусідніх класах. Елементи, які склеюють, знаходять у сусідніх класах проспим порівнянням: ці елементи повинні відрізнятись точно в одній позиції і в цій позиції не повинна бути риска (-).

Якщо помістити до одного класу всі , які були отримані із двох сусідніх класів, то на наступному кроці знову доведеться порівнювати лише елементи із сусідніх класів. Елементи, які беруть участь склеюванні, позначити *; надалі вони не залишаться у списку простих імплікант. Попередній список після обробки виглядатиме так:

Непозначеними * залишились 4 елементи: 01-; 10-; -11; 1-1. Отже, множина всіх простих імплікант функції

є такою: , а її скорочена ДНФ- .

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

Метод Блейка заснований на застосуванні рівносильної і узагальненого склеювання:

,

де А, В,С- довільні формули.

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

Доведемо рівносильність узагальненого склеювання, використовуючи закони алгебри Буля:

Теорема 27. Якщо в будь-якій ДНФ булевої функції виконати