Программа дисциплины дпп. 04 Математическая логика и теория алгоритмов



Скачать 94.36 Kb.
Дата08.10.2012
Размер94.36 Kb.
ТипПрограмма

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ


 

 

 

 

УТВЕРЖДАЮ


Руководитель Департамента

образовательных программ

и стандартов

профессионального образования

 

__________________ Л.С. Гребнев

 

“__3__” сентября_______ 2001 г.

 

 

 

 

 

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


 

ДПП.04 МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ


 

 

 

Рекомендуется Министерством образования Российской Федерации


для направления подготовки

 

540200 ФИЗИКО-МАТЕМАТИЧЕСКОЕ ОБРАЗОВАНИЕ

 

 

ДИСЦИПЛИНА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

 

Направление: 540200 Физико-математическое образование

Профиль: 540201 Математика

Курс: 4

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

Семестр: 8


Количество часов на дисциплину: 100

Количество аудиторных часов на дисциплину: 70

 

Цель дисциплины: ознакомление студентов с основными приемами символической логики, используемыми при исследовании структуры математических знаний.

 

Задачи дисциплины:

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

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

  • подготовить к работе с литературой по логике.

 

Принципы отбора содержания и организации учебного материала

Содержание курса складывается вокруг понятий, отобранных в соответствии с поставленной целью и с учетом выделяемого времени. В основу положены фундаментальные понятия (но не вопросы!) логики: исчисление, алгоритм, язык логики предикатов, формальное доказательство, формальная аксиоматическая теория.

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

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

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

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

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

 

Текущая аттестация качества усвоения знаний

Контроль достижения целей обучения осуществляется с помощью:

  • контрольной работы в течение семестра;

  • письменных опросов по текущему материалу;

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

  • собеседований.

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

 

Итоговая аттестация

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

 

Основное содержание

Исходные понятия математики символьных объектов.

Знак-символ (буква). Исходные допущения. Слово, вхождение слова в слово, подслово. Фигура слов, вхождение слова в фигуру. Алфавит. Операции конкатенации, подстановки в слова в слово вместо буквы, замены подслова на слово.

Понятие языка. Понятие правила построения слова из некоторых слов. Понятие исчисления на словах. Общее понятие исчисления. Исчисление высказываний и предикатов. Примеры.

Введение в теорию алгоритмов. Машина Тьюринга. Нормальные алгорифмы Маркова. Примеры. Общее понятие алгоритма. Принцип нормализации. Примеры алгоритмически неразрешимых проблем.

Рекурсивные функции. Теорема Гёделя о неполноте.

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

Логические языки.

Семантические категории естественного и математического языка (высказывания, предикаты, предметные имена, функторы).

Синтаксис языка первого порядка (алфавит, сигнатуры, термы, формулы, однозначность прочтения термов и формул, свободные и связанные переменные, замкнутые формулы). Аксиомы.

Стандартная семантика языка первого порядка (алгебраическая система, интерпретация сигнатуры языка, значения терма и формулы).

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

Варианты языков первого порядка. Примеры использования языка первого порядка для записи свойств математических структур и их элементов. Аксиомы натуральной арифметики. Ограниченность выразительных возможностей языка первого порядка.

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

Прямые и непрямые умозаключения. Фигуры заключения и понятие натурального вывода. Допустимые правила. Линейные доказательства и доказательства в виде дерева. Натуральный вывод с равенством. Другие способы формализации логического вывода (исчисление гильбертовского типа, семантические таблицы, секвенциальные исчисления) Понятие формальной аксиоматической теории. Примеры теорий. Примеры моделирования содержательных доказательств путем их формализации.

 

Организация самостоятельной работы

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

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

Рекомендуется также такая форма самостоятельной работы как выполнение реферата по одной из предложенных тем (объемом не менее 4 машинописных страниц), изученных студентом самостоятельно. Возможные темы рефератов: “Нормальные формы формул языка логики высказываний”, “Полные системы логических связок”, “Аналитические таблицы”, “Семантические таблицы”, “Вариант исчисления предикатов гильбертовского типа”, “Понятие трехзначной логики Лукасевича” и т.д.

 

Основные понятия

  • исчисление;

  • язык;

  • алгоритм;

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

  • формальная аксиоматическая теория.

 
