Лекция №12

Тема: ПРЕДИКАТЫ С НЕОГРАНИЧЕННЫМИ КВАНТОРАМИ

Основные вопросы, рассматриваемые на лекции:

1. Определение смысла кванторов

2. Основные свойства кванторов в виде эквивалентности

3. Основные свойства кванторов в виде импликации

Краткое содержание лекционного материала

Кванторы вида $ x и " x называются также неограниченными. Эти, неограниченные, кванторы рассматриваются в основном в математической логике. Далее мы неограниченные кванторы называем просто кванторами.

Выясним смысл кванторов. Для простоты рассмотрим навешивание кванторов $ x и " x к предикату P (x) с одной свободной переменной (в общем случае остальные свободные переменные принимают фиксированные значения). Предложения $ xP (x) (подтверждение P (x) переменной x) и " xP (x) (обобщение P (x) переменной x) являются высказываниями, истинностные значения которых определяются по следующим правилам (D – множество допустимых значений переменной x):

Если множество D ={ a ₁,…, a_k } конечно, то подтверждение равносильно дизъюнкции, а обобщение – конъюнкции: $ xP (x)º P (a ₁)Ú…Ú P (a_k) и " xP (x)º P (a ₁)Ù…Ù P (a_k).

Если P (x) не содержит y, то $ xP (x)º$ yP (y) и " xP (x)º" yP (y).

Если переменные x и y – различные, то $ yP (x)º" yP (x)º P (x).

Основные свойства кванторов представляют собой либо равносильности, либо необратимые импликации. Эти свойства можно "доказывать", используя определения операций Ø, Ú, Ù и операций навешивания кванторов, и опираясь на здравый смысл.

Свойства кванторов – равносильности.

(1) $ x (P (x)Ú Q (x))º$ xP (x)Ú$ xQ (x).

Действительно, $ x (P (x)Ú Q (x))ºИ (подтверждение)Û

P (a)Ú Q (a))ºИ для некоторого a Î D (дизъюнкция)Û

P (a)ºИ или Q (a))ºИ для некоторого a Î D (подтверждение)Û

$ xP (x)ºИ или $ xQ (x)ºИ (дизъюнкция)Û

$ xP (x)Ú$ xQ (x)ºИ.

(2) " x (P (x)Ù Q (x))º" xP (x)Ù" xQ (x).

(3) $ x $ yP (x, y)º$ y $ xP (x, y);

Действительно, $ x $ yP (x, y)ºИ (подтверждение)Û

$ yP (a, y)ºИ для некоторого a Î D (подтверждение)Û

P (a, b)ºИ для некоторых a, b Î D (подтверждение)Û

$ xP (x, b)ºИ для некоторого b Î D (подтверждение)Û

$ y $ xP (x, y)ºИ.

(4) " x " yP (x, y)º" y " xP (x, y).

(5) Ø$ xP (x)º" x Ø P (x).

Действительно, Ø$ xP (x)ºИ (отрицание)Û

$ xP (x)ºЛ (подтверждение)Û

P (a)ºЛ для всех a Î D (отрицание)Û

Ø P (a)ºИ для всех a Î D (обобщение)Û

" x Ø P (x)ºИ.

(6) Ø" xP (x)º$ x Ø P (x).

Свойства кванторов – истинные импликации (или следствия).

(7) P (a)Þ$ xP (x) и " xP (x)Þ P (a), где a Î D.

(8) $ x (P (x)Ù Q (x))Þ$ xP (x)Ù$ xQ (x).

Действительно, $ x (P (x)Ù Q (x))ºИ (подтверждение)Û

P (a)Ù Q (a)ºИ для некоторого a Î D (конъюнкция)Û

P (a)ºИ и Q (a))ºИ для некоторого a Î D (подтверждение)Þ

$ xP (x)ºИ и $ xQ (x)ºИ (конъюнкция)Û

$ xP (x)Ù$ xQ (x)ºИ.

(9) " xP (x)Ú" xQ (x)Þ" x (P (x)Ú Q (x)).

Действительно, " xP (x)Ú" xQ (x)ºИ (дизъюнкция)Û

" xP (x)ºИ или " xQ (x)ºИ (обобщение)Û

P (a)ºИ для всех a Î D или Q (a)ºИ для всех a Î D (дизъюнкция)Þ

P (a)Ú Q (a)ºИ для всех a Î D (обобщение)Û

" x (P (x)Ú Q (x))ºИ.

(10) $ x " yP (x, y)Þ" y $ xP (x, y).

Действительно, $ x " yP (x, y)ºИ (подтверждение)Û

" yP (a, y)ºИ для некоторого a Î D (обобщение)Û

P (a, b)ºИ для некоторого a Î D и для всех b Î D (подтверждение)Þ

$ xP (x, b)ºИ для всех b Î D (обобщение)Û

" y $ xP (x, y)ºИ.

Обратные импликации, вообще говоря, не являются истинными.

В качестве интерпретации возьмем множество всех натуральных чисел с обычными операциями и отношениями над числами.

(7¢) Неверно, что $ xP (x)Þ P (a) и P (a)Þ" xP (x), где a Î D.

Пусть P (x) есть x =5, a равно 4. Тогда $ x (x =5)Þ4=5ºЛ.

Пусть P (x) есть x ¹5, a равно 4. Тогда 4¹5Þ" x (x ¹5)ºЛ.

(8¢) Неверно, что $ xP (x)Ù$ xQ (x)Þ$ x (P (x)Ù Q (x)).

Пусть P (x) есть x =5 и Q (x) есть x =4. Тогда

$ x (x =5)Ù$ x (x =4)Þ$ x (x =5Ù x =4)ºЛ.

(9¢) Неверно, что " x (P (x)Ú Q (x))Þ" xP (x)Ú" xQ (x).

Пусть P (x) есть x ¹5 и Q (x) есть x ¹4. Тогда

" x (x ¹5Ú x ¹4)Þ" x (x ¹5)Ú" x (x ¹4)ºЛ.

(10¢) Неверно, что " y $ xP (x, y)Þ$ x " yP (x, y).

Пусть P (x, y) есть x > y. Тогда " y $ x (x > y)Þ$ x " y (x > y)ºЛ.