Лекция 12

ТЕМА: КВАНТОРНЫЕ ОПЕРАЦИИ. ФОРМУЛЫ ЛОГИКИ ПРЕДИКАТОВ.

ПЛАН:

1. Кванторные операции.

2. Формулы логики предикатов.

3. Значение формулы логики предикатов.

4. Равносильные формулы логики предикатов.

Главная

1. Кванторные операции.

Пусть имеется предикат Р(х), определенный на мно­жестве М. Если а - некоторый элемент из множества М, то подстановка его вместо х в предикат Р(х) превращает

этот предикат в высказывание - Р(а). Такое высказыва­ние называется единичным. Наряду с образованием из предикатов единичных высказываний в логике преди­катов рассматривается еще две операции, которые пре­вращают одноместный предикат в высказывание.

Квантор всеобщности. Пусть Р(х) — предикат, определенный на множестве М. Под выражением  х Р(х) понимают высказывание, истинное, когда Р(х) истинно

для каждого элемента х из множества М и ложное, в про­тивном случае. Это высказывание уже не зависит от х.

Соответствующее ему словесное выражение будет: «Для всякого х Р(х) истинно». Символ  называют кванто­ром всеобщности.

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

Квантор существования. Пусть Р(х) — предикат, определенный на множестве М. Под выражением х Р(х) понимают высказывание, которое является истинным, если существует элемент х  М, для которого Р(х) истинно, и ложным в противном случае. Это высказывание уже не зависит от х.

Соответствующее ему словесное выражение будет: «Существует х, при котором Р(х) истинно». Символ  называют квантором существования. В высказывании х Р(х) переменная х связана квантором .

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

Ясно, что высказывание  х Р(х) истинно только в том единственном случае, когда Р(х) - тождественно истинный предикат, а высказывание х Р(х) ложно толь­ко в том единственном случае, когда Р(х) — тождествен­но ложный предикат.

Кванторные операции применяются и к многомест­ным предикатам. Пусть, например, на множестве М за­дан двухместный предикат Р(х,у). Применение кванторной операции к предикату Р(х,у) по переменной х ста­вит в соответствие двухместному предикату Р(х,у) од­номестный предикат x P(x, у} (или одноместный пре­дикат х Р(х, у)), зависящий от переменной у и не за­висящий от переменной х. К ним можно применить кванторные операции по переменной у, которые приведут уже к высказываниям следующих видов:

yxP(x,y), yxP(x,y), yxP(x,y), ухР(х,у).

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

1. yxP(x,y) - «Для всякого у и для всякого х у является делителем х».

2. yxP(x,y) - «Существует у, которое является делителем всякого х».

3. yxP(x,y)- «Для всякого у существует х такое, что х делится на у».

4. ухР(х,у) - «Существует у и существует х та­кие, что у является делителем х».

5. хуP(x,y) - «Для всякого х и для всякого у у является делителем х».

6. хуP(x,y) - «Для всякого х существует такое у, что х делится на у».

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

8. хуР(х,у) - «Существует х такое, что для вся­кого у х делится на у».

Высказывания 1, 5 и 8 ложны, а высказывания 2, 3, 4, 6 и 7 истинны.

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

Рассмотрим предикат – Р(х), определенный на мно­жестве М = {a₁, a₂,…, a_n}, содержащем конечное число элементов. Если предикат Р(х) является тождественно истинным, то истинными будут высказывания P(a₁), P(a₂),…, P(a_n). При этом истинными будут высказывание хР(х) и конъюнкция P(a₁) P(a₂)… P(a_n).

Если хотя бы для одного элемента a_kM P(a_k) окажется ложным, то ложными будут высказывание хР(х) и конъюнкция P(a₁) P(a₂)… P(a_n). Значит, справедлива равносильность:

хР(х)  P(a₁) P(a₂)… P(a_n).

Аналогичным образом можно доказать справедливость равносильности:

хР(х)  P(a₁)V P(a₂)V…VP(a_n).

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

Примеры:

1. Какие из следующих высказываний тождественно ложные , а какие тождественно истинные, если область определения М = R?

а) х (х +5 = х + 3) – тождественно ложное высказывание, т.к. ни при каком х равенство неверно;

б) х (х² +х + 1 > 0) – тождественно истинное высказывание: левую часть неравенства перепишем в виде (х + ½)² + ¾ , эта сумма больше нуля при любом х;

в) х ((х² – 5х +6  0)(х² – 2х + 1 >0)) – высказывание тождественно истинное, если пересечение областей истинности логически умножаемых предикатов не пусто, и ложное, в противном случае.

Первое неравенство представим в виде (х –2)(х – 3) 0, решением которого являются х(-; 2] [3; +).

Второе неравенство представим в виде (х – 1)²> 0 . решением которого являются все х  0.

Пересечение областей истинности: (-; 0)(0; 2][3; +), значит, высказывание тождественно истинное.

2. Предикат Р(х, у): «x<y» определен на множестве М=NN.

а) какие из предикатов тождественно истинные, какие тождественно ложные: хР(х, у), хР(х, у), уР(х, у), уР(х, у)?

хР(х, у) – не является ни тождественно истинным, ни тождественно ложным: при у =1 хР(х, у) = 0, т.к. нет натурального числа меньше 1; при у >1 хР(х, у) = 1, например, х =1. значит, область истинности предиката у>1.

хР(х, у) – тождественно ложный предикат, т.к. какое бы у не задать, среди натуральных чисел найдутся те, которые больше или равны у.

уР(х, у) – тождественно истинный, т.к. для всякого каждого натурального числа можно найти большее натуральное число.

уР(х, у) – тождественно ложный, т.к. какое бы х не задать, среди натуральных чисел найдутся те, которые меньше или равны х.

б) какие из высказываний истинные, какие ложные:

хуР(х, у); хуР(х, у).

хуР(х, у) – ложное высказывание, т.к. не существует натурального х меньшего любого натурального у (для у =1).

хуР(х, у) – истинное высказывание, т.к. для любого натурального х существует большее натуральное число у.

3. Предикаты А(х, у) и В(у, z) определены на множестве МхМ, где М={a, b, c}. Записать формулу xA(x, y)zB(y, z) без кванторных операций. Предикат xA(x, y) равносилен дизъюнкции A(a, y) vA(b, y) vA(c, y). Предикат )zB(y, z) равносилен конъюнкции B(y, a) B(y, b) B(y, c). Тогда справедлива равносильность:

xA(x, y)zB(y, z)( A(a, y) vA(b, y) vA(c, y)) B(y, a) B(y, b) B(y, c).