В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 30
Текст из файла (страница 30)
х) Вспомним, что Г л С есть -~(Г-+ -16). Обоснуйте каждый шаг следующего вывода: (1) -1(Г-+ -зб); (2) ~(Г -+ -1 6) -+ (~Г-+ ~(Г -+ ~б)); (3) -$Г-+ -1(Г-+ -$6); (4) (~Г-+ -з(Г-+ ~6)) -+ ((~Г-+ (Г-+ -зб)) -+ Г); (5) (-зГ-+ (Г-+ -16)) -+Г; (6) -1Г-+ (Г-+ -16); (7) Г. 8.10. Докажите, что имеют место следующие выводимости и теоремы, обосновав возможность построения соответствующих выводов из гипотез: а) >- тчГ-+ Г; б) -тзГ~- Г; в) >- Г-+ ~-зГ; г) Г~- -г~Г; д) >- -~Г-+ ((-16-+ Г) -+ 6); е) Г~~ Г ~- Г; ж) (Г-+ 6) -+ ((Г-+ (6 -+ Н)) -+ (Г-+ Н)).
Р е ш е н и е. а) Рассмотрим следующую последовательность формул: (1) (-зГ-+ ~-зГ) -+ ((-1Г-+ -1Г) -+ Г); (2) ~Г-+ ~Г; (3) (-~Г-+ -э~Г) -+ Г; (4) ~~Р -+ (»Г-+ -»-»Г); (5) »-»Р-» Г. Формула (1) есть аксиома (АЗ). Формула (2) есть доказанная ранее теорема (задача 8.4, а). Ее вывод здесь не приведен, но мы можем его вставить в данную последовательность.
Формула (3) может быть выведена из формул (1) и (2) в силу утверждения задачи 8.9, л, и этот вывод мы также могли бы вписать сюда. Формула (4) есть аксиома (А1). Наконец формула (5) может быть выведена из формул (4) и (3) на основании задачи 8.9, и, и этот вывод мы могли бы также вписать сюда. Итак, хотя мы и не выписали в полном объеме доказательство данной теоремы, у нас не осталось никаких принципиальных трудностей к тому, чтобы это сделать.
Теорема о дедукции н ее применение. Решить задачи 8.11 — 8.18. 8.11. Проделайте доказательство теоремы о дедукции в следующей частной формулировке: а) если Г-+(6-+ Н), 6, Р» — Н, то Г-+ (6-+ Н), 6»- Р-+ Н; б) если Р-+ 6, 6-+ Н, Р»- Н, то Р-+ С, 6 — » Н» — Р-+ Н; в) если Г-» (Г-+ 6), Г»- С, то Г-+ (Г-+ 6)»- Р-» 6; г) если 6»- Н-+ (Р— » 6), то»- 6 -+ (Н-+ (Р-+ 6)); д) если »6»- (Р ~ 6) -+ Г, то»- -»6-+ ЦР ч 6) -+ Р); е) если Р» — Н-+ (»6-» У), то» вЂ” Г-+ (Н-» (»6-» Р)); ж) если »6-+ -»Р, Г»- 6, то »6 -+ ~Г»- Г-+ 6; з) если Г»- (6 -+ -»Р) -+ (6 -+ Р), то»- Г -+ ((6 -+ »Р) -+ -+ (6-+ Г)); и) если Г, 6, Г-+ (6-+ Н)»- Н, то Г, 6»- (Г-+ (6 -+ Н)) -+ Н; к) если Р -+ (6 -+ Н), 6» — à — » Н, то Г-+ (6 -+ Н)» — 6 -+ -+ (Г-+ Н); л) если Г-+ 6, Р-» (6-» Н), Р»- Н, то Р-+ 6, Р-+ (6 -+ -+ Н)»- Р-+ Н; м) если ~6 ~ Г, »6 — » -»Г»- 6, то » 6 -» Г»- (»6-» -»Р) — » -+ 6; н) если Г, -чР»- 6, то Г»- -~Г-» 6; о) если ~Г, Г»- 6, то -»Р»- Г -+ 6. Р е ш е н и е.
а) В задаче 8.9, к требовалось построить вывод формулы Низ гипотез Г-+ (6-+ Н), 6, Г. Воспроизведем этот вывод: В,: 6 (гипотеза); В,: Г(гипотеза); Вз. .Г -+ (6 -+ Н) (гипотеза); В4' 6 + Н (МР Вз Вз) В» Н (МР. В» В4)' (*) Обращаясь к доказательству теоремы о дедукции, мы можем построить вывод Г-+ Н из Г-+ (6-+ Н), 6.
Для этого построим сначала последовательность Г-+ В,: Р-+ 6; Р-+ Вз. 'Р-» Р; 150 Р-з Вз. 'Р -з (Р -+ (6 -з Н)); Р в4' Р (6 Н) Р-з Вз: Р-+ Н. (**) Эта последовательность формул заканчивается нужной нам формулой Р -+ Н, но выводом этой формулы она не является. Дополним последовательность (оо) новыми формулами так, что- бы она стала выводом формулы Р-+ Низ гипотез Р— ~ (6 — з Н) и 6. Для этого будем рассматривать последовательно каждую фор- мулу Р-+ В; из (оо) и добавлять перед ней необходимые формулы в зависимости от того, какова формула В; в выводе (о).
Рассмотрим первую формулу последовательности (**): Р-+ Вь Она имеет вид Р-з 6. Формула В„являющаяся формулой 6, пред- ставляет собой гипотезу в выводе (*). В этом случае перед форму- лой Р-+ В, добавляем в последовательность (**) такие формулы: Ср 6 (гипотеза); Сз. '6 — (Р— 6) (А)); Сз. 'Р-+ 6 (МР: С„Сз). Рассмотрим вторую формулу последовательности (о*): Р -+ Вз. Она имеет вид Р-+ Р Формула Вз, являющаяся формулой Р, пред- ставляет собой гипотезу в выводе (о). Но Рне является гипотезой в выводе, который мы строим. В этом случае перед формулой Р-з Вз добавляем следующие формулы, составляющие вывод формулы Р— з Риз аксиом: С4. 'Р-+ ((Р -+ Р) — з Р) (А1); сз' (Р - ИР - Р) — Р)) — ((Р (Р - Р)) — (Р - Р)) (А2); Со.
(Р-+ (Р -+ Р)) -+ (Р— з Р) (МР: С4, Сз)", С,: Р— з (Р-+ Р) (А1); Со. Р-з Р(МР: Со, Сз). Рассмотрим третью формулу последовательности (*о): Р-з В,. Она имеет вид Р-+ (Р-+ (6-+ Н)). Формула Вз, являющаяся фор- мулой Р -з (6 — з Н), представляет собой гипотезу в выводе (*). Поэтому перед формулой Р— з В, добавляем следующие формулы: Сз. Р— з (6 -+ Н) (гипотеза); С,о. '(Р-+ (6-з Н)) -+ (Р-+ (Р-+ (6-+ Н))) (А1); Сн. Р-+ (Р-+ (6-з Н)) (МР: С„Сго). Рассмотрим четвертую формулу последовательности (оо): Р— з Во.
Она имеет вид Р-+ (6-+ Н). Формула В4, являющаяся формулой 6 — з Н, получена по правилу МР из В, и В, последовательности (*). В этом случае перед формулой Р-+ Во добавим следующие фор- мулы: Сд' (Р-+ (Р-+ (6-з Н))) -+ ((Р-з Р) -+ (Р-+ (6 -+ Н))) (А2); С,з. (Р -з Р) -з (Р -+ (6 -+ Н)) (МР: Сн, Сп); См' Р + (6 ~ Н) (МР Со С~з)' Рассмотрим пятую формулу последовательности (оо): Р— з В,, Она имеет вид Р-з Н. Формула В„являющаяся формулой Н, получена по правилу МР из формул В4 и В, последовательнос- 151 ти (*). В этом случае перед формулой Г-+ В5 добавим следующие формулы: Сц5'. (Г-+ (6 -+ Н)) -э ((Г-+ 6) -+ (Г-~ Н)) (А2); См.
(Г + 6) + (Г -+ Н) (МР См Сп) Сц'. Г-~ Н(МР: Сз См). Получили нужную нам формулу Г-+ Н. Таким образом, вписав недостающие формулы в последовательность (44), мы получили вывод формулы Г-+ Низ гипотез Г-э (6-+ Н), 6: Со См ..., Сп. Проанализируйте полученный вывод, сравнив его с выводом в задаче 8.9, л. 8.12. Докажите, что в исчислении высказываний„в котором правилом вывода является правило МР, теорема о дедукции справедлива тогда и только тогда, когда следующие две формулы являются теоремами (в частности, аксиомами) в этом исчислении: (А1) Г-4 (6 — ~ Г); (А2) (Г-+ (6 -+ Н)) -+ ((Г-+ 6) — ~ (Г-+ Н)).
8.13. Докажите, что во всяком исчислении высказываний, в котором правилом вывода является правило МР и в котором справедлива теорема о дедукции, следующие формулы будут теоремами (выводимы из аксиом), каковы бы ни были аксиомы этого исчисления: а) Г-~ ((Г-~ 6) -~ 6); б) Г-+ (6-+ 6); в) 6 — э (Г-+ Г); г) (Г -+ 6) -+ ((6 — э Н) -э (Г -+ Н))„' д) (Г-~ 6) — э ((Н-+ Г) 4 (Н-+ 6)); е) ((Г-+ 6) -+ Г) -~ ((Г-+ 6) -~ 6); ж) (Г-+ (Г-+ 6)) -+ (Г-+ 6); з) (Г-+ (6 -+ Н)) -+ (6 -+ (Г-+ Н)); и) (6-+ Н) -+ (6-+ (à — э Н)); к) (Г-+ 6) -+ ((Г-+ (6-+ Н)) -+ (Г-~ Н)). Решение.
а) Правило МР состоит в том, что Г, Г-+ 6 ~- >- 6. Применив к этому утверждению дважды теорему о дедукции, получим сначала Г >- (Г-+ 6) 4 6, а затем ~-Г-+ ((Г 4 6) -+ -э 6). к) Выводимость Г-~ 6, à — ~ (6-~ Н), Г ~- Н осуществляется без использования аксиом (см. задачу 8.9, ж). Применив к ней дважды теорему о дедукции, получим требуемое утверждение. 8.14. Используя теорему о дедукции, докажите, что следующие формулы являются теоремами ФИВ (при этом необходимые выводы отыщите в предыдущих задачах): а) -4Г-+ (Г-+ 6); г) Г-+(Гч 6); б) (-46 -+ -4Г) -+ (Г-+ 6); д) (Гч Г) -+ Г; в) Г-+ ((-46-+ -4Г) -+ 6); е) (Гл 6) -+ 6.
Решение. а) В задаче 8.9, р доказана выводимость зГ, Г ~ — 6. Применив к ней дважды теорему о дедукции, сначала получим 152 выводимость зР»- Р-+ 6, а затем и требуемую теорему»- -чР-» -+ (Р-+ 6). 8.15. Используя теорему о дедукции, докажите, что следующие формулы являются теоремами ФИВ (при этом необходимые выводы постройте, опираясь, если это будет необходимо, на ранее доказанные теоремы ФИВ и выводимости): а) (Р-» 6) -+ (з 6-+ -зР); г) (Р-+ 6) -+ ((Р + -з 6) -+ -з Р); б) Р-+ (-и6-» -з(Р-» 6)); д) -зР-» ((-з6 — » Р) — » 6). в) (Р-+6) -+ ((зР-» 6) -+ 6); Решение.
а) Покажем сначала, что Р -+ 6»- -з6 -» -зР, построив для этого соответствующий вывод: (1) Р-+ 6; (2) -гзР— » Р; (3) тзР-» 6; (4) 6 -+ -з-»6; (5) ~-зР— » -з~6; (6) (-г~Р-» .тз6) -+ (-~6 -+ зР); (7) -з6 -+ зР. Поясним: (1) — гипотеза; (2) есть теорема на основании задачи 8.10, а. Формула (3) может быть выведена из (2), (1) на основании задачи 8.9, и (свойство транзитивности); (4) есть теорема в силу задачи 8.10, в.
Формула (5) может быть выведена из (3), (4) на основании задачи 8.9, и; (6) есть теорема согласно задаче 8. 14, б; наконец (7) получена из (5), (6) по МР. Итак, формула з6 -» -+ зРдействительно может быть выведена из Р-» 6. Применив к этой выводимости теорему о дедукции, получим требуемую теорему. 8.16.
Используя теорему о дедукции, докажите, что справедливы следующие выводимости (при этом необходимые выводы отыщите в предыдущих задачах): а) Р»- (Р-+ 6) -+ 6; г) 6»- Р~~ 6; б) Р-+ 6, 6-+ Н»- Р-» Н; д) Р-»(6 — »Н)»- 6-+(Р-+Н); в) Р»-Р~ 6; е) -з6-+ -зР»- Р-» 6. Решение. а) Сначала нужно увидеть, что Р, Р -+ 6»- 6. Но это есть правило вывода МР. Применив к этой выводимости теорему о дедукции, получаем требуемую выводимость: Р»- (Р-+ -+ 6) -» 6. 8.17. Используя теорему о дедукции, докажите, что справедливы следующие выводимости (при этом обоснование возможности соответствующего вывода постройте, опираясь, если это будет необходимо, на ранее доказанные теоремы и выводимости ФИВ): а) Рл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}
