Кванторы

Пусть – предикат, определенный на . Высказывание «для всех из истинно» обозначается . Множество не входит в обозначение и должно быть ясно из контекста. Знак называется квантором общности.

Высказывание «существует такой из , что истинно» обозначается . Знак называется квантором существования. Переход от к или называется связыванием переменной , а также навешиванием квантора на переменную (или на предикат ). Переменная, на которую навешан квантор, называется связанной, в противном случае – свободной.

Смысл связанных и свободных переменных в предикатных выражениях различен. Свободная переменная – это обычная переменная, которая может принимать различные значения из ; выражение – переменное высказывание, зависящее от значения . Выражение не зависит от переменной и при фиксированных и имеет вполне определенное значение. Переменные, являющиеся по существу связанными, встречаются не только в логике. Например, в выражениях или переменная связана. При фиксированной первое выражение равно определенному числу, а второе, функции от и .

Навешивать кванторы можно и на многоместные предикаты и вообще на любые выражения, которые при этом заключаются в скобки. Выражение, на которое навешивается квантор или , называетсяобластью действия квантора. Навешивание квантора на многоместный предикат уменьшает в нем число свободных переменных и превращает его в предикат от меньшего числа переменных.

Пример. Пусть – предикат « – четное число». Тогда высказывание истинно на любом множестве четных чисел и ложно, если содержит хотя бы одно нечетное число. Высказывание истинно на любом множестве, содержащем хотя бы одно четное число и ложно на любом множестве нечетных чисел.

Пример. Теорема Ферма формулируется, с помощью кванторов, следующим образом:

.

Пример. Пусть предикат описывает отношение « любит » на множестве людей. Для разных вариантов навешивания кванторов на обе переменные словесные интерпретации полученных формул будут различны:

– «для любого существует , которого он любит»,

– «существует такой , которого любят все »,

– «все люди любят всех людей»,

– «существует человек, который кого-то любит»,

– «существует человек, который любит всех»,

– «каждого человека кто-то любит».