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