Set of Literals Satisfiable iff No Complementary Pairs

From ProofWiki
Jump to: navigation, search

Theorem

Let $S$ be a set of literals.


Then $S$ is satisfiable if and only if it contains no complementary pairs.


Proof

Necessary Condition

Suppose $S$ contained the complementary pair $\left\{{p, \neg p}\right\}$.

By the Principle of Non-Contradiction, $\left\{{p, \neg p}\right\}$ is unsatisfiable.

By Superset of Unsatisfiable Set is Unsatisfiable, so is $S$.


Hence if $S$ is satisfiable, it cannot contain any complementary pairs.

$\Box$


Sufficient Condition

Suppose $S$ contains no complementary pair.

Define the boolean interpretation $v: \mathcal P_0 \to \left\{{T, F}\right\}$ by:

$v \left({p}\right) = \begin{cases} T & \text{if $p \in S$}\\ F & \text{otherwise} \end{cases}$

Let $\mathbf A \in S$ be an arbitary literal.

If $\mathbf A = p$ is a positive literal, then $v \left({\mathbf A}\right) = T$ is true by the first clause of the definition.

Now suppose $\mathbf A = \neg p$ is a negative literal.

Then $p \notin S$, for $S$ contains no complementary pairs.

Therefore $v \left({p}\right) = F$, and hence:

$v \left({\neg p}\right) = v \left({\mathbf A}\right) = T$


Since $v$ has been demonstrated to be a model of $S$, $S$ is satisfiable.

$\blacksquare$


Sources