Квантор
Ква́нтор — общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих высказывание. Чаще всего упоминают:
- Квантор всеобщности (обозначение: [math]\displaystyle{ \forall }[/math], читается: «для любого…», «для каждого…», «для всех…» или «каждый…», «любой…», «все…»).
- Квантор существования (обозначение: [math]\displaystyle{ \exists }[/math], читается: «существует…» или «найдётся…»).
В математической логике приписывание квантора к формуле называется связыванием или квантификацией.[источник не указан 2976 дней]
В многозначных логиках также вводятся и другие кванторы, например, квантор плюральности (квантор Решера) (обозначается перевёрнутой M, читается «для большинства …»).
Примеры
Обозначим [math]\displaystyle{ P(x) }[/math] предикат «x делится на 9». Используя квантор всеобщности, можно формально записать следующие высказывания (конечно, ложные):
- любое натуральное число кратно 9;
- каждое натуральное число кратно 9;
- все натуральные числа кратны 9;
следующим образом:
- [math]\displaystyle{ (\forall x \in \mathbb{N}) P(x) }[/math].
Следующие (уже истинные) высказывания используют квантор существования:
- существуют натуральные числа, кратные 9;
- найдётся натуральное число, кратное 9;
- хотя бы одно натуральное число кратно 9.
Их формальная запись:
- [math]\displaystyle{ (\exists x \in \mathbb{N}) P(x) }[/math].
Введение в понятие
Пусть на множестве [math]\displaystyle{ X }[/math] простых чисел задан предикат [math]\displaystyle{ P(x) }[/math]: «Простое число [math]\displaystyle{ x }[/math] нечётно». Подставим перед этим предикатом слово «любое». Получим ложное высказывание «любое простое число [math]\displaystyle{ x }[/math] нечётно» (это высказывание ложно, так как 2 — простое чётное число).
Подставив перед данным предикатом [math]\displaystyle{ P(x) }[/math] слово «существует», получим истинное высказывание «Существует простое число [math]\displaystyle{ x }[/math], являющееся нечётным» (например, [math]\displaystyle{ x=3 }[/math]).
Таким образом, превратить предикат в высказывание можно, поставив перед предикатом слова («все», «существует» и другие), называемые в логике кванторами.
Кванторы в математической логике
- Высказывание [math]\displaystyle{ \forall xP(x) }[/math] означает, что область значений переменной [math]\displaystyle{ x }[/math] включена в область истинности предиката [math]\displaystyle{ P(x) }[/math].
(«При всех значениях [math]\displaystyle{ x }[/math] утверждение верно»).
- Высказывание [math]\displaystyle{ \exists xP(x) }[/math] означает, что область истинности предиката [math]\displaystyle{ P(x) }[/math] не пуста.
(«Существует [math]\displaystyle{ x }[/math], при котором утверждение верно»).
Свободные и связанные переменные
Множество свободных переменных* формулы F определяется рекурсивно, следующим образом:
Свободные переменные.
- Все переменные, входящие в атомарную формулу, являются свободными переменными этой формулы,
- свободные переменные формулы F являются свободными переменными формулы ¬F,
- переменные, являющиеся свободными для хотя бы одной из формул F или G, являются свободными переменными формулы (F Д G),
- все свободные переменные формулы F кроме v являются свободными переменными формулы Kv F.
Замкнутая формула.
- Формула без свободных переменных называется замкнутой формулой, или предложением.
Связанная переменная.
- Переменная v связана в формуле F, если F содержит вхождение Kv, где K — квантор.
Связанное переименование, свободное переименование
Операции над кванторами
Правило отрицания кванторов — применяется для построения отрицаний высказываний, содержащих кванторы, и имеет вид:
[math]\displaystyle{ \lnot (\forall x)P(x) = (\exists x) \lnot P(x) }[/math]
[math]\displaystyle{ \lnot (\exists x)P(x) = (\forall x) \lnot P(x) }[/math]
История появления
Философы давно обращали внимание на логические операции, ограничивающие область истинности предиката, однако не выделяли их в отдельный класс операций. Так, Томас Гоббс считал, что они являются частями имён[1].
Хотя кванторно-логические конструкции широко используются как в научной, так и в обыденной речи, их формализация произошла только в 1879 г., в книге Фреге «Исчисление понятий». Обозначения Фреге имели вид громоздких графических конструкций и не были приняты. Впоследствии было предложено множество более удачных символов, но общепринятыми стали обозначения [math]\displaystyle{ \exists }[/math] для квантора существования (перевёрнутая первая буква англ. Exists — существует), предложенное Чарльзом Пирсом в 1885 г., и [math]\displaystyle{ \forall }[/math] для квантора общности (нем. Alle[источник не указан 3764 дня] — «все», «всякий»), образованное Герхардом Генценом в 1935 г. по аналогии с символом квантора существования. Термины «квантор», «квантификация» также предложил Пирс.
Примечания
- ↑ «Но слова: всякое, любое, некоторое и т. д., указывающие на всеобщее или частное значение других слов, являются не именами, а только частями имен». (Томас Гоббс «О теле»)
Литература
- Клини С. К. Введение в метаматематику, пер. с англ., М., 1957, с. 72—80, 130—138
- Колмогоров А. Н., Драгалин А. Г. Математическая логика. Изд. 3-е, стереотипное. — М.: КомКнига, 2006. — 240 с.
- Новиков П. С. Элементы математической логики. — М.: Наука, 1973. — 400 с.
- Чёрч А. Введение в математическую логику, пер. с англ., т. 1, М., 1960, с. 42—48.