# Calculate CNF and DNF without truth tables

$$\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)$$

• Welcome to mathematics SE. People here like to see your work. What have you tried? Please edit your post to include some of your thoughts on the problem. Commented Nov 15, 2019 at 15:14

## 2 Answers

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$$.

• @rapiz Can you edit your original post and show us how you get the DNF of $\varphi_4$? Commented Nov 15, 2019 at 16:16
• Done it correct? Commented Nov 15, 2019 at 16:48
• @rapiz No, the last equality doesn't hold. I suggest that you start with CNF and use distributivity of $\wedge$ over $\vee$. Commented Nov 15, 2019 at 16:54
• Don't get it. Yeah i negated the second term my bad. Want to understand rewrite these equations. What do you mean? Commented Nov 15, 2019 at 17:10
• is this calculation right? Commented Nov 15, 2019 at 17:57

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.)

• How did you get the tautology in line 3 for Number 3? Commented Nov 15, 2019 at 19:28
• @rapiz notice there are both $\neg a \lor a$ in it, first apply Associative law to make ($\neg a \lor a$) together, then Negation law it become $\top$, that part will be $\top \lor (\neg c\lor \neg b)$, then by Domination law we have $\top$ Commented Nov 15, 2019 at 19:29
• Okey got it could you help me with 5 and 6 ? Have to finish it within 2 hours to pass a weekly test that leads to dropping or not and i don't quite get it i will try the dnf for 5 furhter .. Commented Nov 15, 2019 at 20:33
• okay, i'll take a look Commented Nov 15, 2019 at 20:34
• What i actually have $(( \neg a \wedge \neg b ) \vee (\neg a \wedge \neg c) \vee (\neg b \wedge \neg b)) \vee (b \vee b)$ Commented Nov 15, 2019 at 20:34