- •Практический раздел
- •Задачи для самостоятельного решения
- •Контрольное задание №2. Получить сднф, скнф, используя таблицу истинности. Построить днф, кнф, упростив выражение.
- •Методические указания
- •Задачи для самостоятельного решения
- •Контрольное задание №3. Упростить схему (рис. 2)
- •Методические указания
- •Задачи для самостоятельного решения
- •Задачи для самостоятельного решения
- •Задачи для самостоятельного решения
- •Методические указания
- •Задачи для самостоятельного решения. В задачах также надо методом Магу найти доминирующие и независимые множеств вершин графа и исследовать граф на наличие эйлерова и гамильтонова циклов
- •Задачи для самостоятельного решения.
- •Алгоритмы на булевых матрицах. Алгоритмы анализа графов и их использование
Задачи для самостоятельного решения. В задачах также надо методом Магу найти доминирующие и независимые множеств вершин графа и исследовать граф на наличие эйлерова и гамильтонова циклов
6.1. |
|
|
|
|
|
|
6.2. |
|
|
|
|
|
|
6.3. |
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
|
1 |
1 |
1 |
|
1 |
1 |
|
1 |
|
1 |
|
1 |
1 |
|
1 |
1 |
|
|
1 |
2 |
1 |
|
1 |
|
|
1 |
2 |
|
|
1 |
|
1 |
|
2 |
|
|
1 |
1 |
1 |
|
3 |
1 |
1 |
|
1 |
1 |
1 |
3 |
|
|
|
1 |
|
1 |
3 |
|
|
|
|
1 |
1 |
4 |
1 |
|
1 |
|
|
1 |
4 |
|
|
|
|
1 |
|
4 |
|
|
|
|
1 |
|
5 |
|
|
1 |
|
|
1 |
5 |
|
|
|
|
|
1 |
5 |
|
|
|
|
|
1 |
6 |
1 |
1 |
1 |
1 |
1 |
|
6 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6.4. |
|
|
|
|
|
|
6.5. |
|
|
|
|
|
|
6.6. |
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
|
1 |
1 |
|
|
1 |
1 |
|
1 |
|
1 |
1 |
|
1 |
|
1 |
1 |
|
1 |
|
2 |
|
|
1 |
|
1 |
|
2 |
|
|
1 |
|
1 |
|
2 |
1 |
|
1 |
1 |
1 |
|
3 |
|
|
|
1 |
|
1 |
3 |
|
|
|
1 |
1 |
1 |
3 |
1 |
1 |
|
|
1 |
1 |
4 |
|
|
|
|
1 |
|
4 |
|
|
|
|
1 |
1 |
4 |
|
1 |
|
|
1 |
1 |
5 |
|
|
|
|
|
1 |
5 |
|
|
|
|
|
1 |
5 |
1 |
1 |
1 |
1 |
|
1 |
6 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
6 |
|
|
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6.7. |
|
|
|
|
|
|
6.8. |
|
|
|
|
|
|
6.9. |
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
|
1 |
|
1 |
|
1 |
1 |
|
1 |
1 |
1 |
1 |
|
1 |
|
1 |
|
1 |
1 |
|
2 |
|
|
1 |
1 |
1 |
1 |
2 |
|
|
|
|
1 |
|
2 |
1 |
|
1 |
|
1 |
1 |
3 |
|
|
|
1 |
1 |
1 |
3 |
|
|
|
1 |
1 |
1 |
3 |
|
1 |
|
1 |
|
|
4 |
|
|
|
|
|
1 |
4 |
|
|
|
|
1 |
1 |
4 |
1 |
|
1 |
|
|
1 |
5 |
|
|
|
|
|
1 |
5 |
|
|
|
|
|
1 |
5 |
1 |
1 |
|
|
|
1 |
6 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
6 |
|
1 |
|
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6.10 |
|
|
|
|
|
|
6.11 |
|
|
|
|
|
|
6.12 |
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
|
1 |
|
1 |
1 |
|
1 |
|
1 |
|
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
|
1 |
2 |
|
|
1 |
|
|
1 |
2 |
1 |
|
1 |
1 |
|
|
2 |
1 |
|
1 |
|
|
|
3 |
|
|
|
1 |
1 |
|
3 |
|
1 |
|
|
1 |
|
3 |
1 |
1 |
|
1 |
1 |
1 |
4 |
|
|
|
|
|
1 |
4 |
1 |
1 |
|
|
1 |
1 |
4 |
1 |
|
1 |
|
1 |
1 |
5 |
|
|
|
|
|
1 |
5 |
1 |
|
1 |
1 |
|
|
5 |
|
|
1 |
1 |
|
1 |
6 |
|
|
|
|
|
|
6 |
1 |
|
|
1 |
|
|
6 |
1 |
|
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6.13 |
|
|
|
|
|
|
6.14 |
|
|
|
|
|
|
6.15 |
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
|
1 |
1 |
|
1 |
1 |
1 |
|
1 |
1 |
1 |
|
|
1 |
|
1 |
|
1 |
1 |
1 |
2 |
|
|
1 |
1 |
|
1 |
2 |
|
|
1 |
1 |
|
1 |
2 |
1 |
|
1 |
1 |
1 |
|
3 |
|
|
|
1 |
1 |
|
3 |
|
|
|
1 |
1 |
1 |
3 |
|
1 |
|
1 |
1 |
1 |
4 |
|
|
|
|
|
1 |
4 |
|
|
|
|
1 |
1 |
4 |
1 |
1 |
1 |
|
1 |
|
5 |
|
|
|
|
|
1 |
5 |
|
|
|
|
|
1 |
5 |
1 |
1 |
1 |
1 |
|
|
6 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
6 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6.16 |
|
|
|
|
|
|
6.17 |
|
|
|
|
|
|
6.18 |
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
|
1 |
|
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
|
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
2 |
|
|
1 |
|
|
|
2 |
|
|
|
1 |
1 |
1 |
2 |
1 |
|
1 |
|
1 |
|
3 |
|
|
|
1 |
|
1 |
3 |
|
|
|
1 |
1 |
|
3 |
1 |
1 |
|
1 |
|
1 |
4 |
|
|
|
|
1 |
|
4 |
|
|
|
|
1 |
1 |
4 |
1 |
|
1 |
|
1 |
|
5 |
|
|
|
|
|
1 |
5 |
|
|
|
|
|
1 |
5 |
1 |
1 |
|
1 |
|
|
6 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
6 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6.19 |
|
|
|
|
|
|
6.20 |
|
|
|
|
|
|
6.21 |
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
|
1 |
1 |
1 |
|
|
1 |
|
1 |
1 |
|
1 |
|
1 |
|
1 |
1 |
|
|
1 |
2 |
|
|
|
1 |
1 |
1 |
2 |
|
|
1 |
|
1 |
|
2 |
1 |
|
1 |
1 |
1 |
1 |
3 |
|
|
|
1 |
1 |
1 |
3 |
|
|
|
|
1 |
1 |
3 |
1 |
1 |
|
1 |
|
|
4 |
|
|
|
|
1 |
1 |
4 |
|
|
|
|
1 |
1 |
4 |
|
1 |
1 |
|
1 |
|
5 |
|
|
|
|
|
1 |
5 |
|
|
|
|
|
1 |
5 |
|
1 |
|
1 |
|
1 |
6 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
6 |
1 |
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6.22 |
|
|
|
|
|
|
6.23 |
|
|
|
|
|
|
6.24 |
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
|
1 |
|
1 |
|
1 |
1 |
|
1 |
1 |
1 |
|
1 |
1 |
|
1 |
|
1 |
|
1 |
2 |
|
|
1 |
|
1 |
|
2 |
|
|
1 |
|
1 |
1 |
2 |
1 |
|
1 |
1 |
1 |
|
3 |
|
|
|
1 |
|
1 |
3 |
|
|
|
|
1 |
|
3 |
|
1 |
|
1 |
1 |
|
4 |
|
|
|
|
1 |
|
4 |
|
|
|
|
|
1 |
4 |
1 |
1 |
1 |
|
1 |
|
5 |
|
|
|
|
|
1 |
5 |
|
|
|
|
|
1 |
5 |
|
1 |
1 |
1 |
|
1 |
6 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
6 |
1 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6.25 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Контрольное задание №7. Решение логических задач методом характеристического уравнения
Условие задачи. В некотором царстве правил король. Однажды он предложил узнику отгадать, в какой комнате находится принцесса, а в какой тигр. Узнику было объявлено, что в каждой комнате находится либо принцесса, либо тигр, однако может оказаться, что сразу в обеих комнатах будет обнаружено по тигру или по принцессе.
На табличках, прикрепленных к двери каждой из комнат, было написано:
-
1. В этой комнате находится принцесса, а в другой комнате сидит тигр.
2. В одной из этих комнат находится принцесса, кроме того, в одной из этих комнат сидит тигр.
Король сообщил узнику, что на одной из таблиц написана правда, на другой – ложь. Какую дверь надо открыть узнику, если он предпочитает принцессу тигру?
Решение.
Формулируем простые высказывания:
«принцесса находится в комнате i»: i=1,2;
- «тигр сидит в комнате i»: i=1,2;
формулируем сложные высказывания, соответствующие условию задачи:
Получаем систему уравнений:
Составляем характеристическое уравнение:
Приведение левой части характеристического уравнения к ДНФ. Реализуем логические функции с помощью матричного представления (рис. 6.1):
Из последней матрицы видно, что ДНФ содержит только одно слагаемое.
Решением уравнения является набор 0110, т.е. принцесса находится в комнате 2, а тигр в комнате 1.