Логика
Область действия кванторов
«Каждый человек любит кого-то» и «Есть кто-то, кого любят все» - звучат похоже, но означают совершенно разное. Первое всегда истинно (мама!), второе - почти никогда. Вся разница - в порядке слов «каждый» и «кого-то». Формальная логика делает эту разницу явной и точной.
- **SQL запросы:** `WHERE EXISTS (SELECT ... WHERE ...)` - порядок подзапросов определяет, ищем ли мы связь для каждой записи или одну запись для всех
- **Спецификации API:** «Каждый пользователь имеет какой-то токен» vs «Есть мастер-токен для всех пользователей» - критическая разница для безопасности
- **Юридические тексты:** «Каждый гражданин имеет право на какого-то адвоката» vs «Есть общественный защитник для всех» - разные системы правовой помощи
Область действия
**Область действия (scope)** квантора - это часть формулы, на которую он распространяется. Квантор «связывает» переменную в своей области. За пределами области переменная свободна или связана другим квантором.
**Связанная переменная** - переменная под действием квантора. **Свободная переменная** - не под квантором. Формула без свободных переменных - **замкнутая** (предложение). Формула со свободными переменными - **открытая** (предикат).
Скобки критически важны! Формула ∀x P(x) → Q(x) означает «(Если для всех x верно P(x)), то Q(x)» - здесь Q(x) со свободной переменной. А ∀x (P(x) → Q(x)) означает «Для всех x: если P(x), то Q(x)» - полностью связанная формула.
В формуле ∃y (P(x) ∧ Q(y)) какие переменные свободны?
Вложенные кванторы
Кванторы могут быть **вложенными**: один квантор внутри области действия другого. При этом **порядок кванторов критически важен** - перестановка может полностью изменить смысл формулы.
**Правило:** Кванторы одного типа (∀∀ или ∃∃) можно переставлять. Кванторы разных типов (∀∃ или ∃∀) переставлять НЕЛЬЗЯ - смысл меняется!
**Сколемизация** - техника устранения ∃ через функции. Вместо «∀x ∃y P(x,y)» пишем «∀x P(x, f(x))», где f(x) - функция, возвращающая тот y, который существует для данного x. Это используется в автоматическом доказательстве теорем.
Какое утверждение сильнее (из него следует другое)?
Разрешение неоднозначности
Естественный язык полон **неоднозначностей области действия**. Фраза «Каждый студент изучает какой-то язык» может означать либо «у каждого свой язык», либо «есть один язык, который учат все». Формализация устраняет неоднозначность.
**Широкая область (wide scope)** - квантор охватывает всю формулу. **Узкая область (narrow scope)** - квантор в подформуле. «Кто-то помогает всем» - ∃x∀y (широкий ∃) vs «Всем кто-то помогает» - ∀y∃x (широкий ∀).
При формализации всегда спрашивайте: «Один и тот же объект для всех, или для каждого свой?» Если один - экзистенциальный квантор выносится наружу (широкая область). Если разные - остаётся внутри (узкая область).
«Каждый программист знает какой-то язык программирования» - какая формализация отражает естественное прочтение?
Формальный перевод
**Перевод с естественного языка на язык предикатов** - ключевой навык. Шаги: 1) определить предикаты; 2) определить домены переменных; 3) выбрать кванторы и их порядок; 4) расставить скобки для области действия.
**Типичные паттерны:** «Все A есть B» → ∀x(A(x) → B(x)). «Некоторые A есть B» → ∃x(A(x) ∧ B(x)). «Никакие A не есть B» → ∀x(A(x) → ¬B(x)) или ¬∃x(A(x) ∧ B(x)). «Не все A есть B» → ∃x(A(x) ∧ ¬B(x)).
**Ловушка:** «Все A есть B» - это ∀x(A(x) → B(x)), а НЕ ∀x(A(x) ∧ B(x))! Конъюнкция утверждала бы, что ВСЁ в мире есть и A, и B. Импликация говорит: «если что-то A, то оно B» - правильный перевод.
«Все A есть B» переводится как ∀x(A(x) ∧ B(x))
«Все A есть B» переводится как ∀x(A(x) → B(x))
Конъюнкция ∀x(A(x) ∧ B(x)) означает «всё в мире есть и A, и B» - абсурд. Импликация ∀x(A(x) → B(x)) означает «если нечто есть A, то оно B» - правильный перевод универсальных утверждений.
Как формализовать «Некоторые студенты не сдали ни одного экзамена»?
Ключевые идеи
- **Область действия** определяет, какие переменные связаны квантором
- **Порядок кванторов** критически важен: ∀x∃y ≠ ∃y∀x
- **Широкая область** - квантор снаружи, один объект для всех
- **Узкая область** - квантор внутри, разные объекты для каждого
- **Перевод:** «Все A есть B» → ∀x(A(x) → B(x)), НЕ конъюнкция!
Связанные темы
Области действия - ключ к точному выражению мыслей:
- Предикаты и кванторы — Основа - понимание ∀ и ∃
- Отрицание кванторов — Как отрицание взаимодействует с областью действия
- Неоднозначности — Области действия - частый источник неоднозначности
Вопросы для размышления
- Придумайте предложение на естественном языке с двумя разными прочтениями из-за области действия кванторов.
- В программировании: как область видимости переменных (scope) связана с областью действия кванторов?
- Почему юридические документы часто избегают слов «все» и «некоторые» в пользу более явных формулировок?