В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 31
Текст из файла (страница 31)
153 Р е ш е н и е. а) Согласно определению логической связки л требуется доказать следующую выводимостгс -«(à — « -~6) «- Р Строим вывод: (1) «(Г-« -«6); (2) -ч(Г-« -«6) -+ («Р-« -з(Г-« -«6)); (3) «Г — « -«(Р-« -«6); (4) («Р — « -«(Р— « -з6)) -+ ((~Р— «(Р -+ «6)) -+ Р); (5) (-«Р -+ (Г -+ -ч 6)) -«Г; (б) «Р — «(Р-+ -«6); (7) Г. Для пояснения отметим лишь, что формула (б) является теоремой согласно задаче 8.14, а, а следовательно, последовательность (1) — (7) превратится в вывод формулы Г из гипотезы «(Г-« -з 6), как только она будет пополнена доказательством формулы (6). 8.18.
Докажите, что: а) Р, 6 «- Н тогда и только тогда, когда «-(Г л 6) — «Н; б) Р;, ..., Р„«- Нтогда и только тогда, когда «-(Р; л ... л Г„) — «Н. Производные правила вывода и их применение. Решить задачи 8.19 — 8.22. 8.19. Докажите, что справедливы следующие производные правила вывода, называемые правилами введения логических связок (à — некоторое множество формул, возможно пустое): а) введение импликации (-+-вв): Г,Р«-6 Г«-Р— «6 б) введение конъюнкции (л-вв): Г «- Г, Г « — 6 Г« — РЛ6 в) введение дизъюнкции (~-вв): Г «- Г Г «- 6 Г«-Р~~6 Г«-Г~6 г) введение отрицания (приведение к абсурду) («-вв): Г, Г «- 6; Г, Р « — -«6 Р е ш е н и е. В предыдущих задачах найдите оправдание для перечисленных правил введения логических связок.
Например, для обоснования правила в) введения дизъюнкции отметим, что в задаче 8. 16, в доказано, что Г «- Гч 6. Поскольку еще по условию 154 Г «- Р, то по свойству выводимости (задача 8.б, в) из этих двух утверждений заключаем, что Г «- Г~ б. Аналогично, но с использованием задачи 8.9, 4, где доказано, что 6 «- Гч б, проверяется второе правило введения дизъюнкции. 820.
Докажите, что справедливы следующие производные правила вывода, называемые правилами удаления логических связок (à — некоторое множество формул, возможно пустое): а) удаление импликации ( — «-уд): г «- Г; г «-Р -«6 Г «-6 б) удаление конъюнкции (л-уд): Г«-Глб Г«-Гдб Г «- Р ' Г «- б в) удаление конъюнкции (л-уд): Г, Р, б «- Н Г, Г Л 6 «- Н г) удаление дизъюнкции (Генцем) Г «- Г м 6; Г, Г « — Н; Г, б «- Н Г «- Н д) удаление дизъюнкции (Клили) Г,Р«-Н;Г,б«-Н Г,Р~I6«-Н е) сильное удаление отрицания (сильное -1-уд): Г «- Р ж) слабое удаление отрицания (слабое -1-уд): Г «- Р; Г «- -1Р Решение. г) По теореме о дедукции из условия вытекает, что Г «- Г-+ Н и Г «- б — «Н.
Далее, по задаче 8.17, з, Рч 6, Р-«Н, 6-+ Н«- Н. Поскольку, кроме того, по условию еще Г «- Гч 6, то по свойству выводимости из задачи 8.6, в заключаем, что Г «- Н. 155 8.21. Используя производные правила вывода из задач 8.19, 8.20, докажите, что справедливы следующие выводимости: а) -«6, «Н «- -«(б л Н); з) -«б, Н «- б-+ Н; б) «б, Н «- -«(6 л Н); и) 6, «Н «- -«(6 -+ Н); в) б, -«Н «- -«(б л Н); к) 6, Н «- 6 -+ Н; г) ~6, -«Н« — -«(бч Н); л) -«6, -«Н «- 6++ Н; д) «б, Н «- бч Н; м) -«6, Н « — -«(6++ Н); е) б, «Н «- 6 ~ Н; н) 6, -«Н « — -«(6++ Н); ж)-«б, -зН «- 6 — «Н; о) 6, Н «- б ++ Н.
Р е ш е н и е. а) Обоснуем эту выводимостгя (1) «б, -«Н, 6 л Н «- -«б (задача 6, б); (2) -«б, -«Н, 6 л Н «- 6 (л-уд (задача 20, о)); (3) -«б, -зН, «- -ч(6 л Н) («-вв (задача 19, г): (1), (2)). г) Обоснуем эту выводимость: (1) -«б, -«Н « — -«б л «Н(л-вв); (2) -«б л «Н, 6 «- 6 (задача б, б); (3) «б л «Н, 6 « — -«б (л-уд); (4) ~б л ~Н, б « — ~(б м Н) («-уд: (2), (3)); (5) -«б л «Н, Н «- Н (задача б, 6); (6) «б л «Н, Н «- -«Н (л-уд); (7) «б л «Н, Н « — -«(6 ч Н) (-«-уд: (5), (6)); (8) -«б л -«Н, бч Н « — -«(6 з Н) Ч,ч-уд по Клини: (4), (7)); (9) -«б л -«Н, 6 ~ Н « — б ч Н (задача 6, б); (10) «б л -«Н «- -«(б м Н) (-«-вв: (8), (9)); (11) -«б-«Н «- -«(6 ~ Н) (задача б, «с (1), (10)).
и) Приводим обоснование этой выводимости: (1) 6, «Н, 6 -+ Н «- -«Н (задача б, б); (2) 6, «Н, 6 -+ Н «- Н (-+-уд (задача 20, а)); (3) 6, -«Н « — -«(6 — «Н) (-«-вв (задача 19, г): (1), (2)). м) Обоснуйте каждый шаг следующего рассуждения: (1) «б, Н, 6++ Н « — Н-+ 6; (2) Н, Н-+ С «- б; (3) «б, Н, 6++ Н «- 6; (4) -«б, Н, 6++ Н «- -«б; (5) -«б, Н « — ~(б++ Н), 8.22. Используя производные правила вывода из задач 8.19, 8.20, докажите следующие выводимости и теоремы: а) Гл б «- б л Г; б) «- Г ~ -«Г; в) -(Гл 6) ° (бл Г); г) «-(Гч 6) ++ (6 м Г); д) «-(Гл Г) ++ Г; е) «-(Г ~ Г) ++ Г; ж) « — (Гл (6 л Н)) ++ ((Г л 6) л Н); з) « — ~(Гч (6 ~ Н)) ++ ((Г ~ 6) ч Н); и) «-(Г м (Г л 6)) ++ Г; 156 к) «- (Г л (Гч 6)) ++ Г; л) «- 1(Г ч 6) +э ("1Р л "16); м)»- -1(Р л 6) ++ (-»Рч -16); н)»- (Рл (б ч Н)) ++ ((Гл 6) ч (Г л Н)); о) «-~(Рч (бл Н)) ++ ((Рч 6) л (Рч Н)); п)» — (Г «6) ++ (-»6 -+ -»Р); р) «--»-»Р++ Г.
Р е ш е н и е. б) Читателю предлагается тщательно разобраться в приводимом обосновании доказательства. (1) ~(Рч-»Р), Г»- Г(задача 8.6, б); (2) »(Рч -»Г), Г»- Гч »Г(ч-вв: (1)); (3) »(Рч-»Р), Р«- Ч(Рч -»Г) (задача 8.6, б); (4) -1(Рч-»Г) «- -»Г(-»-вв: (2), (3)); (5) И(Рч -»Г)»- Гч -1Р(ч-вв: (4)); (6) -1(Рч -»Г) «- -»(Г ч -»Р) (задача 8.6, а); (7)»- -»-»(Р ч -1Р) (-»-вв: (5), (6)); (8) «- Гч -»Г(сильное -»-уд: (7)). д) Приведем обоснование этой выводимости: (1) Гл Р«- Г(л-уд); (2) «- (Г л Р) -+ Г (-+-вв: (1)); (3) Г, Р-+ -1Г«- Р(задача 8.6, б); (4) Г, Г « -1Р «- -»Г (МР); (5) Р «- -1(Р-+ -1Р) (-1-вв: (3), (4)); (6)»-à — » (Г л Г) (-+-вв: (5)); (7) «-(Р л Р) ++ Р (л-вв: (2), (6)).
ж) Обоснуйте справедливость следующего рассуждения: (1) Гл (6 л Н)«-Г; (2) Р л (б л Н) «- 6 л Н; (3) С л Н «- 6; (4) 6 л Н «- Н; (5) Гл (бл Н) «- б; (6) Рл(блН) «-Н; (7) Рл (бл Н) «- Гл 6; (8) Г л (6 л Н)»- (Р л 6) л Н; (9)» — (Р л (б л Н)) -+ ((Р л 6) л Н); (10) (Р л 6) л Н «- Гл 6; (11) (Р л 6) л Н»- Н; (12) Гл 6»- Р, (13) Рл 6 «- б; (14) (Гл 6) л Н»- Г; (15) (Рл 6) л Н» — 6; (16) (Г л 6) л Н»- б л Н; (17) (Г л С) л Н «- Г л (6 л Н); (18) «- ((Г л 6) л Н) -+ (Р л (6 л Н)); (19) «-((Г л 6) л Н) +«(Р л (б л Н)).
Независимость системы аксиом. Решить задачи 8.23 — 8.27. 157 8.23. Рассмотрим трехэлементное множество М= (О, 1, 2). Введем в нем две операции. Первая операция унарная, сопоставляющая каждому элементу А из М элемент из М, обозначаемый -~А. Вторая операция бинарная, сопоставляющая любым двум элементам А, В из М элемент из М, обозначаемый А -+ В. Сопоставление осуществляется в соответствии со следующими таблицами: Таким образом, если всем переменным, входящим в формулу Г исчисления высказываний, придавать некоторые значения из М, то согласно введенным правилам (если в формулу входят связки л, ч, ++, то нужно предварительно вспомнить нх определения) формула примет некоторое значение из множества М Формула, которая всегда принимает значение О, называется выделенной. Докажите, что: а) всякая формула, получающаяся по схеме аксиом (А2), является выделенной; б) всякая формула, получающаяся по схеме аксиом (АЗ), является выделенной; в) правило МР сохраняет свойство выделенности, т.е.
если формулы Р и à — ~ 6 выделенные, то и формула 6 выделенная. 8.24. Аксиома называется независимой от остальных аксиом аксиоматической теории, если она не может быть выведена из них в этой аксиоматической теории. Докажите, что аксиома (А1) не зависит от аксиом (А2), (АЗ) формализованного исчисления высказываний. Указание. В силу задачи 8.23 все формулы, выводимые из аксиом (А2) и (АЗ), являются выделенными. Поэтому для доказательства того, что аксиома (А1) из них невыводима, достаточно проверить, что она (точнее, одна из конкретных формул, получающихся из схемы (А1)) не является вьщеленной.
158 3 а м е ч а н и е. О рассуждениях, проведенных в задачах 8.23, 8.24, говорят, что построена модель, в которой выполняются аксиомы (А2) и (АЗ), но не выполняется аксиома (А1). 8.25. Докажите, что аксиома (А2) не зависит от аксиом (А1) и (АЗ) формализованного исчисления высказываний. Указание. Рассмотрите, например, модель, в которой операции -1А и А -+ В задаются согласно следующим таблицам: 8.26.
Докажите, что каждая из моделей а) — м) на трехэлементном множестве (О, 1, 2», где операции -з и -+ определены с помощью таблиц, доказывает независимость аксиомы (АЗ) от аксиом (А1) и (А2): Унарная операция чА Бинарная операция А -+ В 159 Окончание таблицы Решение. л) Проверим, что в данной модели формулы (А1) и (А2) будут О-выделенными, т.е. они принимают только значения О. Для этого составьте их таблицы истинности.
Проверим, что в данной модели правило МР вывода формул сохраняет свойство 0-выделенности формул, т.е. если формулы Г и Г-~ 6 О-выделенные, то 0-выделенной будет и формула 6. Это видно из определения операции -+ в данной модели: В самом деле, если бы 6 принимала на некотором наборе (а, Ь, с) значение а' ~ О, т.е. 6(а, Ь, с) = И, е( а (1, 2), то на этом наборе было бы Г(а, Ь, с) ~ 0 или Г(а, Ь, с) -+ 6(а, Ь, с) ~~ 0 (что следует из определения операции -~). Это противоречило бы 0-выделенности формул Ги Г-+ 6. Итак, из 0-выделенных формул с помощью правила вывода МР могут получаться только 0-выделенные формулы.
Теперь для доказательства того, что формула (АЗ) не может быть выведена с помощью правила МР из 0-выделенных формул (А1) и (А2), достаточно проверить, что формула (АЗ) не является О-выделенной. В самом деле, вычислим, например, значение этой формулы при Г = 1, 6 = 2: (-ч2 -+ ~1) -+ ((-12 -э 1) -+ 2) = (1 -+ 0) — ~ ((1 -+ -+ 1) -+ 2) = 0 -+ (О -+ 2) = 0 -+ 1 = 2. м) Доказательство независимости аксиомы (АЗ) с помощью данной модели представляет собой некоторую модификацию доказательства, проделанного с помощью предыдущей модели. Назовем формулу (О, 2)-выделенной„если она принимает только два значения 0 и 2.
Проверьте, что в данной модели формулы (А1) и (А2) будут (О, 2)-выделенными. Для этого составьте их таблицы истинности (нас не должно смущать то, что значение 2 формула (А1) ни разу не принимает). Проверим, что в данной модели правило МР вывода формул сохраняет свойство (О, 2)-выделенности формул, т.е. если формулы Г и Г -+ 6 (О, 2)-выделенные, то (О, 2)-выделенной будет и 1бО формула 6. Это видно из определения операции -+ в данной модели (имеет место как бы замкнутость подмножества (О, 2) в множестве (О, 1, 2) относительно правила МР в указанном смысле): Итак, из (О, 2)-выделенных формул с помощью правила вывода МР могут выводиться только (О, 2)-выделенные формулы. Теперь для доказательства того, что (АЗ) не может быть выведена с помощью правила МР из (О, 2)-выделенных формул (А!) и (А2), достаточно проверить, что формула (АЗ) не является (О, 2)-выделенной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
