Кванторы всеобщности и существования в логике предикатов

Логика высказываний оперирует целыми утверждениями, но не умеет говорить «для каждого» и «найдётся хотя бы один». Эти обороты вводит логика предикатов через два квантора: всеобщности $\forall$ («для всех») и существования $\exists$ («существует»). Именно они превращают предикат с переменной в осмысленное высказывание, у которого есть истинностное значение. Ниже разберём, что значит каждый символ, как читать формулу с кванторами, почему перестановка $\forall$ и $\exists$ меняет смысл и как аккуратно строить отрицание. Если у вас уже есть конкретная формула на разбор, удобнее сразу собрать запрос ниже.

Зачем нужны кванторы

Запись $P(x)$ - это предикат: высказывание о переменной $x$, истинность которого зависит от того, какое значение подставить. Само по себе $P(x)$ ещё не истинно и не ложно - это форма, открытое высказывание. Чтобы получить утверждение с определённым значением, переменную нужно либо подставить конкретно, либо связать квантором.

Квантор «прикрепляется» к переменной и пробегает её по всей области рассуждения. Запись $\forall x\, P(x)$ утверждает, что свойство $P$ выполнено у каждого объекта области; запись $\exists x\, P(x)$ - что хотя бы у одного. После навешивания квантора переменная становится связанной, а всё выражение превращается в полноценное высказывание. На этом же фундаменте строится интерпретация формулы логики предикатов: без выбора области и означивания предикатов истинность квантора оценить нельзя.

Квантор всеобщности

Символ $\forall$ (перевёрнутая латинская A, от all) читается «для всех», «для каждого», «для любого». Формула $\forall x\, P(x)$ истинна в данной интерпретации тогда и только тогда, когда $P(a)$ истинно для каждого элемента $a$ области. Достаточно одного контрпримера - одного $a$, на котором $P(a)$ ложно, - и вся формула становится ложной.

На конечной области квантор всеобщности раскрывается в конъюнкцию: если область $D = \{a_1, a_2, a_3\}$, то

$$\forall x\, P(x) \;\equiv\; P(a_1) \wedge P(a_2) \wedge P(a_3).$$

Чаще всего $\forall$ ходит в паре с импликацией: «все студенты сдали экзамен» формализуется как $\forall x\,(S(x) \rightarrow E(x))$, а не $\forall x\,(S(x) \wedge E(x))$. Второй вариант утверждал бы, что вообще всё на свете - студент, что почти наверняка ложно. Это типичная развилка: всеобщность ограничивают условием через $\rightarrow$.

Квантор существования

Символ $\exists$ (зеркальная E, от exists) читается «существует», «найдётся», «хотя бы для одного». Формула $\exists x\, P(x)$ истинна, когда $P(a)$ истинно хотя бы для одного элемента области; ложна - только если $P$ ложно на каждом объекте. Здесь всё симметрично всеобщности: один пример доказывает существование, а опровергнуть его можно лишь полным перебором.

На конечной области квантор существования раскрывается в дизъюнкцию:

$$\exists x\, P(x) \;\equiv\; P(a_1) \vee P(a_2) \vee P(a_3).$$

С существованием естественно сочетается конъюнкция: «некоторые студенты сдали досрочно» - это $\exists x\,(S(x) \wedge D(x))$, то есть «найдётся объект, который и студент, и сдал досрочно». Подмена связки на импликацию ($\exists x\,(S(x) \rightarrow D(x))$) делает формулу почти всегда истинной за счёт ложной посылки и теряет исходный смысл. Запомните пару: $\forall$ - с $\rightarrow$, $\exists$ - с $\wedge$.

Рассчитать для своей задачи

Порядок кванторов решает всё

Когда кванторы разного типа стоят рядом, их порядок меняет смысл формулы. Сравните:

$$\forall x\, \exists y\, R(x, y) \qquad\text{и}\qquad \exists y\, \forall x\, R(x, y).$$

Первая читается так: «для каждого $x$ найдётся свой $y$, связанный с ним отношением $R$» - для разных $x$ это могут быть разные $y$. Вторая сильнее: «существует один $y$, который связан сразу со всеми $x$» - один универсальный объект на всех. Классический пример: «у каждого человека есть мать» ($\forall x\, \exists y$) - правда, а «есть одна общая мать у всех людей» ($\exists y\, \forall x$) - ложь.

Общее правило: $\exists y\, \forall x\, R(x, y) \rightarrow \forall x\, \exists y\, R(x, y)$ - переход от «одного на всех» к «каждому свой» логически верен, а обратный - нет. Одноимённые кванторы переставлять можно свободно: $\forall x\, \forall y \equiv \forall y\, \forall x$ и $\exists x\, \exists y \equiv \exists y\, \exists x$. Опасна только перестановка разноимённых.

