Экзамен по мат логике - Exhelper.top - портал для учащихся

	Экзаменационные вопросы	© 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 вместо формулы формулу . То есть из этого:

( )!

Получим

( )! (4)

5)Тогда из формул (3) и (4) по правилу . . выводится нужная формула:

4.Доказать, исходя из свойств выводов, аксиом ИВ и правила вывода ИВ

следующие свойства выводов ИВ

2) Если , то , .

. . , !

По свойству №3 («лишняя формула не мешает») и №2 («порядок формул не имеет значения») — добавляем в начало:

, , !

По свойству №4 («удаление выводимой формулы») — так как по условию выводима из , то её можно убрать как выводимую:

, !

3) Если и , то .

. . , !

По свойству №3 («лишняя формула не мешает») и №2 («порядок формул не имеет значения») — добавляем в начало:

, , !

По свойству №4 («удаление выводимой формулы») — так как по условию ивыводимы из , то их можно убрать как выводимые:

4) Если и — любая формула ИВ, то .

. . , ( ) ( )!

По свойству №3 («лишняя формула не мешает») и №2 («порядок формул не имеет значения») — добавляем в начало:

, , ( ) ( )! (1)

Так как ( ) — аксиома А1, то (аксиома следует из любых формул):

( )!

По свойству №3 («лишняя формула не мешает») — добавляем :

( )!

Из (1) по свойству №4 («удаление выводимой формулы») — так как по условиюи ( ), то их можно убрать как выводимые:

5. Теорема дедукции

Если из формул и выводится формула , то из формул выводится формула

(«если , , то »). (Дедукция — переход от общего к частному.) Метод математической индукции (индукция — это переход от частного к общему):

1.Проверяют истинность утверждения для = 1 ( = 0) — база индукции.

2.Предполагают, что утверждение верно для = — индуктивное предположение.

3.Доказывают, что тогда оно верно и для = + 1 — индуктивный переход.

Доказательство (методом математической индукции по числу — длине вывода). Пусть 1, … , есть вывод из и (то есть 1, … , ).

База индукции. Пусть = 1. Тогда совпадает с 1. Согласно определению вывода возможны 3 случая:

1) — аксиома	2) — формула из	3) совпадает с
Если 1 — аксиома, то по свойству №3 («лишняя	Значит совпадает с .
формула не мешает») — добавляем , а если 1 —	По свойству ИВ №1 (
формула из , то ничего не добавляем: в любом из	!) и свойству №3 («лишняя
этих двух случаев можно вывести .	формула не мешает»):
! ( 1!)	!
Тогда, по свойству ИВ №4:	То есть получили
если и — любая формула ИВ, то	(где совпадает с ).

Допустим теперь, что если длина вывода формулы меньше , то утверждение теоремы верно, и докажем, что тогда теорема верна для длины вывода, равного . При этом возможны 4 случая:

1) — аксиома	2) — формула из	3) совпадает с
Доказательство такое же, как при = 1

4) получена по правилу . . из , ( ), где , <
то есть ,	( имеет вид )

Отбрасывая последние − формулы из 1, … , , получаем вывод , . Отбрасывая последние − формулы из 1, … , , получаем вывод , . Длины этих выводов меньше и мы имеем:

, ! (1)

, ! ( , )! (2)

Индуктивное предположение (верно для и ):

! (1)

! ( ( ))! (2)

Далее следует индуктивный переход к .

По аксиоме А2:

( ( )) (( ) ( ))!

Имеем ( → , → , свойство №3: «лишняя формула не мешает» — добавляем ):

( ( )) (( ) ( ))! (3) . . к секвенциям (2) и (3):

( ) ( )! (4)

После этого, применяя все то же правило . . к секвенциям (1) и (4) получаем:

То есть !

Таким образом, индукция проведена, и теорема дедукции доказана.

6.Свойство транзитивности импликации. Доказать секвенцию: ( ),

Транзитивность импликации (правило силлогизма).

, ?

