Конспекты лекций по математической логике.

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]