Минимизация булевых функций и полнота систем

Булева функция — это отображение множества $\{0,1\}$ в само себя. Её можно представить таблицей истинности или формулой с использованием операций конъюнкции ($\wedge$), дизъюнкции ($\vee$) и отрицания ($\neg$).

Один из методов минимизации булевых функций — использование карты Карно. Это таблица, разделённая на клетки, каждая из которых соответствует определённой комбинации переменных.

$$f(x_1,x_2) = \overline{x_1} x_2 + x_1 \overline{x_2}$$

Пример карты Карно для двух переменных: `` x1\x2 | 00 | 01 | 11 | 10 ------|----|----|----|---- 0 | 0| 0| 1| 1 1 | 0| 1| 1| 0 ``

Полной системой называют набор булевых функций, позволяющий выразить любую другую булеву функцию через комбинации этих функций.

Изучение минимизации булевых функций и полноты систем позволяет эффективно решать задачи криптографии, защиты информации и автоматизации вычислений.