По свойству ИВ №2 («если , то , ») и свойству №2 («порядок формул не имеет значения»):

, , ?

По свойству №5 («если из формул выводится , а из набора формул , выводится формула , то из набора формул , выводится формула »):

Получаем («если из формул , выводится , а из формул , выводится формула , то из формул , , выводится формула »):

По свойству №2 («порядок формул не имеет значения») и теореме дедукции («если

, , то »):

, !

Доказать секвенцию: ( ), .

( ), ?

По свойству ИВ №2 («если , то , »):

( ), , ?

По свойству №2 («порядок формул не имеет значения»):

( ), , ?

По теореме дедукции («если , , то »):

( ), ?

По теореме дедукции («если , , то »):

( ) ( )?

По свойству №1 (, или ):

( ) ( )!

По свойству ИВ №2 («если , то , »):

( ), !

По свойству ИВ №2 («если , то , »):

( ), , !

По свойству №2 («порядок формул не имеет значения»):

( ), , !

По теореме дедукции («если , , то »):

( ), !

7. Противоречивые формулы

Доказать:

1)Если и ¬ , то («из ложного следует всё, что угодно»).

Пусть — любая формула. Тогда из двух данных секвенций по свойству ИВ №4 («если и — любая формула ИВ, то ») следует, что ¬ и¬ ¬. По аксиоме А3 (заметим, что аксиома следует из любых формул):

(¬ ¬) ((¬ ) )!

По свойству №3 («лишняя формула не мешает») — добавляем :

(¬ ¬ ) ((¬ ) )!

Тогда применяя 2 раза свойство ИВ №2 («если , то , »), получим:

, (¬ ¬), (¬ ) !

По свойству №4 («удаление выводимой формулы») — так как ¬ ¬ и ¬ , то выводимые формулы (¬ ¬) и (¬ ) можно убрать:

2)Если , то , ¬ .

По условию:

По свойству №3 («лишняя формула не мешает») — добавляем ¬:

, ¬ !

Следующее утверждение также справедливо, так как по свойству №1 (¬ ¬) и по свойству №3 («лишняя формула не мешает») — добавляем :

, ¬ ¬ !

По уже доказанному выше утверждению («если и ¬, то ») — так как

, ¬ и , ¬ ¬, то получим: , ¬ !

8. Обоснование доказательства от противного: доказать, что если , ¬ , то

Доказательство «от противного» — вид доказательства, при котором «доказывание» некоторого суждения (тезиса доказательства) осуществляется через опровержение отрицания этого суждения — антитезиса.

Доказательство утверждения проводится следующим образом. Сначала принимают предположение, что утверждение неверно, а затем доказывают, что при таком предположении было бы верно некоторое утверждение , которое заведомо неверно.

Из определения импликации следует, что, если ложно, то формула ¬ истинна тогда и только тогда, когда ¬ ложно, следовательно утверждение истинно.

Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение ¬¬ , которое по закону двойного отрицания равносильно утверждению .

Доказательство №1 (если , ¬ , то ).

Так как , ¬ , то есть из и ¬ выводима любая формула, то, в частности, выводима и формула : , ¬ . Значит, ¬ по теореме дедукции.

По свойству ИВ №1 ( ) из любых формул (в частности, из формул ) выводится ¬ ¬, а по свойству №3: «лишняя формула не мешает»: ¬ ¬.

Сдругой стороны, по аксиоме А3:

(¬ ¬ ) ((¬ ) )!

Имеем ( → , свойство №3: «лишняя формула не мешает» — добавляем ):

(¬ ¬ ) ((¬ ) )!

Применяя 2 раза свойство ИВ №2 («если , то , »), получим:

, (¬ ¬ ), (¬ ) !

По свойству №4 («удаление выводимой формулы») — так как ¬ и ¬ ¬, то, удаляя выводимые формулы ¬ и ¬ ¬, получим: !

Доказательство №2 (если , , то ¬).

В самом начале докажем, что если — любая формула, то , ¬ . По свойству №1 ( ):

