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

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

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

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

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

Пусть $\tilde{x}=(x_1,\dots ,x_n)$ — конечный набор (так в теории дискретных функций принято называть кортежи, пустые кортежи тоже допускаются) переменных такой, что $X(\mathrm{\Phi })\subseteq \tilde{x}$. Значением формулы $\mathrm{\Phi }$ на наборе значений $\tilde{\alpha }=({\alpha }_1,\dots ,{\alpha }_n)\in E_2^n$ переменных $\tilde{x}$ определяется следующим образом:

• если $\mathrm{\Phi }=x_i$, то

$\mathrm{\Phi }[\tilde{x},\tilde{\alpha }]={\alpha }_i$;

• если $\mathrm{\Phi }=f({\phi }_1,\dots ,{\phi }_n)$, то

$\mathrm{\Phi }[\tilde{x},\tilde{\alpha }]=f({\phi }_1[\tilde{x},\tilde{\alpha }],\dots ,{\phi }_n[\tilde{x},\tilde{\alpha }])$.

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

$f({\alpha }_1,\dots ,{\alpha }_n)=\mathrm{\Phi }[\tilde{x},\tilde{\alpha }]$

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

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

Литература

• Шаблон:Cite web