Когда это удобнее для отрицания используем знак «» вместо черты сверху
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Когда это удобнее, для отрицания используем знак «» вместо черты сверху, т.е. A=¬A, A→B=¬A→B и т.д.
Привести к дизъюнктивной и конъюнктивной нормальным формам:
P→Q→R→¬P→¬Q→¬R;
P→Q→¬P→¬Q→¬R→R;
P→Q→R→P→¬R→P→¬Q.
Нужно полное решение этой работы?
Решение
Избавляемся от импликаций:
P→Q→R→¬P→¬Q→¬R≡¬¬¬P∨Q∨¬R∨¬P∨¬¬Q∨¬R;
вносим знак отрицания используя закон де Моргана, убираем двойные отрицания (идемпотентность отрицания) и лишние скобки (ассоциативность дизъюнкции):
¬¬¬P∨Q∨¬R∨¬P∨¬¬Q∨¬R≡¬¬¬P∨Q&¬¬R∨¬P∨¬¬Q∨¬R;
¬¬¬P∨Q&¬¬R∨¬P∨¬¬Q∨¬R≡¬P∨Q&¬¬R∨¬P∨Q∨¬R;
¬P∨Q&¬¬R∨¬P∨Q∨¬R≡¬P∨Q&¬¬R&¬¬P∨Q∨¬R;
¬P∨Q&¬¬R&¬¬P∨Q∨¬R≡¬P∨Q&R&P∨Q∨¬R;
расставляем скобки нужным образом (ассоциативность конъюнкции):
¬P∨Q&R&P∨Q∨¬R≡¬P∨Q&P&R∨Q∨¬R
раскрываем скобки (дистрибутивность конъюнкции относительно дизъюнкции):
¬P∨Q&P&R∨Q∨¬R≡¬P&P∨Q&P&R∨Q∨¬R≡0∨Q&P&R∨Q∨¬R≡
≡Q&P&R∨Q∨¬R;
расставляем скобки нужным образом (ассоциативность конъюнкции и дизъюнкции):
Q&P&R∨Q∨¬R≡Q&P&R∨Q∨¬R;
применяем закон поглощения:
Q&P&R∨Q∨¬R≡Q∨¬R.
Полученная формула является и ДНФ (дизъюнкция двух одночленных конъюнктов) и КНФ (конъюнкция единственного дизъюнкта)
. Q мы рассматриваем как конъюнкцию Q&1, а R — как R&1, тогда Q∨¬R≡Q&1∨¬R&1, т.е. это — ДНФ; с другой стороны, Q∨¬R≡Q∨¬R&1 — КНФ.
2) избавляемся от предпоследней и последней импликаций:
P→Q→¬P→¬Q→¬R→R≡¬¬P→Q→¬P→¬Q∨¬R∨R;
вносим знак отрицания используя закон де Моргана и убираем двойные отрицания (идемпотентность отрицания):
¬¬P→Q→¬P→¬Q∨¬R∨R≡¬¬P→Q→¬P→¬Q&¬¬R∨R≡
≡P→Q→¬P→¬Q&R∨R;
применяем закон поглощения:
P→Q→¬P→¬Q&R∨R≡R.
Полученная формула является и ДНФ — R≡R&1∨0 и КНФ — R≡R∨0&1.
3) для удобства восстанавливаем скобки вокруг третьей импликации:
P→Q→R→P→¬R→P→¬Q
избавляемся от импликаций:
P→Q→R→P→¬R→P→¬Q≡¬¬¬P∨¬Q∨R∨¬P∨¬R∨¬P∨¬Q;
вносим знак отрицания используя закон де Моргана и убираем двойные отрицания (идемпотентность отрицания):
¬¬¬P∨¬Q∨R∨¬P∨¬R∨¬P∨¬Q≡¬¬¬P∨¬Q∨R&¬¬P&¬¬R∨¬P∨¬Q≡
≡¬P∨¬Q∨R&P&R∨¬P∨¬Q;
комбинируем скобки (ассоциативность дизъюнкции и конъюнкции) и применяем закон поглощения:
¬P∨¬Q∨R&R&P∨¬P∨¬Q≡R&P∨¬P∨¬Q;
комбинируем скобки (ассоциативность дизъюнкции) и раскрываем скобки (дистрибутивность дизъюнкции относительно конъюнкции):
R&P∨¬P∨¬Q≡R&P∨¬P∨¬Q≡R∨¬P&P∨¬P∨¬Q;
используем закон исключённого третьего и нейтральность 1 относительно конъюнкции:
R∨¬P&P∨¬P∨¬Q≡R∨¬P&1∨¬Q≡R∨¬P∨¬Q≡¬P∨¬Q∨R.
Полученная формула является и ДНФ — дизъюнкция трёх одночленных конъюнктов ¬P∨¬Q∨R≡¬P&1∨¬Q&1∨R&1 и КНФ — конъюнкция единственного дизъюнкта ¬P∨¬Q∨R≡¬P∨¬Q∨R&1.
Задать вопрос
на новый заказ в Автор24.
