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

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

Булева формула — терм над некоторым множеством булевых функций. Более развёрнуто: пусть — некоторое множество булевых функций, — множество символов переменных, «» «» «» — множество символов пунктуации, причём все три множества попарно непересекаются. Булева формула над множеством функций и множеством переменных индуктивно определяется как слово над алфавитом следующим образом:

  1. слово , где — формула;
  2. слово , где и имеет арность — формула;
  3. слово , где , имеет арность , — некоторые формулы, — формула;
  4. любая формула получена за конечное число применения шагов 1-3.

Термин булева формула назван по имени Джорджа Буля.

Если переменная входит в множество — это ещё не значит, что она встречается в формуле. Подмножество переменных, которые встречаются в формуле, называется множеством переменных формулы . Оно всегда конечно. Формулы, множество переменных которых пусто, называются замкнутыми.

Пусть — конечный набор (так в теории дискретных функций принято называть кортежи, пустые кортежи тоже допускаются) переменных такой, что . Значением формулы на наборе значений переменных определяется следующим образом:

  • если , то
;
  • если , то
.

Говорят, что формула задаёт функцию относительно набора переменных при если функция определяется соотношением:

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

Всего существует -арных булевых функций, поэтому существует столько же классов эквивалентных булевых формул над множеством переменных мощности .

Литература

[править | править код]