20

1. Теория алгоритмов

1.1 Различные подходы к определению алгоритма

1⁰. Неформальное понятие алгоритма (последовательность инструкций для выполнения действия).

2⁰. Машина с неограниченными регистрами (МНР).

3⁰ Машина Тьюринга - Поста (МТ-П).

4⁰ Нормальные алгоритмы Маркова (НАМ).

1.1.1 Машина с неограниченными регистрами (МНР)

Имеется некое устройство, в котором счетное число ячеек памяти (регистров), в которых хранятся целые числа.

Допустимые команды:

Z(n) - обнуление регистра R_n.

S(n) - увеличение числа в регистре R_n на 1.

T(m,n) - копирует содержимое R_m в регистор R_n.

I(p,q,n) - если содержимое R_p = R_q то выполняется команда с номером n, если нет следующая.

Программа для МНР должна быть последовательностью команд Z, S, T, I с определенным порядком, выполняемые последовательно.

Тезис Черча (Churcha): Первое и второе определение алгоритма эквивалентны между собой. Любой неформальный алгоритм может быть представлен в программе для МНР.

1.1.2 Машина Тьюринга - Поста

Имеется устройство, просматривающее бесконечную ленту, где есть ячейки содержащие элементы алфавита: , где - пустой символ (пустое слово), который может принадлежать и не принадлежать А. Также существует управляющая головка (устройство) (УУ)/(УГ), которая в начальный момент расположена в определенном месте, в состоянии . Также существуют внутренние состояния машины:

Слово в данном алфавите - любая конечная упорядоченная последовательность букв данного алфавита, притом длина слова это количество букв в нем (у пустого слова длина 0).

Допустимые команды:

1) ,где . 2) (остановка программы).	Последовательность команд называется программой, если в этой последовательности не встречается команд с одинаковыми левыми частями. Машина останавливается если она не находит команды с левой частью подобной текущей.

1.1.3 Нормальные алгоритмы Маркова

Тип машины перерабатывающий слова, в которой существует некий алфавит , для которого W - множество всех слов.

Допустимые команды: (Для машин этого типа важна последовательность команд.)

где	Пример: Программа:

1.1.4 Реализация функции натурального переменного.

но мы допускаем не всюду определенную функцию.

то это означает, что

притом , если f не определена, то и программа не должна ничего выдавать.

притом , если f не определена, то и программа не должна ничего выдавать.

(, а числа представляются в виде ,например .)

1.2 Эквивалентность трех подходов к понятию алгоритм

1.2.1 Теорема об эквивалентности понятия вычислимой функции

вычислима: ()

Если существует программа МНР, которая вычисляет эту функцию.

Если существует программа МТ-П, которая вычисляет эту функцию.

Если существует программа НАМ, которая вычисляет эту функцию.

Использование НАМ:

Теор.: Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР совпадают.

Пусть которая вычисляется на МТ-П, вычислим её на НАМ.

МТ-П:

НАМ:

Команда МТП: преобразуется по правилам:

Команда МТП:

2. Булевы функции

2.1 Основные определения

2.1.1 Декартово произведение

- мн-во всевозможных упорядоченных пар элементов из А и В.

Пример:

2.1.2 Декартова степень произвольного множества

Опр: - множество всевозможных упорядоченных наборов длины n, элементов множества А.

2.1.3 Определение булевой функции от n переменных

Любое отображение - называется булевой функцией от n переменных, притом множество

2.2 Дизъюнктивные нормальные формы

2.2.1 Основные определения

- конечный алфавит из переменных.

Рассмотрим слово:

Экспоненциальные обозначения:

- элемент конъюнкции.

S - длина элемента конъюнкции.

ДНФ - дизъюнкция нескольких различных элементарных конъюнкций.

Любая булева функция может быть представлена как ДНФ

2.2.2 Теорема о совершенной ДНФ

Любая булева функция тождественно не равная 0 может быть разложена в ДНФ следующего вида:

Опр: Носитель булевой функции

.

Лемма:

это элементарно

возьмем набор

а)

б)

Доказательство: , будем доказывать, что.

Докажем, что . Возьмем он попадает в число суммируемых наборов и по нему будет проводиться сумирование.

Докажем, что . Возьмем другой набор из

Следовательно

2.2.3 Некоторые другие виды ДНФ

Опр: - называется минимальной ДНФ, если она имеет - наименьшую возможную длину из всех ДНФ данной функции.

Опр: - называется тупиковой ДНФ, если из неё нельзя выбросить ни одного слагаемого с сохранением булевой функции.

(Легко понять, что любая минимальная ДНФ является тупиковой, а обратное не верно.)

Опр: К-мерной гранью называется такое подмножество , которая является носителем некоторой элементарной конъюнкции длины: n-k.

Опр: Предположим дана функция и есть . Грань называется отмеченной, если она целиком содержится в носителе Т.

Опр: Максимальная грань - это такая грань, которая не содержится ни в какой грани более высокой размерности.

Предложение: Любую отмеченную грань можно вложить в максимальную грань.

Предложение:

(Носитель любой функции можно разложить в объединение нескольких граней разной размерностей)

Предложение: Носитель любой функции разлагается в объединение всех своих максимальных граней.

Опр: Элементарная конъюнкция называется минимальной, если её носитель является максимальной гранью. Следовательно всякая булева функция разлагается в дизъюнкцию всех своих элементарных конъюнкций.

Опр: Сокращенная ДНФ - разложение данной булевой функции в соответствующие ДНФ, которые соответствуют объединению её максимальных граней.

