Задача 66345 ...

628a022a6653d96aeebf61ed

20.10.2022 11:59:03

привести формулы Ф и Ψ равносильными преобразованиями к
дизъюнктивной нормальной форме

626fab9a354ab65fb2f43abb

20.10.2022 12:41:13

★

Здесь нет возможности поставить черту над буквами, поэтому я отрицание буду обозначать значком ~.
Дизъюнктивная нормальная форма (ДНФ) - это запись вида: Z = (X1 /\ Y1) \/ (X2 /\ Y2) \/ (X3 /\ Y3) \/ ...
Φ = ~((~A /\ ~B ⇒ C) \/ B)
Импликация преобразуется так:
X ⇒ Y = ~X \/ Y
Φ = ~((~A /\ B \/ C) \/ B) = ~(~A /\ B \/ C) /\ ~B =
= (A \/ ~B /\ ~C) /\ ~B = (A /\ ~B) \/ (~B /\ ~C)
ДНФ: Φ = (A /\ ~B) \/ (~B /\ ~C)
Ψ = (A \/ B) /\ (~A \/ C) /\ (B \/ C) =
= ((A /\ ~A) \/ (B /\ ~A) \/ (A /\ C) \/ (B /\ C)) /\ (B \/ C) =
= (0 \/ (B /\ ~A) \/ (A /\ C) \/ (B /\ C)) /\ (B \/ C) =
= (~A /\ B /\ B) \/ (A /\ C /\ B) \/ (B /\ C /\ B) \/
\/ (~A /\ B /\ C) \/ (A /\ C /\ C) \/ (B /\ C /\ C) =
= (~A /\ B) \/ (A /\ B /\ C) \/ (B /\ C) \/
\/ (~A /\ B /\ C) \/ (A /\ C) \/ (B /\ C)
По закону поглощения: X \/ (X /\ Y) = X
Поэтому:
(~A /\ B) \/ (~A /\ B /\ C) = (~A /\ B)
(B /\ C) \/ (A /\ B /\ C) = (B /\ C)
Получаем:
ДНФ: Ψ = (~A /\ B) \/ (B /\ C) \/ (A /\ C)