Confused about negation within a proof I wanted to come up with a proof using contrapositive, so I needed the negation of the following: "one of x and y is congruent to 1 modulo 6 while the other is congruent to 5 modulo 6."
I interpreted this statement as being the same as "one of x and y is congruent to 1 modulo 6 and the other is congruent to 5 modulo 6", so the negation I got was "one of x and y is not congruent to 1 modulo 6 or the other is not congruent to 5 modulo 6".
Turns out the negation is "one of x and y is not congruent to 1 or 5 modulo 6."
I'm not seeing it. Please help me understand.
 A: Without loss of generality, we may assume your statement is, in effect,
$$x \equiv 1 \pmod 6 \land y \equiv 5 \pmod 6$$
(This is equivalent since, in the end, the assignments of $x,y$ are arbitrary since they're not further defined outside of these properties.) Then why is the negation of this
$$x \not \equiv 1 \pmod 6 \lor y \not \equiv 5 \pmod 6$$
instead of your suggestion? 

The issue lies, fundamentally, with the logical "and" ($\land$) operator. If $P \land Q$ is true, that means $P,Q$ individually are both true. What would be the negation of that, then? It would be whenever $P \land Q$ is false, i.e. one of the following holds:


*

*$P$ false, $Q$ true

*$P$ true, $Q$ false

*$P,Q$ both false


This can be summarized more succinctly as "at least one of $P,Q$ are false," or perhaps even more clearly as "$P$ is false or $Q$ is false."
Symbolically, this would be notated $\neg (P \land Q) = \neg P \lor \neg Q$ -- the negation of an "and" statement, in other words, is one of the comprising statements of it is false.
A: they are both wrong.  
I see the statement as, the set of congruences of the set $x,y$ is the set $1,5$.
The negation of that is, the set of congruences of the set $x,y$ is not the set $1,5$.
So they could both be congruent to $1$, the could both be congruent to $5$, one could be congruent to $1$ and the other to anything else  but $5$, one could be congruent to $5$ and the other to anything else but $1$, or they could both be congruent to something other than $1$ or $5$.