Теор: Минимальная ДНФ может быть получена из сокращенной отбрасыванием некоторого количества слагаемых, возможно пустого.

3 Логические исчисления

3.1 Исчисления высказывания (ИВ)

3.1.1 Определения

Опр: V - словом в алфавите А, называется любая конечная упорядоченная последовательность его букв.

Опр: Формативная последовательность слов - конечная последовательность слов и высказываний , если они имеют формат вида:

Опр: F - формулой ИВ, называется любое слово, входящее в какую-нибудь формативную последовательность.

Пример:

Опр: Аксиомы - специально выделенное подмножество формул.

Reg - правила вывода ИВ (некоторые правила преобразования первого слова в другое).

a - символ переменной

- произвольное слово ИВ (формула)

Отображение действует так, что на место каждого вхождения символа а, пишется слово .

Пример:

Правило modus ponens:

3.1.2 Формальный вывод (простейшая модель доказательства теоремы)

Опр: Последовательность формул ИВ, называется формальным выводом, если каждая формула этой последовательности имеет следующий вид:

Опр: Выводимый формулой (теоремой) ИВ называется любая формула входящая в какой-нибудь формальный вывод. - выводимая формула ИВ.

Пример:

1)
2)
3)
4)
5)
6)

Правило одновременной подстановки.

Замечание: Если формула выводима, то выводима и

Возьмем формативную последовательность вывода и добавим в неё , получившаяся последовательность является формальным выводом.

(Если выводима то если , то выводима )

Теор: Если выводимая формула , то ( - различные символы переменных) выводима

Выберем - символы переменных которые различны между собой и не входят не в одну из формул , сделаем подстановку и последовательно применим и в новом слове делаем последовательную подстановку: , где - является формальным выводом.

3.1.3 Формальный вывод из гипотез

Опр: Формальным выводом из гипотез (формулы), называется такая последовательность слов , каждая из которых удовлетворяет условию:

если формулу можно включить в некоторый формальный вывод из гипотез .

Лемма: ; : то тогда

Напишем список:

Лемма:

Док:

3.1.4 Теорема дедукции

Если из

и 2а) , где по правилу m.p. , ч.т.д.

2б) - уже выводили , ч.т.д.

Базис индукции: N=1 - формальный вывод из длинного списка

(только что доказано), осуществим переход по индукции:

по индукции

и по лемме 2

Пример:

по теореме дедукции

3.2 Критерий выводимости в ИВ

3.2.1 Формулировка теоремы

- тавтология

при любой интерпретации алфавита (символов переменных)

3.2.2 Понятие интерпретации

символ переменной переменную поставим в соответствие.

, где - проекция на .

; - только символ

переменных, т. к.

это заглавное слово

формативной последовательности вида:

Где:

3.2.3 Доказательство теоремы

формальный вывод

3.3 Непротиворечивость ИВ

3.3.1 Определение

ИВ противоречиво, если формула А выводима в нем. .

формула выводима в ИВ)ИВ противоречиво.

ИВ противоречиво.

ИВ непротиворечиво, если оно не является противоречивым.

Теорема: ИВ является непротиворечивым исчислением по отношению к любому из трех определений.

Док-во: (1) Если , то соответствующая ей булева функция будет тождественно равна 1.

(2) Если любая формула выводима, то выводима и А, что соответствует пункту 1.

(3) Пусть и - булева функция

- противоречие.

3.4 Формальные исчисления

Алфавит - конечное или счетное множество символов, возможно, разбитых на группы. Алфавит должен быть упорядоченным множеством.

Слово - конечная упорядоченная последовательность символов алфавита, в т.ч. пустое слово.

V - множество всех слов.

Вычислимая функция от нескольких натуральных переменных

(f - может быть не всюду определенной)

f - называется вычислимой, если такая машина Тьюринга, которая её вычисляет.

- разрешимое множество, если характеристическая функция

- является вычислимой.

Множество называется перечислимым, если такая вычислимая функция

М - разрешимо М и N \M перечислимы.

М - перечислимо М - область определения некоторой вычислимой функции.

Множество всех формул F - некоторое разрешимое подмножество V.

Т - счетное множество, если его биективное отображение на V.

- обозначение счетного множества. ( - алеф-нуль)

Если и зафиксировано биективное и вычислимое отображение (вычис.),

то L - ансамбль.

V - ансамбль (слова лексикографически упорядочены и занумерованы)

Определение: В произвольном формальном исчислении: - множество всех аксиом - разрешимое подмножество множества всех формул.

Правило вывода:

,при разрешимо. Для ИВ N=2.

Пример:

(пустое слово),

1 и 2 - формальные выводы.

3 - не является формальным выводом.

4. Предикаты и кванторы

4.1 Определение предиката

- высказывание, содержащее переменную.

- предметная область предиката.

Пусть А - множество объектов произвольной природы (предметная область предиката).

-местный предикат - произвольное отображение

Множество истинности данного предиката

-

- характеристическая

функция от x на множестве

А - совпадает

с предикатами

4.2 Понятие квантора

k - связанная переменная

n - свободная переменная

t - свободная, x - связанная.

, a,b,y - свободные переменные, x - связанная.

4.3 Геометрическая интерпретация навешивания кванторов

	- ортогональная проекция на ось x

Пронесение отрицания через кванторы

Геометрическое 'доказательство':

не обладает свойством, что прямая целиком лежит в

ч.т.д.