Элементы теории алгоритмов
Содержание
| Введение .................................................................................................. | |
| 1 Алгебра высказываний (АВ) ............................................................... | |
| 2 Булевы функции (БФ) .......................................................................... | |
| 3 Логика предикатов (ЛП) ...................................................................... | |
| 4 Логические исчисления (ЛИ) .............................................................. | |
| 5 Приложения математической логики (Прил) .................................... | |
| Список использованных источников .................................................... |
Введение
Методические указания содержат опорные конспекты (ОК) по дисциплине «Математическая логика», которые созданы как поддержка лекционного курса для организации самостоятельной работы студентов в процессе изученияучении указанной дисциплины. Содержание ОК ориентировано, прежде всего, на студентов специальностей 010501 Прикладная математика и информатика, 010503 Математическое обеспечение и администрирование информационных систем и направления подготовки 010500 Прикладная математика и информатика.
Согласно рабочим программам дисциплины для перечисленных выше специальностей и направления подготовки содержание курса включает вопросы:
Алгебра высказываний (АВ)
Высказывания. Операции над высказываниями. Формулы АВ. Таблица истинности формулы. Классификация формул. Основные тавтологии АВ.
Логическое следование. Логическая равносильность. Основные равносильности АВ. Упрощение формул, приведение их к заданному виду.
Двойственность формул АВ, принцип двойственности. Нормальные формы формул АВ: ДНФ, КНФ. СДН- и СКН-формы формул АВ.
Проблема разрешимости в АВ. Доказательство тавтологий преобразованиями (в т.ч. с помощью КНФ), с помощью алгоритма редукции, алгоритма Квайна.
Булевы функции (БФ)
Понятие булевой функции. Булевы функции одного и двух аргументов. Способы задания БФ. Тождества, справедливые для БФ. Разложение функций по переменным (СДНФ, СКНФ). Многочлен Жегалкина.
Полные и замкнутые системы БФ. Замыкание множества функций. Основные замкнутые классы БФ: классы функций, сохраняющих константы; линейные, монотонные, самодвойственные функции. Критерий полноты системы БФ. Примеры полных систем.
Приложения БФ к теории переключательных схем.
Логика предикатов (ЛП)
Понятие n-местного предиката. Область определения и множество истинности предиката. Логические и кванторные операции над предикатами. Теоретико-множественный смысл логических операций над предикатами.
Понятие формулы ЛП. Свободные и связанные переменные. Логическое значение формулы ЛП. Истинность формул в модели, на множестве.
Равносильность формул ЛП. Основные равносильности ЛП. Предваренная нормальная форма формулы ЛП.
Общезначимость и выполнимость формул ЛП. Теорема Черча.
Логические исчисления (ЛИ)
Понятие формального исчисления. Исчисление высказываний: алфавит, формулы, аксиомы, правило вывода. Производные правила вывода. Теорема дедукции.
Разрешимость, полнота и непротиворечивость ИВ.
Исчисление предикатов (ИП): алфавит, формулы, аксиомы, правило вывода. Производные правила вывода. Проблема разрешимости ИП. Полнота и непротиворечивость ИП. Теорема о полноте для случая одноместных предикатов. Теорема Геделя о неполноте.
Приложения математической логики
Роль математической логики в системе компьютерных наук. Автоматическое доказательство теорем. Правило резолюций.
Метод резолюций как основа логического программирования. Его использование в ИВ и ИП для установления логической выводимости.
Элементы теории алгоритмов
Интуитивное понятие алгоритма и его уточнение: вычислимые функции, машины Тьюринга, нормальные алгорифмы Маркова.
Вычислимые функции, тезис Черча. Примеры вычислимых функций. Разрешимые и перечислимые множества
Простейшие функции: сдвиг, аннулятор и проектор. Операции суперпозиции, примитивной рекурсии и минимизации. Примитивно-рекурсивные, частично-рекурсивные и общерекурсивные функции. Вычислимость частично-рекурсивных функций.
Опорные конспекты являются частью УМК по указанной дисциплине, дополняя рабочие программы, и охватывают следующие разделы математической логики: «Алгебра высказываний», «Булевы функции», «Логика предикатов», «Логические исчисления», «Приложения математической логики». Раздел «Элементы теории алгоритмов» не представлен в данной методической разработке.
Содержание каждого ОК устанавливает минимум знаний по соответствующему подразделу дисциплины, который необходимо продемонстрировать студенту для получения положительной оценки на коллоквиуме, экзамене.
Алгебра высказываний (АВ)
ОК АВ 1
Опыт древних в искусстве правильно рассуждать был систематизирован Аристотелем. Он – основатель традиционной, классической логики.
Математическая логика (символическая, теоретическая) выросла из традиционной, но составила значительное ее расширение. С одной стороны, эта наука применила математические методы для изучения общих структур правильного мышления, а с другой – математическая логика сделала предметом своего изучения процесс доказательства математических теорем и сами математические теории. Таким образом, она стала инструментом для исследований в области оснований математики.
Высказывание– повествовательное утверждение, о котором можно сказать,
истинно оно или ложно.
A, B, C, …, A1, A2, A3, …
Функция истинности l
Договоримся писать вместо l(A)=1 или l(A)=0 просто A=1 или A=0
Элементарные и составные высказывания
Операции над высказываниями