Вариант 8. Построить рефлексивное, симметричное, не транзитивное бинарное отношение
- ID: 30650
- 11 страниц
Фрагмент работы:
ВАРИАНТ 8
Задача 8
Доказать, что если А, В, С и D не пусты, то [image] и [image] тогда и только тогда, когда [image].
Решение:
Если [image], [image], [image]
Если [image], [image], [image]
Так как [image], то [image] и [image]
Задача 18
Построить рефлексивное, симметричное, не транзитивное бинарное отношение.
Решение:
Заданное бинарное отношение построим в виде графа с тремя вершинами. Так как отношение должно быть рефлексивно, то каждая вершина графа будет иметь петли. Чтобы отношение имело свойство симметричности, граф должен быть неориентированным. В соответствии с условием отсутствия транзитивности граф не будет полным:
[image]
Составим матрицу полученного бинарного отношения и проверим по ней выполнение заданных свойств:
[image]
Так как все элементы главной диагонали – единицы, то отношение рефлексивно.
Транспонируем матрицу:
[image]
Так как [image], то отношение симметрично.
Умножим матрицу саму на себя:
[image]
Так как [image], то отношение не является транзитивным.
Задача 28
Сколькими способами можно получить предложение, из данного предложения путем вычеркивания слов, не потеряв основного смысла:
Решение:
Минимальное предложение, отражающее основной смысл исходного:
,
то есть оно получается из исходного путем вычеркивания либо одного, либо двух слов. Следовательно, число способов получить сокращенное предложение, равно
[image]
Задача 34
Получить выражение в алгебре Буля, равносильное заданному, с наименьшим числом вхождения переменных, пользуясь аксиомами алгебры Буля и теоремами I-II:
[image]
Решение:
[image]
[image]
[image]
[image]
[image]
[image]
[image]
[image]
[image]
Задача 39
Получить СДНФ, СКНФ булевой функции:
[image]
Решение:
Составим таблицу истинности функции:
По таблице истинности запишем СДНФ:
[image]
СКНФ:
[image]
Задача 45