Булева алгебра

Булева алгебра  — это непустое множество B с заданными на нем двуместными операциями ۸ (аналог конъюнкции), ۷ (аналог дизъюнкции), одноместной операцией ⌐ (аналог отрицания) и двумя выделенными элементами 0 и 1 (аналоги лжи и истины), такими что для всех элементов выполняются следующие аксиомы:

Например, множество всех подмножеств некоторого множества S является булевой алгеброй относительно операций пересечения, объединения, дополнения. Роль нуля в такой алгебре играет пустое множество, роль единицы – всё множество S.

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

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

Имеет место теорема Стоуна о представлении, обобщающая этот результат на бесконечные булевы алгебры: всякая булева алгебра изоморфна подалгебре алгебры всех подмножеств некоторого множества — более точно, алгебре всех открыто-замкнутых подмножеств некоторого компактного вполне несвязного хаусдорфова топологического пространства.

В логике важную роль играет алгебра Линденбаума–Тарского произвольной теории первого порядка T — это фактор множество множества всех формул (в некотором языке) по отношению эквивалентности формул в теории T. Она является ещё одним примером булевой алгебры.