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

Дата добавления: март 2006г.

    Конспекты лекций по математической логике
    Теория алгоритмов
    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 Реализация функции натурального переменного.
    но мы допускаем не всюду определенную функцию.
    то это означает, что

притом , если 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 Основные булевы тождества.
    (ассоциативность)
    (коммутативность)
    (свойство нуля)
    (закон поглощения для 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 – правила вывода ИВ (некоторые правила преобразования первого слова в другое). a – символ переменной

    - произвольное слово ИВ (формула)

Отображение действует так, что на место каждого вхождения символа а , пишется слово . Пример:

    Правило modus ponens:

3. 1. 2 Формальный вывод. (простейшая модель доказательства теоремы) Опр: Последовательность формул ИВ, называется формальным выводом, если каждая формула этой последовательности имеет следующий вид:

Опр: Выводимый формулой (теоремой) ИВ называется любая формула входящая в какой-нибудь формальный вывод. - выводимая формула ИВ.

    Пример:
    1)
    2)
    3)
    4)
    5)
    6)
    Правило одновременной подстановки.
    Замечание: Если формула выводима, то выводима и

Возьмем формативную последовательность вывода и добавим в неё , получившаяся последовательность является формальным выводом. (Если выводима то если , то выводима )

Теор: Если выводимая формула , то ( - различные символы переменных) выводима Выберем - символы переменных которые различны между собой и не входят не в одну из формул , сделаем подстановку и последовательно применим и в новом слове делаем последовательную подстановку: , где - является формальным выводом.

    3. 1. 3 Формальный вывод из гипотез.

Опр: Формальным выводом из гипотез (формулы), называется такая последовательность слов , каждая из которых удовлетворяет условию:

если формулу можно включить в некоторый формальный вывод из гипотез . Лемма: ; : то тогда

    Напишем список:
    Лемма:
    Док:
    3. 1. 4 Теорема Дедукции.
    Если из
    и 2а) , где по правилу m. p. , ч. т. д.
    2б) - уже выводили , ч. т. д.

Базис индукции: N=1 - формальный вывод из длинного списка (только что доказано), осуществим переход по индукции:

    по индукции
    и по лемме 2
    Пример:
    по теореме дедукции
    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 Понятие квантора.
    k – связанная переменная
    n – свободная переменная
    t – свободная, x – связанная.
    , a, b, y – свободные переменные, x – связанная.
    4. 3 Геометрическая интерпретация навешивания кванторов.
    - ортогональная проекция на ось x
    Пронесение отрицания через кванторы
    Геометрическое 'доказательство':
    не обладает свойством, что прямая целиком лежит в
    ч. т. д.