Двухэлементная булева алгебра

Рассмотрим множество В_о = {0,1} и определим на нем операции , согласно таблицам истинности формул , , .

Тогда система B _о = является двухэлементной булевой алгеброй со всеми свойствами на операции. Формулы алгебры логики, содержащие лишь логические операции являются термами в B _о. Термом является любое функциональное выражение, составленное с помощью переменных и/или сигнатурных функциональных символов.

По теореме о функциональной полноте в булевой алгебре B _о с помощью терма можно задать любую булеву функцию.

Функции одной переменной y = f(x)

Существует четыре различных функции одной переменной на множестве {0,1}: константа "0", константа "1", переменная x и инверсия переменной x (). Нетрудно убедиться, что из этих функций с помощью операций суперпозиции и подстановки можно получить только функцию одной переменной.

Перенумеруем эти функции (их 4) естественным образом и расположим в виде таблицы:

Видно, что f₀ (х) = 0, a f₃ (х) = 1, т. е. эти две функции не зависят от х, f₁ (х) = х, т.е. она не меняет аргумента. Функция f₂ (х) действительно содержательная функция. Она принимает значения, противоположные значениям аргумента, обозначается f₂ (х) = и называется отрицанием (применяют еще обозначение x (читается “не x ”)).

Отрицанием высказывания X называется высказывание , которое истинно, когда X ложно, и ложно, когда X истинно.

Таблица истинности для отрицания

X