Реферат: Программа дисциплины по кафедре Прикладная математика и информатика математическая логика и теория алгоритмов

,ФЕДЕРАЛЬНОЕ АГЕНТСВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования
Тихоокеанский государственный университет






УТВЕРЖДАЮ

Проректор по учебной работе

________________С.В. Шалобанов

«______»_____________200__г.


ПРОГРАММА ДИСЦИПЛИНЫ

по кафедре Прикладная математика и информатика

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

Утверждена научно-методическим советом университета для направлений подготовки (специальностей) в области информатики и вычислительной техники


Хабаровск 2006 г.

Программа разработана в соответствии с требованиями государственного образовательного стандарта, предъявляемыми к минимуму содержания дисциплины и в соответствии с примерной программой дисциплины, утвержденной департаментом образовательных стандартов профессионального образования с учетом особенностей региона и условий организации учебного процесса Тихоокеанского государственного университета


Программу составила

Хан Сун Э, к.ф.м.н, доцент кафедры ПМИ


Программа рассмотрена и утверждена на заседании кафедры ПМИ

протокол № ____ от «_____»__________200_ г

Зав.кафедрой _________________ «______»_________200_ г. Зарубин А.Г.


Программа рассмотрена и утверждена на заседании УМК и рекомендована к изданию протокол № ____ от «_____»__________200_ г
Прекдседатель УМК _________________ _________200_ г ________________
Подпись дата Ф.И.О.


Директор института _________________ _________200_ г ________________
Подпись дата Ф.И.О.
^ (декан факультета)
Цели и задачи дисциплины


Целью преподавания дисциплины «Математическая логика и теория алгоритмов» является ознакомление студентов с важнейшими разделами математической логики и теории вычислимости, оказывающими наибольшее влияние на теорию и практику современного программирования.

При преподавании учебной дисциплины «Математическая логика и теория алгоритмов» ставятся следующие задачи:

обучить студентов классической логике высказываний и предикатов, теории рекурсивных функций;

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

привести естественное содержательное истолкование изучаемых понятий и результатов в терминах современного программирования;

выработать у студентов навыки свободного обращения с такими объектами как логические формулы, логико-алгебраические модели, системы формального вывода, модели вычислений, рекурсивные множества и функции;

дать студентам представление о потенциальных возможностях и ограничениях формальных логических теорий и алгоритмов;

развить у студентов аналитическое мышление и общую математическую культуру;

привить студентам умение самостоятельно изучать учебную и научную литературу в области математики.



^ Требования к уровню освоения содержания дисциплины

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


^ Объем дисциплины и виды учебной работы
Наименование
По учебным планам основной траектории обучения

С максимальной трудоемкостью

С минимальной трудоемкостью
Общая трудоемкость дисциплины
По ГОС

По УП


140

85


100


Изучается в семестрах

3



Виды итогового контроля по семестрам
Зачет

Экзамен

Курсовой проект (КП)

Курсовая работа (КР)

^ Виды итогового контроля самостоятельной работы без отчетностей

Расчетно-графические работы (РГР)

Реферат (РФ)

Домашние задания (ДЗ)



3




^ Аудиторные занятия:

Всего

В том числе: лекции (Л)

Лабораторные работы (ЛР)

Практические занятия (ПЗ)


51

34


17



Самостоятельная работа
Общий объем часов (С2)

В том числе: на подготовку к лекциям

на подготовку к ЛР

на подготовку к ПЗ

на выполнение КП

на выполнение КР

на выполнение РГР

на написание РФ

на выполнение ДЗ

на экзаменационную сессию


34

17


17






Содержание дисциплины