По свойству №3 («лишняя формула не мешает») — добавляем ¬:

¬ , !

¬ , ¬ !

То есть ¬ , и ¬ , ¬ — по уже доказанному в 7-ом вопросе утверждению («если и ¬, то ») и свойству №2 («порядок формул не имеет значения»):

, ¬ !

Теперь перейдём к основному доказательству («если , , то ¬»).

Так как по доказанному выше («если — любая формула, то , ¬ ») и свойству №2 («порядок формул не имеет значения»), то имеем:

¬¬ , ¬ !

Так как по доказательству №1 («если , ¬ , то »), то:

¬¬ !

Кроме того, формулы и по условию противоречивы (, ). Тогда по свойству №3 («лишняя формула не мешает») — будут противоречивы 3 формулы:

, ¬¬ !

Как уже было написано, ¬¬ ! — значит по свойству №4 («удаление выводимой формулы») можно удалить выводимую формулу :

, ¬¬ !

Тогда по доказательству №1 («если , ¬ , то ») получаем ¬.

Источник

Материал из Викиконспекты

Перейти к: навигация, поиск

Конспекты лекций Штукенберга по мат. логике

Исчисление высказываний, формальная система (Вопросы 1, 2)
Лемма о дедукции, полнота исчисления высказываний (Вопросы 3, 4)
Исчисление предикатов (Вопросы 5, 6)
Секвенциальное и интуиционистское исчисление (Вопросы 7,
Теории первого порядка (Вопросы 9, 10)
Рекурсивные функции, представимость в формальной арифметике (Вопросы 11, 12, 13)
Геделева нумерация. Арифметизация доказательств (Вопросы 14)
1я и 2я теоремы Геделя о неполноте арифметики (Вопросы 15, 16)
Теория множеств (Вопросы 17, 18,19)

Экзамен

Решение задач по логике

Вопросы к экзамену по математической логике за 3 семестр

Теоретический минимум по математической логике за 3 семестр

Источник

Демонстрационный вариант экзамена по дисциплине «Элементы математической логики»

Инструкция для студентов

На выполнение письменной работы по математике дается 2 астрономических часа (120 минут).

Экзаменационная работа состоит из двух частей: основной и дополнительной.

При выполнении любого задания требуется предоставить ход решения и указать ответ.

Правильное выполнение задания оценивается баллами. Баллы, полученные за все задания, суммируются.

Критерии оценки выполнения работы:

Оценка	Число баллов, необходимых для получения оценки
«3» (удовлетворительно)	9-13
«4» (хорошо)	14-17
«5» (отлично)	18-20

Основная часть

1. (1балл) Даны множества А={ 4,7,11}, B={1,4,5,7}, U={1,2,3,4,5,9,10,11}. Определите мощность множества .

2. (1 балл) Изобразите с помощью кругов Эйлера множество .

3. (1 балл) Вычислить

4. (1 балл) Найти , если .

5. (1 балл) Запишите сложное высказывание на языке алгебры логики: «Я не вымокну, если на улице нет дождя или если прогулка отменяется, и я останусь дома».

6. (1 балл) Упростите формулу

7. (1 балл) Постройте таблицу истинности формулы .

8. (1 балл) Запишите СДНФ и СКНФ для булевой функции, заданной вектором значений f=(11001010).

9. (1 балл) Запишите суждение и его отрицание в виде формулы логики предикатов: «Не всякое действительное число является рациональным». Оцените истинность обоих высказываний.

10. Найти множество истинности предиката ,:

Дополнительная часть

11. (2 балла) В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе. Известно, что:

1. Смит самый высокий;

2. играющий на скрипке меньше ростом играющего на флейте;

3. играющие на скрипке и флейте и Браун любят пиццу;

4. когда между альтистом и трубачом возникает ссора, Смит мирит их;

5. Браун не умеет играть ни на трубе, ни на гобое.

На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

12. (2 балла) Дано множество . Составьте матрицу отношения R- « иметь общий делитель, отличный от единицы» определите его свойства.