Конспекты лекций по математической логике.
Теория алгоритмов
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.1.3 Нормальные алгоритмы Маркова.
, для которого W – множество всех слов.
Допустимые команды: (Для машин этого типа важна последовательность
команд.)
но мы допускаем не всюду определенную функцию.
, если f не определена, то и программа не должна ничего выдавать.
, если f не определена, то и программа не должна ничего выдавать.
.)
1.2 Эквивалентность трех подходов к понятию алгоритм.
1.2.1 Теорема об эквивалентности понятия вычислимой функции.
)
Если существует программа МНР, которая вычисляет эту функцию.
Если существует программа МТ-П, которая вычисляет эту функцию.
Если существует программа НАМ, которая вычисляет эту функцию.
Теор.: Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР
совпадают.
которая вычисляется на МТ-П, вычислим её на НАМ.
преобразуется по правилам:
2. Булевы функции.
2.1 Основные определения
2.1.1 Декартово произведение
– мн-во всевозможных упорядоченных пар элементов из А и В.
2.1.2 Декартова степень произвольного множества.
2.1.3 Определение булевой функции от n переменных.
2.1.4 Примеры булевой функции.
логическая сумма (дизъюнкция).
логическое умножение (конъюнкция).
сложение по модулю два.
логическое следствие (импликация).
отрицание.
2.1.5 Основные булевы тождества.
(ассоциативность)
(коммутативность)
(свойство нуля)
(закон поглощения для 1)
(ассоциативность)
(коммутативность)
(свойство нуля по умножению)
(свойство нейтральности 1 по умножению)
(дистрибутивность)
(дистрибутивность 2)
(закон поглощения)
( Законы
де Моргана)
(закон снятия двойного отрицания)
(tertium non datur – третьего не дано)
(ассоциативность)
(Свойства
идемпотентности)
2.2 Дизъюнктивные нормальные формы.
2.2.1 Основные определения.
– конечный алфавит из переменных.
– элемент конъюнкции.
S – длина элемента конъюнкции.
ДНФ – дизъюнкция нескольких различных элементарных конъюнкций.
Любая булева функция может быть представлена как ДНФ
2.2.2 Теорема о совершенной ДНФ.
тождественно не равная 0 может быть разложена в ДНФ следующего вида:
.
.
он попадает в число суммируемых наборов и по нему будет проводиться
сумирование.
2.2.3 Некоторые другие виды ДНФ.
– наименьшую возможную длину из всех ДНФ данной функции.
– называется тупиковой ДНФ, если из неё нельзя выбросить ни одного
слагаемого с сохранением булевой функции.
(Легко понять, что любая минимальная ДНФ является тупиковой, а обратное
не верно.)
, которая является носителем некоторой элементарной конъюнкции длины:
n-k.
. Грань называется отмеченной, если она целиком содержится в носителе
Т.
Опр: Максимальная грань – это такая грань, которая не содержится ни в
какой грани более высокой размерности.
Предложение: Любую отмеченную грань можно вложить в максимальную грань.
(Носитель любой функции можно разложить в объединение нескольких граней
разной размерностей)
Опр: Элементарная конъюнкция называется минимальной, если её носитель
является максимальной гранью. Следовательно всякая булева функция
разлагается в дизъюнкцию всех своих элементарных конъюнкций.
Опр: Сокращенная ДНФ – разложение данной булевой функции в
соответствующие ДНФ, которые соответствуют объединению её максимальных
граней.
Теор: Минимальная ДНФ может быть получена из сокращенной отбрасыванием
некоторого количества слагаемых, возможно пустого.
3 Логические Исчисления.
3.1 Исчисления высказывания (ИВ).
3.1.1 Определения.
Опр: V – словом в алфавите А, называется любая конечная упорядоченная
последовательность его букв.
, если они имеют формат вида:
Опр: F – формулой ИВ, называется любое слово, входящее в какую-нибудь
формативную последовательность.
Reg – правила вывода ИВ (некоторые правила преобразования первого слова
в другое).
– произвольное слово ИВ (формула)
.
3.1.2 Формальный вывод.(простейшая модель доказательства теоремы)
Опр: Последовательность формул ИВ, называется формальным выводом, если
каждая формула этой последовательности имеет следующий вид:
– выводимая формула ИВ.
Правило одновременной подстановки.
, получившаяся последовательность является формальным выводом.
)
– различные символы переменных) выводима
– является формальным выводом.
3.1.3 Формальный вывод из гипотез.
, каждая из которых удовлетворяет условию:
.
Напишем список:
3.1.4 Теорема Дедукции.
Если из
, ч.т.д.
, ч.т.д.
(только что доказано), осуществим переход по индукции:
по индукции
и по лемме 2
3.2 Критерий выводимости в ИВ.
3.2.1 Формулировка теоремы.
– тавтология
при любой интерпретации алфавита (символов переменных)
3.2.2 Понятие интерпретации.
переменную поставим в соответствие.
.
– только символ
переменных, т.к.
это заглавное слово
формативной последо-
вательности вида:
3.2.3 Доказательство теоремы.
формальный
3.3 Непротиворечивость ИВ.
3.3.1 Определение.
.
ИВ противоречиво.
ИВ противоречиво.
ИВ непротиворечиво, если оно не является противоречивым.
Теорема: ИВ является непротиворечивым исчислением по отношению к любому
из трех определений.
(2) Если любая формула выводима, то выводима и А, что соответствует
пункту 1.
– булева функция
– противоречие.
3.4 Формальные исчисления.
Алфавит – конечное или счетное множество символов, возможно, разбитых на
группы. Алфавит должен быть упорядоченным множеством.
Слово – конечная упорядоченная последовательность символов алфавита, в
т.ч. пустое слово.
V – множество всех слов.
( 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 Геометрическая интерпретация навешивания кванторов.
Пронесение отрицания через кванторы
Геометрическое ‘доказательство’:
ч.т.д.
PAGE
PAGE 12
PAGE
Курс лекций по математической логике, читаемый Андреевым Кириллом
Кирилловичем
Создал Томашевич Максим Сергеевич ([email protected])
Нашли опечатку? Выделите и нажмите CTRL+Enter
