Введение в логику

О базисе

Показывать лекцию целиком

Трех функций - отрицания, конъюнкции и дизъюнкции - достаточно, чтобы через них выразить любую логическую функцию. Эти три функции составляют тот базис, который встраивается практически во все языки программирования. Как правило, для удобства к этим трем функциям добавляется тождество, иногда Исключительное Или, реже – импликация.

Теоретический интерес представляет вопрос о минимальном базисе. Ранее мы видели, что конъюнкцию можно выразить через отрицание и дизъюнкцию, так что базис можно сократить до двух функций. Удивительно, но базис может быть сокращен до одной функции. Такими функциями, составляющими минимальный базис, являются функции Штрих Шеффера и Стрелка Пирса.

Проверьте справедливость следующих эквивалентностей:

$$X \uparrow X \equiv \neg X$$

Вернуться к учебному плану