Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://old.hcs.cmc.msu.ru/lectures/DS_2005.htm
Дата изменения: Mon May 16 12:25:41 2005 Дата индексирования: Mon Oct 1 20:35:01 2012 Кодировка: Windows-1251 |
В письменный экзамен могут войти задачи из следующих разделов курса
Способы
определения множеств.
Подмножества,
собственные подмножества. Операции над
множествами. Равенство множеств. Прямое
произведение.
Свойства
множеств. Пустое множество, разбиение
множеств. Законы Де Моргана.
Бинарные
отношения. Свойства бинарных отношений:
рефлексивность, симметричность,
транзитивность.
Представление
отношений с помощью ориентированных графов.
Отношение
эквивалентности. Определение отношений с
помощью классов эквивалентности (классов
смежности).
Размещения. Размещения без повторений.
Перестановки.
Сочетания. Сочетания с повторениями.
Треугольник Паскаля.
Бином Ньютона. Биномиальные коэффициенты.
Число подмножеств конечного множества. Прочие тождества для C(n,k).
Графы: основные понятия; способы представления графов. Ориентированные графы.
Подграфы. Степень вершины.
Цепи, пути и контуры. Эйлеровы и гамильтоновы контуры.
Деревья, их свойства.
Дизъюнктивная нормальная форма. Функция, порождаемая пропозициональной формой. Построение формы, порождающей заданную функцию.
Полные системы связок.
Формальные аксиоматические теории. Вывод. Теорема дедукции.
Цифровые логические схемы. Вентили и типы вентилей. Описание схем с помощью булевских выражений. Синтез схем по таблицам истинности. Эквивалентность схем.
N-ичные
системы счисления.
Понятие
предиката и множества истинности.
Кванторы
общности и существования. Отрицание
квантифицированных высказываний. Связь
между кванторами и связками.
Логика
предикатов, определение языка. Связанные и
свободные переменные. Понятие
интерпретации.
1. Н.К. Верещагин, А. Шень. Начала теории множеств. 2-е издание, испр.- М.: МЦНМО, 2002.
2. С.В. Судоплатов, Е.В. Овчинникова. Элементы дискретной математики: Учебник. М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2003. - 280 с. (Серия "Высшее образование").
3. Б.Н. Иванов. Дискретная математика. Алгоритмы и программы: Учеб. пособие.- М.: Лаборатория Базовых Знаний, 2002 - 288 с.
4. С.В. Яблонский. Введение в дискретную математику: Учеб. пособие для вузов. 2-е изд, перераб. и доп.- М.: Наука, Гл. ред. физ.-мат. лит., 1986.-384 с.
5. А. Шень. Программирование: теоремы и задачи.- М.: МЦНМО, 1995.
6. Э. Мендельсон. Введение в математическую логику.- М.: Наука, 1976.
7. А.Н.Колмогоров, А.Г.Драгалин. Математическая логика.- М.:УРСС, 2004.