В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 58
Текст из файла (страница 58)
При «фильтровании» вывода лишними оказываются формулы С,— Сн С7 — Сп (см. задачу 8.4, л); е) построения этой задачи получаются из построений задачи 8.11, г), если вспомнить, что Г~ б есть ~Г-+ б, и заменить в этих построениях Гна -зГ; ж) в задаче 8.9, и имеется вывод 6 из ~ 6 » -чГ, Г: (В,): -~6-» + ~Г (Вз) Г (Вз)' ( ~6 + чГ) + (( ~6 + Г) + 6) (В4)' ( чб + -+ Г) -+ 6, (В5): Г -+ (-чб -+ Г), (В«): -чб -+ У; (Вр): 6. Строим последовательность: Г-+ В„..., Г-+ В, и дополняем ее до вывода формулы Г-+ 6 из гипотезы -~6-+ -~Г: (С,): -зб -+ -чГ; 282 (С2): ( 16 -+ ~г) -+ (г -+ (~6 -+ ~г))' (С3) ° Г + (Чб + Р) (С.): (Р-+ ((Р-+ Р) -+ Р)) -+ ((Р-+ (Г-+ Р)) -+ (Р-+ Р)); (с): г- ((г г) — г); (С«): (Г-+ (Г-+ Г)) -+ (Р-+ Р); (С7): г- (г- г); (Св): Р-+ Г; (~): (~б -+ ~г) -+ ((-16 -+ Р) -+ 6); (См): ( ~6-» ~Г) -+ ((16-+ Р) -+ 6) -+ (Г-+ (( 'б-+ 'Г)-+ -+ ((-16 -+ Р) -+ 6))); (Сп): Р -+ ((~6 -+ -1Р) -+ ((-16 -+ Р) -+ 6)); ( Сп) ° (Г (( 6 Р) (( 6 Г) 6))) ((Г ( б -+ -1Р)) -+ (Р-+ ((~6 -+ Р) -+ 6))); (С„): (Р-+(-6-+-Р)) -+(Г-+(( 6-+ Г) -+ 6)); (См): Г-+ ((-16 -+ Р) -+ 6); (с„): г- ( б- г); (См): (Г-+ ( 16 -+ Р)) -+ (Г-+ (Г-+ ( 6 -+ Р)))," (с): г (г ( б г))' (с„): (г-+ (г-+ (-~6-+ г))) -+ ((г-+ г) -+ (г-+ (~6-+ г))); (с ): (г- г) - (г-+ (- б г)); (Сто): Р-+ (16-+ Р)' (Сн) (Р (( 6 Г) 6)) Иг ( б Г)) (Г 6)) (Сп): (Р-+ ("16 -+ Г)) -+ (Р-+ 6); (См): Г-+ б.
После «фильтрации» остаются формулы Сп Сп См С« — Си, Сп — Сп (см. задачу 8.9, ч); з) мы имеем два вывода формулы (б-+ -1Р) — » (6-» Р) из Р: в 7 шагов и в 5 шагов (см. задачу 8.9, и). Примените алгоритм теоремы о дедукции к каждому из них и из построенных выводов «отфильтруйте» наикратчайший; и — р) первоначальные выводы для применения алгоритма теоремы о дедукции вы найдете в задаче 8.9. 12. Предположим, что теорема о дедукции выполняется в том или ином исчислении высказываний.
Тогда, применив ее дважды к очевидной выводимости Г, 6 ь- Р, получим сначала Г»- 6 -» — » Р, а затем ~- Р -+ (6 -+ Р). Далее нетрудно проверить, что выводимость à — > (б -+ Н), Р-+ б, Р ~ — Н (см. задачу 8.9, ж) выполняется вне зависимости от состава аксиом исчисления высказываний, а лишь при наличии в нем правила вывода МР. Применим к этой выводимости трижды теорему о дедукции. Получим сначала Г-+ (б -+ Н), Г-+ 6, >- Р-+ Н, затем Р-» (6 -+ Н) ~- ~ — (Р-+ 6) -+ (Р-+ Н) и наконец ь- (Г-+ (б -+ Н)) -+ ((Р-+ -+ 6) -+ (Г-+ Н)). Обратно, если в составе аксиом исчисления высказываний есть данные формулы, или они на каком-то этапе развития исчисления появились как его теоремы, то, проанализировав доказатель- 283 ство теоремы о дедукции (Учебник, теорема 15.4), мы увидим, что в его ходе (кроме правила МР) использованы лишь эти формулы.
13. Данная задача является продолжением необходимости предыдущей задачи. Укажем те выводимости, применение к которым (может быть, неоднократное) теоремы о дедукции приводит к обоснованию выводимости данных формул из аксиом: б)Г,С~-6; в) 6,Г -Г; г) Г-~ 6, 6-+ Н, Г ~- Н; д) Г-+ 6, Н-+ Г, Н ~ — 6; е) (Г-+ 6) -+ Г, Г-+ 6 ~- 6; ж) Г-+ (Г-+ 6), Г ~- 6; з) Г-+ (6 — ~ Н), 6, Г >- Н; и) 6-+ Н, 6, Г ~- Н. 14. Мы наконец подошли к тому месту, когда начнем пожинать плоды тех усилий, которые затратили на освоение теоремы о дедукции. Уяснив, как работает ее алгоритм по созданию выводов (доказательств), мы больше не будем пускать его в ход, а будем лишь держать в уме эту возможность, осознавая, что ее реализацию можем осуществить в любой момент.
а) Здесь необходимо обратить внимание на два момента. Вопервых, при применении второй раз теоремы о дедукции, т.е. при применении ее к выводимости -зГ ~- à — э 6, не забудьте заключить в скобки формулу Г-+ 6, чтобы у вас в итоге не получилась не формула ~Г -+ Г -+ 6 или не теорема (-зГ -+ Г) -+ 6. Вовторых, выводимость -~Г, Г >- 6 можно толковать и как Г, -~Г ~- ~- С. Двукратное применение теоремы о дедукции к этой выводи- мости приводит сначала к выводимости Г >-.зГ -+ 6, а затем к теореме >- à — ~ (~à — > 6); б) в задаче 8.9, л доказана выводимость ~6 — ~ -зГ, Г >- 6, применив к которой дважды теорему о дедукции, получим требуемую теорему. Данную теорему можно получить и однократным применением теоремы о дедукции к выводимости ~ 6-+ зГ>- Г-+ -+ 6, установленной в задаче 8.9, ч; в) взгляд на выводимость в задаче 8.9, и как на Г, з 6 -+ -зГ ~- 6 и двукратное применение к ней теоремы о дедукции приводит к данной теореме; г) двукратное применение теоремы о дедукции к выводимости Г, -~Г ~- С, полученной в задаче 8.9„р, приводит к теореме ~ — Г-+ -+ (-~Г-+ 6), в которой -з Г-+ 6 и есть Г ч 6.
Отметим здесь, что теорема ~-6-+ (Г ~ 6) есть просто аксиома (А1): 6-+ (зГ-+ 6); д) обратная импликация для предыдущей верна только при 6— = Ги вытекает по теореме о дедукции из выводимости Гч Г~- Г, установленной в задаче 8.10, е; е) см. задачу 8.9, х. 284 15. б) См. Учебник, теорема 15.8, е; в) см. Учебник, теорема 15.8, ж; г) покажем, что Р-+ 6, Г-+ ~6 >- ~Г: (1) Г-+ 6, (2) Г-+ -~6, (3) (Г -+ 6) -+ (~б -+ ~Г), (4) -зб -+ -~Г, (5) (Г -+ ~6) -+ -+ (~~6-+ ~Г), (6) -лб -+ -чГ, (7) (-зб -+ -чГ) — э ((-гзб-+ -зГ) -+ -+ -зГ), (8) (-з-чб -+ -зГ) -+ -зГ, (9) ~Г.
Остается к полученной выводимости дважды применить теорему о дедукции; д) выводимость из задачи 8.9, ш позволяет получить эту теорему в результате однократного применения теоремы о дедукции к этой выводимости, а выводимость из задачи 8.9, щ — в результате двукратного. 16. Укажем выводимости, из которых по теореме о дедукции следует данная выводимость: б) 8.10, е; в) 8.9, р; г) б, -~Г >- 6 (задача 8.6); д) 8.9, л; е) 8.9, и. 17. Приведем обоснования данных выводимостей. б) (1) Р -+ б, (2) -лГ -+ Г, (3) ~чГ -+ 6, (4) 6 -+ тамб, (5) -т зГ -+ -губ, (6) -зб -+ -~Г; в) (1) Г-+ 6, (2) ~Г-+ б, (3) (Г-+ С) -+ (-зб -+ -зГ), (4) -зб-э -+-зГ, (5) (-чГ-+ 6) -+ (-зб -+ ттГ), (6) -зб -+ -з-иГ; (7) (~С -+ -+-пГ) -+ ((-юб -+ -юГ) -+ 6), (8) (~6 -+ -чГ) -+ 6, (9) 6; г) (1) Г -+ С, (2) Г -+ -зб, (3) -з 6 -+ -зГ, (4) -з-чГ -+ -гз 6, (5) (ттГ-+ -ч-зб) -+ ((-пГ-+ ~6) -+ ~Г), (6) (~~Г -+ ~6) -+ -+-зГ, (7) -т зГ -+ Г, (8) -з-юГ -+ -юб, (9) -чГ; е), ж) вытекают из предыдущих задач а) и д) соответственно ввиду определения логической связки ++: Г++ 6 есть (Г-+ 6) л л(б-+ Г); з) (1) Г -+ 6(Гч 6), (2) Г-+ Н, (3) 6 -+ Н, (4) (Г -+ Н) -+ -+ (-ъН вЂ” э чГ), (5) -ъН вЂ” ь -чГ, (6) (6-+ Н) -+ (~Н вЂ” ь ~ 6), (7) ~Н-+ -+ ~6, (8) зН-ь 6, (9) (-зН-+ -з 6) -+ ((-зН вЂ” э 6) -+ Н), (10) (~Н вЂ” э -+ 6) -+ Н, (11) Н.
18. а) Пусть Г, б ~- Н. По задаче 8.17, а имеем Г л 6 ~- Г, а по задаче 8.9, х — Г л 6 ~- 6. Тогда по задаче 8.6, а Г л 6 ~- Н. Наконец, отсюда по теореме о дедукции следует, что ~ — (Гл 6) — ~ -+ Н. Обратно, пусть выполняется последняя теорема. Тогда по задаче 8.7, а Гл 6 ~- Н. Кроме того, по задаче 8.17, д Г, 6 ~- Гл 6. Наконец, из двух последних выводимостей по задаче 8.6, в заключаем, что Г, 6 ~- Н.
19. а) Это есть теорема о дедукции; б) в задаче 8.17, д доказано, что Г, 6 ~- Гл 6. Поскольку, кроме того (по условию), Г ~- ~- Г и Г ~- 6, то по задаче 8.6, в имеем Г ~ — Г л 6; г) из условия по теореме о дедукции заключаем, что Г ~- Г-+ б и Г ~- à — ~ -ч С. Остается доказать, что Г-+ 6, Г-+ ~ б ~- ~Г (это сделано в задаче 8.17, г), и применить утверждение задачи 8.6, в.
20. а) Следует на основании угаерждения задачи 8.6, в ввиду того, что в силу правила МР справедлива выводимость Г, Г -+ 285 -+ 6 «- 6; б) по условию, Г «- Г л б. В силу задачи 8.17, а Г л л б «- Г. Тогда (задача 8.о, в) Г «- Г. Аналогично, но с использованием задачи 8.9, х, где доказано, что Г л 6 «- б, проверяется второе правило удаления конъюнкции; в) имеем: Г л 6 «- Г (задача 8.17, а), Г л 6 «- б (задача 8.9, х). Тогда Г, Г л 6 «- Г и Г, Г л 6 «- 6. В силу условия Г, Р, 6 « — Н оба последних вывода вместе можно продолжить до вывода формулы Н, т.е.
мы будем иметь: Г, Р л 6 «- Н; д) из условия по теореме о дедукции следует, что Г « — Р-+ Ни Г «- С -«Н. Получив формулы Г-+ Ни 6-+ -+ Ни добавив к ним формулу Гч 6, мы можем получить выводи- мост«к Г ч 6, Р -+ Н, 6 -+ Н «- Н (это доказано в задаче 8.17, з). В итоге получаем, что Г, Г~ б « — Н; е) следует из задач 8.9, р и 8.6, в; ж) следует из задач 8.10, б и 8.6, в. 21. б) (1) -~б, Н, 6 л Н «- -«б, (2) «б, Н, б л Н « — 6, (3) ~6, Н «- -~(6 л Н); в) (1) 6, -~Н, 6 л Н «- .зН, (2) 6, «Н, 6 л Н «- Н, (3) б, -«Н«- -~(6 л Н); д), е) очевидно следуют из правила введения дизъюнкции (задача 9.19, в); ж) (1) ~6, -«Н, С « — Н, (2) -чб, -«Н «- 6 -+ Н; з) (1) ~6, Н, 6 «- Н, (2) ~6, Н «- 6-+ Н; к) (1) б, Н, 6 «- Н, (2) б, Н «- 6 -+ Н; л) (1) «б, -~Н «- 6 -+ Н, (2) -зН, « 6 «- Н -« 6, (3) -чб, ~Н «- « — (б -+ Н) л (Н-+ С).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
