В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 56
Текст из файла (страница 56)
а) ((х ч у)(х' ч у'), (х ч у) ++ ~); б) (у,х); в) (ху', Ц; г) ((х+ у)~, Ц; д) (х'у' ч х'г,' ч у'~', х+ у), (х+ у, ху, Ц, (х'у' ч у'~' ч х'~', Ц, (х'у' ч х'г,' ч у'~', ху); е) ((х -+ у) -э ~, х'И, (х', худ); ж) (х -+ (у -+ ~), х + у), (х -+ (у -+ а), 0); з) (х ч у~; х+ у, Ц, (х ч у~, О, Ц; и) (ху ч ~, х++ у, О), (ху ч ~, О, Ц; к) (ху ч у'~, О, Ц, ((у-+ х)(у' -+ х), О, Ц; л) (~ч хг.', х+у, Ц, (ач хг', х++у, Ц. 1. а) хуч ~ч г; б) худ; в) х; г) х'; д) 1; е) 0; ж) ху ч гх', з) х'у' ч ч одг; и) (х ч у)(г, ч !); к) х(у ч ~)а 2.
а) ((х' ч у' ч г)и ч !)~'; б) х'у' ч у~г; в) (х ч у)2 ч х(~ ч у); г) (ху ч д) и (х ч у); д) (хе' ч у) з! (ху ч у~); е) х~' ч у ч хгуч х 'ч уг) ж) (х чу'Я~~ ч !)(х'гч ~'); з) (х чу' ч Г) г(х' ч ~'); и) (х 'ч и)(уч г)чху', к) х~у' ч ги ч ух~'. 4. а) (х' ч у') (х ч ~у); б) ху' ч х'(у ч г); в) хуг.' ч у' ч х'; г) ху 'ч ч х'у' ч х'~; д) ~'(х 'ч у')х'т~у' ч ~'); е) х 'ч у ч ~'; ж) ху ч х'у'; з) (худ' ч ч (х 'чу')~чх'г,' и) 0; к) х' чу 'чх'(х'чу')(х'ч ~'). 6.
а) х'ч у ч ~; б) 0; в) (х ч 2)у', г) ху~ ч ху'~'; д) х ч у', е)х ч 6 у ч ч и); ж) х'у'~' ч у~; 3) у'(а ч !); и) (х ч 2)у; к) 1. 7. а) у ч ха', б) ~ ч ху'; в) х ч у ч ~', г) х; д) г; е) х 'ч у ч ~; ж) х ~'ч ч у; 3) !'(х ч у ч г); и) у (х ч ~); к) х (у ч г! ч ~'!') ч у~'. 8. а) (х'~' ч хе)у', б) (х ч у )~'; в)х у ч у !', г) (х у ! ч у!')д; д) (х 'ч ч ~')у'г; е) уг(х~ч х'~'); ж) х'(у ч ~); з) (х ч у)~'; и) у'г; к) (х ч у!)~'.
10. хучудч~х. 11. х(уг.чуич уоч гичгоч ио). 12. !х ч у ч т ч !)(х 'ч у' ч ~' ч !'). 13. худ ч х'у'~'!'. 14. (хчучг)(х'чу'ча'). 15. х'угио ч ху'~ио ч ху~'ио ч худи'о ч хулио'. 16. ху~'и' ч х'у'ио ч х'уи'о ч х'уио' ч худ'оч уди'о' ч х~'ио' ч ч ху'~о' ч у'ги'о ч х'у'ги ч х'у~'и. 274 17. хуч21. 18. хчуч~'. 19. ич (х'чу'ч~')(х'чу'ч и'). 21. (хуч х'у')хч (ху' чх'у)~' и (хучх'у')~' ч (ху' чх'у) я. 22.
(хуч х'у')Яч ~'г') ч (ху' ч х'у) (гг'ч ~'г). 23. (х'у'~' ч х'уя ч ху 'г, ч худ')(ин ч и'и') ч (худ ч ху'~' ч х'уг,' ч ч х'у'~)(и'и ч ии'). 24. Такая функция на любых двух соседних наборах значений аргументов принимает противоположные значения. 25. х(у'~чу~') чх'(у~чу'~'). 26. а) х', б) х; в) у'; г) х, д) не подойдет никакой; е) хили у', ж) х или у; з) х, у или ~; и) у или ~; к) любой. 1. в) Аксиома (А1); г) не аксиома; е) аксиома (А1); ж) эта формула похожа на аксиому (АЗ), но все же не порождается этой схемой. Если в схеме (АЗ) взять в качестве Г формулу -1Г, а в качестве б — -~6, то мы получим формулу (-гзб -э тзГ) -+ -+ ((.изб -+ зР) -+ ~б), которая никак не сводится к данной формуле: мы не можем здесь заменить .тзГ и -гзб на Г и 6 соответственно; з) (АЗ); и) не аксиома, хотя и похожа на (А1); к) (А2); л) не аксиома (по сравнению с (А1) скобки стоят не там); м) (АЗ); н) (А2).
2. г) (Г-+ 6) -+ (Н-+ (Г-+ 6)); д)Р- б; е) -1Г-+ -иО ж) (б -+ Г) -+ ((6 -+ -3Г) -+ (б -+ Р)); з) 6-+ (-1Р-+ Р); и) 6. 3. б) Формула (3) получена из (2) и (1) по свойству (правилу) транзитивности: из формул Г-+ б и 6-+ Н выводится формула Г-+ Н.
Это правило имеет место, но оно еще не получило своего обоснования, о чем речь будет идти далее; в) это — вывод. Формулы (1) и (2) являются аксиомами (А1) и (А2) соответственно, формула (3) получена из них по МР; г) формула (1) есть аксиома (А2). Формула (3) получена из (2), (1) по МР. Но формула (2) не является аксиомой. Следовательно, данная последовательность — не вывод. Формула (2) является теоремой (см.
Учебник, пример 15.2 или задачу 8.4, а), а значит, если в данную последовательность перед формулой (2) вписать ее вывод из аксиом, то в итоге будет получен вывод из аксиом формулы 6 -+ -+ (Г-э Р); д) это — вывод: (1) аксиома (А1); (2) аксиома (А1); (3) получена по МР из (1), (2); (4) аксиома (А2); (5) получена по МР из (3), (4); (6) аксиома (А1); (7) получена по МР из (6), (5); е) это не вывод, и комментарии здесь те же, что и в задаче 8.3, г, 275 так как формула (1) здесь представляет собой ту же теорему, что и формула (2) там; ж) последовательность формул, состоящая из единственной формулы — аксиомы„является выводом.
Это означает, что всякая аксиома теории является ее теоремой. 4. Формулы б), в), г), д), е) имеют вид 6 -+ Т, где Т— аксиома или теорема ФИВ. Их вывод выглядит так: Т, Т-» (б-+ 7) (аксиома (А1)), 6 — » 7'. При этом, если Т вЂ” теорема, то перед первой формулой этой последовательности следует выписать ее вывод. Формула в) допускает и другое доказательство: (1) Р-+ (б-+ -+ Г), (2) (Г-+ (6-+ Р)) -+ ((Г-+ 6) -+ (Г-+ Г)), (3) (Г-+ 6) -+ -+(Р-+ Г); ж), з) вывод первой формулы помещен в условии задачи 8.3, д. Вторая формула получается из первой заменой 6 на б-+ С. Такой же заменой получится и вывод второй формулы из вывода первой; н) нужно вспомнить, что Г ч 6 обозначает формулу -зР-» С.
Тогда данная формула имеет вид 6-+ (-~Р-» 6)— аксиома (А1); к) вот ее вывод: (1) -»6-+ -зб (теорема), (2) (-чб-+ — »-зб) — » ((~б -+ 6) -+ 6) (АЗ), (3) (-зб -+ 6) -+ 6 (МР: (1), (2)); л) вот ее вывод: (1) (-з Р-+-з 6) -+ ((-чГ-+ 6) -+ Г), (2) ((-»Р-+ 6) — ((~Р- 6) — Р)) — (- 6 — ((-Р— 6) — (( Г 6)— -+ Р))), (3) -чб -+ ((~Р -+~С) -+ ((-юР -+ 6)-+ Р)), (4) (-зб -+ -+ ((-юР-+ -з 6) -+ ((-зР-» 6) -+ Р)))-+ ((-ю б-+ (-»Р-+ -» 6)) -+ (~ 6-+ -э ((-зР -+ 6) -+ Р))), (5) (-юб-+ (-юР -+ -зб)) -+ (-юб -+ ((-зР -+ -+ 6) -+ Р)), (б) -юб -+ (-зР-+ -зб), (7) -зб -+ ((-юР-+ 6) -+ Г).
5. Формулы В, и Вз любого вывода из гипотез могут быть как аксиомами, так и гипотезами. Если же Г = О, т.е. имеется вывод из аксиом, то эти формулы могут быть лишь аксиомами. (Для получения формулы по правилу МР нужно среди предыдущих иметь по меньшей мере две формулы. Так что ни В„ни тем более В, не могут быть получены по правилу МР из двух предыдущих формул.) б. Свойства а) и б) выражают тот очевидный факт, что каждая формула выводима из самой себя: выводом служит последовательность, состоящая лишь из самой этой формулы. Для доказательства свойства в) нужно выписать друг за другом сначала последовательности, являющиеся выводами формулы 6, из гипотез Уь ..., Р„, затем — 6» из тех же гипотез и т.д., наконец — 6» из тех же гипотез, а после них — последовательность, являющуюся выводом формулы Н из гипотез 6„С„..., 6».
Поскольку для каждой из формул 6; в последовательности имеется ее вывод из гипотез Р„..., Р„, то вся полученная последовательность формул удовлетворяет определению вывода формулы Н из гипотез Г„ ..., Г„. 7. Эта задача служит в некотором роде подготовкой к теореме о дедукции.
В ней сформулированы достаточно очевидные свойства понятия выводимости: каждое последующее утверждение является некоторым обобщением предыдущего. Теорема о дедукции 276 будет утверждать, что верны утверждения, обратные к каждому утверждению настоящей задачи. И эти утверждения будут уже весьма не очевидными.
а) Если имеется вывод формулы Г-+ 6 из аксиом: В„..., В, „ Г -+ б, то выводом С из Г будет служить последовательность: Вп ..., В, ь Г-э б, Г, 6, где à — гипотеза, а б получена из двух предыдущих формул последовательности по правилу МР. Аналогично доказывается второе утверждение, а третье вытекает из т-кратного применения второго утверждения. 8. б) См. ответ к задаче 8.1, ж; в) вывод: 6 ~- Г-+ б; г) вывод формулы (5) из (2), (4); д) аксиомой здесь является лишь формула (7), которая есть не что иное как (А3).
Формулы (4), (6), (8), (9) получены по правилу МР из предыдущих. Следовательно, данная последовательность есть вывод формулы (9) из гипотез (1), (2), (3), (5). Формулы (3) и (5) из числа гипотез исключить нельзя; е) вывод (7) из (1), (5); ж) вывод (5) из (4); з) аксиомами здесь являются формулы (2) и (4). Формула (3) получена по правилу МР из (1), (2). Формулы (1), (5) придется считать гипотезами, и данная последовательность формул, по существу, оказывается выводом формулы (5) из самой себя. 9.а) Г,Г-+6,6; г) б, б -+ (Г-+ С), Г -+ б, (Г -+ 6) -+ (Н-э (Г -+ 6)), Н -+ — (Г- '6); д) см.
задачу 8.8, а; е) Г, Г -+ б, б -+ Н, б, Н; ж) à — ~ 6, Г ~ (6 ~ Н), Г, 6, 6 ~ Н, Н; з) Г -+ 6, Г -+ (б -э Н), (Г-+ (6 -+ Н)) -+ ((Г -+ 6) -+ (Г -+ -+ Н)), (Г-+ 6) -э (à — > Н), Г-+ Н; к) полезно отметить, что в ФИВ (как и в содержательных математических теориях) одно и то же утверждение может иметь различные доказательства. Примером может служить настоящая задача. Вот одно из доказательств этого утверждения: (1) Г, (2) б, (3) Г-+ (б -+ Н), (4) (Г -+ (6 -+ Н)) -+ ((Г -+ 6) -+ (Г -+ Н)), (5) (Г-+ 6) -+ (Г-+ Н), (6) С -+ (Г-+ С), (7) Г-+ 6, (8) Г-+ Н, (9) Н В этом доказательстве использованы аксиомы (А1) (формула (б)) и (А2) (формула (4)).
Вот значительно более короткий вывод (к тому же вовсе не использующий аксиом, а использующий лишь правило вывода МР): Г, 6, Г-+ (б-+ Н), б — > Н, Н; м) это важное свойство о перестановке посылок (Ги 6) можно доказать следующим образом: (1) Г-+ (6-+ Н), (2) (Г-+ (6-+ -+ Н)) -+ ((Г-+ 6) -+ (Г-э Н)), (3) (Г-+ 6) -+ (Г-+ Н), (4) ((Г-+ -+ 6) -+ (Г -+ Н)) -+ ((6 -+ (Г -+ 6) -+ (Г -+ Н))), (5) 6 -+ -+ ((Г -+ 6) -+ (Г -+ Н)), (6) (б -+ ((Г -+ С) -+ (Г -+ Н))) -+ -+ ((6-» (à — э 6)) -+ (6 -+ (Г-+ Н)), (7) (6 -э (Г-+ 6)) -+ (6-+ -+ (Г -+ Н)), (8) 6 -+ (Г -+ 6), (9) 6 -+ (Г -+ Н). 277 После этого нетрудно построить вывод, подтверждающий, что Р -э (О -+ Н), О ~- Р -+ Н (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
