Конспекты лекций по математической логике Теория алгоритмов 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 Теорема об эквивалентности понятия вычислимой функции. вычислима: ()
Если существует программа МНР, которая вычисляет эту функцию. Если существует программа МТ-П, которая вычисляет эту функцию. Если существует программа НАМ, которая вычисляет эту функцию. Использование НАМ:
Теор. : Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР совпадают. Пусть которая вычисляется на МТ-П, вычислим её на НАМ. МТ-П: НАМ: Команда МТП: преобразуется по правилам: Команда МТП: 2. Булевы функции. 2. 1 Основные определения 2. 1. 1 Декартово произведение - мн-во всевозможных упорядоченных пар элементов из А и В. Пример: 2. 1. 2 Декартова степень произвольного множества.
Опр: - множество всевозможных упорядоченных наборов длины n , элементов множества А. 2. 1. 3 Определение булевой функции от n переменных.
Любое отображение - называется булевой функцией от n переменных, притом множество 2. 1. 4 Примеры булевой функции. логическая сумма (дизъюнкция). логическое умножение (конъюнкция). сложение по модулю два. логическое следствие (импликация). отрицание. 2. 1. 5 Основные булевы тождества. (ассоциативность) (коммутативность) (свойство нуля) (закон поглощения для 1) (ассоциативность) (коммутативность) (свойство нуля по умножению) (свойство нейтральности 1 по умножению) (дистрибутивность) (дистрибутивность 2) (закон поглощения) ( Законы де Моргана) (закон снятия двойного отрицания) (tertium non datur – третьего не дано) (ассоциативность) (Свойства идемпотентности) 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 Пронесение отрицания через кванторы Геометрическое 'доказательство': не обладает свойством, что прямая целиком лежит в ч. т. д.