# 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. – Alain Remillard Nov 15 '19 at 15:14

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? – rapiz Nov 15 '19 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$ – Manx Nov 15 '19 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 .. – rapiz Nov 15 '19 at 20:33
• okay, i'll take a look – Manx Nov 15 '19 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)$ – rapiz Nov 15 '19 at 20:34

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$? – Olivier Roche Nov 15 '19 at 16:16
• Done it correct? – rapiz Nov 15 '19 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$. – Olivier Roche Nov 15 '19 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? – rapiz Nov 15 '19 at 17:10
• is this calculation right? – rapiz Nov 15 '19 at 17:57