- •Розділ 1. Математичні основи синтезу логічних схем
- •1.1. Деякі поняття і визначення булевої алгебри
- •1.2. Способи задання булевих функцій
- •1.3. Булеві функції від однієї і двох змінних
- •1.4. Принцип суперпозиції логічних функцій. Пріоритет операцій
- •1.5. Аксіоми та закони булевої алгебри
- •Аксіоми кон’юнкції, диз’юнкції і заперечення:
- •1.7. Аксіоми та закони алгебри Жегалкіна
- •1. Комутативний закон
- •2. Сполучний закон
- •3. Розподільний закон по відношенню до додавання за модулем 2
- •1.8. Аксіоми та закони для функцій Шеффера та Пірса
- •1.9. Аналітичне подання булевих функцій
- •1.10. Класи булевих функцій. Теорема про повноту
- •1.11. Розвинення логічних функцій за змінними
- •1.12. Зв’язок між дднф і дкнф. Канонічні нормальні форми
Аксіоми кон’юнкції, диз’юнкції і заперечення:
1. ; 1. 0 0 = 0; 1. 0 0 = 0;
2. . 2. 0 1 = 0; 2. 0 1 = 1;
3. 1 0 = 0; 3. 1 0 = 1;
4. 1 1 = 1; 4. 1 1 = 1;
Закони булевої алгебри випливають із аксіом і також мають дві форми вираження: для кон’юнкції і для диз’юнкції.
1. Комутативні закони
а) ; б) .
2. Сполучні закони
а) ; б) .
3. Розподільні закони
а) ; б)
4. Закони поглинання
а) ; б) .
5. Закони склеювання
а) ; б) .
6. Закон подвійного заперечення
.
7. Закони де Моргана
а) ; б)
або після інвертування лівих і правих частин:
в) ; г) .
Зауважимо, що закони де Моргана є дійсними для будь-якої кількості змінних:
; .
8. Закони ідемпотентності
а) ; б) .
9. Закони універсальної множини
а) ; б) .
10. Закони нульової множини
а) ; б) .
11. Закони доповнення
а) ; б) .
Правильність наведених законів легко доводиться за допомогою викладених вище аксіом або шляхом побудови таблиці істинності.
Доведемо, наприклад, справедливість розподільного закону (випадок б):
Спочатку виконаємо доведення скориставшись аксіомами:
.
Доведемо шляхом побудови таблиці істинності. Для цього побудуємо таблиці істинності для виразів, які знаходяться в лівій і правій частинах рівності. Результати обчислень наведено в табл. 9.
Таблиця 9
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Співпадання значень у виділених стовпцях табл. 9 доводить справедливість рівності.
Аналогічно можна довести інші закони.
Із комутативного і асоціативного законів для диз’юнкції (кон’юнкції) випливає, що диз’юнкція (кон’юнкція) декількох змінних може виконуватись послідовно, причому порядок обчислення диз’юнкції не впливає на результат. Це дає можливість сформулювати такі правила:
1. Якщо в логічному добутку (кон’юнкції), що містить не менше двох співмножників, один із співмножників дорівнює нулю, то логічний добуток дорівнює нулю.
2. Якщо в логічному добутку, що містить не менше двох співмножників, є співмножник, який дорівнює одиниці, то цей співмножник можна вилучити.
3. Якщо в логічній сумі (диз’юнкції), що містить не менше двох доданків, є доданок, який дорівнює нулю, то цей доданок можна вилучити.
4. Якщо в логічній сумі, один із доданків дорівнює одиниці, то ця сума дорівнює одиниці.
Приклад 2. а) Довести, що Маємо
б). Довести, що . Маємо
в) Довести, що . Маємо
г) Довести, що . Маємо
.
1.6. Двоїстість
Означення 1. Логічна функція називається двоїстою до функції , якщо .
Означення 2. Функція, двоїста сама до себе, тобто , називається самодвоїстою.
Правило побудови двоїстої функції. Для запису функції , двоїстої до функції , треба у функції всюди 0 замінити на 1, 1 – на 0, знак – на , а знак – на . Наведене правило побудови двоїстих функцій називається принципом двоїстості.
Приклад 3. Нехай, задано логічну функцію . Побудувати функцію двоїсту до заданої.
Розв’язання. а) Виходячи з означення двоїстості та застосувавши правило де Моргана два рази, одержимо
.
б) Скориставшись правилом побудови двоїстих функцій (принципом двоїстості) зразу одержимо, що .
Легко переконатись, що таблиця істинності двоїстої функції одержується з таблиці істинності для функції шляхом інвертування (заміною значень 0 на 1 та 1 на 0) значень функції й записом стовпчика інвертованих значень функції у зворотному порядку (див. два останні стовпці табл. 10)
Таблиця 10
x |
y |
z |
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
|
1 |
0 |
0 |
|
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
|
0 |
1 |
0 |
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
|
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
|
0 |
0 |
1 |
|
0 |
1 |
На підставі законів де Моргана можна вивести таке твердження: якщо функція двоїста до функції , то справедлива тотожність
.
Таким чином, заперечення функції можна знайти або за допомогою закону де Моргана, або заміною в функції двоїстої до заданої значення всіх змінних на протилежні – на і на , де .
Логічна функція є самодвоїстою (непарною), якщо на кожній парі протилежних наборів вона приймає протилежні значення, тобто
або .
Для двох змінних такими функціями є: .
Приклад 4. Користуючись таблицею істинності вияснити чи є функція самодвоїстою.
Розв’язання. Для побудови двоїстої функції скористаємось правилом побудови двоїстих функцій. Аналізуючи таблицю істинності (табл.11) легко переконатись, що побудована функція не є самодвоїстою, тобто: , і .
Таблиця 11
x |
y |
|
|
|
|
|
|
|
0 |
0 |
1 |
1 |
1 |
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |