Дискретная математика 06

Контрольная работа №2

1. На множестве задать операцию так, чтобы алгебра была бы полугруппой.

Решение:

Элементы множества Т являются натуральными числами, тогда в качестве можно взять обычную операцию сложения чисел. Отсюда получим полугруппу.

2. Построить таблицу истинности .

Решение:

3. Доказать, что высказывание является тавтологией.

Доказательство:

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

Так как в последнем столбце не все элементы 1, то данное высказывание не будет тавтологией.

4. Записать таблицу истинности . Найти ДНФ, КНФ, СДНФ, СКНФ.

Решение:

Таблица истинности:

Выпишем СДНФ:

Упростим формулу, чтобы получить ДНФ:

Составим СКНФ:

Упростим формулу, чтобы получить КНФ:

5. По , построить функцию

Решение:

Выпишем СКНФ для первой функции и вторую функцию в формульном виде:

.

Тогда

,

Так как функция .

6. Построить СДНФ и СКНФ для функции из задания 5.

Решение:

Так как функция тождественно равна 0, то СДНФ не существует.

СКНФ: выпишем таблицу истинности для функции 3 переменных:

.

7. Определить фиктивные и существенные переменные для функций из заданий 3 и 5.

Решение:

Для функции из задания 5 все переменные являются фиктивными, так как она тождественно равна 0.

Для функции из задания 3:

Так как , тогда переменная r является существенной.

Так как , тогда переменная q является существенной.

Так как , тогда переменная р является существенной.