Визначення булевої функції

Визначення 4.1. Булевою функцією f(x₁, x₂, ... , x_n) називається довільна функція n змінних, аргументи якої x₁, x₂, ... , x_n і сама функція f приймає значення 0 або 1, тобто x_i {0, 1}, i = 1, 2, ... , n; f(x₁, x₂, ... , x_n) {0, 1}.

Будь-яка булева функція може бути представлена таблицею, у лівій частині якої перераховані всі набори змінних (їх 2ⁿ), а в правій частині – значення функції. Приклад такого завдання представлений у таблиці 4.1.

Таблиця 4.1

Для формування стовпця значень змінних зручний лексико-графічний порядок, відповідно до якого кожен наступний набір значень виходить із попереднім додатком 1 у двійковій системі числення, наприклад, 100 = 011+ 1.

Всього існує 2² різних булевих функцій n змінних.

Функцій однієї змінної – 4. З них виділимо функцію “заперечення x”(позначається Øx). Ця функція представлена в таблиці 4.2.

Таблиця 4.2

Булевих функцій двох змінних – 16 (2² при n = 2). Ті з них, які мають спеціальні назви, представлені в таблиці 4.3.

Таблиця 4.3

x1 x2	x1Vx2	x1& x2	x1 x2	x1~x2	x1 Å x2	x1¯ x2	x1ï x2
0 0 0 1 1 0 1 1		0	1	1

У таблиці 4.3 представлені наступні функції двох змінних:

x₁Vx₂ – диз’юнкція;

x₁& x₂ – кон’юнкція;

x₁Éx₂ – імплікація;

x₁~x₂ – еквівалентність;

x₁Å x₂ – додавання по модулі 2;

x₁¯x₂ – стрілка Пірса;

x₁ï x₂ – штрих Шеффера.

Інші функції спеціальних назв не мають і можуть бути виражені через перераховані вище функції.