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

12. (а) ЧхЧуЧг(5(х, у, г) З 5(у, х, г)); (б) ЧхЧЧЧгЧиЧчЫп ((5(х, у, и) $ Б(и, г, г) 63(у, г, |г)):) 5(х, |г, я)); (е) Чх 3 У(П(у)8х и у) (П из 9 (е), Я из 10 (6)). 13. Все предложения ложны в системе %, 20. (а) Р = Чх)!(х, х); (б) С ЧхЧУ(Л(х, у):) г!(у, х)); (в) Т и ЫхЧУЧг ((Я(х, у) ЬЯ(у, г)) Л Я(х, г)); (г) (РВСН) (Р, С, Т из (а), (6), (в) ) . 2!.

(а) Ч, - Ых(х и х); Ч ЧхЫУ ((х и уеду ( х) Э х = у); Ч ЧхЧУЧг((х ~ уеду Я г) З х и г); (б) Ч,, Ч, Ч из (а), ЧхЧУ (к и у ч у ~ х), 22. Пусть х = у Я(х, у)$Д(у, х)). (а) ЧУЯ(х, у); (б) Чу Я(у, х) ~ у = х). 23. (а) х = у П г (Ц(х, у) о Д(х, г) $ $Ы и(Я(и, у) ЬЯ(и, г)):) Д(и, х))); Ч. Н. МАТЕМАТИЧЕСКАЯ ЛОГИКА Ц З) (б) х = у О г Щу, х)8(2(г, х)8,Ыи(Я(у, и)ЙЯ(г, и)) З(г(х, и))); (в) х = и с» Ыу()(х, у); (г) х = А Ы у(2(у х)' (д)х= — у ЭгЗи(г=хГ)уйг=ийи=х()уйи=А) (О,О, и, А из предыдущих пунктов). 24. (а) хСу Дх,у) = х. (б) Пусть х = и и Ыу (х ~ у) (~ из (а) ). Тогда «х — одноэлементное множество» - (Ыу((у С х) Э (у = х чу = о)) 8, - х = о).

29. ((Р (0)8Ых(Р (х) Э Р (8~(х)))) ~ ЫхР (х)). 30. Пустьх < у (Ц(х,у) 8-1 Д(у, х)). Тогда (Ыу (Ы. (х < у ~ Р(х)) ~.Р(у)) ~ ЫуР(у)). ф 5. Выполнимость формул логики предикатов 2. См. (д) определения истинностного значения в з 4. 4. Пусть А — бескванторная формула и А, ..., А — различные атомные формулы, являющиеся подформулами А. Требуемая формула получается заменой всех вхождений А, ...,А„вА на пропози!'"' « циональные переменные Р, ..., Р соответственно.

5. (в) Например, А ЫхВуР(х,у); 3Й=(.4',Р), где Р(х,у) =и«» «»хсу, б. Иидукцией по числу шагов построения формулы А. 7. (а) Выполнима в (4',Р), где Р(х) = и «» х — четное число. (б) Выполнима в (.4',Р), где Р(х) — тождественно истинный предикат.

(в) Невыполнима. Пусть ! — модель, в которой эта формула истинна. Тогда существует элемент а из 5)) такой, что 5)) ~ Ыу ((1(а, а) 8 8-1 Ц(а, у)). Отсюда имеем % ~ Я(а, а)8 .«Я(а, а)). Приходим к противоречию. (г) Выполнима в модели из (а). (д) Выполнима в ( Ф'; Д, )«), где Д(х, у) = и «» х ге у; 1«(х, у, г) = = и «» х + у < г. (е) Выполнима в ( 4', Р), где Р(х) тождественно ложен. 8. (а) Нет. Формула ложна в ( Ф'; Р), где Р(х) = и «» х — четное число. (б) Нет. Формула ложна в(Х; Р), где Р(х) = и для всех х. (в) Да. (г) Нет. Формула ложна в (,4'; Я), где Д(х, у) = и «» х < у. 202 ОТВЕТЫ, РКШЕНИЯ, УКАЗАНИЯ 19, (а) А(х) и З ур(х, у), г =у . (б) А(х) ИЧуР(х, у), Г = у.

