И.А. Лавров,Л.Л. Максимов-Задачи по теории множеств, математической логике и теории алгоритмов (Учебник Лаврова 2006-го года), страница 33

Тогда в А найдутся ф)нк ииУ, Ю С[,У~ (е Со*75 М 1" ~4 Ю Р'55 ~ М. Функции 8(х) =7,(х, ..., х) н Ь(х) = 5 (х, ..., х) являются либо функциями 0 и 1, либо одна из них есть ч. В первом случае вследствие задачи 20 (а) из У получаем ч. Во втором случае вследствиезада-, 5 чи 21 (а) из ~- получаем 0 и 1. Итак, О, 1, 1 Е.А. Теперь вследствие задачи 22 (а) из 7' получаем 8. Итак, ч, 8Е АиА = С (см. задачу 8 (в)). 26.

Воспользуемся указанием к задаче 25. Из любого базиса для С можно оставить не более пяти функций: У1 Ю С1, ф С, у ф 1., у ~ Р, у ф М. Если у (х, ..., х) = О, то у ~ Р н можно выбросить |. Если ( (х, ..., х) =!, то 7" Ю Р и можно выбросить | . 4' 2 Еслибы (х, ..., х) = Г (х, ..., х) = -1 х, то можно выбросить) . 29. Индукцией по числу шагов построения Т, используя задачи 27 и 28.

30. 31. Следуют из задачи 29. 32. ЗЗ. См. задачу 30. 0 3. Исчисления высказываний 1. (а) А 1-А, 1- (А Р А) (аксиома, правило 7). (6) Х,: А 1-А (аксиома), Х: (А ~ В) «(А З В) (аксиома), Х:А, (А ~ В) «В (правило 8, Х, Х ), Х4. (В Э С) 1- (В Э С) (аксиома), Х5.' А, (А З В) „(В ~ С) 1- С (правило 8, Хз' Х4) Х: (А ~ В), А, (В:1 С) «С(правило 14,Х ), Х:(А Э В), (В З С), А 1- С (правило 14, Х ). (в) Из аксиом чА «.зА и .1-1А «-~-~А, применяя правила 14, 10, 1 1, 7, получить 1- (.1 -1 А ~ А). Из аксиом -1 А « -~ А и -1 р А 1- -1 -1 А, 7* !9б ОТВЕТЫ, РЕЩЕНИЯ, УКАЗАНИЯ применяя правила 10, 9, 7, получить «-(А э -« -«А).

Применить пра- вило 1, (г) Из аксиом А «- А, (А Э В) ь (А з В), (А«(В:«С)) «- (А~(В~ С)) с помощью правил 8, 14, 15. (д) Из аксиом А «- А, (А ~ В) ь (А Э В), -«В ь -«В с помощью пра- вил 9, 10, 14. (е) См. указание к (д). 2, Заменить в секвенциях вывода для А, ..., А ьВ каждую фор!'"' а мулу В на Р(Р««С) . Доказать индукцией по длине вывода, что при этом получится требуемый вывод. 3.

(а) Использовать правила 7 и 8. (б) Использовать аксиому (А8В) ь(А8В) и правила 2, 3, 14, 15 и (а). (в) ИспользоватьаксиомыА ьА, В «-В и правила 1, 14 н (а). (г) Использовать аксиому (А ч В) «(А У В) и правила б, 15. (д) Использоватьаксиому 1В ь-«Виправила 9, 10, 14. (е) Использовать аксиому В ь В и правила 10, 11, 14.

(ж) Использовать (б) и правило 7. (з) Использовать (в) и правило 8. 4. По правилу 12 из выводимости Г «- следует выводнмость ! Г, «- -«(А ~ А). Далее используем выводимость «- (А «А) и правило 1О. 5. Использовать задачу 3. б. (а) Использовать правила 1 и 7. (б) ИспользоватьаксиомыА ьА, В ьВи правила 2, 3 и 8. 7. Использовать задачи 3 и 5, 8. Ицдукцией по числу шагов построения А из В, используя за- дачу б. 9. (д), (е) Использовать правила 1 — 5 н задачи 3 и 5.

(ж), (з> Использовать правила 1 — 5 и задачи 1(а), 3 и 5. (и) Х: (А «В), А «- В (по правилу 8), Х: (А:! В), А «-(-«АчВ) (правило5), Х: (А ~ В), и (-«А ч В) л -«А (задача 3(д)), Х4. (А ~ В), - (. АчВ) л(«А У В) (правило 8), Х: (А ЗВ), и (-«А У В) ь-«(-«А о В) (правило 13), Хб. (А «В), и (и А У В) «-(правило 10), Х: (А «В) «- (1 А ч В) (правило 11). (к) Использовать (и) и задачи 1 (а), 3 (а). (л) Х,: -«А, В,А «-В (правило 13), !97 Ч. 11. МАТЕМАТИЧЕСКАЯ ЛОГИКА Ц 31 Х: ~А, В 1-(А Э В) (правило 7), 2' Х: и (А З В), В «А (пРавило 14 и задачи 1(в), 3(а),(д) н 5(а)), 3' Х: «(-! (А э В) 'З (В ЗА)) (правило 7,дважды), 4' Х: 1- ((А З В) ч (В Э А)) (по (и) н 1 (в)).

10. Использовать задачу 23 из 9 1 и задачу 8. 11. См. задачу 25 из 3 1 н задачу 9 (к). 12. Индукцией по длине вывода. 13. Следует из задач 9 — 11. 14. Использовать задачу 12. Для (д) н (е) воспользоваться также задачей 3 (ж), (з). 15. Привести А к с.д.н.ф. (А ч...ч А ), а В к с.к.н.ф. (В, 8 „, !Ъ В ). Тогда для любой пары А. и В. секвенция А «В. доказуема в ИС и / / поэтому А и В.имеют общий литерал С.. Полагаем С = ч Ь С,, / !/ !/ 16.

(а) В; (б) (Р 8 А). 17. (а) Да. (б) Да. (в) Нет. 18. (а) А = (Р э (Р э Р)), ', = ИР:) (Р ~ Р)) ~ ((Р ) ((Р ~ Р) ~ Р)) ~ (Р ~ Р))» 4з = ((Р ~ ((Р ~ ') ~ Р)) ~ (Р ~ Р)) * А,=( ((Р Р)~ )), Аз=(РЭР). (б) А1, АЗ, АЗ' А4' АЗ, ((Р ! Р) ! ((Р Э Р) !((Р Ч Р) ! Р))), ((Р З Р) Э ((Р ч Р):) Р)), ((Р ч Р) З Р); А, — А взяты из (а). (в) Получается из (а) и аксиомы 9. 19. Пусть А, ..., А есть вывод А в ИВ. Доказать нндукцией по/с 1' ' /! что А,(,Р 1В), ..., А (Р 1 В) есть вывод в ИВ. 20.

