Дискретная математика 06
Контрольная работа №2
1. На множестве 
задать операцию 
так, чтобы алгебра 
была бы полугруппой.
Элементы множества Т являются натуральными числами, тогда в качестве можно взять обычную операцию сложения чисел. Отсюда получим полугруппу.
2. Построить таблицу истинности 
.
|
А |
B |
C |
D |
|
|
|
|
|
|
F |
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
3. Доказать, что высказывание 
является тавтологией.
Доказательство:
Составим таблицу истинности:
|
P |
Q |
R |
|
|
|
|
|
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Так как в последнем столбце не все элементы 1, то данное высказывание не будет тавтологией.
4. Записать таблицу истинности 
. Найти ДНФ, КНФ, СДНФ, СКНФ.
Решение:
Таблица истинности:
|
А |
B |
C |
D |
|
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
1 |
|
1 |
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
0 |
Выпишем СДНФ:
Упростим формулу, чтобы получить ДНФ:
Составим СКНФ:
Упростим формулу, чтобы получить КНФ:
5. По 
, построить функцию 
Решение:
Выпишем СКНФ для первой функции и вторую функцию в формульном виде:
.
Тогда
,
Так как функция 
.
6. Построить СДНФ и СКНФ для функции из задания 5.
Решение:
Так как функция тождественно равна 0, то СДНФ не существует.
СКНФ: выпишем таблицу истинности для функции 3 переменных:
|
А |
B |
C |
| |
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
0 |
.
7. Определить фиктивные и существенные переменные для функций из заданий 3 и 5.
Решение:
Для функции из задания 5 все переменные являются фиктивными, так как она тождественно равна 0.
Для функции из задания 3:
|
P |
Q |
R |
|
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
1 |
Так как 
, тогда переменная r является существенной.
Так как 
, тогда переменная q является существенной.
Так как 
, тогда переменная р является существенной.
| < Предыдущая | Следующая > |
|---|