# Thread: Need help with this logic question (algerbraically)

1. ## Need help with this logic question (algerbraically)

Question. While trying to prove a propositional logic statement, a student makes use o the following incorrect equivalence: NOT(p OR q) == NOT p OR NOT q

Show algerbraically that the equivalence is invalid.

Now the only thing I can think of is writting

NOT(p AND q) expands to NOT p AND NOT q
NOT p OR NOT q simplifies to NOT(p AND q)

So you can see they are not the same thing, but the question is worth 8% I'm not really sure what it's asking exactly.

2. ## Re: Need help with this logic question (algerbraically)

Originally Posted by uperkurk
Question. While trying to prove a propositional logic statement, a student makes use o the following incorrect equivalence: NOT(p OR q) == NOT p OR NOT q
Show algerbraically that the equivalence is invalid.
Now the only thing I can think of is writting
NOT(p AND q) expands to NOT p AND NOT q
NOT p OR NOT q simplifies to NOT(p AND q)
So you can see they are not the same thing, but the question is worth 8% I'm not really sure what it's asking exactly.
What does "Show algerbraically that the equivalence is invalid." really mean?

3. ## Re: Need help with this logic question (algerbraically)

It's supposed to mean break it down. You can prove something is right or wrong via truth tables or algerbraically apparently. Here is a picture from some examples of "showing algebraically"

So any idea?

5. ## Re: Need help with this logic question (algerbraically)

Proofs that proceed by rewriting using logic laws can show that two expressions are equivalent, not that they are non-equivalent. The only way to show the latter is if you have two expressions about which you know that they are not equivalent. For example, it may be given that x AND y is not equivalent to x OR y or that T is not equivalent to F. If the first of these non-equivalences is known, then you may substitute NOT x for p and NOT y for q in the erroneous equation. Then, using that equation, the left-hand side is equivalent to x OR y. Using the correct De Morgan's rule, the left-hand side is equivalent to x AND y.

A better way would be to replace p and q with truth values that make the truth-value of the left-hand side different from the truth value of the right-hand side and then reduce both sides to those truth values using logic laws. It seems that we can take for granted that T is not equivalent to F. However, this method is basically the same as using truth tables.

6. ## Re: Need help with this logic question (algerbraically)

Thanks, here is the actual question in full maybe this will clear things up...

7. ## Re: Need help with this logic question (algerbraically)

That's what I am saying: the problem suggests producing a statement whose left-hand side cannot be equivalent to the right-hand side. Now, about which two expressions it is clear that they cannot be equivalent is subjective. To one person it is clear that NOT (p OR q) cannot be equivalent to (NOT p) OR (NOT q), but to another this is not obvious and he/she only knows that p AND q and p OR q are not equivalent. To a purist, the only obvious thing is that T and F are not equivalent. For this reason, I don't think the problem is well-posed. Nevertheless, I suggest choosing two expressions whose non-equivalence you can justify and then proceed by making appropriate substitutions for p and q as described in post post #5.

8. ## Re: Need help with this logic question (algerbraically)

Here's what I would do. I'd start re-writing the RHS $\displaystyle \neg p\vee\neg q$ to get to $\displaystyle \neg(p\wedge q)$ and then conclude that quite obviously, $\displaystyle \neg(p\wedge q)\not\equiv\neg(p\vee q)$, since that would mean conjunction is equivalent to disjunction.

9. ## Re: Need help with this logic question (algerbraically)

Originally Posted by uperkurk
Now the only thing I can think of is writting

NOT(p AND q) expands to NOT p AND NOT q
NOT p OR NOT q simplifies to NOT(p AND q)
I'm not quite sure how your argument would proceed. NOT(p AND q) does not expand to NOT p AND NOT q, but to NOT p OR NOT q. (I've given my suggestion above, btw.) And, being a logic teacher myself, I find the phrasing of this assignment ambiguous.