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

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

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

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]