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
    $\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$ – Alain Remillard Nov 15 '19 at 15:14
0
$\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.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How did you get the tautology in line 3 for Number 3? $\endgroup$ – rapiz Nov 15 '19 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$ – Manx Nov 15 '19 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 Nov 15 '19 at 20:33
  • $\begingroup$ okay, i'll take a look $\endgroup$ – Manx Nov 15 '19 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 Nov 15 '19 at 20:34
1
$\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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @rapiz Can you edit your original post and show us how you get the DNF of $\varphi_4$? $\endgroup$ – Olivier Roche Nov 15 '19 at 16:16
  • $\begingroup$ Done it correct? $\endgroup$ – rapiz Nov 15 '19 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$ – Olivier Roche Nov 15 '19 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 Nov 15 '19 at 17:10
  • $\begingroup$ is this calculation right? $\endgroup$ – rapiz Nov 15 '19 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.