Предикаты

Предметом рассмотрения этого параграфа будут предикаты - связные повествовательные предложения, содержащие п переменных, при фиксации значений которых можно сказать, истинно оно (предложение) или ложно.

Определение З.Ц. Предикатом местности п (n-местным предикатом), определенным на области П = {(ж],Ж9, • •., жп)}, называют отображение Q во множество высказываний.

Здесь a?i, #2, • • •, хп ~ символы переменных произвольной природы. Эти переменные называют предметными.

Приведем несколько примеров предикатов:

  • 1) Р(х,у) = «натуральное число х делится (без остатка) на натуральное число у» - двуместный предикат, определенный на множестве пар натуральных чисел N х N. Очевидно, что Р(6,3) = 1, Р(9,2) = 0.
  • 2) Ь(х, у) = «у ^ ж2, ж, у G М» - двуместный предикат, определенный на множестве пар действительных чисел МхМ. Ясно, что L( 1,1) = 1, L(1,0) = 0.
  • 3) Q(x) = «ж2 + 1 = 0, х G М» - одноместный предикат, определенный на множестве действительных чисел М. Очевидно, Q(x) = 0 для любого действительного числа х.

Определение 3.15. Областью истинности n-местного предиката Р, определенного на области И = {(х,хо, ? ? ? ,хп)}: называется подмножество 1{Р) множества П, образ которого соответствует истинным высказываниям. Предикат, область истинности которого - пустое множество, называют тождественно ложным. Если область истинности предиката совпадает с П. то его называют тождественно истинным на Q.

П р и м е р 3.22. Определить область истинности для предикатов, рассмотренных выше.

1. Областью истинности предиката Р(х,у) — «натуральное число х делится (без остатка) на натуральное число у» является подмножество декартова произведения N х N. - 1(Р) = {(ж, у)х — ку, х G N, у G N, к G N}.

Рис. 11

  • 2. Область истинности предиката L(x,y) = = «у^х2,х.у?Ш» - подмножество множества МхМ. Геометрической интерпретацией этого множества может служить неограниченная область на плоскости, расположенная внутри параболы ;/ = ж , включая точки параболы (рис. 11).
  • 3. Область истинности предиката Q(x) = «ж2+1 = = 0,жбМ» - пустое множество. Этот предикат тождественно ложный на множестве R.

Поскольку предикаты - это отображения во множество высказываний, где введены логические операции, то эти операции определяются аналогичным образом и для предикатов. Более того, множество предикатов вместе с операциями конъюнкции, дизъюнкции и отрицания образуют булеву алгебру, т. е. для них справедливы все законы булевой алгебры. Кроме того, для предикатов определены две новые операции: связывания предметной переменной квантором общности и квантором существования. Сформулируем определения кванторов и результаты операций связывания ими переменных.

Определение 3.16. Символ V называют квантором всеобщности. Высказывание /хР(х) (читается «для любого х Р(х)») истинно тогда и только тогда, когда Р(х) - тождественно истинный предикат.

Определение 3.17. Символ 3 называют квантором существования. Высказывание ЗхР(х) (читается «существует х Р(х)») ложно тогда и только тогда, когда Р(х) - тождественно ложный предикат.

Обозначения V и 3 для кванторов - это перевернутые английские буквы А и Е, которые являются первыми буквами в словах АП - все, Exist- существовать. Отметим, что данные символы широко используются не только в логике, но и в других разделах математики.

Запишем на языке логики предикатов определение антисимметричного бинарного отношения на множестве А.

П р и м е р 3.23. Определить истинностные значения высказываний: 1) WxVyP(xyy), 2) УуЗхР(х. у). 3) ЗхУуР(х, у), если Р(х,у) это определенный выше предикат «х делится нацело на у, т, уЕ N».

Каждая из трех формул логики предикатов представляет собой высказывание. Поскольку предикат Р(хуу) не является тождественно истинным на множестве N, то УхУуР(х,у) = 0. Так как предикат Q(y) = = 3хР(хуу) является тождественно истинным на множестве N (достаточно взять х = у), то УуЗхР(хуу) = 1. Однако неверно, что существует такое натуральное т, которое делится нацело на любое натуральное у, значит ЗхУуР(х,у) = 0 (предикат УуР(х,у) = 0 является тождественно ложным на множестве N).

Последний пример, в частности, показывает, что разноименные кванторы не всегда можно переставлять.

Упражнение 8. Определить истинностные значения высказываний /хЗуР(х, у) и Зу/хР(х, у).

Определение 3.18. Часть формулы, на которую распространяется действие квантора, называется областью действия этого квантора. Если вхождение переменной х в формулу находится в области действия квантора Зх pi ли Ух, то оно называется связанным вхождением. В противном случае вхождение переменной в формулу называется свободным.

Определение 3.19. Если формула не содержит свободных вхождений переменных, то она называется замкнутой.

П р и м е р 3.24. Определить свободные и связанные вхождения переменных в предикате УхУуР{х, у) У 3yQ{x. у, z).

Область действия кванторов Ух и У у предикат Р(х, у), квантора Зу предикат Q{x, у, z). Значит, оба вхождения переменной у являются связанными, первое вхождение переменной х связано, а второе свободно. Вхождение переменной z свободно.

Определение 3.20. Предикат называется выполнимым на множестве М, если при некотором наборе значений переменных из этого множества он принимает значение «истина». Предикат называется опро- вержимым на множестве М, если при некотором наборе значений переменных из этого множества он принимает значение «ложь».

