Дискретная математика и математическая логика

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

«УТВЕРЖДАЮ»

Декан

факультета прикладной математики

и информатики

«___ »______________2006 г.

РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНы

Дискретная математика и математическая логика

ООП:

080801 – Прикладная информатика в менеджменте,

квалификация – информатик - менеджер

Факультет прикладной математики и информатики

Курс 1 семестр 1

Лекции – 51 час

Практические /лабораторные работы – 51/0 час

Расчетно-графическая работа – семестр 1

Самостоятельная работа – 30 час

Экзамен – 1 семестр

Всего – 132 часа

Новосибирск

2006

Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности 351400 – Прикладная информатика (по областям).

Регистрационный номер 52 мжд/СП, дата утверждения 14.03.2000 г.

Шифр дисциплины в ГОС: ЕН. Ф.01, федеральный компонент

Рабочая программа обсуждена на заседании кафедры прикладной математики (протокол № 3 от 16 мая 2006 г.).

Программу разработал

доц., к. т.н., доц.,

доц., к. т.н.

Ответственный за основную

образовательную программу:

заведующий кафедрой “Прикладная математика”,

д. т.н., профессор _________________

Дополнения и изменения к рабочей программе на 20 /20 учебный год

В рабочую программу вносятся следующие изменения: __________________

Рабочая программа пересмотрена и одобрена на заседании кафедры «___» __________20 г.

Заведующий кафедрой «___» ______20 г.

1. Внешние требования

Таблица 1

Требования ГОС к обязательному минимуму содержания учебной дисциплины

Шифр дисциплины	Содержание учебной дисциплины	Часы
ЕН. Ф.01	Дискретная математика: логические исчисления, графы, комбинаторика.	132

1.3.Квалификационные требования

Информатик-менеджер должен осуществлять профессиональную деятельность и уметь решать задачи, соответствующие его квалификации. Он должен обладать:

Þ  специальной подготовкой в предметной области;

Þ  специализацией, определяемой перечнем дисциплин из предметной области и из области информатики;

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

Информатик-менеджер должен знать:

Þ  задачи предметной области и методы их решения.

Информатик-менеджер должен уметь:

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

Информатик-менеджер должен владеть:

Þ  методиками анализа предметной области и проектирования профессионально-ориентированных информационных систем.

Информатик-менеджер должен иметь опыт:

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

Þ  разработки проектных решений и их реализации в заданной инструментальной среде.

7. 1.Требования к профессиональной подготовленности выпускника

Информатик - менеджер должен

знать и уметь использовать:

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

иметь опыт:

Þ  употребления математической символики для выражения количественных и качественных отношений объектов;

Þ  аналитического и численного решения алгебраических уравнений;

иметь представление:

Þ  о математике как особом способе познания мира, общности ее понятий и представлений.

2. Особенности (принципы) построения дисциплины

Таблица 2

Особенности (принципы) построения дисциплины

Особенность (принцип)	Содержание
Основание для введения дисциплины в учебный план специальности	Стандарт специальности, дисциплина федерального компонента
Адресат дисциплины	Студенты специальности: 080801 – Информатик - менеджер
Главная цель дисциплины	изучение основ математической логики, теории доказательств, развитие логического мышления.
Ядро дисциплины	задачи теории множеств, математической логики, исчисления предикатов, теории графов
Требования к начальной подготовке, необходимые для успешного усвоения дисциплины	Для успешного изучения курса студенту необходимо знать школьный курс математики и информатики
Уровень требований по сравнению со Стандартом	Соответствует требованиям стандарта
Объём курса в часах	51 час лекций, 51час практических занятий
Основные понятия дисциплины	Множество, булева алгебра, булева функция, предикат, истинность, граф, комбинаторная конфигурация
Описание основных точек контроля	Промежуточный контроль – контроль выполнения домашних заданий, контрольные работы, защита РГЗ. Итоговый контроль – экзамен

3. Цели курса

