Контрольная работа : Булевы функции и теория графов 


Полнотекстовый поиск по базе:

Главная >> Контрольная работа >> Математика


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




Задание

Дано:

  • Универсум

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

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

  • Функция

Требуется:

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.

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

  • Графы. Решение практических задач с использованием графов (С++)

    Реферат >> Математика
    ... История возникновения теории графов. Родоначальником теории графов принято считать ... E называются гипердугами, а граф называется гиперграфом. Если задана функция F : V → M и/или F : ... квадратной булевой матрицы M, отражающей смежность вершин, называется ...
  • Теория экономического прогнозирования

    Реферат >> Экономико-математическое моделирование
    ... • старение информации; • изменение функций, структуры, параметров объекта прогнозирова­ния; ... системы прогнозирования [3]. Таблица 2.2 Булева матрица наличия или отсутствия связи ... методы основаны на использовании теории графов. Основная цель Сохранение ...
  • ПТЦА - Прикладная теория цифровых автоматов

    Реферат >> Остальные работы
    ... комбинационных схем, реализующих данную систему булевых функций. Функции у1 и у2 могут быть непосредственно ... микропрограмм эффективные методы теории графов. При графическом описании отдельные функции алгоритмов (микрооперации) отображаются ...
  • Шпоры по теории автоматов

    Реферат >> Радиоэлектроника
    ... , структурные. Абстрактная и структурная теория автоматов. ЦА - устройство, ... где wg = λ(am). Граф: Ориентированный граф, вершины которого соответствуют состояниям, ... элементов и реализует булеву функцию или совокупность булевых функций. Логический элемент: ...
  • Математичекие основы теории систем: анализ сигнального графа и синтез комбинационных схем

    Реферат >> Остальные работы
    ... параграф дисциплины «Математические основы теории систем». В первом ... 1.1.1 1.2 Преобразование структурной схемы к сигнальному графу Граф прохождения сигнала G=, где Х – ... была выполнена минимизация полученных булевых функций следующими методами: метод ...
  • Основы теории надежности

    Реферат >> Остальные работы
    ... = х1х2 v х1х3х4 Повторной формой булевой функции называется такое ее представление, когда ... Метод расчета надежности с использованием теории Марковских процессов. Пусть имеется ... процесс удобно описывать ориентировочно графом переходов вершины которого, ...
  • Синтез мікропрограмних автоматів

    Курсовая работа >> Информатика, программирование
    ... Близькість до булевої алгебри і теорії графів, наочність графічного представлення і ... у вигляді автомата Мілі. Оптимальну функціональну схему керуючих частин автомата ... її необхідними по алгоритму функціональними автоматами. 1.2 Синтезувати мікропрограмний ...
  • Алгоритм раскраски графа (точный)

    Курсовая работа >> Математика
    ... ребер графа). Согласно классификации всех задач теории графов по ... 4. Раскрываем скобки по правилам булевой алгебры и выбираем слагаемое, ... функций. Функция WinMain является главной функцией программы, из которой производится вызов остальных функций. Функция ...
  • Прикладна теорія цифрових автоматів

    Курсовая работа >> Информатика, программирование
    ... курсового проекту по дисципліні "Прикладна теорія цифрових автоматів" є закріплення ... . 1.1 Вибір завдання. 1.1 Вибір граф-схеми алгоритму Граф-схеми алгоритмів обираються кожним ... отримали комбінаційну схему булевої функції в заданому базисі та побудували ...