Раб усч программа Математическая логика и теори..

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
НГГУ
Факультет информационных технологий и математики
УТВЕРЖДАЮ

______________________
Зав. Кафедрой ФМО Кузнецова Л.Г.

"_____"__________________2012 г.


Рабочая учебная программа дисциплины

Математическая логика и теория алгоритмов
Направление Информатика и вычислительная техника
Профиль
Программное обеспечение средств вычислительной техники и автоматизированных систем


Квалификация выпускника
бакалавр

Форма обучения
очная


Нижневартовск
2012
1. Цели освоения дисциплины
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются формирование систематизированных знаний в области математической логики и теории алгоритмов, представлений о проблемах оснований математики и роли математической логики в их решении; развитие логического и алгоритмического мышления, логической и алгоритмической культуры мышления, что позволит выпускнику эффективно использовать основные методы научных исследований в своей профессиональной деятельности.
2.Место дисциплины в структуре ООП специальности.
Код дисциплины Б2.В.ОД.03 дисциплина «Математическая логика и теория алгоритмов» относится к дисциплинам математического и естественнонаучного цикла вариативная часть.
Для освоения дисциплины «Математическая логика и теория алгоритмов» используются знания, умения и навыки, полученные в ходе изучения дисциплин: Математика, Информатика.
Дисциплина «Математическая логика и теория алгоритмов» является логической основой понимания сущности доказательств и их логического строения, изучения аксиоматических математических теорий из разных областей математики, а также теоретической основой логической составляющей обучения программированию, систем искусственного интеллекта.
Знания и умения, формируемые в процессе изучения дисциплины «Математическая логика» будут использоваться при подготовке ВКР и в дальнейшем в профессиональной деятельности.
3 Компетенции обучающегося, формируемые в результате освоения дисциплины

В ходе изучения дисциплины частично формируются следующие компетенции: ОК-1, ОК-10, ПК-2, ПК-4.
В результате освоения дисциплины обучающийся должен:
Знать: основные понятия и методы математической логики и теории алгоритмов;
Уметь: использовать методы математической логики и теории алгоритмов для решения профессиональных задач;
Владеть: методами решения прикладных задач методами математической логики и теории алгоритмов, а также иметь опыт содержательной интерпретации полученных результатов
4. Структура и содержание дисциплины «Математическая логика теория алгоритмов»
Общая трудоемкость дисциплины составляет 4 зачетные единицы 144 часа.


п/п
Раздел
Дисцип-
лины
Семестр
Неделя семестра
Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)

Формы текущего контроля успеваемости
(по неделям семестра)
Форма промежуточной аттестации (по семестрам)





лекц
практ
к/р
СРС


1
Алгебра и исчисление
высказываний
3
1-4
6
8
1,5
18
1 неделя - устный опрос









2 неделя - тест









3 неделя- проверка домашней работы









4 неделя - проверка контрольной работы

2
Алгебра и исчисление предикатов
3
5-8
6
8
1,5
18
5 неделя - устный опрос









6 неделя - тест









7 неделя- проверка домашней работы









8 неделя - проверка контрольной работы

3
Теория доказательств первого порядка
3
9-12
8
10
1,5
18
9 неделя - устный опрос









10 неделя - тест









11 неделя- проверка домашней работы









12 неделя - проверка контрольной работы

4
Введение в теорию алгоритмов
3
13-16
6
10
1,5
20
13 неделя - устный опрос









14 неделя - тест









15 неделя- проверка домашней работы









16 неделя - проверка контрольной работы

Итого
144
13 =SUM(ABOVE) 142615
13 =SUM(ABOVE) 143615
6
13 =SUM(ABOVE) 147415
экзамен

