Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






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



 

Пусть имеется предикат P(x), определенный на множестве M. Если а – некоторый элемент из множества M, то подстановка его вместо x в предикат P(x) превращает этот предикат в высказывание P(а). Такое высказывание называется единичным. Наряду с образованием из предикатов единичных высказываний в логике предикатов рассматривается еще две операции, которые превращают одноместный предикат в высказывание.

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

Пусть P(x) – предикат, определенный на множестве M. Под выражением "x P(x) понимают высказывание, истинное, когда P(x) истинно для каждого элемента x из множества M и ложное в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение будет «Для всякого x P(x) истинно». Символ " называют квантором всеобщности.

Переменную x в предикате P(x) называют свободной (ей можно придавать различные значения из M), в высказывании "x P(x) переменную x называют связанной квантором ".

2. Квантор существования.

Пусть P(x) – предикат, определенный на множестве M. Под выражением $x P(x) понимают высказывание, которое является истинным, если существует элемент x Î M, для которого P(x) истинно, и ложным в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение будет: «Существует x, при котором P(x) истинно». Символ $ называют квантором существования. В высказывании $x P(x) переменная x связана квантором $.

Приведем пример употребления кванторов. Пусть на множестве N натуральных чисел задан предикат P(x): «Число x кратно 5». Используя кванторы, из данного предиката можно получить высказывания: "x Î N P(x) – «Все натуральные числа кратны 5»; $x Î N P(x) – «Существует натуральное число, кратное 5». Очевидно, первое из этих высказываний ложно, а второе истинно.

Ясно, что высказывание "x P(x) истинно только в том единственном случае, когда P(x) – тождественно истинный предикат, а высказывание $x P(x) ложно только в том единственном случае, когда P(x) – тождественно ложный предикат.

Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве M задан двухместный предикат P(x,y). Применение кванторной операции к предикату P(x,у) по переменной x ставит в соответствие двухместному предикату P(x,у) одноместный предикат "x P(x,y) (или одноместный предикат $x P(x,y)), зависящий от переменной y и не зависящий от переменной x. К ним можно применить кванторные операции по переменной y, которые приведут уже к высказываниям следующих видов:



"y"x P(x,y), $y"x P(x,y), "y$x P(x,y), $y$x P(x,y).

Например, рассмотрим предикат P(x,y): «x делится на y», определенный на множестве N. Применение кванторных операций к предикату P(x,y) приводит к восьми возможным высказываниям.

1. "y"x P(x,y) – «Для всякого y и для всякого x y является делителем x».

2. $y"x P(x,y) – «Существует y, который является делителем всякого x».

3. "y$x P(x,y) – «Для всякого y существует x такой, что x делится на любое y».

4. $y$x P(x,y) – «Существует y и существует x такие, что y является делителем x».

5. "x"y P(x,y) – «Для всякого x и для всякого y y является делителем x».

6. "x$y P(x,y) – «Для всякого x существует такой y, что x делится на y».

7. $x$y P(x,y) – «Существует x и существует y такие, что y является делителем x».

8. $x"y P(x,y) – «Существует x такой, что для всякого y x делится на y».

Легко видеть, что высказывания 1, 5 и 8 ложны, а высказывания 2, 3, 4, 6 и 7 истинны.

Из рассмотренных примеров видно, что в общем случае изменение порядка следования кванторов изменяет смысл высказывания, а значит, и его логическое значение (например высказывания 3 и 8).

Рассмотрим предикат P(x), определенный на множестве M = {a1, a2, …, an}, содержащем конечное число элементов. Если предикат P(x) является тождественно истинным, то истинными будут высказывания P(a1), P(a2),…, P(an). При этом истинными будут высказывание "x P(x) и конъюнкция P(a1)& P(a2)&…&P(an).

Если же хотя бы для одного элемента ak Î M P(ak) окажется ложным, то ложными будут высказывание "x P(x) и конъюнкция P(a1)& P(a2)&…&P(an). Следовательно, справедлива равносильность



"x P(x) º P(a1)& P(a2)&…&P(an).

Нетрудно показать, что справедлива и равносильность

$x P(x) º P(a1P(a2) Ú…ÚP(an).

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

 

 


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!