Область действия и связанные переменные

Область действия (scope) квантора - это подформула, на которую он распространяется. В $\forall x\,(P(x) \rightarrow Q(x))$ квантор связывает оба вхождения $x$, потому что скобки задают его область. А в $\forall x\, P(x) \rightarrow Q(x)$ без скобок $\forall x$ покрывает только $P(x)$, и второе $x$ в $Q(x)$ остаётся свободным - это уже другая формула с открытой переменной.

Различают свободные и связанные вхождения переменной. Связанное вхождение «принадлежит» квантору, свободное - параметр формулы. Имя связанной переменной несущественно: $\forall x\, P(x)$ и $\forall y\, P(y)$ - одна и та же формула, переменную можно переименовать (с осторожностью, чтобы не захватить уже занятое имя). На корректном переименовании и выносе кванторов вперёд строится предварённая нормальная форма, к которой приводят формулу перед сколемизацией и автоматическим доказательством.

Отрицание кванторов

Отрицание квантора переводит его в двойственный по правилам де Моргана для предикатов:

$$\neg\,\forall x\, P(x) \;\equiv\; \exists x\, \neg P(x), \qquad \neg\,\exists x\, P(x) \;\equiv\; \forall x\, \neg P(x).$$

Словами: «неверно, что все обладают свойством» означает «найдётся тот, кто им не обладает»; «неверно, что хоть один обладает» означает «никто не обладает, то есть все обладают отрицанием». Отрицание как бы «протаскивается» внутрь, переворачивая квантор и инвертируя предикат.

Для цепочки кванторов правило применяют слева направо, по одному квантору за шаг:

$$\neg\,\forall x\, \exists y\, R(x, y) \;\equiv\; \exists x\, \forall y\, \neg R(x, y).$$

Каждый $\forall$ стал $\exists$, каждый $\exists$ стал $\forall$, а отрицание дошло до ядра $R$. Это и есть стандартный приём доказательства от противного: чтобы опровергнуть $\forall x\, \exists y\, R(x,y)$, достаточно предъявить такой $x$, что ни один $y$ не подходит.

Частые ошибки

• Импликация и конъюнкция перепутаны. «Все $A$ суть $B$» - это $\forall x\,(A(x)\rightarrow B(x))$, а «некоторые $A$ суть $B$» - $\exists x\,(A(x)\wedge B(x))$. Связка $\wedge$ под всеобщностью и $\rightarrow$ под существованием почти всегда дают неверную формализацию.
• Перестановка разноимённых кванторов. $\forall x\,\exists y$ и $\exists y\,\forall x$ - разные утверждения; менять их местами нельзя, в отличие от одноимённых.
• Потеря области действия. Без скобок квантор связывает только ближайшую подформулу, и часть переменных остаётся свободной - формула перестаёт быть высказыванием.
• Неполный перенос отрицания. При отрицании цепочки нужно перевернуть каждый квантор и довести $\neg$ до предиката, а не остановиться на первом.
• Пустая область. На пустой области $\forall x\, P(x)$ истинно «вакуумно» (нет контрпримеров), а $\exists x\, P(x)$ - ложно. Это сбивает с толку, поэтому в классической логике область считают непустой.

FAQ

Чем квантор всеобщности отличается от квантора существования? $\forall$ требует, чтобы свойство выполнялось у каждого объекта области, и опровергается одним контрпримером. $\exists$ требует хотя бы одного подходящего объекта и доказывается одним примером. Они двойственны: отрицание одного даёт другой с инвертированным предикатом.

Как правильно читать формулу с несколькими кванторами? Слева направо, вкладывая один в область действия другого. $\forall x\,\exists y\,R(x,y)$ - «для каждого $x$ подберём свой $y$»; $\exists y\,\forall x\,R(x,y)$ - «есть один $y$ на всех $x$». Самый левый квантор «главнее»: он перебирает объекты, а внутренний зависит от уже выбранного.

Можно ли менять кванторы местами? Одноимённые - да: $\forall x\,\forall y \equiv \forall y\,\forall x$, $\exists x\,\exists y \equiv \exists y\,\exists x$. Разноимённые - нельзя в общем случае; верен только переход $\exists\,\forall \rightarrow \forall\,\exists$, обратный неверен.

Коротко

Кванторы $\forall$ («для всех») и $\exists$ («существует») связывают переменную предиката и превращают открытую формулу в высказывание: всеобщность раскрывается в конъюнкцию и опровергается контрпримером, существование - в дизъюнкцию и доказывается примером. Под $\forall$ ставят импликацию, под $\exists$ - конъюнкцию; порядок разноимённых кванторов менять нельзя; отрицание переворачивает квантор и инвертирует предикат по де Моргану. Истинность всегда оценивается относительно выбранной непустой области интерпретации.