Section 7.2.2.2: Satisfiability

Exercise 244. [M20] If $A$ is a set of variables, let $[A]^0$ or $[A]^1$ stand for the set of all clauses that can be formed from $A$ with an even or odd number of negative literals, respectively; each clause should involve all of the variables. (For example, ${1,2,3}^1 = {123, \bar{1}23, 1\bar{2}3, 12\bar{3}}$.) If $A$ and $B$ are disjoint, express $[A \cup B]^0$ in terms of the sets $[A]^0$, $[A]^1$, $[B]^0$, $[B]^1$.

Verified: no
Solve time: 1m22s

Solution

For a clause on $A \cup B$, the literals involving variables in $A$ and the literals involving variables in $B$ form two disjoint parts. Write $CD$ for the clause obtained by concatenating a clause $C$ on $A$ with a clause $D$ on $B$.

Let $C$ contain $r$ negative literals and let $D$ contain $s$ negative literals. The clause $CD$ contains $r+s$ negative literals. Hence $CD$ belongs to $[A\cup B]^0$ exactly when

$$ r+s \equiv 0 \pmod 2. $$

This congruence holds precisely in the two cases

$$ r\equiv 0\pmod 2,\qquad s\equiv 0\pmod 2, $$

or

$$ r\equiv 1\pmod 2,\qquad s\equiv 1\pmod 2. $$

The first case gives all concatenations of a clause from $[A]^0$ with a clause from $[B]^0$, and the second gives all concatenations of a clause from $[A]^1$ with a clause from $[B]^1$. Therefore

$$ \boxed{ [A\cup B]^0

{CD\mid C\in[A]^0,\ D\in[B]^0} \cup {CD\mid C\in[A]^1,\ D\in[B]^1} }. $$

Every clause on the right has an even total number of negative literals, so it belongs to $[A\cup B]^0$. Conversely, every clause in $[A\cup B]^0$ splits uniquely into its $A$-literals and $B$-literals, and the parity condition forces those two parts to have the same parity. Hence every clause in $[A\cup B]^0$ occurs in one of the two sets on the right.

This completes the proof.

∎