Математика

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


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

                            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]




смотреть на рефераты похожие на "Математическая Логика"