Помогите упростить логическое выражение:
((¬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)
Выбирайте, что для вас - результат "упрощения".Похожие вопросы
- Напишите программу которая вычисляет SS=(a+b+a)/(a*b*b)
- Как упростить лог выражение?
- Информатика значения переменных "a" и "b"
- Упростить выражение по информатике 8 класс тема «логика»
- Помогите пожалуйста, истинное и ложное выражение с объяснением (информатика)
- Прочитайте фрагменты программ, определите чему равно значение «c». Информатика. 8 класс. Как решать?
- Значения арифметического выражения.
- (a-2x) в квадрате перевести в квадрат помогите пожалуйста
- Минимизировать логическую схему
- Вводится 6 чисел. Найти количество чисел, оканчивающихся на нечётную цифру. C++ решите