Домашние задания: Информатика

Помогите упростить логическое выражение: ((¬A≡¬(B*C))→¬C)→(¬A+¬C≡¬B)

Помогите упростить логическое выражение:
((¬A≡¬(B*C))→¬C)→(¬A+¬C≡¬B)
Что значит "упростить"?
Если речь о нормальных формах (ДНФ, КНФ, СДНФ, СКНФ), то первым делом нужно избавиться от импликаций и эквивалентностей:
 X ≡ Y  =  (X * Y) + (¬X * ¬Y)
X → Y = ¬X + Y
Исходная формула:
 ((¬A ≡ ¬(B * C)) → ¬C) → (¬A + ¬C ≡ ¬B)
(1) (2)
Слева от импликации убираем эквивалетности и импликации, вносим отрицание под скобки, пользуясь законами де Моргана, и убираем скобки в операциях равного приоритета, пользуясь законами ассоциативности.
 (1) =  (¬A ≡ ¬(B * C)) → ¬C  =  ¬((A * B * C) + (¬A * ¬(B * C))) + ¬C  =
= (¬(A * B * C) * ¬(¬A * ¬(B * C))) + ¬C =
= ((¬A + ¬B + ¬C) * (A + (B * C)) + ¬C
Пользуясь законами дистрибутивности, раскрываем скобки. Исключаем нулевые слагаемые и убираем поглощаемые слагаемые:
 ¬X * X = 0
(X * Y) + X = X
Получаем:
 (1) =  ((¬A + ¬B + ¬C) * ((A * B) + (A * C))) + ¬C  =
= (A * B * ¬C) + (A * ¬B * C) + ¬C = (A * ¬B * C) + ¬C
¬(1) = ¬((A * ¬B * C) + ¬C) = ¬(A * ¬B * C) * C =
= (¬A + B + ¬C) * C = (¬A * C) + (B * C)
Далее преобразуем выражение справа от импликации:
 (2) =  ¬A + ¬C ≡ ¬B  = ((¬A + ¬C) * ¬B) + (¬(¬A + ¬C) * B)  =
= (¬A * ¬B) + (¬B * ¬C) + (A * B * C)
Теперь преобразуем саму импликацию, пользуясь законами поглощения:
 (1) → (2)  =  (¬A * C) + (B * C) + (¬A * ¬B) + (¬B * ¬C) + (A * B * C)  =
= (¬A * ¬B) + (¬A * C) + (B * C) + (¬B * ¬C)
Получилась дизъюнктивная нормальная форма (ДНФ). Возможно, вам для ответа её хватит.

Чтобы получить совершенную дизъюнктивную нормальную форму (СДНФ), потребуется дополнить слагаемые таким образом, чтобы в каждом слагаемом присутствовали все буквы, а затем исключить повторяющиеся слагаемые. Например,
 ¬A * ¬B  =  (¬A * ¬B * C) + (¬A * ¬B * ¬C)
¬A * C = (¬A * B * C) + (¬A * ¬B * C)
(¬A * ¬B) + (¬A * C) = (¬A * B * C) + (¬A * ¬B * ¬C)
Если вам нужна СДНФ, то думаю, сможете проделать оставшуюся часть этого упражнения самостоятельно.

Чтобы получить конъюнктивную нормальную форму (КНФ), нужно по закону дистрибутивности перемножить слагаемые и придти к произведению сумм. Можно предварительно вынести общие множители, тогда преобразование будет проще.
 (¬A * ¬B) + (¬A * C) + (B * C) + (¬B * ¬C)  =
= (¬A * (¬B + C)) + ((¬B + C) * (B + ¬C)) =
= (¬B + C) * (¬A + B + ¬C)
Получилась КНФ.

Алгоритм получения СКНФ в общем случае довольно сложен, но в данном случае это делается элементарно:
 (A + ¬B + C) * (¬A + ¬B + C) * (¬A + B + ¬C) 
Итог:
 ДНФ:  (¬A * ¬B) + (¬A * C) + (B * C) + (¬B * ¬C)
СДНФ: (¬A * B * C) + (¬A * ¬B * ¬C) + ...
КНФ: (¬B + C) * (¬A + B + ¬C)
СКНФ: (A + ¬B + C) * (¬A + ¬B + C) * (¬A + B + ¬C)
Выбирайте, что для вас - результат "упрощения".
Семен Семеныч
Семен Семеныч
87 571
Лучший ответ