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.
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"
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.
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.