In Discrete Mathematics, is there a difference between $(\neg P \wedge \neg Q)$ and $\neg (P \wedge Q)$?

Question

I am wondering, in discrete mathematics, whether there is a difference between $(\neg P \wedge \neg Q)$ and $\neg (P \wedge Q)$.

My query comes from a practice problem in a book:

Either John and Bill are both telling the truth, or neither of them is.

Any my solution above corresponds to $P ::=$ John is telling the truth, $Q ::=$ Bill is telling the truth.

Thank you.

Answer 1

Neither John nor Bill telling the truth is:

$$\neg P \land \neg Q$$

or, equivalently:

$$\neg (P \lor Q)$$

But that is not the same as:

$$\neg (P \land Q)$$

because that is merely saying that it is not true that they are both telling the truth (i.e. that they are not both telling the truth)... which is compatible with one of the lying, but the other one still telling the truth.

In short: 'both not' is not the same as 'not both'

Answer 2

Try this for yourself:

Suppose $P$ is true and $Q$ is false. Then:

• Is $(\neg P \wedge \neg Q)$ true or false?
• Is $\neg(P\wedge Q)$ true or false?

Answer 3

These two statements does not have the same truth value as By Demorgan's law, $ \neg(p \wedge q) = \neg p \vee \neg q$.

Here, John and Bill are both telling the truth corresponds to $p \wedge q$.

The negation of the statement is either John is not telling the truth or Bill is not telling the truth($\neg p \vee \neg q$).

It is not the same as neither of them is telling the truth($\neg p \vee \neg q$).