скачать
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Псковский государственный педагогический университет
имени С.М. Кирова
Физико-математический факультет
Кафедра алгебры и геометрии
УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС
учебной дисциплины
Математическая логика и теория алгоритмов
Специальность 032200.00 Физика
с дополнительной специальностью математика
Физико-математический факультет
Форма обучения дневная
4 курс 7 семестр
Псков 2007
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
^
имени С.М. Кирова
Физико-математический факультет
Кафедра алгебры и геометрии
«Утверждаю»
Декан физико-математического факультета
_______________И.Н. Медведева
«_____»_____________200__г.
^
учебной дисциплины
Математическая логика и теория алгоритмов
Специальность 032200.00 Физика
с дополнительной специальностью математика
Физико-математический факультет
^
4 курс: 7 семестр
Всего часов: 90
Лекции: 30
Практические работы: 16
Лабораторные работы: 0
Самостоятельная работа: 44
Зачет: 7 семестр
Псков
2007
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности 032100.00 Математика с дополнительной специальностью физика.
Номер государственной регистрации
№ 662 пед/сп (новый)
31» января 2005 г.
Рабочая программа принята на заседании кафедры алгебры и геометрии.
Протокол № ____ заседания кафедры
«____»____________ 200 __ г.
Программа разработана ассистентом кафедры алгебры и геометрии
__________________________ Д.С. Лобарёв
Заведующий кафедрой алгебры и геометрии
________________________ И.Н. Медведева
1. Пояснительная записка
1.1 Требования к содержанию учебной дисциплины из Государственного образовательного стандарта.
^
Курс математической логики в педагогическом институте имеет своей целью изложить основы этой науки, а именно, познакомить студентов с формализацией математического языка, формализованным аксиоматическим методом построения математических теорий, охватывающим также и логические средства, с его основными частями: языком, аксиомами, правилами вывода в самой общей форме, проблемами непротиворечивости, полноты, разрешимости теорий.
Такой подход при изучении математических теорий характерен для современной математики.
Изучение математической логики, безусловно, будет способствовать более ясному представлению об общей структуре математических теорий.
Особое внимание необходимо уделить приложению логической науки к логико-математической практике (решение текстовых математических и геометрических задача, а также задач логического характера) и анализу и синтезу дискретных устройств, что является корнем понимания функционирования простейших и тем самым сложных электронно-вычислительных машин.
Курс математической логики имеет разнообразные межпредметные связи с курсами «Математика», «Основы абстрактной и компьютерной алгебры», «Теория алгоритмов», «Программирование» и другими.
В результате изучения курса студенты должны обладать техникой логических преобразований, особенно обращению с кванторами, научиться формально доказывать формулы исчисления высказываний (теоремы). При достаточном количестве производных правил уметь провести доказательство любой тавтологии т.п.
^
Тема
|
ЛК
|
ПР
|
СР
|
Всего
|
1. Дедуктивный характер математики
|
2
|
|
2
|
2
|
2. Алгебра логики
|
10
|
6
|
14
|
30
|
3. Исчисление высказываний
|
4
|
2
|
6
|
10
|
4. Логика предикатов
|
6
|
6
|
12
|
24
|
5. Исчисление предикатов
|
4
|
-
|
4
|
8
|
6. Теория алгоритмов
|
4
|
2
|
6
|
12
|
Итого
|
30
|
16
|
44
|
90
|
^
3.1 Содержание лекционного курса
№ лек.
|
Тема лекции
|
Содержание лекции
|
Вид контроля
|
1
|
Введение
|
Дедуктивный характер математики Предмет математической логики. Из истории возникновения логической науки.
|
коллоквиум
|
2
3
|
Высказывания
Формулы
|
Определение высказывания. Логические операции над высказываниями, примеры.
Определение формулы. Истинностные значения формул. Определение функции. Представления истинностных функций формулами.
|
коллоквиум
|
3
|
Тавтологии
Равносильные формулы
|
Определения тавтологии и противоречия. Закон контрапозиции, исключенного третьего, двойного отрицания и т.п.
Равносильность. Равносильные преобразования формул. Связь равносильностей с тавтологиями.
|
коллоквиум
|
4
|
Нормальные формы
|
Определения ДН-формы и КН-формы, приводимость всякой формулы к нормальной форме, примеры. Закон двойственности.
|
коллоквиум
|
5
|
Совершенные нормальные формы
|
Определения СДН-формы и СКН-формы, их единственность, алгоритм нахождения.
|
коллоквиум
|
6
|
Логическое следствие. Проблема разрешимости
|
Определение логического следствия. Проблема разрешимости. Основные теоремы.
|
коллоквиум
|
7
|
Аксиоматическое построение логики высказываний. Теорема дедукции
|
Определение формулы. Аксиомы и правила вывода. Доказуемость формул. Выводимость из гипотез, правила выводимости. Доказательство теоремы дедукции, утверждения выводимые из неё.
|
коллоквиум
|
8
|
Свойства исчисления высказываний
|
Непротиворечивость, полнота и разрешимость исчисления высказываний. Независимость аксиом.
|
коллоквиум
|
9
|
Предикаты
Формулы логики предикатов
|
Понятие предиката. Операции над предикатами, примеры. Определение формулы, истинностные значения формул, равносильность, предваренная нормальная форма.
|
Тест
|
10
|
Общезначимость и выполнимость формул
|
Свойства. Проблема разрешения для общезначимости и выполнимости, неразрешимость ее в общем случае.
|
Тест
|
11
|
Язык логики предикатов
|
Применения языка логики предикатов для записи мат. предложений, определений, построение отрицаний предложений.
|
Тест
|
12
|
Аксиоматическое построение логики предикатов
|
Логические и специальные аксиомы. Правила вывода. Доказательства в теории. Теорема дедукции.
|
|
13
|
Основные положения
исчисления предикатов
|
Проблемы непротиворечивости, полноты, разрешимости теорий. Непротиворечивость.
Теоремы Геделя о неполноте
|
|
14
|
Понятие алгоритма
|
Машины Тьюринга. Автоматы. Рекурсивные вычислимые функции. Нормальные алгорифмы.
|
Самостоятельная работа
|
15
|
О массовых проблемах
|
Алгоритмически неразрешимые проблемы, примеры.
|
Самостоятельная работа
|
^
№ занят.
|
Тема практического занятия
|
Содержание практического занятия
|
Вид контроля
|
1
|
Высказывания и операции над ними
Формулы алгебры высказываний
Тавтологии. Равносильные формулы
|
Задачи на определения высказываний, на определение значений высказываний, на операции над высказываниями.
Определение формул, составление таблиц истинности формул.
Определение тавтологии и равносильных формул, их связь. Задачи на применение равносильных преобразований.
|
Самостоят. работа
|
2
|
Нормальные и совершенные нормальные формы, проблема разрешимости формул
|
Приводимость всякой формулы к КН-форме или ДН-форме. Нахождение СДН-формы или СКН-формы по алгоритму.
|
Самостоят. работа
|
3
|
Логическое следствие.
Приложение тавтологий.
Построение доказательств
|
Задачи на логические следствия. Метод доказательства от противного. Прямые, обратные и противоположные теоремы, задачи. Построение доказательств, свойства выводимости, их доказательства.
|
Самостоят. работа
Индивид. задание
|
4
|
Теорема дедукции
Правила вывода
|
Применение теоремы дедукции при доказательстве утверждений и теорем.
Производные правила вывода, доказательства некоторых выводимостей.
|
Индивид. задание
|
5
|
Независимость системы аксиом
Контрольная работа
|
Задачи на доказательство независимости систем аксиом.
Контрольная работа по алгебре и исчислению высказываний
|
Самостоят. работа
Контр. работа
|
6
|
Понятие предиката и операции над ним
Множество истинности предиката
|
Задачи на определение предикатов. Истинностные значения предикатов. Построение высказываний с помощью кванторов.
Нахождение множества истинности предикатов. Записи на языке алгебры предикатов.
|
Самостоят. работа
|
7
|
Формулы алгебры предикатов
Тавтологии и равносильные преобразования формул
|
Выполнимость формул.
Определение тавтологий. Доказательства равносильностей. Задачи на применение равносильностей.
|
Индивид. задание
Контр.работа
|
8
|
Алгоритмы.
|
Машины Тьюринга. Автоматы. Вычислимые функции: подстановка, примитивная рекурсия, частичная рекурсия, полная рекурсия. Нормальные алгоритмы.
|
Индивидуальное задание.
|
^
Основным методом изучения тем, вынесенных в лекционный курс, является информационно-объяснительный метод с элементами проблемных ситуаций и заданий студентам. На практических занятиях основным является поисковый метод, связанный с решением различных типов задач.
^ является базовый учебник, дополнительные пособия для организации самостоятельной работы студентов, демонстрационные материалы, компьютерные обучающие программы, сборники задач.
^ учебно-познавательной деятельности студентов являются приемы, направленные на осмысление и углубление предлагаемого содержания и приемы, направленные на развитие аналитико-поисковой и исследовательской деятельности.
Важно четко представлять структуру курса, уметь выделить в каждом разделе основные, базовые понятия, обозначенное минимумом содержания, определенного государственным образовательным стандартом.
Необходимо на каждом занятии рассматривать связь математической логики с другими дисциплинами, элементарной математикой, курсом методики преподавания математики, истории математики.
Данный курс должен сыграть большую роль в профессиональной подготовке будущего учителя.
^
В основе оценки знаний по предмету лежат следующие основные требования:
освоение всех разделов теоретического курса Программы;
умение применять полученные знания к решению конкретных задач.
Ответ заслуживает отличной оценки, если экзаменуемый показывает знания, в полной степени, отвечающие предъявляемым к ответу требованиям: это требование основных понятий и приемов решения задач. Отличная оценка характеризует свободную ориентацию экзаменуемого в предмете. Ответы на вопросы, в том числе и дополнительные, должны обнаруживать уверенное владение терминологией, основными умениями и навыками.
Хорошая оценка характеризует тот ответ, который не в полной степени удовлетворяет вышеперечисленным критериям, однако, экзаменуемый обнаруживает прочные знания в объеме курса. Ответ должен быть достаточно аргументирован, вопросы глубоко и осмысленно изложены.
Оценка «удовлетворительно» выставляется за то, что ответ экзаменуемого соотносится с основными требованиями, т.е. имеются в виду твердые знания в объеме учебной программы и умение владеть терминологией. Удовлетворительная оценка выставляется за знание в целом, однако, отдельные детали могут быть упущены.
Неудовлетворительная оценка выставляется, если ответ не удовлетворяет хотя бы одному из требований или отсутствуют знания основных понятий и методов решения задач.
^
Дисциплина разбита на 4 модуля.
По каждому модулю проводится текущий и блочный контроль. Максимальное число баллов по каждому из видов контроля указано в технологической карте.
Уровень успеваемости задается 60% (оценка удовлетворительно)
Оценка «хорошо» - 75%.
Оценка «отлично» - 90%.
Студент, пропустивший текущий рейтинг по уважительной причине имеет право написать его в другое время.
При повторной сдаче коллоквиума, сдаче его не графику (без уважительных причин) максимальный балл снижается до 12.
Если студент не имеет уровня успеваемости или хочет повысить рейтинговую оценку, он сдает экзамен. На экзамене предлагается два вопроса и тест. Каждое задание оценивается в 10 баллов. Итого (с учетом рейтинга) максимальное число баллов становится 130.
Если студент набрал 50% (65 баллов) - ставится оценка удовлетворительно, если 70% (91 балл) - оценка «хорошо», если 85% (110 баллов) - оценка «отлично».
^
Название блока (модуля)
|
Вид контроля, содержание
|
^
|
Контрольные сроки
|
Максимальное количество баллов по блоку
|
^
|
Текущий
|
25
|
Высказывания и операции над ними
|
0-3
|
|
Формулы алгебры логики
3. Тавтологии
|
0-3
0-3
|
|
^
|
0-3
|
|
5. Приложение алгебры логики
|
0-3
|
|
Блочный
|
Презентация/буклет
|
0-5
|
|
^
|
0-5
|
|
Исчисление высказываний.
|
Текущий
|
20
|
Система аксиом и правила вывода
|
0-3
|
|
Теорема о дедукции
Правила вывода
|
0-3
|
|
Непротиворечивость и полнота ИВ
|
0-3
|
|
Блочный
|
Коллоквиум №1
(теория, устно)
|
0-11
|
|
Алгебра предикатов.
|
Текущий
|
15
|
Предикат, операции, кванторы
|
0-3
|
|
Формулы АП
|
0-3
|
|
^
|
0-3
|
|
Блочный
|
^
|
0-6
|
|
Исчисление предикатов.
|
Аксиомы и правила вывода ИП
Теорема о дедукции
Непротиворечивость
Теорема Геделя о неполноте
|
0-10
|
|
10
|
1-4.
|
Семестровый контроль
|
0-30
|
|
30
|
Итого
|
100
|
Примечание. Технологическая карта выдается студентам на первом занятии с указанием конкретных сроков прохождения контроля и правил начисления баллов. В дальнейшем правила игры не меняются.
^
к коллоквиуму.
1. Предмет математической логики.
2. Определение высказывания. Логические операции над высказываниями, примеры.
3. Определение формулы. Истинностные значения формул. Определение функции. Представления истинностных функций формулами.
4. Определения тавтологии и противоречия. Закон контрапозиции, исключенного третьего, двойного отрицания.
5. Равносильность. Равносильные преобразования формул. Связь равносильностей с тавтологиями.
6. Определения ДН-формы и КН-формы, приводимость всякой формулы к нормальной форме, примеры.
7. Логическое следствие
8. Закон двойственности.
9. Определения СДН-формы и СКН-формы, алгоритм нахождения.
10. Аксиомы исчисления высказываний и правила вывода. Доказуемость формул. Выводимость из гипотез, правила выводимости.
11. Теоремы дедукции.
12. Непротиворечивость исчисления высказываний.
13. Полнота и разрешимость исчисления высказываний.
14. Независимость аксиом.
^
Укажите, какой ученый является основателем формальной логики?
Буль
Евклид
Аристотель
Колмогоров
Лейбниц
Какие из следующих предложений являются высказываниями?
Какое чудесное утро!
Треугольник называется равнобедренным, если его боковые стороны равны.
Число x не превосходит единицы.
Если треугольник равнобедренный, то высота, опущенная на основание, одновременно является медианой и биссектрисой.
Укажите ложное высказывания:
210 < 1000.
Уравнение  не имеет действительных корней.
 >14.
