Тема 12.3. Кванторы

Но есть и две новые операции, специфические. Они называются несколько вызывающе – операциями навешивания кванторов. Эти операции соответствуют фразам «для всех» – квантор общности и «некоторые» – квантор существования. Следует немного сказать о значках, которые при этом используются, в силу их экзотичности. Квантор общности произошёл от английского «All» и обозначается буквой A, перевернутой вверх ногами (). Квантор существования произошёл от английского Exist и обозначается буквой E, которую вверх ногами переворачивать бесполезно, поэтому её повернули кругом ().

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

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

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

Пример 12.5: В выражениях или переменная связана: при фиксированной функции первое выражение равно определённому числу, а второе становится функцией от пределов интегрирования.

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

Пример 12.6:

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

Рассмотрим двухместный предикат на множествах с отношением нестрогого порядка. Предикат есть одноместный предикат от переменной . Если – множество неотрицательных чисел, то этот предикат истинен в единственной точке . Предикат (можно записать ) высказывание истинное на множестве, состоящем из одного элемента и ложное на всяком другом множестве. Высказывание утверждает, что в множестве имеется максимальный элемент (для любого существует такой , что ). Оно истинно на любом конечном множестве целых чисел. Высказывание утверждает, что для любого элемента имеется элемент , не меньший его. Оно истинно на любом непустом множестве ввиду рефлексивности отношения . Последние два высказывания говорят о том, что перестановка кванторов меняет смысл высказывания и условие его истинности.

Дата добавления: 2015-10-28