Рекомендуемая литература

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

  1. Гладкий А.В. Математическая логика. – М., 1998.

  2. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. 3-е изд. – М., 1995.

  3. Математическая логика: Учебное пособие /Латотин Л.А., Макаренков Ю.А., Николаева В.В., Столяр А.А.; Под общей редакцией А.А. Столяра. – М., 1991.

  4. Михайлов А.Б., Рыжова Н.И., Швецкий М.В. Упражнения по основам математической логики. Учебное пособие для студентов математического факультета. – СПб., 1998.

  5. Михайлов А.Б., Швецкий М.В. Лекции по основам математической логики. Формальные системы первого порядка. – СПб., 1998.

  6. Михайлов А.Б., Швецкий М.В. Лекции по основам математической логики. Математические теории. – СПб., 1997.

б) дополнительная литература

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

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

  3. Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику. – М., 1982.

  4. Мартин-Леф П. Очерки по конструктивной математике. – М., 1975.

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

  6. Слупецкий Е., Борковский Л. Элементы математической логики и теория множеств. – М., 1965.

  7. Бирюков Б.В., Тростников В.Н. Жар холодных чисел и пафос бесстрастной логики. Формализация мышления от античных времен до эпохи кибернетики. – М., 1977.

  8. Гетманова А.Д. Логика. – М., 1995.

  9. Войшвилло Е.К., Дегтярев М.Г. Логика: Учебник для вузов. – М., 1998.

10. Ивин А.А., Никифоров А.Л. Словарь по логике. – М., 1997.

 

Автор-составитель примерной программы дисциплины “Математическая логика и теория алгоритмов”: Михайлов А.Б., канд. физ.-мат. наук, доцент.

 

 

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

Программа обсуждена и одобрена на заседании учебно-методического совета по направлению 540200 Физико-математическое образование Учебно-методического объединения по направлениям педагогического образования на базе РГПУ им. А.И.Герцена (протокол № 14 от 13 ноября 2000 г.).

 

 

 

Председатель совета УМО

по направлениям педагогического образования

на базе РГПУ им. А.И.Герцена ________________ Г.А.Бордовский

 

 

Председатель УМС по направлению

540200 Физико-математическое образование ________________ С.Д.Ханин

Похожие:

Программа дисциплины дпп. 04 Математическая логика и теория алгоритмов iconРабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются получение теоретических знаний по основам математическая...
Программа дисциплины дпп. 04 Математическая логика и теория алгоритмов iconУчебная программа Дисциплины р2 «Математическая логика и теория алгоритмов»
Фгос впо, содействует формированию мировоззрения и системного мышления. Целью преподавания дисциплины «Математическая логика и теория...
Программа дисциплины дпп. 04 Математическая логика и теория алгоритмов iconРабочая программа дисциплины Математическая логика и теория алгоритмов

Программа дисциплины дпп. 04 Математическая логика и теория алгоритмов iconРабочая программа по курсу «Математическая логика и теория алгоритмов» для специальности 090102 «Компьютерная безопасность»
«Математическая логика и теория алгоритмов», рекомендованной Министерством образования Российской Федерации в 2000 году для специальностей...
Программа дисциплины дпп. 04 Математическая логика и теория алгоритмов icon1. Организационно-методический раздел. 1 Название курса. Математическая логика и теория алгоритмов
Основной курс "Математическая логика и теория алгоритмов" предназначен для студентов первого курса отделения прикладной инфоматики...
Программа дисциплины дпп. 04 Математическая логика и теория алгоритмов iconРабочая программа дисциплины математическая логика и теория алгоритмов (наименование дисциплины)
«Информатика и вычислительная техника», а также задачами, стоящими перед Новосибирским государственным университетом по реализации...
Программа дисциплины дпп. 04 Математическая логика и теория алгоритмов iconРабочая программа дисциплины математическая логика и теория алгоритмов
Рабочая программа обсуждена на заседании кафедры вычислительной техники “ ” 2002 г., протокол №
Программа дисциплины дпп. 04 Математическая логика и теория алгоритмов iconТехнологий В. П. Битюцкий Н. В. Папуловская Математическая логика. Исчисления высказываний и предикатов Методическое пособие по дисциплине "Математическая логика и теория алгоритмов" Екатеринбург 2005 удк

Программа дисциплины дпп. 04 Математическая логика и теория алгоритмов iconПрограмма-минимум кандидатского экзамена по специальности 01. 01. 06 «Математическая логика, алгебра и теория чисел» по физико-математическим наукам
В основу настоящей программы положены следующие дисциплины: математическая логика; алгебра; теория чисел
Программа дисциплины дпп. 04 Математическая логика и теория алгоритмов iconМосковская государственная академия приборостроения и информатики кафедра " Персональные компьютеры и сети"
Ульянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 1: Математическая логика. – М.: Мгапи, 2003. – 47...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org