What is an efficient way to check if a boolean expression is more specific than another one?

Question

Suppose we have one expression A && B && C && D and another A && B && C

The first expression is more specific than the second one. Is there an efficient way to evaluate that given two boolean expressions, one is more specific than the other? Is there a way to determine how much more specific it is (e.g., D)?

Answer 1

First of all, the question is often stated as the question whether $f \rightarrow g$ is valid. In your example, $f = A \wedge B \wedge C \wedge D$, and $g = A \wedge B \wedge C$.

The usual way to answer is to check the satisfiability of $f \wedge \neg g$. The implication is valid if and only if $f \wedge \neg g$ is unsatisfiable. Hence the problem of checking implication is coNP-complete when $f$ and $g$ are propositional formulae.

The fact that it is a classic intractable problem does not stop people from solving instances of it. The actual method they employ depends on the language in which $f$ and $g$ are expressed. For propositional logic and quantifier-free fragments of first-order logic there are tools that can routinely solve pretty large problems, but as they say, your mileage may vary.

As for the question of "how much more specific," the first thing to notice is that there is in general more than one solution. Every $h$ such that $f = g \wedge h$ is a solution and $h$ can be either true or false where $g$ is false. So either you accept that the solution is a family of formulae, or you introduce a notion of cost, and find a solution that is optimal according to it.

Answer 2

As already pointed out, there is no general efficient way, since this problem is equivalent to the problem of logical equivalence, which is NP complete.

But if you want to know 'how much more specific' a statement is compared to a different one, I think the only reasonable thing to do is to create a combined truth-table and see under which the statements are true. Thus, if you find that statement 1 is true in 25 of the 64 rows, and statement 2 is true in those same 25 rows, but also in another 19 rows (i.e. In 44 rows total), then you could use that to get some kind of 'measure' of 'specificity', and how much 'more specific' a statement is compared to some other.