Номер цели	Содержание цели
Студент будет иметь представление:
1	о теории множеств
2	о булевой алгебре
3	о математической логике, исчислении высказываний и предикатов
4	о системах счисления и комбинаторике
5	о теории графов
Студент будет знать
6	основные алгоритмы перевода чисел между системами счисления
7	основные понятия и законы теории множеств
8	основы теории переключательных функций, алгоритмы приведения булевых функций к нормальной форме и построения минимальных форм, понятие полноты системы функций и способы её проверки по классам Поста
9	основы исчисления высказываний, алгоритмы и приёмы построения выводов и доказательств
10	основы исчисления предикатов, приёмы построения и описания моделей на языке исчисления предикатов, способы проверки истинности утверждений, основы формальной логики Аристотеля
11	Основные понятия и законы комбинаторики
12	Основные понятия и алгоритмы теории графов
Студент будет уметь:
13	Приводить переключательные функции к дизъюнктивной нормальной форме и строить минимальную форму. Определять полноту системы переключательных функций.
14	Строить и грамотно излагать доказательства, проверять логическую непротиворечивость выводов
15	Описывать модель явления на языке исчисления предикатов
16	Распознавать основные комбинаторные конфигурации и вычислять их количество
17	Определять основные свойства графа, представлять его в виде матрицы, находить компоненты связности и кратчайший путь между вершинами

4. Содержание курса

Структура курса:

Ссылки на цели курса	Часы	Темы лекционных занятий
1, 7, 14	8	Теория множеств. Основные понятия. Понятие множества. Конечные и бесконечные множества. Способы задания множеств. Пустое множество. Универсум. Подмножество. Булеан. Пресечение и объединение множеств. Разность множеств. Дополнение. Диаграммы Эйлера-Венна. Основные свойства операций над множествами. Декартово произведение. Степень. N-местное отношение. Бинарное отношение. Область определения, область значений. Обратное отношение. Образ. Прообраз. Композиция бинарных отношений. Функции и отображения. Свойства функций: инъекция, сюръекция, биекция. Операции. Свойства операции: коммутативность, ассоциативность, дистрибутивность. Специальные бинарные отношения. Диагональ. Полное отношение. Рефлексивность. Иррефлексивность. Симметричность. Антисимметричность. Транзитивность. Разбиение и отношение эквивалентности; отношение порядка
2, 4, 8, 13	2	Переключательные функции. Определение переключательной функции. Набор. Таблица истинности. Переключательные функции двух переменных. Старшинство операций. Схемы из функциональных элементов.
2, 8, 13	5	Булева алгебра. Минимизация булевых функций. Булева формула. Аксиомы дизъюнкции, конъюнкции, отрицания. Правило подстановки. Упрощение с использованием аксиом. Элементарное произведение. Конституэнты нуля и единицы. СДНФ и СКНФ. Теоремы о представимости любой переключательной функции в виде СДНФ и СКНФ. Примеры. Импликанта. Простая импликанта. Сокращенная ДНФ. Лишние импликанты. Тупиковая ДНФ. Минимальная ДНФ. Аналитические методы минимизации: метод Квайна и метод Блэйка. Графическая минимизация. Минимизация при помощи карт Карнапа.
2, 8,13	2	Полнота систем переключательных функций. Функциональные системы с операциями. Функциональная полнота. Функции, сохраняющие ноль. Функции, сохраняющие единицу. Самодвойственность. Монотонность. Алгебра Жегалкина. Линейность. Классы Поста. Замкнутость классов. Сильная теорема Поста. Слабая теорема Поста. Базис.
3, 9, 10, 14, 15	4	Исчисление высказываний. Алфавит. Формула. Система аксиом Клини. Правило вывода. Посылки. Вывод. Доказательство. Примеры. Теорема о дедукции. Применение исчисления высказываний к естественному языку. Анализ рассуждений.
3, 10, 14, 15	10	Исчисление предикатов (ИП). Предикат. Местность предиката. Кванторы. Формула. Аксиомы Клини. Правила вывода. Вывод и доказательство в исчислении предикатов. Связанные и свободные вхождения переменных. Свойства кванторов. Приведенная нормальная форма.. Теорема о дедукции. Применение ИП к естественному языку. Выполнимость формул. Примеры. Модель. Формализация предложений. Исчисление одноместных предикатов как исчисление классов. Теория категорических суждений и силлогизмов Аристотеля. Модусы.
4, 11, 16	6	Комбинаторика. Комбинаторные задачи. Правило суммы. Правило произведения. Закон включений и исключений. Размещения без повторений. Размещения с повторениями. Перестановки. Перестановки с повторениями. Сочетания. Сочетания с повторениями. Свойства сочетаний. Коды. Примеры.
5, 12, 17	6	Основные понятия теории графов. Псевдограф. Вершина. Ребро. Петля. Мультиграф. Граф. Дуги. Ориентированные и неориентированные графы. Геометрический граф. Смежность. Инцедентность. Изоморфизм графов. Геометрическая реализация. Сеть. Маршрут. Цепь. Цикл. Простая цепь. Простой цикл. Степень вершины. Теорема о связи суммарной степени вершин с числом ребер. Лемма о рукопожатиях. Свойства маршрутов, цепей и циклов. Понятие связности. Теорема о разбиении множества вершин. Расстояние. Диаметр. Подграф. Компоненты связности. Остовной подграф. Связность в орграфах. Свойства связных графов. Деревья и леса. Теорема об основных свойствах дерева. Свойства деревьев. Разделяющие множества. Теорема об остовном дереве. Полный граф. Двудольный граф. Точка сочленения. Операции над графами. Удаление вершины, ребра. Дополнение. Подразбиение. Гомеоморфизм. Декартово произведение графов. Объединение графов.
5, 12, 17	2	Планарность. Планарный граф. Плоский граф. Внутренняя грань. Внешняя грань. Теорема Эйлера для связных плоских графов. Непланарные графы. Теорема о непланарности графов Понтрягина-Куратовского I и II типов. Теорема Понтрягина-Куратовского. Теорема Эйлера для несвязных плоских графов. Свойства планарных графов. Алгоритм построения плоского изображения для планарного графа.
5, 12, 17	2	Матричное представление графов. Матрица смежности. Степень матрицы смежности. Матрица инцидентности. Теорема о ранге матрицы инцидентности.
5, 12, 17	4	Классические задачи теории графов. Алгоритм выделения в орграфе сильно связных компонент. Эйлерова цепь, цикл. Теорема Эйлера. Гамильтонова цепь, цикл. Задача коммивояжера.