^ ЛОГИКА ВЫСКАЗЫВАНИЙ Язык логики высказываний. Понятие логического высказывания. Логические операции над высказываниями. Формулы алгебры высказываний. Равносильные формулы алгебры высказываний. Принцип двойственности. Дизъюнктивные и конъюнктивные нормальные формы, совершенные дизъюнктивные и конъюнктивные нормальные формы. Минимизация СДНФ методом Квайна. Логические функции аргументов. Разложение Шеннона. Полнота системы логических функций. Теорема Поста. Базисы (булевский, Жегалкина, Шеффера и др.). Приведение функций к различным формам. Некоторые приложения алгебры высказываний. Переключательные схемы, синтез логических схем, решение логических задач методами алгебры высказываний.

^ ЛОГИКА ПРЕДИКАТОВ Синтаксис языка логики предикатов: алфавит, термы, атомы, правила построения формул. Свободные и связанные вхождения переменных, замкнутые формулы. Семантика языка логики предикатов, интерпретация формул. Предваренная нормальная форма. Применение языка логики предикатов для записи математических предложений.

^ ФОРМАЛЬНЫЕ (АКСИОМАТИЧЕСКИЕ) СИСТЕМЫ Понятия формальной системы и формального вывода. Исчисление высказываний как формальная система, множественность аксиоматизаций. Теорема дедукции. Связь выводимости и истинности формул в логике высказываний. Примеры формального вывода. Основные свойства формальных систем: непротиворечивость, полнота, разрешимость. Теоремы о неполноте формальных систем.

^ ТЕОРИЯ АЛГОРИТМОВ Понятие алгоритма и его характерные черты. Вычислимые функции. Примитивно рекурсивные, частично-рекурсивные функции, тезис Черча. Машины Тьюринга, тезис Тьюринга. Рекурсивные и рекурсивно-перечислимые множества и языки. Алгоритмически разрешимые и неразрешимые задачи. Меры сложности алгоритмов: временная и емкостная сложность. Асимптотическая сложность, порядок сложности. Сложность в среднем и в худшем случае. Языки и задачи. Легко- и трудноразрешимые задачи, классы задач P и NP. NP-полные задачи. Недетерминированная машина Тьюринга.
^ Разделы дисциплины и виды занятий и работ



№
Раздел дисциплины
Л

ПЗ

С2



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

*

*






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

*

*

*



Формальные системы

*

*

*



Теория алгоритмов

*

*

*



Практические занятия

^ ЛОГИКА ВЫСКАЗЫВАНИЙ

Задание. Решение задач по теме: таблицы истинности формул алгебры высказываний, равносильные преобразования формул, логические функции, полные системы логических функций, представление функции в различных базисах, некоторые приложения алгебры высказываний. Время на выполнение задания – 6 часов

Оснащение. Для проведения всех практических занятий целесообразно использовать  Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. – СПб.: Издательство «Лань», 1998, Игошин В.И. Задачник-практикум по математической логике. – М.: Просвещение, 1986, Гиндикин С.Г. Алгебра логики в задачах. – М.: Наука, 1972, сборники задач на усмотрение преподавателя.

^ ЛОГИКА ПРЕДИКАТОВ

Задание. Решение задач по теме: предикаты, их область определения и область истинности, операции дизъюнкции, конъюнкции, отрицания над предикатами, кванторные операции, равносильные формулы логики предикатов, предваренная нормальная форма. Время на выполнение задания – 3 часа

^ ФОРМАЛЬНЫЕ (АКСИОМАТИЧЕСКИЕ) СИСТЕМЫ

Задание. Решение задач по теме: доказуемые формулы исчисления высказываний, выводимость, производные правила вывода. Время на выполнение задания – 4 часа.


^ ТЕОРИЯ АЛГОРИТМОВ

Задание. Решение задач по теме: построение некоторых машин Тьюринга, доказательство принадлежности функции классу примитивно рекурсивных или частично рекурсивных функций. Время на выполнение задания – 4 часа.

Практические занятия и их взаимосвязь с содержанием лекционного курса



№ п/п

№ раздела по варианту содержания
^ Наименование практических занятий


1

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



