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

Для облегчения записи условий задачи используются также символы, аналогичные кванторам существования и всеобщности в логике предикатов.

Любое предложение из логики предикатов может быть записано с помощью логики высказываний в том случае, когда область определения переменных является конечным множеством X. Предикатную константу P(x) в таком случае можно считать набором высказываний P₁=P(x₁), ... ,P_N=P(x_N), здесь N – количество элементов в множестве X. Формулу, использующую квантор всеобщности (∀xP(x)), можно записать в виде выражения P₁ ∧ ... ∧ P_N, а формулу, использующую квантор существования (∃ xP(x)), можно записать в виде P₁ ∨ ... ∨ P_N.

Примером рассуждения, не выразимого в логике высказываний, часто приводят следующий: "Все люди смертны. Сократ – человек. Следовательно, Сократ смертен".

Множество "всех людей" хоть и очень большое, но конечное. Поэтому можно ввести обозначения высказываний:

P_i – i-й человек, Q – смертен, S – Сократ.

В этих обозначениях вышеприведенное рассуждение записывается следующим образом:

В пределах задания одного множества нет необходимости использовать символы всеобщности или существования, так как существование или всеобщность какой-то переменной (слова) задается ее отсутствием:

• если мощность множества задается равной 0 (пустое множество), то отсутствие переменной означает, что пустым оно будет при ее любом значении;
• если же множество задается не пустым, то отсутствие переменной означает, что для некоторых ее значений (может быть, и всех, но не обязательно) множество будет не пустым.

В перечень значений переменной входит также и ее отрицание (равенство 0).

Необходимость использования кванторов возникает при задании условий, накладываемых на два или более множеств. Например, такое условие "гитарист и пианист учатся на одном факультете" можно представить как "существует факультет Ф, на котором они оба учатся", что запишется следующим образом:

Если имеется перечень возможных факультетов (географический, филологический, исторический, ...), то это условие существования записывается как предыдущие выражения для каждого факультета, связанные друг с другом логической связкой "ИЛИ":

Опять получается очень громоздкая запись. Для ее сокращения как раз и используется символ "#", задающий условие, аналогичное квантору существования. Предыдущее условие запишется следующим образом:

Программа это выражение просто преобразует в предыдущее.

Квантор всеобщности в такой же интерпретации заменяется выражениями, связанными друг с другом логической связкой "И". Например, условие "имеется по одному шарику каждого цвета" запишется следующим образом:

Для упрощения записи можно использовать символ "*", задающий условие, аналогичное квантору всеобщности:

Программа, как и в предыдущем случае, заменит его более длинным выражением с использованием логической связки "И".

Что касается перечня значений свойства, то программа использует лишь те значения, которые встречаются во всей строке задания условия задачи. Так как во время синтаксического разбора строки кванторы обрабатываются в последнюю очередь, то это обеспечивает использование всех значений свойства, не зависимо от того, встретились они до или после квантора.