Основи двійкової арифметики. Порозрядні логічні операції (Булівські операції)

Основні поняття

Множину {0, 1} позначимо літерою B. Множину всіх можливих послідовностей з 0 і 1 – Bn. Такі послідовності за традицією будемо називати наборами або векторами довжини n. Очевидно, Bn містить 2n елементів. Значення 0 і 1 називаються протилежними одне до одного.

Означення. Всюди визначена функція з Bn у B називається n-місною функцією алгебри логіки або n-місною бульовою функцією.

Послідовність змінних (x1, x2, …, xn) із значеннями у B позначимо . Бульова функція f( ) задається у вигляді таблиці, або графіка зі стандартним розташуванням наборів:

x1, x2, …, xnf(x1, x2, …, xn)

0, 0, …, 0, 0f(0, 0, …, 0, 0)

0, 0, …, 0, 1f(0, 0, …, 0, 1)

0, 0, …, 1, 0f(0, 0, …, 1, 0)

0, 0, …, 1, 1f(0, 0, …, 1, 1)

……

0, 1, …, 1, 1f(0, 1, …, 1, 1)

1, 0, …, 0, 0f(1, 0, …, 0, 0)

……

1, 1, …, 1, 0f(1, 1, …, 1, 0)

1, 1, …, 1, 1f(1, 1, …, 1, 1)

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

x yf(x, y)

0 01

0 10

1 01

1 11

можна ототожнити з вектором (1011).

Далі іноді будемо позначати n-місну функцію f( ) як f(n)( ), підкреслюючи кількість змінних, від яких вона залежить.

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