0

Starting with (¬a∨b)∧(¬b∨a), I'm having trouble reducing this to: (a∨b)⟹(a∧b)

I am lost with what is the next step after (¬a∨b)∧(¬b∨a). Is it this perhaps?:

¬(¬a∨b)∧¬(¬b∨a) ? And then work on from there?

Ivan Lendl
  • 1

1 Answers1

2

First "FOIL" it (i.e. use the distributive property twice) to get $$(\lnot a \land \lnot b)\lor(\lnot a\land a)\lor(b\land\lnot b)\lor(b\land a).$$ The middle terms are zero so go away and then just use Demorgan on the first to get $$ \lnot(a\lor b) \lor (b\land a)$$ which is the same thing as $$ (a\lor b)\Rightarrow(a\land b)$$

spaceisdarkgreen
  • 58,508
  • Could you help me to reduce this further? I'm unsure what to do next after distributing it twice – Ivan Lendl May 15 '17 at 03:52
  • @Lendl edited it. That's the most I'll do. That's all the steps so you just need to understand them and write them out explicitly. – spaceisdarkgreen May 15 '17 at 03:57
  • @Lendl Extended hint: in the opposite direction from spaceisdarkgreen's answer (+1), it would work out something like this: $$ \require{cancel} \begin{align} \color{red}{(a \lor b)\implies(a \land b)} ;&=; \lnot(a \lor b) \lor (a \land b) \ &=; (\lnot a \land \lnot b) \lor (a \land b) \ &=; \cancel{(\lnot a \lor a)} \land \color{red}{(\lnot a \lor b) \land (\lnot b \lor a)} \land \cancel{(\lnot b \lor b)} \end{align} $$ – dxiv May 15 '17 at 04:01
  • thanks @spaceisdarkgreen. I'm just stuck on the last step. how you got from ¬(a∨b)∨(b∧a) to (a∨b)⇒(a∧b). which law takes you this this point? – Ivan Lendl May 15 '17 at 04:51
  • @Lendl The usual definition of $\Rightarrow$ is $a \Rightarrow b = \lnot a \lor b.$ Is yours different? – spaceisdarkgreen May 15 '17 at 05:37
  • That's the definition of the material implication connective. – Michael McGovern May 15 '17 at 05:39
  • @MichaelMcGovern What but that do you suppose OP means by $\Rightarrow$ in the post? (The title is Boolean algebra... I only see one interpretation here.) – spaceisdarkgreen May 15 '17 at 06:07
  • @MichaelMcGovern Didn't see how close that was in time to my comment. Perhaps you meant to direct that at OP, not me. If so disregard. – spaceisdarkgreen May 15 '17 at 06:12
  • @spaceisdarkgreen don't worry, I understand it now. Thanks for the help everyone. – Ivan Lendl May 15 '17 at 08:14