Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have to show that (!(P.Q) + R)(!Q + P.!R) => !Q by simplifying it using De Morgan's Laws. Here is what I did but I'm not sure it's right.

(!(P.Q) + R)(!Q + P.!R) => !Q

(!P + !Q + R)(!Q + P.!R)

!(P.Q) + !P.P.!R + !Q + !Q.P.!R + R.!Q + R.P.!R

!(P.Q) + 0 + !Q + !Q.P.!Q + R.!Q + 0

!(P.Q) + !Q + !Q(1 + P.!R + R)

!(P.Q) + !Q + !Q

!Q + !(P.Q)

!Q(1 + !P)

!Q

Hope that's clear enough.

share|improve this question
    
The sedond line: how did $(P' · Q' + R)$ turn into $(P' + Q' + R)$? –  user87690 Aug 28 '13 at 15:12
    
De Morgan's Law !(P.Q) = !P + !Q, did I do it wrong? –  Dromad Aug 28 '13 at 15:21
    
But there is $P' · Q'$ and not $(P · Q)'$. –  user87690 Aug 28 '13 at 15:39
    
Yeah sorry about that I wasn't sure how to type it out. It's P.Q Negated with the line above it, so I think it should be !(P.Q) I'll have to edit the question if this is right, –  Dromad Aug 28 '13 at 15:44
    
Actually since $Q'$ is in both conjunts of the second line expression, you can factor it out immediately: $(P' + Q' + R)(Q' + PR') = Q' + (P' + R)(PR')$ which implies $Q'$ –  user87690 Aug 28 '13 at 15:49

2 Answers 2

Indeed, your work is correct. Let's shorten things up, though, using the Distributive Law (D.L.) twice immediately following the application of DeMorgan's:

$\begin{align}(\overline{P\cdot Q} + R)\cdot (\overline Q + P\cdot \overline R) &= (\overline P + \overline Q + R)\cdot(\overline Q + P\cdot \overline R) \tag{DeMorgan's} \\ \\ & = \overline Q + (\overline P + R)(P\cdot \overline R) \tag{D.L.} \\ \\ & = \overline Q + (\color{blue}{\overline P\cdot P}\cdot \overline R) + (\color{red}{R}\cdot P\cdot \color{red}{ \overline R}) \tag{D.L.}\\ \\ & = \overline Q + \color{blue}{ 0} + \color{red}{\bf 0} \tag{$A \cdot \overline A = 0$}\\ \\ &= Q'\end{align}$

share|improve this answer
    
$\Large{+}^\infty $ –  Software Aug 28 '13 at 20:21
    
@amWhy: very instructive +1 –  Amzoti Aug 29 '13 at 12:16

Yes your simplification is right, but can be done shorter way: $((PQ)' + R)(Q' + PR') = (P' + Q' + R)(Q' + PR') = Q' + (P' + R)(PR') = Q' + P'PR' + RPR' = Q' + 0 + 0 = Q'$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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