Булева функція

Бу́лева фу́нкція (функція алгебри логіки, логічна функція) — в дискретній математиці відображення Bⁿ → B, де B = {0,1} — булева множина.

Bⁿ — множина всіх можливих послідовностей з 0 та 1 довжини n.

Булева функція задається у вигляді таблиці, або графіка зі стандартним (лексикографічним) розташуванням наборів аргументів.

В стандартному розташуванні набори можна розглядати як двійкові записи цілих чисел від 0 до $2^n - 1$ . Функцію, задану зі стандартним розташуванням наборів, можна ототожнити з набором довжини $2^n$ .

Очевидно, що множина всіх можливих наборів довжини $2^n$ , тобто множина n-арних булевих функцій, складається з $2^{2^n}$ елементів. При n=0 це 2, при n=1 — 4, при n=2 — 16, при n=3 — 256 тощо.

Нуль-арними булевими функціями є сталі 0 і 1.

Функції 0 і 1 називаються тотожними нулем і одиницею, функція x — тотожною, $\overline x$ — запереченням. Замість виразу $\overline x$ вживається ще вираз $\neg x$ . Ці вирази читаються як «не x».

Подамо також деякі з 16 бінарних функцій разом із їх позначеннями:

Функція, позначена виразом $x \wedge y$ , називається кон'юнкцією і позначається ще як x&y, $x\cdot y$ або xy. Усі ці вирази читаються як «x і y».

Зауважимо, що інфіксні позначення наведених функцій вигляду x f y, де f — відповідний знак, склалися історично. Їх так само можна позначати й у вигляді f(x, y), наприклад, $\vee(x, y)$ .