Тема: Булевы функции и теория графов

  • Вид работы:
    Контрольная работа
  • Предмет:
    Математика
  • Язык:
    Русский
  • Формат файла:
    MS Word
  • Размер файла:
    771,82 kb
Булевы функции и теория графов
Булевы функции и теория графов
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

Задание

Дано:

·Универсум

·Множества , ,

·Бинарные отношения

·Функция

Требуется:

. Найти

. Решить уравнение

. Построить графы и матрицы отношений P и Q, указать , ,

. Исследовать отношение Р на наличие стандартных свойств (рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность).

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

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

. Построить графы и матрицы замыканий отношения Р:

. Для каждого из замыканий указать и.

. Найти, построить естественную проекцию :.

. Построить таблицу значений, граф и матрицу функции f. Указать .

. Построить граф и матрицу отношения .

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

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

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

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

Решение

. Найти

. Решить уравнение

3. Построить графы и матрицы отношений P и Q, указать , ,

рефлексивность симметричность граф матрица

. Исследовать отношение Р на наличие стандартных свойств (рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность).

По матрице отношения Р определяем его свойства:

.Не рефлексивно, т.к. на главной диагонали имеются нули.

.Не антисимметрично, т.к. на главной диагонали имеются единицы.

.Не антисимметрично

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

По полученной матрице видно, что отношение Р не транзитивно.

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


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

. Построить графы и матрицы замыканий отношения Р: . Для каждого из замыканий указать и.

. Найти, построить естественную проекцию :.

. Построить таблицу значений, граф и матрицу функции f. Указать .

x12345678910f(x)5712243211

10. Построить граф и матрицу отношения .

или в матричной форме

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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


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

Похожие работы

 

Не нашел материал для курсовой или диплома?
Поможем написать качественную работу
Без плагиата!