Конспекты лекций по математической логике.
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 Машина Тьюринга — Поста.
Имеется устройство просматривающее бесконечную ленту, где есть ячейки
содержащие элементы алфавита: [pic] , где [pic] — пустой символ (пустое
слово), который может принадлежать и не принадлежать А. Также существует
управляющая головка (устройство) (УУ)/(УГ), которая в начальный момент
расположена в определенном месте, в состоянии [pic]. Также существуют
внутренние состояния машины: [pic]
Слово в данном алфавите — любая конечная упорядоченная
последовательность букв данного алфавита, притом длина слова это
количество букв в нем (у пустого слова длина 0).
Допустимые команды:
|1) [pic] ,где [pic]. |Последовательность команд |
|2) [pic] (остановка программы). |называется программой, если в этой|
| |последовательности не встречается |
| |команд с одинаковыми левыми |
| |частями. Машина останавливается |
| |если она не находит команды с |
| |левой частью подобной текущей. |1.1.3 Нормальные алгоритмы Маркова.
Тип машины перерабатывающий слова, в которой существует некий алфавит
[pic], для которого W — множество всех слов.
Допустимые команды: (Для машин этого типа важна последовательность
команд.)
|[pic] где [pic] |Пример: [pic] [pic] |
| |Программа: [pic] |
| |[pic] |1.1.4 Реализация функции натурального переменного. [pic]
[pic] но мы допускаем не всюду определенную функцию.
[pic] то это означает, что [pic]
притом [pic], если f не определена, то и программа не должна ничего
выдавать.
[pic] [pic][pic][pic]
притом [pic], если f не определена, то и программа не должна ничего
выдавать.
([pic] , а числа представляются в виде [pic] ,например [pic] .)
1.2 Эквивалентность трех подходов к понятию алгоритм.1.2.1 Теорема об эквивалентности понятия вычислимой функции.
[pic] вычислима: ([pic])
1) Если существует программа МНР, которая вычисляет эту функцию.
2) Если существует программа МТ-П, которая вычисляет эту функцию.
3) Если существует программа НАМ, которая вычисляет эту функцию.Использование НАМ: [pic] [pic]
[pic] [pic]Теор.: Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР
совпадают.
Пусть [pic] которая вычисляется на МТ-П, вычислим её на НАМ.МТ-П: [pic]
НАМ: [pic]
Команда МТП: [pic] преобразуется по правилам:
[pic]
Команда МТП: [pic] [pic] [pic]2. Булевы функции.
2.1 Основные определения
2.1.1 Декартово произведение
[pic] — мн-во всевозможных упорядоченных пар элементов из А и В.
Пример: [pic]
[pic] [pic]
[pic]2.1.2 Декартова степень произвольного множества.
Опр: [pic] — множество всевозможных упорядоченных наборов длины n ,
элементов множества А. [pic]2.1.3 Определение булевой функции от n переменных.
Любое отображение [pic] — называется булевой функцией от n переменных,
притом множество [pic]
[pic]2.1.4 Примеры булевой функции.
1) [pic] логическая сумма (дизъюнкция).
2) [pic] логическое умножение (конъюнкция).
3) [pic] сложение по модулю два.
4) [pic] логическое следствие (импликация).
5) [pic] отрицание.2.1.5 Основные булевы тождества.
1) [pic] (ассоциативность)
2) [pic] (коммутативность)
3) [pic] (свойство нуля)
4) [pic] (закон поглощения для 1)
5) [pic] (ассоциативность)
6) [pic] (коммутативность)
7) [pic] (свойство нуля по умножению)
8) [pic] (свойство нейтральности 1 по умножению)
9) [pic] (дистрибутивность)
10) [pic] (дистрибутивность 2)
11) [pic] (закон поглощения)
12) [pic] ( Законы
13) [pic] де Моргана)
14) [pic] (закон снятия двойного отрицания)
15) [pic] (tertium non datur – третьего не дано)
16) [pic] (ассоциативность)
17) [pic]
18) [pic]
19) [pic]
20) [pic]
21) [pic] (Свойства
22) [pic] идемпотентности)2.2 Дизъюнктивные нормальные формы.
2.2.1 Основные определения.
[pic] — конечный алфавит из переменных.
Рассмотрим слово: [pic]
Экспоненциальные обозначения: [pic]
[pic] — элемент конъюнкции.
S – длина элемента конъюнкции.
ДНФ – дизъюнкция нескольких различных элементарных конъюнкций.
[pic]
Любая булева функция может быть представлена как ДНФ2.2.2 Теорема о совершенной ДНФ.
Любая булева функция [pic] тождественно не равная 0 может быть разложена
в ДНФ следующего вида:
[pic]Опр: Носитель булевой функции [pic]
[pic].
Лемма: [pic]
1) [pic] это элементарно [pic]
2) [pic] возьмем набор [pic]
а) [pic]
б) [pic]
Доказательство: [pic], будем доказывать, что[pic].
1) Докажем, что [pic]. Возьмем [pic] он попадает в число суммируемых
наборов и по нему будет проводиться сумирование.
[pic]
2) Докажем, что [pic]. Возьмем другой набор из [pic]
[pic]
Следовательно [pic]2.2.3 Некоторые другие виды ДНФ.
Опр: [pic] — называется минимальной ДНФ, если она имеет [pic] —
наименьшую возможную длину из всех ДНФ данной функции.Опр: [pic] — называется тупиковой ДНФ, если из неё нельзя выбросить ни
одного слагаемого с сохранением булевой функции.(Легко понять, что любая минимальная ДНФ является тупиковой, а обратное
не верно.)Опр: К-мерной гранью называется такое подмножество [pic], которая
является носителем некоторой элементарной конъюнкции длины: n-k.Опр: Предположим дана функция [pic] и есть [pic]. Грань называется
отмеченной, если она целиком содержится в носителе Т.Опр: Максимальная грань – это такая грань, которая не содержится ни в
какой грани более высокой размерности.Предложение: Любую отмеченную грань можно вложить в максимальную грань.
Предложение: [pic]
(Носитель любой функции можно разложить в объединение нескольких граней
разной размерностей)Предложение: Носитель любой функции разлагается в объединение всех своих
максимальных граней. [pic]Опр: Элементарная конъюнкция называется минимальной, если её носитель
является максимальной гранью. Следовательно всякая булева функция
разлагается в дизъюнкцию всех своих элементарных конъюнкций.Опр: Сокращенная ДНФ – разложение данной булевой функции в
соответствующие ДНФ, которые соответствуют объединению её максимальных
граней.Теор: Минимальная ДНФ может быть получена из сокращенной отбрасыванием
некоторого количества слагаемых, возможно пустого.3 Логические Исчисления.
3.1 Исчисления высказывания (ИВ).
3.1.1 Определения.
[pic]
[pic]
[pic]
Опр: V – словом в алфавите А, называется любая конечная упорядоченная
последовательность его букв.Опр: Формативная последовательность слов – конечная последовательность
слов и высказываний [pic], если они имеют формат вида:
[pic]
Опр: F – формулой ИВ, называется любое слово, входящее в какую-нибудь
формативную последовательность.Пример: [pic]
[pic] [pic]Опр: Аксиомы – специально выделенное подмножество формул. [pic]
1) [pic]
2) [pic]
3) [pic]
4) [pic]
5) [pic]
6) [pic]
7) [pic]
8) [pic]
9) [pic]
10) [pic]
11) [pic]Reg – правила вывода ИВ (некоторые правила преобразования первого слова в
другое).
a – символ переменной [pic]
[pic] — произвольное слово ИВ (формула)
Отображение [pic] действует так, что на место каждого вхождения символа а
, пишется слово [pic].
Пример: [pic]
Правило modus ponens: [pic] [pic]3.1.2 Формальный вывод.(простейшая модель доказательства теоремы)
Опр: Последовательность формул ИВ, называется формальным выводом, если
каждая формула этой последовательности имеет следующий вид:
[pic]
Опр: Выводимый формулой (теоремой) ИВ называется любая формула входящая в
какой-нибудь формальный вывод. [pic] — выводимая формула ИВ.Пример: [pic]
|1) |[pic] |[pic] |
|2) |[pic] |[pic] |
|3) |[pic] |[pic] |
|4) |[pic] |[pic] |
|5) |[pic] |[pic] |
|6) |[pic] |[pic] |Правило одновременной подстановки.
Замечание: Если формула [pic] выводима, то выводима и [pic]
Возьмем формативную последовательность вывода [pic] [pic] и добавим в неё
[pic], получившаяся последовательность является формальным выводом.
(Если выводима [pic] то если [pic] , то выводима [pic] )Теор: Если выводимая формула [pic], то [pic] ([pic] — различные символы
переменных) выводима
Выберем [pic] — символы переменных которые различны между собой и не
входят не в одну из формул [pic] , сделаем подстановку [pic] и
последовательно применим [pic] и в новом слове делаем последовательную
подстановку: [pic], где [pic] — является формальным выводом.3.1.3 Формальный вывод из гипотез.
Опр: Формальным выводом из гипотез [pic](формулы), называется такая
последовательность слов [pic], каждая из которых удовлетворяет условию:
[pic]
[pic] если формулу [pic] можно включить в некоторый формальный вывод из
гипотез [pic].
Лемма: [pic]; [pic]: то тогда [pic]
Напишем список:
[pic] [pic] [pic]
Лемма:[pic]
Док: [pic] [pic] [pic]3.1.4 Теорема Дедукции.
Если из
[pic] [pic]
1) и 2а) [pic], где [pic] [pic] по правилу m.p. [pic], ч.т.д.
2б) [pic] — уже выводили [pic], ч.т.д.Базис индукции: N=1 [pic] — формальный вывод из длинного списка [pic]
[pic] (только что доказано), осуществим переход по индукции:
[pic]
[pic] по индукции
[pic] и по лемме 2
[pic]
Пример: [pic]
[pic] по теореме дедукции [pic]3.2 Критерий выводимости в ИВ.
3.2.1 Формулировка теоремы.
[pic] — тавтология
при любой интерпретации алфавита (символов переменных)
[pic]3.2.2 Понятие интерпретации.
[pic]
символ переменной [pic] [pic] переменную поставим в соответствие.
[pic], где [pic] — проекция на [pic].
[pic]
; [pic] — только символ
переменных, т.к.
это заглавное слово
формативной последо-
вательности вида:Где: [pic]
3.2.3 Доказательство теоремы.
формальный
вывод [pic]1)
3.3 Непротиворечивость ИВ.
3.3.1 Определение.
1) ИВ противоречиво, если формула А выводима в нем. [pic].
2) [pic]формула выводима в ИВ)[pic]ИВ противоречиво.
3) [pic]ИВ противоречиво.
ИВ непротиворечиво, если оно не является противоречивым.Теорема: ИВ является непротиворечивым исчислением по отношению к любому
из трех определений.
Док-во: (1) Если [pic], то соответствующая ей булева функция будет
тождественно равна 1. [pic](2) Если любая формула выводима, то выводима и А, что соответствует
пункту 1.
(3) Пусть [pic] и [pic] [pic] — булева функция
[pic] — противоречие.3.4 Формальные исчисления.
Алфавит – конечное или счетное множество символов, возможно, разбитых на
группы. Алфавит должен быть упорядоченным множеством.
Слово – конечная упорядоченная последовательность символов алфавита, в
т.ч. пустое слово.
V – множество всех слов.Вычислимая функция от нескольких натуральных переменных [pic]
( f – может быть не всюду определенной )
f – называется вычислимой, если [pic] такая машина Тьюринга, которая её
вычисляет.[pic] — разрешимое множество, если характеристическая функция
[pic] — является вычислимой.
Множество [pic] называется перечислимым, если [pic] такая вычислимая
функция
[pic]
М — разрешимо [pic] М и N M перечислимы.
М – перечислимо [pic] М – область определения некоторой вычислимой
функции.
Множество всех формул F – некоторое разрешимое подмножество V.
Т – счетное множество, если [pic] его биективное отображение на V.
[pic] — обозначение счетного множества. ([pic] — алеф-нуль)Если [pic] и зафиксировано биективное и вычислимое отображение [pic]
(вычис.),
то L – ансамбль.
V – ансамбль (слова лексикографически упорядочены и занумерованы)Определение: В произвольном формальном исчислении: [pic] — множество всех
аксиом – разрешимое подмножество множества всех формул.
[pic]
Правило вывода:
[pic] ,при [pic] разрешимо. Для ИВ N=2.
Пример:
[pic] [pic] (пустое слово) , [pic]
[pic]
1 и 2 – формальные выводы.
3 – не является формальным выводом.4 Предикаты и кванторы.
4.1 Определение предиката.
[pic]
[pic] — высказывание, содержащее переменную.
[pic] — предметная область предиката.
[pic]Пусть А – множество объектов произвольной природы (предметная область
предиката).[pic]-местный предикат – произвольное отображение [pic] [pic]
Множество истинности данного предиката [pic]
[pic] —
— характеристическая
функция от x на множестве
А — совпадает
с предикатами[pic]
[pic]
[pic]4.2 Понятие квантора.
k – связанная переменная
n – свободная переменная[pic] t – свободная, x – связанная.
[pic] , a,b,y – свободные переменные, x – связанная.
[pic]
[pic]
[pic]
[pic] [pic]
[pic]4.3 Геометрическая интерпретация навешивания кванторов.
|[pic] |[pic] |[pic] |
| |[pic] |[pic] |
| |[pic][pic] — | |
| |ортогональная проекция | |
| |на ось x | |Пронесение отрицания через кванторы
[pic] [pic]
Геометрическое 'доказательство':
[pic] не обладает свойством, что прямая [pic] целиком лежит в [pic]
[pic]
[pic]
[pic] ч.т.д.[pic]
[pic]
————————
[pic][pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
?????????????????/?????????–??/?[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