11. Формула выполнима в (,4", Р), где Р(х, у) и «ь х < у. Пусть формула выполнима в а) = (М; Р). Заметим, что Р(т, т) = л для всех т Е М. Пусть а — произвольный элемент из М. Среди элементов х О таких, что Р(а,, х) = и, выберем произвольный и обозначим его через а . Среди элементов х таких, что Р(а, х) = и, выберем произвольный Г 1' и обозначим его через а .

Продолжая этот процесс, получим последовательность элементов а,, а, а, ... Докажем, что все эти элементы различны. Если 1<), то Р(а„а, ) = и, Р(а., а, ) = и, ... ..., Р(а, а) = и, а значит, Р(ар а) = и. Таким образом, а. и а .. 12. Докажем, что если данная формула ложна в какой-то модели 3Й = (М; Р), то Ф ~ 4. Ложность этой формулы в модели означает, что для любого х ЕМ найдется р(х) ЕМ такое, что Р(х,р(х)) = и, Р(д>(х), х) = л, Р(х,х) и Р(р(х), р(х)). Отсюда х ««р(х) для любого х е м.

имеем х ы д»р(х) для любого х е м, так как в противном случае было бы Р(р(х), рр(х)) = и, Р(р(х),х) = л. Так как Р(х, х) и ~ Р(р(х), р(х)), Р(р(х), р(х)) и Р(рр(х), (ор(х)), Р()вр(х), р(а(х)) и -с Р(р«»р(х), «»)»р(х)), то Р(х, х) ««Р((вр(в(х), «»рр(х)), т. е. х и рр(а(х). Итак, для любого х Е М элементы 1>(х), «»р(х) и «»рр(х) отличны от х. 13. (а) Докажем, что если данная формула ложна в какой-то модели 5)1 = (М; Р), то М вЂ” бесконечное множество. Ложность этой формулы означает, что для любого хем существует и(х) ем такое, что Р(х,х) = и, Р(р(х),х) = л и для всякого х ЕМ имеем (Р(д>(х), г) ~ Р(х, з)) = и.

Строим последовательность (у~(х)), где р~(х) = х, р(~~(х) = р(р'(х)). Пусть ( с )) Тогда имеем Р(р((х), р) (х)) = и, но Р(ЗР(х), р~ (х)) = л, т. е. р (х) ««(а((х). Таким образом, данная последовательность состоит из раличных элементов. Данная формула не выполняется в 5Л = ( 4'; Р), где Р(х,у) = и«ьх и у. 14. З хР (х) $ З хР (х) $ 3 хР (х) б З хр (х) $ 3 хр (х) 8 $ Ч х $ (Р,(х) ~ Ъ -1 Р(х)) ~)=( ' )~( 15. (а) Пусть в системе Й = (М; о) данная формула ложна. Это означает, что в этой системе ч 3хА(х) = и, -1ЧхА(х) = л, т.

е. ЗхА(х) = л иЧхА(х) = и. Так как Мм а, тотакого быть не может. (б) Если бы данная формула была ложной в системе й) = (М; и), то в этой системе 3 х(А(х) ЦВ э С(х))) = и, Ч х(А(х) Э ч С(х)) = и, 2ОЗ «В* л. Пусть я»ИВК таково,-по А(п»)'=и, (В'~ С(л«)) = и. Тогда я'А(в») з '-т С(л»)) и, а значит, С(л«) = л. Имяем йз = л, что противо- речит"«В = л. (в) Пусть в систеь«е28 (М; а) данная формула ложна. Это озна- азет, что а этой оисвеме Ы х(А(х) «ч В(х)) = и, Л хА(х) = и, 'Ы хВ(х) = и.

Сун»еогвует «в Е М такое, что А(«л) = н. Имеем (А(т) «ч В(«п)) = н, т. е. В(в») = л, чтопротиворечит Ы хВ(х) = и. (г) Если бы данная'формула была ложкой в системе 1)) = (М; а), то в атой системе Ы х(А(х).:» - В(х)) = и, Ы хА(х) = и, Л хВ(х) = и. Су- ществует п««е М завов, что В(и») = и. Имеем, (Я(«««) ~ - В(и«)) = н, .е-«А(п«) л, чтозгротт«воречнт'Ыж4(х) = и. 18. Иидукцией по числу.шагов построения формулы, используя вадачк,)б и 17; где необходимо, переименовывать связанные перемен- ные повидаие 1б (с),(т). 19.4а) Ы х3 уЫ ДВи чА! '(б) Э х Э гЫ у (А(х, у)ЗВ(з,:у)); «(в) "3 ХУД«Ы х(А(х, у) ««В(х, х)); , (г)Ы хЬРЗ хЫ»(А(х,у) ~ В(х, »)).

