RUS ENG

Мощенский А. В. Курс математической логики

Мощенский А. В. Курс математической логики: Учеб. пособие / А. В.Мощенский, В. А. Мощенский; Пер. с бел. яз. авторов. — Мн.: БГУ, 2001.— 129 с.

ISBN 985-445-453-3

В учебном пособии излагаются все понятия курса математической логики, однако основное внимание уделяется темам «предикаты» и «алго ритмы».

Данное пособие предназначается для студентов физико-математических специальностей высших учебных заведений, учебные программы которых включают курсы по дискретной математике и информатике.


Оглавление

Предисловие

3

1. Логика высказываний

4

1.1. Высказывания

4

1.2. Логические операции

5

1.3. Формулы логики высказываний. Тавтологии

9

1.4. Логическое следствие

12

1.5. Некоторые применения тавтологий

14

2. Функции алгебры логики и k - значной логики

18

2.1. Понятие булевой функции. Элементарные функции

18

2.2. Формулы, суперпозиции. Свойства элементарных булевых функций

20

2.3. Принцип двойственности

23

2.4. Разложение булевых функций попеременным

24

2.5. Импликативная нормальная форма

26

2.6. Полные системы булевых функций

27

2.7. Важные замкнутые классы

28

2.8. Критерий полноты

31

2.9. Представление о теоремах Поста

32

2.10. Функции k- значной логики

33

2.11. Реализация функций k -значной логики формулами. Основные эквивалентности

35

3. Исчисление высказываний

38

3.1. Формальные аксиоматические теории

38

3.2. Формулы и аксиомы исчисления высказываний. Примеры выводимых формул

41

3.3. Дальнейшие свойства выводов

43

3.4. Непротиворечие

47

3.5. Полнота

48

3.6. О независимости аксиом и k -значиых логиках

52

4. Логика предикатов

54

4.1. Предикаты

55

4.2. Операции над предикатами. Формулы логики предикатов

57

4.3. Интерпретации. Равносильность формул

61

4.4. Основные равносильности

66

4.5. Общезначимость. Выполнимость

70

4.6. Понятие о теориях первого порядка

76

5. Алгоритм

79

5.1. Интуитивное понятие алгоритма и необходимость его уточнения

80

5.2. Машины Тьюринга

82

5.3. Функции, вычислимые по Тьюрингу. Тезис Тьюринга

86

5.4. Операции над машинами Тьюринга

89

5.5. Частично-рекурсивные функции (класс Ч)

92

5.6. Классы Ч и Т

97

5.7. Алгоритмически неразрешимые проблемы

99

5.8. Универсальные машины Тьюринга и функции

102

5.9. Некоторые общие теоремы теории алгоритмов

105

5.10. k -Ленточные машины Тьюринга, k ≥ 1 (детерминированные и недетерминированные)

111

5.11. Классы Р и NP . Проблема P =? NP . NP -полные проблемы

116

5.12. О машинно-независимой теории сложности вычислений

121

5.13. Перечисление рекурсивно-перечислимых множеств

125

Список литературы

127

Другие сайты факультетаСтруктураОбразованиеМагистратураНаукаМеждународное сотрудничествоСтудентуНИРСАСовет молодых ученыхОлимпиадыАбитуриентуШкольникуЦентр
Компетенций
по ИТ
Microsoft
Imagine Premium
ИсторияИздания факультетаПрофбюро ФПМИПерсональные страницыФотогалереи Газета ФПМыНаши партнеры