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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Булева формула (по имени Джорджа Буля) — формула логики высказываний. Может содержать логические переменные и пропозициональные связки — конъюнкцию»), дизъюнкцию»), отрицание («») и другие. Формула называется тождественно истинной (ложной), если она истинна (ложна) при любых значениях переменных. Две булевы формулы называются эквивалентными тогда и только тогда, когда они истинны на одном и том же подмножестве множества значений аргументов. Булева формула от n переменных определяет булеву функцию .  — множество значений каждой переменной , значение 0 соответствует тому, что ложно, а значение 1 соответствует тому, что истинно. Всего существует булевых функций, поэтому существует столько же классов эквивалентных булевых формул.