РЕШАЕМ МАТЕМАТИКУ ВМЕСТЕ!
 
СТУДЕНТАМ:    Учебники     Решебники    Шпаргалки    Контрольные работы   Видео уроки

ШКОЛЬНИКАМ:  ГДЗ - 1 класс  2 класс  3 класс  4 класс  5 класс  6 класс  7 класс  8 класс  9 класс  10 класс  11 класс


Главная » Файлы » Учебные материалы » Математическая логика и теория алгоритмов
Гуц А.К. Математическая лоrика и теория алrоритмов.

11.12.2011, 21:24
Учебное пособие посвящено изложению основ математической логики и теории алгоритмов. Основу пособия составляют конспекты лекций, которые читались студентам втopoгo курса отделения компьютерных наук Омского государственного университета в 2002 году.
Оглавление
I Логика  7

1. Классическая логика
  8
1.1 Логика высказываний   8
1.1.1. Высказывания   8
1.1.2. Основные законы логики  9
1.1.3. Логический парадокс Рассела 10
1.1.4. Алгебра (логика) высказываний  11
1.1.5. Релейно-контактные схемы  12
1.1.6. Равносильные формулы  14
1.1.7. Алгебра Буля  15
1.1.8. Истинные и общезначимые формулы  15
1.1.9. Проблема разрешимости   15
1.1.10. Логическое следствие  16
1.1.11. Силлогизмы  17
1.2. Логика предикатов  17
1.2.1. Предикаты и формулы 18
1.2.2. Интерпритации  19
1.2.3.Истинность и выполнимость формул. Модели, общезначимость, логическое следствие  20
1.2.4. Готлоб Фреге   21
1.2.5. Сколемовские функции и сколемизация формул  22
1.3. Метод резолюций  25
1.3.1. Метод резолюций в логике высказываний  25
1.3.2. Метод резолюций в логике предикатов  29
2. Формальные теории (исчисления)  31
2.1 Определение формальной теории, или исчисления  32
2.1.1. Доказательство. Непротиворечивость теории. Полнота теории  32
2.2 Исчисление высказываний  33
2.2.1. Язык и правила вывода исчисления высказываний  33
2.2.2. Пример доказательства теоремы  35
2.2.3. Полнота и непротиворечивость исчисления высказываний  36
2.3. Исчисление предикатов  37
2.3.1. Язык и правила вывода исчисления предикатов 37
2.3.2. Полнота и непротиворечивость исчисления предикатов  39
2.4 Формальная арифметика  39
2.4.1. Эгалитарные теории 39
2.4.2. Язык и правила вывода формальной арифметики  39
2.4.3. Непротиворечивость формальной арифметики. Теорема Генцена  40
2.4.4. Теорема Гёделя о неполноте  41
2.4.5. Курт Гёдель  42
2.5. Автоматический вывод теорем  43
2.5.1. С.Ю. Маслов  43
2.6. Логическое программирование  45
2.6.1. Логическая программа  46
2.6.2. Языки логического программирования  49
3. Неклассические логики  50
3.1. Интуиционистская логика  50
3.2. Нечеткая логика  51
3.2.1. Нечеткие подмножества 51
3.2.2. Операции над нечеткими подмножествами  52
3.2.3. Свойства множества нечетких подмножеств  53
3.2.4. Нечеткая логика высказываний 54
3.2.5. Нечетко релейно-контактные схемы  56
3.3. Модальные логики  56
3.3.1. Типы модальности  57
3.3.2. Исчисления I и Т (Фейса-фон Вригта)  57
3.3.3. Исчисления S4,S5 и исчисление Брауэра  58
3.3.4. Означивание формул 59
3.3.5. Семантика Крипке  60
3.3.6. Другие интерпретации модальных знаков  62
3.4. Георг фон Вригт 62
3.5. Временные логики  62
3.5.1. Временная логика Прайора  63
3.5.2. Временная логика Леммона  64
3.5.3. Временная логика фон Вригта  64
3.5.5. Временная логика Пнуели 67
3.6. Алгоритмические логики  70
3.6.1. Принципы построения алгоритмической логики  71
3.6.2. Чарльз Хоар  3
3.6.3. Алгоритмическая логика Хоара 74

II Алгоритмы 77

4. Алгоритмы 78
4.1. Понятие алгоритма и вычислимой функции 78
4.2. Рекурсивные функции 79
4.2.1. Примитивно рекурсивные функции 80
4.2.2. Частично рекурсивные функции 81
4.2.3. Тезис Чёрча  82
4.3. Машина Тьюринга-Поста 83
4.3.1. Вычисления функций на машине Тьюринга-Поста  84
4.3.2. Примеры вычислений 86
4.3.3. Тезис Тьюринга 87
4.3.4. Универсальная машина Тьюринга-Поста 87
4.4. Алан Тьюринг  87
4.5. ЭмильПост  89
4.6. Эффективные алгоритмы 91
4.7. Алгоритмически неразрешимые проблемы  91
5. Сложность алгоритмов 93
5.1. Понятия о сложности алгоритмов 93
5.2. Классы задач Р и NP  94
5.2.1. Класс задач Р  84
5.2.2. Класс задач NP 95
5.2.3. Недетерминированная машина Тьюринга  95
5.3. О понятиях сложности  97
5.3.1. Три типа сложности  97
5.3.2. Четыре категории чисел по Колмогорову  97
5.3.3. Тезис Колмогорова  98
5.4. А.Н. Колмогоров 99
6. Алгоритмы реальности 101
6.1. Генератор виртуальной реальности  102
6.2. Принцип Тьюринга 102
6.3. Логически возможные среды Кантгоуту 104
Литература 105








Размер файла: (867.4Kb)

Категория: Математическая логика и теория алгоритмов | Добавил: nikka
Просмотров: 1734 | Загрузок: 259 | Рейтинг: 0.0/0


Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]



ВЫБОР ПО КАТЕГОРИЯМ:

Аналитическая геометрия и алгебра [0]
Высшая алгебра [52]
История математики [55]
Математика для технарей [21]
Математика для экономистов, юристов и т.д.. [5]
Математическая логика и теория алгоритмов [40]
Теория вероятностей и мат. статистика [28]
Теория чисел [33]
Учебники по математике [46]



При полном или частичном использовании материалов
активная ссылка на портал VMATE.RU обязательна


Высшая математика онлайн - всё бесплатно, наш портал создан специально для студентов кому интересна высшая математика. У нас на портале возможно скачать бесплатно учебники по высшей математике, книги по математике или сделать заказ учебных пособий, скачать контрольные по высшей математике, заказать, задачники по высшей математики и решебники. Оставить запрос по предмету - аналитическая геометрия или задать вопрос - справочная по математике Заказать решение и т.д. Высшая математика онлайн - математический портал и здесь собраны шпаргалки по высшей математике и видео уроки. миэмп Добро пожаловать! Вход