§ 23. Предикаты и кванторы

Определения и обозначения

Предикат — высказывание с переменными, которое становится истинным или ложным после подстановки конкретных значений. Например, «x больше 3» при x = 5 истинно, а при x = 2 ложно. Пока значение x не задано, перед нами не обычное высказывание с установленной истинностью, а условие. Предикаты нужны, чтобы описывать свойства объектов и проверять их для разных значений.

Область определения предиката — множество допустимых значений его переменных. Для условия «x² = 4» областью могут быть целые числа, натуральные числа или действительные числа, и допустимые подстановки будут разными. Поэтому область обычно указывают явно, особенно если рядом стоят кванторы. Она помогает точно понять, о каких объектах идёт речь.

Множество истинности предиката — все наборы значений из области определения, при которых предикат истинен. Если P(x) означает «x — чётное число», а область задана как {1, 2, 3, 4}, то множество истинности равно {2, 4}. Оно показывает, какие именно значения удовлетворяют условию. Это удобно, когда нужно проверить предикат сразу на всей заданной области.

Квантор — обозначение, которое показывает, для скольких значений переменной верно утверждение: для всех или хотя бы для одного. Квантор всеобщности обозначают ∀, а квантор существования — ∃. С ними предикат превращается в высказывание, истинность которого можно оценить. Для такой оценки необходимо знать область определения переменной.

Как это устроено

Подстановка значения превращает открытое высказывание в обычное. Например, условие P(x): «x + 2 = 7» при x = 5 становится истинным высказыванием, а при x = 4 — ложным. Причина в том, что после подстановки переменной уже нечего выбирать: равенство можно проверить. Поэтому предикат сам по себе не называют истинным или ложным, пока значения переменных не заданы.

Одна и та же запись предиката может давать разные множества истинности при разных областях. Для P(x): «x² = 4» среди целых чисел подходят −2 и 2, а среди натуральных — только 2, если натуральные числа начинаются с 1. Если область не обозначить, невозможно понять, какие значения требуется проверять и что именно означает найденное множество. Область определения делает условие точным.

Квантор всеобщности ∀ означает, что условие должно выполняться для каждого значения из области. Запись ∀x P(x) истинна, только если при любой допустимой подстановке предикат P(x) становится истинным. Достаточно найти один контрпример — значение, при котором P(x) ложно, — чтобы опровергнуть такое утверждение. Поэтому проверка всеобщего утверждения сводится к поиску возможных исключений.

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

Квантор связывает переменную только в пределах своей области действия — той части формулы, к которой он относится. Скобки помогают увидеть границы этой части и не перепутать, какие условия относятся к переменной. Например, в записи ∀x (P(x) и Q(x)) квантор охватывает оба предиката, а в записи (∀x P(x)) и Q(y) переменная y этим квантором не связана. Если переменная встречается за пределами области действия, её значение задаётся отдельно.

Кванторные высказывания

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

Разбор задач

Множество истинности предиката

Условие. Для P(x): «x — чётное число» и области определения {1, 2, 3, 4} найти множество истинности. Нужно проверить каждое значение из указанной области, а не все числа вообще. Чётным называется целое число, делящееся на 2 без остатка.

1. Проверяем x = 1: число 1 не делится на 2 без остатка, поэтому P(1) ложно.
2. Проверяем x = 2 и x = 3: число 2 чётное, значит P(2) истинно; число 3 нечётное, поэтому P(3) ложно.
3. Проверяем x = 4: оно делится на 2 без остатка, значит P(4) истинно. Собираем значения, при которых предикат истинен.

Ответ: множество истинности — {2, 4}. В него попали только элементы заданной области, удовлетворяющие предикату.

Запись с квантором всеобщности

Условие. Записать с помощью кванторов высказывание «Каждое натуральное число не меньше 1» и указать область определения. Слово «каждое» показывает, что проверять нужно все значения переменной. Уточнение области необходимо, чтобы запись имела однозначный смысл.

1. Обозначим переменную буквой n и зададим область: n ∈ ℕ, где ℕ — множество натуральных чисел.
2. Выбираем квантор всеобщности, потому что высказывание относится к каждому элементу области.
3. Переводим слова «не меньше 1» в неравенство n ≥ 1 и соединяем его с квантором.

Ответ: ∀n ∈ ℕ: n ≥ 1. При принятом определении натуральных чисел, начинающихся с 1, это высказывание истинно.

Истинность высказываний и их отрицания

Условие. Для P(x): «x² = 4» на целых числах определить истинность высказываний «для всех x верно P(x)» и «существует x, для которого верно P(x)», а затем сформулировать их отрицания. Здесь важно отдельно проверить оба квантора: всеобщность требует проверки каждого целого числа, а существование — одного подходящего. При отрицании меняется и квантор, и смысл предиката.

1. «Для всех x верно P(x)» ложно: например, при x = 0 равенство 0² = 4 неверно.
2. «Существует x, для которого верно P(x)» истинно, поскольку x = 2 и x = −2 удовлетворяют равенству.
3. Отрицаем первое утверждение: «существует целое x, для которого x² ≠ 4». Оно истинно, например, при x = 0.
4. Отрицаем второе утверждение: «для всех целых x x² ≠ 4». Оно ложно, так как при x = 2 равенство выполняется.

Ответ: всеобщее утверждение ложно, существовательное истинно. Их отрицания — соответственно «найдётся целое x, для которого x² ≠ 4» и «для всех целых x x² ≠ 4».

Типичные ошибки

Считать предикат истинным или ложным до задания значения переменной — ошибка: переменная ещё может принимать разные значения. Её допускают, путая условие с готовым высказыванием. Проверьте себя: если в записи осталась свободная переменная и не указан квантор, спросите, какое значение ей подставлено.

Если не указать область определения, можно незаметно изменить смысл и истинность утверждения. Например, среди натуральных чисел уравнение x² = 4 имеет решение 2, а среди целых есть также −2. Ошибка возникает, когда область кажется очевидной и её опускают. Перед проверкой кванторного высказывания всегда выпишите множество допустимых значений.

Квантор существования часто ошибочно понимают как «ровно один». На самом деле он требует хотя бы одного подходящего значения, и таких значений может быть несколько. Путаница появляется из-за бытового смысла слова «существует». Проверьте себя: если найдено два решения, утверждение с ∃ всё равно истинно.

При отрицании иногда оставляют прежний квантор, хотя это меняет смысл исходной фразы. Отрицание «для всех x верно P(x)» — «найдётся x, для которого P(x) неверно», а отрицание существования — всеобщность с противоположным условием. Ошибка возникает, если отрицать только предикат и забыть о кванторе. Проверьте себя, задав вопрос: что должно произойти, чтобы исходное утверждение стало ложным?

Связь с другими темами

Для работы с предикатами нужно знать, что такое высказывание, переменная, множество и истинность высказывания: эти понятия позволяют подставлять значения и проверять условия. В программировании предикаты записывают как логические условия, например при проверке свойств данных или элементов массива. Кванторы помогают точно формулировать утверждения о множествах и их элементах. Тема также подготавливает к изучению логических операций, отрицания сложных высказываний и математических доказательств.

Что запомнить

• Предикат становится высказыванием после задания значений переменных.
• Для предиката важно указать область определения.
• Множество истинности содержит значения, при которых предикат истинен.
• Квантор всеобщности читается как «для любого» или «для всех».
• Квантор существования читается как «существует» или «найдётся хотя бы один».
• При отрицании квантор всеобщности заменяется квантором существования, а квантор существования — всеобщности.