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

Почему силлогизм Аристотеля «Все люди смертны. Сократ - человек. Следовательно, Сократ смертен» работает? Пропозициональная логика не может объяснить: для неё «Все люди смертны» и «Сократ смертен» - просто разные буквы P и Q. Предикатная логика раскрывает внутреннюю структуру утверждений.

• **Базы данных:** SQL-запрос `SELECT * FROM users WHERE age > 18 AND country = 'RU'` - это комбинация предикатов. `EXISTS` и `ALL` - это кванторы
• **Программирование:** Методы `every()`, `some()`, `filter()`, `find()` - реализации кванторов и предикатов из логики первого порядка
• **Математика:** Определения и теоремы формулируются с кванторами. «∀ε>0 ∃δ>0: |x-a|<δ → |f(x)-f(a)|<ε» - определение непрерывности

Предикат

В пропозициональной логике мы работали с **целыми высказываниями** как неделимыми единицами: P, Q, R. Но утверждение «Сократ смертен» имеет структуру: **субъект** (Сократ) и **свойство** (смертен). **Предикат** - это свойство или отношение, которое можно применить к объектам.

**Предикат** - это функция, которая принимает объект(ы) и возвращает истину или ложь. Запись: P(x), где P - предикат, x - переменная. Примеры: Смертен(x), Больше(x, y), Между(x, y, z).

В программировании предикаты - это **функции, возвращающие boolean**. Метод `isEven(n)` - предикат. Фильтр `array.filter(x => x > 0)` использует предикат `x => x > 0`. SQL-условие `WHERE age > 18` - тоже предикат.

Кванторы

Предикаты становятся по-настоящему мощными с **кванторами** - операторами, которые говорят, **сколько** объектов удовлетворяют предикату. Два основных квантора: **универсальный** (∀ - «для всех») и **экзистенциальный** (∃ - «существует»).

**∀x P(x)** читается «для всех x верно P(x)» или «каждый x обладает свойством P». **∃x P(x)** читается «существует x такой, что P(x)» или «хотя бы один x обладает свойством P».

Кванторы можно комбинировать. Порядок важен! «∀x ∃y Любит(x, y)» означает «каждый кого-то любит» (у каждого есть объект любви, возможно разный). А «∃y ∀x Любит(x, y)» - «есть кто-то, кого любят все» (один объект всеобщей любви).

Универсальный квантор

**Универсальный квантор ∀** (читается «для всех» или «для любого») утверждает, что свойство выполняется для **каждого** объекта из рассматриваемой области. Это самое сильное утверждение - достаточно одного контрпримера, чтобы его опровергнуть.

**Домен (область определения)** - множество объектов, по которому пробегает переменная. «Все лебеди белые» при домене {австралийские лебеди} ложно, при домене {европейские лебеди} - веками считалось истинным.

**Вакуумная истинность:** утверждение ∀x (P(x) → Q(x)) истинно, если **нет объектов, удовлетворяющих P**. «Все единороги розовые» - истинно (нет единорогов для проверки). Это часто контринтуитивно, но математически корректно.

Экзистенциальный квантор

**Экзистенциальный квантор ∃** (читается «существует» или «для некоторого») утверждает, что свойство выполняется **хотя бы для одного** объекта. Это слабое утверждение - достаточно одного примера, чтобы его доказать.

**Связь кванторов через отрицание (законы де Моргана для кванторов):** ¬(∀x P(x)) ≡ ∃x ¬P(x) и ¬(∃x P(x)) ≡ ∀x ¬P(x). «Не все студенты сдали» = «Существует несдавший». «Не существует бессмертного» = «Все смертны».

**Уникальность:** иногда нужно сказать «существует **ровно один**». Обозначается ∃! (читается «существует единственный»). ∃!x P(x) означает: ∃x P(x) ∧ ∀y∀z (P(y) ∧ P(z) → y = z) - существует и единственный.

Ключевые идеи

• **Предикат:** функция от объектов, возвращающая истину или ложь - P(x), Q(x, y)
• **∀ (для всех):** утверждение о каждом объекте, опровергается одним контрпримером
• **∃ (существует):** утверждение о существовании, доказывается одним примером
• **Де Морган:** ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
• **Порядок кванторов важен:** ∀x∃y ≠ ∃y∀x в общем случае

Связанные темы

Предикатная логика - основа формальных систем:

• Нормальные формы — Предикатная логика имеет свои нормальные формы (Сколема, Пренекса)
• Дедукция — Силлогизмы Аристотеля формализуются в предикатной логике
• Множества — Множества определяются через предикаты: {x | P(x)}

Вопросы для размышления

• Как бы вы формализовали «Каждый программист иногда делает ошибки» с помощью кванторов?
• Почему в SQL есть и `EXISTS`, и `NOT EXISTS`, а не просто отрицание?
• Приведите пример утверждения, которое меняет смысл при перестановке кванторов.

Связанные уроки

• comp-18-type-checking
• ml-02