(а) ((Р З (Ц Э /1)), Р, Ц). (б) ((Р ! -! -! Д), -! Ц). 21. Вывод состоит из одной формулы А. 22. (г) Если А, ..., А есть вывод А из Г,, В, ..., В есть вывод В из А, Г, тоА,, ..., А, В,, ..., В есть выводВизГ,, Г . (д) Аналогично задаче 19. 198 ОТВЕТЫ, РЕШЕНИЯ, УКАЗАНИЯ 23. Пусть В, ...,В„есть. выводВ изГ,А. Доказать иидукцией по п, используя аксиомы 1, 2 и задачу 18 (а), что формулы (А з В ), „(А З В ) выводимы из Г. 24.

(а) Пусть Т = (А 'Э (В гА)). Имеем А ь(Т Э А),и В ь(Т З В). Тогда А, В ь (Т з (А $ В)) по аксиоме 5. Отсюда А, В, Т ь (А 8 В) и А,В ь(АЙВ). (б), (в), (д), (е), (з) Следуюг непосредственно из аксиом. (иг) Использовать задачу 23. Г, А. ь -г В (г) И!оиильзовать правило .', которое следует из аксиом и Г, В ь.гА' задачи 23. 28. Иусвь. Г ьА, Г ь-гА;  — любая формула. Тогда Г, -г В ьА; Г, .т:.Вь-~.А; Г ь-г -г В; -~ -гВ ьВ; Г ьВ. Обратноеочевидно.

26. Использовать задачи 23, 24. 27:Следует иэ задачи 26. 28- Использовать задачи 22 — 24. 29 '.Иидукцией по длине вывода А в Ий. 30.' Доказать одновременно три утверждения (а), (б), (в) индукцией по длине вывода секвенции в ИС. 32. Следует из задач 13 и 30 (в). ЗЗ( Например, А = Р, В = Д, где Р и Д вЂ” различные переменные. 34. Используем задачу 32. Пусть, например, А принимает значение л при значении л для переменных Р,, ..., Рв и значении и для переменных Р, ..., Р„. Положим В; =... = В = (Рб.г Р), В„ ...= В =(Рч тР).Тогда А (Р гВ, „Р гВ ) тождественноложна и ч А (Р гВ, ..., Р' гВ ) выводима. 35.

(а) Следует из задачи 26. (б) ИАИ (') ИВИ = ИЛЬИ, ИАИ () ИВИ = ИА ч ВИ, — ИА11 = 11-~АИ. (в) г-А ~ ь(В ~ А) ~ ИВИ «ИАИдлялюбайфармулыВ. Обратна, пусть ИАИ = 1. Возьмем В такую, что ьВ. Тогда ИВИ «ИАИ~ ~ь(В ЗА) ~ г-А, 37. (а) Индукцией по числу шагов в построении формулы А, используя задачу 66 из 8 3 части 1. (б) Пусть неверно ВА. Тогда ИА И и 1 в Р/= (см. задачу 35 (в)). Существует ультрафильтр Тна Рl= такой, что И А И Ю Т (см. задачу 68 из 8 3 части 1). Приладим переменным значения, как в (а).

Тогда А принимает значение л. 199 ч 11, мАткмАтическАя лОГикА 1$ 31 39.А принимаетзначение 1приР= Д = 1, Я = 2. 40. Следующие логические матрицы доказывают (см. задачу 38) независимость аксиом: 1) М= (О, 1, 2); Р = (2); х8у= поп (х, у); хчу= щах(х,у); (2, если х < у, хну= ~ '(О, если х > у; х = 2 — х. 2) Матрица из задачи 39.

3) М = (О, Ц; Р = (Ц; х8у = у; ч, Э, -~ определяются, как в9 2. 4) М = [О, Ц; Р = (Ц; х8у = х; ч, з, - определяются, как в 82. 5) М= (О, Ц; Р = (Ц; лбу = 0; ч, ~,-т определяются, как в 82. 6) М = (О, Ц; Р = (Ц; х ч у = у; $, ~, -~ определяются, как в 8 2. 7) М = (О, 1); Р = (Ц; хну= х; 8, ~, -~определяются, как в 82. 8) М = (О, Ц;,Р = (Ц; х и у = 1; 8, ~, -в определяются, как.в 8 2. 9) М = (О, Ц; Р = (Ц; -юх = 0; ч, 8, Э определяются, как в 82.

10) М = (О, 1, 2); Р = (2); х $ у = ппп (х, у); х ч у = щах (х, у); ~2, если х н у, ~0, если х >О, х~у= (у, если х > у; (2, если х= О. -х= 41. (а) Достаточно вывести в ИВ аксиому 1З. (б) См. указание к задаче 23. (в) Доказать, что все аксиомы ИВ выводимы в 1.. 42. (а) Достаточно вывести в ИВ формулу (-~ А З (А Э В)). (б) Использовать матрицу из указания 10) к задаче 40. 43. См. указание к задаче 23.

44. (а) См. указание к задаче 29. (6), (в), (г) См. указание к задаче 30. 45. Использовать задачу 44. 46. Инлукцией по длине вывода формулы А в ИВ, используя задачу 45. 47. (6) Формула А не общезивчзичв е,'М . 48. Пусть М содержит л элементов для.некоторого л Е У. Рассмотрим формулу А из задачи 47 и произвольные значения перемени ных в множестве м. тогда для некоторой пары 1,7 (1 м у) значения Р, и Р. совпадают, и формула А принимает значение О, так как ! л ьи ((В ч (Р еч Р)) ч С) для любых формул В и С.

Поэтому А общезначима в 88, но невыводима в ИИВ (см. задачу 47) . Ответы, РГшения, укА3Ания 0 4. Язык логики предикатов 1. (а), (б) Да. (в) Нет. 2. (а), (б) Да. (в), (г) Нет. 3. г не является предметной переменной. о 3 (а) (го г (го) Ф(~о)) (6) ("о' а ("о' "о)' а ('о' а (~о "о))' з (~ ("о' "о)* "о)' а (~ ('о' "о)' в™о' "о))' " )' 9. (а) О(к) Ф Ч У Б (х У У) ' (б) Е(х) ЧУР(х У У)' (в) Д(х) и Л г(Е(г) М(г, г, х)) 3 г(Ч УР(г, у, у)$5(г, г, х)) (Е(г) из (б))', (г) Ч(. ) = 3 уб (у,у, х); (д) Н(х) - -1Ч(х) -| 3 УЯ(У, У, х) (Ч(х) из (г) ); (е) П(х) и (-| Е(х) бЧУЧг(Р(у, г, х):) (Е(у) ч Е(г)))) (Е(г) из (6) ) . 10. (а) х = у Ч г Ы и(5(х, г, и):| 5(у г ™)) ' (б) х и у 3 г3(х, г У)' (в) х < уа(х ~ уй -|х = у) (Я, = из (а) и (б)); (г) Д(х, у) и 3 гР(х, г, у).