Курсова робота: Системи булевих функцій
Зміст
1. Повні системи булевих функцій
2. Скорочені й тупикові диз'юнктивні нормальні форми
3. Алгоритм Квайна й Мак-Класки мінімізації булевої функції
4. Геометричне подання логічних функцій
5. Геометричний метод мінімізації булевої функції
6. Мінімізація булевої функції за допомогою карти Карно
7. Побудова оптимальних контактно-релейних схем
Бібліографічний список
1. Повні системи булевих функцій
Нагадаємо, що булевої функцією називають функцію
, у якої всі незалежні аргументи 
й сама функція є логічними змінними, приймаючими тільки два значення: 0 і 1. Ці функції можуть бути задані аналітично у вигляді формули (ПФ) геометрично або за допомогою таблиць істинності. Наприклад, всі елементарні булеві функції двох змінних представлені таблицею істинності 1.Таблиця 1
| № | X1= 0 X2= 0 | 0 1 | 1 0 | 1 1 | fk (X1, X2) |
| | 0 | 0 | 0 | 0 | f1 = 0 |
| | 0 | 0 | 0 | 1 |  |
| | 0 | 0 | 1 | 0 |  |
| | 0 | 0 | 1 | 1 |  |
| | 0 | 1 | 0 | 0 |  |
| | 0 | 1 | 0 | 1 |  |
| | 0 | 1 | 1 | 0 |  |
| | 0 | 1 | 1 | 1 |  |
| | 1 | 0 | 0 | 0 |  |
| | 1 | 0 | 0 | 1 |  |
| | 1 | 0 | 1 | 0 |  |
| | 1 | 0 | 1 | 1 |  |
| | 1 | 1 | 0 | 0 |  |
| | 1 | 1 | 0 | 1 |  |
| | 1 | 1 | 1 | 0 |  |
| | 1 | 1 | 1 | 1 |  |
Функція f1 називається нульовою; f16 - одиничною; f2 - кон'юнкцією; f8 - диз'юнкцією; f11 і f13 - запереченнями Х1 і Х2 відповідно; f12 і f14 - імплікаціями; f3 і f5 - коімплікаціями; f10 - еквівалентцією; f7 - додаванням по модулі дві або розділова диз'юнкції; f9 - стрілки Пірса (функцією Вебба); f15 - штрихом (функцією) Шеффера.
Функцію, отриману з елементарних шляхом перенумерації аргументів і підстановки замість аргументів у деяких інших булевих функцій, називають суперпозицією функцій. Неважко переконатися, що будь-яка булева функція від n аргументів є суперпозицією елементарних функцій, заданих табл.1. Наприклад, функція
є суперпозицією елементарних функцій: заперечення, диз'юнкції, імплікації.Система булевих функцій називається повної, якщо будь-яка булева функція є суперпозицією цих функцій.
В останньому стовпці таблиці 1 показано, що всі елементарні функції двох змінних, отже, і будь-які булеві функції, можуть бути записані за допомогою трьох логічних операцій
. Тому справедливо наступну теоремуТеорема. Заперечення, диз'юнкція й кон'юнкція утворять повну систему булевих функцій
Цей набір булевих функцій найбільш зручний для побудови складних булевих функцій і найчастіше використовується в додатках, однак він не є мінімальним і може бути ще скорочений.
Повна система булевих функцій називається базисом, якщо вона перестає бути повної при видаленні хоча б однієї із цих функцій.
Відповідно до цього визначення система булевих функцій
не є базисом. Дійсно, застосовуючи закони де-моргана 
, 
, кон'юнкцію в булевої функції можна замінити на диз'юнкцію й заперечення, а диз'юнкцію - на кон'юнкцію й заперечення. Отже, заперечення й диз'юнкція (заперечення й кон'юнкція) також утворять повну систему булевих функцій. Неважко переконатися, що набори 
і 
є базисними, тому що їхнє подальше скорочення без порушення повноти системи неможливо.Для перевірки повноти заданої системи булевих функцій може бути використане наступне очевидне твердження:
Якщо система
- повна й кожна з функцій f1, f2,.,fm може бути виражена за допомогою суперпозицій через функції g1, g2,…,gk, те система 
також повна.Приклад 1. Довести повноту системи
.Для доказу скористаємося системою
, повнота якої вже доведена, ці функції можна виразити через g1 і g2 по формулах:f1=g1,
,отже система функцій
є повною.У загальному випадку для перевірки повноти системи булевих функцій використовується критерій повноти Поста. Перш ніж його сформулювати, нагадаємо деякі визначення [3].
Функція f = (Х1, Х2,., Хn) називається функцією, що зберігає константу 0 (1), якщо
f (0,0,.0) = 0, (f (l, 1.1) = 1).
Функція f (X1,X2,.,Xn) називається самодвоїстої, якщо
f (X1,X2,., Xn) =
.Функція f (X1,X2,.,Xn) називається монотонної, якщо для будь-яких двох наборів X = (X1,X2,…,Xn) і Y = (Yl, Y2,.,Yn), таких, що X
Y (для будь-якого i Xi Yi) має місце нерівність:f (X1,X2,., Xn)
f (Yl, Y2,.,Yn).Функція f (X1,X2,., Xn) називається лінійної, якщо
f (X1,X2,., Xn) =
,де
.Перші чотири властивості перевіряються за допомогою таблиці істинності, а для перевірки лінійності функції необхідно побудувати багаточлен Жегалкина. Наприклад, з табл.1 треба, що f2 = X1X2 і f8 = X1X2 - функції, що зберігають константу 0; f10 = X1↔X2 - функція, що не зберігає константу 0, але яка збірегає константу 1; f7 = X1
X2 - функція; f2, fg - монотонні функції; f14 = X1→X2 - немонотонна функція, тому що монотонність порушується (0, 0) і (1, 0); f3 - нелінійна функція, тому що відповідний їй багаточлен Жегалкина X1 + X2 + X1X2 - нелінійна.Теорема Поста. Система D = {f1, f2,. fm} булевих функцій є повною тоді й тільки тоді, коли серед функцій цієї системи існують: функція, що не зберігає константу 0, функція, що не зберігає константу 1, а також нелінійна, й немонотонна функції.
Приклад 2. Довести повноту системи
.Рішення. Нехай K0 - клас функцій, що зберігають константу 0; К1 - клас функцій, що зберігають константу 1; Кл, Kc, Км - класи лінійних, самодвоїстих і монотонних функцій відповідно.
Складемо таблицю Поста наступного виду.
Таблиця 2
| № | φi | K0 | К1 | Кл | Kc | Км |
| 1 | X1 X2 | + | - | + | - | - |
| 2 | X1 X2 | + | + | - | - | + |
| 3 | 1 | - | + | + | - | - |
Знак "+", щокоштує на перетинанні i - й рядка й j-гo стовпця цієї таблиці, показує, що функція φi - належить відповідному класу, записаному в j-ом стовпці,
З табл.1 бачимо, що φ1 = f7не зберігає константу 1 і не є монотонної, φ2=f8 - нелінійна й функція, φ3 = f16 не зберігає константу 0. Отже, всі умови теореми Поста виконані, і задана система
є повною.Приклад 3. Довести, що система {|} є базисом.
Рішення. Розглянута система складається з однієї функції f15 (функції Шефера). З табл.1 бачимо, що f15 - функція, що не зберігає 0 і 1, немонотонна (монотонність порушується на наборах (1, 0) і (1, 1),, тому що
, a двоїста функція 
нелінійна, тому що багаточлен Жегалкина для цієї функції має вигляд: 1 + X1X2. Отже, система {f15} = {|} задовольняє всім умовам теореми Поста і є базисом.Таким чином, для аналітичного завдання булевої функції можна використовувати різні мови формул. Критерієм повинен служити характер розглянутої задачі.
1 2 3 4 5 6