Булевы функции и алгебра логики

dlyachainikov.ru · Дискретная математика

Определение булевой функции

Булева функция — это отображение из множества двоичных наборов длины n в множество {0, 1}.
Обозначается как $f(x_1, x_2, ..., x_n)$ , где $x_i$ принимает значения 0 или 1.

Операция конъюнкции обозначается символом $\wedge$ . Результат равен 1 тогда и только тогда, когда все операнды равны 1.
$x \wedge y = \begin{cases} 1 & \text{если } x=1 \text{ и } y=1 \\ 0 & \text{иначе} \end{cases}$

Операция дизъюнкции обозначается символом $\vee$ . Результат равен 1, если хотя бы один из операндов равен 1.
$x \vee y = \begin{cases} 1 & \text{если } x=1 \text{ или } y=1 \\ 0 & \text{иначе} \end{cases}$

Операция инверсии обозначается символом $\neg$ . Она меняет значение переменной на противоположное.
$\neg x = \begin{cases} 1 & \text{если } x=0 \\ 0 & \text{если } x=1 \end{cases}$

Полином Жегалкина — это представление булевой функции с помощью операций сложения по модулю 2 ( $+$ ) и умножения ( $\cdot$ ). Например, функция $f(x, y) = x \oplus y$ может быть представлена как $x + y$

Определение булевой функции

Булева функция — это отображение из множества двоичных наборов длины n в множество {0, 1}.

Обозначается как

f(x_1, x_2, ..., x_n)

, где

x_i

принимает значения 0 или 1.

Конъюнкция (И)

Операция конъюнкции обозначается символом

\wedge

. Результат равен 1 тогда и только тогда, когда все операнды равны 1.

x \wedge y = \begin{cases} 1 & \text{если } x=1 \text{ и } y=1 \\ 0 & \text{иначе} \end{cases}

Дизъюнкция (ИЛИ)

Операция дизъюнкции обозначается символом

\vee

. Результат равен 1, если хотя бы один из операндов равен 1.

x \vee y = \begin{cases} 1 & \text{если } x=1 \text{ или } y=1 \\ 0 & \text{иначе} \end{cases}

Инверсия (НЕ)

Операция инверсии обозначается символом

\neg

. Она меняет значение переменной на противоположное.

\neg x = \begin{cases} 1 & \text{если } x=0 \\ 0 & \text{если } x=1 \end{cases}

Полином Жегалкина

Полином Жегалкина — это представление булевой функции с помощью операций сложения по модулю 2 (

+

) и умножения (

\cdot

). Например, функция

f(x, y) = x \oplus y

может быть представлена как

x + y