Булевы функции от одной и двух переменных

Булевы функции от одной переменной – это отображения множества {0,1} в себя. Булевы функции от одной переменной можно рассматривать как унарные операции на множестве {0,1}. В следующей таблице приведены все четыре булевы функции от одной переменной.

x g₀(x) g₁(x) g₂(x) g₃(x)

--------------------------------

0 0 0 1 1

1 0 1 0 1

Имеем:

g₀(x)=0 – функция, тождественно равная 0 (тождественный ноль);

g₁(x)=x – тождественная функция;

g₂(x)=1–x – эта функция соответствует отрицанию и носит то же название; в теории булевых функций отрицание принято обозначать через x’, поэтому мы будем писать g₂(x)=x’;

g₃(x)=1 – функция, тождественно равная 1 (тождественная единица).

Булевы функции от двух переменных можно рассматривать как бинарные операции на множестве {0,1}. В следующей таблице приведены все шестнадцать булевых функции от двух переменных (значения аргументов и функций выписаны в строках, функции перечисляются в столбце). Для некоторых функций указаны используемые обозначения и названия.

x₁ 0 0 1 1

x₂ 0 1 0 1

-------------------------------

f₀ 0 0 0 0 0 – тождественный ноль

f₁ 0 0 0 1 ⋅ умножение, конъюнкция

f₂ 0 0 1 0

f₃ 0 0 1 1 x₁

f₄ 0 1 0 0

f₅ 0 1 0 11 x₂

f₆ 0 1 1 0 ⊕ – сложение по модулю 2

f₇ 0 1 1 1 ∨ – дизъюнкция

f₈ 1 0 0 0 ↓ – стрелка Пирса

f₉ 1 0 0 1 ↔ – эквивалентность

f₁₀ 1 0 1 0

f₁₁ 1 0 1 1 ← – обратная импликация

f₁₂ 1 1 0 0

f₁₃ 1 1 0 1 → – импликация

f₁₄ 1 1 1 0 | – штрих Шеффера

f₁₅ 1 1 1 1 1 – тождественная единица

Комбинируя перечисленные функции (с помощью суперпозиций), можно строить более сложные булевы функции, в том числе и большего числа переменных, например, xy→zt и т.п. Булевы отрицание, конъюнкция (умножение), дизъюнкция, импликация обладают свойствами, подобными тем, которыми обладают соответствующие логические операции (с естественной заменой равносильности формул на равенство функций). Например, законы де Моргана принимают следующий вид (знак умножения, как это часто делается, опущен):

(xy)’=x’∨y’; (x∨y)’=x’y’.

Кроме того, имеем:

1’=0; 0’=1;

x∨x’=1; xx’=0;

0x=0; 1x=x; 0∨x=x; 1∨x=x.

Приведем некоторые уравнения, в которых одни булевы функции выражены через другие:

x’ = x→0 = x|x = x↓x = 1⊕x;

xy = (x’∨y’)’ = x’↓y’ = (x↓x)↓(y↓y);

x∨y = (x’y’)’ = x’→y = =(x→y)→y = x’|y’ = (x|x)|(y|y);

x→y = x’∨y;

x↔y = (x→y) (y→x) = xy∨x’y’;

Все эти равенства легко проверяются с помощью таблиц.

Принцип двойственности естественным образом переносится на булевы функции. Приведем необходимые формулировки. Двойственной к булевой функции f(x,y,…,z) называется функция

f^*(x,y,…,z)=f’(x’,y’,…,z’).

Если f(x,y,…,z) представлена формулой, содержащей только конъюнкции, дизъюнкции и отрицания, то двойственная функция получается заменой в этой формуле конъюнкций на дизъюнкции, а дизъюнкций на конъюнкции. x⊕y = xy’∨x’y.