Главная » Каталог    
рефераты Разделы рефераты
рефераты
рефератыГлавная

рефератыБиология

рефератыБухгалтерский учет и аудит

рефератыВоенная кафедра

рефератыГеография

рефератыГеология

рефератыГрафология

рефератыДеньги и кредит

рефератыЕстествознание

рефератыЗоология

рефератыИнвестиции

рефератыИностранные языки

рефератыИскусство

рефератыИстория

рефератыКартография

рефератыКомпьютерные сети

рефератыКомпьютеры ЭВМ

рефератыКосметология

рефератыКультурология

рефератыЛитература

рефератыМаркетинг

рефератыМатематика

рефератыМашиностроение

рефератыМедицина

рефератыМенеджмент

рефератыМузыка

рефератыНаука и техника

рефератыПедагогика

рефератыПраво

рефератыПромышленность производство

рефератыРадиоэлектроника

рефератыРеклама

рефератыРефераты по геологии

рефератыМедицинские наукам

рефератыУправление

рефератыФизика

рефератыФилософия

рефератыФинансы

рефератыФотография

рефератыХимия

рефератыЭкономика

рефераты
рефераты Информация рефераты
рефераты
рефераты

Лекция: Математическая Логика

Конспекты лекций по математической логике. 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) Лекция: Математическая Логика (ассоциативность) 2) Лекция: Математическая Логика (коммутативность) 3) Лекция: Математическая Логика (свойство нуля) 4) Лекция: Математическая Логика (закон поглощения для 1) 5) Лекция: Математическая Логика (ассоциативность) 6) Лекция: Математическая Логика (коммутативность) 7) Лекция: Математическая Логика (свойство нуля по умножению) 8) Лекция: Математическая Логика (свойство нейтральности 1 по умножению) 9) Лекция: Математическая Логика (дистрибутивность) 10) Лекция: Математическая Логика (дистрибутивность 2) 11) Лекция: Математическая Логика (закон поглощения) 12) Лекция: Математическая Логика ( Законы 13) Лекция: Математическая Логика де Моргана) 14) Лекция: Математическая Логика (закон снятия двойного отрицания) 15) Лекция: Математическая Логика (tertium non datur – третьего не дано) 16) Лекция: Математическая Логика (ассоциативность) 17) Лекция: Математическая Логика 18) Лекция: Математическая Логика 19) Лекция: Математическая Логика 20) Лекция: Математическая Логика 21) Лекция: Математическая Логика (Свойства 22) Лекция: Математическая Логика идемпотентности) 2.2 Дизъюнктивные нормальные формы. 2.2.1 Основные определения. Лекция: Математическая Логика - конечный алфавит из переменных. Рассмотрим слово: Лекция: Математическая Логика Экспоненциальные обозначения: Лекция: Математическая Логика Лекция: Математическая Логика - элемент конъюнкции. S – длина элемента конъюнкции. ДНФ – дизъюнкция нескольких различных элементарных конъюнкций. Лекция: Математическая Логика Любая булева функция может быть представлена как ДНФ 2.2.2 Теорема о совершенной ДНФ. Любая булева функция Лекция: Математическая Логика тождественно не равная 0 может быть разложена в ДНФ следующего вида: Лекция: Математическая Логика Опр: Носитель булевой функции Лекция: Математическая Логика Лекция: Математическая Логика . Лемма: Лекция: Математическая Логика 1) Лекция: Математическая Логика это элементарно Лекция: Математическая Логика 2) Лекция: Математическая Логика возьмем набор Лекция: Математическая Логика а) Лекция: Математическая Логика б) Лекция: Математическая Логика Доказательство: Лекция: Математическая Логика , будем доказывать, чтоЛекция: Математическая Логика . 1) Докажем, что Лекция: Математическая Логика . Возьмем Лекция: Математическая Логика он попадает в число суммируемых наборов и по нему будет проводиться сумирование. Лекция: Математическая Логика 2) Докажем, что Лекция: Математическая Логика . Возьмем другой набор из Лекция: Математическая Логика Лекция: Математическая Логика Следовательно Лекция: Математическая Логика 2.2.3 Некоторые другие виды ДНФ. Опр: Лекция: Математическая Логика - называется минимальной ДНФ, если она имеет Лекция: Математическая Логика - наименьшую возможную длину из всех ДНФ данной функции. Опр: Лекция: Математическая Логика - называется тупиковой ДНФ, если из неё нельзя выбросить ни одного слагаемого с сохранением булевой функции. (Легко понять, что любая минимальная ДНФ является тупиковой, а обратное не верно.) Опр: К-мерной гранью называется такое подмножество Лекция: Математическая Логика , которая является носителем некоторой элементарной конъюнкции длины: n-k. Опр: Предположим дана функция Лекция: Математическая Логика и есть Лекция: Математическая Логика . Грань называется отмеченной, если она целиком содержится в носителе Т. Опр: Максимальная грань – это такая грань, которая не содержится ни в какой грани более высокой размерности. Предложение: Любую отмеченную грань можно вложить в максимальную грань. Предложение: Лекция: Математическая Логика (Носитель любой функции можно разложить в объединение нескольких граней разной размерностей) Предложение: Носитель любой функции разлагается в объединение всех своих максимальных граней. Лекция: Математическая Логика Опр: Элементарная конъюнкция называется минимальной, если её носитель является максимальной гранью. Следовательно всякая булева функция разлагается в дизъюнкцию всех своих элементарных конъюнкций. Опр: Сокращенная ДНФ – разложение данной булевой функции в соответствующие ДНФ, которые соответствуют объединению её максимальных граней. Теор: Минимальная ДНФ может быть получена из сокращенной отбрасыванием некоторого количества слагаемых, возможно пустого. 3 Логические Исчисления. 3.1 Исчисления высказывания (ИВ). 3.1.1 Определения. Лекция: Математическая Логика Лекция: Математическая Логика Лекция: Математическая Логика Опр: Vсловом в алфавите А, называется любая конечная упорядоченная последовательность его букв. Опр: Формативная последовательность слов – конечная последовательность слов и высказываний Лекция: Математическая Логика , если они имеют формат вида: Лекция: Математическая Логика Опр: F – формулой ИВ, называется любое слово, входящее в какую-нибудь формативную последовательность. Пример: Лекция: Математическая Логика Лекция: Математическая Логика Лекция: Математическая Логика Опр: Аксиомы – специально выделенное подмножество формул. Лекция: Математическая Логика 1) Лекция: Математическая Логика 2) Лекция: Математическая Логика 3) Лекция: Математическая Логика 4) Лекция: Математическая Логика 5) Лекция: Математическая Логика 6) Лекция: Математическая Логика 7) Лекция: Математическая Логика 8) Лекция: Математическая Логика 9) Лекция: Математическая Логика 10) Лекция: Математическая Логика 11) Лекция: Математическая Логика Reg – правила вывода ИВ (некоторые правила преобразования первого слова в другое). a – символ переменной Лекция: Математическая Логика Лекция: Математическая Логика - произвольное слово ИВ (формула) Отображение Лекция: Математическая Логика действует так, что на место каждого вхождения символа а , пишется слово Лекция: Математическая Логика . Пример: Лекция: Математическая Логика Правило modus ponens: Лекция: Математическая Логика Лекция: Математическая Логика 3.1.2 Формальный вывод.(простейшая модель доказательства теоремы) Опр: Последовательность формул ИВ, называется формальным выводом, если каждая формула этой последовательности имеет следующий вид: Лекция: Математическая Логика Опр: Выводимый формулой (теоремой) ИВ называется любая формула входящая в какой-нибудь формальный вывод. Лекция: Математическая Логика - выводимая формула ИВ. Пример: Лекция: Математическая Логика
1)

