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

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

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

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

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

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

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

x	f₀	f₁	f₂	f₃

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

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

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

X