Ранее в курсе мы изучали только пропозициональную логику: использовали пропозиции с нотациями, на их примерах рассматривали софизмы и эквивалентные высказывания.
Но есть ситуации, которые невозможно адекватно описать терминами логики пропозиций. Например:
Каждый человек имеет право водить машину, если он достиг восемнадцатилетнего возраста
С помощью логики пропозиций нельзя решить, истинно это высказывание или ложно, потому что это утверждение относится ко всем людям, а не к конкретному человеку.
Здесь нужен более мощный инструмент — логика предикатов. В этом уроке мы начнем изучать эту тему и освоим ее самые базовые понятия.
Логика предикатов
Логика предикатов — это расширение логики пропозиций, которую мы рассматривали ранее в курсе.
Это следующая ступень, на которой появляются два новых понятия — предикаты и квантификаторы. Эти понятия помогают лучше передать смысл утверждений, которые сложно выразить в пропозициональной логике.
Предикаты
Предикаты (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.
Изучим еще один пример:
- Представим, что предикат
P(x)— это высказываниеx+x=6+ - Присвоим переменной
xзначение3+ - Так как мы присвоили
xконкретное значение, высказываниеx+x=6становится пропозицией. Теперь можно определить, истинно оно или ложно + - Подставим значение и проверим, истинно или ложно высказывание
3+3=6. Получается, что дляx=3предикатP(3)— это истина + - А теперь поменяем значение
xс3на4+ - Высказывание
x+x=6снова становится пропозицией, и теперь можно определить, истинно оно или ложно + - Подставим значение и проверим, истинно или ложно высказывание
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— для любого значенияxx^2≥0— квадратxне отрицателен
Объединяем части и получаем понятное высказывание: «Квадрат любого числа не отрицателен».
Экзистенциальная квантификация
Некоторые математические высказывания утверждают, что элемент с определенным свойством существует — это экзистенциальная квантификация.
Экзистенциальный квантификатор обозначается символом ∃, который похож на перевернутую букву E.
С помощью экзистенциальной квантификации можно сформировать предложение, которое истинно, только если P(x) истинно хотя бы для одного значения x в области.
Вернемся к примеру выше:
∃x(x^2≥0)
Превратим его в экзистенциальную квантификацию. Для этого разделим на части и переведем на естественный язык:
∃x— существует значениеxx^2≥0— квадратxне отрицателен
В итоге получаем такое высказывание: «Существует такое число x, квадрат которого не отрицателен».
Теперь вспомним высказывание из начала урока:
Каждый человек имеет право водить машину, если он достиг восемнадцатилетнего возраста
Попробуем применить логику предикатов и преобразовать это высказывание в математическое утверждение. Получим такой результат:
∀P(x) ≡ Q(x)
В выражении выше мы видим:
P(x)— это утверждение «xстарше 18 лет»Q(x)— это утверждение «xимеет право водить машину»
Объединяем и получаем: «Любой x старше 18 лет имеет право водить машину».
Квантификатор единственности
Универсальные и экзистенциальные квантификаторы являются самыми важными в математике и информатике, но есть и другие. Из остальных возможных квантификаторов чаще всего встречается квантификатор единственности, который обозначается ∃!.
Например, высказывание «Существует единственный x, при котором P(x) истинно» можно записать в виде нотации ∃!x P(x).
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
