Розділ 1 ФУНКЦІЇ АЛГЕБРИ ЛОГІКИ ТА ЇХ ОСНОВНІ ВЛАСТИВОСТІ

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

1.1 Основні поняття теорії елементарних функцій алгебри логіки

Функцію , яка набуває тільки значення 0 або 1, як і її аргументи, прийнято називати логічною функцією або булевою функцією. Аргументи булевої функції також називають булевими.

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

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

В табл. 1.1 задані дві логічні функції трьох аргументів і .

Таблиця 1.1

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	0	1	0	0	0	1
1	0	0	1	0	1	1	0

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

а) будь-яка логічна функція n аргументів визначена на наборах.

Відомо, що кількість різних n-розрядних чисел дорівнює , якщо кожному набору аргументів можна поставити у відповідність двійкове n-розрядне число. Так, наприклад, подані в табл. 1.1 логічні функції визначені на 8 наборах: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1);

б) число різних логічних функцій n аргументів скінченне і дорівнює .

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

в) кількість логічних функцій n аргументів різко зростає зі збільшенням n (табл. 1.2).

Таблиця 1.2

Кількість аргументів	1	2	3	4	5
Число переми-каючих функцій	4	16	256	65536	4,3Ч10⁹

Логічна функція одного аргументу подана в табл. 1.3.

Таблиця 1.3

0	1	Умовне позначення	Найменування функції
0	0	0	Константа нуля
0	1		Змінна
1	0		Інверсія
1	1	1	Константа одиниці

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

Таблиця 1.4

Функція	0 0	0 1	1 0	1 1	Назва функції	Позна-чення	Функція, що виконується
	0	0	0	0	константа нуль	0
	0	0	0	1	Добуток (кон’юнкція)
	0	0	1	0	f заборона по y
	0	0	1	1	змінна х		X
	0	1	0	0	f заборона по х
	0	1	0	1	змінна y		Y
	0	1	1	0	сума за модулем 2
	0	1	1	1	диз’юнкція
	1	0	0	0	операція Пірса (функція Вебба)
	1	0	0	1	логічна рівнозначність	~
	1	0	1	0	інверсія y
	1	0	1	1	імплікація від у до х
	1	1	0	0	інверсія х
	1	1	0	1	імплікація від х до у
	1	1	1	0	операція Шеффера (штрих Шеффера)
	1	1	1	1	константа одиниці	1

Існує 16 різних логічних функцій двох аргументів ( і ), кожна з яких визначена на 4-х наборах.

З 16-ти функцій, які подані в табл. 1.4, 6 функцій

;

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

Функція називається кон’юнкцією, логічним множенням або логічним І. Для її позначення використовуються: знак множення Ч - ; знак кон’юнкції Щ - ; знак логічного І - & - .