On the Complexity of Some Equivalence Problems for Propositional Calculi

摘要

In the present paper we study the complexity of Boolean equivalence problems (i.e. have two given propositional formulas the same truthtable) and of Boolean isomorphism problems (i.e. does there exists a permutation of the variables of one propositional formula, such that the truthtable of this modified formula coincides with the truthtable of the second formula) of two given generalized propositional formulas and certain classes of Boolean circuits.