В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 57
Текст из файла (страница 57)
задачу 8.9, л); н) см. задачу 8.8, г; о) -з 6, -и 6 -+ (-~Р -+ -з 6), -зР -+ -з О, (-зР -+ -~ С) -+ ((-зР -+ -+ 6) -+ Г), (~Р-+ С) -+ Р. Последняя формула в силу определения связки ~ может быть записана так: (Р~ 6) -+ Р; п) ~6-+ -~Р, Р, (-зО-+ -~Р) -+ ((-~6 -+ Г) -+ 6), (-зО -+ Р) -~ О Р- ( О- Р) ~6- Р О; р) Р, -~Р, Г -+ (-зО -+ Р), -~6 -+ Г, ~Р-+ (-зО -+ ->Р), -зО -+ -+ ~Р, (~6 -+ -зР) -+ ((~6 -+ Р) -+ 6), (-зО-+ Р) -+ О, О; с) ~6 -+ Г, -~6 -+ -~Р, (~6 -+ чР) -+ ((-ч О-+ Р) -+ 6), О; т) эта выводимость также допускает два доказательства. Первое опирается на аксиомы (А1) и (А2): (1) Г, (2) Р-+ (-зР -+ Р), (3) -зР-+ Г, (4) (-зР-+ Р) -+ (6-+ (~Р-+ Р)), (5) 6 -+ (-зР-+ Р), (6) (О -+ (-зР -+ Р)) -+ ((6 -+ -зР) -+ (О -+ Р)), (7) (О -+ -+ ~ Г) -+ (О -+ Р). Второе опирается только на аксиому (А1): (1) Г, (2) Г-+ (О-+ Р), (3) 6-+ Р, (4) (6-+ Р) -+ ((6-+-зР) -+ (6-+ Р)), (5) (О -+ -ФР) -+ (О -+ Р); у) второе доказательство предыдущего утверждения и доказательство настоящего по сути являются калькой с доказательства утверждения г) настоящей задачи; ф) С, О-+ (-~Р-+ 6), -зР-+ 6 (Рч 6); х) приводим вывод, напоминая, что -~(Р— ~ ~6) есть Р а О: (1) -ч(Р-+ -зО), (2) -з(Р-+ -~6) -+ (-~6-+ -з(Р-+ -зО)), (3) -зО-+ -+-з(Р-+ -зО), (4) (-зО-+ -ч(Р-+ ~6)) -+ ((~6-+ (Г-+ ~6)) -+ 6), (5) (-зО -+ (Г-+ -зС)) -+ 6, (б) -зО -+ (Р -+ -зО), (7) 6; ц) эта выводимость представляет собой предыдущую, если вспомнить, что Р++ О означает (Р -+ 6) л (6 -+ Р); ч) если вам все же не удалось построить вывод, то обратитесь к помощи теоремы о дедукции (см.
задачу 8.11, ж); ш) приводим вывод: ~Р, -~Р-+ (-~6-+ -чР), -чО -+ -зР, (-~6-+ -+ -зР) -+ ((-~6 -+ Р) -+ 6), (-зО -+ Р) -+ 6; щ) необходимый здесь вывод получается из вывода предыдущей задачи добавлением двух формул: -зО -+ Г (гипотеза) и О (получена из двух последних формул по правилу МР). 10. В предыдущей задаче мы установили ряд важных выводимостей (свойств выводимости), которые можем использовать для установления новых выводимостей. До настоящего момента все доказательства (как из аксиом, так и из гипотез) мы выписывали в полном виде. Используя полученные выводимости, начнем постепенно отходить от этого правила. Теперь мы будем выписывать не доказательства (выводы) как таковые, а определенные обоснования возможности написания таких доказательств. Настоящая серия задач — первый шаг на этом пути. 278 а) Студентам полезно будет выписать полное доказательство этой теоремы, с тем чтобы до конца уяснить построенные ранее выводы; б) ясно, что, дополнив приведенный в предыдущей задаче вывод формулами ~~Г(гипотеза) и Г(получена из -гзГи ~-~Г-+ -+ Гпо правилу МР), мы получим вывод Г из тзГ; в) приведем обоснование возможности построения доказательства этой формулы: (1) (-тпГ-+ зР) -+ ((-ттзГ-+ Р) -+ тзР) (аксиома (АЗ)), (2) -ттзГ-+ -зГ(задача 8.10, а), (3) (-гтчГ-+ Г) -+ -+ ~-зГ(МР: (2),(1)), (4) Г-+ (.тз~Г-+ Г) (аксиома (А1)), (5) Г-+ -+-з~Г(задача 8.9, и); г) предыдущий вывод нужно дополнить формулами Р, -г~Г, д) чГ -э (~6 -+ -зГ), (-з6 -э -зГ) -э ((-~6 -+ Г) -+ 6), ~Г -+ -э ((.з 6-+ Р) -+ 6).
Последняя формула может быть выведена из двух предыдущих (аксиомы (А1) и (АЗ) соответственно) в силу свойства транзитивности (задача 8.9, и); е) -зГ-+ -чГ(это — теорема на основании задачи 8.4, а), (-~Г-+ -+ зГ) -э ((-зГ -+ Р) -+ Г), (-зГ -+ Р) -+ Р, -~Г -+ Г, Г„ ж) на основании выводимости 9.9, в, приняв за Гформулу à — ~ -э (6 -+ Н), за 6 формулу Г-+ 6, за Н формулу Г-+ Н, можем записать: (Г-+ (6-+ Н)) -+ ((Г-+ 6) -+ (Г-+ Н)) ~- (Г-+ 6) -+ -+ ((Г-+ (6-+ Н)) -+ (Г-+ Н)).
Формула, стоящая в левой части выводимости, есть аксиома (А2). Поэтому формула, стоящая в правой части, выводима из аксиом, т.е. является теоремой. 11. Теорема о дедукции утверждает, что если Г„..., Г„о Г„~- ~- 6, то Рн ..., Г„, ~- Г„-+ 6, т.е. если имеется вывод формулы 6 из гипотез Рн ..., Г„„Р„, то может быть построен и вывод формулы Г„-+ 6 из меньшего числа гипотез Г„..., Р„,. Доказательство этой теоремы, приведенное в Учебнике (теорема 15.4), как раз и состоит в изложении четкого алгоритма по построению вывода формулы Г -+ 6 из гипотез Рн ..., Г„, на основании имеющегося вывода формулы 6 из гипотез Гн ..., Р„„Г„.
Для уяснения механизма действия этого алгоритма и предназначена настоящая серия задач. В них предлагается провести не абстрактное по индукции рассуждение для произвольных формул, как в теореме Учебника, а рассуждение для конкретных формул с конкретным количеством шагов. а) Сравнение полученного по теореме о дедукции вывода С,— Сп с выводом (1) — (7), предлагаемым в задаче 8.9„л, показывает, прежде всего, что первый вывод получился значительно более длинным, нежели второй.
Это говорит о том, что алгоритм теоремы о дедукции не направлен на поиск оптимального (наикратчайшего) вывода, а обеспечивает лишь неотвратимость нахождения хотя бы одного требуемого вывода. Ведь кратчайший вывод (1) — (7) в задаче 8.9, л вы могли бы и не найти, действуя методом творческого поиска. Вывод же С,— Сп вы построите не- 279 пременно, если уясните механизм действия алгоритма. Далее, анализируя полученный вывод С, — Сгь вы видите, что он содержит формулы, которые без ущерба могут быть опущены. Так, формулы С» и С~«абсолютно одинаковы и последовательность формул С9 — С,« направлена Фактически на вывод формулы С,« из самой себя. При этом, только для этой цели привлекается формула С~. Р-+ Р, вывод которой составляет последовательность С« — См Таким образом, опустив формулы С« — См См — С,4, мы получим последовательность формул С„См Сь С9, Сн, См, Сп, также представляющую собой вывод формулы Р -+ Н из гипотез Р-+ (6-+ Н), 6.
Сравнив этот вывод с выводом (1) — (7), предложенным в задаче 8.9, л, мы видим, что он совпадает с ним с точностью до порядка входящих в него формул. Эти «недостатки» алгоритма, приведенного в теореме о дедукции, нисколько не умаляют его значения, которое состоит в его универсальной применимости и в неизбежности прихода к результату. И еще один момент, связанный с алгоритмом в теореме о дедукции, необходимо уяснить.
Этот алгоритм применяется исключительно и только к выводам, доказательствам, а не к псевдовыводам, т.е. к последовательностям формул, поясняющим возможность построения вывода. Каждая формула этой последовательности может быть либо аксиомой, либо гипотезой (либо остающейся в списке гипотез, либо перебрасываемой направо), она может быть либо получена из двух предыдущих формул последовательности по правилу МР (и не может быть получена по какому-либо другому правилу, например по правилу транзитивности и т.п.); б) в задаче 8.9, е построен вывод формулы Низ гипотез: (В,): Р -+ 6, (В2): 6 -+ Н, (Вз): Р1 (В«): 6, (В~): Н. Строим последовательность Р-+ Вп Р-» В„Р-+ В„Р-+ В«, Р-+ В,. По алгоритму теоремы о дедукции дополняем ее до вывода формулы Р-+ Низ гипотез Р-+ 6, 6-+ Н: (С,): Р-+ 6; (С2): (Р-+ 6) -+ (Р-+ (Р-+ 6)); (Сз) Р + (Р + 6) (с«): 6- и; (с5): (6 - Н) — (Р - (6 - Нв (С«): Р-» (6 -+ Н); (С,): Р-+ ((Р-+ Р) -+ Р); (С,).
:(Р- ((Р Р)-+Р))- «Р (Р- Г»- (Р- РВ (С9): (Р-+ (Р + Р)) -+ (Р-+ Р)' (С!0) Р + (Р + Р) (Сп):Р-+ Р; (с!2):(Р-+ (Р-+ 6)) -+ ИР-+ Р) -+ (Р-+ 6)); (сц) (Р + Р) + (Р + 6)1 (с«):Р- 6; 280 (Сн): (Г-+ (6 -+ Н)) -+ ((Г-+ 6) — > (Г-+ Н)); (См):(Г-+ 6) -+ (Г-+ Н); (Сп):Г-+ Н. Для получения требуемого вывода из этой последовательности достаточно ограничиться формулами Сп С4, См Сб, Сн, См, Сп. Этот вывод не отличается от вывода, приведенного в задаче 8.9, и; в) нетрудно построить вывод формулы 6 из гипотез à — э (à — ~ -+ 6), Г: (В,): Р-+ (Г-+ 6), (Вз): Р; (Вз): Г-+ 6, (В4): 6.
Строим последовательность Г-+ В„Г-+ Вп Г-+ В„Г-+ В4 и по алгоритму теоремы о дедукции дополняем ее до вывода формулы Г-+ 6 из гипотезы Г-+ (Г-+ 6): (С~): Г-+ (Г-+ 6); (Сз): (Г-+ (Г-+ 6)) -+ (Г-+ (Р-+ (Г-+ 6))); (Сз) Г + (Р + (Г + 6))1 (С4): (Г-+ ((Г-+Р) -+ Р)) -+ ((Г-+ (Г -+ Р)) -+ (Г -+ Р)); (С5): Г-+ ((Г-+ Р) -+ Р); (С,): (Г- (Р- Г)) - (Г- Г); (С7): Г- (Г- Р); (Св): Г-э Г; (С~): (Г-+ (Г-+ (Г-+ 6))) -+ ((Р-+ Г) -+ (Г-+ (Г-+ 6))); (С!0) ° (Г + Г) + (Г ~ (Г ~ 6)) (Сп): à — «(Р-+ 6); (Сп): (Р-+ (Г-+ 6)) -+ ((Р-+ Р) -+ (Г-+ 6))1 (С!3)' (Р + Г) + (Р + 6)* (См): Г-+ 6 При сокращении этого вывода не удается опустить формулы С, — С„дающие вывод Г-+ Г из аксиом, поскольку последняя формула используется ниже.
«Отфильтрованный» вывод: Сп С4, Сп Са, Сп См Сп, Со, С„, который мы имели в задаче 8.9, и. г) В задаче 8.9, г имеется вывод Н-+ (Г-+ 6) из 6: (В,): 6, (Вз) 6 + (Р + 6) (Вз)' Р + бъ (В4)' (Р + 6) + (Н + (Р + 6))~ (В,): Н вЂ” ь (Г-э 6). Строим последовательность 6 -+ В„О -+ В„О -+ В„О -+ В4, 6-+ В5 и дополняем ее до вывода из аксиом: (С,):(6 -+ ((6 -+ 6) -+ 6)) -+ ((6 -+ (6 -+ 6)) -+ (6 -+ 6)); (С~): 6 -+ ((6 -+ 6) -э 6); (Сз):(6 -+ (6 -+ 6)) -+ (6 -+ 6); (С4) 6 + (6 + 6) (С~):6 -+ 6; (Са):(6-+ (Г-+ 6)) -+ (6-+ (6-+ (Г-+ 6))); (С7):6-+ (Р-+ 6); (Сз): 6 -+ (6 -+ (Г -+ 6)); (С9) (6 (6 (Г 6))) ((6 6) (6 (Г 6))) (См): (6-+ 6) -+ (6-+ (Г-+ 6)); (Сп): 6-+ (Р-+ 6); (Сп): (Г-+ 6) -+ (Н-+ (Р-+ 6)); 281 (С~з): ((Г -+ 6) -+ (Н -+ (Г -+ 6))) -+ (6 -+ ((Г -+ 6) -+ (Н -+ -+ (Г-+ 6)))); (См) 6 + ((Г + 6) + (Н + (Г + 6))) (См): (б -+ ((Р-+ 6) -+ (Н вЂ” » (Г-+ 6)))) -+ ((б -+ (Г-+ 6)) -+ -+ (6-+ (Н-+ (Г-+ 6)))); (См): (б-+ (Г-+ 6)) -+ (6-+ (Н-» (Г-+ 6))); (Сп): 6 -+ (Н -+ (Г -+ 6)).
При «фильтровании» вывода лишними оказываются формулы С,— См С,— Сц (см. задачу 8.4, ж); д) в задаче 8.9, о имеется вывод (Гм 6) — » Гиз ~б: (В,): -~б, (Вг): ~6-+ (-зГ-» -зб)) (Вз): -~Г-» -~б (В4): (-~Г-» -~6) -+ И-~Г-+ -+ 6) -аГ), (В5): (-~Г -+ 6) -+ Г Строим последовательность -зб -» Во -зб -+ Вь ~6 -+ Вь ~6 -+ В4, -зб -+ В, и дополняем ее до вывода из аксиом: (С~): (~б -» ((-~б -+ -~6) -+ -~б)) -+ ((-~6-+ (~6-+ -~б)) -+ -+ (-з б -+ -зб)); (Сз) ~6 + (( $6 + ъб) + ъб) (Сз): (-зб -+ (~6 -+ -зб)) -+ (-зб -+ -зб); (С4). зб + ( зб + чб) (С5): -~6 -+ -~6; (С«): -~6-+ (~Г-» -зб); (С7): (-~6-+ (-~Г-» -зб)) -+ (-зб-» (~6-» (~Г-+ ~б))); (С8) ~6 + (~6 + (~Г + ~6))1 (Сд): (-зб -+ (-зб -» (-~Г-+ -~6))) -+ ((-~6-» -~6) -+ (-~6 -+ — > (-чГ-+ -ч 6))); (С$0) ° (з б 6) (з б ( Г 6)) (Сп): ~6-+ (~Г-+ ~6); (Сп): (-зГ-» -чб) -+ ((~Г-+ 6) -+ Г); (Сц): ((-зГ -+ -зб) -+ ((-зГ -+ 6) -+ Р)) -+ (-зб -+ ((-зГ -+ -+ -~б) -+ ((-зГ-» 6) -+ Р))); (См) зб + ((( зГ + ~6) + (( зГ + 6) + Г)) (См): (-зб -+ ((-~Г -+ -~6) -+ ((~Г -+ 6) -+ Г))) -+ ((-зб -+ -+ (~Г -+ -зб)) -+ (~6 -+ ((~Г-» 6) -+ Г))); (См): (-~6 -+ (-~Г-» -~6)) -+ (-~б -+ ((-~Г-» 6) -+ Г)); (бп): ~б -+ (( ~Г -+ 6) -+ Г).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
