Квантор всеобщности

Среди примеров, приведенных выше, S(x) — предикат —1 < sin(x) < 1, где х принадлежит множеству действительных чисел. Тот факт, что для любого значения х -1 < sin(x) < 1, дает основание сказать, что для любого х истинно S(x), что символически изображается как ∀ xS(x)

или

∀ x(-1 < sin(x) < 1).

Символ ∀ x называется универсальным квантором, или квантором всеобщности, и читается " для любого х" или " для всех х". Множество значений, которое может принимать х, называется универсом, или предметной областью. В частности, предметной областью может являться множество действительных чисел, множество целых чисел или другие подобные множества. Вообще говоря, истинность утверждения с квантором всеобщности зависит от предметной области.

Например, высказывание ∀ x(x² > 5)

не истинно, если универсом (предметной областью) является множество целых чисел; однако, оно было бы истинным, если в качестве предметной области взять

множество целых чисел, больших чем 2. Точно так же высказывание ∀ x(x² > 0) истинно, если предметная область — множество действительных чисел, но ложно, если предметная область содержит комплексное число i, т.к. i² = — 1.

Предикат ∀ x∀ y R(x, y) читается как " для каждого х, для каждого у имеет место R(х, у)" или " для каждого х и для каждого у имеет место R(x, у)". Предикат ∀ х∀ уR(x, y) истинный только тогда, когда для любого набора значений х и у из соответствующей предметной области х² + у² > 0 истинно. Если предметной областью для х и для у является множество действительных чисел, то ∀ х∀ уR(x, y).

Квантор существования ∃ x P(x)

Высказывание ∃ х(х² = 4) истинно, если предметной областью есть множество действительных чисел, т.к. х² = 4 истинно для х = 2. Высказывание ∃ х(х² = 5) также истинно, если предметной областью есть множество действительных чисел; однако, оно не является истинным, если предметная область есть множество целых чисел, так как не существует целого числа, квадрат которого равен 5.

Поскольку для предиката Q(x, y, z) высказывания Q(1, 2, 0) и Q(-3, 4, 5) истинны, то высказывание ∃ x∃ y∃ z Q(x, y, z) истинно.

Чтобы предикат был высказыванием, все его переменные должны иметь конкретные значения или быть связаны соответствующим квантором. Например, (∃ x)(∀ z)Q(x, y, z)

не является высказыванием, т.к. переменная у не связана никаким квантором.

Если D{x) — предикат, то высказывание ∀ xD(x) истинно только тогда, когда высказывание -D(x) истинно для любого х. Когда же высказывание ∀ xD(x) будет ложным? Отрицание может быть записано как Ø ∀ xD(x)

Тождества:

Ø ∀ x(D(x))=∃ x(Ø D(x))

Ø ∃ x(G(x)) = ∀ x(Ø G(x))

Для образования отрицания с навешенным квантором всеобщности нужно заменить ∀ x на ∃ х и взять отрицание предиката, следующего за квантором. А для формирования отрицания предиката с навешенным квантором существования нужно заменить ∃ х на ∀ x и взять отрицание предиката, следующего за квантором.

Отрицание высказывания, содержащего более одного квантора, осуществляется путем последовательного рассмотрения каждого квантора, начиная с первого.

Например:

Аналогично:

Следовательно, для отрицания высказывания, содержащего кванторы, ∃ заменяется на ∀ и наоборот, после чего берется отрицание предиката, связанного с этой последовательностью кванторов.

Определения:

1) Универсальная конкретизация Из истинности ∀ xP(x) следует истинность Р(а) для произвольного а из универса.

2) Универсальное обобщение Если произвольное а из универса обеспечивает истинность Р{а), делаем вывод, что ∀ x(P(x) истинно.

3) Экзистенциональная конкретизация Из истинности ∃ хР(х) следует, что существует конкретное b такое, что Р(x) истинно.

4) Экзистенциональное обобщение Из существования конкретного с из универса, для которого Р(с) истинно, можно сделать вывод, что ∃ хР(х).

ТЕОРЕМА Для произвольных предикатов Р(х) и Q(x), имеющих одну предметную область,

а) ∀ x(P(x) Ù Q(x)) = ∀ xP(x) ∀ xQ(x);

б) ∃ x(P(x) Q(x)) = ∃ xP(x)Ú ∃ xQ(x);

в) из ∀ xP(x) Ú ∀ xQ(x) следует, что ∀ x(P(x) Ú Q(x))

г) из ∃ х(Р(х) Ù Q(x)) следует, что ∃ хР(х) Ù ∃ xQ(x).