Решение.
Запишем данную формулу:
;
применим формулу 10:
;
последовательно применим формулу 22:
;
;
;
применим формулы 15 и 21:
;
;
;
применим формулу 6:
;
применим формулу 17:
;
применим формулу 12:
;
и, наконец, применяя формулу 17 окончательно, получим:
,
что и требовалось доказать.
Задание № 5. Используя основные тавтологии, построить равносильные данной формуле ДНФ и КНФ. (При решении ссылаться на номер формулы из перечня равносильных формул).
Решение.
Запишем данную формулу:
;
дважды применим формулу 22:
;
применим формулу 24:
;
дважды применим формулу 22:
;
дважды применим формулу 15:
;
дважды применим формулу 21:
;
дважды применим формулу 5:
;
дважды применим формулы 1 и 7:
;
дважды применим формулу 10:
.
Получена КНФ, равносильная данной формуле. Продолжим процесс для получения равносильной КНФ.
Последовательно применим формулы 18 и 13:
;
;
последовательно применим формулы 1 и 2:
;
;
применим формулу 26:
.
Получена ДНФ, равносильная данной формуле.
Ответ: – ДНФ;
– КНФ.
Задание № 6. Построив таблицу истинности данной формулы, построить равносильные ей СДНФ и СКНФ.
Решение.
Построим таблицу истинности данной формулы:
|
|
|
|
|
|
|
Итог |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
Для построения СДНФ обратимся к значениям «1» в столбце «Итог». Каждому значению «1» сопоставим одну ПЭК по следующему правилу: переменная ( или ) в ПЭК входит сама, если значение этой переменной в этой строке «1» и её отрицание, если значение этой переменной в этой строке «0». Имеем:
;
;
;
;
;
.
Следовательно,
.
– СДНФ – равносильная данной формуле.
Для построения СКДНФ обратимся к значениям «0» в столбце «Итог». Каждому значению «0» сопоставим одну ПЭД по следующему правилу: переменная ( или ) в ПЭК входит сама, если значение этой переменной в этой строке «0» и её отрицание, если значение этой переменной в этой строке «1». Имеем:
;
;
Следовательно,
– СКНФ – равносильная данной формуле.
Ответ: 
– СДНФ;
– СКНФ.
Задание № 7. Для данной формулы алгебры высказываний построить многочлен Жегалкина.
-
.