Булева формула

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

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

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

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

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

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