В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 29
Текст из файла (страница 29)
Все они называются аксиомами. Поэтому каж- дое из выражений (А1), (А2), (АЗ) называют схемой аксиом. Далее определяется следующее правило получения новых формул из имеющихся. Если имеются формулы Г и (Г-+ 6), то они дают формулу б. Это правило называется тос(ив ропепв или правилом отделения (сокращенно МР) и записывается так: Г, (Г-+6) Наконец определяется понятие доказательства или вывода. Доказательством или выводом формулы Г из множества формул (гипотез) Г называется такая конечная последовательность В„ В„..., В, формул, каждая формула которой является либо аксиомой, либо формулой из Г (гипотезой), либо получена из двух предыдущих по правилу МР, а последняя формула В, совпадает с Г. Если имеется вывод формулы Гиз множества гипотез Г, то 143 говорят, что Р выводима из Г, и пишут Г ~ —.
Если же имеется вывод Гиз пустого множества гипотез, то говорят, что Рвыводима из аксиом или что Р доказуема. В этом случае Р называют глеоремой и пишут ~- Р. Если Г = (Го Ри ..., Р„), то вместо (Ро Ри ..., Р,„) ~- 6 будем писать Р„Р;, ..., Р„~- 6. Поскольку в аксиомах не участвуют связки л, ч, ++, то нам придется их определить. Эти связки вводятся с помощью следующих определений: (Р л 6) означает -~(Р-+ -зб); (Р чб) означает(-зР-+ 6); (Г++ 6)означает ((Р-+ 6) л(6-+ Р)).
Как и в алгебре высказываний, договоримся внешние скобки у формулы не писать. Построение выводов нз аксиом. Решить задачи 8.1 — 8.4. 8.1. Среди следующих формул укажите те, которые являются аксиомами: а) (Г -+ ((Р -+ Р) -+ Р)) -+ ((Р -+ (Р -+ Р)) -+ (Р -+ Р)); б) Г -+ ((-зР -+ 6) -+ Р); в) (6 -+ Н) -+ (Р -+ (б -+ Н)); г) (-чР-+ 6) -+ (-~6 -+ -пР); д) (чР -+ -з-ч 6) -+ ((-чР -+ -ч 6) -+ Р); е) -~Р-+ (Р-+ -зР); ж) (6 -+ Р) -+ ((6 -+ ~Р) -+ -зб); 3) (-зб -+ тзР) -+ ((-зб -+ -зР)); и) (Г-+ 6) -+ (Н-+ (б-+ Р)); к) (б -+ (-~Р -+ Г)) -+ ((6 -+ -зР) -+ (б -+ Р)); л) ((-зР-+ 6) -+ (Г-+ 6)) -+ (-зР-+ 6); м) (-и-юР -+ -зР) -+ ((~~~Р -+ Р) -+ -пР); н) (Р -+ ((Н -+ Р) — э (б -+ (Н -+ Р)))) -+ ((Г -+ (Н -+ Р)) -+ (Р- (6 — (Н вЂ” Р)))) Ре ш е н и е.
а) Аксиома, получающаяся из схемы аксиом (А2), если там в качестве формулы Г взять саму Р, в качестве б взять Р-+ Р, а в качестве Н взять Р б) Аксиома (А1), если взять Р- =Р, 6 = -зР-+ б. в) Аксиома (АЗ), если взять Р= — Р, 6 =- зб. 8.2. Укажите недостающую формулу 1е так, чтобы третья из данных формул получалась из первой и второй формул по правилу вывода МР: а) Р-+ (Н-+ Г), (Р-+ (Н-+ Р)) -+ (Р-+ (6-+ (Н-+ Р))), И'; б) Р -+ (б -+ Н), 1е', (Р -+ 6) -+ (Р -+ Н); в) И; (~6 -+ -зб) -+ ((-зб -+ 6) -+ 6), (-чб -+ 6) -+ 6; г) Р-+ б, И~ Н-ь (Р-+ 6); д) 6, б-+ (Р-+ 6), И~; е) И~, (~Р-+ -чб) -+ ((-зР-+ 6) -+ Р), (-зР-+ 6) -+ Р; ж) б -+ Р, )т', (б -+ -зР) -+ (6 -+ Р); 144 з) И; (6-+ (зР-+ Р)) -+ ((6-+ зР) -+ (6-+ Р)), (б-» -зР) -+ -+ (б-+ Р); и) зб -+ (Р -+ -зб), (-зб -+ (Р-+ -чб)) -+ 6, И'".
Решение. а) Если в схеме правила вывода МР принять за Р формУлУ Р-+ (Н-+ Р), то вторая формула данной задачи может выступить в качестве формулы Р -+ б правила МР, где б есть формула Р-+ (б-+ (Н вЂ” » Р)). По правилу МР она является резуль- татом применения этого правила к двум данным формулам, т.е. является искомой формулой 1К б) Здесь для двух формул Р и 6 требуется сконструировать такую формулу И~ чтобы из Г и И'выводилась б по правилу МР.
Ясно, что в качестве И~должна быть взята формула Р-» 6. В дан- ном случае (Р-+ (6 -+ Н)) -+ ((Р-+ 6) -+ (Г-+ Н)). в) Первая из двух данных формул имеет вид Р-+ 6, где Р=— -з 6-+ -6 6=-( 6- 6)- б.п уж=--6- -б. 8.3. Выясните, является ли данная последовательность формул выводом из аксиом. Если является, то обоснуйте каждый шаг по- строения этой последовательности. Если не является, то докажите это. а) (1) б-+ (Р-+ 6), (2) (6- (Р— 6)) — (б- (6- (Р- 6))), (3) б-+ (б-+ (Р-+ 6)).
б) (1) (-чб -+ -зР) -+ ((-чб -+ Р) -+ С), (2) ~Р -+ (зб -+ -зР), (3) -зР-» ((-зб -+ Р) -+ 6). в) (1) Г-+ (6-+ Р), (2) (Р-+ (б -+ Р)) -+ ((Р -+ 6) -+ (Р-+ Р)), (3) (Р-+ 6) -+ (Р-+ Р). г) (1) (Р-+ Р) -+ (6-+ (Р-+ Р)), (2) Г-» Р, (3) б -+ (Г-+ Р). д) (1) (Н-+ Р) -+ (6-+ (Н-+ Р)), (2) ((Н-+ Р) -+ (6-+ (Н-+ Р))) -+ (Г-+ ((Н-+ Р) -+ (6-+ -» (Н-» Р)))), (3) Г -+ ((Н -+ Р) -+ (6 -+ (Н -+ Г))), (4) (Р -+ ((Н -+ Р) -+ (6 -+ (Н -+ Р)))) -+ ((Р -+ (Н -+ -+ Р)) -+ (Р -+ (б -+ (Н -+ Р)))), (5) (Р-+ (Н-+ Р)) -+ (Р-+ (6 -+ (Н-+ Г))), (б) Р-+ (Н вЂ” » Г), (7) Г-+ (6-+ (Н-+ Р)).
е) (1) -чб -+ ~6, (2) (-зб -+ зб) -+ ((-зб -+ 6) -+ 6), (3) (зб -+ 6) -+ 6, ж) (1) б -+ (-зР-» 6). Решение. а) Данная последовательность формул является выводом. Обоснуем это. Каждая из формул (1), (2) представляет 145 собой аксиому (А1). Формула (3) получена из (1) н (2) по правилу МР. б) Данная последовательность формул не является выводом. Покажем это. Хотя формулы (1) и (2) являются аксиомами ((А2) и (А1) соответственно), формула (3) не является аксиомой и не может быть получена из (1) и (2) по правилу МР. Следовательно, раз имеется хотя бы один неверный шаг, то последовательность выводом не является. 8.4.
Докажите, что следующие формулы являются теоремами формализованного исчисления высказываний, построив последовательности формул, являющиеся выводами данных формул из аксиом: а) Г-+ Р; ж) Р-+ (6 -+ (Н-+ Р)); б) 6-+ (Г-+ Р); з) Г-+ ((6-+ 6) -+ (Н-+ Р)); в) (Г-+ 6) -+ (Г-+ Р); и) 6-+Ч(Рч 6); г) 6 -+ (6-+ (Р-+ 6)); к) (-з6 -+ 6) -+ 6; д) 6-+ (Г-+ (6 -+ Г)); л) ~6 -+ ((-гГ-+ 6) -+ Г). е) 6-+ (Р-+ (Н-+ Р)); Решение. а) Таким выводом является, например, следующая последовательность формул: (1) (Р-+ ((Р-+ Р) -+ Р)) -+ ((Г-+ (Г-+ Р)) -+ (Г-+ Р)), (2) Г-+ ((Г-+ Г) -+ Р), (3) (Р-+ (Г-+ Р)) -+ (Г-+ Р), (4) Г-+ (Г-+ Р), (5) Г-+ Г.
В самом деле, формула (1) представляет собой аксиому (А2), в которой в качестве формул Р и 6 взята формула Р, а в качестве формулы 6 — формула Г-+ Г. Формула (2) представляет собой аксиому (А1), в которой в качестве формулы 6 берется формула Г-+ Г. Формула (3) получена из формул (1) и (2) по правилу МР. Формула (4) есть аксиома (А1). Наконец формула (5) получена из формул (3) и (4) по правилу МР. г) Обоснуйте каждый шаг вывода этой формулы, помещенного в задаче 8.3, а.
Построение выводов из гипотез. Решить задачи 8.5 — 8.10. 8.5. Пусть последовательность формул „„..., В, является выводом из множества гипотез Г и Г в И. Уточните, что можно сказать тогда о формулах В, и В,. Тот же вопрос для случая Г = И.
8.6. Докажите, что понятие выводимости обладает следующими свойствами: а) Г)- Г; б) Г„Рп ..., Р ) — Гь ! = 1, 2, ..., т; в) если Р„Рп ..., Г„~- 6„Г„Рп ..., Г„~ — 6п ..., Ро Гн ..., Р„~ — 6ги 6п 6н ..., 6г~ — Н,тоРп Рн ..., Рщ~ — Н. 8.7. Докажите, что: а) если ь-Р-+ 6, то Р ~- 6; 146 б) еслиР„...,Р„п~-Р -+ б,тоРп ...,Р „Р ~- б; в) если(>-Рп-+(...-+(Р„,-+(Р„-+ 6))...),то Рп ..., Р„„Р„~- 6. 8.8. Выясните, является ли данная последовательность выво- дом из гипотез. Если да, то укажите, выводом из каких формул и какой формулы является. Если нет, то объясните почему.
а) (1) 6 -~ Н; (2) б; (3) Н; (4) Н-ь (Р-+ Н); (5) Р-+ Н. б) (1) Р -+ 6; (2) Г-+ -зб; (3) (Р-+ 6) -+ ((Г-+ -юб) -+ -юР); (4) (Р-+ -зб) -+ -чР; (5) -зР. в) (1) 6; (2) 6-+ (Р-э 6); (3) Р-+ С. г) (1) (Р-+ (Р-+ 6)) -+ ((Р-+ Р) -+ (Р-+ 6)); (2) Г-+ (Р-э 6); (3) (Р-+ Р) -+ (Р-+ 6); (4) Р-+ Р, (5) Р-+ 6. д) (1) Р-» б; (2) -зР-+ 6; (3) (Р -+ С) -+ (-з 6 -+ -зР); (4) -зб -+ ~Р; (5) (зР -+ 6) -+ (-з 6 -+ -АР)," (о) -зб -+ тзР, (7) (-~ 6 -+ -тзР) -+ ((-з 6 -+ ~Р) — э 6); (8) (зб -+ зР) -+ 6; (9) 6. е) (1) Р-+ (б — э Н); (2) (Г-+ (О -+ Н)) -+ ((Р-+ 6) -э (Р-+ Н)); (3) (Р-+ С) -+ (Г-+ Н); (4) б-+ (Г-+ 6); (5) б; (б) Р-+ 6; (7) Г-+ Н. ж) (1) Р-+ (б-+ Р); (2) (Р -+ (6 -+ Р)) -+ ((Г -+ 6) -+ (Г -+ Р)); (3) (Р-+ 6) -+ (Р-+ Р); (4) Р-+ б; (5) Р-+ Н.
з) (1) -иб -+ зР; (2) (-чб -+ -зР) -+ ((-зб -э Р) -+ 6); 147 (3) (~6-+ Г) — » 6; (4) Р -+ (-з 6 -+ Р); (5) Р-+ 6. Р е ш е н и е. а) Гипотезами здесь выступают формулы (1), (2). Формула (3) получена из (2), (1) по правилу МР. Итак, здесь приведен вывод формулы Г-+ Низ гипотез 6, 6 -+ Н.
б) Формулы (1), (2) не являются аксиомами и потому должны быть приняты за гипотезы. Формула (3) похожа на аксиому (АЗ), но все же не является ею. Формула (4) получена из (1), (3) по МР. Формула (5) получена из (2), (4) по МР. Итак, данная последо- вательность является выводом формулы (5) из формул (1), (2), (3), но не является выводом формулы (5) из формул (1), (2). 8.9. Докажите, что имеют место следующие выводимости, построив соответствующие выводы из гипотез: а) Г,Р-+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.8, в. в) Ясно, что если формула выводится из какого-то множества гипотез (см. задачу 8.9, б) настоящей серии, то она выводится и из большего (обьемлющего его) множества гипотез (см. теоре- му 15.3, а в Учебнике). и) Приведем соответствующий вывод с краткими пояснениями: 148 (1) Г-+ 6 (гипотеза)„' (2) 6 -+ Н (гипотеза); (3) (б -+ Н) -+ (Г-+ (6 -+ Н)) (А1); (4) Г-+ (б -+ Н) (МР: (2), (3)); (5) (Г-+ (б -+ Н)) -+ ((Г-+ 6) -+ (Г-+ Н)) (А2); (6) (Г-+ 6) -+ (Г-+ Н) (МР: (4), (5)); (7) Г -+ Н (МР: (1), (6)).
Обратите внимание на то, что в Учебнике, в лемме 15.7, а обоснование у этой выводимости опирается на теорему о дедукции. л) Вывод этой формулы помещен в условие задачи 8.8, е. Обратите внимание на то, что в Учебнике в лемме 15.7, б приведено обоснование этой выводимости с помощью теоремы о дедукции. т) Обоснуйте каждый шаг следующего вывода: (1) Г; (2) Г -+ (-зà †» Г); (3) -зГ -э Г; (4) (-зГ-+ Г) -+ (6-+ (-1Г-+ Г)); (5) б-+ ('чГ-+ Г); (6) (б -+ (-1Г -+ Г)) -+ ((6 -+ -1Г) -+ (6 -+ Г)); (7) (б -+ ~Г) -+ (6 -+ Г).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
