В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 60
Текст из файла (страница 60)
Истинны высказывания б), г), е), з), к). 31. а) Р = Ап х = а, у = Ь; б) Р = Ап х = а, у = Ь; в) Р= Ап у = а; г) Р = Аг, д) Р = Аз, х = Ь, у = а; е) Р = Ат или Р = Аз,' ж) Р = Аг, х = Ь, у = а; з) Р = Аь х = а, у = Ь. 32. а) Предикат «х < у» на множестве отрицательных целых чисел У; б) предикат «х' + у' < О» на множестве действительных чисел Я; г) предикат «х < у» на множестве действительных чисел Я. 33. б) Предикат «х' + у' < О» на множестве действительных чисел Я; г) предикат «х < у» на множестве целых чисел У. 35.
Выполнимы все, кроме в), з). 38. б) Рассмотрите М= (5, б) и предикаты Р(х); «5 ~ х», Д(х): «3 ~ х»; в) рассмотрите М = Ф и предикаты Р(х): «х — простое число», Д(х); «х > 10», Я(х): «х — составное число»; д) сравните первую формулу с известной тавтологией алгебры высказываний (Р -+ Д) ~ (Д -+ Р). Докажите, что первая из данных формул логики предикатов также всегда будет превращаться в истинное высказывание, т.е. является тавтологией логики предикатов. Вторая же формула этим свойством не обладает.
40. Нет, примером может служить формула (»хНЭуН'Ф~НР(х, у, ~)). Поменяйте местами кванторы общности и в обе формулы вместо переменной Р(х, у, ~) подставьте конкретный предикат «(х — у)л = О». 45. Тавтологиями являются лишь формулы в), д), е), з). 51. а) (ЭхН-чР(х) ч (»уНЦ(у))); б) (ЬхНР(х)) и (~~уН-ч Д(у)); в) (ЭхН-юР(х)) ч (Д(у) л (Э~Н~Я(~))); г) ((ЭхНР(х)) л (ЭуН-чД(у))) ~ А(~); д) (ЭхНР(х) л ~о(х)) «('»уНЯ(у) г ~Я(~)); е) (ЭхНЪуН(Р(х) л ~Р(у)) «(Р(у) л ~Р(х))); ж) (ЭхНР(х, у) л ('»уН-зД(у))); з) (ЭхН(ЭуН-тР(у)) «Д(х)) л (ЭуН'ФхНД(х) л -~Р(у)); 290 и) (ЧуН(Р(у) л (ЛхН-1Ц(х))) ч ((ЧхНД(х) л ~Р(у)))); к) (ЭхНЪуНЭ~НР(х, у, е) л (чгН-зфх, г) ч -зД(у, г) ч -юО(~, г))).
52. а) (ЭхНЪ'иНЭуН(Р(х) -+ Д(х)) -+ (Р(и) -+ Д(у))); б) (ЛхН'с~уНР(х) -+ Д(у)); в) (Ухни)(УгНУа)(Ях, у) ч (Ц(и, и) -+ (Я(0 ~) -+ Д(а, а)))); г) (ЧуНЭ~НД(у, Е) -+ Я(х, Г, Е)); д) (ЭуНЦ(х, у) -+ Я(х, х)); е) (ЪхНР(у) -+ -з(Д(х, у) -+Р(у))); ж) (Ъ'хНЛиНЯ(х, у, е) -+ О(и, у)); з) (ЛхНч'иНч'о)((Р(х) ч Яи)) л (В(у) -+ Я(и))); и) (чхН'ФиН'Ф~Н'ФиНР(х, у) ч (Р(и, и) -+ -ю(Д(у, ~) -+ Р(в, ~)))); к) (ЛиН(Р(у) л Д(х)) -+ -чЯ(и, ~)); л) (ЭхНЪуНЛ~Нч'иНР(х, у) -+ Яи, ~)). 53. См.
задачу 9.59. 55. (Лх, у, ~, иНЯ(х, у) л Я(х, е) л Я(х, и) л Я(у, ~) лЯ(у, и) л л Я(, и) л (МН-Я(0 ))). 67. а) Нет; б) да; в) нет; ж) да; з) да; и) нет; к) да. 68. а) Да; б) да; в) нет; г) да; д) да. 8 10 1. б) (ЛхНР(х)) л (чхНчуН(Р(х) л Р(у)) -+ (х = у)); в) (ЭхНЭуНР(х) л Р(у) л (х ~ у)); г) (чхНчуН~~НР(х) л Р(у) л Р(~)) -+ ((х = у) ч (х = ~) ч (у = г)); д) конъюнкция в) и г).
4. в) (ЧА, ВН((А ~ В) -+ (Л(Н(А е 1) л (В е !))) л ((ч'РН(А ер) л л (В а Р)) -+ (Р = П)); и) х ~ 1 л х и 2 л (ЧтН'ФлН(х = тл) -+ Ят = 1) л (и = х)) ч ((т = = х) л (и = 1)). 6. и) Ни одно нечетное число не делит никакое простое число. 9. Верны а), г). 10. а) Верно; б) верно; в) верно; г) не верно; д) не верно; з) верно; и) верно; к) не верно. 13. а) ((г(х) > 0) л (я(х) > 0)) ч ((Ях) < 0) л (8(х) < 0)); б) ((~(х) > 0) л (8(х) < 0)) ч ((Ях) < 0) л (8(х) > 0)); в) (~ (х) > 0) л (я(х) > 0) л (~ (х) < (8(х))2"); г) ((8(х) > 0) л 9(х) > (я(х))'")) ч ((8(х) < 0) л Ях) > 0)); е) (-8(х) < Ях)) л (Ях) < 8(х)); ж) (Ях) > я(х)) ч (Ях) < -8(х)); з) ((х > 0) л (Ях) = я(х))) ч ((х < 0) л (г (-х) = 8(х))); и) ((Ях) > 0) л (~(х) = я(х))) ч ((Ях) < 0) л ( — Дх) = я(х))) ч ч ((8(х) > 0) л (Ях) = 8(х))) ч ((8(х) > 0) л (-,Ях) = 8(х))); к) ((~(х) > 0) л (Ь(Ях)) = 8(х))) ч ((Ях) < 0) л (Ь(-Ях)) = 8(х))).
14. в) -6 < х < -5; г) (х > 3) ч (х < -6); д) (х < -5) ч (х > 4); е) (О < х < 1/2) ч (1 < х < 2) ч (3 < х < 6); ж) х > — 4; з) х = О. 291 5 11 1. Рассмотрим в качестве формулы Г(х) формулу (ЭуКР(х у)) и подставьте ее в аксиому (РА1). Проверьте, что полученная формула не будет общезначимой. 2. Рассмотрите предикаты А(х): б ~ х и В(х): 3 ) х над Ф. 4. б) Доказательство аналогично предыдущему, но использует аксиому (РА2) и Э-правило: (1) (ЭхКГ(х)), (2) У(х) -+ (Эу)Щу)), (3) (ЭхКГ(х)) -+ (ЭуКГ(у)), (4) (ЭуКГ(у)). 5.
а) (1) (чхКГ(х)) -+ Г(у), (2) Г(у) -+ (ЭхКГ(х)), (3) ('о'х) (Г(х)) -+ (ЭхКГ(х)); б) (1) (чуКГ(х, у)) -+ Г(и, е), (2) ('сгхКтуКГ(х, у)) — > Г(и, е), (3) (ЪхК~уКГ(х, у)) -+ (~и)(Г(и, и)), (4) (ЪхН~гуНГ(х, у))-+ -+ (~ге)С~и)(Г(и, е)), (5) (мх)(Чу)(Р(х, у)) -+ (~/уКЧхКГ(х, у)), (б) (чуКчхКг1х, у)) -+ (тхКчуКГ(х, у)), (7) ('ФхКчуКГ(х, у)) ++ ++ (ЧуК'ФхНГ(х, у)); г) (1) (чуКГ(х, у)) -+ Г(х, и), (2) Г(х, о) -+ (ЭиКГ(и, о)), (3) (чуКГ(х, у)) -+ (ЭиКГ(и, а)), (4) ('чуКГ(х, у)) -+ (~юКЭиКЩи, и)), (5) (ЭхКЧуКГ(х, у)) -+ (УеКЭиКГ(и, а)), (6) (ЭхК~~уКГ(х, у)) -+ -+ (туКЭх)Щх, у)).
б. б) Начните с теоремы а): (1) (ЭхКГ(х)) ++ ~(чхК~Г(х)), (2) (ЭхКГ(х)) -+ (~ГхК-Г(х)) (3) -ИхК зГ(х)) -+ (ЭхКГ(х)) (4) -з-ч('ФхК-чГ(х)) -+ -з(ЭхКГ(х)), (5) -ю(ЭхКГ(х)) -+ ~ ~(ЭхК~Г(х)), (о) (ЧхК~Г(х)) -+ -и-и('с~хК-иГ(х)), (7) (тхК-зГ(х)) -+ -з(ЭхКГ(х)), (8) тч('ФхК-зГ(х)) -+ (~хК-юГ(х)), (9) -ч(ЭхКГ(х)) -+ ('ФхК~Г(х)), (10) -ч(ЭхКГ(х)) ++ (чхК-иГ(х)). 7. б), в) Эти правила непосредственно вытекают из аксиом (РА1) и (РА2) соответственно по правилу вывода МР. 8.
а) (1) (чхКГ(х) -+ 6(х)), (2) (чхКГ(х) -+ 6(х)) -+ (Г(у) -+ -+ 6(у)), (3) Г(у) -э 6(у), (4) ((ЧхКГ(х)) -+ Г(у)) -+ ((Г(у) -+ -+ 6(у)) -+ (('о'хКГ(х)) -+ 6(у))), (5) (чхКГ(х)) -+ Г(у), (6) (Г(у) -+ -+ 6(у)) -+ ((Ъх)(Г(х)) -+ 6(у)), (7) (Ъх)(Г(х)) -+ 6(у), (8) (~гхКЩх)) -+ (~гуК6(у)), (9) (~х)(Г(х)) -+ (ЧхКб(х)); б) (1) Г(у) -+ 6(у), (2) 6(у) -+ (ЭхК 6(х)), (3) Г(у) -+ (ЭхК 6(х)), (4) (ЭуКГ(у)) -+ (ЭхКб(х)), (5) (ЭхКГ(х)) -+ (ЭхК6(х)); в) (1) (Ъ'хКГ(х) -+ 6(х)), (2) (тхКГ(х) -+ 6(х)) — э (Г(у) — > 6(у)), (3) Г(у) -э 6(у), (4) (ЭхКГ(х)) -+ (ЭхКб(х)); г) (1) (Ъ хК 6-+ Г(х)), (2) (ЪхК 6-+ Г(х)) -+ (6-+ Г(у)), (3) 6-+ -+ Г(у), (4) 6 -+ (чуКГ(у)), (5) 6 -+ (чхКГ(х)); д) (1) (~хКГ(х) -+ С), (2) (~хКГ(х) -+ 6) -+ (Г(у) -+ 6), (3) Г(у) -+ б, (4) (ЭуКГ(у)) -+ б, (5) (ЭхКГ(х)) -+ 6; е) (1) (Эх)(Г(х)) -+ (~1х)(6(х)), (2) (Чх)(6(х)) -+ 6(у), (3) (ЭхКГ-зу(х)) -+ 6(у), (4) Г(у) -+ (ЭхКГ(х)), (5) Г(у) -+ 6(у); ж) (1) (Эх)Г(х)) -+ (чхК6(х)), (2) Г(у) -+ 6(у), (3) (Г(у) -+ -+ 6(у)) -+ (ЭхКГ(х) -+ 6(х)), (4) (ЭхКГ(х) -+ 6(х)); з) (1) (ЭхКГ(х)) -+ (ЧхК 6(х)), (2) Г(у) -+ 6(у), (3) (~ГхКГ(х) — э 6(х)); 292 и) (1) ('тхНГ(х) ++ 6(х)), (2) Г(у) ++ 6(у), (3) Г(у) — э 6(у), (4) 6(у) -+ Г(у), (5) (ЭхНГ(х)) -+ (ЗхНб(х)), (6) (ЗхНб(х)) -+ -+ (ЭхНГ(х)), (7) ((ЗхНГ(х)) -+ (ЗхН6(х))) -+ (((ЗхН6(х)) -+ -+ (ЗхНГ(х))) -+ ((ЗхНГ(х)) ++ (ЗхНб(х)))), (8) ((ЗхН6(х)) -+ -+ (ЗхНГ(х))) -+ ((ЗхНГ(х)) ++ (ЗхН6(х))), (9) (ЗхНГ(х)) ++ ++ (ЗхН 6(х)).
9. б) Начните с только что доказанной теоремы: (1) -з(~'х) (Г(х)) ++ (Зх)(-1Г(х)), (2) -з(Чх)(Г(х)) -+ (Зх)(~Г(х)), (3) (ЗхН-чГ(х)) -+ -з(тхНГ(х)); (4) ~(ЭхН~Г(х)) -+ -з-ю(ЧхНГ(х)), (5) -гч(тхНГ(х)) -+ -ч(ЗхН-зГ(х)), (6) -ю-~(ЪхНГ(х)) -+ (тхНГ(х)), (7) -ч(ЗхН-чГ(х)) -+ (тхНГ(х)), (8) (чхНГ(х)) -+ -п(чхНГ(х)), (9) (ЧхНГ(х)) -+ ~(ЗхН-зГ(х)), (10) (ЧхНГ(х)) ++ -ч(ЗхН-чГ(х)). 11. в) Покажем сначала, что 6-+ Г(у), б ~- (Зх)Щх)): (1) 6-+ -+ Г(у), (2) 6, (3) Г(у), (4) Г(х), (5) (Зх)(Г(х)).
Из этой выводи- мости по теореме о дедукции заключаем, что б -+ Г(у) ~- 6 -+ -+ (ЗхНГ(х)). Из этой выводимости по правилу УКС (задача 11.10) заключаем, что (ЗуН6 -+ Г(у)) >- б -+ (ЗхНГ(х)) или (ЗхН6 -+ -+ Г(х)) ~ — б -+ (АКР(х)); г) докажите сначала, что Г(у) -+ 6, (чхНГ(х)) >- б. Затем примените теорему о дедукции и правило УКС (задача 11.10). 12. а) Из задачи 11.8, г по теореме о дедукции получаем теорему (ЧхН6 -+ Г(х)) -+ (6 -+ (тхНГ(х))), а из задачи 11.11, а— теорему (б -+ (тхНГ(х))) — ~ (~хНб -+ Г(х)). Из них по правилу л-вв приходим к требуемой теореме; б) из задачи 9.8, д по теореме о дедукции получаем теорему (чхНГ(х) -+ 6) -+ ((ЗхНГ(х)) -+ -+ 6), а из задачи 9.11, б — теорему ((ЗхНГ(х)) -+ 6) -+ -+ (чхНГ(х) -+ 6).
Из них по правилу л-вв приходим к требуемой теореме; д) исходя из определения связки ~ нужно доказать теорему (чх)(-~ б -+ Г(х)) ++ (-1 6 -+ (тхНГ(х))). Она доказана в задаче 11.12, а5 е) исходя из определения связки л нужно доказать теорему (ЗхН-1(Г(х) -+ ~6)) ++ ~((ЗхНГ(х)) -+ ~6). Она будет доказана из теоремы задачи 9.9, а и приводимой ниже теоремы на основании следующего правила вывода ФИВ: Р++ Д, Д++ Я ~= ~= Р ++ Я, ~(ЪхНГ(х) -+ ~6) ++ ~((ЗхНГ(х)) -+ ~6).
Последняя же теорема, в свою очередь, будет доказана (на основании правила контрапозиции в ФИВ), если будет доказана теорема (чхКГ(х) -+ — ~ ~ 6) ++ ((ЗхНГ(х)) — ~ ~ 6). Она доказана в задаче 9.12, б; ж) докажем сначала, что (чхНГ(х) л 6(х)) >- (ЧхНГ(х)) л (Чх)(6(х)): (1) ('ю'хНГ(х) л 6(х)), (2) (ЪхНГ(х) л 6(х)) -+ (Г(у) л 6(у)), (3) г1у) л 6(у), (4) Г(у), (5) 6(у), (6) (чхНГ(х)), (7) (УхН6(х)), (8) (тхКГ(х)) л (1гхНб(х)). Следовательно, по теореме о дедукции имеем -ч(Ъ'хНГ(х) л 6(х)) -э ((чхНГ(х)) л (ЧхН6(х))). (*) Теперь докажем, что (чх)(Г(х)) л (тх)(6(х)) ~ — (АКР(х) л л 6(х)): (1) (охНГ(х)) л (~хНб(х)), (2) (ьх)Г(х)), (3) ('~хйб(х)) 293 (4) (»зх)(Г(х)) -+ Г(у), (5) Г(у), (6) (ох)(6(х)) -з 6(у), (7) 6(у), (8) Г(у) л 6(у), (9) А, (10) (Г(у) л 6(у)) -+ (А -+ (Г(у) л 6(у))), (11) А -+ (Г(у) л 6(у)), (12) А -+ (ох)(Г(х) л 6(х)), (13) (ох)(Г(х) л л 6(х)). Следовательно, по теореме о дедукции $-((Чх)(Г(х) л (Ь»х)(6(х))) -+ ('Фх)(Г(х) л 6(х)).
(о*) Из теорем (о) и (оо) по правилу л-вв получаем требуемую теорему. 1. б) 111111ао1; в) 1ао1111; г) 1111111; д) 1111111; е) 11111111; ж) 111111; з) 111...11 (/с+ 1 единица). 2. а) ао; б) 1; в) ао; г) ао; е) 1ао111; ж) 11аоаоаоаоаоаоаоао1; з) 11аоаоаоао1' 3. в) д! ао -+ д4П, %1 -+ дзЛ, дзао -+ доП, дз1 -+ дзЛ дзао -+ доП, дз1 -+ дЛ, д,1 -+ дзао доао -+ до1, дзао -+ доП, дз1 -+ ао, доао -+ до д61 + дзао дзао + дои» д71 + ао 4. а) 111111; б) 111111; в) 1111; г) 111; д) 11111; е) 11111; ж) 1111. 5. а) 1; б) ао, в) 111; г) 11; д) 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
