Введение в математическую логику
2026-02-26 17:29 Diff
https://ru.hexlet.io/courses/logic/lessons/predicates_and_quantifiers/theory_unit

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

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

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

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

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

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

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

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

Предикаты

Предикаты (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:

Обратите внимание, что в примере выше n=2, потому что мы рассматривали 2 значения: 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).