Булева формула (по имени Джорджа Буля ) — формула логики высказываний . Может содержать и пропозициональные связки — конъюнкцию (« ${\displaystyle \wedge }$ »), дизъюнкцию (« ${\displaystyle \vee }$ »), отрицание (« ${\displaystyle \neg }$ ») и другие.

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

Булева формула от n переменных определяет булеву функцию ${\displaystyle E^{n}\to E}$ , где

${\displaystyle E=\{0;1\}}$ — множество значений каждой переменной ${\displaystyle x_{i}}$ ,

значение 0 соответствует тому, что ${\displaystyle x_{i}}$ ложно, а значение 1 соответствует тому, что ${\displaystyle x_{i}}$ истинно.

Всего существует ${\displaystyle 2^{2^{n}}}$ булевых функций, поэтому существует столько же классов эквивалентных булевых формул.

В статье не хватает ссылок на источники (см. рекомендации по поиску ). Информация должна быть проверяема , иначе она может быть удалена. Вы можете статью, добавив ссылки на авторитетные источники в виде сносок . ( 7 июня 2019 )