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

ТЕМА 4.1 БУЛЕВА АЛГЕБРА

Розділ 4.

Визначення 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}.

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

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

Таблиця 4.1

x 1 x 2 x 3	f (x 1, x 2, x 3)
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

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

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

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

Таблиця 4.2

x	Ø x

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

Таблиця 4.3

x 1 x 2	x 1V x 2	x 1& x 2	x 1 x 2	x 1~ x 2	x 1 Å x 2	x 1¯ x 2	x 1ï x 2
0 0 0 1 1 0 1 1		0	1	1

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-10-17