Темы практических занятий

Ссылки на цели курса	Часы	Темы	Решая задачи, студент:
4, 6	3	Системы счисления	·  изучает позиционные и непозиционные системы счисления, римскую систему счисления как пример непозиционной системы, двоичную, восьмеричную и шестнадцатеричную системы. ·  применяет основные действия арифметики ·  использует алгоритмы перевода чисел
1, 3, 7, 14	9	Теория множеств. Основные понятия.	·  изучает способы задания множеств, основные операции над множествами ·  учится грамотно излагать доказательства ·  использует основные приёмы доказательств
2, 8, 13	2	Переключательные функции	·  строит таблицы истинности ·  использует основные законы для преобразования формул ·  строит СДНФ и СКНФ
2, 8, 13	4	Булева алгебра. Минимизация булевых функций.	·  использует различные алгоритмы минимизации функций
2, 8, 13	2	Полнота систем булевых функций	·  определяет принадлежность заданных функций классам Поста ·  строит полную систему функций
3, 9, 14, 15	4	Исчисление высказываний	·  применяет исчисление высказываний для формализации высказываний на естественном языке ·  строит выводы и доказательства в исчислении высказываний
3, 14, 15	6	Исчисление предикатов	·  сроит модели в исчислении предикатов ·  формализует высказывания ·  изучает теорию силлогизмов
4, 11, 16	6	Комбинаторика	·  распознает основные комбинаторные конфигурации ·  использует основные законы комбинаторики для решения задач
5, 12, 14, 17	6	Основные понятия теории графов	·  решает задачи с использованием основных определений и теорем ·  оперирует основными понятиями теории графов ·  учится распознавать изоморфные графы
5, 12, 17	2	Планарность	·  доказывает некоторые свойства планарных графов
5, 12, 17	3	Матричное представление графов	·  строит матрицы смежности и инцидентности ·  использует матричные алгоритмы исследования свойств графа

