Основные законы булевой алгебры. СДНФ и СКНФ
2.1.По таблице истинности формулы 
найти её СДНФ и СКНФ и упростить:
| 
| 
| Номера вариантов | ||||||||||||||||||||||||
2.2.Упростить формулу двумя способами: при помощи таблицы истинности (использовать СДНФ или СКНФ) и элементарными преобразованиями.
Основные структуры:
| 1. |  
| 112. | 
| 23. | 
|
| 2. | 
| 113. | 
| 24. | 
|
| 3. | 
| 1 14. | 
| 25. | 
|
| 4. | 
| 1 15. | 
| 26. | 
|
| 5. | 
| 1 16. | 
| 27. | 
|
| 6. | 
| 1 17. | 
| 28. | 
|
| 7. | 
| 1 18. | 
| 29. | 
|
| 8. | 
| 1 19. | 
| 30. | 
|
| 9. | 
| 2 20. | 
| 31. | 
|
| 10. |
| 2 21. | 
| 32. | 
|
| 11. | 
| 2 22. | 
| 33. | 
|
Раздел III. Составные структуры.
Тема III. 1. Основные понятия теории графов.
Определение графа, его элементы. Виды графов. Матрицы смежности и инцидентности.
3.1.1. Для графов, приведенных на рис.1., выполните следующие задания:
1) определите степени и полустепени вершин;
2) укажите содержащиеся в них:
а) контуры (циклы),
б) петли,
в) узлы,
г) висячие вершины;
3) определите, какие из графов являются:
а) ориентированными,
б) однородными,
в) полными,
г) мультиграфами.
1. х2 х3 2. х2 х3
х1 х4
х1 х4
х3 х3
3. х2 4.
х4 х2 х4
х1 х5
х1 х5
3.1.2. По заданным полустепеням вершин постройте, если это возможно, ориентированный граф:
1) Р+(хi)=1, P_(xi)=1, i=1,…,4;
2) P+(x1)=P+(x2)=P_(x2)=P_(x3)=1,
P+(x3)=P_(x1)=2;
3) P+(xi)=i, P_(xi)=6-i, i=1,…,5.
3.1.3. По заданным степеням вершин постройте, если это возможно, неориентированный граф:
1) P(xi)=3, i= 1,…,4;
2) P(xi)=i, i=1,…,5;
3) P (x1)=1, P (x2)=2, P (x3)=7.
3.1.4. Определите, являются ли следующие графы эйлеровыми (гамильтоновыми). Если да, то укажите эйлеров (гамильтонов) цикл.
1. х2 х3 2. х2 х3
х6
х5 х6 х4
х1 х4 х1 х5
х3 х4 х5
4.
3. х1 х9 х10 х6 х2 х3
х1 х8 х1 х7 х8 х4
 |
х6 х5
`
3.1.5. Укажите, если он существует, изоморфизм следующих графов:
1. х2 х3 у2 у3
и
х1 х4
у1 у4
у2 у3
2. х2 х3
и
у1 у4
х1 х4
3. х2
у2 у3
и
х4
х1 х3 у1 у4
х3 у2 у3
4.
х2 х4
и
у1 у4
х1 х5
у5
3.1.6. Перечислите все неизоморфные между собой подграфы данного графа:
 |
1. 2.
 |
3.1.7. Являются ли следующие графы плоскими:
1. 2. х3 х4 х5
х2 х6
х7
х1 х8
3.1.8. В графе 4) из №1.4.:
1) слейте вершины: а) х2 и х4, б) х2 и х5;
2) стяните ребро: а) (х8х4), б) (х7х5).
3.1.9. Для графов из №1.1. составьте матрицы смежности и инцидентности.
3.1.10. По данной матрице смежности постройте ориентированный граф и, если это возможно, неориентированный граф. Определите степени и полустепени вершин.
1) 0 1 0 2) 0 1 1 3) 0 1 1 1 4) 0 1 1 1
1 0 1 1 0 0 0 0 0 0 1 0 0 0
1 0 0 1 0 0 0 1 0 1 0 1 0 1
0 1 1 0 1 0 0 1
3.1.11. По данной матрице инцидентности постройте граф. Определите степени (полустепени) вершин.
1) 
2) 
; 3) 
; 4) 
5) 
; 6) 
Тема III.2. Приложение теории графов к решению задач.