Лекция: Математическая Логика

Лекция: Математическая Логика

2)

Лекция: Математическая Логика

Лекция: Математическая Логика

3)

Лекция: Математическая Логика

Лекция: Математическая Логика

4)

Лекция: Математическая Логика

Лекция: Математическая Логика

5)

Лекция: Математическая Логика

Лекция: Математическая Логика

6)

Лекция: Математическая Логика

Лекция: Математическая Логика

Правило одновременной подстановки. Замечание: Если формула Лекция: Математическая Логика выводима, то выводима и Лекция: Математическая Логика Возьмем формативную последовательность вывода Лекция: Математическая Логика Лекция: Математическая Логика и добавим в неё Лекция: Математическая Логика , получившаяся последовательность является формальным выводом. (Если выводима Лекция: Математическая Логика то если Лекция: Математическая Логика , то выводима Лекция: Математическая Логика ) Теор: Если выводимая формула Лекция: Математическая Логика , то Лекция: Математическая Логика (Лекция: Математическая Логика - различные символы переменных) выводима Выберем Лекция: Математическая Логика - символы переменных которые различны между собой и не входят не в одну из формул Лекция: Математическая Логика , сделаем подстановку Лекция: Математическая Логика и последовательно применим Лекция: Математическая Логика и в новом слове делаем последовательную подстановку: Лекция: Математическая Логика , где Лекция: Математическая Логика - является формальным выводом. 3.1.3 Формальный вывод из гипотез. Опр: Формальным выводом из гипотез Лекция: Математическая Логика (формулы), называется такая последовательность слов Лекция: Математическая Логика , каждая из которых удовлетворяет условию: Лекция: Математическая Логика Лекция: Математическая Логика если формулу Лекция: Математическая Логика можно включить в некоторый формальный вывод из гипотез Лекция: Математическая Логика . Лемма: Лекция: Математическая Логика ; Лекция: Математическая Логика : то тогда Лекция: Математическая Логика Напишем список: Лекция: Математическая Логика Лекция: Математическая Логика Лекция: Математическая Логика Лемма: Лекция: Математическая Логика Док: Лекция: Математическая Логика Лекция: Математическая Логика Лекция: Математическая Логика 3.1.4 Теорема Дедукции. Если из Лекция: Математическая Логика Лекция: Математическая Логика 1) и 2а) Лекция: Математическая Логика , где Лекция: Математическая Логика Лекция: Математическая Логика по правилу m.p. Лекция: Математическая Логика , ч.т.д. 2б) Лекция: Математическая Логика - уже выводили Лекция: Математическая Логика , ч.т.д. Базис индукции: N=1 Лекция: Математическая Логика - формальный вывод из длинного списка Лекция: Математическая Логика Лекция: Математическая Логика (только что доказано), осуществим переход по индукции: Лекция: Математическая Логика Лекция: Математическая Логика по индукции Лекция: Математическая Логика и по лемме 2 Лекция: Математическая Логика Пример: Лекция: Математическая Логика Лекция: Математическая Логика по теореме дедукции Лекция: Математическая Логика 3.2 Критерий выводимости в ИВ. 3.2.1 Формулировка теоремы. Лекция: Математическая Логика - тавтология при любой интерпретации алфавита (символов переменных) Лекция: Математическая Логика 3.2.2 Понятие интерпретации. Лекция: Математическая Логика символ переменной Лекция: Математическая Логика Лекция: Математическая Логика переменную поставим в соответствие. Лекция: Математическая Логика , где Лекция: Математическая Логика - проекция на Лекция: Математическая Логика . Лекция: Математическая Логика Лекция: Математическая Логика Лекция: Математическая Логика ; Лекция: Математическая Логика - только символ переменных, т.к. это заглавное слово формативной последо- вательности вида: Где: Лекция: Математическая Логика 3.2.3 Доказательство теоремы. Лекция: Математическая Логика Лекция: Математическая Логика Лекция: Математическая Логика формальный вывод Лекция: Математическая Логика Лекция: Математическая Логика (1) Лекция: Математическая Логика 3.3 Непротиворечивость ИВ. 3.3.1 Определение. 1) ИВ противоречиво, если формула А выводима в нем. Лекция: Математическая Логика . 2) Лекция: Математическая Логика формула выводима в ИВ)Лекция: Математическая Логика ИВ противоречиво. 3) Лекция: Математическая Логика ИВ противоречиво. ИВ непротиворечиво, если оно не является противоречивым. Теорема: ИВ является непротиворечивым исчислением по отношению к любому из трех определений. Док-во: (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

Лекция: Математическая Логика

Лекция: Математическая Логика

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

Лекция: Математическая Логика Лекция: Математическая Логика Геометрическое 'доказательство': Лекция: Математическая Логика не обладает свойством, что прямая Лекция: Математическая Логика целиком лежит в Лекция: Математическая Логика Лекция: Математическая Логика Лекция: Математическая Логика Лекция: Математическая Логика ч.т.д. Лекция: Математическая Логика Лекция: Математическая Логика
рефераты Рекомендуем рефератырефераты

     
Рефераты @2011