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?
$\endgroup$ 26 Answers
$\begingroup$$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.$$
$\endgroup$ 25 $\begingroup$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.
$\endgroup$ 1 $\begingroup$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).
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$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$.
$\endgroup$ $\begingroup$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.
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).
Write the statement symbolically in reverse Polish notation. The principal connective always gets represented by the very last symbol.
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 1Also, "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".
$\endgroup$ 2
