ГДЗ по информатике, 10 класс, Поляков, номер 22.3: Предикаты и кванторы

Это высказывание читается так: «Для любого x существует такой y, что выполняется предикат P(x,y)». Здесь выбор значения y может зависеть от конкретного выбранного x. То есть для каждого элемента множества X мы можем подобрать свой собственный элемент из множества Y, который удовлетворяет условию. Нет требования, чтобы этот y подходил всем x сразу.

Пример: Пусть P(x,y) означает «y>x», где x и y — натуральные числа. Высказывание ∀x∃y(y>x) истинно. Действительно, какое бы число x мы ни взяли, всегда можно найти число y, которое больше него (например, y=x+1).

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

Пример: Используем тот же предикат P(x,y): «y>x» для натуральных чисел. Высказывание ∃y∀x(y>x) ложно. Не существует такого натурального числа y, которое было бы больше всех натуральных чисел одновременно. Какое бы огромное число y мы ни выбрали, всегда найдется x=y+1, для которого условие нарушится.

Из приведенных примеров видно, что первое высказывание может быть истинным, тогда как второе — ложным. Следовательно, эти высказывания не равносильны .

Общее правило логики предикатов гласит: ∃y∀xP(x,y)implies∀x∃yP(x,y) То есть если верно второе высказывание (есть универсальный y), то автоматически верно и первое (для каждого x найдем этот самый y). Однако обратное утверждение неверно: наличие индивидуального решения для каждого x не гарантирует наличия одного общего решения для всех x.