1.30. Составим таблицу истинности для формулы :
![](../Chem/chemmm_clip_image004.gif)
|
![](../Chem/chemmm_clip_image006.gif)
|
![](../Chem/chemmm_clip_image008.gif)
|
![](../Chem/chemmm_clip_image010.gif)
|
![](../Chem/chemmm_clip_image012.gif)
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
2.30. Проверим эквивалентность формул и , составив для них таблицы истинности.
![](../Chem/chemmm_clip_image018.gif)
|
![](../Chem/chemmm_clip_image020.gif)
|
![](../Chem/chemmm_clip_image014_0000.gif)
|
![](../Chem/chemmm_clip_image023.gif)
|
![](../Chem/chemmm_clip_image025.gif)
|
![](../Chem/chemmm_clip_image016_0000.gif)
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
Формулы не эквивалентны, так как 3-й и 6-й столбцы таблицы не совпадают.
3.30. Для упрощения формулы используем правило исключения импликации: .
![](../Chem/chemmm_clip_image030.gif)
.
4.30. Используя законы логики приведем формулу к виду, содержащему только дизъюнкции элементарных конъюнкций. Полученная формула и будет искомой ДНФ:
![](../Chem/chemmm_clip_image036.gif)
Для построения СДНФ составим таблицу истинности для данной формулы:
A |
B |
C |
A Ù B |
(A Ù B ) Ú C |
![](../Chem/chemmm_clip_image038.gif)
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
Помечаем те строки таблицы, в которых формула (последний столбец) принимает значение “1”. Для каждой такой строки выпишем формулу, истинную на наборе переменных A,B,C данной строки: строка 1 – ; строка 3 – ; строка 5 – . Дизъюнкция этих трех формул будет принимать значение “1” только на наборах переменных в строках 1, 3, 5, а следовательно и будет искомой совершенной дизьюнктивной нормальной формой (СДНФ): ![](../Chem/chemmm_clip_image046.gif)
5.30. Для того, чтобы записать формулу в приведенном виде, следует , пользуясь формулой , исключить операцию импликации, а затем “опустить” операцию отрицания на простые переменные: .
|