Calculate CNF and DNF without truth tables

Question

$$ \begin{array}{l}{\varphi_{1}=(\neg a \wedge b) \rightarrow \neg c} \\ {\varphi_{2}=((c \rightarrow \neg a) \wedge(\neg b \rightarrow \neg c)) \rightarrow(a \vee b \vee c)} \\ {\varphi_{3}=(a \vee \neg b) \leftrightarrow(a \wedge c)} \\ {\varphi_{4}=(\neg a \wedge c) \vee(a \rightarrow b)} \\ {\varphi_{5}=((a \wedge b) \vee(b \wedge \neg c)) \rightarrow(b \vee c)} \\ {\varphi_{6}=((a \uparrow b) \oplus(a \downarrow c))}\end{array} $$

I have to calculate the cnf and dnf for all. I have problems doing that without the truth table. Have to do find the dnf for $4-6$ without truth table and cnf for $1-3$ without truth table. Can somebody help me doing that? Please.

Problems with $5$ my truth table tells me it's a tautology.

Calculating the DNF leads me to : $$ ((\neg a \vee b) \wedge(c \vee \neg b)) \vee(b \vee c) $$

Answer 1

Here's how you can proceed (I hope that this exercise intends to teach you that using the truth tables is a better method):

1. Convert all operators so that only the operators $\neg,\, \vee, \, \wedge$ remain(eg $\phi \to \psi$ becomes $\neg \phi \vee \psi$).
2. Use either distributivity until you're in conjonctive (resp. disjunctive) form. Favor distributivity of $\vee$ over $\wedge$ if you want CNF and vice-versa. Don't forget to simplify using associativity and idempotency after each step.

As an example, let's compute the CNF of $\varphi_4$ :
$$\begin{eqnarray} \varphi_4 & = &(\neg A \wedge C)\vee (A \to B)\\ &\equiv & (\neg A \wedge C)\vee (\neg A \vee B)\\ &\equiv& \big(\neg A \vee (\neg A \vee B)\big)\wedge \big( C\vee (\neg A \vee B) \big) \\ &\equiv& (\neg A \vee B)\wedge ( C\vee \neg A \vee B)\end{eqnarray}$$

$(\neg A \vee B)\wedge ( C\vee \neg A \vee B)$ is in conjonctive form, it is hence the CNF of $\varphi_4$.

Answer 2

Update: (Use Logical equivalence)

$$p⊕q\equiv (p\land\neg q)\lor (\neg p\land q)\equiv(p\lor q)\land(\neg p\lor\neg q)\tag*{aka Xor}$$

$$p ↓ q\equiv \neg p \land \neg q\tag*{aka Nor}$$

$$p ↑ q\equiv \neg p\lor\neg q\tag*{aka Nand}$$

\begin{align} \varphi_6&\equiv((a↑b)⊕(a↓c))\\ &\equiv(\neg a\lor\neg b)⊕(\neg a \land \neg c)\\ &\equiv((\neg a\lor\neg b)\lor(\neg a \land \neg c))\land(\neg(\neg a\lor\neg b)\lor\neg(\neg a \land \neg c))\\ &\equiv (((\neg b\lor\neg a)\lor \neg a)\land((\neg a\lor\neg b)\lor\neg c)\land(\neg(\neg a\lor\neg b)\lor\neg(\neg a \land \neg c))\\ &\equiv ((\neg b\lor(\neg a\lor \neg a))\land((\neg a\lor\neg b)\lor\neg c)\land(\neg(\neg a\lor\neg b)\lor\neg(\neg a \land \neg c))\\ &\equiv ((\neg b\lor \neg a)\land((\neg a\lor\neg b)\lor\neg c))\land(\neg(\neg a\lor\neg b)\lor\neg(\neg a \land \neg c))\\ &\equiv ((\neg a\lor \neg b)\land((\neg a\lor\neg b)\lor\neg c))\land(\neg(\neg a\lor\neg b)\lor\neg(\neg a \land \neg c))\\ &\equiv (\neg a\lor \neg b)\land(\neg(\neg a\lor\neg b)\lor\neg(\neg a \land \neg c))\\ &\equiv (\neg a\lor \neg b)\land((a\land b)\lor(a \lor c))\\ &\equiv ((\neg a\lor \neg b)\land (a\land b))\lor ((\neg a\lor \neg b)\land(a \lor c))\\ &\equiv (\neg( a\land b)\land (a\land b))\lor ((\neg a\lor \neg b)\land(a \lor c))\\ &\equiv \bot\lor ((\neg a\lor \neg b)\land(a \lor c))\\ &\equiv (\neg a\lor \neg b)\land(a \lor c)\tag*{CNF}\\ &\equiv (\neg a\land(a \lor c))\lor (\neg b\land(a \lor c))\\ &\equiv ((\neg a\land a) \lor (\neg a\land c)))\lor ((\neg b\land a) \lor (\neg b\land c)))\\ &\equiv (\bot \lor (\neg a\land c)))\lor ((\neg b\land a) \lor (\neg b\land c)))\\ &\equiv (\neg a\land c)\lor ((\neg b\land a) \lor (\neg b\land c)))\\ \end{align}

And since $(\neg a\land c)\lor (\neg b\land a)$ implies $(\neg b\land c)$ we can prove its DNF form is $(\neg a\land c)\lor (\neg b\land a)$.

---

Hints for $1-3$: \begin{align} \varphi_1&\equiv(\neg a\land b)\to c\\ &\equiv a\lor \neg b\lor c\tag*{CNF&DNF}\\ \varphi_2&\equiv\neg((\neg c\lor¬a)∧(b\lor¬c))\lor(a∨b∨c)\\ &\equiv(c\land a)\lor(\neg b\land c)\lor(a\lor b \lor c)\\ &\equiv a\lor b\lor c\tag*{CNF&DNF}\\ \varphi_3&\equiv (a∨¬b)↔(a∧c)\\ &\equiv (a∨¬b)\to(a∧c)\land(a\land c)\to(a\lor\neg b)\\ &\equiv ((\neg a\land b)\lor(a\land c))\land((\neg a\lor \neg c)\lor(a\lor \neg b))\\ &\equiv ((\neg a\land b)\lor(a\land c))\land\top\\ &\equiv (\neg a\land b)\lor(a\land c)\tag*{DNF}\\ &\equiv ((\neg a\land b)\lor a) \land ((\neg a\land b)\lor c)\\ &\equiv (\neg a\lor a)\land(a \lor b)\land(\neg a\lor c)\land(b\lor c)\\ &\equiv \top\land(a \lor b)\land(\neg a\lor c)\land(b\lor c)\\ &\equiv (a \lor b)\land(\neg a\lor c)\land(b\lor c)\\ \end{align}

And since $(a \lor b)\land(\neg a\lor c)\equiv(\neg a \to b)\land(a\to c)$ which will imply $(b\lor c)$, that will make it true in the statement, so we can prove its CNF is $(a \lor b)\land(\neg a\lor c)$.

(my suggestion is, for relatively detailed answers, ask one question a time.)