How to reason with Equisatisfiability

1.1k Views Asked by At

I am having trouble reasoning about the equisatisfiability of statements.

(In the following I'll use the notation where addition is OR, multiplication is AND, and overbar is NOT.)

By exhaustive search of possibilities I can see that for any three propositional formulas $A,B,C$ then if $$\left(A+B\right)\left(\overline{A}+C\right)$$ is satisfiable that necessarily $$\left(B+C\right)$$ is satisfiable. However if the first is unsatisfiable, that does not necessarily mean the second is (for example if A and B are unsatisfiable, but C is satisfiable). So I'm already a bit confused why this is called equisatisfiable in the first place. However if the later is unsatisfiable, then the former is as well. My understanding is that this means they are equisatisfiable.

I also see that this is distinguishable from equivalence, as

$$\left(A+B\right)\left(\overline{A}+C\right)=\left(A\overline{A}+AC+B\overline{A}+BC\right)=\left(AC+B\overline{A}+BC\right)$$ $$=\left(\overline{A}B+AC\right) \ne \left(B+C\right)$$

However I don't understand how to reason with these notions. For instance, consider the formula: $$\left(A+\overline{B}\right)\left(\overline{A}\right)\left(\overline{A}+B\right)$$ It looks like I can simplify that, preserving equisatisfiability as follows:
First using commutation of AND $$\left(\overline{A}\right)\left(A+\overline{B}\right)\left(\overline{A}+B\right)$$ then applying the equisatisfiability result from above $$\left(\overline{A}\right)\left(\overline{B}+B\right)$$ then removing the tautology $$\left(\overline{A}\right)$$

But if I use a different sequence:
First duplicating a clause doesn't change result $$\left(A+\overline{B}\right)\left(\overline{A}\right)\left(A+\overline{B}\right)\left(\overline{A}+B\right)$$ Then trying to apply the above equisatisfiability result twice: $$\left(\overline{B}\right)\left(A+\overline{B}\right)\left(\overline{A}+B\right)$$ $$\left(\overline{B}\right)\left(\overline{B}+B\right)$$ then removing the tautology leaves us with $$\left(\overline{B}\right)$$

The first claimed only the satisfiability of $\overline{A}$ matters, while the second claims it doesn't matter at all.

So clearly it is incorrect to reason about equisatisfiability the way I am doing it.

Question:
So what is the proper way to reason about equisatisfiability? What did I do wrong and how does how one go about proving two statements are equisatisfiable?

I am more interested in learning how to reason about these things in general, than the specific mistake I made above. That was just to illustrate my confusion. If it is not a good example to discuss reasoning about equisatisfiability, please feel free to use another for your answer, as I'm sure I'm making multiple mistakes here.

1

There are 1 best solutions below

6
On

Just to clarify... I take it that you're using $A,B,C..$ as schematic letters, so that e.g. $A$ might be the satisfiable formula $p\bar q$ or the unsatisfiable formula $p\bar p$.

Now, to say that formulas are equisatisfiable is just to say that one is satisfiable iff the other is.

As you mention, equisatisfiability is not the same as equivalence. A priori, equisatisfiability has the form "there's an $F$ iff there's a $G$" whereas equivalence has the form "the $F$s and the $G$s coincide". For counterexamples besides the one you mention: consider the pair of atomic formulas $p,q$, or for that matter the pair $p,\top$.

It seems to me that the argument of the first paragraph of your posting does not establish an equisatisfability result but only a result of the form "if $D$ is satisfiable, then so is $E$".

The argument of the subsequent part of the post now looks like this. "Consider $D$. If $D$ is satisfiable, then so is $\bar A$. But also if $D$ is satisfiable then so is $\bar B$. However, $\bar A$ and $\bar B$ are unrelated!"

For example, note that $\bar A(B+\bar B)$ might be satisfiable while $\bar A(A+\bar B)(\bar A+B)$ isn't: pick, say, that $A=\bot$ and $B=\top$.