Дискретная математика и математическая логика
(заочное 2-ое высшее, Екатеринбург)
Содержание курса
I. Теория графов
1. Основные определения: граф как геометрическая фигура и как реляционная модель, маршруты, цепи, циклы, связность, компоненты связности.
2. Способы задания графа. Диаметр, радиус, центры.
3. Эйлеровы циклы и графы. Теорема Эйлера.
4. Гамильтоновы циклы и графы. Теорема Дирака.
5. Деревья, теорема о деревьях.
6. Планарные графы. Укладка на поверхности. Теорема Эйлера о многогранниках. Непланарность графов K5 и K3,3.
7. Критерии планарности: теоремы Понтрягина-Куратовского.
8. Раскраска планарного графа. Теорема о четырех красках.
II. Логика высказываний и булевы функции
1. Высказывания и операции с ними
2. Формулы, равносильность, логическое следствие.
3. Нормальные формы.
4. Булевы функции: замкнутость и полнота.
5. Основные замкнутые классы.
6. Теорема Поста.
Рекомендуемая литература (основная)
1. Замятин и сети: Учеб. пособие. Екатеринбург: Изд-во Урал. ун-та
2. Замятин логика: Учеб. пособие. Екатеринбург: Изд-во Урал. ун-та
Контрольная работа по "Дискретной математике"
(Римская цифра – номер задачи, арабская цифра – номер варианта)
I. Нарисовать обыкновенный граф, множество вершин которого V={1,2,...,7}. Записать матрицу инцидентности. Будет ли граф связным?
1. | 6. |
2. | 7. |
3. | 8. |
4. | 9. |
5. | 10. |
II. Нарисовать граф, заданный матрицей смежности. Вычислить диаметр, радиус, центры графа. Будет ли граф эйлеровым, гамильтоновым? Если да, выписать соответствующий цикл.
1. |
| 5. |
| 9. |
|
2. |
| 6. |
| 10. |
|
3. |
| 7. |
| ||
4. |
| 8. |
|
III. Является ли планарным граф, заданный списком смежности? Если да, нарисовать соответствующий плоский граф, если нет, доказать по признакам планарности.
1.
| 3.
| 5.
| 7.
| 9.
|
2.
| 4.
| 6.
| 8.
| 10.
|
IV. Является ли формула G логическим следствием формул F1,...,Fk? Привести высказывания, соответствующие формулам.
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
V. Привести к СДНФ.
1. | 6. |
2. | 7. |
3. | 8. |
4. | 9. |
5. | 10. |
VI. Является ли полным класс K булевых функций?
1. | 6. |
2. | 7. |
3. | 8. |
4. | 9. |
5. | 10. |