Например, предикат Ух(х>у) на множестве действительных чисел является как выполнимым (при у——1 он принимает значение «истина»), так и опровержимым (при у— 1 он принимает значение «ложь»). А на множестве натуральных чисел данный предикат не является выполнимым, так как его область истинности в данном случае пустое множество.

Теорема 3.11. В логике предикатов справедливы следующие утверждения:

  • 1) УхР(х) = ЗхР(х) и ЗхР(х)=УхР(х) - законы де Моргана;
  • 2) УхУуР(х, у) =УуУхР(х, у) и ЗхЗуР(х, у) = ЗуЗхР(х, у) - законы коммутативности одноименных кванторов;
  • 3) yx(P(x)&Q(x)) =УхР(х)&Ух(^(х) и Зх(Р(х) У Q(x)) = — ЗхР(х) У 3xQ{x) - законы дистрибутивности;
  • 4) если формула Ф получена заменой связанной переменной формулы F другой переменной, не входящей в /у в кванторе и всюду в области его действия, то Ф = F.

Доказательство. Для примера докажем первое из равенств 3. Пусть левая часть равенства истина, тогда P(x)foQ(x) - тождественно истинный предикат. Значит оба предиката Р(х) и Q(x) тождественно истинные. Отсюда УР(х) и УхД(х) - тождественно истинные высказывания, т. е. правая часть равенства истина, Если высказывание в левой части равенства ложно, то P(x)&Q(x) = 0 хотя бы для одного значения х. Тогда, хотя бы один из предикатов Р(х) и Q(x) для этого х является ложным. Значит, и правая часть равенства ложна, так как в этом случае ложным является по крайней мере одно из высказываний /хР(х) и VxQ(x).

Поясним четвертый пункт теоремы. Например, если в предикате УхУуР(х, у) V 3Q(x, у, z) заменить переменную у на переменную t только в области действия квантора Зу, а в области действия квантора Уу замену переменной не производить, то получим формулу, равносильную исходной.

Определение 3.21. Говорят, что предикат находится в предваренной нормальной форме, если все кванторы в ней вынесены влево, т. е. если она имеет вид Q1X1Q0X2 . ? ? QnxnP{x 1, ?2, • • •, xnj %п+ ъ • • •, ж*), где Qi - символ квантора.

П р и м е р 3.25. Привести к нормальной предваренной форме предикат ЗуУхР(х,у) У 3y/xS(x, у).

По теореме 3.11 (пункт 3) данный предикат равносилен предикату Зу(УхР(х,у) VУхБ(х>у)). Заметим, что предикат /хIэ(х, у) У/хS(х. у) не равносилен предикату Ух(Р(х, у) У S(x, у)). Например, если Р(х.у) = — «х^у», a S(x, у) = «х > у», то УхР(х, у) VУхS(х,у) = О при любом значении у, тогда как Ух(Р(х.у)У S(x.y)) тождественно истинный предикат. Чтобы привести к нормальной форме, в предикате УхЗ(х. у) сделаем замену переменной (теорема 3.11, пункт 4). Тогда

Проиллюстрируем применение языка предикатов на примере. Рассмотрим определение предела, числовой последовательности. Высказывание «число а является пределом числовой последовательности правносильно истинности следующего выражения

при условии, что п, N - натуральные числа, е - положительное действительное число. Тот факт, что число а не является пределом числовой последовательности {.тп}, означает истинность отрицания построенного предиката, т. е.

Преобразуем, используя равенства 1 теоремы 3.11 и известные равносильности логики высказываний.

Следовательно, для доказательства того, что число а не является пределом последовательности {хп} достаточно найти такое положительное число г, что какое бы большое ни было число /V, найдется п> N, для которого выполнено неравенство хп — а У г.

Вопросы и задания для самоконтроля

I. Что в математической логике называется высказыванием? Приведите примеры сложных высказываний, составьте для них логические формулы.

2. Пусть А - высказывание «число 2 является простым,», В

«жирафы, обитают в Сибири». Приведите примеры тождественно истинных формул, которые содержат высказывания А и В.

  • 3. Докажите методом косвенного доказательства (от противного) тождественную истинность формулы (А—>В)—>((В—>С)—>(А—>С)).
  • 4. Среди формул: А^А, Л, ЛЛ, Л/Л, А^А укажите тавтологии и противоречия, если Л - тавтология.
  • 5. Какая формула называется дизъюнктивной нормальной формой (совершенной дизъюнктивной нормальной формой)?
  • 6. Укажите, какие из следующих формул х V ад, XXs V Т2Т3, аЦОДТз VаДОДОД V ад ОДТз? (ад V ад)ад являются ДНФ, СДНФ?
  • 7. Укажите, какие из формул ад V ад, (ад V ад V ад) (ад У х% V ад), aj1.T3V.T2.T3, (tiVt2)t3 являются КНФ, СКНФ?
  • 8. Составьте многочлен Жегалкина для формул Т]—>тд, Ti|t2.
  • 9. Какая система логических связок называется полной? Является ли полной система связок (&, V)?
  • 10. Какая функция называется двойственной (самодвойственной) логической функции /(ад, ад,..., тп)?

II. Какая связь между булевыми функциями и формулами алгебры высказываний?

  • 12. Что называется предикатом? Приведите примеры предикатов.
  • 13. Запишите формулы, равносильные следующим формулам: ЗхР(т), ЗтР(т), Vt(P(t)&Q(t)), ЗхР(х) V 3Q(x).
  • 14. С помощью символов логики предикатов запишите предложение: «для любого действительного числа х найдется действительное число у такое, что ху = 1».
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >