Учебно-методическое и информационное обеспечение дисциплины (курса)

Федеральное агентство по образованию

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

«Новосибирский муниципальный университет» (НГУ)

Факультет информационных технологий

Кафедра общей информатики

Программка

ДИСЦИПЛИНЫ Математическая логика

ЦИКЛ* ЕН — Общие математические и естественнонаучные дисциплины

НАПРАВЛЕНИЕ ПОДГОТОВКИ БАКАЛАВРОВ 230100.62 «ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»

Создатель Пальчунов Дмитрий Евгеньевич, д.ф.-м.н., доцент

(ФИО, ученая степень, ученое звание)

Новосибирск 2009

* Наименование цикла дисциплин в согласовании Учебно-методическое и информационное обеспечение дисциплины (курса) с ГОС ВПО

Программка дисциплины «Математическая логика» составлена в согласовании с требованиями к неотклонимому минимуму содержания и уровню подготовки бакалавра по циклу «Общих математических и естественнонаучных дисциплин» Федеральных муниципальных образовательных эталонов высшего проф образования по направлению 230100.62 «Информатика и вычислительная техника».

Цели и задачки дисциплины (курса)

Дисциплина (курс) «Математическая логика Учебно-методическое и информационное обеспечение дисциплины (курса)» имеет собственной целью ознакомление студентов с основами теории множеств, теории моделей и теории вычислимости. Основной целью освоения дисциплины является приобретение студентами теоретических познаний и способностей решения задач по теории множеств, логике выражений, логике предикатов, теории моделей, теории алгоритмов и теории вычислимости, также компетенций по формализации дискретных задач а математическом языке Учебно-методическое и информационное обеспечение дисциплины (курса).

Для заслуги поставленной цели выделяются задачки курса:

1) исследование теоретической части курса в согласовании с программкой

2) решение цикла задач по курсу в согласовании с программкой

3) сдача коллоквиума

4) выполнение контрольных работ

5) сдача экзаменов в согласовании с учебным планом.

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

В итоге освоения дисциплины студент должен:

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

Знать содержание программки курса, главные понятия и аксиомы теории множеств, теории моделей, теории алгоритмов

Уметь решать задачки по математической логике, теории моделей и теории алгоритмов.

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

Вид учебной работы Всего часов Семестры
1 2
Общая трудозатратность дисциплины
Аудиторные занятия, в том числе:
Лекции
Семинары
Лабораторные Учебно-методическое и информационное обеспечение дисциплины (курса) работы - - -
Самостоятельная работа, в том числе:
Курсовой проект
Реферат
Расчетные работы
Другие виды самостоятельной работы
Выполнение домашних заданий
Подготовка к контрольным работам
подготовка к коллоквиуму
Вид промежного контроля экзамен экзамен

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

4.1. Новизна курса (научная, содержательная; сравнительный анализ с схожими курсами в Рф и за рубежом).

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

4.2. Направленный на Учебно-методическое и информационное обеспечение дисциплины (курса) определенную тематику план курса (рассредотачивание часов по видам учебной работы).

Семестр 1

№ п/п Наименование тем и разделов ВСЕГО (часов) Аудиторные занятия (часов), в том числе Самостоятельная работа (часов)
Лекции Семинары Лаб. работы
Базы теории множеств
Логика выражений
Логика предикатов
Базы теории алгоритмов
Дела и функции.
Мощность огромного количества
Булевы Учебно-методическое и информационное обеспечение дисциплины (курса) алгебры
Секвенциальное исчисление выражений.
Семантика исчисления секвенций.
Семантика исчисления секвенций.
Гомоморфизм и изоморфизм алгебраических систем.
Итого по курсу:

Семестр 2

№ п/п Наименование тем и разделов ВСЕГО (часов) Аудиторные занятия (часов), в том числе Самостоятельная работа (часов)
Лекции Семинары Лаб. работы
Секвенциальное исчисление предикатов
Аксиома о полноте
Исчисление предикатов гильбертовского типа Учебно-методическое и информационное обеспечение дисциплины (курса)
Базы теории моделей
Машины Тьюринга
Универсальные рекурсивные функции
Клиниевская нумерация
Рекурсивные и рекурсивно-перечислимые огромного количества
Алгоритмически разрешимые и неразрешимые препядствия
Скулемовские и эрбрановы обычные формы. Аксиома Эрбрана
Итого по курсу: -

4.3. Содержание разделов и тем курса.

Семестр

Огромного количества и операции над ними. Простые теоретико-множественные тождества.

Язык логики Учебно-методическое и информационное обеспечение дисциплины (курса) выражений. Понятие формулы. Таблицы истинности. Эквивалентность формул. Связь теоретико-множественных тождеств и тождеств логики выражений. Главные тождества логики выражений и теории множеств. Обычные формы. Приведение формулы к СДНФ и СКНФ.

Понятие алгебраической системы, алгебры, модели. Примеры. Термы и формулы логики предикатов. Истинность формулы на модели. Тождественно Учебно-методическое и информационное обеспечение дисциплины (курса) настоящие и выполнимые формулы. Семантическая эквивалентность формул. Главные тождества логики предикатов.

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

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

Аксиома Кантора-Бернштейна, аксиома Кантора. Счётные огромного количества. Счётность огромного количества слов в конечном алфавите. Континуум. Несчётность огромного количества вещественных чисел Учебно-методическое и информационное обеспечение дисциплины (курса). Равномощность огромного количества вещественных чисел и огромного количества всех подмножеств огромного количества натуральных чисел. Бесконечность класса безграничных мощностей. Континуум-гипотеза и обобщённая континуум-гипотеза. Ординальные и катигоричные числа.

Множество-степень, понятие и главные характеристики булевой алгебры. Примеры. Атомные и безатомные элементы булевых алгебр. Конечные булевы алгебры, аксиома Учебно-методическое и информационное обеспечение дисциплины (курса) Стоуна для конечных булевых алгебр.

· Секвенциальное исчисление выражений.

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

Аксиома о правильности. Аксиома о подстановке. Аксиома о подмене. Аксиома о существовании КНФ. Аксиома о полноте исчисления секвенций. Аксиома об адекватности

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

· Гомоморфизм и изоморфизм алгебраических систем.

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

2 семестр

Секвенциальное исчисление предикатов, теоремы и правила вывода. Аксиома о правильности. Допустимые правила вывода. Аксиома о подмене Учебно-методическое и информационное обеспечение дисциплины (курса). Вывод главных эквивалентностей. Приведение формулы к предваренной обычной форме.

Полные теории. Аксиома о существовании модели. Аксиома Гёделя о полноте и аксиома компактности Мальцева. Аксиома Мальцева о расширении. Понятие о необычных моделях. Существование необычной модели математики.

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

Обогащение модели константами. Простая и полная диаграммы. Подмодели и расширения, связь с универсальными и экзистенциальными формулами. Простые расширения и подмодели, простые вложения. Аспект элементарности вложения. Аксиомы Ливенгейма-Скулема. Феномен Скулема. Аксиоматизируемые классы. Теория класса и класс теории Учебно-методическое и информационное обеспечение дисциплины (курса). Естественно аксиоматизируемые классы. Характеризация классов, замкнутых относительно подмоделей и расширений. Интерполяционная аксиома Крейга (без подтверждения) и её следствия. Очевидная и неявная определимость. Аксиома Бета об определимости (без подтверждения).

Верно вычислимые функции на машинах Тьюринга. Аксиома о правильной вычислимости частично-рекурсивных функций. Шифровка машин Тьюринга. Аксиома о обычной Учебно-методическое и информационное обеспечение дисциплины (курса) форме Клини. Эквивалентность классов вычислимых функций. Тезис Чёрча.

Универсальные рекурсивные функции. Несуществование универсальной примитивно рекурсивной функции и универсальной общерекурсивной функции, существование универсальной отчасти рекурсивной функции.

Клиниевская нумерация. s-m-n аксиома. Аксиома о недвижной точке. Аксиома о рекурсии. Аксиома Райса.

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

Формальная математика Пеано. Гёделевская нумерация. Представимость рекурсивных функций в математике Пеано Учебно-методическое и информационное обеспечение дисциплины (курса). Аксиома Гёделя о неполноте. Разрешимые и неразрешимые теории. Аксиома Чёрча о неразрешимости логики предикатов. Аксиома Гёделя о неразрешимости математики.

4.4. Список примерных контрольных вопросов и заданий для самостоятельной работы.

  1. Дайте определение конечной булевой алгебры. Обоснуйте аксиому Стоуна для конечных булевых алгебр.
  2. Обоснуйте аксиому об эквивалентных определениях Рекурсивно-перечислимых множеств.
  3. Обоснуйте аксиому о Учебно-методическое и информационное обеспечение дисциплины (курса) существовании модели, случай с равенством.
  4. Обоснуйте аксиому о существовании модели, случай без равенства.

4.5. Примерная тема рефератов, курсовых работ.

Не предвидено.

Учебно-методическое и информационное обеспечение дисциплины (курса)

5.1. Примерный список вопросов к зачету (экзамену) по всему курсу.

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

1. Аксиома Геделя о полноте и аксиома компактности Мальцева.

2. Оператор ограниченной минимизации.

3. Секвенциальное исчисление выражений. Аксиома о полноте исчисления секвенций.

4. Существование Учебно-методическое и информационное обеспечение дисциплины (курса) частичной универсальной вычислимой функции.

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

  1. Ершов Ю.Л., Палютин Е.А. Математическая логика, М.: Наука. 1987. –336 с.
  2. Лавров И.А., Максимова Л.Л. Задачки по теории множеств, математической логике и теории алгоритмов, М.: Физмалит. 2001. 256 с.

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

1. Гончаров С.С., Дроботун Б.Н., Никитин А.А. Методические Учебно-методическое и информационное обеспечение дисциплины (курса) нюансы исследования алгебраических систем высшем учебном заведении. Новосибирск: НГУ, 2007.


uchebno-metodicheskoe-posobie-po-proizvodstvennoj-praktike-dlya-studentov-specialnosti-060105-mediko-profilakticheskoe-delo-ekaterinburg-2012.html
uchebno-metodicheskoe-posobie-po-uchebnoj-praktike-dlya-studentov-specialnosti-060105-mediko-profilakticheskoe-delo-ekaterinburg-2012.html
uchebno-metodicheskoe-posobie-po-vipolneniyu-vipusknoj-kvalifikacionnoj-raboti-razrabotano-v-sootvetstvii-s-trebovaniyami-gosudarstvennogo-obrazovatelnogo-standarta-po-napravleniyu-210300-stranica-5.html