4

I got screwed when trying to understand this expression. I've thought several times but I cant get the meaning.

  1. ! (p || q) is equivalent to !p && !q For this one, somehow I can comprehend a little bit. My understanding is " Not (p q) = not p and not q" which is understandable

  2. ! (p && q) is equivalent to !p || !q For the second, I'm totally got screwed. How come
    My understanding is " Not (p q) = Not p or Not q " . How come and and or can be equivalent each other? as for the rule in the truth table between && and || is different.

That's how I comprehend each expression, perhaps I have the wrong method in understand the expression. Could you tell me how to understand those expressions?

Kev
  • 118,037
  • 53
  • 300
  • 385
YLTO
  • 41
  • 2
  • i think this deserves to be here: http://cstheory.stackexchange.com/ – corroded May 25 '11 at 16:26
  • @corroded - To quote the faq from cstheory *"It does not include questions at the level of difficulty of typical undergraduate course/textbook homework/exercise."* which is what this is. – Kev May 25 '11 at 16:48
  • @Kev, then it should be here? http://math.stackexchange.com/ – corroded May 25 '11 at 17:03
  • @corroded - I think you'll find that the maths in this question is a bit under the complexity threshold required of maths.se. I'm happy for it to remain. – Kev May 25 '11 at 17:11

2 Answers2

5

You can use a Truth table to see how the two expressions are equal. Like This:


!(P || Q) = !P && !Q 

_________________________________________________
   P   Q   P || Q   !(P||Q)   !P   !Q   !P && !Q
_________________________________________________
   1   1      1         0      0    0       0
   1   0      1         0      0    1       0
   0   1      1         0      1    0       0
   0   0      0         1      1    1       1
_________________________________________________

Note that the column labeled !(P||Q) is the same as the column labeled !P && !Q. You can work this from the left most column where we set the initial values for P and Q. Then work out each column towards the right.


!(P && Q) = !P || !Q 

_________________________________________________
   P   Q   P && Q   !(P&&Q)   !P   !Q   !P && !Q
_________________________________________________
   1   1      1         0      0    0       0
   1   0      0         1      0    1       1
   0   1      0         1      1    0       1
   0   0      0         1      1    1       1
_________________________________________________
Ori Pessach
  • 6,777
  • 6
  • 36
  • 51
Vincent Ramdhanie
  • 102,349
  • 23
  • 137
  • 192
0

Think of it in terms of the Red Toyota.

Let p = "The car is red"

Let q = "The car is a Toyota"

! ( p && q ) means "The car is not a red Toyota"

Which is the same as saying:

!p || !q "it's not red, or (inclusive) it's not a Toyota" , right?

Nimloth
  • 209
  • 2
  • 4