Луна – естественный спутник Земли.
Существуют действительные иррациональные числа.
Укажите отрицание высказывания: «Существуют иррациональные числа»
Все числа иррациональные.
Все числа рациональные.
Существуют рациональные числа.
Все числа нерациональные.
Нет иррациональных чисел.
Укажите унарную алгебраическую операцию:
╞
Сформулируйте и запишите в виде конъюнкции или дизъюнкции условие истинности высказывания |a| > 3 (а, b R).
Укажите, какие из предложенных последовательностей символов – формула.
Формула, итоговый столбец которой состоит из одних нулей, является:
тождественно-истинной
выполнимой
опровержимой
тождественно-ложной
общезначимой
Укажите тавтологию.
Укажите верное утверждение:
Равносильность является операцией алгебры логики
Отношение равносильности обладает свойством симметричности
Отношение равносильности обладает свойством антирефлексивности
Равносильность является операцией алгебры предикатов
Отношение равносильности обладает свойством полноты
Формулой равносильной к  является.
0
1
Укажите, какая выводимость (логическое следствие) имеет место.
 ,  ╞ 
1╞ 
 ╞ r
 ╞ 
0╞ ()
Укажите, в каких высказываниях вместо многоточия необходимо вставить выражение (достаточно, но необходимо), чтобы оно было истинным:
Для того, чтобы четырёхугольник был параллелограммом, … , чтобы все его стороны были равны
 - четное число … для того, чтобы  было четным числом  .
 … для того, чтобы 
