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

---

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

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

---