5. Учебная деятельность

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

Первая контрольная работа проводится по 2 и 3 модулю, вторая – по 4 и 5 модулю.

Расчётно-графическое задание включает в себя индивидуальный для студента набор задач по модулям 2, 3 и 5.

6. Правила аттестации студентов по учебной дисциплине

Знания и умения студентов по дисциплине оцениваются как по контрольным работам и РГЗ, так и в ходе итогового экзамена.

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

Итоговый экзамен сдается письменно по билетам, пример одного из которых приведён в приложении. Студент, не согласный с оценкой за письменную работу, может повысить оценку на собеседовании. Оценку «удовлетворительно» получает студент, усвоивший не менее 30% материала по каждому из модулей. Оценку «хорошо» получает студент, усвоивший не менее 60% материала по каждому из модулей. Оценку «отлично» получает студент, усвоивший не менее 80% материала по каждому из модулей.

7. Список литературы

7.1. Основной список

1.  , Рояк дискретной математики. Учебное пособие. – Новосибирск: Изд-во НГТУ, 2003.

2.  , Рояк логика: методические указания. – Новосибирск, НГТУ, 1997

3.  , Рояк графов: методические указания. – Новосибирск, НГТУ, 1998

4.  Судоплатов математика: учебник для вузов по технических спец-ей / ; НГТУ Издание 2-е переработанное - М.:Инфра-М; Новосибирск: Издательство НГТУ 2005

7.2. Дополнительный список

5.  “Новое о системах счисления”. - Киев, 1982.

6.  “Рассказы о множествах”. - М., “Наука”, 1969.

7.  “Математическая логика”. - М., “Мир”, 1973

8.  “Комбинаторика”. - М., “Наука”, 1969

9.  “Популярная комбинаторика”. - М., “Наука”, 1975

10., , “Элементы комбинаторики”. - М., “Наука”, 1977

11. “Комбинаторика для программистов”.- М., “Мир”, 1988

12. “Конечные графы и сети”.- М., “Наука”, 1974

13., Адельсон- “Дискретная математика для инженера”. - М., 1988

14. “Компьютерная математика”. - М., “Наука”, 1990

15., , “Теория графов”. - М., 1976

16. “Теория конечных графов”. - Новосибирск, “Наука”, 1969

17. “Теория графов”.- М., “Наука”, 1968

18. “Комбинаторика”. - М., “Мир”, 1973

19. “Теория графов. Алгоритмический подход.”

20., “Задачи по теории множеств, математической логике и теории алгоритмов”. - М, “Наука”, 1975

21.Москинова математика. Математика для менеджера в примерах и упражнениях: Учебное пособие. – М.: Логос, 2000. – 240с.

8. Контролирующие материалы для аттестации студентов по дисциплине

Типовой экзаменационный билет.

1. Построить антисимметричное, не симметричное, транзитивное бинарное отношение.

2. Найти сокращенную ДНФ функции . Выписать СДНФ и СКНФ.

3. В модели , где – множество людей;

" – мужчина"; " – женщина",

" и – супруги", " ребенок ",

" и – один и тот же человек";

записан предикат .

Какому из следующих выражений он соответствует:

1) " брат ", 2) " брат ", 3) " сестра ", 4) " брат", 5) " брат"?

4. Сколько различных десятизначных чисел можно написать, используя цифры 1, 2, 3?

5. Пусть – граф с вершинами, а` его дополнительный граф. Доказать, что по крайней мере один из них не планарный.

6. Построить доказательство ÷¾ .