- •Ф.К. Алиев, и.А. Юров
- •Введение
- •Основные способы задания двоичных функций
- •1.1. Табличный способ задания
- •1.2. Геометрический способ задания
- •1.3. Задание двоичных функций формулами
- •Основные способы задания двоичных функций (продолжение)
- •2.1. Нормальные формы двоичных функций
- •2.2. Многочлен Жегалкина и действительный многочлен двоичной функции
- •2.3. Теорема о разложении в ряд Фурье
- •Полнота и замкнутость. Критерий полноты системы. Функционально полные системы. Замкнутые классы булевых функций
- •3.1. Полнота и замкнутость. Функционально полные системы
- •3.2. Замкнутые классы булевых функций
- •3.3. Критерий полноты системы булевых функций
- •4.1. Псевдобулевы функции
- •4.2. Функции k-значной логики
- •5.1 Минимизация двоичных функции
- •5.2. Геометрическая интерпретация минимизации днф
- •6.1. Метод Квайна — Мак-Класки нахождения сокращённой днф двоичной функции
- •6.2. Метод нахождения тупиковых днф
- •6.3. Метод Петрика нахождения тупиковых днф
- •Алгебраические системы
- •7.1. Алгебраические системы. Булевы алгебры
- •7.2. Изоморфизм алгебраических систем
- •Алгебры высказываний. Предикаты и операции над ними
- •8.1. Основные логические операции и их свойства
- •8.2. Предикаты и операции над ними
- •Исчисление предикатов
- •9.1. Общее понятие о логическом исчислении
- •9.2. Формулы алгебры предикатов
- •9.3. Равносильность формул. Основные отношения равносильности
- •9.4. Использование равносильностей для упрощения формул
- •9.5. Построение исчисления предикатов
- •9.6. Выводимость и доказуемость формул
- •9.7. Семантика исчисления предикатов
- •Понятие о теории моделей
- •Элементы теории алгоритмов
- •11.1. Основные требования к алгоритмам
- •11.2. Машина Тьюринга и функции, вычислимые по Тьюрингу
- •11.3. Машины произвольного доступа и вычислимые функции
- •Частично рекурсивные функции и их вычислимость
- •Вычислимость суперпозиции
- •Вычислимость рекурсии
- •Вычислимость минимизации
- •Нумерация наборов чисел и слов
- •Нормальные алгоритмы
- •Нумерация алгоритмов
- •1. Нумерация машин Тьюринга
- •2. Нумерация мпд-программ
- •Универсальные функции
- •Алгоритмически неразрешимые проблемы
- •16.1. Алгоритмически неразрешимые проблемы
- •16.2. Примечательные алгоритмически неразрешимые проблемы
- •Характеристики сложности вычислений
- •Характеристика сложности вычислительных задач
- •18.1. Классы сложности p и np и их взаимосвязь
- •18.3. Основные np-полные задачи. Сильная np-полнота
- •Список Литературы
Нумерация наборов чисел и слов
В теории алгоритмов получил распространение прием, позволяющий сводить изучение функций от нескольких переменных к изучению функций одной переменной. Он основан на нумерации наборов чисел так, что имеется биективное соответствие между наборами чисел и их номерами, причем функции, определяющие по набору чисел его номер и по номеру сам набор чисел являются общерекурсивными.
Рассмотрим сначала множество — множество пар натуральных чисел. Рассмотрим следующее упорядочение этих пар, называемойканторовским:
(0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), … (13.1)
Здесь в порядке возрастания упорядочиваются пары (x, y) с условием x + y = n в виде последовательности
(0, n), (1, n – 1), …, (x, y), …, (n, 0). (13.2)
Пусть c(x, y) — номер пары (x, y) в последовательности (13.1), причем считаем c(0, 0) = 0. Если c(x, y) = n, то обозначим через r, l — функции, удовлетворяющие x = l(n), y = r(n) и, следовательно, c(l(n), r(n)) = n.
Покажем, что функции c, l, r в явном виде выражаются через обычные арифметические функции. Произвольная пара (x, y) находится на месте x + 1 в последовательности (13.2). Далее, перед последовательностью (13.2) находятся последовательности, отвечающие элементам (x, y) с условием x1 + y1 = t, где t = 0, 1, …, x + y – 1, и каждая из них содержит t + 1 элемент.
Следовательно, элемент (x, y) находится в последовательности (13.1) на месте 1 + 2 + … + x + y + x + 1. Поскольку нумерация начинается с нуля, то номер элемента (x, y) в последовательности (13.1) равен
. (13.3)
Пусть теперь c(x, y) = n и найдем x = l(n) и y = r(n). Из (13.3) следуют равенства:
;
;
.
Следовательно, или
.
Это означает, что
. (13.4)
Теперь, используя (13.3), определяем x:
.
Подставляя найденное значение x в (13.4), получаем y:
.
Заметим, что важен не сам вид полученных функций c(x, y), r(n), l(n), а важен факт их эффективной вычислимости.
Теперь с помощью нумерации пар чисел легко получить нумерацию троек чисел, т.е. элементов множества . Определим функцию. Тогда, если, тоz = r(n), y = r(l(n)), x = l(l(n)).
Аналогично, для наборов произвольной длины r + 1 полагаем
, , …,
…
и по определению называем число канторовским номеромn-ки . Если, тоxn = r(m), xn – 1 = r(l(m)), …, x2 = r(l(…l(m)), x1 = l(l(…l(m)).
Теперь, имея нумерацию множеств (k > 0), можно установить нумерацию множества . Положим для любого . Ясно, что с — биективное соответствие между М и N0. Кроме того, если , то,. Отсюда эффективно определяются.
Приведем еще одну нумерацию наборов чисел. Номер пары (x, y) зададим функцией
.
Ясно, что это общерекурсивная функция. При этом, если p(x, y) = n, то выполнено ,. Следовательно, для данной нумерации,.
Теперь, имея нумерационную функцию для пар чисел, аналогично предыдущему строим нумерационные функции для к-ок чисел и множества наборов .
Другую нумерацию множества М можно получить так. Пусть
.
Ясно, что — вычислима. Чтобы установить вычислимость, заметим, что каждое натуральное число имеет единственное представление в двоичной позиционной записи. Т.е. для любогоn можно эффективно и однозначно найти k > 0 и такое, что. Откуда получаем , где,(0 <i < k).
Рассмотрим теперь вопрос о нумерации слов в некотором алфавите и укажем некоторые из применяемых способов такой нумерации.
Пусть — конечный алфавит и пусть— множество всех слов конечной длины в алфавитеА, включая и пустое слово ^.
Алфавитная нумерация определяется следующим образом:
c(^) = 0, .
Поскольку при фиксированном r каждое положительное число n однозначно представимо в виде
, (0 < ij < r + 1),
то каждое число есть алфавитный номер одного и только одного слова из множества . Разложение (16) называетсяr-ичным разложением числа n с цифрами 1, …, r в отличии от обычного r-ичного разложения с коэффициентами 0, …, r – 1.
Нумерация слов через нумерационные функции. Пусть имеется счетный алфавит . Тогда нумерация слов определяется так:
v(^) = 0, ,
где функция определена выше. Ясно, что так определенная функция v является биективной и вычислимой.
Геделевская нумерация. Пусть имеем счетный алфавит . Определимгеделевы номера для каждой буквы . Теперь для каждого словаопределим геделев номер, где—k-е простое число. Кроме того, положим g(^) = 1. При этом геделев номер последовательности слов P0, P1, …, Pk определяется так: .
Рассмотрим теперь два применения нумерационных функций.
Утверждение 13.1. а) Функция f(x, y), отличная от нуля на конечном множестве пар из , общерекурсивна.
Доказательство. Действительно, пусть на парах чисели пусть имеет на них значенияz1, …, zt. На остальных пара f(x, y) = 0. Положим , где c — нумерационная функция Кантора.
Определим функцию g так: ,g(u) = 0 на остальных . Было выше показано, чтоg — общерекурсивна. По построению выполнено f(x, y) = g(c(x, y)) и поэтому f — общерекурсивна.
б) Определим сначала понятие совместной рекурсии. В схеме совместной рекурсии функция порождается с помощью нескольких функций.
Пусть для определенности даны функции ,, здесь. Тогда можно определить пару функцийипо рекурсии:
,
,
,
.
Утверждение 13.2. Если g1, g2, h1, h2 — общерекурсивные функции, то f1, f2 также общерекурсивны.
Доказательство. Определим функцию
,
где c — нумерационная функция Кантора. Тогда имеем: ,. Далее имеем
—
частично рекурсивная по условию.
т.е. функция получается по схеме обычной рекурсии с помощью функций
,
.
Значит функция — частично рекурсивная, а потому частично рекурсивны и функциии, что и требовалось доказать.
Л е к ц и я 14