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

Булева формула — терм над некоторым множеством булевых функций. Более развёрнуто: пусть $F$ — некоторое множество булевых функций, $X$ — множество символов переменных, $S=\{$«$,$» «$($» «$)$»$\}$ — множество символов пунктуации, причём все три множества попарно непересекаются. Булева формула над множеством функций $F$ и множеством переменных $X$ индуктивно определяется как слово над алфавитом $F\cup X\cup S$ следующим образом:

1. слово $x$, где $x\in X$ — формула;
2. слово $c$, где $c\in F$ и $c$ имеет арность $0$ — формула;
3. слово $f(\varphi _{1},\ldots ,\varphi _{n})$, где $f\in F$, $f$ имеет арность $n>0$, $\varphi _{1},\ldots ,\varphi _{n}$ — некоторые формулы, — формула;
4. любая формула получена за конечное число применения шагов 1-3.

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

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

Пусть ${\tilde {x}}=(x_{1},\ldots ,x_{n})$ — конечный набор (так в теории дискретных функций принято называть кортежи, пустые кортежи тоже допускаются) переменных такой, что $X(\Phi )\subseteq {\tilde {x}}$. Значением формулы $\Phi$ на наборе значений ${\tilde {\alpha }}=(\alpha _{1},\ldots ,\alpha _{n})\in E_{2}^{n}$ переменных ${\tilde {x}}$ определяется следующим образом:

• если $\Phi =x_{i}$, то

$\Phi [{\tilde {x}},{\tilde {\alpha }}]=\alpha _{i}$;

• если $\Phi =f(\varphi _{1},\ldots ,\varphi _{n})$, то

$\Phi [{\tilde {x}},{\tilde {\alpha }}]=f(\varphi _{1}[{\tilde {x}},{\tilde {\alpha }}],\ldots ,\varphi _{n}[{\tilde {x}},{\tilde {\alpha }}])$.

Говорят, что формула $\Phi$ задаёт функцию $f$ относительно набора переменных ${\tilde {x}}$ при если функция $f$ определяется соотношением:

$f(\alpha _{1},\ldots ,\alpha _{n})=\Phi [{\tilde {x}},{\tilde {\alpha }}]$

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

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

Литература

• Подколзин А. С. 1 лекция курса «Теория дискретных функций»  (рус.). http://intsys.msu.ru. Дата обращения: 4 мая 2024.