|
|
|
|
Лекция: Математическая Логика
Лекция: Математическая Логика
Конспекты лекций по математической логике.
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 Реализация функции натурального переменного.
но мы допускаем не всюду определенную функцию.
![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_16_1.gif) ![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_17_1.gif) то это означает, что
притом , если f не определена, то и программа не должна ничего выдавать.
![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_21_1.gif) ![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_21_2.gif) ![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_23_1.gif) ![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_19_2.gif)
притом , если f не определена, то и программа не должна ничего выдавать.
( , а числа представляются в виде ,например .)
1.2 Эквивалентность трех подходов к понятию алгоритм.
1.2.1 Теорема об эквивалентности понятия вычислимой функции.
вычислима: ( )
1) Если существует программа МНР, которая вычисляет эту функцию.
2) Если существует программа МТ-П, которая вычисляет эту функцию.
3) Если существует программа НАМ, которая вычисляет эту функцию.
Использование НАМ:
Теор.: Классы функций
вычислимых на МТ-П, с помощью НАМ и с помощью МНР совпадают.
Пусть которая вычисляется на МТ-П, вычислим её на НАМ.
МТ-П: ![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_34_1.gif)
НАМ:
Команда МТП: преобразуется по правилам:
Команда МТП:
2. Булевы функции.
2.1 Основные определения
2.1.1 Декартово произведение
- мн-во всевозможных упорядоченных пар элементов из А и В.
Пример:
2.1.2 Декартова степень произвольного множества.
Опр: -
множество всевозможных упорядоченных наборов длины n , элементов множества А.
2.1.3 Определение булевой функции от n переменных.
Любое отображение -
называется булевой функцией от n переменных, притом множество
2.1.4 Примеры булевой функции.
1) ![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_51_1.gif) логическая сумма (дизъюнкция).
2) ![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_53_1.gif) логическое умножение (конъюнкция).
3) ![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_55_1.gif) сложение по модулю два.
4) ![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_57_1.gif) логическое следствие (импликация).
5) ![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_59_1.gif) отрицание.
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 Формальный вывод.(простейшая модель доказательства теоремы)
Опр: Последовательность формул ИВ, называется формальным выводом, если каждая
формула этой последовательности имеет следующий вид:
Опр: Выводимый формулой (теоремой) ИВ называется любая формула входящая в
какой-нибудь формальный вывод.
- выводимая формула ИВ.
Пример:
Правило одновременной подстановки.
Замечание: Если формула выводима, то выводима и
Возьмем формативную последовательность вывода
и добавим в неё ,
получившаяся последовательность является формальным выводом.
(Если выводима то если , то выводима )
Теор: Если выводимая формула , то ( - различные символы переменных) выводима
Выберем - символы
переменных которые различны между собой и не входят не в одну из формул
, сделаем подстановку
и последовательно применим
и в новом слове делаем последовательную подстановку:
, где - является
формальным выводом.
3.1.3 Формальный вывод из гипотез.
Опр: Формальным выводом из гипотез
(формулы), называется такая последовательность слов
, каждая из которых удовлетворяет условию:
если формулу можно включить в некоторый формальный вывод из гипотез .
Лемма: ; : то тогда
Напишем список:
Лемма:
Док:
3.1.4 Теорема Дедукции.
Если из
1) и 2а) , где по правилу m.p. , ч.т.д.
2б) - уже выводили , ч.т.д.
Базис индукции: N=1 - формальный вывод из длинного списка
(только что доказано), осуществим переход по индукции:
по индукции
и по лемме 2
Пример:
по теореме дедукции
3.2 Критерий выводимости в ИВ.
3.2.1 Формулировка теоремы.
- тавтология
при любой интерпретации алфавита (символов переменных)
3.2.2 Понятие интерпретации.
символ переменной переменную поставим в соответствие.
, где - проекция на .
![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_203_1.gif)
; - только символ
переменных, т.к.
это заглавное слово
формативной последо-
вательности вида:
Где:
3.2.3 Доказательство теоремы.
![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_208_1.gif)
формальный
вывод
(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 Геометрическая интерпретация навешивания кванторов.
![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_5_1.jpg)
| ![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_258_1.gif)
![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_259_1.gif)
![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_260_1.gif) - ортогональная проекция на ось x
| ![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_6_1.jpg)
![Лекция: Математическая Логика Лекция: Математическая Логика](/image/11341_262_1.gif)
|
Пронесение отрицания через кванторы
Геометрическое 'доказательство':
не обладает свойством, что прямая целиком лежит в
ч.т.д.
|
|
|
|
|