Булевы функции и теория графов
Задание
Дано:
· Универсум
· Множества ,
,
· Бинарные отношения
· Функция
Требуется:
. Найти
. Решить уравнение
. Построить графы и матрицы отношений P
и Q, указать ,
,
. Исследовать отношение Р на наличие стандартных
свойств (рефлексивность, антирефлексивность, симметричность,
антисимметричность, транзитивность).
. Построить граф и матрицу отношения ,
указать ,
.
. Построить граф и матрицу отношения ,
указать ,
.
. Построить графы и матрицы замыканий отношения
Р:
. Для каждого из
замыканий указать и.
. Найти,
построить естественную проекцию :.
. Построить таблицу значений, граф и матрицу
функции f.
Указать
.
. Построить граф и матрицу отношения .
. Найти ,
построить индуцированное отображение :
.
. Построить граф и матрицу отношения М.
Указать ,
.
. Доказать, что отношение М есть отношение
строгого порядка в А.
. Исследовать М на линейность (полноту).
. Интерпретируя отношение М как «меньше», найти
в множестве А относительно М минимальные и максимальные, наименьшие и
наибольшие элементы (если таковые существуют).
Решение
. Найти
. Решить уравнение
3. Построить графы и матрицы отношений P
и Q, указать ,
,
рефлексивность симметричность граф
матрица
. Исследовать отношение Р на наличие стандартных
свойств (рефлексивность, антирефлексивность, симметричность,
антисимметричность, транзитивность).
По матрице отношения Р определяем его свойства:
. Не рефлексивно, т.к. на главной
диагонали имеются нули.
. Не антисимметрично, т.к. на главной
диагонали имеются единицы.
. Не симметрично
. Не антисимметрично
. Для определения является ли отношение
транзитивным, возведем его матрицу в квадрат:
По полученной матрице видно, что отношение Р не
транзитивно.
. Построить граф и матрицу отношения ,
указать ,
.
. Построить граф и матрицу отношения ,
указать ,
.
. Построить графы и матрицы замыканий отношения
Р: .
Для каждого из замыканий указать и.
. Найти,
построить естественную проекцию :.
. Построить таблицу значений, граф и матрицу
функции f.
Указать
.
x
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
f(x)
|
5
|
7
|
1
|
2
|
2
|
4
|
3
|
2
|
1
|
1
|
10. Построить граф и матрицу отношения .
или в матричной
форме
. Найти ,
построить индуцированное отображение :
.
12. Построить граф и матрицу отношения М.
Указать ,
.
. Доказать, что отношение М есть отношение
строгого порядка в А.
Отношение называется отношением строгого
порядка, если оно антирефлексивно, антисимметрично и транзитивно. По матрице
отношении М:
. Отношение антирефлексивно, т.к. на главной
диагонали нет 1.
. Отношение антисимметрично, т. к. при aRb
и
bRa
a=b.
3. Для проверки на транзитивность возведем
матрицу отношения в квадрат:
Сравнивая полученную матрицу с исходной видим,
что отношение транзитивно.
Следовательно, отношение М является отношением
строгого порядка.
. Исследовать М на линейность (полноту).
Рассмотрим отношения связности:
На основе этого строим ранжированный граф:
Граф представляет собой прямую линию, т.е. в нем
нет параллельных вершин, следовательно, отношение М линейно.
. Интерпретируя отношение М как «меньше», найти
в множестве А относительно М минимальные и максимальные, наименьшие и
наибольшие элементы (если таковые существуют).
Рассмотрим ранжированный граф.
В графе нет параллельных вершин, поэтому
минимальный элемент является наименьшим, а максимальный - наибольшим.
Наименьший элемент - 3, наибольший элемент - 7.