Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let a statement P is "X is true if and only if Y is true". What is the negation of P? I am little confused. It seems that digital equivalent of this statement is P = X and Y. Hence negation of P is (not X) or (not Y) i.e. Either X or Y is false. Am I right guys?

share|cite|improve this question
The negation happens to be equivalent to "X is true if and only if Y is false". – Rahul Nov 15 '10 at 19:06
As a several-months-late aside, this is commonly expressed in mathematical English as "exactly one of X and Y holds." – user83827 Aug 13 '11 at 15:38
up vote 23 down vote accepted

$X\leftrightarrow Y$ is the conjunction of $X\leftarrow Y$ and $X\rightarrow Y$. The negation of a conjunction is the disjunction of the negations; the negation of $P\rightarrow Q$ is $P\wedge \neg Q$. So we have: \begin{align*} \neg(X\leftrightarrow Y) &\Longleftrightarrow \neg\Bigl( (X\rightarrow Y)\wedge (Y\rightarrow X)\Bigr)\\ &\Longleftrightarrow \neg(X\rightarrow Y)\vee \neg(Y\rightarrow X)\\ &\Longleftrightarrow (X\wedge \neg Y) \vee (Y\wedge \neg X). \end{align*} So the negation of "$X$ is true if and only if $Y$ is true" is "Either $X$ is true and $Y$ is false, or $X$ is false and $Y$ is true." Added: as it happens, as noted by Rahul Narain in his comment, this is in turn equivalent to "$X$ is true if and only if $Y$ is false" (just compare the cases when they are each true). So you also get that $$\neg(X\leftrightarrow Y) \Longleftrightarrow X\leftrightarrow \neg Y \Longleftrightarrow \neg X\leftrightarrow Y.$$

share|cite|improve this answer
@Dilawar: You cannot accept both; you can only accept one answer. So pick one. If you like Gabe's answer better, then "give" it to him. – Arturo Magidin Nov 15 '10 at 19:43
@Dilawar: As an engineer, just toss a coin, then. (-: – Arturo Magidin Nov 15 '10 at 20:07
@Doug: Indeed, if you decide, as you usually do, to interpret everything in your own idiosyncratic and secret way, suddenly and miraculously nothing anybody else says will be correct. If that is the sum total of what you want to contribute, perhaps you can instead just talk to yourself. As for your downvoting (I'm guessing it's you) it seems as well founded and useful as the rest of your contributions to this site; i.e., not at all. – Arturo Magidin Aug 12 '11 at 21:14
@Doug: The assumption that the question does not refer to the usual meanings of the words is not just idiosyncratic, it is downright perverse, as is your attitude, your insistence on polish notation and neologisms, and your attempts at justifying your silliness. Trying to impose a nonstandard interpretation just to justify your vengeful downvoting... well that's just pathtetic. You aren't going to convince me, so take them elsewhere. – Arturo Magidin Aug 12 '11 at 22:20
@Doug:In short, you criticized and downvoted an answer about nine months after it was posted because if you interpret it in a non-standard context (non-classical logic), when there is no reason to believe the original poster meant anything of the sort, then it suddenly turns out to be inapplicable. Like I said: silly, self-serving, unhelpful, and trollish. As are the vast majority of your contributions to this site. – Arturo Magidin Aug 12 '11 at 23:06

The digital equivalent is P = X XNOR Y, and thus the negation is (not P) = X XOR Y. In other words, P is false when X is true but Y is false, or when X is false but Y is true.

share|cite|improve this answer
hmmm.. Making sense to me. Lets wait for some more time. – Dilawar Nov 15 '10 at 19:16

Yes, but you have to be very precise here, because the negation of implication is exclusive (not inclusive) OR. So the answer is "Either $X$ or $Y$ is false, but not both".

In general, if you are confused, start with a truth table for implication and then negate it. Resulting table matches XOR (exclusive OR).

share|cite|improve this answer

You are not right. Let $X = (\ell$ is even) and $Y = (\ell$ is not odd). Then clearly $X \Leftrightarrow Y$, but "($\ell$ is not even) or ($\ell$ is odd)" is strictly weaker; you want "($\ell$ is not even) $\Leftrightarrow$ ($\ell$ is odd)" to be true.

share|cite|improve this answer

The assertion $X \leftrightarrow Y$ can also be written as $X = Y$. So its negation is $X \neq Y$, which is the same as $X = \overline{Y}$ (since $X,Y \in \{0,1\}$), which is the same as $\overline{X} \leftrightarrow Y$.

share|cite|improve this answer

The confusion here, I think, arises from not recognizing the principal connective at work. I know of at least three ways to figure out the principal connective.

  1. Write the statement symbolically in Polish notation. The principal connective always gets represented by the very first symbol (or the string is not a wff).

  2. Write the statement symbolically in reverse Polish notation. The principal connective always gets represented by the very last symbol.

  3. Write out an abbreviated truth table. Just like regular truth tables you start with atomic wffs, then deal with longer and longer wffs "gradually". The last column that gets filled in falls under the symbol of the principal connective.

For this formula here's an abbreviated truth table with step numbers listed below the columns.

(( x  ->  y)  ^  (y  ->  x))
   F   T  F   T   F   F  F
   F   T  T   F   T   F  F
   T   F  F   F   F   T  T
   T   T  T   T   T   T  T
   1   2  1   3   1   2  1

Also, "x if and only if y" in Polish notation goes KCxyCyx. So, we have a conjunction, and thus its negation goes NKCxyCyx, a negation of the conjunction of two conditionals. What this implies depends on the logical system in place. If we have an appropriate De Morgan law for the logic, then we can infer ANCxyNCyx (at least one of either of the negation of one of the conditionals or the negation of the other conditional holds). But, that De Morgan law might not hold (and in fact doesn't hold for some logical systems). Also, "x if and only if y" isn't logically equivalent in two-valued logic to "x and y", as I hope the above makes clear from the truth table of "x and y".

share|cite|improve this answer
There is no need to abreviate a truth table when the proposition has only 2 variables. Secondly, even if there was a need, the table you wrote isn't it. I recommend you remove it because it makes no sense and only serves to add confusion. – user4536 Aug 13 '11 at 14:15
@Bwkaplan The number of variables simply does not determine anything about what type of wff you have. NKpq, Apq, CCCpqpq all have two variables. In other words, it doesn't tell you anything about what the principal connective. The last step in an abbreviated truth table always falls under the column of the principal connective. ((x->y)^(y->x)) in words goes ""if x then y" and "if y then x", or in other words ""y, if x" and "x, if y". Or ""x only if y" and "x if y"" which more compactly becomes "x if and only if y". (x<->y) in words goes "the material equivalence of x and y". – Doug Spoonwood Aug 14 '11 at 1:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.