Для того, чтобы четырёхугольник был прямоугольником, … , чтобы все его углы были равны.
Для того, чтобы четырёхугольник был прямоугольником, … , чтобы его диагонали были равны.
Сколько различных приведенных форм имеет формула:  .
3
1
0
2
Укажите операции, являющиеся двойственными
1. и 
2.  и 
3. и отрицание
4. отрицание и
5.  и
В основе, какой из равносильностей лежит принцип доказательства «методом контрапозиции»
1. 
2. 
3. 
4. 
5. 
Укажите, какие формулы являются КН – формами
1. 
2. 
3. 
4. 
5. 
Теорема, противоположная для  :
1. 
2. 
3. 
4. 
5. 
СДНФ формулы алгебры логики :
1
0
Для доказательства теоремы  на основании теоремы о дедукции необходимо доказать вывод:
,  ╞
 ╞ 
 , ╞
, ╞
,  ╞
Дан список аксиом:
a. 
b. 
c. 
d. 
Непротиворечивыми являются:
a,b,c
c,d
a,b,d
a,b,c,d
b,с,d
Правило силлогизма имеет вид:
1.  ├ 
2.  ├ 
3.  ├ 
4.  ├ 
5.  ├
Укажите выражения, которые не являются предикатами.
 , 
 ( - столица России),  множеству наименований европейских городов
 ( - множество прямых плоскости)
 ,