1

Полные системы логических функций. Представление функции в различных базисах



1

Некоторые приложения алгебры высказываний



2

Предикаты. Область определения и область истинности. Кванторы. Равносильные формулы логики предикатов. Предваренная нормальная форма



3

Формулы исчисления высказываний. Система аксиом и правила вывода. Доказуемые формулы. Производные правила вывода



3

Выводимость формулы из совокупности формул. Доказательство некоторых законов исчисления высказываний



4

Реализация алгоритмов на машине Тьюринга



4

Элементарные вычислимые функции. Примитивно рекурсивные, частично рекурсивные функции



Контроль знаний студентов

^ 1. Входной контроль знаний студентов
Для изучения дисциплины необходимо знание понятий и положений курсов «Математический анализ», «Алгебра», «Дискретная математика», «Информатика».
^ 2. Текущий контроль знаний студентов
Контроль достижения целей обучения осуществляется с помощью проведения контрольной работы в течение семестра по темам курса. Главной целью проведения контрольной работы является установление уровня и характера усвоения студентами основных понятий, умений и навыков, формируемых в процессе изучения курса.

Примерное содержание контрольной работы

^ Контрольная работа содержит 5 задач по темам: равносильные преобразования формул алгебры высказываний, полнота систем логических функций, логические операции над предикатами, доказуемые и выводимые формулы исчисления высказываний, машины Тьюринга.


3.^ Выходной контроль знаний студентов

Дисциплина завершается устным экзаменом. На экзамене проверяется степень усвоения студентами основных понятий дисциплины, понимание их взаимосвязи, умение доказывать основные теоремы, а также навыки в решении задач по каждому из разделов дисциплины.

^ Экзаменационные вопросы

Понятие «элементарное высказывание». Логические операции над элементарными высказываниями. Формулы алгебры высказываний. Подформулы.

Тавтология и противоречие. Равносильные формулы. Связь между равносильностью и эквивалентностью. Равносильные преобразования формул: теорема подстановки и теорема замены.

Двойственные формулы. Принцип двойственности. Основные равносильности алгебры высказываний.

Определение логической функции. Логические функции одной и двух переменных.

Конъюктивные и дизъюнктивные нормальные формы. Совершенные конъюктивные и дизъюнктивные нормальные формы. Теорема Шеннона.

Классы Поста. Полная система. Критерий Поста. Базис. Основные базисы пространства бинарных логических функций.

Одноместный предикат. - местный предикат. Область определения и область истинности предиката. Тождественно истинный и тождественно ложный предикат.

Логические операции над одноместными предикатами. Кванторы всеобщности и существования.

Формулы логики предикатов. Равносильные формулы. Равносильности логики предикатов.

Нормальная форма формулы логики предикатов и предваренная нормальная форма. Теорема о предваренной нормальной форме.

Понятие «чистое исчисление предикатов». Алфавит, формулы, аксиомы и основные правила вывода исчисления предикатов.

Алфавит, формулы, аксиомы и основные правила вывода прикладных исчислений предикатов.

Алфавит, формулы, аксиомы и основные правила вывода исчисления высказываний.

Доказуемая формула. Правило одновременной подстановки. Правило сложного заключения.

Формула, выводимая из совокупности формул. Теорема дедукции.

Эквивалентные формулы. Теорема эквивалентности.

Проблемы аксиоматического исчисления высказываний.

Понятие «алгоритм». Основные требования, предъявляемые к алгоритмам. Блок-схемы алгоритмов.

Машина Тьюринга. Определение и описания. Конфигурация машины Тьюринга. Стандартная начальная и стандартная заключительная конфигурация.

Эквивалентные машины Тьюринга. Теорема о машине Тьюринга, не содержащей направления «» (или «на месте»). Композиция машин Тьюринга. Функции, правильно вычислимые на машине Тьюринга.

