How to compute CNF from truth table

Question

How can I write a propositional formula with variables p, q, r in a CNF that has 3 models v1, v2, v3:

I've failed to find any related sources.

Answer 1

To construct a CNF, take those assignments that make the formula false, then conjoin these rows where for each row corresponding to counter model $v$, disjoin the variables with the truth values reversed, i.e. write $p$ iff $v(p) = 0$ and $\neg p$ iff $v(p) = 1$:

$$CNF(\phi) = \bigwedge_i \bigvee_j \begin{cases}\neg p_j & \text{if }v_i(p_j) = 1\\p_j & \text{if }v_i(p_j) = 0\end{cases} \quad \text{ where }i \in \{i : v_i(\phi) = 0\}, j \in \{j : p_j \text{ is a prop. var. in } \phi\}$$

For comparison,

$$DNF(\phi) = \bigvee_i \bigwedge_j \begin{cases}p_j & \text{if }v_i(p_j) = 1\\\neg p_j & \text{if }v_i(p_j) = 0\end{cases} \quad \text{ where }i \in \{i : v_i(\phi) = 1\}, j \in \{j : p_j \text{ is a prop. var. in } \phi\}$$

---

First find out the counter models, which is the truth table complement of the rows which make the propositional formula true:

   | p q r | φ 
---------------
v1 | 0 0 0 | 0 <==
v2 | 0 0 1 | 0 <==
v3 | 0 1 0 | 1 (= your v1)
v4 | 0 1 1 | 0 <==
v5 | 1 0 0 | 0 <==
v6 | 1 0 1 | 1 (= your v2)
v7 | 1 1 0 | 0 <==
v8 | 1 1 1 | 1 (= your v3)

Then form the conjunction of the disjunction of the reversed literals for the counter models:

$\underbrace{(p \lor q \lor r)}_{\widehat{=} v_1} \land \underbrace{(p \lor q \lor \neg r)}_{\widehat{=}v_2} \land \underbrace{(p \lor \neg q \lor \neg r)}_{\widehat{=}v_4} \land \underbrace{(\neg p \lor q \lor r)}_{\widehat{=}v_5} \land \underbrace{(\neg p \lor \neg q \lor r)}_{\widehat{=}v_7}$

---

The intuition is that we specify all (-> big conjunction) the possibilities which must not be the case by effectively negating each counter model by speciying that at least one (-> small disjunctions) of the variable assignments for this potential counter model is not the case (-> reversed truth values), i.o.w. for each counter model, not all its assignments are the case:

$\underbrace{\neg \underbrace{(\neg p \land \neg q \land \neg r)}_{=v_1}}_{\large \equiv (p \lor q \lor r)} \land \underbrace{\neg \underbrace{(\neg p \land \neg q \land r)}_{=v_2}}_{\large \equiv (p \lor q \lor \neg r)} \land \neg \ldots$

By de Morgan's laws, each of these negated conjunctions of literals is equivalent to a disjunction of the negated literals ($\neg (\phi \land \psi \land \chi) \equiv (\neg \phi \lor \neg \psi \lor \neg \chi)$), which yields precisely the CNF above.

Answer 2

CNF

Each $v_i$ is equivalent to a conjunction, eg $v_1$ is equivalent to $\neg p \wedge q \wedge \neg r$. Now take a disjunction of these conjunctions :

$$\underbrace{(\neg p \wedge q \wedge \neg r)}_{\equiv v_1} \vee \underbrace{(p \wedge \neg q \wedge r)}_{\equiv v_2} \vee \underbrace{(p \wedge q \wedge r)}_{\equiv v_3}$$

DNF

We gather implications that must be satisfied, then we turn these implications into disjunctions :

• The first row is the only row where $p=0$, and we see that $\neg p \to q$ and $\neg p \to \neg r$. This gives us $p \vee q$ and $p \vee \neg r$.

• The second row is the only row where $q=0$, and we see that $\neg q \to p$ and $\neg q \to r$. This gives us $q \vee p$ (wee already had that, let's drop it) and $q \vee r$.

• The third row is the only row where both $p = 1$ and $q = 1$. This gives us the implication $(p \wedge q) \to r$. This gives us $\neg (p \wedge q) \vee r$, which is equivalent to $\neg p \vee \neg q \vee r$

All in all, you get the DNF : $$(p\vee q) \wedge (p \vee \neg r) \wedge (q \vee r) \wedge (\neg p \vee \neg q \vee r)$$