Квантор

Ква́нтор — общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих высказывание. Чаще всего упоминают:

• Квантор всеобщности (обозначение: $\mathrm{\forall <!--\; \forall \; -->}$$\forall$, читается: «для любого…», «для каждого…», «для всех…» или «каждый…», «любой…», «все…»).
• Квантор существования (обозначение: $\mathrm{\exists <!--\; \exists \; -->}$$\exists$, читается: «существует…» или «найдётся…»).

В математической логике приписывание квантора к формуле называется связыванием или квантификацией.

В многозначных логиках также вводятся и другие кванторы, например, квантор плюральности (квантор Решера) (обозначается перевёрнутой M, читается «для большинства …»).

ПримерыПравить

Обозначим $P(x)$$P(x)$  предикат «x делится на 9». Используя квантор всеобщности, можно формально записать следующие высказывания (конечно, ложные):

1. любое натуральное число кратно 9;
2. каждое натуральное число кратно 9;
3. все натуральные числа кратны 9;

следующим образом:

$(\mathrm{\forall <!--\; \forall \; -->}x\in <!--\; \in \; -->\mathbb{N})P(x)$$(\forall x\in {\mathbb {N}})P(x)$ .

Следующие (уже истинные) высказывания используют квантор существования:

1. существуют натуральные числа, кратные 9;
2. найдётся натуральное число, кратное 9;
3. хотя бы одно натуральное число кратно 9.

Их формальная запись:

$(\mathrm{\exists <!--\; \exists \; -->}x\in <!--\; \in \; -->\mathbb{N})P(x)$$(\exists x\in {\mathbb {N}})P(x)$ .

Введение в понятиеПравить

Пусть на множестве $X$$X$  простых чисел задан предикат $P(x)$$P(x)$ : «Простое число $x$$x$  нечётно». Подставим перед этим предикатом слово «любое». Получим ложное высказывание «любое простое число $x$$x$  нечётно» (это высказывание ложно, так как 2 — простое чётное число).

Подставив перед данным предикатом $P(x)$$P(x)$  слово «существует», получим истинное высказывание «Существует простое число $x$$x$ , являющееся нечётным» (например, $x=3$$x=3$ ).

Таким образом, превратить предикат в высказывание можно, поставив перед предикатом слова («все», «существует» и другие), называемые в логике кванторами.

Кванторы в математической логикеПравить

• Высказывание $\mathrm{\forall <!--\; \forall \; -->}xP(x)$$\forall xP(x)$  означает, что область значений переменной $x$$x$  включена в область истинности предиката $P(x)$$P(x)$ .

(«При всех значениях $x$$x$  утверждение верно»).

• Высказывание $\mathrm{\exists <!--\; \exists \; -->}xP(x)$$\exists xP(x)$  означает, что область истинности предиката $P(x)$$P(x)$  не пуста.

(«Существует $x$$x$ , при котором утверждение верно»).

Свободные и связанные переменныеПравить

Множество свободных переменных* формулы F определяется рекурсивно, следующим образом:

Свободные переменные.

• Все переменные, входящие в атомарную формулу, являются свободными переменными этой формулы,
• свободные переменные формулы F являются свободными переменными формулы ¬F,
• переменные, являющиеся свободными для хотя бы одной из формул F или G, являются свободными переменными формулы (F Д G),
• все свободные переменные формулы F кроме v являются свободными переменными формулы Kv F.

Замкнутая формула.

• Формула без свободных переменных называется замкнутой формулой, или предложением.

Связанная переменная.

• Переменная v связана в формуле F, если F содержит вхождение Kv, где K — квантор.

Связанное переименование, свободное переименование

Операции над кванторамиПравить

Правило отрицания кванторов — применяется для построения отрицаний высказываний, содержащих кванторы, и имеет вид:

$\mathrm{\neg <!--\; \neg \; -->}(\mathrm{\forall <!--\; \forall \; -->}x)P(x)=(\mathrm{\exists <!--\; \exists \; -->}x)\mathrm{\neg <!--\; \neg \; -->}P(x)$$\lnot (\forall x)P(x)=(\exists x)\lnot P(x)$ 
$\mathrm{\neg <!--\; \neg \; -->}(\mathrm{\exists <!--\; \exists \; -->}x)P(x)=(\mathrm{\forall <!--\; \forall \; -->}x)\mathrm{\neg <!--\; \neg \; -->}P(x)$$\lnot (\exists x)P(x)=(\forall x)\lnot P(x)$ 

История появленияПравить

Философы давно обращали внимание на логические операции, ограничивающие область истинности предиката, однако не выделяли их в отдельный класс операций. Так, Томас Гоббс считал, что они являются частями имён.

Хотя кванторно-логические конструкции широко используются как в научной, так и в обыденной речи, их формализация произошла только в 1879 г., в книге Фреге «Исчисление понятий». Обозначения Фреге имели вид громоздких графических конструкций и не были приняты. Впоследствии было предложено множество более удачных символов, но общепринятыми стали обозначения $\mathrm{\exists <!--\; \exists \; -->}$$\exists$  для квантора существования (перевёрнутая первая буква англ. Exists — существует), предложенное Чарльзом Пирсом в 1885 г., и $\mathrm{\forall <!--\; \forall \; -->}$$\forall$  для квантора общности (нем. Alle — «все», «всякий»), образованное Герхардом Генценом в 1935 г. по аналогии с символом квантора существования. Термины «квантор», «квантификация» также предложил Пирс.

ЛитератураПравить

• Клини С. К. Введение в метаматематику, пер. с англ., М., 1957, с. 72—80, 130—138
• Колмогоров А. Н., Драгалин А. Г. Математическая логика. Изд. 3-е, стереотипное. — М.: КомКнига, 2006. — 240 с.
• Новиков П. С. Элементы математической логики. — М.: Наука, 1973. — 400 с.
• Чёрч А. Введение в математическую логику, пер. с англ., т. 1, М., 1960, с. 42—48.

СсылкиПравить

• Кванторы