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

тригонометрическая функцияалгебраическая функцияБулева функция — это отображение из множества двоичных наборов длины 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}$$

Таблица истинности показывает соответствие значений входных переменных и выходных значений функции.

Пример таблицы истинности для функции $f(x, y) = x \wedge y$:

`` x | y | f(x,y) 0 | 0 | 0 0 | 1 | 0 1 | 0 | 0 1 | 1 | 1 ``

полином ЖегалкинаКНФДНФ представляет собой дизъюнкцию конъюнкций переменных или их отрицаний.

Например, выражение $(x \wedge y) \vee (\neg x \wedge z)$ является ДНФ.

ДНФполином ЖегалкинаКНФ представляет собой конъюнкцию дизъюнкций переменных или их отрицаний.

Например, выражение $(x \vee y) \wedge (\neg x \vee z)$ является КНФ.

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

Булевые функции широко применяются в цифровой электронике, программировании и криптографии.

таблицатистинылогическаяоперациябулевафункция