В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 62
Текст из файла (страница 62)
5. б) ппп(х, у) = х †. (х †. У); в) птах(х, у) = у + (х — у). 6. б) Схема примитивной рекурсии: г(0, у) = О, г(х + 1, у) = = Я(г(х, у)) . ва([у — Я(г(х, у))[), выражение через суперпозицию известных примитивно рекурсивных функций: «(х, у) = х — (у [х/у)); х в) т(х) = т ~вя г(х, !); (=! т г) о(х) =т~„! вя г(х,!); !=1 д) х — простое число ~~ т(х) = 2 (см.
1 3 . 6, в), поэтому тр (х) =,', вИ()т(!) — 2) + г(х, !)); х е) л(х) = ~вй([т(!) -2[); (см. задачу 13.6, в), !=! 7. б) х у = пт(п(х, у); в) х « у = птах(х, у). 9. б) 1(п) = р~ ~ п[~> ,", вя г(п, р(!)) = О); в) ехр(х, у) = р~ < х[(ва г(у, (р(х))" ') . вй у = 0[; г) НОК(х, у) = !!~ < х. У[г. ва(х у) + ва(х у)(ваг+ г(г, х) + + г(~, у)) = 01; д) НОД(х, у) = +х вау+у.вах; НОК(х, у) ! е) [!х~=р~<х[за((~+1)' — х)=О~; ж) Я = р~ < х [вя((~ + 1)т — х) вя у = 0~+ вау х; 3) [х Г21 = Р~ < 2х[яа((~+1)2 — 2хт) = 03. 11.
б) Хл„„=Хр Хл„', в) Хт =Щх-'у); г) Х!(х,у) =ьИ!х — У[. 12. Х(х) = вя([,р(х) — фх)/). 298 14. Характеристические функции этих предикатов: а) зя(~,'.„отр(х„..., х„, 1)); П,'о(Хр(х~, —, х.. 1)) 15 б) <Р(хь -, х.) = Л Хр, + ... + Л тр„. Заметим, что это соотношение определяет 9 и в том случае, когда ни один из Р„ ..., Р, не истинен: в этом случае ~р равно нулю. 19. ~(х) = ру[х + 1 + у = О). 21. Все примитивно рекурсивные функции всюду определены, а среди частично рекурсивных функций встречаются и функции не всюду определенные, например функции, рассмотренные в задаче 17, а — г.
$14 2. а) ИасЫсс; б) ИасЬаа; в) БЬасЬаЬс; г) йИсЬаЬс; д) ИайаБс; е) ИасЬ; ж) ИаЬс; з) с1сЬаЬс; и) г1асйЬаЬс; к) ИасааЬс; л) ИЫсЬаЬс. 3. а) сБг1ссс1ас; б) сЬаадас; в) не применима; г) сЬаЬсИс; д) ааЬсгГас; е) сЫас; ж) Ьсйас; з) сЬаЬсс; и) сЬаБсасд; к) сааЬсйае' л) сЬЫЬсИас. 5. а) асаасаасааса; б) ЬЬаЬЬаЬЬаЬЬа; в) ЬсЬссЬссЬсса; г) саасаасаасаа; д) ЬаЬЬаЬЬаЬЬаЬ; е) Ьса; ж) Л; з) Ьса; и) Ьса; к) саса; л) ЬсЬЬсЬЬсЬЬсЬ.
6. а) саасаасаасаа; б) ЬаЬЬаЬЬаЬЬаЬ; в) сЬссЬссЬссБс; г) сасаасаасааЬ; д) аЬЬаЬЬаЬЬаЬЬ; е) саЬ; ж) саЬ; з) Л; и) саЬ; к) саса; л) сЬЬсЬЬсЬЬсЬЬ. 7. а) асс)асБа, ИасЫс, сБйсас; б) ааИасЬа, ИасЬаа, сЬаас(ас; в) аЬсЬЬасЬа, ЬЬасЬаЬс, не применима; г) аЬсс(ИсЬа, ИйсБаЬс, сЬаЬсИс; д) аЬсИайа, ИайаЬс, г1аЬсг1ас; е) ИасЬа, ИасЬ, сЬаас; ж) аЬсИа, ИаЬс, Ьсг1ас; з) аЬсасЬа, с1сЬаБс, сЬаЬсс; и) аЬсасИЬа, асааЬаЬс, сЬаЬсаса; к) аасИасаа, ааасааас, сааасаас; л) Ьс1ЬсИЬс1сЬЫ, ИЬс1сЬЬаЬс, сЬЫЬсг(Ьс1с.
9. а) Л; б) Л; в) 1; г) Л; д) 1; е) 1; ж) 1; з) 1; и) Л; к) 1; л) 1. 10. а) аа; б) а; в) Л; г) не применим; д) не применим; е) а; ж) ааа; з) Л; и) Л; к) Ь. Данный алгоритм каждое слово в алфавите А = (а, Ь) перерабатывает либо в слово, состоящее лишь из одних букв а (их число равно разности чисел букв а и букв Ь в данном слове, если эта разность положительна), либо в слово, состоящее лишь из одних букв Ь (их число равно разности чисел букв Ь и букв а в данном слове, если эта разность положительна), либо в пустое слово (если число букв а в данном слове равно числу букв Ь в нем).
13. а) Ьаа; б) ааа; в) ааа; г) ааа; д) ЬБЬЬ; е) ааа; ж) а; з) аа; и) ЬЬааа; к) аа. 299 14. а) ЬЬЬ; б) ЬЬЬ; в) ЬЬЬЬ; г) Л; д) ЬЬЬЬЬ; е) ЬЬЬ; ж) ЬЬЬЬЬ; з) ЬЬ; и) ЬЬЬ; к) ЬЬЬЬ; л) ЬЬЬЬ. Алгоритм «извлекает» из слова все буквы Ь, если они там есть, и выдает Л, если в слове этих букв нет. 15. а) ЬЬ; б) ЬЬЬЬ; в) ЬЬЬ; г) не применим; д) ЬЬЬЬ; е) ЬЬ; ж) ЬЬЬЬЬ„ з) Ь; и) ЬЬЬЬЬ; к) ЬЬЬЬ; л) ЬЬЬ. 16. а) а; б) Ьаааа; в) Ьаа; г) Ьаааа; д) ЬЬ; е) Ьааа; ж) Ьаа; з) Ьаа; и) Ьааа; к) Ьааа; л) Ьааа. 18.
а) ЬЬ; б) Ь; в) ЬЬ; г) Ь; д) ЬЬ; е) Ь; ж) Ь; з) ЬЬ; и) Ь; к) Ь; л) ЬЬ. 19. а) ИссЬ; б) ИсЬ; в) ЬЫс; г) ЬЫсЬ; д) ИсЬЬ; е) йсЬ; ж) ИссЬ; 3) Ььсй; и) с3сЬЬ; к) Ььйс. 21. а) ~(х) = х„б) нигде не определенную функцию. СПИСОК ЛИТЕРАТУРЫ 1. Байиф Ж -К Логические задачи: Пер. с фр. — М., 1983. 2. Бизан Д., Герцег Я. Игра и логика (85 логических задач): Пер. с венг.
— М., 1975. 3. БизамД., Герцег Я. Многоцветная логика (175 задач): Пер. с венг.— М., 1978. 4. Гаврилов Г П., СапоженкоА А. Сборник задач по дискретной математике. — М., 1977. 5. Гиндикин С.Г. Алгебра логики в задачах. — М., 1972. 6. Гохиан А.В., Спивак М.А., Розен В.В. Сборник задач по математической логике и алгебре множеств. — Саратов, 1969. 7. Драбкина М.Е. Логические упражнения по элементарной математике. — Минск, 1965. 8.
Игошин В.И. Математическая логика и теория алгоритмов. — Саратов, 1991. 9. Игошин В.И. Задачник-практикум по математической логике. — М., 1986. 10. Игошин В.И. Тетрадь по математической логике с печатной основой. — Саратов, 1996; 1999. 11. Касаткин В.Й., ВерланьА. Ф., Переход И.А. Элементы кибернетики — школьнику: Сборник упражнений и задач. — Киев, 1974.
12. Коррова Л. История с узелками: Пер.'с англ. — М., 1973. 13. Коррова Л. Логическая игра: Пер. с англ. — М., 1991. 14. Лавров И.А., Максимова Л Л. Задачи по теории множеств, математической логике и теории алгоритмов. — М., 1975. 15. Ликтарников Л.М., Сукачева Т. Г.
Математическая логика: Курс лекций. Задачник-практикум и решения. — СПб., 1999. 16. Математическая логика / Под ред. А.А. Столяра. — Минск, 1991. 17. Мельников В.Н. Логические задачи. — Киев; Одесса, 1989. 18. Михайлов А.В., Рыжова Н.И., Швецкий М.В. Упражнения по основам математической логики.
— СПб., 1998. 19. Рыжова Н.И., Швецкий М.В. Упражнения по основам формальной символической логики. — СПб., 1998. 20. Смаллиан Р.М. Принцесса или тигр?: Пер. с англ. — М., 1985. 21. Шапиро С. И. Решение логических и игровых задач. — М., 1984. 22.
Шевченко В.Е. Некоторые способы решения логических задач.— Киев, 1979. ОГЛАВЛЕНИЕ Предисловие Гл а в а 1. АЛГЕБРА ВЫСКАЗЫВАНИЙ б 1. Основные понятия алгебры высказываний ........,..............,......, 6 Высказывания и операции над ними (6). Формулы алгебры высказываний (15). Тавтологии алгебры высказываний (20). Логическое следование (24). Равносильность формул (33). Упрощение систем высказываний (39). б 2. Нормальные формы для формул алгебры высказываний и нх применение ...40 Отыскание нормальных форм (41).
Применение нормальных форм (47). Нахождение следствий из посылок (57). Нахождение посылок для данных следствий (62). б 3. Приложение алгебры высказываний к логнко-математической практике ...68 Обратная и противоположная теоремы (68). Принцип полной дизъюнкции (75). Необходимые и достаточные условия (76). Упрощение систем высказываний (81). Правильные и неправильные рассуждения (82). Нахождение всех следствий из посылок (85). Нахождение посылок лля следствий (87). «Логические» задачи (88). 92 Глава П. БУЛЕВЫ ФУНКЦИИ б 4.
Понятие булевой функции и свойства булевых функций ........... 92 Число булевых функций (93). Равенство булевых функций (96). Свойства булевых функций (98). б 5. Специальные классы булевых функций .....................................101 Полиномы Жегалкина и линейные булевы функции (1О1). Двойственность и самодвойственные булевы функции (107).
Монотонные булевы функции (113). Булевы функции, сохраняющие нуль и сохраняющие единицу (120). б б. Полные системы и функционально замкяутые классы булевых функций . . 123 Полные и неполные системы булевых функций (123). Применение теоремы Поста (125). Функционально замкнутые классы булевых функций (127). Базисы булевых функций (128). б 7.
Примеаенне булевых фуикцай к релейно-контактным схемам .130 Анализ релейно-контактных схем (130), Синтез релейно-контактных схем (138). 302 Глава П1. ФОРМАЛИЗОВАННОЕ ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ .143 0 8. Построение формализованного исчисления высказываний и исследование сястемы акском на независимость .......................... 143 Построение выводов из аксиом (144). Построение выводов из гипотез (!46). Теорема о дедукции и ее применение (150). Производные правила вывода и их применение (154). Независимость системы аксиом (! 57).
Глава 1У. ЛОГИКАПРЩИКАТОВ ... ... 162 0 9. Основные понятия логики предпкатов ....................................... 162 Понятие предиката и операции нал предикатами (162). Множество истинности предиката (167). Равносильность и следование предикатов (179). формулы логики предикатов, их интерпретация и классификация (182). Равносильность формул логики предикатов (188).
Тавтологии логики предикатов (!91). Равносильные преобразования формул (195). Проблемы разрешимости для общезначимости и выполнимости формул (197). Логическое следование формул логики предикатов (200). 0 10. Применение логики предикатов к логико-математической практике . 204 Записи на языке логики предикатов (204). Правильные и неправильные рассуждения (208). Логика предикатов и алгебра множеств (2!О). Равносильные преобразования неравенств и уравнений при их решении (212). 0 П. Формализованное исчисление предккатов ...............................
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
