И.А. Лавров,Л.Л. Максимов-Задачи по теории множеств, математической логике и теории алгоритмов (Учебник Лаврова 2006-го года), страница 35

задачу 5 (б)). 35. Если Чх, ...Ыхт Еу, ... Зу А(х,, ...,хслу,, ..., ув) ложна в й = (М;а), то существуют а,, ..., а ЕМ такие, что й )(Зу, ... ... Лу А(а, ..., а,у,, ..., у ). Тогда этаформулаложнавподмодели й, = (М,; а), где М, = (а,, ..., ат). Далее применяем, если нужно, задачу 29, ч. и. и!(тнмлтнчнскАя логик!( И 51 36. Пусть 1]] = (М; о). Рассмотрим отношение эквивалентности на М: х — у сь ((Р (х) и Р (у))$... 8(Р (х) и Р (у))) = и. Пусть М =М/-. Ясно, что М я 2". Положим Р,([х]) = Р.(х), Индукцией ! по числу шагов построения А(х,, ...,х„) доказать, что для любых а, ..., а Е М имеем (М; о) ~А([а ], ..., [а ]) ~ь ]В ~А(а), ..., а„).

37. (а) Выполнима на модели В] = (М; Р), где М= (а, Ь] и Р(а) = и, Р(Ь) = л. (б) Выполнима на модели 1В =(М; Р,,Р., Р ), где М= (а] и Р((а) = Рз(а) = Рз(а) = и. (в) Невыполнима. 38. Если подформула С формулы А имеет вид ЯуС (х, ..., х, у), где Д есть 3 (У), то привести С (х, ..., х„, у) к виду ч $ С. соответственно 8 ч С..] ], где каждое С..

