Математическая Логика (стр. 1 из 4)
Конспекты лекций по математической логике.
1. Теория алгоритмов
1.1 Различные подходы к определению алгоритма:
10. Неформальное понятие алгоритма (последовательность инструкций для выполнения действия).
20. Машина с неограниченными регистрами (МНР).
30 Машина Тьюринга – Поста (МТ-П).
40 Нормальные алгоритмы Маркова (НАМ).
1.1.1 Машина с неограниченными регистрами (МНР).
Имеется некое устройство, в котором счетное число ячеек памяти (регистров), в которых хранятся целые числа.Допустимые команды:
Z(n) - обнуление регистра Rn.
S(n) - увеличение числа в регистре Rnна 1.
T(m,n) - копирует содержимое Rm в регистор Rn.
I(p,q,n) - если содержимое Rp = Rq то выполняется команда с номером 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Теорема об эквивалентности понятия вычислимой функции.
вычислима: ( 
)1) Если существует программа МНР, которая вычисляет эту функцию.
2) Если существует программа МТ-П, которая вычисляет эту функцию.
3) Если существует программа НАМ, которая вычисляет эту функцию.
Использование НАМ:
Теор.: Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР совпадают.Пусть
которая вычисляется на МТ-П, вычислим её на НАМ.МТ-П:
НАМ:
Команда МТП:
преобразуется по правилам: 
Команда МТП:
2. Булевы функции.
2.1 Основные определения
2.1.1 Декартово произведение
- мн-во всевозможных упорядоченных пар элементов из А и В.Пример:
2.1.2 Декартова степень произвольного множества.
Опр:
- множество всевозможных упорядоченных наборов длины n , элементов множества А. 
2.1.3 Определение булевой функции от n переменных.
Любое отображение
- называется булевой функцией от n переменных, притом множество 
2.1.4 Примеры булевой функции.
1)
логическая сумма (дизъюнкция).2)
логическое умножение (конъюнкция).3)
сложение по модулю два.4)
логическое следствие (импликация).5)
отрицание.2.1.5 Основные булевы тождества.
1)
(ассоциативность)