Булевы функции и теория графов
Отношение Р и наличие стандартных свойств: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность. Графы и матрицы замыканий отношения Р. Таблица значений, граф и матрица функции f. Исследование М на линейность (полноту).
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 06.06.2011 |
| Размер файла | 3,3 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Задание
Дано:
· Универсум
· Множества , ,
· Бинарные отношения
· Функция
Требуется:
1. Найти
2. Решить уравнение
3. Построить графы и матрицы отношений P и Q, указать , ,
4. Исследовать отношение Р на наличие стандартных свойств (рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность).
5. Построить граф и матрицу отношения , указать , .
6. Построить граф и матрицу отношения , указать , .
7. Построить графы и матрицы замыканий отношения Р:
. Для каждого из замыканий указать и.
8. Найти, построить естественную проекцию :.
9. Построить таблицу значений, граф и матрицу функции f. Указать .
10. Построить граф и матрицу отношения .
11. Найти , построить индуцированное отображение : .
12. Построить граф и матрицу отношения М. Указать , .
13. Доказать, что отношение М есть отношение строгого порядка в А.
14. Исследовать М на линейность (полноту).
15. Интерпретируя отношение М как «меньше», найти в множестве А относительно М минимальные и максимальные, наименьшие и наибольшие элементы (если таковые существуют).
Решение
1. Найти
2. Решить уравнение
3. Построить графы и матрицы отношений P и Q, указать , ,
рефлексивность симметричность граф матрица
4. Исследовать отношение Р на наличие стандартных свойств (рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность).
По матрице отношения Р определяем его свойства:
1. Не рефлексивно, т.к. на главной диагонали имеются нули.
2. Не антисимметрично, т.к. на главной диагонали имеются единицы.
3. Не симметрично
4. Не антисимметрично
5. Для определения является ли отношение транзитивным, возведем его матрицу в квадрат:
По полученной матрице видно, что отношение Р не транзитивно.
5. Построить граф и матрицу отношения , указать , .
6. Построить граф и матрицу отношения , указать , .
7. Построить графы и матрицы замыканий отношения Р: . Для каждого из замыканий указать и.
8. Найти, построить естественную проекцию :.
9. Построить таблицу значений, граф и матрицу функции 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. Построить граф и матрицу отношения .
или в матричной форме
11. Найти , построить индуцированное отображение : .
12. Построить граф и матрицу отношения М. Указать , .
13. Доказать, что отношение М есть отношение строгого порядка в А.
Отношение называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно. По матрице отношении М:
1. Отношение антирефлексивно, т.к. на главной диагонали нет 1.
2. Отношение антисимметрично, т. к. при aRb и bRa a=b.
3. Для проверки на транзитивность возведем матрицу отношения в квадрат:
Сравнивая полученную матрицу с исходной видим, что отношение транзитивно.
Следовательно, отношение М является отношением строгого порядка.
14. Исследовать М на линейность (полноту).
Рассмотрим отношения связности:
На основе этого строим ранжированный граф:
Граф представляет собой прямую линию, т.е. в нем нет параллельных вершин, следовательно, отношение М линейно.
15. Интерпретируя отношение М как «меньше», найти в множестве А относительно М минимальные и максимальные, наименьшие и наибольшие элементы (если таковые существуют).
Рассмотрим ранжированный граф.
В графе нет параллельных вершин, поэтому минимальный элемент является наименьшим, а максимальный - наибольшим. Наименьший элемент - 3, наибольший элемент - 7.
Размещено на Allbest.ru
Подобные документы
Построение логических взаимосвязей между цветами при помощи аппарата дискретной математики. Структуры объекта в виде множеств, граф отношений между ними. Исследование на рефлексивность, транзитивность, симметричность. Матрицы смежности и инцидентности.
контрольная работа [129,4 K], добавлен 07.06.2010Разработка логико-формальной модели описания методики изготовления винных изделий. Разделение ингредиентов и продукции на множества. Исследование на рефлексивность, транзитивность, симметричность. Построение графа, матрицы смежности и инцидентности.
контрольная работа [165,2 K], добавлен 07.06.2010Теоретико-множественная и геометрическая форма определения графов. Матрица смежностей вершин неориентированного и ориентированного графа. Элементы матрицы и их сумма. Свойства матрицы инцидентности и зависимость между ними. Подмножество столбцов.
реферат [81,0 K], добавлен 23.11.2008Ориентированные и неориентированные графы: общая характеристика, специальные вершины и ребра, полустепени вершин, матрицы смежности, инцидентности, достижимости, связности. Числовые характеристики каждого графа, обход в глубину и в ширину, базис циклов.
курсовая работа [225,5 K], добавлен 14.05.2012Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.
реферат [368,2 K], добавлен 13.06.2011Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа [145,5 K], добавлен 19.07.2011Граф как совокупность объектов со связями между ними. Характеристики ориентированного и смешанного графов. Алгоритм поиска кратчайшего пути между вершинами, алгоритм дейкстры. Алгебраическое построение матрицы смежности, фундаментальных резервов и циклов.
методичка [29,4 M], добавлен 07.06.2009Математическое описание системы автоматического управления с помощью графов. Составление графа и его преобразование, избавление от дифференциалов. Оптимизации ориентированных и неориентированных графов, составления матриц смежности и инцидентности.
лабораторная работа [42,2 K], добавлен 11.03.2012Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.
дипломная работа [272,5 K], добавлен 05.06.2014Типы бинарных отношений. Изображение графов в виде схемы. Цикл в графе, совпадение его начальной и конечной вершины. Понятие достижимости в теории графов, их математические свойства. Частично упорядоченное множество как один из типов бинарного отношения.
контрольная работа [116,5 K], добавлен 04.09.2010
