А.А. Вороненко, В.С. Федорова - Дискретная математика. Задачи и упражнения с решениями (1060726), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

Привести пример одноместной примитивно рекурсивной функции,из которой двукратным применением операции минимизации можно получить нигде не определённую функцию.J1. Всюду определённая функция f (x) в точке x = 0 принимаетзначение f (0). Тогда, применив операцию минимизации, получим,что µ(f (x))|x=0 = 0.1012. Если функция не определена в нуле, то применением к ней операции минимизации получим нигде не определённую функцию. Неопределённую в нуле функцию можно получить применением операции минимизации к любой функции, не принимающей значениеноль, например, f (x) = x + 1.IV.2.10(1, 4).

Обосновать вычислимость следующих функций:2· y)) −· (x + 1)3 ;· (x − sg(2x −1) f (x, y, z) =x+1x2 − y 2 (x3 +y)·sg(x−y·z)·4) f (x, y, z) =·2.z+1J Среди используемых функций есть две частично рекурсивные:x − y и xy . Частичная рекурсивность x − y обосновывалась выше (V.2.5(11)). Непосредственно убеждаемся, что xy = µx (x · y).Остальные используемые фукнции примитивно рекурсивны. I102Список литературы[1 ] Алексеев В. Б. Лекции по дискретной математике. Учебное пособие.

М.: Инфра-М, 2012.[2 ] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике М.: Физматлит, 2004.[3 ] Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986.103ОглавлениеЧасть 1. Курс «Дискретная математика» . . . .

. . . . . . . . . . .Занятие № 1.1. Функции алгебры логики. Формулы. Существенныеи фиктивные переменные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Занятие № 1.2. ДНФ, КНФ, СФЭ . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .Занятие № 1.3. Полиномы и линейные функции . . . . . . . . . . . . . . . . . . .Занятие № 1.4. Замкнутые классы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Занятие № 1.5. Класс М. Подсчёт числа функций . . . . . . . . . . . . . . . . .Занятие № 1.6. Полнота и шефферовость в алгебре логики . . . . . . .Занятие № 1.7. Графы: изоморфизм, связность . . . .

. . . . . . . . . . . . . . .Занятие № 1.8. Графы: деревья, гомеоморфизм . . . . . . . . . . . . . . . . . . .Занятие № 1.9. Графы: планарность, раскраски, орграфы . . . . . . . .Занятие № 1.10. Алфавитное кодирование. Оптимальные коды . . .Занятие № 1.11. Коды, исправляющие ошибки . . . . . . . . . . . . . . . . . . . .Занятие № 1.12. Автоматы. Часть 1 . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .Занятие № 1.13. Автоматы. Часть 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Часть 2. Курс «Дополнительные главы дискретнойматематики» . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .Занятие № 2.1. Элементарные функции многозначной логики.Представление функций в первой и второй формах . . . . . . . . . . . . . .Занятие № 2.2. Замкнутые классы. Представление функцийполиномами по модулю k . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Занятие № 2.3. Полнота систем функций многозначной логики . . .Занятие № 2.4. Исследование систем функций на полноту.Критерий Слупецкого . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.Занятие № 2.5. Задание детерминированных и ограниченнодетерминированных функций деревьями . . . . . . . . . . . . . . . . . . . . . . . . . .Занятие № 2.6. Представление ограниченно-детерминированныхфункций диаграммами Мура и каноническими уравнениями . . . . .Занятие № 2.7. Операции над ограниченно-детерминированнымифункциями . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Занятие № 2.8. Реализация ограниченно-детерминированныхфункций схемами. Полнота в множествах ограниченнодетерминированных функций . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .Занятие № 2.9. Простейшие свойства машин Тьюринга . . . . . . . . . . .Занятие № 2.10. Операции над машинами Тьюринга. Функции,вычислимые на машинах Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . .1043379131518202628323741455353556063666973828790Занятие № 2.11. Примитивно рекурсивные функции . . . . . . . . . . . . . . 94Занятие № 2.12. Частично рекурсивные функции . . . . . . . . . . . . . . . . . 98Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . 103105.

Характеристики

Список файлов книги