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

Визначення 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₁x₂x₃	f(x₁, x₂, x₃)
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₁x₂	x₁Vx₂	x₁& x₂	x₁ x₂	x₁~x₂	x₁Å x₂	x₁¯ x₂	x₁ï x₂
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₂– штрих Шеффера.

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Розділ 4.	\|	Формули логіки булевих функцій

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.006 сек.