Кванторы
Наивное определение кванторов
Исчисление предикатов начинается, когда в предметную теорию с бесконечным числом сущностей вводятся кванторы существования \(\exists\) и всеобщности \(\forall\). В ограниченной предметной области, они служат лишь сокращением для конечной цепочки логических связок "\(\vee\) " и "\(\&\)". В общем же случае кванторы превращаются в бесконечные конструкции вида: \[ \begin{array}{l} \exists_x\, A(x) ~~~\equiv~~~ A(x_1) \vee A(x_2) \vee A(x_3) \vee ..., \\[2mm] \forall_x\, A(x) ~~~\equiv~~~ A(x_1) \,\&\, A(x_2) \,\&\, A(x_3) \,\&\, ..., \end{array} \] где \(\{x_1, x_2, x_3,...\}\) — множество значений предметной переменной \(x\) (все предметные сущности). Выражение \(\exists_x\, A(x)\) истинно, если существует хотя бы один предмет \(x_i\) для которого предикат \(A(x_i)\) истинен. Аналогично выражение \(\forall_x\, A(x)\) истинно, если предикат \(A(x)\) истинен для всех предметов (и для первого, и для второго, и т.д.)Определить истинность или ложность подобных выражений при помощи таблиц истинности проблематично.
Иногда, соответствующий подтверждающий или опровергающий пример находится быстро. Например, если все \(A(x_i)\) при \(i < 100000\) истины, а \(A(x_{1000000})\) ложен, то и выражение \(\forall_x\, A(x)\) будет ложно. И наоборот, первое же истинное \(A(x_i)\) сделает истинным утверждение \(\exists_x\, A(x)\).
Однако, часто перебор предметных констант не приводит к опровергающему для \(\forall_x\, A(x)\) или подтверждающему для \(\exists_x\, A(x)\) примеру. В результате, опровергнуть высказывание типа \(\forall_x\, A(x)\), при помощи таблиц истинности можно, а вот доказать его таким образом — нельзя ( полуразрешимость теории предикатов). Никто не способен бесконечно долго оценивать предикаты и понятие истинности, основанное на соответствующих таблицах, может оказаться не применимым к подобным формулам.
\(\diamond\) Например, по теореме Ферма, для всех \(n>2\) нельзя найти таких \(x,y,z\in \mathbb N\), чтобы выполнялась обобщенная формула Пифагора: \[ \forall_n \,\forall_x \,\forall_y\, \forall_z \,\bigr( (n>2)\,\&\,(x>0)\,\&\,(y>0) \,\to\, ( x^n + y^n \neq z^n) \bigr) . \] Можно выяснить истинность или ложность каждого предиката: \(n > 2\), \(x > 0\), \(x^n + y^n = z^n\) при данных \(n\), \(x\), \(y\), \(z\). Однако этого нельзя сделать для всей формулы в целом так как пришлось бы просмотреть бесконечное множество чисел. Убедится в правильности такой формулы можно, только построив её вывод из аксиом арифметики. \(\square\)
Когда кванторы не пререстановочны
Различные кванторы не перестановочны: "для любого \(x\) существует \(y\)" не тоже, что "некий \(y\) существует для любого \(x\)": \[ \forall_x \, \exists_y\, A(x,y)~~ \not \equiv ~~\exists_y\, \forall_x \, A(x,y). \] В обыденной жизни подобная неэквивалентность вполне естественна. Пусть \(A(x,y)\): "\(x\) имеет мать \(y\)". Тогда очевидно, что для "любого \(x\) существует мать \(y\)", тогда как утверждение "некая \(y\) является матерью всех людей \(x\)" истинно только в очень специфическом мире. Чтобы доказать не общезначимость формулы (т.е. что она не тавтология) достаточно придумать пример где она ложна.
\(\diamond\) Пусть предметная область — это натуральные числа: \(0,1,...\), а предикат \(A(x,y):~x < y\). Утверждение \(\forall_x\, \exists_y \, (x < y)\) истинно ("для каждого \(x\) существует \(y\), который его больше"). Утверждение же \(\exists_y \, \forall_x \, (x < y)\) ложно, так как нет числа, большего любого натурального. Пример с матерями и детьми — это также опровергающий пример. \(\square\)
Тем не менее, далее мы докажем, что следующая формула является тавтологией: \[ \exists_y\, \forall_x \, A(x,y) ~~ \to ~~ \forall_x \, \exists_y\, A(x,y). \] Стоит её проверить, для \(A(x,y)\): "\(x\) имеет мать \(y\)". Заметим, что в этой и предыдущей формулах область действия кванторов ограничивается только предикатом (кванторы имеют наивысший приоритет). В частности, можно было бы написать \(\exists_y\, \forall_x \, A(x,y) \,\to\, \forall_u \, \exists_v\, A(u,v)\).
Разберём неперестановочность \(\forall_x\) и \(\exists_y\) с других позиций. Всеобщность \(\forall_x \, A(x,y)\) связывает переменную \(x\) и выражение зависит только от \(y\): \[ \exists_y\forall_x \, A(x,y) ~\equiv~ \exists_y\,\bigr(A(x_1, y) \,\&\, A(x_2, y) \,\&\,A(x_3, y) \,\&\, ...\bigr), \] где \(x_i\) — все предметы теории, множеству \(\mathbb X =\{x_1,x_2,...\}\) которых принадлежит первый аргумент предиката \(A(x,y)\). Эта формула истинна, если существует такая константа \(\bar{y}\) (одна или несколько), для которой \(A(x,\bar{y})\) истинно при каждом \(x\in \mathbb X\), т.е. \(\bar{y}\) одинаков для всех \(x\). Связывание сначала квантором существования допускает больше произвола: \[ \forall_x\exists_y \, A(x,y) ~\equiv~ \forall_x \,\bigr(A(x ,y_1) \vee A(x, y_2) \vee A(x, y_2) \vee ...\bigr). \] Выражение истинно, если для каждого \(x\) есть такое \(y_i\), что \(A(x,y_i)\) истинно. Следовательно, существует одна или несколько функций \(y=f(x)\), для которых \(\forall_x\,\exists_y\,A(x,y)\) можно заменить на \(\forall_x\,A(x,f(x))\), где \(f(x)\) даёт при данном \(x\) существующий \(y\). Понятно, что если \(A(x,\bar{y})\) истинно для константы \(\bar{y}\), то оно будет истинно и для некоторых функций \(A(x,f(x))\), по крайней мере константных \(f(x)=\bar{y}\) (но, возможно, не только).
Единственная ситуация когда всегда можно переставлять кванторы \(\exists\) и \(\forall\) местами это предметная область с единственной сущностью. Однако в этом случае использовать кванторы бессмысленно.
Однотипные кванторы пререстановочны
Однотипные кванторы, можно переставлять местами: \[ \begin{array}{lcl} \forall_x\,\forall_y\,A(x,y) &~\equiv~& \forall_y\,\forall_x\,A(x,y),\\[2mm] \exists_x\,\exists_y\,A(x,y) &~\equiv~& \exists_y\,\exists_x\,A(x,y). \end{array} \] В таких формулах иногда будет использоваться сокращение \(\forall_{x,y}:~\forall_x\forall_y\) и аналогично для \(\exists\). Таким образом \(\forall_{x,y}\equiv \forall_{y,x}\) и \(\exists_{x,y}\equiv \exists_{y,x}\). Число аргументов предикатов, входящих в формулу, произвольно. Например, справедливо: \(\forall_x\,\forall_y\,A(w,x,v,y,z) ~~\equiv~~ \forall_y\,\forall_x\,A(w,x,v,y,z)\).
Другие свойства кванторов
Отрицание можно "проносить" через квантор, меняя его: \[ \begin{array}{lcl} \neg \forall_x\, A(x) &~\equiv~& \exists_x\, \neg A(x),\\[2mm] \neg \exists_x\, A(x) &~\equiv~& \forall_x\, \neg A(x). \end{array} \] ("если не верно для всех \(x\), то есть \(x\) для которого ложно").
Действие любого квантора (\(\mathcal{Q}=\exists~или~\forall\)) можно расширять, вынося за дизъюнкцию или конъюнкцию (правила расширения действия): \[ \begin{array}{lcl} \mathcal{Q}_x\, A(x) ~\&~ B &~\equiv~& \mathcal{Q}_x\, \bigr(A(x) \,\&\, B\bigr),\\[2mm] \mathcal{Q}_x\, A(x) \,\vee\, B &~\equiv~& \mathcal{Q}_x\, \bigr(A(x) \vee B\bigr), \end{array} \] где отсутствие явного указания у предиката \(B\) аргумента \(x\) означает, что он от \(x\) не зависит, а при отсутствии скобок приоритет кванторов считается максимальным, т.е. \(\forall_x A(x)\,\&\,...\) — это \((\forall_x A(x))\,\&\,...\) и т.д.
Наконец, для родственных операций (\(\&\) для \(\forall\) и \(\vee\) для \(\exists\) ) можно объединять кванторы ( правила объединения): \[ \begin{array}{lcl} \forall_x\,\forall_y\, \bigr(A(x)\,\&\,B(y)\bigr) &~\equiv~& \forall_x\, \bigr(A(x)\,\&\,B(x)\bigr),\\[2mm] \exists_x\,\exists_y\, \bigr(A(x)\vee B(y)\bigr) &~\equiv~& \exists_x\, \bigr(A(x)\vee B(x)\bigr). \end{array} \]
Полезны также тождества разбиения: \[ \begin{array}{lcl} \forall_x\,\forall_y\, A(x,y) &~\equiv~& \forall_x\,A(x,x)~\&~\forall_x\forall_y\,\bigr(x\neq y \,\to\,A(x,y)\bigr),\\[2mm] \exists_x\,\exists_y\, A(x,y) &~\equiv~& \exists_x\,A(x,x)\,\vee\,\exists_x\exists_y\,\bigr(x\neq y ~~\&~~A(x,y)\bigr). \end{array} \]
Для конечных предметных областей все эти тождества несложно доказать при помощи алгебры логики, записав квантор всеобщности как цепочку логических И, а квантор существования как цепочку логических ИЛИ. Постулируется, что все эти тождества справедливы не только для конечных, но и для бесконечных множеств.
Доказательства
Перестановочность кванторов непосредственно следует из коммутативности \(A\,\&\,B\equiv B\,\&\,A\) и правил поглощения \(A\,\&\,A\equiv A\).
Тождества с отрицанием следуют из правил \(\neg(A\,\&\, B)~\equiv~ \neg A\vee \neg B\): \[ \neg \forall_x\, A(x) ~~\equiv~~ \neg (A_1 \,\&\, A_2 \,\&\, ...) ~~\equiv~~ \neg A_1 \vee \neg A_2 \vee ... ~~\equiv~~\exists_x\, \neg A(x), \] где \(A_i=A(x_i)\). Также легко доказываются правила расширения для родственных операций. Например \(\forall_x\, A(x) \,\&\, B ~\equiv~ \forall_x\, \bigr(A(x) \,\&\, B\bigr)\) это \[ (A_1\,\&\,A_2\,\&\,...)\,\&\,B \equiv (A_1\,\&\,B)\,\&\,(A_2\,\&\,B)\,\&\,..., \] где учтена ассоциативность, коммутативность и поглощение \(B\,\&\,B\equiv B\). Для неродственных операций используется свойство дистрибутивности. Так \(\forall_x\, A(x) \vee B ~\equiv~ \forall_x\, \bigr(A(x) \vee B\bigr)\) это \[ (A_1\,\&\,A_2\,\&\,...)\vee B \equiv (A_1\vee B)\,\&\,(A_2\vee B)\,\&\,... \] Чтобы обосновать правила объединения кванторов с родственными операциями, распишем в \(\forall_x\forall_y\, \bigr(A(x) \,\&\, B(y))\) сначала \(\forall_y\), а затем \(\forall_x\): \[ (A_1\&\,B_1)\,\&\,(A_1\&\,B_2)\,\&\,(A_1\&\,B_3)\,\&\,...(A_2\,\&\,B_1)\,\&\,(A_2\&\,B_2)\,\&\,(A_2\,\&\,B_3)\,\&\,... \] По свойству поглощения это: \((A_1\,\&\,B_1)\,\&\,(A_2\,\&\,B_2)\,\&\,... \equiv \forall_x\,(A_x\,\&\,B_x)\). Аналогично доказываются тождества разбиения.
Число существований
Пусть в теории определён предикат равенства \(x=y\), позволяющий выяснять одинаковы ли две сущности \(x\) и \(y\). С его помощью можно детализировать количество существующих объектов. Например:
Не более одного объекта \(\{0,1\}\) обладает свойством \(A\): \[ \forall_{x,y}\, [ A(x)\,\&\,A(y) \to x=y ]. \]
Один и только один объект \(\{1\}\) обладает свойством \(A\): \[ \exists_x\,A(x)~~\&~~\forall_{x,y}\, [ A(x)\,\&\,A(y) \to x=y ]. \] Последний вид существования в единственном экземпляре иногда обозначают при помощи квантора с восклицательным знаком: \(\exists^{!}_{x}\,A(x)\). Аналогично строятся формулы относительно двух сущностей:
По меньшей мере два объекта \( \{2,3,...\}\) обладают свойством \(A\): \[ \exists_{x,y}\, [ A(x)\,\&\,A(y) \,\&\, x\neq y ]. \]
Не более двух объектов \(\{0,1,2\}\) обладают свойством \(A\): \[ \forall_{x,y,z}\, [ A(x)\,\&\,A(y)\,\&\,A(z) ~\to~ (x=y ~\vee~ x=z ~\vee~ y=z) ]. \] Объединение двух последних формул логическим "И" приведёт к фразе: "в точности два объекта обладают свойством \(A\)". Подобным образом можно говорить о трёх сущностях, и т.д.