3. Булеві функції однієї та двох змінних

Булеві функції однієї та двох змінних можна легко полічити.

Функції однієї змінної:

, , , ; (1)

Функції двох змінних:

, , ,

, , ,

, , ,

, , ,

, , ,

. (2)

Порівнюючи визначення функцій (1,2) і логічних операцій (0, 1, …, 11, п. 1) можна прийти до висновку, що булеві функції однієї та двох змінних можна подати первинними логічними формулами:

; , , ; (3)

; ; ; ;

; ; ; ;

; ; ; ;

; ; ; . (4)

З огляду на це булеві функції однієї та двох змінних називають відповідною операцією:

– константа 0;

– повторення аргументу;

– заперечення аргументу,

– константа 1;

– константа 0;

– кон’юнкція;

– заперечення імплікації;

– повторення аргументу ;

– заперечення зворотної імплікації;

– повторення аргументу ;

– сума за модулем 2;

– диз’юнкція;

– стрілка Пірса;

– еквівалентність;

– заперечення другого аргументу ;

– зворотна імплікація;

– заперечення першого аргументу ;

– імплікація;

– штрих 4улевих;

– константа 1.

Булеві функції однієї та двох змінних можна подати і складними логічними виразами.

Приклад 1.; .

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

Приклад 2.

Логічний вираз визначає одну булеву функцію. Обернене твердження не правильне. Будь-яка логічна функція може бути подана багатьма формулами (теоретично необмеженою кількістю). Формули, які визначають одну і ту саму функцію називаються рівносильними. Рівносильні формули з′єднуються знаком рівності (=).

Практичне заняття 1

Вправа 1. Записати таблицю істинності булевих функції за її номером.

Виконання. Задана функція має чотири аргументи. Кількість слів . Номер функції .

.

Вправа 2. Булева функція з невідомим номером k задана таблицею істинності

.

Знайти номер k цієї функції.

Виконання. .

Вправа 3. Встановити номер 5улевих функції заданої логічною формулою.

Виконання.

.

В підсумку .

Варіанти для самостійної роботи.

Номер варіанту	Вправа 1	Вправа 2	Вправа 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4. Системи базових (елементарних) операцій

З визначення булевих функцій (2, п. 3) можна переконатися в справедливості рівностей

(1)

На підставі цього можна для логічних операцій (а значить і для логічних функцій) записати такі тотожності:

, ; (2)

; (3)

, ; (4)

, ; (5)

, ; (6)

, . (7)

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

Прикладом (одним із найважливіших) систем елементарних операцій є

(8)

Ця система елементарних операцій є надлишковою. Це випливає з того, що справедливими є такі співвідношення

, (9)

, (10)

Ці рівності доводяться з використанням таблиці істинності:

Таким чином з врахуванням рівностей (9) і (10) можна дійти висновку, що система елементарних операцій (8) може бути скорочена (наприклад) до

( (11)

Система елементарних операцій (11) має значні зручності і широко використовуються на практиці. Проте і вона є надлишковою. Це випливає із справедливості рівностей

, (12)

. (13)

Тому систему елементарних операцій (11) можна скоротити до

, (14а)

або

. (14б)

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

, (15)

, (16)

, (17)

з них випливає, що системи (14а) і (14б) можуть бути скорочені до

(18)

або

. (19)

Втім, особливого практичного значення останнє не має.

При обчисленні значень формул з операціями (8) необхідно врахувати їх пріоритети:

2. заперечення ;

3. кон’юнкція

4. диз’юнкція

5. імплікація

6. еквівалентність

(першими виконуються операції з меншим порядком (більшим пріоритетом) у цьому списку).

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

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

Приклад 1. Обчислити значення виразу при , , , .

Виконання:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .