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

  • Просмотров 846
  • Скачиваний 49
  • Размер файла 2257
    Кб

Задание Дано: Универсум Множества , , Бинарные отношения Функция Требуется: 1. Найти 2. Решить уравнение 3. Построить графы и матрицы отношений P и Q, указать , , 4. Исследовать отношение Р на наличие стандартных свойств (рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность). 5. Построить граф и матрицу отношения , указать , . 6. Построить граф и матрицу отношения , указать , . 7. Построить графы и матрицы

замыканий отношения Р: . Для каждого из замыканий указать и. 8. Найти, построить естественную проекцию :. 9. Построить таблицу значений, граф и матрицу функции f. Указать . 10. Построить граф и матрицу отношения . 11. Найти , построить индуцированное отображение : . 12. Построить граф и матрицу отношения М. Указать , . 13. Доказать, что отношение М есть отношение строгого порядка в А. 14. Исследовать М на линейность (полноту). 15. Интерпретируя

отношение М как «меньше», найти в множестве А относительно М минимальные и максимальные, наименьшие и наибольшие элементы (если таковые существуют). Решение 1. Найти 2. Решить уравнение 3. Построить графы и матрицы отношений P и Q, указать , , рефлексивность симметричность граф матрица 4. Исследовать отношение Р на наличие стандартных свойств (рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность).

По матрице отношения Р определяем его свойства: Не рефлексивно, т.к. на главной диагонали имеются нули. Не антисимметрично, т.к. на главной диагонали имеются единицы. Не симметрично Не антисимметрично Для определения является ли отношение транзитивным, возведем его матрицу в квадрат: По полученной матрице видно, что отношение Р не транзитивно. 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. Доказать, что отношение М есть