Элементы теории алгоритмов

Содержание

 

Введение ..................................................................................................
1 Алгебра высказываний (АВ) ...............................................................
2 Булевы функции (БФ) ..........................................................................
3 Логика предикатов (ЛП) ......................................................................
4 Логические исчисления (ЛИ) ..............................................................
5 Приложения математической логики (Прил) ....................................
Список использованных источников ....................................................

Введение

 

Методические указания содержат опорные конспекты (ОК) по дисциплине «Математическая логика», которые созданы как поддержка лекционного курса для организации самостоятельной работы студентов в процессе изученияучении указанной дисциплины. Содержание ОК ориентировано, прежде всего, на студентов специальностей 010501 Прикладная математика и информатика, 010503 Математическое обеспечение и администрирование информационных систем и направления подготовки 010500 Прикладная математика и информатика.

Согласно рабочим программам дисциплины для перечисленных выше специальностей и направления подготовки содержание курса включает вопросы:

Алгебра высказываний (АВ)

Высказывания. Операции над высказываниями. Формулы АВ. Таблица истинности формулы. Классификация формул. Основные тавтологии АВ.

Логическое следование. Логическая равносильность. Основные равносильности АВ. Упрощение формул, приведение их к заданному виду.

Двойственность формул АВ, принцип двойственности. Нормальные формы формул АВ: ДНФ, КНФ. СДН- и СКН-формы формул АВ.

Проблема разрешимости в АВ. Доказательство тавтологий преобразованиями (в т.ч. с помощью КНФ), с помощью алгоритма редукции, алгоритма Квайна.

Булевы функции (БФ)

Понятие булевой функции. Булевы функции одного и двух аргументов. Способы задания БФ. Тождества, справедливые для БФ. Разложение функций по переменным (СДНФ, СКНФ). Многочлен Жегалкина.

Полные и замкнутые системы БФ. Замыкание множества функций. Основные замкнутые классы БФ: классы функций, сохраняющих константы; линейные, монотонные, самодвойственные функции. Критерий полноты системы БФ. Примеры полных систем.

Приложения БФ к теории переключательных схем.

Логика предикатов (ЛП)

Понятие n-местного предиката. Область определения и множество истинности предиката. Логические и кванторные операции над предикатами. Теоретико-множественный смысл логических операций над предикатами.

Понятие формулы ЛП. Свободные и связанные переменные. Логическое значение формулы ЛП. Истинность формул в модели, на множестве.

Равносильность формул ЛП. Основные равносильности ЛП. Предваренная нормальная форма формулы ЛП.

Общезначимость и выполнимость формул ЛП. Теорема Черча.

Логические исчисления (ЛИ)

Понятие формального исчисления. Исчисление высказываний: алфавит, формулы, аксиомы, правило вывода. Производные правила вывода. Теорема дедукции.

Разрешимость, полнота и непротиворечивость ИВ.

Исчисление предикатов (ИП): алфавит, формулы, аксиомы, правило вывода. Производные правила вывода. Проблема разрешимости ИП. Полнота и непротиворечивость ИП. Теорема о полноте для случая одноместных предикатов. Теорема Геделя о неполноте.

Приложения математической логики

Роль математической логики в системе компьютерных наук. Автоматическое доказательство теорем. Правило резолюций.

Метод резолюций как основа логического программирования. Его использование в ИВ и ИП для установления логической выводимости.

Элементы теории алгоритмов

Интуитивное понятие алгоритма и его уточнение: вычислимые функции, машины Тьюринга, нормальные алгорифмы Маркова.

Вычислимые функции, тезис Черча. Примеры вычислимых функций. Разрешимые и перечислимые множества

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

Опорные конспекты являются частью УМК по указанной дисциплине, дополняя рабочие программы, и охватывают следующие разделы математической логики: «Алгебра высказываний», «Булевы функции», «Логика предикатов», «Логические исчисления», «Приложения математической логики». Раздел «Элементы теории алгоритмов» не представлен в данной методической разработке.

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

 

Алгебра высказываний (АВ)

ОК АВ 1

 

Опыт древних в искусстве правильно рассуждать был систематизирован Аристотелем. Он – основатель традиционной, классической логики.

Математическая логика (символическая, теоретическая) выросла из традиционной, но составила значительное ее расширение. С одной стороны, эта наука применила математические методы для изучения общих структур правильного мышления, а с другой – математическая логика сделала предметом своего изучения процесс доказательства математических теорем и сами математические теории. Таким образом, она стала инструментом для исследований в области оснований математики.

 

Высказывание– повествовательное утверждение, о котором можно сказать,

истинно оно или ложно.

 

A, B, C, …, A₁, A₂, A₃, …

 

Функция истинности l

 

Договоримся писать вместо l(A)=1 или l(A)=0 просто A=1 или A=0

 

Элементарные и составные высказывания

 

Операции над высказываниями