Название: Булевы функции и теория графов
Вид работы: контрольная работа
Рубрика: Математика
Размер файла: 2.15 Mb
Скачать файл: referat.me-215295.docx
Краткое описание работы: Отношение Р и наличие стандартных свойств: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность. Графы и матрицы замыканий отношения Р. Таблица значений, граф и матрица функции f. Исследование М на линейность (полноту).
Булевы функции и теория графов
Задание
Дано:
· Универсум
· Множества ,
,
· Бинарные отношения
· Функция
Требуется:
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.
Похожие работы
-
Двумерная кластеризая по предельному расстоянию. Дискретная математика
Изучение основных вопросов теории графов и области ее применения на практике. Разработка алгоритма кластеризации по предельному расстоянию и построение минимального остовного дерева каждого кластера. Результаты тестирований работы данного алгоритма.
-
Математика матрица
Матрицы Матрица - прямоугольная (в частном случае квадратная) таблица с числами. Матрица m × n - это таблица из m строк и n столбцов. Если m = n, матрицу называют квадратной матрицей порядка n.
-
Основы дискретной математики
Минимизация заданного выражения алгебры множеств на основании известных свойств. Анализ заданного бинарного отношения в общем виде. Вывод формул булевых функций для каждого элемента и схемы в целом. Преобразование формулы булевой функции логической схемы.
-
Дискретная математика
bookfoldsheets0 Федеральное агентство по образованию РФ «ДИСКРЕТНАЯ МАТЕМАТИКА» (КОНСПЕКТ ЛЕКЦИЙ) Преподаватель: профессор, Архипов Игорь Константинович МНОЖЕСТВА
-
Операции на графах
Операции на графах позволяют образовывать новые графы из нескольких более простых. Операции на графах без параллельных ребер. Объединение графов. Свойства операции объединения т, которые следуют из определения операции и свойств операций на множествах.
-
Свойства бинарных отношений
Типичные примеры рефлексивных бинарных отношений. Понятие множества и его элементов. Операции над множествами: объединение, пересечение и разность. Декартово произведение множеств. Отношения функциональные, эквивалентности, порядка. Отношения степени n.
-
Матрицы графов
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Кафедра информатики РЕФЕРАТ На тему: «Матрицы графов» МИНСК, 2008 В теоретико-множественной и геометрической форм определения (задания) графов, часто используется матричная форма их представления. Существуют различные виды матриц графов, однако все они, как правило, полностью передают основные свойства графов.
-
Структуры данных
Постановка задачи. Основные понятия и определения. Абстрактные структуры данных.
-
Графы Основные понятия
Министерство образования и науки Российской Федерации Курский государственный технический университет Кафедра ПО ВТ и АС Лабораторная работа № 1 Графы. Основные понятия
-
Логика формальная и графическая модель описания изготовления винных изделий
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ Государственный университет информатики и искусственного интеллекта Кафедра системного анализа и моделирования