|
Экзаменационные вопросы |
© Kovalenko Leonid |
|
|
по математической логике и теории алгоритмов |
|
|
|
Весь материал взят с книг и научных работ. Ничего не придумано☺ |
||
1. Определение формальной аксиоматической теории (ФАТ). Секвенции (выводы). |
|||
Формулы. Построение формул. 5 свойств выводов ............................................................ |
|
3 |
|
2. Исчисление высказываний. Построение ИВ как ФАТ. Алфавит, формулы, аксиомы, |
|||
выводы и правила вывода....................................................................................................... |
|
4 |
|
3. Доказать, исходя из аксиом ИВ и правила вывода секвенцию ! — первое |
|||
свойство выводов ИВ.............................................................................................................. |
|
5 |
|
4. Доказать, исходя из свойств выводов, аксиом ИВ и правила вывода ИВ следующие |
|||
свойства выводов ИВ .............................................................................................................. |
|
6 |
|
5. Теорема дедукции ........................................................................................................... |
|
6 |
|
6. Свойство транзитивности импликации. Доказать секвенцию: , |
|||
................................................................................................................................................. |
|
|
8 |
7. Противоречивые формулы ............................................................................................. |
|
9 |
|
8. Обоснование доказательства от противного: доказать, что если , ¬ , то 9 |
|||
9. Тождественность формул ИВ. Доказать тождество: ¬ ¬ ≡ .............. |
11 |
||
10. |
Аксиоматическое введение в ИВ и ..................................................................... |
|
12 |
11. |
Теорема о том, что всякая выводимая в ИВ формула есть тавтология ................. |
13 |
|
12. Доказательство леммы , , … , ............................................... |
|
13 |
|
13. |
Теорема о том, что любая тавтология выводима в ИВ ........................................... |
|
16 |
14. |
Полнота и непротиворечивость ИВ .......................................................................... |
|
17 |
15. |
Предикаты. Кванторы. Свойства кванторов ............................................................ |
|
18 |
16. |
ИП — исчисление предикатов. Алфавит ИП. Формулы в ИП. Равносильность |
||
формул ИП. Приведённые и нормальные формулы ИП. Теоремы о приведённой и |
|||
нормальной форме формул ИП............................................................................................ |
|
20 |
|
17. Выполнимость и общезначимость формул ИП. Общезначимость формул |
|||
, ..................................................................................................................... |
|
21 |
|
18. Аксиомы ИП. Общезначимость аксиом ИП. Правила вывода ИП. Оформление ИП |
|||
как ФАТ .................................................................................................................................. |
|
23 |
|
19. |
Теорема об общезначимости формул ИП, получающихся из общезначимых по |
||
любому из 4-х правил вывода ИП ....................................................................................... |
|
23 |
|
20. |
Полнота и непротиворечивость ИП. Теорема Гёделя. Тезис Чёрча ...................... |
24 |
|
21. |
Алгоритмы. Определение (интуитивное) алгоритма. Свойства алгоритмов. |
||
Направления поисков точного определения алгоритма. Вычислимые функции. |
|||
Проблема алгоритмической неразрешимости.................................................................... |
|
25 |
|
22. Рекурсивные функции. 3 простейших ПРФ (примитивно-рекурсивных функций). |
|||
Оператор суперпозиции. Примеры...................................................................................... |
|
26 |
|
23. Оператор ПР (примитивной рекурсии). Доказать, что функции + , , − , |
|
− , − — ПРФ.............................................................................................................. |
27 |
24. Оператор минимизации. Частично-рекурсивные функции. Доказать, что ÷ = |
|
− , ≥ не определена, < — ЧРФ. Точное определение алгоритма. Тезис |
|
Чёрча ....................................................................................................................................... |
29 |
25. Машина Тьюринга. Тьюринговая функциональная схема. Точное определение |
|
алгоритма. Тезис Тьюринга.................................................................................................. |
31 |
26. Функции, вычислимые по Тьюрингу. Доказать, что 3 простейших ПРФ — |
|
вычислимы по Тьюрингу...................................................................................................... |
34 |
27. Геделева нумерация МТ. Примеры: по номеру найти МТ и по МТ записать номер |
|
................................................................................................................................................. |
36 |
28. Самоприменимость МТ. Теорема об алгоритмической неразрешимости проблемы |
|
самоприменимости................................................................................................................ |
37 |
29. Нормальные алгоритмы Маркова. Точное определение алгоритма. Примеры.... |
38 |
Литература ......................................................................................................................... |
41 |
1. Определение формальной аксиоматической теории (ФАТ). Секвенции (выводы). Формулы. Построение формул. 5 свойств выводов
Различают неформальную и формальную аксиоматические теории:
•Неформальная (интуитивная) аксиоматическая теория — теория, в которой правила логики явно не заданы (геометрия, арифметика, теория вероятностей и т. п.).
•Формальная аксиоматическая теория — теория, в которой правила логики явно заданы.
Формальная аксиоматическая теория (ФАТ) – теория, в которой определены:
•Выражения (конечные последовательности символов).
•Формулы (подмножество выражений — последовательность символов определенного вида; стержень теории; обычно количество формул в данной теории составляет счётное множество).
o Алфавит (счётное число символов, часто — латинские буквы).
o Связки между формулами и правила их записи. Число связок всегда конечно. Связки бывают 1-го порядка (связывающие одну формулу; например, sin в тригонометрии), 2-го порядка (связывающие две формулы; например,
+ в арифметике). Теоретически связки могут быть и -го порядка,
связывающие между собой формул.
oСкобки двух видов — правая и левая — нужны для того, чтобы определять порядок действий в формулах.
•Аксиомы данной теории (конечное число формул объявляются аксиомами).
•Правила вывода в рамках данной теории (правила вывода, позволяющие из одних формул получать другие — это действия с формулами; обычно количество правил вывода — конечное множество).
Построение формул:
1)Объявляются первичные (атомарные) формулы. Часто первичные формулы обозначаются заглавными буквами латинского алфавита.
2)Если — некоторая (уже построенная) формула и 1 — связка 1-го порядка, то 1
— тоже формула. Если и — две построенные формулы и 2 — связка 2-го порядка, то 2 — тоже формула, и, в общем случае, если 1, … , — построенных формул и — связка порядка , то (1, … , ) — тоже формула.
3)Любая формула данной теории либо сама является первичной, либо построена из первичных формул с помощью конечного числа применения правила №2.
Пусть («гамма») — произвольное конечное множество формул (возможно, пустое), используемых в качестве посылок вывода (гипотез).
Выводы (секвенции). Заметим, что слово секвенция означает «последовательность».
Далее следует считать, что вывод — это последовательный список формул, каждая из которых выводится из аксиом или предыдущих формул при помощи правил вывода.
Формула называется непосредственным следствием формул 1, … , −1, если
может быть получена из этих формул с помощью однократного применения какоголибо правила вывода .
Вывод (секвенция) — последовательность формул 1, … , , каждая из которых либо является аксиомой, либо выводится из одной или нескольких предыдущих формул этой последовательности по одному из правил вывода.
Теорема — последняя формула вывода. Иначе говоря, теорема аксиоматической теории — формула, которая может быть выведена при помощи правил вывода.
Формула называется следствием множества формул тогда и только тогда,
когда существует такая последовательность формул 1, … , −1 , каждая из которых либо аксиома, либо формула из , либо непосредственное следствие предыдущих формул. Эта последовательность формул называется выводом из ( — « есть следствие формул » или « можно вывести из формул »). Если — пустое множество формул, то есть следствие аксиом: — то есть теорема. Если из некоторых формул следует любая формула данной теории, то это значит, что формулы противоречивы: . Если состоит из формул 1, … , , то вывод из можно записать так: 1, … , . Формулы из множества называются посылками или предположениями.
Свойства выводов:
1), !
2)Если , , , то , , («порядок формул не имеет значения»).
3)Если и — любая формула, то , («лишняя формула не мешает»).
4)Если , и , то («удаление выводимой формулы»).
Пусть 1, … , — вывод формулы из , . То есть 1, … , .
Тогда если среди 1, … , встречается формула , то каждое её вхождение заменяем последовательностью формул, составляющих вывод из .
Таким образом, получаем вывод из .
5)Если из формул выводится , а из набора формул , выводится формула , то из набора формул , выводится формула .
{ |
|
( ), |
, |
|
, |
|
|
Запишем вывод формулы из , . Каждое вхождение в этот вывод заменим выводом из . Получим вывод из , .
2. Исчисление высказываний. Построение ИВ как ФАТ. Алфавит, формулы, аксиомы, выводы и правила вывода
Наиболее употребительными являются 2 системы аксиом:
•Исчисление высказываний.
•Исчисление секвенций.
По существу, обе эти системы составляют одну теорию.
Символы ИВ:
•Алфавит: , , 1, 2, …
•Связки:
o Отрицание ¬ — связка первого порядка. ¬ — «не ».
o Импликация — связка второго порядка. — «из следует ».
o Тождественная истинность ≡ — связка второго порядка. ≡ — « то же самое, что и ».
o Скобки () — порядок действий.
o Знак вывода . — « есть следствие » или « можно вывести из ».
Формулы ИВ:
•Первичные формулы — заглавные буквы латинского алфавита (возможно, с
индексами): , , 1, 2, … Смысл первичных формул в ИВ — каждая буква заменяет высказывание, которое
может быть либо истинным, либо ложным.
•Если и — формулы, то ¬ , ¬ , , — тоже формулы.
•Все остальные формулы получаются из первичных с помощью применения конечного числа связок отрицания ¬ и импликации .
Внешние скобки можно опускать. Например, ((¬ ) ( )) → ¬ .
Отрицание относится непосредственно к наикратчайшей формуле, следующей за этим знаком. Например, ¬ означает (¬) .
Правило вывода формул ИВ только одно: modus ponens (. ., «модус поненс»,
переводится как «правило вывода») — которое состоит в следующем: , («если верно и из следует , то тоже должно быть истинным»).
Аксиомы ИВ (являются независимыми друг от друга): А1. ( ) (утверждение следствия).
А2. ( ( )) (( ) ( )) (самодистрибутивность импликации). А3. (¬ ¬) ((¬ ) ) (рассуждение от противного).
Вместо , и можно подставлять любые формулы ИВ.
(Можно ввести другие системы аксиом, равносильные этим трём.)
3. Доказать, исходя из аксиом ИВ и правила вывода секвенцию ! —
первое свойство выводов ИВ
(рефлексивность импликации). Это означает, что из приведённых выше трёх аксиом следует, что из любой формулы следует сама . Построим вывод:
1)Подставим в аксиому А2 вместо формулы формулу , а вместо — . То есть из этого:
( ( )) (( ) ( ))!
Получим:
( (( ) )) (( ( )) ( )) ! (1)
2)Подставим в аксиому А1 вместо формулы формулу . То есть из этого:
( )!
Получим:
(( ) )! (2)
3)По правилу . . из (1) и (2) непосредственно следует формула:
( ( )) ( )! (3)
4)Подставим в аксиому А1 вместо формулы формулу . То есть из этого:
( )!
Получим