начинается с квантора илн (![ [ к) ! ! имеет вид Р(з) или -1 Р(з) для некоторого Р из и н переменной г. Далее использовать эквивалентности нз задачи 16. Повторяя процесс, получим требуемую формулу. 39. ПустьА выполнима вЯ1 = (М; а). Каждому С, (1 я ! я к) сопоставляем элемент а! Е М такой, что зВ у С, (а,.), где С, = (3 х) С(((х). Полагаем значение В.. равным значению Р.(а ). Тогда А истинна.

!1 ! Обратно. Пусть А = н при некоторых значениях переменных В., ! !/ Возьмем М = (а,, ..., а ] и положим значение Р (а.) равным значению !' "' ! В., Тогда(М; а) ~А. (! 40. Сначала использовать задачу 38. Затем привести полученную формулу В к д,н.ф, В, в которой вместо пропознциональных !' переменных подставлены 3-составляющие. Далее применить задачу 39. Принеобходимостивоспользоваться эквивалентностью С вЂ” ((3 х Р(х) 8 С) ч (3 х -1 Р(х) 8 С)). 41.

(а) Выполнима. Например, М = (а, Ь], Р(а)= Д(а)= ()(Ь)= н, Р(Ь) = л. (б), (в) Невыполнима. 42.(а)Чх)Чх ...т'х Чх~~, (х,=хч...чх,=х ч чх =х ч...чх =х ), ! л+! "' ° ч+! ' (б) См. задачу 43. ОТВЕТЫ, РЕШЕНИЯ, УКАЗАНИЯ (.) 3 х, 3 , ... 3 „ ( х, = , а ... а х, = „ а ...

а . „ , = 8 ЬЧу (у=х чу=х ч...чу= х )). 43. (в) Использовать указание к задаче 38 и (б) . (г) Привести А к д.н.ф. и использовать (а). 44. Например, (и", 82, Вз, ...) (см. задачу 43 (а)). 45. Записать формулу с = и одним двуместным предикатом Р, означающую, что предикат Р иррефлексивен, симметричен и является всюду определенной 1-1-функцией.

й б. Исчисления предикатов 1. Вывод секвенции в ИС является выводом в И ПС. 2. Требуемый вывод получается из вывода в ИС заменой всех формул С на С(Р ~В). 3. Аналогично задачам 3 и б иэ э 3. 4. (а) Из аксиомы А(у) РА(у) с помощью правил 18 и 19. (б> Из аксиомы Ч хА(х) ь У хА(х) с помощью правил 1б и 17. 5. Использовать задачу 3 и правила 16 и 17. 8.

Следует из задачи 7. 9. Следует из задач б и 8, См. также указание к задаче 18 из з 5. 11. Индукцией по числу шагов построения А, используя задачи 1, 9 из э 3 и задачи б и 8. 12. См. указание к задаче 28 из 9 1. 14. (а) Нет. (б) Да. (в) Да. 15. (а), (б> усвободнодляхвА(х) иуневходитсвободновА(х). 17, (а) Из аксиомы 11 по правилу11. (б) Из аксиомы 12 по правилу Н1. (в) Доказать сначала (ЧуА(х, у) э 3 хА(х, у)). 18. (а) Нет. (б) Да. 21. Пусть В, ...,  — вывод В из Г, А н Л(В.) — соответствующие Г"' 1 этому выводу множества формул. Докажем индукцией по длине вывода, что каждая из формул (А Э В.) (1 < 1 < й) имеет вывод из Г, причем в этом выводе Л (А Э В,) С Л(В.) Г1 Г. Рассмотрим лишь случай, ч и мАтемАтическАя лОГикА Я 61 207 когда В.

есть непосредственное следствие В. = (С Э А (х)) по прави- 1 1 . 1 лу 2. По предположению индукции имеем Г ь (А З (С З А1(х))) и Л,((А Э (С Э А (х)))) С Ь((С ~А,(х))) Г1 Г и х не входит свободно в С и формулы из Л((С ~ А (х))). Возможны два случая. 1. А Ю Л((С Э А,(х))). Тогда Г 1-(С 7ЫуА,(у)) и Г ь(А Э (СЗ З ЧуА (у))) по аксиоме 1. Имеем Л ((А Э (С 7 ЧуА,(у)))) С Л((С» Э ЧуА,(у))) Г1Г. 2. А Е Л((С ~А (х))). Тогда х не входит свободно в А и в 1 Л ((А ~(С ~А (х)))). Тогда Г ь (А З (С ~ А (х))), Г ь ((А ЙС) ~А,(х)), Г ь((А 8С) ~ЧуА (у)), Г «(А ~(С ЭЧуА (у))).

Следовательно, Л ((А Э (С Э Ч уА (у)))) = А (А Э (С ~ А (х))). 24. (в) Пусть Т вЂ” аксиома без свободных переменных. Тогда Г ь (Т Э А(х)), Г ь (Т ~ Ч хА(х)), Г ь Ч хА(х). 26. В формулах вывода В из А заменить все связанные вхождения переменных г, ..., з на переменные х, ..., х, не входящие ни в одну 1' ''' в 1' ''' ь' из рассматриваемых формул. Доказать, что получится вывод В из А, 27. Использовать задачу 26. 28. Если в выводе А из Г использовались константы или функциональные символы, не входящие в о, то заменяем везде в выводе константы на переменные, не входящие в зтот вывод, а Дх, ..., х„) на х . Доказать, что полученная последовательность формул будет выво- 1' дом А из Г. В полученном выводе все атомные подформ1лы с предика- тами Ине о заменяем на Я = ЧУ(у, ...,у), где Д вЂ” предикатный символ из о, а у — переменная, не встречающаяся в выводе.

Доказать, что получится требуемый вывод. 29. Доказать аксиомы и правила вывода ИП в ИПС. 30. См, указание к задаче 30 из й 3. 31. См. задачи 8, 29 и 30. 32. Индукцией по длине вывода А из Г. 34. Следует из задачи 32. 35. См. указание к задаче 25 нз з 3. 37. Перенумеруем все предложения сигнатуры гл А, А1, А, гов ОТВЕТЫ, РЕШЕНИЯ, УКАЗАНИЯ Положим Т =Т, О Т, О (А,.), если Т,!! (А,) непротиворечиво, Т. !+! Т. У (-! А.» в противном случае, ! ! Т~ О Т, !е т Доказать, что все Т.

непротиворечивы, Т полно и непротиворе- ! чино. 39. (б! Пусть Г !1ЧхА(х). Тогда Г ~--тЧхА(х), Г ьЭх-~А(х), Г !- -~ А(1) и Г !1А(1) для некоторого 1. 41. Пусть А,Л, ... — все предложения сигнатуры о' = о О О' !' ''' ! ! (с,, с, ...), где с! — предметные констаты, не входящие в а. По- ложим Т =Т, О Т. !.! (.~ А.), если Т.!! (А.)противоречиво, Т, О (3 хВ(х), В(с)), если Т, !! (А,) непротиворечиво, А! имеет вид 3 хВ(х) и с.

— первая ! константа, не входящая в Т, и Л., ! ! в противном случае !+! Т !.! (Л.) Т= О Т, !и Ф' Доказать,что все Т. непротиворечивы, Т непротиворечиво и полно в сигнатуре о' (см. задачи 40, 36!. Определим % = (М; о). Пусть М— множество термов сигнатуры о' без свободных переменных. Определим на М функции и предикаты из гл значение1(1, ..., 1 ) есть терм!(11, ..., ! ); 1)! ~р(1, „,1) ° Т ьр(1„..., 1„).

Доказать индукцней по числу шагов построения формулы Л(х,, ..., х ), что для любых 1,, ..., 1 Е М имеем й р А(1, ..., ! ) с» !ь т !- А(1, ..., 1 ). Тогда 1П есть искомая система. !'' 'л 42. Построенная в указании к задаче 41 система является счетной. См. также задачу 34. 43. ( ° А) непротиворечиво; см. далее задачи 41 и 42.

44. Следует из задачи 25, 33, 43. 209 ч.и. млтнмлтнчнскли логикл И 71 45. Следует из задачи 43. 4б. Следует из задачи 42. 47. Множество Г О ( -1 А) невыполнимо и, следовательно, противоречиво. 48. Если Г невыполнимо, то Г противоречиво (см. задачу 41). Так как всякий вывод содержит только конечное число формул, то существует конечное подмножество Г С Г, являющееся противоречивым и, 1 значит, невыполнимым. 49.

Если Г невыполнимо, то существует конечное противоречивое подмножество Г С Г (см. указание к задаче 47), Конъюнкция формул из Г составляет противоречивое множество. 50. Следует из задач 32 и 48. 51. Следует из задачи 50 и того, что всякий вывод конечен. 52.

Следует из задачи 13 из б 5 и задачи ЗЗ. 53. Следует из задачи 4 из б 5 и задачи 44. 54. Использовать задачу 44. (а), (б), (г) Нет. (в), (д) Да. й 7. Аксиоматические теории 1. Индукцией по числу шагов построения г и А. 2. См. задачу 50 из з б. 3. См. задачу 50 из з б. 4. Пусть в % = (М; о) истинны все аксиомы Т.

Положим х — у«»% ~х = у. Доказать, что — — эквивалентность на М, а 3[ = (М/-; и), ! где а =[а„[, У([х,[,...,[х ))=Ях(,...,х)[, Р([х,[,...,[х ])= = Р(х ...„х ), для а1,Л, Р Ест,есть требуемаямодель. 5. Следует из задачи 41 из б б и задачи 4. б. Следует из задачи 50 из з б и задачи 4. 7. Пусть С вЂ” атомная формула. Ищем в С первое вхождение терма Л(, ..., 2„), где(, ..., г несодержатУ.

ПустьС'естьрезультатзамены этого вхождения в С на переменную г, не входящую в С. Положим С+ = Э х(А((,, ..., (», х)$С'). Продолжая этот процесс, получим формулу С* для С, не содержащую). Если С не содержите то С = С. г!о ОТВЕТЫ, РЕШЕНИЯ, УКАЗАНИЯ Далее обозначаем через В' для любой формулы В результат замены калсцой атомной подформулы С на С .

Утверждения задачи следуют из задачи 21 из 9 5 и задачи б. 8. множествот, = т О (в!, и"з, ...),где»",, 8з, ...взятыиз задачи 43 нз б 5, выполнимо и, следовательно, непротиворечиво. Ввиду задачи 42 из 9 б множество Т, выполнимо в счетной системе Я!. Поступая так же, как в указании к задаче 4, получим нормальную модель й, для т .