Конспекты лекций по математической логике
1.1 Различные подходы к определению алгоритма:
1 0 . Неформальное понятие алгоритма (последовательность инструкций для выполнения действия).
2 0 . Машина с неограниченными регистрами (МНР).
3 0 Машина Тьюринга – Поста (МТ-П).
4 0 Нормальные алгоритмы Маркова (НАМ).
1.1.1 Машина с неограниченными регистрами (МНР).
Имеется некое устройство, в котором счетное число ячеек памяти (регистров), в которых хранятся целые числа.
Допустимые команды:
Z(n) - обнуление регистра R n .
S(n) - увеличение числа в регистре R n на 1.
T(m,n) - копирует содержимое R m в регистор R n .
I(p,q,n) - если содержимое R p = R q то выполняется команда с номером n , если нет
следующая.
Программа для МНР должна быть последовательностью команд Z, S, T, I с определенным порядком, выполняемые последовательно.
Тезис Черча (Churcha) : Первое и второе определение алгоритма эквивалентны между собой. Любой неформальный алгоритм может быть представлен в программе для МНР.
Имеется устройство просматривающее бесконечную ленту, где есть ячейки содержащие элементы алфавита:
, где
- пустой символ (пустое слово), который может принадлежать и не принадлежать
А
. Также существует управляющая головка (устройство) (УУ)/(УГ), которая в начальный момент расположена в определенном месте, в состоянии
. Также существуют внутренние состояния машины:
Слово в данном алфавите - любая конечная упорядоченная последовательность букв данного алфавита, притом длина слова это количество букв в нем (у пустого слова длина 0).
Допустимые команды:
|
1)
2)
|
Последовательность команд называется программой , если в этой последовательности не встречается команд с одинаковыми левыми частями. Машина останавливается если она не находит команды с левой частью подобной текущей. |
1.1.3 Нормальные алгоритмы Маркова.
Тип машины перерабатывающий слова, в которой существует некий алфавит
, для которого W - множество всех слов.
Допустимые команды: (Для машин этого типа важна последовательность команд.)
|
|
Пример:
Программа:
|
1.1.4 Реализация функции натурального переменного.
но мы допускаем не всюду определенную функцию.
притом
, если
f
не определена, то и программа не должна ничего выдавать.
притом
, если
f
не определена, то и программа не должна ничего выдавать.
(
, а числа представляются в виде
,например
.)
1.2 Эквивалентность трех подходов к понятию алгоритм.
1.2.1 Теорема об эквивалентности понятия вычислимой функции.
)
Использование НАМ:
Пусть
которая вычисляется на МТ-П, вычислим её на НАМ.
МТ-П:
НАМ:
Команда МТП:
преобразуется по правилам:
Команда МТП:
2. Булевы функции.
2.1 Основные определения
2.1.1 Декартово произведение
Пример
:
2.1.2 Декартова степень произвольного множества.
Опр
:
- множество всевозможных упорядоченных наборов длины n , элементов множества А.
2.1.3 Определение булевой функции от n переменных.
Любое отображение
- называется булевой функцией от n переменных, притом множество
2.1.4 Примеры булевой функции.
2.1.5 Основные булевы тождества.
2.2 Дизъюнктивные нормальные формы.
2.2.1 Основные определения.
Рассмотрим слово:
Экспоненциальные обозначения:
- элемент конъюнкции.
S – длина элемента конъюнкции.
ДНФ – дизъюнкция нескольких различных элементарных конъюнкций.
Любая булева функция может быть представлена как ДНФ
2.2.2 Теорема о совершенной ДНФ.
Любая булева функция
тождественно не равная 0 может быть разложена в ДНФ следующего вида:
Опр
: Носитель булевой функции
.
Лемма
:
это элементарно
возьмем набор
а)
б)
Доказательство:
, будем доказывать, что
.
. Возьмем
он попадает в число суммируемых наборов и по нему будет проводиться сумирование.
. Возьмем другой набор из
Следовательно
2.2.3 Некоторые другие виды ДНФ.
Опр:
- называется
минимальной ДНФ
, если она имеет
- наименьшую возможную длину из всех ДНФ данной функции.
Опр:
- называется
тупиковой ДНФ
, если из неё нельзя выбросить ни одного слагаемого с сохранением булевой функции.
(Легко понять, что любая минимальная ДНФ является тупиковой, а обратное не верно.)
Опр:
К-мерной гранью
называется такое подмножество
, которая является носителем некоторой элементарной конъюнкции длины: n-k.
Опр: Предположим дана функция
и есть
. Грань называется
отмеченной
, если она целиком содержится в носителе
Т
.
Опр: Максимальная грань – это такая грань, которая не содержится ни в какой грани более высокой размерности.
Предложение: Любую отмеченную грань можно вложить в максимальную грань.
Предложение:
(Носитель любой функции можно разложить в объединение нескольких граней разной размерностей)
Предложение: Носитель любой функции разлагается в объединение всех своих максимальных граней.
Опр: Элементарная конъюнкция называется минимальной , если её носитель является максимальной гранью. Следовательно всякая булева функция разлагается в дизъюнкцию всех своих элементарных конъюнкций.
Опр: Сокращенная ДНФ – разложение данной булевой функции в соответствующие ДНФ, которые соответствуют объединению её максимальных граней.
Теор: Минимальная ДНФ может быть получена из сокращенной отбрасыванием некоторого количества слагаемых, возможно пустого.
3 Логические Исчисления.
3.1 Исчисления высказывания (ИВ).
3.1.1 Определения.
Опр: V – словом в алфавите А , называется любая конечная упорядоченная последовательность его букв.
Опр:
Формативная последовательность слов
– конечная последовательность слов и высказываний
, если они имеют формат вида:
Опр: F – формулой ИВ , называется любое слово, входящее в какую-нибудь формативную последовательность.
Пример:
Опр:
Аксиомы
– специально выделенное подмножество формул.
Reg – правила вывода ИВ (некоторые правила преобразования первого слова в другое).
a
– символ переменной
- произвольное слово ИВ (формула)
Отображение
действует так, что на место каждого вхождения символа
а
, пишется слово
.
Пример:
Правило modus ponens
:
3.1.2 Формальный вывод.(простейшая модель доказательства теоремы)
Опр: Последовательность формул ИВ, называется формальным выводом, если каждая формула этой последовательности имеет следующий вид:
Опр: Выводимый формулой (теоремой) ИВ называется любая формула входящая в какой-нибудь формальный вывод.
- выводимая формула ИВ.
Пример:
|
1) |
|
|
|
2) |
|
|
|
3) |
|
|
|
4) |
|
|
|
5) |
|
|
|
6) |
|
|
Правило одновременной подстановки.
Замечание
: Если формула
выводима, то выводима и
Возьмем формативную последовательность вывода
и добавим в неё
, получившаяся последовательность является формальным выводом.
(Если выводима
то если
, то выводима
)
Теор: Если выводимая формула
, то
(
- различные символы переменных) выводима
Выберем
- символы переменных которые различны между собой и не входят не в одну из формул
, сделаем подстановку
и последовательно применим
и в новом слове делаем последовательную подстановку:
, где
- является формальным выводом.
3.1.3 Формальный вывод из гипотез.
Опр: Формальным выводом из гипотез
(формулы), называется такая последовательность слов
, каждая из которых удовлетворяет условию:
если формулу
можно включить в некоторый формальный вывод из гипотез
.
Лемма:
;
: то тогда
Напишем список:
Лемма
:
Док:
3.1.4 Теорема Дедукции.
Если из
, где
по правилу m.p.
2б)
- уже выводили
, ч.т.д.
Базис индукции: N=1
- формальный вывод из длинного списка
(только что доказано), осуществим переход по индукции:
по индукции
Пример:
по теореме дедукции
3.2 Критерий выводимости в ИВ.
3.2.1 Формулировка теоремы.
при любой интерпретации алфавита (символов переменных)
3.2.2 Понятие интерпретации.
символ переменной
переменную поставим в соответствие.
- проекция на
.
- только символ
переменных, т.к.
это заглавное слово
формативной последо-
вательности вида:
Где:
3.2.3 Доказательство теоремы.
формальный
вывод
3.3 Непротиворечивость ИВ.
3.3.1 Определение.
.
ИВ
противоречиво
.
ИВ непротиворечиво , если оно не является противоречивым.
Теорема : ИВ является непротиворечивым исчислением по отношению к любому из трех определений.
Док-во
: (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 Понятие квантора.
n – свободная переменная
4.3 Геометрическая интерпретация навешивания кванторов.
|
|
|
|
Пронесение отрицания через кванторы
Геометрическое 'доказательство':
целиком лежит в
ч.т.д.
,где
.
(остановка программы).
- ортогональная проекция на ось x
