В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 32
Текст из файла (страница 32)
В самом деле, вычислим, например, значение этой формулы при Г= О, 6 = 1: (-ч! -+ -чО) -+ ((-з! -+ 0) -+ 1) = (1 -+ 1) -+ ((1 -+ 0) -+ 1) = 0-+ -+ (О -+ 1) = 0 -+ 1 = 1. Замечание. Если каждая аксиома системы не зависит от остальных аксиом этой системы, то такая система аксиом называется независшиой. Таким образом, в задачах 8.24, 8.25, 8.26 устанавливается независимость системы аксиом (А1), (А2), (АЗ) формализованного исчисления высказываний.
8.27. Докажите, что если схему аксиом (АЗ) в системе аксиом (А1), (А2), (АЗ) формализованного исчисления высказываний заменить схемой аксиом (АЗ'): (-з 6-+ -~Г) -+ (Г-+ 6), то класс теорем от этого не изменится. У к а з а н и е. Для этого достаточно показать, что формула (АЗ') выводима из аксиом (А1), (А2), (АЗ) (см. задачу 8.14, б), и обратно показать, что формула (АЗ) выводима из аксиом (А1), (А2), (АЗ'). би Глава ГУ ЛОГИКА ПРЕДИКАТОВ Эта глава объединяет три параграфа (й 9 — 11). В 5 9 рассматриваются основные понятия, связанные с предикатами, — множество истинности, классификация предикатов, их равносильность и следование, операции над предикатами, формулы и тавтологии логики предикатов, равносильность и следование формул логики предикатов, а й 10 посвящен применению логики предикатов в математической практике и практике рассуждений.
В 5 11 строится формализованное исчисление предикатов. 5 9. Основные понятия логики предикатов Понятие предиката и операции иад предикатами. и-Местным нредикатом (или 4ункцией-высказыванием от и переменных), определенным на множествах (областях) М„Мъ ..., М„, называют выражение, содержащее п (предметных) переменных хо х,, ..., х», превращающееся в высказывание при подстановке вместо этих переменных конкретных элементов (предметов) из множеств Мь М„..., М„соответственно. Для н-местного предиката будем использовать обозначение Р (х„х„..., х„). Высказывание будем считать 0-местным предикатом. На предикаты естественным образом переносятся все операции (логические связки), которые мы проделывали над высказываниями. Например, дизьюнкцией и-местных предикатов Р(х„хъ ..., х„) и 0(х„х„..., х„), заданных над множествами М„М„..., М„, называют новый и-местный предикат над этими множествами, обозначаемый Р(х„х„..., х„) ~ Д(хп х„..., х„), который обращается в ложное высказывание на тех и только тех значениях переменных из множеств М„М„..., М„, на которых в ложное высказывание обращаются оба данных предиката.
Кроме того, для предикатов определяются еще две операции: 1) квантер общности (зх)(Р(х)) (читается: «Для всех х имеет место Р(х)»); 2) квантор существования (Лх)(Р(х)) (читается: «Существует х, для которого имеет место Р(х)»). Эти операции применяются к одному предикату. Они ставят в соответствие одноместному предикату Р(х) высказывания (чх)(Р(х)) и (Лх)(Р(х)) соответственно, логические значения которых определяются следующими формулами: 162 1, если Р(х) — тождественно истинный Ц('Фх)(Р(х))1 = предикат, 0 — в противном случае; О, если Р(х) — тождественно ложный Х((Зх)(Р(х))) = предикат, 1 — в противном случае. Квантор можно применять также к и-местному предикату; в результате получается (и — 1)-местный предикат.
Переменную, к которой относится квантор, называют связанной, остальные переменные называют свободньиии. Выражение ( ех)(Р(х) -» О(х)) обозначают ('ФР(х))(о(х)). Символ (ч'Р(х)) называют ограниченным квантором общности. Выражение (Зх)(Р(х) л Ц(х)) обозначают (3Р(х))(о(х)).
Символ (ЗР(х)) называют ограниченнььи квантором существования. 9.1. Какие из следующих выражений являются предикатами: а) «х делится на 5» (х е Ф); б) «Река х впадает в озеро Байкал» (х пробегает множество названий всевозможных рек); в) «х2 + 2х + 4» (х е Я); Г) «(х + у)' = х' + 2ху+ у'» (х, у е Я); д) «х есть брат у» (х, у пробегают множество всех людей); е) «х и у лежат по разные стороны от я» (х, у пробегают множество всех точек, а ~ — всех прямых одной плоскости); ж) «стя 45' = 1»; з) «х перпендикулярна у» (х, у пробегают множество всех прямых одной плоскости); и) «х'+ х — 6 = 0» (х а Я); к) «Для всех вещественных чисел х выполняется равенство х'+х †6». 9.2.
Для каждого из следующих высказываний найдите предикат (одноместный или многоместный), который обращается в данное высказывание при замене предметных переменных подходящими значениями из соответствующих областей: а) «3 + 4 = 7»; б) «Вера и Надежда — сестры»; в) «Сегодня — вторник»; г) «Город Саратов находится на берегу реки Волги»; д) «з(п 30' = 0,5»; е) «А.С. Пушкин — великий русский поэт»; ж) «Зз + 42 = 5з»' з) «Река Индигирка впадает в озеро Байкал»; 163 и) «Если число делится на 3, то оно делится на 9»; к) «Луна есть спутник Марса»; л) 1а(а/4) = 1».
Построив такой предикат, постарайтесь или точно указать его область истинности, или как-то ее обрисовать. Решение. л) Можно указать три предиката, каждый из которых обращается в данное высказывание при соответствующей подстановке. Первый предикат одноместный: «гях = 1» [х в Я ~ [я/2+ ял: л в Ф]). Он превращается в данное высказывание при подстановке х = я/4. Получающееся высказывание истинно.
Указанным значением не исчерпывается множество истинности построенного предиката. Как нетрудно установить, это множество следующее: [х/4+ ял: л е Ь/]. Второй предикат также одноместный: «гя(я/4) = у» (у е Я). Он превращается в данное высказывание при подстановке у = 1. Ясно, что этим значением и исчерпывается множество истинности этого предиката. Наконец можно построить третий предикат, двухместный: «гях = у» [х а Я ~ [я/2+ хл: и в Ф], у в й). Он превращается в данное высказывание при подстановке х = а/4, у = !. Его область истинности представляет собой множество упорядоченных пар, совокупность которых графически изображается в виде бесконечного семейства кривых, называемых тангенсоидами. 9.3.
Прочитайте следующие высказывания и определите, какие из них истинные, а какие ложные, считая, что все переменные пробегают множество действительных чисел: а) (Чх) (3у) (х+ у = 7); б) (Бу) («х) (х+ у = 7); в) (Зх) («'у) (х+ у = 7); г) ('Фх) ('Фу) (х+ у = 7); д) [(Чх) ('Фу) (х + у = 3)] -» (3 = 4); е) (чх) [(х' > х) ++ ((х > 1) ~ (х < О))]; ж) ('Фа) [[(3х) (ах = 6)] +» (а ~ О)]; з) (г'Ь) (3а) ('Фх) [х' + ах + Ь > О]; и) (~'х) [((х > 1) ч (х < 2)) ++ (х = х)]; к) (3Ь) (Ча) (Зх) (х + ах+ Ь = О); л) (3а) («'Ь) (3х) (х + ах+ Ь = О).
Р е ш е н и е. а) Двухместный предикат «х+ у = 7» задан над множеством действительных чисел Я. Это означает, что вместо каждой из двух его предметных переменных х и у могут быть подставлены действительные числа. Если такая подстановка сделана вместо обеих переменных, например «6+ 3 = 7», то предикат превращается в высказывание (в нашем случае ложное). Но данный двухместный предикат «х+ у = 7» может быть превращен в высказывание и другим путем: именно путем применения к нему операций квантификации (взятия квантора общности или квантора существования). Применим сначала к двухместному предикату «х + у = 7» 164 операцию взятия квантора существования по переменной у. Получим уже одноместный предикат «(Лу)(х + у = 7)» относительно переменной х, которая пробегает множество А. Говорят, что в полученном выражении переменная у связана, а переменная х свободна.
Вместо переменной у мы уже ничего не можем подставлять, в то время как вместо х могут быть подставлены действительные числа, в результате чего одноместный предикат будет превращаться в высказывания. Например, высказывание «(~у)(10 + у = 7)» можно прочитать так: «Существует действительное число у, такое, что 10 + у = 7». Ясно, что это высказывание истинно.
(В качестве такого у, существование которого утверждает это высказывание, нужно взять действительное число -3.) Легко далее понять, что, какое бы действительное число х«мы ни подставили вместо переменной х в предикат «(Лу)(х+ у = 7)», предикат превращается в истинное высказывание. Действительно, в качестве такого числа у, существование которого утверждает высказывание, нужно взять разность 7 — х.
Это обстоятельство согласно определению операции взятия квантора общности означает, что получающееся высказывание «(~х)(Лу)(х+ у = 7)» истинно. Его можно прочитать следующим образом; «Для любого действительного числа существует такое действительное число, сумма которого с первым равна 7», В выражении «('Фх)(Лу)(х+ у = 7)» уже нет свободных переменных. Обе переменные х и у стоят под знаками кван- торов и поэтому являются связанными. Само же выражение уже не является предикатом, оно есть высказывание истинное, как было установлено ранее. Впрочем, по желанию, развивая понятие предиката, можем считать, что высказьгвание — это 0-местный предикат, т.е.
предикат без предметных переменных. Но мы должны осознавать, что количественный переход от одноместного предиката к 0-местному приводит к качественному скачку, так что 0-местный предикат — это объект качественно иной, нежели предикат одноместный, хотя и подводимый нами условно под понятие «предикат». б) Высказывание «(Зу)(чх)(х + у = 7)» можно прочитать так: «Существует такое действительное число, которое после прибавления к любому действительному числу в сумме дает 7».
Нетрудно понять, что это утверждение ложно. В самом деле, рассмотрим одноместный предикат «(чх)(х+ у = 7)» относительно переменной у, применением к которому квантора существования получается данное высказывание. Ясно, что какое бы действительное число ни подставить вместо предметной переменной у, например «(»хКх+ 4 = 7)», предикат будет превращаться в ложное высказывание. (Высказывание «(»х)(х+ 4 = 7)» ложно, так как одноместный предикат «х+ 4 = 7» превращается в ложное высказывание, например при подстановке вместо переменной х числа 5.) Поэтому высказывание «(Бу)(чх) (х + у = 7)», получающееся из одно- 165 местного предиката «(~гх)(х+ у = 7)» применением операции взя- тия квантора существования по у, ложно.
и) Это высказывание читается так: «Любое действительное чис- ло равно самому себе тогда и только тогда, когда оно больше 1 или меньше 2». Чтобы выяснить, истинно или ложно данное вы- сказывание, будем, например, искать такое действительное число х, которое превратило бы одноместный предикат ((х > 1) ч (х < 2)) ++ «+ (х = х) в ложное высказывание. Если нам удастся найти такое число, то данное высказывание, получающееся из этого предиката «навешиванием» (т.е. применением операции взятия) квантора общ- ности, ложно. Если же мы придем к противоречию, предположив, что такое х существует, то данное высказывание истинно.
Ясно, что предикат «х = х» превращается в истинное высказы- вание при подстановке вместо х любого действительного числа, т.е. является тождественно истинным. Спрашивается, можно ли указать действительное число, которое превратило бы предикат «(х > 1) ~~ (х < 2)» в ложное высказывание? Нет, потому что какое бы действительное число мы ни взяли, оно либо больше 1, либо меньше 2 (либо одновременно и больше 1 и меньше 2, что вовсе не возбраняется в нашем случае). Следовательно, предикат «(х > > 1) ~ (х < 2)» тождественно истинен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