и  ( - множество наименований европейских городов)
Укажите тождественно-ложный предикат
(- ромб)(- параллелограмм) , где  множеству четырехугольников
 ,  .
 , где 
точка равноудалена от точек , где множеству точек плоскости
 , где
Укажите предикат на N, который задает множество степеней двойки:
1. 
2. 
3. 
4. 
5. 
Пусть  ( ),  ( ),  . Укажите выражение на языке алгебры предикатов высказывания: «Некоторые натуральные числа кратные 12 не являются кратными 3».
Переведите на русский язык следующую символьную запись:  , где  ,  - простые числа.
Каждое, четное число >2, есть сумма двух чисел, из которых одно простое.
Всякое натуральное число, кратное двум и >2 есть сумма двух чисел, из которых одно простое.
Некоторые четное числа >2 являются суммой двух простых.
Всякое натуральное четное число, >2 является суммой двух простых.
Всякое натуральное число, >2 является суммой двух простых.
Формулой равносильной к  является.
Предваренной формой к формуле  является.
Укажите тавтологию алгебры предикатов (общезначимую формулу).
 
^
1. Изучение литературы при подготовке презентаций и буклетов
2. Подготовка рефератов в форме презентаций или электронных публикаций (перечень тем см. ниже)
3. Изучение доказательств лемм, теорем.
4. Доказательство по аналогии.
5. Работа с Интернет-ресурсами.
6. Работа с электронными учебниками (см. Наглядные пособия)Анализ школьных учебников
7. Выполнение расчетно-графической работы.
При организации самостоятельной работы применяются типы работ:
-воспроизводящие самостоятельные работы (по образцу)
-реконструктивные самостоятельные работы
-эвристические самостоятельные работы
-исследовательские самостоятельные работы
^
Предмет математической логики
Понятия, экспликации, суждения и умозаключения
Логические и семантические парадоксы
Теоретико-множественные операции
Континуум
Логико-математический язык
Кванторы
Принцип дедукции
Формальный вывод и разрешимая формула
Метод резолюций
Диаграммы Венна
Модальная логика
Темпоральная и нечеткая логика
Нечеткие множества
Нечеткие отношения
Лингвистическая переменная
Синтаксические и семантические правила
Логико-лингвистический подход
Аксиоматический метод
Аксиоматико-дедуктивный метод в математике
Неформальная аксиоматика
Программа Гильберта
Понятие о метаязыке и метатеории
Формальные системы
Формализация теории, интерпретация и представление системы
Фразы
Грамматики
Финитные и дефинитные методы
Этапы становления математической логики
Логика Аристотеля
^
Текущий контроль:
- Самостоятельные работы
- Индивидуальные задания
- Опрос студентов
^
- Коллоквиум по алгебре и исчислению высказываний
- Контрольный тест по алгебре и исчислению высказываний
- Контрольная работа по алгебре и исчислению предикатов
- Расчетно-графическая работа
Итоговый контроль:
- Экзамен
^
Основная
Игошин В.И. Математическая логика и теория алгоритмов: Учебное пособие для студентов высших учебных заведений. – М.: Издательский центр «Академия», 2004. – 448 с.
Игошин В.И. Задачник-практикум по математической логике. – М.:1986.
Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М., 1975.
Мендельсон Э. Введение в математическую логику: Пер. с англ. – М.,1976.
Мощенский В.А. Лекции по математической логике. – Минск, 1973.
Дополнительная
Аристотель. Сочинения: В 4 т. – М., 1976-1981.
Бойко А.П. Краткий курс логики. – М., 1995.
Ефремов Г.О. Алгебра логики и контактные схемы. – М., 1969.
Новиков П.С. Элементы математической логики. – М., 1973.
Столл Р.Р. Множества. Логика. Аксиоматические теории: Пер. с анг. – М.,1968.
Ресурсы сети Интернет
Плиско В. Е. Математическая логика: Курс лекций. -- 86 с. -- http://lpcs.math.msu.su/~plisko/matlog.pdf, http://lpcs.math.msu.su/~plisko/matlog.ps
Плиско В. Е. Теория алгоритмов: Курс лекций. -- 38 с. -- http://lpcs.math.msu.su/~plisko/ta.pdf, http://lpcs.math.msu.su/~plisko/ta.ps
Bilaniuk S. A Problem Course in Mathematical Logic. -- 2003. -- XII, 152 p. -- http://www.trentu.ca/mathematics/sb/pcml/
Добавить документ в свой блог или на сайт
|
