Булевы функции и теория графов (стр. 2 из 2)

11. Найти

, построить индуцированное отображение : .

12. Построить граф и матрицу отношения М. Указать

, .

13. Доказать, что отношение М есть отношение строгого порядка в А.

Отношение называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно. По матрице отношении М:

1. Отношение антирефлексивно, т.к. на главной диагонали нет 1.

2. Отношение антисимметрично, т. к. при aRbиbRaa=b.

3. Для проверки на транзитивность возведем матрицу отношения в квадрат:

Сравнивая полученную матрицу с исходной видим, что отношение транзитивно.

Следовательно, отношение М является отношением строгого порядка.

14. Исследовать М на линейность (полноту).

Рассмотрим отношения связности:

На основе этого строим ранжированный граф:

Граф представляет собой прямую линию, т.е. в нем нет параллельных вершин, следовательно, отношение М линейно.

15. Интерпретируя отношение М как «меньше», найти в множестве А относительно М минимальные и максимальные, наименьшие и наибольшие элементы (если таковые существуют).

Рассмотрим ранжированный граф.

В графе нет параллельных вершин, поэтому минимальный элемент является наименьшим, а максимальный – наибольшим. Наименьший элемент – 3, наибольший элемент – 7.