§3. Реалізація булевих функцій формулами

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

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

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

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

Таблиця 5

	1		2		3
0	0	0	1	1	1	0
0	0	1	1	1	1	1
1	0	0	0	0	0	0
1	1	1	1	0	1	1

З таблиці 5 видно, що формула реалізує функцію .

Приклад 3. Дано функції , . Написати таблицю функції .

Розв’язання. Спочатку запишемо таблицю функцій та (табл. 6).

Таблиця 6.

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

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

Таблиця 7.

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

Отже . Легко перевірити, що .

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

Деякі основні еквівалентності:

– комутативні закони

– асоціативні закони

– дистрибутивні закони

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

– тотожності з константами

– закони поглинання

– закони де Моргана

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

– закон протиріччя

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

– правило викреслювання

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

Розв’язання. Побудуємо таблицю істинності функції, але дещо в іншому вигляді (табл. 8). Спочатку йтимуть стовпці зі значеннями змінних, після них – стовпці з результатами виконаних операцій.

Таблиця 8.

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

продовження таблиці 8.

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

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

; ;

; .

Отже, – фіктивна змінна.

Оскільки , то – істотна змінна.

Нерівність показує, що – також істотна змінна.

Тепер перетворимо формулу до вигляду, що не містить фіктивної змінної:

.