Квантор

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Примеры[править | править вики-текст]

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

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

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

(\forall x \in \mathbb{N}) P(x).

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

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

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

 (\exists x \in \mathbb{N}) P(x).

Введение в понятие[править | править вики-текст]

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

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

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

Кванторы в математической логике[править | править вики-текст]

  • Высказывание \forall xP(x) означает, что область значений переменной x включена в область истинности предиката P(x).

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

  • Высказывание \exists xP(x) означает, что область истинности предиката P(x) непуста.

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


Свободные и связанные переменные[править | править вики-текст]

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

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

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

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

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

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

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

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

Операции над кванторами[править | править вики-текст]

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

\lnot (\forall x)P(x) = (\exists x) \lnot P(x)
\lnot (\exists x)P(x) = (\forall x) \lnot P(x)


История появления[править | править вики-текст]

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

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

Литература[править | править вики-текст]

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

Ссылки[править | править вики-текст]

Примечания[править | править вики-текст]

  1. «Но слова: всякое, любое, некоторое и т. д., указывающие на всеобщее или частное значение других слов, являются не именами, а только частями имен». (Томас Гоббс «О теле»)


A