Квантор

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

• Квантор всеобщности (обозначение: ∀ {displaystyle forall } , читается: «для любого…», «для каждого…», «для всех…» или «каждый…», «любой…», «все…»).
• Квантор существования (обозначение: ∃ {displaystyle exists } , читается: «существует…» или «найдётся…»).

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

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

Примеры

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

любое натуральное число кратно 9;

каждое натуральное число кратно 9;

все натуральные числа кратны 9;

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

( ∀ x ∈ N ) P ( x ) {displaystyle (forall xin mathbb {N} )P(x)} .

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

существуют натуральные числа, кратные 9;

найдётся натуральное число, кратное 9;

хотя бы одно натуральное число кратно 9.

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

( ∃ x ∈ N ) P ( x ) {displaystyle (exists xin mathbb {N} )P(x)} .

Введение в понятие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

¬ ( ∀ x ) P ( x ) = ( ∃ x ) ¬ P ( x ) {displaystyle lnot (forall x)P(x)=(exists x)lnot P(x)}
¬ ( ∃ x ) P ( x ) = ( ∀ x ) ¬ P ( x ) {displaystyle lnot (exists x)P(x)=(forall x)lnot P(x)}

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

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

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