ЛЕКЦИЯ 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)L B(y, b) LB(y, c). Тогда справедлива равносильность:

$xA(x, y)"zB(y, z)º( A(a, y) vA(b, y) vA(c, y))L B(y, a)L B(y, b) LB(y, c).