Вариант 8. Построить рефлексивное, симметричное, не транзитивное бинарное отношение

Фрагмент работы:

ВАРИАНТ 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