Эквивалентность булевых выражений
У меня есть проблема, которые состоят в сравнении булевых выражений (ИЛИ + И *). Чтобы быть более точным вот, пример:
У меня есть следующее выражение: "A+B+C" и я хотим сравнить его с "B+A+C". Сравнение его как строка не является решением - это скажет мне, что выражения не соответствуют, который является, конечно, ложью. Какие-либо идеи о том, как сравнить те выражения?
Какие-либо идеи о том, как я могу заняться этой проблемой? Я принимаю любой вид предложений, но (как примечание) заключительный код в моем приложении будет написан в C++ (C принятый, конечно).
Нормальное выражение могло содержать также круглую скобку:
(* B * C) + D или A+B* (C+D)+X*Y
Заранее спасибо,
Iulian
2 ответа
Я думаю, что конкурирующий подход к исчерпывающему (и, возможно, изнурительному) созданию таблиц истинности будет заключаться в приведении всех ваших выражений к канонической форме и их сравнении.Например, перепишите все в конъюнктивную нормальную форму с некоторым правилом о порядке символов (например, в алфавитном порядке внутри терминов) и терминов (например, в алфавитном порядке по первому символу в термине). Это, конечно, требует, чтобы символ A в одном выражении совпадал с символом A в другом.
Я не знаю, насколько легко написать (или взять из сети) функцию C или C ++ для переписывания ваших выражений в CNF. Тем не менее, в C и C ++ было проделано много работы в области ИИ, поэтому вы, вероятно, найдете что-то, когда заглянете в Google.
Я также немного не уверен в сравнительной вычислительной сложности этого подхода и подхода таблицы истинности. Я сильно подозреваю, что это то же самое.
Независимо от того, используете ли вы таблицы истинности или каноническое представление, вы, конечно, можете сократить объем работы, которую необходимо выполнить, разделив формы ввода на группы в зависимости от количества различных символов, которые они содержат.
РЕДАКТИРОВАТЬ: Прочитав другие ответы, в частности предложение создать все таблицы истинности и сравнить их, я думаю, что @Iulian сильно недооценил количество возможных таблиц истинности.
Предположим, что мы выбрали RPN для записи выражений, это позволит избежать использования скобок и что есть 10 символов, что означает 9 (бинарных) операторов. Будет 10! различный порядок символов и 2 ^ 9 различных порядков операторов. Следовательно, будет 10! x 2 ^ 9 == 1,857,945,600 строк в таблице истинности для этого выражения.Это действительно включает некоторые дубликаты, любое выражение, содержащее только «и» и «или», например, будет одинаковым независимо от порядка символов. Но я не уверен, что смогу понять это дальше ...
Или я делаю большую ошибку?
Можно вычислить таблицу истинности для каждого выражения по всем возможным входам, а затем сравнить таблицы истинности.