.
Содержание дисциплины «Математическая логика и теория алгоритмов»
Раздел №1. Алгебра и исчисление высказываний
Предмет математической логики
Высказывание
Логика (алгебра) высказываний
Формулы логики высказываний, понятие подформулы.
Таблицы истинности.
Выполнимые формулы, тавтологии, тождественно ложные формулы.
Важнейшие равносильности.
Дизъюнктивные и конъюнктивные нормальные формы.
Алгоритм приведения формул логики высказываний к совершенной дизъюнктивной (конъюнктивной) нормальной форме.
Примеры практического применения нормальных форм.
Исчисление высказываний.
Различных аксиоматик при построении исчисления высказываний.
Требования к построению исчисления высказываний.
Вывод формул
Метод резолюций
Дедуктивный метод доказательства в исчислении высказываний?
Применения к естественному языку; анализ рассуждений
Раздел №2. Алгебра и исчисление предикатов
Понятие предиката
Одноместные и n-местные предикаты
Логики предикатов
Кванторы
Свободное и связанное вхождение переменных
Примеры предикатных формул. Термы
Истинность предикатной формулы в данной модели
Переименование связанных переменных
Предварённая нормальная форма
Приведение формулы к предварённой нормальной форме.
Сколемовская форма
Метод резолюций в логике предикатов
Исчисление предикатов
Применения предикатов к естественному языку
Исчисление предикатов с равенством
Раздел №3. Теория доказательств первого порядка
Математика аксиоматическая и математика интуитивная
Формальные системы, метаматематика
Формальная арифметика и некоторые другие формальные системы
Функциональное исчисление первого порядка секвенциального типа.
Схема аксиом.
Правила вывода.
Линейное доказательство и доказательство в виде дерева.
Функциональное исчисление первого порядка гильбертовского типа.
Теорема Гёделя о неполноте
Парадокс Сколема и нестандартные модели арифметики
Теорема Эрбрана
Теорема Робинсона о непротиворечивости
Неклассическая логика и ее значение в современных технологиях
Алгоритмическая логика Хоара
Использование математической логики при разработке систем искусственного интеллекта
Содержание раздел №4. Основы теории алгоритмов
Введение в теорию алгоритмов
Понятие алгоритма. Требования к алгоритмам. Примеры алгоритмов
Вычислимая функция
Машина Тьюринга
Тезис Чёрча
Теорема Чёрча (в терминах машин Тьюринга)
Применения к формальной арифметике; неразрешимость (теорема Чёрча) и неполнота (теорема Гёделя)
Применения к формальной арифметике; доказательства непротиворечивости (вторая теорема Гёделя)
Применения к исчислению предикатов (Чёрч, Тьюринг)
Степени неразрешимости (Пост), иерархии (Клини)
Теоремы о неразрешимости и неполноте (Россер)
Нормальный алгоритм Маркова
Теория рекурсивных функций
Рекурсия, рекуррентных последовательности и рекуррентные уравнения
Оценка сложности алгоритмов
Понятие P и NP классах сложности алгоритмов.
5. Образовательные технологии
В процессе изучения дисциплины используются современные образовательные технологии, реализации различных видов учебной работы, в частности используется проектная деятельность по подготовке компьютерных симуляций по материалу дисциплины.
Использование в учебном процессе следующих активных и интерактивных форм проведения занятий
компьютерные симуляции - по разделу №4;
деловые и ролевые игры - по разделу №1 и №2;
разбор конкретных ситуаций по всем разделам;
коллективная проектная деятельность по созданию вики-ресурса по дисциплине по всем разделам дисциплины.
Удельный вес занятий, проводимых в интерактивных форма составляет не менее 25% аудиторных занятий (определяется требованиями ФГОС с учетом специфики ООП).
Занятия лекционного типа составляют 41% всех аудиторных занятий.
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.
Для закрепления материала и повышения эффективности его усвоения, а также для возможности проведения текущего и рубежного контроля планируется проведение следующих видов самостоятельной работы студентов по разделам дисциплины.
Раздел №1. Алгебра и исчисление высказываний
Виды самостоятельной работы по разделу №1:
индивидуальное домашнее задание (см. [5] Практикум по математической логике и теории алгоритмов);
ответы на контрольные вопросы и выполнение заданий по разделу;
Контрольные вопросы по разделу №1
В чем состоит предмет математической логики?
Что такое логика высказываний?
Приведите примеры высказываний с использованием и без использования логических связок.
Приведите формулы логики высказываний, дайте понятие подформулы.
Выпишите таблицы истинности для логических связок и формул.
Приведите примеры выполнимых формул, тавтологий, тождественно ложных формул.
Перечислите важнейшие равносильности.
Дайте определение дизъюнктивных и конъюнктивных нормальных форм.
Опишите алгоритм приведения формул логики высказываний к совершенной дизъюнктивной (конъюнктивной) нормальной форме.
Приведите примеры практического применения нормальных форм.
Что такое исчисление высказываний.
Приведите примеры различных аксиоматик при построении исчисления высказываний.
Опишите требования исчислению высказываний.
Как осуществляется вывод формул?
В чем состоит дедуктивный метод доказательства в исчислении высказываний?
Поясните понятия достаточности, полноты, непротиворечивости независимости системы аксиом.
Контрольные задания по разделу №1
1. Записать в виде логических формул высказывания:
Если преступление предусмотрено общей и специальной нормами, совокупность преступлений отсутствует и уголовная ответственность наступает по специальной норме.
Преступление признается совершенным с прямым умыслом, если лицо осознавало общественную опасность своих действий (бездействия), предвидело возможность или неизбежность наступления общественно опасных последствий и желало их наступления.
Преступление признается совершенным группой лиц, если в его совершении совместно участвовали два или более исполнителя без предварительного сговора.
2. Пусть А - истинное высказывание, В - ложное высказывание. Определить значение истинности следующих сложных высказываний:
A( B)( A ;
(A ( B) ( A;
A ( (A ( B) ( A;
A ( (B ( A);
A ( (A( A(B);
A(B (A( (A (B);
A ( (B ( C ( C);
5. Известно, что импликация A ( B истинна, а эквивалентность A (B ложна. Что можно сказать о значении импликации B ( A?
6. Найти логические значения A и B, при которых выполнятся равенства:
(1 ( A) ( B = 0,
A ( B = A.
7. Найти равносильную формулу операции эквивалентность, в которой используются:
только три операции: отрицания, дизъюнкции и конъюнкции;
только две операции: отрицания и дизъюнкции.
8. Выразить операции дизъюнкции, конъюнкции и эквивалентности через отрицание и импликацию
9. Доказать закон контрапозиции и Modus ponens с помощью таблиц истинности.
10. Проверить правильность рассуждения средствами логики суждений: "Если человек осуждён судом, то он лишается избирательных прав. Если человек признан невменяемым, то он также лишается избирательных прав. Следовательно, если человек обладает избирательным правом, то он здоров и не был осуждён судом".
11. Проверить правильность рассуждения средствами логики суждений: «Иванов утверждает, что не встречал этой ночью Сидорова. Если Иванов не встречал этой ночью Сидорова, то либо Сидоров был убийцей, либо Иванов лжёт. Если Сидоров не был убийцей, то Иванов не встречал его этой ночью, а убийство было совершено после полуночи. Если убийство было совершено после полуночи, то либо Сидоров был убийцей, либо Иванов лжёт. Следовательно, убийцей был Сидоров».
12. Проверить правильность рассуждения средствами логики суждений: «Если бы он не пошёл в кино, то он не получил бы двойки. Если бы он подготовил домашнее задание, то не пошёл бы в кино. Он получил двойку. Значит, он не подготовил домашнее задание».
Проверить правильность следующего рассуждения: «Для того чтобы сдать экзамен, мне необходимо достать учебник или конспект. Я достану конспект только в том случае, если мой приятель не уедет. Мой приятель уедет, только если я сдам экзамен. Следовательно, я сдам экзамен».
Выяснить, кто из четверых виновен на основе информации: “Петров виновен, только если виновен Иванов. Неверно, что виновность Сидорова влечет виновность Родионова и что Иванов виновен, а Сидоров нет”.
Петров, Иванов и Сидоров сдавали экзамен по информатике и математике. Если Петров не сдал экзамен на «отлично», то и Иванов не сдал на «отлично». Сидоров и еще один из друзей сдали экзамен на «отлично». Следует ли отсюда, что не верно, что Петров сдал экзамен не на «отлично», а Иванов на «отлично»?
На складе совершено хищение. Подозрение пало на трех человек: a, b, и c, они были доставлены для допроса. Установлено следующее:
Никто, кроме a, b, c, не был замешан в деле.
a никогда не ходит на дело без, по крайней мере, одного соучастника.
c не виновен.
Виновен ли b?
Разбирается дело Иванова, Петрова и Сидорова. Один из них совершил преступление. В процессе расследования каждый из них сделал по два заявления.
Иванов: Я не делал этого. Петров не делал этого. Петров: Сидоров сделал это. Иванов не делал этого. Сидоров: Я не делал это. Иванов сделал это.
Далее было установлено, что один из них дважды солгал, другой дважды сказал правду, а третий раз солгал, раз сказал правду.
Кто совершил преступление? Какой будет ответ при условии, что каждый из них один раз сказал правду, а один раз солгал?
В деле об убийстве имеются двое подозреваемых - Иванов и Петров. Допросили четырех свидетелей, которые последовательно дали такие показания: "Иванов не виноват", "Петров не виноват", "Из двух первых показаний по меньше мере одно истинно", "Показания третьего ложны". Четвертый свидетель оказался прав. Кто виновен?
По подозрению в совершенном преступлении задержали Иванова, Петрова и Сидорова. Один из них был уважаемым в городе стариком, другой был малоизвестным чиновником, третий - известным мошенником. В процессе следствия старик говорил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом - ложь. Вот, что они утверждали:
Иванов: Я совершил это. Петров не виноват. Петров: Иванов не виноват. Преступление совершил Сидоров. Сидоров: Я не виноват. Виноват Иванов.
Требуется определить фамилии старика, мошенника и чиновника, и кто из них виноват, если известно, что преступник один.
Было совершено ограбление квартиры. Подозрение пало на двух известных воров Иванова и Петрова. Кроме того, обнаружились три свидетеля, которые заявили:
Первый: Это они сделали вместе.
Второй: Ограбление совершил Иванов, Петров в этом не участвовал.
Третий: Если Петров совершил ограбление, то Иванов тоже принимал в этом участие.
Какой вывод можно сделать из показаний свидетелей, если выяснилось, что все они обманывали?
Предположим, что а говорит: "Или я лжец, или b рыцарь". Кто из двух персонажей – а и b – рыцарь и кто лжец?
Предположим, что а высказывает утверждение: "Я – лжец, а b не лжец". Кто из персонажей а и b рыцарь и кто лжец?
Предположим, а утверждает: «Если b рыцарь, то я – лжец». Кто из персонажей а и b рыцарь и кто лжец?
Предположим, а утверждает: «Если я рыцарь, то и b – рыцарь». Убедиться, что и а и b – рыцари.
Известно, что каждый из а, b, с является либо рыцарем, либо лжецом. Можно ли определить, кто есть кто, по их следующим высказываниям:
а: « Мы все рыцари»;
b: «Только один из нас – рыцари»?
На некотором острове, населенном рыцарями и лжецами, разнесся слух о том, что на нем зарыты сокровища. Вы прибываете на остров и спрашиваете одного из местных жителей: “Есть ли на острове золото?”. В ответ на ваш вопрос он заявляет: “Сокровища на этом острове есть в том и только в том случае, если я рыцарь”.
а) можно ли определить, кто такой этот местный - рыцарь или лжец? б) можно ли определить, есть ли сокровища на острове?
Один из а, b и с является рыцарем, один лжецом, один – простым крестьянином (иногда говорит правду, иногда лжет).. Они утверждают следующее:
а: « Я крестьянин»;
b: « То, что сказал А, - правда»;
с: « Я – не крестьянин».
Кем являются а, b и с в действительности?
подготовка к тестированию (см. контрольные вопросы задания по разделу),
подготовка к контрольной работе (см. домашнее задание, контрольные вопросы и задания по разделу)
подготовка реферата
Темы рефератов по разделу№1
История развития математической логики
Значение математической логики в развитии систем искусственного интеллекта
Роль российских ученых в развитии математической логики
Критика классической математической логики современными учеными
создание электронного ресурса по дисциплине
Создать электронный учебный ресурс (электронный учебник), раскрывающий содержание темы с использованием компьютерной анимации и содержащий не менее 10 контрольных вопросов в виде html-страницы для изучения конкретной темы. Выбор темы согласовать с преподавателем.
Раздел №2. Алгебра и исчисление предикатов
Виды самостоятельной работы по разделу №2:
домашняя работа (см. Практикум по математической логике и теории алгоритмов);
ответы на контрольные вопросы по разделу.
Контрольные вопросы разделу №2
Дайте определение предиката
Приведите примеры одноместных, n-местных предикатов
В чем отличие логики предикатов от логики высказываний?
Приведите примеры записи предикатов с использованием кванторов
Чем отличаются свободные и связанные вхождения переменных?
Приведите примеры предикатных формул
Что такое терм?
Как определить истинность предикатной формулы в данной модели?
Как происходит переименование связанных переменных?
Что такое предварённая нормальная форма
Опишите приведение формулы к предварённой нормальной форме.
Что такое сколемовская форма?
Поясните суть метода резолюций в логике предикатов
Что такое исчисление предикатов?
подготовка к тестированию (см. содержание раздела);
подготовка к контрольной работе (см. домашнее задание);
подготовка реферата
Темы рефератов по разделу №2.
Метод резолюций
Вклад С.К. Клини в математическую логику
Труды Дж. Буля по математической логике
Взгляды Куайна на построение математической логики
создание электронного ресурса по дисциплине (см. раздел №1)
Раздел №3. Теория доказательств первого порядка
домашняя работа (см. Практикум по математической логике и теории алгоритмов)
ответы на контрольные вопросы по разделу
Контрольные вопросы по разделу
Дайте определение теории первого порядка
Приведите примеры аксиоматического построения известных Вам из школы теорий
Функциональное исчисление первого порядка секвенциального типа.
Схема аксиом.
Правила вывода.
Линейное доказательство и доказательство в виде дерева.
Функциональное исчисление первого порядка гильбертовского типа.
Теорема Гёделя о неполноте
Приведите примеры аксиом и теорем из школьного курса геометрии.
Приведите примеры теорий (можно использовать, теорию групп, теорию полей, формальную арифметику, элементарную геометрию).
Теоремы Тарского о полноте и разрешимости элементарной геометрии (без доказательства).
В чем причины возникновения неклассических математических логик. Предмет неклассических логик.
Приведите примеры формальных (аксиоматических) систем.
В чем состоит формальный аксиоматический метод Гильберта,
Раскройте значение теорем Гёделя о неполноте.
подготовка к тестированию,
подготовка к контрольной работе
подготовка реферата
создание электронного ресурса по дисциплине
Раздел №4 Основы теории алгоритмов
домашняя работа,
ответы на контрольные вопросы по разделу
Контрольные вопросы и задания по разделу
Что изучает теория алгоритмов?
Перечислите основные требования к алгоритмам.
Что такое вычислимая функция? Приведите примеры
Дайте определение Машины Тьюринга.
В чем состоит тезис Чёрча (Черча-Тьюринга).
Опишите машину Поста.
Как задается нормальный алгоритм Маркова
Приведите основные положения теории рекурсивных функций
Приведите примеры рекурсии, рекуррентных последовательностей и рекуррентных уравнений
Как оценивают эффективность алгоритмов
Приведите пример оценки сложности алгоритмов
Дайте понятие P и NP классах сложности алгоритмов.
подготовка к тестированию (см. содержание раздела),
подготовка к контрольной работе(см. содержание раздела)
подготовка реферата
Темы рефератов по разделу
Алгоритмически неразрешимые проблемы математики
Тезис Черча и его значение для развития теории алгоритмов
Вклад Маркова в развитие теории алгоритмов
создание электронного ресурса по дисциплине (см. раздел №1)
Вопросы для итоговой аттестации по дисциплине
Предмет математической логики
Высказывание
Логика (алгебра) высказываний
Формулы логики высказываний, понятие подформулы.
Таблицы истинности.
Выполнимые формулы, тавтологии, тождественно ложные формулы.
Важнейшие равносильности.
Дизъюнктивные и конъюнктивные нормальные формы.
Алгоритм приведения формул логики высказываний к совершенной дизъюнктивной (конъюнктивной) нормальной форме.
Примеры практического применения нормальных форм.
Исчисление высказываний.
Различных аксиоматик при построении исчисления высказываний.
Требования к построению исчисления высказываний.
Вывод формул
Метод резолюций
Дедуктивный метод доказательства в исчислении высказываний?
Применения к естественному языку; анализ рассуждений Понятие предиката
Одноместные и n-местные предикаты
Логики предикатов
Кванторы
Свободное и связанное вхождение переменных
Примеры предикатных формул. Термы
Истинность предикатной формулы в данной модели
Переименование связанных переменных
Предварённая нормальная форма
Приведение формулы к предварённой нормальной форме.
Сколемовская форма
Метод резолюций в логике предикатов
Исчисление предикатов
Применения предикатов к естественному языку
Исчисление предикатов с равенством
Математика аксиоматическая и математика интуитивная
Формальные системы, метаматематика
Функциональное исчисление первого порядка секвенциального типа.
Схема аксиом.
Правила вывода.
Линейное доказательство и доказательство в виде дерева.
Функциональное исчисление первого порядка гильбертовского типа.
Теорема Гёделя о неполноте
Формальная арифметика и некоторые другие формальные системы
Парадокс Сколема и нестандартные модели арифметики
Теорема Эрбрана
Теорема Робинсона о непротиворечивости
Неклассическая логика и ее значение в современных технологиях
Использование математической логики при разработке систем искусственного интеллекта
Понятие алгоритма. Требования к алгоритмам. Примеры алгоритмов
Вычислимая функция
Машина Тьюринга, тезис Чёрча
Теорема Чёрча (в терминах машин Тьюринга)
Применения к формальной арифметике; неразрешимость (теорема Чёрча) и неполнота (теорема Гёделя)
Применения к формальной арифметике; доказательства непротиворечивости (вторая теорема Гёделя)
Применения к исчислению предикатов (Чёрч, Тьюринг)
Степени неразрешимости (Пост), иерархии (Клини)
Теоремы о неразрешимости и неполноте, использующие лишь простую непротиворечивость (Россер)
Нормальный алгоритм Маркова
Основы теории рекурсивных функций
Рекурсия, рекуррентных последовательности и рекуррентные уравнения
Оценка сложности алгоритмов
Понятие P и NP классах сложности алгоритмов.
7. Учебно-методическое и информационное обеспечение дисциплины «Математическая логика»
а) основная литература:
Лихтарников Л.М., Сукачева Т.Г. Математическая логика. – СПБ: Лань, 1999.
Игошин В.И. Задачник – практикум по математической логике. – М.: Просвещение, 1986.
Лавров И.А., Максимова Л.Л. Задачник по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 1975.
Практикум по математической логике и теории алгоритмов. Нижневартовск. НГГУ. 2012. 28 с.
Мендельсон Э. Введение в математическую логику. – М.: Наука, 1971.
б) дополнительная литература:
1. Игошин В.И. Математическая логика и теория алгоритмов. – Саратов: Изд-во Саратовского университета, 1991.
5. Эдельман С.Л. Математическая логика. –Мн.: ВШ, 1975.
10.   Лихтарников Л.М., Сукачева Т.Г. Курс лекций по математической логике. –Новгород: Изд-во НГПИ, 1993.
12. Латонин Л.А. и др. Математическая логика. –Мн.ВШ,1991.
в) программное обеспечение и Интернет-ресурсы
Электронно - библиотечная система образовательные и просветительские издания: [сайт ] URL: [ Cкачайте файл, чтобы посмотреть ссылку ]
Основы теории множеств и математической логики: [сайт ] URL: [ Cкачайте файл, чтобы посмотреть ссылку ]
8. Материально-техническое обеспечение дисциплины (модуля)
Для проведения компьютерных симуляций, тестирования необходимо наличие учебного класса, оснащенного компьютерами
Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по специальности «Прикладная математика»
Автор Уразаева Л.Ю.
Рецензент Дмитриев Н.П.
Программа одобрена на заседании кафедры физико-математического образования от 01.06.12 года, протокол № 9.












Приложенные файлы

  • doc 8958756
    Размер файла: 160 kB Загрузок: 0

Добавить комментарий