Нуль-функция, функция следования и функция проекции. Операторы суперпозиции, примитивной рекурсии и минимизации. Примитивно рекурсивные, частично рекурсивные функции.

Нормальные алгоритмы Маркова.

Алгоритмическая разрешимость. Меры сложности алгоритмов. Верхние и нижние оценки сложности алгоритмов.



^ Учебно-методическое обеспечение дисциплины

Основная литература.

Верещагин. Лекции по математической логике и теории алгоритмов.

Гетманова А.Д. Учебник по логике. – М.: ЧеРо, 1997.

Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука, 1987.

Ивлев Ю.В. Логика: учебник для вузов.- М.: Логос, 1997.

Игошин В.И. Математическая и теория алгоритмов. – Саратов: изд. СГУ, 1991.

Клини С. Математическая логика.– М.: Мир, 1973.

Ковальский Р. Логика в решении проблем. – М.: Наука, 1990.

Лавров С.С. Лекции по теории программирования. – СПб.: изд. НЕСТОР, 1999.

Лихтарников Л.М., Сукачева Т.Г. Математическая логика. – Москва: "Лань", 1999.

Мальцев А.И. Алгоритмы и рекурсивные функции.

Мендельсон Э. Введение в математическую логику. – М.: Наука, 1984.

Непейвода Н.Н. Прикладная логика. – Новосибирск: изд НГУ, 2000.

Новиков П.С. Элементы математической логики. – М.: Наука, 1973.


Дополнительная литература

Гилберт Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики. – М.: Наука, 1979.

Яблонский С.В. Введение в дискретную математику. – М.: Высш. шк., 2001.

Белоусов А.И., Ткачев С.Б. Дискретная математика. – М.: Издательство МГТУ им. Н.Э. Баумана, 2001.

Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001.

Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.

Клини С.К. Математическая логика. – М.: Мир, 1973.

Гилберт Д., Бернайс П. Основания математики. Теория доказательств. – М.: Наука, 1982.

Гудстейн Р.Л. Математическая логика. – М.: ИЛ, 1961.

Гиндикин С.Г. Алгебра логики в задачах. – М.: Наука, 1972.

Марков А.А., Нагорный Н.М. Теория алгорифмов. – М.: Наука, 1984.

Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике.–М.: Наука, 1977.



Методические рекомендации по организации изучения дисциплины


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

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

Математические курсы, соответствующие данной программе, должны содержать лекции, практические занятия в аудитории, индивидуальные занятия студентов с преподавателем и самостоятельную работу студентов. Целью лекций является изложение теоретического материала и иллюстрация его примерами и задачами. Основным теоретическим результатам должны сопутствовать пояснения об их приложениях к другим разделам математики и к техническим наукам. Желательно также кратко излагать историю появления наиболее важных понятий и результатов. Курс лекций должен строиться на основе четких формулировок и доказательств основных теорем, так как лишь при таком подходе студенты приобретают математическую культуру, необходимую для дальнейшего изучения инженерных дисциплин. Недопустимо сводить чтение лекций только к разбору примеров и алгоритмов их решения. Целью практических занятий является закрепление теоретического материала лекций и выработка умения решать примеры и задачи для последующего применения математических методов в технических приложениях. Важнейшей частью математических курсов являются индивидуальные занятия с преподавателем. Поэтому изучаемый курс должен содержать контрольные работы в течение семестра.

Организация самостоятельной работы предполагает, что:

отдельные темы могут быть отнесены на самостоятельное изучение;

на лекциях предлагается значительное количество контрольных вопросов и упражнений, служащих для проверки усвоения теории;

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

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

Знания, полученные при изучении дисциплины «Математическая логика и теория алгоритмов» применяются при изучении широкого спектра профильных, специальных предметов.

Программа рассчитана на 85 часов.

Программа составлена в соответствии с государственными образовательными стандартами высшего профессионального образования.


^ Словарь терминов

