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

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

ВАРИАНТ 8

Задача 8

Доказать, что если А, В, С и D не пусты, то... и... тогда и только тогда, когда....

Решение:

Если.........

Если.........

Так как..., то... и...

Задача 18

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

Решение:

Заданное бинарное отношение построим в виде графа с тремя вершинами. Так как отношение должно быть рефлексивно, то каждая вершина графа будет иметь петли. Чтобы отношение имело свойство симметричности, граф должен быть неориентированным. В соответствии с условием отсутствия транзитивности граф не будет полным:

…

Составим матрицу полученного бинарного отношения и проверим по ней выполнение заданных свойств:

…

1) Так как все элементы главной диагонали - единицы, то отношение рефлексивно.

2) Транспонируем матрицу:

…

Так как..., то отношение симметрично.

3) Умножим матрицу саму на себя:

…

Так как..., то отношение не является транзитивным.

Задача 28

Сколькими способами можно получить предложение, из данного предложения путем вычеркивания слов, не потеряв основного смысла:

Два толстых журнала небрежно лежали на столе

Решение:

Минимальное предложение, отражающее основной смысл исходного:

Два журнала лежали на столе

то есть оно получается из исходного путем вычеркивания либо одного, либо двух слов. Следовательно, число способов получить сокращенное предложение, равно

…

Задача 34

Получить выражение в алгебре Буля, равносильное заданному, с наименьшим числом вхождения переменных, пользуясь аксиомами алгебры Буля и теоремами I-II:

…

Решение:

…

Задача 39

Получить СДНФ, СКНФ булевой функции:

…

Решение:

Составим таблицу истинности функции:

0 0 0 0 1 1 1 1 1 0 0

0 0 1 0 1 0 0 0 0 0 1

0 1 0 0 0 1 1 1 1 0 0

0 1 1 0 0 1 1 1 1 0 0

1 0 0 0 0 1 1 1 1 0 0

1 0 1 0 0 1 1 1 1 1 1

1 1 0 1 0 1 1 1 0 0 1

1 1 1 1 0 1 1 1 0 1 0

По таблице истинности запишем СДНФ:

…

СКНФ:

…

Задача 45

Получить минимальную ДНФ заданной функции и составить схему, реализующую данную функцию (схема должна быть на контактах или на логических элементах).

…

Решение:

Минимальную ДНФ найдем с помощью карты Карно:

1 1

х1 1

По карте видно, что в данном случае минимизация невозможна, то есть минимальная ДНФ равна СДНФ:

…

Реализуем данную функцию на логических элементах:

…

Задача 50

Функции какого класса Поста надо добавить к заданной функции, чтобы получить полную систему функций:

…

Решение:

Заданную функцию представим в виде таблицы истинности:

х у z f

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 1

Определим, к каким классам Поста принадлежит заданная функция:

1).........

2).........

3)..................

4).........

5) Чтобы определить принадлежность функции к классу линейных функций, найдем полином Жегалкина. Запишем по таблице истинности СДНФ:

…

Таким образом, чтобы получить полную систему функций, к данной функции нужно добавить функцию, не сохраняющую 0; функцию, не сохраняющую 1; не самодвойственную функцию и нелинейную функцию.

Задача 51

Проверить правильность рассуждения: Если 2 - простое число, то это наименьшее простое число. Если 2 - наименьшее простое число, то 1 не есть простое число. Число 1 не есть простое число. Следовательно, 2 - простое число.

Решение:

Проверим правильность рассуждения графическим методом. Введем следующие обозначения для высказываний:

X - высказывание "2 - простое число";

Y - высказывание "2 - наименьшее простое число";

Z - высказывание "1 - простое число".

Тогда рассуждение можно записать в формализованном виде:

…

Данное рассуждение F будет истинным, если из конъюнкции посылок следует заключение, т.е. если импликация... тождественно истинна. Для проверки правильности рассуждения построим таблицу истинности:

Таблица истинности высказывания F

X Y Z...............

0 0 0 1 1 1 1 0

0 0 1 0 1 1 0 1

0 1 0 1 1 1 1 0

0 1 1 0 1 0 0 1

1 0 0 1 0 1 0 1

1 0 1 0 0 1 0 1

1 1 0 1 1 1 1 1

1 1 1 0 1 0 0 1

По таблице истинности видно, что функция F не принимает значение истины на всех допустимых значениях простых операндов, следовательно, рассуждение F не является правильным.

Задача 56

Определить истинность формулы... в заданной интерпретации: предметное множество..., значение предикатов... и... задано таблично:

1 0 1 0 1 0

Решение:

По таблице истинности предикатов составим таблицу истинности формулы...:

х у...

1 1 1

1 2 0

2 1 0

2 2 0

Видим, что формула не является истинной.

Задача 63

Найти матрицы смежности и инцидентности для графов:

Решение:

Пронумеруем вершины и ребра графов для составления матриц:

…

Матрица смежности графа G1:

…

Матрица инцидентности графа G1:

…

Матрица смежности графа G2:

…

Матрица инцидентности графа G2:

…

Задача 68

Определить......... графов

В графе... найти любой простой разрез и любой простой остов.

Решение:

1)...:

…

2)...:

…

3)...:

…

Преобразуем граф... в неорграф без петель:

…

Этот связный граф имеет 9 вершин и 15 ребер, его остов имеет... ребер. Остов:

…

Простой разрез:

…