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

Булева формула (по имени Джорджа Буля) — формула логики высказываний. Может содержать логические переменные и пропозициональные связки — конъюнкцию ("$\wedge$"), дизъюнкцию ("$\vee$"), отрицание ("$\neg$") и другие. Формула называется тождественно истинной (ложной), если она истинна (ложна) при любых значениях переменных. Две булевы формулы называются эквивалентными тогда и только тогда, когда они истинны на одном и том же подмножестве множества значений аргументов. Булева формула от n переменных определяет булеву функцию $E^n \to E~$. $E=\{0;1\}~$ - множество значений каждой переменной $x_i~$, значение 0 соответствует тому, что $x_i~$ ложно, а значение 1 соответствует тому, что $x_i~$ истинно. Всего существует $2^{2^n}~$ булевых функций, поэтому существует столько же классов эквивалентных булевых формул.