Лекція. Алгебра логіки
Крім звичайної алгебри існує спеціальна, основи якої були закладені англійським математиком XIX століття Дж. Булем. Ця алгебра займається так званим обчисленням висловлювань.
Її особливістю є можливість застосування для опису роботи так званих дискретних пристроїв, до числа яких належить цілий клас пристроїв автоматики і обчислювальної техніки.
При цьому сама алгебра виступає в якості виробу. Це означає, що робота довільного пристрою зазначеного типу може бути лише в якомусь відношенні описана за допомогою побудов цієї алгебри. Дійсне реальний пристрій фізично працює не так, як це описує алгебра логіки. Проте застосування положень цієї теорії дозволяє зробити ряд корисних в практичному відношенні узагальнень.
Розглянемо деяку схему і представимо її у вигляді так званого "чорного" ящика.
Будемо вважати, що внутрішній вміст ящика невідомо.
X 1, X 2, X 3 - вхідні сигнали, F - вихідний сигнал.
Вважаємо також, що схема А - елементарна, тобто немає іншої схеми Б, меншою, ніж А, яка б містилася в А.
Побудуємо абстрактне пристрій з елементарних пристроїв, типу А, Б, В і т.д. Очевидно, більш складний пристрій можна побудувати з простих шляхом:
послідовного з'єднання елементів;
паралельного з'єднання;
перестановки входів елементів.
Тоді роль Y 1 для другого елементу Б буде грати:
Y 1 = F А (X 1, X 2, X 3)
Y 2 = F Б (X 1, X 2)
F = F (Y 1, Y 2) = F (F А (X 1, X 2, X 3), F Б (X 1, X 2))
Паралельне з'єднання елементів не змінює функції, тому, з точки зору логіки, цей тип з'єднання не використовується. Фізично іноді все ж застосовують паралельне з'єднання елементів, але в основному для того, щоб, наприклад, посилити сигнал.
У зв'язку з цим, паралельне з'єднання елементів в алгебрі логіки не розглядається.
Функція, яку виконує елемент, взагалі кажучи, залежить від змінних, які подаються на вхід.
Тому перестановка аргументів впливає на характер функції.
F = F (F А (X 1, X 2, X 3), F Б (X 2, X 3))
F (F Б (X 2, X 3), F А (X 1, X 2, X 3))
Таким чином, довільні, як завгодно складні в логічному відношенні схеми, можна будувати, використовуючи два прийоми:
послідовне з'єднання елементів;
перестановка входів елементів.
Цим двом фізичним прийомам в алгебрі логіки відповідають:
принцип суперпозиції (підстановка у функцію замість її аргументів інших функцій);
підстановка аргументів (зміна порядку запису аргументів функцій або заміна одних аргументів функції іншими).
Отже, фізична задача побудови і аналізу роботи складного пристрою замінюється математичної завданням синтезу і аналізу відповідних функцій алгебри логіки.
Елементарні функції алгебри логіки
Існує кілька синонімів по відношенню до функцій алгебри логіки:
функції алгебри логіки (ФАЛ);
перемикальні функції;
Булевського функції;
виконавчі функції.
У міру необхідності будемо користуватися всіма цими синонімами.
Розглянемо деякий набір аргументів:
<X 1 ,X 2 ,X 3 ,...Х i ,...X n>
і будемо вважати, що кожен з аргументів приймає тільки одне з двох можливих значень, незалежно від інших
Чому дорівнює число різних наборів?
X i = {0, 1}
Поставимо кожному набору у відповідність деякий двійкове число:
X 1, X 2 ,........... X n
0, 0 ,..........., 0 нульової набір
0, 0 ,..........., 1 перший набір
0, 0 ,.......... 1,0 другий набір
...................
1, 1 ,..........., 1 (2 n -1)-ий набір
Очевидно, що кількість різних X 1, X 2 ,........... X n n-розрядних чисел в позиційній двійковій системі є 2 n.
Припустимо, що деяка функція F (X 1, X 2 ,.... X n) задана на цих наборах і на кожному з них вона приймає або '0'-е, або '1'-е значення.
Таку функцію називають функцією алгебри логіки або перемикальної функцією.
Чому дорівнює число різних перемикальних функцій 'n' аргументів?
Оскільки функція на кожному наборі може прийняти значення '0' або '1', а найбільше різних набору 2 n, то загальне число різних функцій 'n' аргументів є: 2 2n.
У порівнянні з аналітичною функцією безперервного аргументу навіть для одного аргументу існує безліч різних функцій.
Число аргументів | 1 | 2 | 3 | 4 | 5 | 10 |
Число різних перекл. ф-цій | 4 | 16 | 256 | 65536 | ~ 4 * 10 9 | ~ 10 300 |
Різні пристрої ЕОМ містять десятки і сотні змінних (аргументів), тому зрозуміло, що кількість різних пристроїв, що відрізняються один від одного, практично нескінченно.
Отже, потрібно навчитися будувати ці складні функції (а отже, і пристрої), а також аналізувати їх.
Завдання синтезу більш складних функцій полягає в поданні їх через прості на основі операцій суперпозиції і підстановки аргументів. |
Таким чином, спочатку необхідно вивчити ці елементарні функції, щоб на їх основі будувати більш складні.
ФАЛ одного аргументу
Щоб задати ФАЛ, потрібно задати її значення на всіх наборах аргументів.
Аргумент Х | значення | Найменування функції | |
0 | 1 | ||
F 0 (x) | 0 | 0 | константа '0' |
F 1 (x) | 0 | 1 | змінна 'х' |
F 2 (x) | 1 | 0 | інверсія 'х' (заперечення х) |
F 3 (x) | 1 | 1 | константа '1' |
Будемо у функції ставити індекс, еквівалентний набору її значень для відповідних значень аргументу, починаючи з 0,0 ,...., 0 ,..... і т.д. в порядку зростання.
Ці функції можна реалізувати на 4-х елементи, кожен з яких має максимум один вхід. Таким чином, принципом підстановки аргументів для побудови більш складних функцій не можна скористатися.
Необхідно розглянути більш складні функції, тобто ФАЛ 2х аргументів.
Дамо такі визначення:
ФАЛ, що приймають однакові значення на всіх наборах аргументів, називаються рівними.
ФАЛ істотно залежить від аргументу Х i, якщо
F (X 1, X 2 ,..., Х i-1, 0, X i +1 ,..., X n)
F (X 1, X 2 ,..., Х i-1, 1, X i +1 ,..., X n)
В іншому випадку вона залежить не суттєво, а відповідний аргумент зв. фіктивним.
Наприклад:
Х 1 | Х 2 | Х 3 | F (X 1, X 2, Х 3) |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
Видно, що Х 3 - фіктивний аргумент. Це показує, що у функцію можна ввести будь-яке число фіктивних аргументів, від яких вона суттєво не залежить. Цей прийом надалі буде потрібно для виконання низки перетворень.
Всі ФАЛ від 2-х аргументів. Зведемо їх в єдину таблицю 2.1.
Таблиця 2.1. | ||||||
№ функції | Значення функції на наборах логічних змінних | Найменування функції | Позначення функції | |||
X 1 | 0 | 0 | 1 | 1 | ||
X 2 | 0 | 1 | 0 | 1 | ||