I'm having issues with applying De Morgan's Law ... Feedback?

Every time one of these questions c开发者_开发百科omes up in my assignments I get it wrong...can anyone help me understand? Or is the teacher's key off? (There is no way for me to know as I'm not given the correct answer, it only lets me know that mine is wrong.)

Assume x = 7 and y = 5. Applying De Morgan's Law, select the logical expression below that is equivalent to the following logical expression: !(x>5)||!(y>7)

(a) !(x>5)&&!(y>7)

(b) !((x>5)||(y>7))

(c) !(x>5)&&(y>7)

(d) (x>5)||!(y>7)

(e) None of the above

I would select B as the answer, but since I have gotten them all wrong so far I'm afraid to continue without some help.

The way I understand this it that you can consolidate the two ! into one by putting it in front of the whole statement, changing:

!(a)||!(b)

to

!((a)||(b))

According to Wikipedia, de Morgan's Law (which to me was just a thing I knew) is

NOT (P AND Q) = (NOT P) OR (NOT Q)

In your question, P maps to (x>5) and Q maps to (y>7). Therefore !((x>5)&&(y>7)) is your answer. But you don't have such a one in your list. (Your teacher is sloppy if this is your real question, since only one proposed answer has double round brackets, which is a huge clue - you can rule out b because it still uses || and rule out the others for a lack of double round brackets, going straight to e.)

If you really can't make these things stand still for you, use the sample values the question provides. (If neccessary, make some up.) x>5 is true for x=7. y>7 is false for y=5. so you have !true || !false, which is false || true, which is true. Evaluate each of the possible expressions and rule out the ones that don't come out to the same answer. If you're still lost, pick different sample values and repeat. One of the possible answers will keep matching, or none will so you'll go with "none of the above." That will earn you the mark even if you don't really understand why.

As for why, it's because of the opposite behaviour of && and ||. The only way you get a true from && is with true on both sides. The only way you get a false from || is with false on both sides. If you flip the parameters with !, you can flip the operator and get the opposite result.

Here, look De Morgan's Law: up http://en.wikipedia.org/wiki/De_Morgan's_laws ! It is not like you described, but

NOT (P AND Q) = (NOT P) OR  (NOT Q)
NOT (P OR Q)  = (NOT P) AND (NOT Q)

Notice that AND becomes OR. Just like OR becomes AND. The negation (NOT) goes into the arguments.

Therefore for !(x>5) || !(y>7) the first rule applies as it's the same as the right hand side with P as (x>5) and Q as (y>7). First change the operator from || (OR) to && (AND), then but the ! (NOT) in front. The result is

!(x>5) || !(y>7)   =   !((x>5) && (y>7))

which looks just like c if there were parentheses, or just like b if there was && instead of ||. With exactly these options the answer is e.

No, the transformation that works is !(a)||!(b) -> !(a && b) - "and" instead of "or" in the transformed version.

Your expression is

!(x>5)||!(y>7)  ==  (x <= 5) || (y <= 7)

which I don't think matches any of those. I'd go for E.

Applying De Morgan's laws (there are two of them, but there are symmetrical) will change:

!(x>7) || !(y>5)

into:

!( (x>7) && (y>5) )

Which I assume is what option c is supposed to be, but the way you wrote it the external brackets are missing. You got almost everything right, you just forgot that the operator also changes.

Here is the easiest way I know to handle De Morgan rules. Suppose you have something like this: ( (A) OP (B) ) where OP is either "or" or "and". Make sure you write all of the brackets, even if the external ones are redundant. Now the negate all the brackets and switch the operator "or" becomes "and" and vice versa. So what you get is this: !( !(A) OTHER_OP !(B) ) Now you usually end up having double negative which can be removed. But identifying the correct structure (the three brackets and the matching operator) is the key.

You can think of DeMorgan's Law as toggling.

Let P, Q be propositions and let OP be an element of {AND, NOT}. Then the following holds:

NOT (P OP Q) = (NOT P) (NOT OP) (NOT Q)

where "NOT AND" denotes OR and "NOT OR" denotes AND. DeMorgan's Law just toggles all truth values and operators.

De Morgan's laws read:

1. ¬(A or B) = ¬A and ¬B
2. ¬(A and B) = ¬A or ¬B

note that you have to conjugate the operator too.

This example may help to clarify the thought process.

If I want something that is not red or a ball, then what I am after is neither red nor a ball. However, if I want something that is not red and a ball then I am seeking an object that is either not red or not a ball.

So the reworking of the expression would be

!((x>5)&&(y>7))

Which isn't given (e).

However, if x=7 and y=5 then (x>5) but !(y>7) so the expression !(x>5)||!(y>7) evaluates to true. E.g. I want something that is not red (x>5) or not a ball (y>7) and I am given a red bucket ( false || true ).

[EDIT] I type too slow.