Предикаты и квантификаторы — Введение в математическую логику

• Логика предикатов
  • Предикаты
  • Квантификаторы
  • Универсальная квантификация
  • Экзистенциальная квантификация
  • Квантификатор единственности

Ранее в курсе мы изучали только пропозициональную логику: использовали пропозиции с нотациями, на их примерах рассматривали софизмы и эквивалентные высказывания.

Но есть ситуации, которые невозможно адекватно описать терминами логики пропозиций. Например:

Каждый человек имеет право водить машину, если он достиг восемнадцатилетнего возраста

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

Здесь нужен более мощный инструмент — логика предикатов. В этом уроке мы начнем изучать эту тему и освоим ее самые базовые понятия.

Логика предикатов

Логика предикатов — это расширение логики пропозиций, которую мы рассматривали ранее в курсе.

Это следующая ступень, на которой появляются два новых понятия — предикаты и квантификаторы. Эти понятия помогают лучше передать смысл утверждений, которые сложно выразить в пропозициональной логике.

Предикаты

Предикаты (P) можно рассматривать как функции, которые определяют истинность высказывания P(x) при разных значениях x. Проще говоря, предикат помогает определить, истинно высказывание или ложно.

Рассмотрим утверждение x>3. Оно состоит из двух частей:

• Переменная x — переменная высказывания
• Высказывание >3 — предикат. Он обозначает свойство, которым может обладать переменная x

Высказывание «x больше 3» можно записать как P(x). В таком случае x будет обозначать переменную, а P— предикат «больше 3».

Как только переменной x присваивается значение, высказывание P(x) становится пропозицией. У него появляется значение истинности или ложности.

Возьмем конкретное значения для x и проверим, как это работает. Для примера возьмем значение x=10 и подставим его в P(x). В итоге мы получим P(10): 10 > 3. Это истина, ведь 10 действительно больше 3.

Изучим еще один пример:

1. Представим, что предикат P(x) — это высказывание x+x=6 +
2. Присвоим переменной x значение 3 +
3. Так как мы присвоили x конкретное значение, высказывание x+x=6 становится пропозицией. Теперь можно определить, истинно оно или ложно +
4. Подставим значение и проверим, истинно или ложно высказывание 3+3=6. Получается, что для x=3 предикат P(3) — это истина +
5. А теперь поменяем значение x с 3 на 4 +
6. Высказывание x+x=6 снова становится пропозицией, и теперь можно определить, истинно оно или ложно +
7. Подставим значение и проверим, истинно или ложно высказывание 4+4=6. Получается, что для x=4 предикат P(4) — это ложь, ведь 4+4=8, а не 6

Высказывание, которое включает в себя n переменных x_1, x_2, x_3, ..., x_n:

P(x_1, x_2, x_3, ..., x_n)

Обратите внимание, что в примере выше n=2, потому что мы рассматривали 2 значения: x_1=3, x_2=4. Это можно обозначить так:

P(x_1=3, x_2=4)

В этом случае P называется n-арным предикатом.

Квантификаторы

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

Рассмотрим два высказывания:

• Вася любит вкусную еду
• Каждый человек любит вкусную еду

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

Само слово каждый — это квантификатор, а подобное выражение называется *квантифицированным**.

В логике квантификатор — это способ утверждать, что определенное количество элементов удовлетворяет каким-то определенным критериям.

В этом уроке мы рассмотрим три вида квантификаторов:

• Универсальные
• Экзистенциальные
• Квантификаторы единственности

Универсальная квантификация

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

Универсальный квантификатор обозначается символом ∀, который похож на перевернутую букву A и обозначает для всех или для любого.

Универсальная квантификация P(x) — это предложение, которое утверждает, что P(x) истинно для всех значений x.

Возьмем для примера такое выражение:

∀x(x^2≥0)

Разделим его на отдельные части и переведем на естественный язык:

• ∀x — для любого значения x
• x^2≥0 — квадрат x не отрицателен

Объединяем части и получаем понятное высказывание: «Квадрат любого числа не отрицателен».

Экзистенциальная квантификация

Некоторые математические высказывания утверждают, что элемент с определенным свойством существует — это экзистенциальная квантификация.

Экзистенциальный квантификатор обозначается символом ∃, который похож на перевернутую букву E.

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

Вернемся к примеру выше:

∃x(x^2≥0)

Превратим его в экзистенциальную квантификацию. Для этого разделим на части и переведем на естественный язык:

• ∃x — существует значение x
• x^2≥0 — квадрат x не отрицателен

В итоге получаем такое высказывание: «Существует такое число x, квадрат которого не отрицателен».

Теперь вспомним высказывание из начала урока:

Каждый человек имеет право водить машину, если он достиг восемнадцатилетнего возраста

Попробуем применить логику предикатов и преобразовать это высказывание в математическое утверждение. Получим такой результат:

∀P(x) ≡ Q(x)

В выражении выше мы видим:

• P(x) — это утверждение «x старше 18 лет»
• Q(x) — это утверждение «x имеет право водить машину»

Объединяем и получаем: «Любой x старше 18 лет имеет право водить машину».

Квантификатор единственности

Универсальные и экзистенциальные квантификаторы являются самыми важными в математике и информатике, но есть и другие. Из остальных возможных квантификаторов чаще всего встречается квантификатор единственности, который обозначается ∃!.

Например, высказывание «Существует единственный x, при котором P(x) истинно» можно записать в виде нотации ∃!x P(x).