Алгоритм – точное предписание, определяющее детерминированный и результативный процесс решения множества задач определенного класса


Вывод – непустая конечная последовательность утверждений, каждое из которых представляет собой либо аксиому, либо посылку, либо получено из предыдущих шагов по одному из правил вывода


Дедукция – тип умозаключения, в котором между посылками и заключением

существует отношение логического следования


^ Дизъюнктивная нормальная форма – дизъюнкция различных конъюнкций, причем членами конъюнкций являются различные переменные или отрицания переменных


Дизъюнкция двух высказываний x, y – новое высказывание, которое считается ложным, если оба высказывания x, y ложны, и истинным во всех остальных случаях


Доказательство – вывод из пустого множества посылок


Импликация двух высказываний x, y – новое высказывание, которое считается ложным, если высказывание x истинно, а y ложно, и истинным во всех остальных случаях


^ Конъюнктивная нормальная форма – конъюнкция различных дизъюнкций, причем членами дизъюнкций являются различные переменные или отрицания переменных


Конъюнкция двух высказываний x, y – новое высказывание, которое считается истинным, если оба высказывания x, y истинны, и ложным во всех остальных случаях


^ Логическая функция n переменных – функция, у которой каждая переменная аргумента и само значение функции принимают только два значения 0 и 1, то есть .


^ Непротиворечивость формальной системы – свойство системы, при котором любое утверждение, доказуемое в ней, является истинным


Область истинности предиката – множество таких , что P(x)=1.


^ Область ложности предиката – множество таких , что P(x)=0.


Отрицание высказывания x – новое высказывание, которое является истинным, если высказывание x ложно, и ложным, если x истинно


^ Полнота формальной системы – свойство системы, при котором любое утверждение, истинное в ней, является доказуемым


Предикат от n переменных – функция P, которая декартову произведению множеств предметных переменных сопоставляет множество {0,1}.


^ Предикат от одной переменной – функция P, которая множество предметных переменных X отображает в множество {0,1}. Обозначается


Противоречие – формула алгебры высказываний, которая принимает ложное значение при любых значениях, входящих в нее элементарных высказываний


^ Равносильные формулы алгебры высказываний – формулы, которые принимают одинаковые значения на любом наборе значений, входящих в них элементарных высказываний


^ Равносильные предикаты на множестве Х – предикаты, у которых есть общая область определения Х и которые принимают одинаковые значения при любых предметных переменных из этой области


^ Совершенная дизъюнктивная нормальная форма – дизъюнктивная нормальная форма, у которой каждая переменная или ее отрицание входит в каждую конъюнкцию ровно один раз


^ Совершенная конъюнктивная нормальная форма – конъюнктивная нормальная форма, у которой каждая переменная или ее отрицание входит в каждую дизъюнкцию ровно один раз


Тавтология – формула алгебры высказываний, которая принимает истинное значение при любых значениях, входящих в нее элементарных высказываний


^ Тождественно истинный предикат – предикат , у которого область истинности совпадает с его областью определения


^ Тождественно ложный предикат – предикат , у которого область ложности совпадает с его областью определения


^ Универсальное высказывание, соответствующее одноместному предикату – высказывание «каждый элемент множества ^ Х удовлетворяет предикату Р(х)», оно считается истинным, если предикат тождественно истинный и ложным во всех остальных случаях


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


^ Формула алгебры высказываний – высказывание, полученное из элементарных высказываний с помощью операций конъюнкции, дизъюнкции, импликации, эквиваленции, отрицания


Эквиваленция двух высказываний x, y – новое высказывание, которое считается истинным, когда оба высказывания x, y одновременно истинны или одновременно ложны, и ложным во всех остальных случаях


Экзистенциальное высказывание, соответствующее одноместному предикату – высказывание «существует элемент множества Х, удовлетворяющий предикату Р(х)», оно считается ложным, если предикат тождественно ложный и истинным во всех остальных случаях


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