20. Пои»жнм значение функции У. «чш.термах», ..., » равным « терму У «(», ..., » ). Предиката( определяем произвольным образом. ! !' "" ««« « 21. (а) Иусть а,...,а ЕМ. БслиЯ)!)РЯ0« ...Зу В(а,...,а, у! «««« .;. у ), по ".берем в качестве»р(а, ..., а-) такие «««,, что !'"' и (1)( ~ В (,, ..., „; Ь,, ..., б ). Если 1)) «» Эу, ...Эу В(а, ...,а„,:у,, „у ), то в -качестве у«,(а,, ..., а ) можно взять я»роизвольиьш элементы. (б) Следуетиз (а). «22 ыхыу(((уь р)(х)) ти(у >х)) Щ~2(х, у) < «р (х))8 -«(р (х„у) сх)). Например, р,(х) = х + 1, х«(х, у) х.

22. ЫхЫ у(Р(«(, р \~~Ц8 Р(у,««р (х,у)))."П~~им«р.(х;у) = 1.~ "«(х .'О) и! «рз(х, у) = 1 )Р(х, 1) (х — 1, !если:хо О, О ='0 ' 2 .25.'Следует нз задачи 21, 2б «(а):Пусть в некоторой системе 1)! = (М; а; Р) .формула 3 иЫ хт1уЛ(и,х«у) .истинна, а,формула 3 и (Ых (Эу А(и, х, у) « ОТВЕТЫ, РЕШЕНИЯ, УКАЗАНИЯ 204 ЭР(и,х)) Э ЧхР(и, х)) ложна. Тогда существует а т М такое, что й 'уЫхЭуА(а, х,у), й уЫх(ЭуА(а,х,у)эР(а,х)) ий )(ЧхР(а, х). Пусть х тМ таково, что Р(а, х ) =л. Тогда й )! Зу А(а,х,,у) н й ')( Ч х 3 у А(а, х, у).

Приходим к противоречию. Обратно, для любой системы й = (М; а) строим систему й =(М;а; Р), где й ~ Чи Ых (Р(и, х) гв ЛуА(и, х,у)). Тогда й ~ (Чх (Зу А(а, х,у) ЭР(а,х)) ! Ых Р(а,х)) для некоторого аЕМ.Поэтомуй уЫх Р(а,х)и,значит,й ~ Ли Чх Эу А(и,х,у). (б) Заметим, что А — Э Р А и Э и (Ч х (3 у А(и, х, у) э Р(и, х)) ~ ЭЧхР(,и,х)) Ли 3з3у Ых ((А(и, з,у) Э Р(и, г)) ЭР(и, х)).

Приводя А к пренексной нормальной форме (см. задачу 18) и используя несколько раз (а) и вышеприведенную эквивалентность, получим ис- комуюА . 27. Имеем А ~ А* (см. указание к задаче 2б (а) ). Пусть А = Зи Ч х 3 у Ц(и, х, у). Тогда в 4', где Д(и, х, у) = н «» «»у< х, Р(и, х) тождественноистинен, А истинна,А ложна. (х, если хтМ, 29. Пусть Ь ~ М н )г(х) = 1 Индукцией по числу шагов построения А доказать, что для любых с,, ..., с Е М, имеем й, ~ А(с,, ...„с ) й 'у А()в(с,), ..., )»(с )). 31. Использовать задачу 30. 32.

Использовать задачу 31. 33. Если Чх, ...Ых А(х,, ..., х ) ложна в какой-то модели т !'"' т й = (М; а), то существуют а, ..., а я Мтакне, чтоА(а, ..., а ) = л. 1'"' т !' ''" т Тогда данная формула является ложной и в подмоделн й = (М; а), 1 !' где М = (а, ..., а ). Если'некоторые из а, ..., а совпадают, то нс- 1 1'"' т' 1* ' т пользовать задачу 29. 34. Если Зх, ... Зх А(х,, ...,х ) ложна в какой-то модели и! 1'' ' т й = (М; и), то она является ложной и в подмодели й = ((а); а), где а е М (см.