2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Nov 15, 2019 at 15:14

2 Answers 2

2
$\begingroup$

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

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

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

$\endgroup$
14
  • $\begingroup$ How did you get the tautology in line 3 for Number 3? $\endgroup$
    – rapiz
    Commented Nov 15, 2019 at 19:28
  • $\begingroup$ @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$ $\endgroup$
    – Ethan
    Commented Nov 15, 2019 at 19:29
  • $\begingroup$ 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 .. $\endgroup$
    – rapiz
    Commented Nov 15, 2019 at 20:33
  • $\begingroup$ okay, i'll take a look $\endgroup$
    – Ethan
    Commented Nov 15, 2019 at 20:34
  • $\begingroup$ 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)$ $\endgroup$
    – rapiz
    Commented Nov 15, 2019 at 20:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .