- •© Михеева е. А., 2016 © Ульяновский государственный университет, 2016 оглавление
- •Раздел 6. Элементы математической логики . . . . . . . . . . . . . . . . . . . . 9
- •Раздел 7. Ограниченно-детерминированные (автоматные) функции
- •Раздел 8. Вычислимые функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
- •Раздел 9. Теория кодирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
- •Раздел 6. Элементы математической логики Предисловие
- •Исчисление высказываний
- •Язык ив
- •Аксиомы ив
- •Формулы алгебры высказываний
- •Соответствие между формулами ав и ив
- •Непротиворечивость ив
- •Полнота ив
- •Логические операции над предикатами
- •Теорема о полноте системы одноместных предикатов, заданных на конечном множестве
- •Исчисление предикатов (ип)
- •Формулы исчисления предикатов
- •Определение формул
- •Замена переменных в формулах
- •Правила образования выводимых формул
- •Замена переменного предиката
- •Задания для самостоятельной работы
- •Раздел 7. Ограниченно-детерминированные (автоматные) функции
- •Детерминированные функции
- •Свойство детерминированной функции
- •Примеры детерминированных и недетерминированных функций
- •Способ задания д.Функций
- •Вес детерминированной функции
- •Ограниченно-детерминированные функции
- •Способы задания о.Д.Функций
- •Конечные автоматы
- •Задания для самостоятельной работы
- •Раздел 8. Вычислимые функции Машины Тьюринга
- •Пусть в некоторый момент головка машины обозревает символ , находясь в состоянии , тогда:
- •Методы построения машин Тьюринга
- •1. Принцип двойственности для программ (машин).
- •2. Последовательное подключение одной машины к другой.
- •3. Итерация машины.
- •4. Специальный операторный язык для записи алгоритмов.
- •Описание технологии программирования для машин Тьюринга
- •Вычислимые функции
- •Операции с, Пр и
- •Классы вычислимых и рекурсивных функций
- •Эквивалентность класса рекурсивных функций и функций, вычислимых на машинах Тьюринга
- •Задания для самостоятельной работы
- •Раздел 9. Теория кодирования Алфавитное кодирование
- •Критерий однозначности декодирования
- •Задания для самостоятельной работы
Способ задания д.Функций
Определение. Информационное бинарное дерево – это бесконечное ориентированное дерево:
у которого некоторая вершина
отмечена и называется корнем;и
з
каждой вершины
выходят ровно 2 ребра.
Все
слова множества
удобно задавать с помощью информационного
бинарного дерева, перенумеруя ребра:
левое - 0, правое – 1.
Но
нам надо еще указать значение функции.
Пусть
,
определяется последовательностью
,
где
Тогда для задания д.функции
с помощью информационного дерева нужно
у каждого ребра через запятую написать
значение соответствующей функции
следующим образом:
Таким
образом, если есть некоторая д.функция
,
то она однозначно задает некоторое
информационное дерево
и наоборот:
.
Рассмотрим примеры, взятые выше:
1.
2.
3.
Вес детерминированной функции
Обозначение:
Пусть имеется информационное дерево
с корнем
и некоторая вершина
.
Рассмотрев поддерево дерева
,
начиная от вершины
,
мы получим новое информационное дерево
.
Определение.
Пусть даны два информационных дерева
и
с корнями
и
соответственно,
которые являются поддеревьями
.
Тогда
,
если
,
т.е. 2 дерева эквивалентны, если они
задают одну и ту же функцию.
Свойство, следующее из предыдущего определения:
Если
,
тогда между этими информационными
деревьями существует изоморфизм,
который сохраняет пометки.
Определение
(ключевое).
Пусть
и
- ее информационное дерево. Тогда весом
д.функции
называется максимальное число попарно
неэквивалентных поддеревьев дерева
.
Вес д.функции
обозначим через
.
Рассмотрим в примерах, взятых выше, каков вес д.функций:
Здесь
,
т.к. любое поддерево этого дерева
эквивалентно самому дереву
.
Здесь аналогично примеру 1 .
Здесь
,
но
,
и какое бы мы поддерево не взяли, оно
будет эквивалентно либо
,
либо
,
значит,
.
Ограниченно-детерминированные функции
Определение. Ограниченно-детерминированной функцией (или о.д.функцией) называется такая д.функция, которая имеет конечный вес.
Множество
всех о.д.функций обозначим через
.
Из примеров 1 - 3, взятых выше, следует, что все три д.функции являются о.д.функциями.
Теперь приведем пример д.функции, не являющейся о.д.функцией.
Пример 6.
Рассмотрим
бесконечную периодическую последовательность
,
где
,
но
,
т.к. она бесконечна. Рассмотрим функцию
-
такое, что
.
Очевидно, что
есть д.функция. Она задает следующее
информационное дерево
:
Заметим,
что на всех ребрах одного уровня значения
функции одинаковы и они равны значению
соответствующей позиции бесконечной
периодической последовательности
.
Т.к. в последовательности
на каждом последующем шаге число нулей
увеличивается на 1, то в
попарно неэквивалентных поддеревьев
будет бесконечно много, т.е.
.
Пусть
,
,
имеет вес
,
т.е. в ее информационном дереве
можно найти
- попарно неэквивалентных поддеревьев.
Тогда для любого поддерева
дерева
,
что
,
где
