Why is ~(P v Q) equivalent to (~P & ~Q)?

[Coldie]

Hi,

For one of the questions in my Discrete Mathematics course, I have to find what property of a formula makes its dual formula also its negative. With a dual formula, the logical operators of "^" and "v" are reversed, the former meaning "and" and the latter meaning "or". With its negative, all the letters in the equation are simply given a negative sign in front of them, turning positives into negatives and vice versa.

I hope someone can help!
Coldie

 

[Corneo]

I think you might want to look into De Morgan's Law.

 

[Coldie]

Thanks, I can see now that the basic formula for DeMorgan is one for which the dual is also its negative. (-pvq) is equivalent to -p^-q. I'm still not sure why or how to explain it, though. Can you give me a hint? Does it simply have to be two statements on either side of an ^ or v?

 

[honestrosewater]

Well, there are several ways of explaining it. Have you tried looking at a truth table as a guide?

$$\begin{array}{|c|c|c|c|c|c|c|}\hline P&Q&\neg P&\neg Q&(P \wedge Q)&\neg (P \wedge Q)&(\neg P \vee \neg Q) \\ \hline T&T&F&F&T&F&F \\ \hline T&F&F&T&F&T&T \\ \hline F&T&T&F&F&T&T \\ \hline F&F&T&T&F&T&T \\ \hline\end{array}$$

(~P v ~Q) is true when ~P is true or* ~Q is true.
What's another way of saying that ~P is true? Answer: P is false.
What's another way of saying that ~Q is true? Answer: Q is false.
So in other words, (~P v ~Q) is true when P is false or Q is false.

~(P & Q) is true when it is not the case that P and Q are both true.
Well, if they aren't both true, then at least one of them must be false.
So in other words, ~(P & Q) is true when P is false or Q is false.

Make sense? Can you explain why ~(P v Q) is equivalent to (~P & ~Q)?

*all ors are inclusive (x or y or both)