Geum.ru

Программа курса «Математическая логика и теория алгоритмов»

Вид материалаПрограмма курса

Содержание


1.2. Элементарные функции алгебры логики.
1.3. Аналитическое представление ФАЛ.
1.4. Замкнутые классы ФАЛ.
Логика предикатов.
Элементы теории алгоритмов
Подобный материал:




Программа курса «Математическая логика и теория алгоритмов»

(по специальностям «Вычислительные машины, системы, комплексы и сети», «Информационные технологии»)


1. Алгебра логики
    1. Логика высказываний.

Высказывание. Основная задача логики высказываний. Основные операции над высказываниями. Формализованный язык алгебры высказываний. Тавтологии. Равносильность формул. Критерий равносильности (теорема). Важнейшие равносильности алгебры логики. Правило отделения (теорема). Правила подстановки (теоремы). Равносильное преобразование формул. Алгебра Буля.

Отличие алгебры логики от логики высказываний. Логическая переменная. Логическая функция. Теорема о числе ФАЛ от n переменных. Недоопределенные ФАЛ.

1.2. Элементарные функции алгебры логики.

Логические функции одного аргумента. Теорема о числе ФАЛ, существенно зависящих от n аргументов. Логические функции двух аргументов. Свойства элементарных ФАЛ. Выражение одних элементарных ФАЛ через другие. Свойства элементарных ФАЛ.

1.3. Аналитическое представление ФАЛ.

Теоремы о дизъюнктивном и конъюктивном представлении ФАЛ. Полиноминальные представления ФАЛ. Совершенные нормальные формы ФАЛ. Алгоритмы перехода от табличной ФАЛ к СНДФ и СНКФ. Числовое и геометрическое представление ФАЛ. Представление ФАЛ в импликативных формах. Разложение ФАЛ по переменным (теорема). Полином Жегалкина. Теорема Жегалкина. Производные от булевых функций.

1.4. Замкнутые классы ФАЛ.

Принцип и законы двойственности в алгебре логики. Замкнутые классы (определение). Замкнутые классы ФАЛ. Полные системы функций. Базис. Минимальный базис. Теорема Поста-Яблонского.

1.5. Минимизация ФАЛ.

Числовое и геометрическое представление ФАЛ. Метод неопределенных коэффициентов. Метод Квайна. Метод Квайна Мак-Класки. Метод минимизационных карт.

1.6. Элементы цифровых устройств.

Понятие логического элемента. Реализация ФАЛ на логических элементах. Комбинационные схемы. Триггеры. Общие характеристики триггера. Классификация триггеров. Параметры триггера. Асинхронный R-S триггер и его разновидности. Синхронные триггеры. Двухступенчатые триггеры. Универсальные триггеры.


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

2.1. Основные компоненты исчисления высказываний (ИВ). Алфавит исчисления высказываний. Формула, подформула (ИВ). Секвенции, правила вывода ИВ. Система аксиом ИВ. Правило подстановки. Правило простого заключения.

2.2. Определение доказуемой формулы. Производные правила вывода (правило одновременной подстановки, правило сложного заключения, правило силлогизма, правило контрпозиции, правило снятия двойного отрицания).

2.3. Понятие выводимости формулы из совокупности формул. Понятие вывода. Правило расширения. Правило удаления выводимой гипотезы. Правило удаления импликации. Теорема дедукции. Обобщенная теорема дедукции. Правило введения конъюнкции. Правило введения дизъюнкции.

2.4. Доказательство некоторых законов логики: Закон перестановки посылок. Закон соединения посылок. Закон разъединения посылок. Закон исключения третьего.

2.5. Связь между алгеброй высказываний и исчислением высказываний. Проблемы аксиоматического исчисления высказываний (Проблема разрешимости. Проблема непротиворечивости. Проблема полноты. Проблема независимости)


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

3.1 Понятие предиката. Одноместный предикат. Двухместный предикат. Область определения предиката. Логические операции над предикатами. Кванторные операции. Понятие формулы логики предикатов. Равносильные формулы логики предикатов. Предваренная нормальная форма. Общезначимость и выполнимость формул.


4. Элементы теории алгоритмов.
    1. Интуитивное определение алгоритма. Характерные черты алгоритма (дискретность, детерминированность, элементарность шагов алгоритма, массовость, результативность). Основные направления уточнения алгоритма.
    2. Вычислимые функции. Эффективно вычислимые функции. Построение класса вычислимых функций. Суперпозиция функций. Схема примитивной рекурсии. Операция минимизации. Частично рекурсивная функция. Общерекурсивная функция. Тезис А. Чёрча.
    3. Машины Тъюринга. Устройство (внешний алфавит, внутренний алфавит, внешняя память (бесконечная лента), управляющая головка). Принцип реализации алгоритма (основная функциональная схема). Примеры реализации алгоритмов в машине Тъюринга.
    4. Основная гипотеза теории алгоритмов. Тезис Тъюринга.
    5. Нормальные алгоритмы Маркова.



Рекомендуемая литература:
  1. С.В. Яблонский. Введение в дискретную математику. М., В.ш., 2001 г.
  2. О.П. Кузнецов. Дискретная математика для инженера. Санкт-Петербург-Москва, 2004 г.
  3. С.Д. Шапорев. Математическая логика. Санкт-Петербург, 2005,
  4. Я.М. Ерусалимский. Дискретная математика., М, Вузовская книга, 2001.
  5. Б.Н. Иванов. Дискретная математика. Алгоритмы и программы. М., ЛБЗ, 2002.
  6. С.В. Судоплатов, Е.В. Овчинникова. Элементы дискретной математики. М.-Новосибирск, ИНФРА-М, НГТУ, 2002.
  7. Белоусов А.И., Ткачев С.Б. Дискретная математика. Под ред. В.С. Зарубина, А.П. Крищенко. М., МГТУ им. Н.Э. Баумана, 2004 г.
  8. Г.П. Гаврилов, А.А. Сапоженко. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.
  9. В.А. Горбатов, А.В. Горбатов, М.В. Горбатова. Дискретная математика. М., АСТ Астрель, 2003.



Зав. кафедрой ВИТ В.С. Холушкин


Профессор В.В. Алексеев.