III. Элементы теории графов

II. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ.

I. ДИСКРЕТНЫЕ МНОЖЕСТВА.

Докажите тождества двумя способами:

а) используя определения равенства множеств и операций над множествами;

б) с помощью алгебры логики.

1.	2.
3.	4.
5.	6.
7.	8.
9.	10.
11.	12.
13.	14.
15.	16.
17.	18. ;
19. ;	20.

Для заданной булевой функции трех переменных:

а) постройте таблицу истинности, найти двоичную форму булевой функции и привести функцию к СДНФ и СКНФ,

б) найдите двумя способами многочлен Жегалкина и ответить на вопрос, является ли данная булева функция линейной,

в)с помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ. СДНФ, СКНФ.

1. ;	2. ;	3. ;
4. ;	5. ;	6. ;
7. ;	8. ;	9. ;
10. ;	11. ;	12. ;
13. ;	14. ;	15. ;
16. ;	17. ;	18. ;
19. ;	20. .

В задачах 1-10 требуется составить структурную матрицу для данного орграфа (или графа) и, методами булевой алгебры, найти все пути P_ijиз вершины iв вершину j, затем найти все сечения S_ijмежду этими вершинами. В данном задании (чтобы исключить возможные неясности графического рисунка) указываются все ориентированные ребра, причем запись (2-4) означает, что 2 вершина связана с 4-й, а обратной связи нет.

Напомним, что для нахождения путей из вершины iв вершину jнужно раскрывать минор структурной матрицы M_ji(вычеркивать из структурной матрицы строчку с номером jи столбец с номером i). Сечения же находятся отрицанием путей (конъюнкция меняется на дизъюнкцию и наоборот)

1. Дан орграф. Имеется 2 ориентированных ребра: (2-5) и (3-4); i=3, j=1.

2. Дан орграф. Имеется 2 ориентированных ребра: (2-3) и (2-4); i=4, j=6.

3. Дан орграф. Имеется 2 ориентированных ребра: (2-3) и (2-4); i=4, j=6.

4. Дан орграф. Имеется 2 ориентированных ребра: (6-2) и (5-4); i=3, j=5.

5. Дан орграф. Имеется 4 ориентированных ребра: (3-2), (3-4), (2-5) и (1-6); i=3, j=1

6. Дан орграф. Имеется 4 ориентированных ребра: (2-3), (3-5), (5-4) и (4-6); i=3, j=2

7. Дан орграф. Имеется 3 ориентированных ребра: (2-1), (2-3) и (4-5); i=2, j=4

8. Дан орграф. Имеется 2 ориентированных ребра: (2-1) и (5-3); i=3, j=1

9. Дан орграф. Имеется 2 ориентированных ребра: (2-3) и (5-2); i=4, j=6

10. Дан орграф. Имеется 3 ориентированных ребра: (2-1), (4-3) и (3-5); i=2, j=4

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

1. Капитонов Ю.В. и др. Лекции по дискретной математике. СПб. 2004.

2. ЕрусалимскийЯ.М. Дискретная математика. М.: Вузовская книга, 2005.

3. Судоплатов СВ., Овчинникова Е.В. Элементы дискретной математики. М.-Новосибирск: ИНФРД-М НГТУ, 2002.

4. Нефёдов В.Н., Осипова В.А. Курс дискретной математики М.: Изд-во МАИ, 1992.

5. Кузнецов О. П. Дискретная математика для инженеров. М., 2005.

6. Романовский И. В. Дискретный анализ. СПб.-М., 2000.

7. Горбатов В.А. Фундаментальные основы дискретной математики. М.: Наука; Физматлит, 2000.

8. Шапорев С Д. Математическая логика. Курс лекций и практических за­нятий. СПб.: БХВ-Петербург, 2005.

Дата добавления: 2014-11-07