Ранее в курсе мы изучали только пропозициональную логику: использовали пропозиции с нотациями, на их примерах рассматривали софизмы и эквивалентные высказывания.
Но есть ситуации, которые невозможно адекватно описать терминами логики пропозиций. Например:
Каждый человек имеет право водить машину, если он достиг восемнадцатилетнего возраста
С помощью логики пропозиций нельзя решить, истинно это высказывание или ложно, потому что это утверждение относится ко всем людям, а не к конкретному человеку.
Здесь нужен более мощный инструмент — логика предикатов. В этом уроке мы начнем изучать эту тему и освоим ее самые базовые понятия.
Логика предикатов
Логика предикатов — это расширение логики пропозиций, которую мы рассматривали ранее в курсе.
Это следующая ступень, на которой появляются два новых понятия — предикаты и квантификаторы. Эти понятия помогают лучше передать смысл утверждений, которые сложно выразить в пропозициональной логике.
Предикаты
Предикаты ( ) можно рассматривать как функции, которые определяют истинность высказывания при разных значениях . Проще говоря, предикат помогает определить, истинно высказывание или ложно.
Рассмотрим утверждение . Оно состоит из двух частей:
-
Переменная — переменная высказывания
-
Высказывание — предикат. Он обозначает свойство, которым может обладать переменная
Высказывание « больше » можно записать как . В таком случае будет обозначать переменную, а — предикат «больше ».
Как только переменной присваивается значение, высказывание становится пропозицией. У него появляется значение истинности или ложности.
Возьмем конкретное значения для и проверим, как это работает. Для примера возьмем значение и подставим его в . В итоге мы получим . Это истина, ведь действительно больше .
Изучим еще один пример:
-
Представим, что предикат — это высказывание
-
Присвоим переменной значение
-
Так как мы присвоили конкретное значение, высказывание становится пропозицией. Теперь можно определить, истинно оно или ложно
-
Подставим значение и проверим, истинно или ложно высказывание . Получается, что для предикат — это истина
-
А теперь поменяем значение с на
-
Высказывание снова становится пропозицией, и теперь можно определить, истинно оно или ложно
-
Подставим значение и проверим, истинно или ложно высказывание . Получается, что для предикат — это ложь, ведь , а не
Высказывание, которое включает в себя переменных , , , , :
, , , ,
Обратите внимание, что в примере выше , потому что мы рассматривали значения: , . Это можно обозначить так:
( , )
В этом случае называется n-арным предикатом.
Квантификаторы
Часто у нас возникает необходимость проверить истинность высказывания не с конкретным значением, а сразу на диапазоне значений. В этом и помогают квантификаторы.
Рассмотрим два высказывания:
-
Вася любит вкусную еду
-
Каждый человек любит вкусную еду
В обоих высказываниях есть критерий: любит вкусную еду. В первом высказывании Вася — это конкретное значение. Во втором случае слово каждый указывает, что в качестве переменной мы рассматриваем много людей, то есть диапазон значений.
Само слово каждый — это квантификатор, а подобное выражение называется квантифицированным.
В логике квантификатор — это способ утверждать, что определенное количество элементов удовлетворяет каким-то определенным критериям.
В этом уроке мы рассмотрим три вида квантификаторов:
-
Универсальные
-
Экзистенциальные
-
Квантификаторы единственности
Универсальная квантификация
Иногда в математических высказываниях утверждается, что любое значение переменной удовлетворяет критерию. Такое утверждение называется универсальной квантификацией.
Универсальный квантификатор обозначается символом , который похож на перевернутую букву и обозначает для всех или для любого.
Универсальная квантификация — это предложение, которое утверждает, что истинно для всех значений .
Возьмем для примера такое выражение:
Разделим его на отдельные части и переведем на естественный язык:
-
— для любого значения
-
— квадрат не отрицателен
Объединяем части и получаем понятное высказывание: «Квадрат любого числа не отрицателен».
Экзистенциальная квантификация
Некоторые математические высказывания утверждают, что элемент с определенным свойством существует — это экзистенциальная квантификация.
Экзистенциальный квантификатор обозначается символом , который похож на перевернутую букву .
С помощью экзистенциальной квантификации можно сформировать предложение, которое истинно, только если истинно хотя бы для одного значения в области.
Вернемся к примеру выше:
Превратим его в экзистенциальную квантификацию. Для этого разделим на части и переведем на естественный язык:
-
— существует значение
-
— квадрат не отрицателен
В итоге получаем такое высказывание: «Существует такое число , квадрат которого не отрицателен».
Теперь вспомним высказывание из начала урока:
Каждый человек имеет право водить машину, если он достиг восемнадцатилетнего возраста
Попробуем применить логику предикатов и преобразовать это высказывание в математическое утверждение. Получим такой результат:
В выражении выше мы видим:
-
— это утверждение « старше 18 лет»
-
— это утверждение « имеет право водить машину»
Объединяем и получаем: «Любой старше 18 лет имеет право водить машину».
Квантификатор единственности
Универсальные и экзистенциальные квантификаторы являются самыми важными в математике и информатике, но есть и другие. Из остальных возможных квантификаторов чаще всего встречается квантификатор единственности, которые обозначается .
Например, высказывание «Существует единственный , при котором истинно» можно записать в виде нотации .
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
- Статья «Как учиться и справляться с негативными мыслями»
- Статья «Ловушки обучения»
- Статья «Сложные простые задачи по программированию»
- Вебинар «Как самостоятельно учиться»
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
