# 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. Nov 15, 2019 at 15:14

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$? Nov 15, 2019 at 16:16
• Done it correct? 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$. 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? Nov 15, 2019 at 17:10
• is this calculation right? 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? 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$
– Manx
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 .. Nov 15, 2019 at 20:33
• okay, i'll take a look
– Manx
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)$ Nov 15, 2019 at 20:34