В логике предикатов будем пользоваться следующей символикой:
1. Символы \(p, q, r, ...\) - переменные высказывания, принимающие два значения: 1- истина , 0 – ложь.
2. Предметные переменные – \(x, y, z, ...\) которые пробегают значения из некоторого множества \(M\); \(x^{0}, y^{0}, z^{0}, ...\) – предметные константы, то есть значения предметных переменных.
3. \(P( \cdot ) , F (\cdot )\) - одноместные предикатные переменные; \(Q ( \cdot ,\cdot , ...,\cdot ) , R ( \cdot ,\cdot , ...,\cdot )\) - n-местные предикатные переменные.
\(P^{0} ( \cdot ) , Q^{0} ( \cdot , \cdot , ..., \cdot )\) - символы постоянных предикатов.
4. Символы логических операций: \(\wedge , \vee , \rightarrow , -\).
5. Символы кванторных операций: \(\forall\)\(x\), \(\exists\)\(x\).
6. Вспомогательные символы: скобки, запятые.
Определение формулы логики предикатов.
1. Каждое высказывание как переменное, так и постоянное, является формулой (элементарной).
2. Если \(F ( \cdot ,\cdot ,...,\cdot )\) – \(n\)-местная предикатная переменная или постоянный предикат, а \(x_{1}, x_{2},...,x_{n}\) – предметные переменные или предметные постоянные (не обязательно все различные), то \(F (x_{1}, x_{2},...,x_{n})\) есть формула.
Такая формула называется элементарной, в ней предметные переменные являются свободными, не связанными кванторами.
3. Если \(A\) и \(B\) – формулы, причем, такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой – свободной, то слова \(A \vee B, A \wedge B\), \(A \rightarrow B\) есть формулы. В этих формулах те переменные, которые в исходных формулах были свободны, являются свободными, а те, которые были связанными, являются связанными.
4. Если \(A\) – формула, то \(\bar{A}\) – формула, и характер предметных переменных при переходе от формулы \(A\) к формуле \(\bar{A}\) не меняется.
5. Если \(A (x)\) – формула, в которую предметная переменная \(x\) входит свободно, то слова \(\forall\)\(x\)\(A (x)\) и \(\exists\)\(x\)\(A (x)\) являются формулами, причем, предметная переменная входит в них связанно.
6. Всякое слово, отличное от тех, которые названы формулами в пунктах 1 – 5, не является формулой.
Например, если \(P (x)\) и \(Q (x,y)\) – одноместный и двухместный предикаты, а \(q, r\) – переменные высказывания, то формулами будут слова: \(q\), \(P (x)\), \(P(x) \wedge Q ( x^{0}, y)\), \(\forall\)\(x\)\(P (x)\)\(\rightarrow\)\(\exists\)\(x\)\(Q (x,y)\), \((\overline{ Q (x,y)} \vee q) \rightarrow r\).
Не является формулой, например, слово: \(\forall\)\(x\)\(Q (x,y)\)\(\rightarrow\)\(P (x)\). Здесь нарушено условие п.3, так как формулу \(\forall\)\(x\)\(Q (x,y)\) переменная \(x\) входит связанно, а в формулу \(P (x)\) переменная \((x\) входит свободно.
Из определения формулы логики предикатов ясно, что всякая формула алгебры высказываний является формулой логики предикатов.
Пример. Какие из следующих выражений являются формулами логики предикатов? В каждой формуле выделите свободные и связанные переменные.
1) \(\overline {\exists x \forall z}\)\(\overline{(P(x,y)\rightarrow P (y,z))}\);
2) \(( p \rightarrow q) \wedge ( \bar{r}\vee \bar{p})\);
3) \(P(x) \wedge\)\(\forall x\)\(Q (x)\);
4) \(\forall x\)\((P(x)\rightarrow Q(x))\) \(\leftrightarrow\)\((\exists x\)\(P(x)\rightarrow\)\(\forall x\)\(R (x,y))\);
5) \((P(x) \leftrightarrow Q(x)) \vee\)\(\exists y\)\((\forall y\)\(R (y))\);
6) \(\exists x\)\(\forall z\)\((P(x,y)\rightarrow P(y,z))\).
Решение. Выражения 1), 2), 4), 6) являются формулами, так как записаны в соответствии с определением формулы логики предикатов. Выражения 3) и 5) не являются формулами. В выражении 3) операция конъюнкция применена к формулам \(P(x)\) и \(\forall x\)\(Q (x)\); в первой из них переменная v свободна, а во второй связана квантором общности, что противоречит определению формулы. В выражении 5) квантор существования по переменной \(y\) навешен на формулу \(\forall y\)\(R (y)\), в которой переменная \(y\) связана квантором общности, что также противоречит определению формулы.
В формуле 1) переменная В формуле 1) переменная \(y\) свободна, а переменные \(x\) и \(z\) связаны. В формуле 2) нет предметных переменных. В формуле 4) переменная \(x\) связана, а переменная \(y\) свободна.
