- Минимизация булевых функций
- Минимизация булевой функции — это процесс приведения функции к наиболее простой форме при сохранении её логического значения.
- Полнота системы булевых функций
- Система булевых функций называется полной, если с её помощью можно выразить любую булеву функцию.
- Конъюнктивная нормальная форма (КНФ)
- Функция называется конъюнктивной нормальной формой (КНФ), если она представлена в виде дизъюнкции конъюнкций литералов.
- Дизъюнктивная нормальная форма (ДНФ)
- Функция называется дизъюнктивной нормальной формой (ДНФ), если она представлена в виде конъюнкции дизъюнкций литералов.
- Литерал
- Литералом называется переменная или её отрицание.
- Метод Квайна — МакКласки
- Метод Квайна — МакКласки используется для минимизации булевых функций в ДНФ и КНФ.
- Метод Куайна
- Метод Куайна — это способ минимизации булевых функций, основанный на использовании таблиц истинности и карт Карно.
- Карта Карно
- Карта Карно — это графическое представление булевой функции, позволяющее визуально минимизировать её.
- Базис булевых функций
- Система булевых функций называется полной, если в неё входят функции $f_1(x_1, x_2) = x_1$, $f_2(x_1, x_2) = x_2$, $f_3(x_1, x_2) = x_1 \oplus x_2$.
- Функция суммирования по модулю 2
- Функция $f(x_1, x_2, \dots, x_n) = x_1 \oplus x_2 \oplus \dots \oplus x_n$ называется функцией суммирования по модулю 2.
- Функция отрицания
- Функция $f(x_1, x_2, \dots, x_n) = \neg x_1 \land \neg x_2 \land \dots \land \neg x_n$ называется функцией отрицания.
- Функция конъюнкции
- Функция $f(x_1, x_2, \dots, x_n) = x_1 \land x_2 \land \dots \land x_n$ называется функцией конъюнкции.
- Функция дизъюнкции
- Функция $f(x_1, x_2, \dots, x_n) = x_1 \lor x_2 \lor \dots \lor x_n$ называется функцией дизъюнкции.
- Функция эквивалентности
- Функция $f(x_1, x_2, \dots, x_n) = x_1 \leftrightarrow x_2 \leftrightarrow \dots \leftrightarrow x_n$ называется функцией эквивалентности.