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