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?
Negation of if and only if?
-
3As a several-months-late aside, this is commonly expressed in mathematical English as "exactly one of X and Y holds." – 2011-08-13
6 Answers
$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.$
-
0@Arturo I h$a$ven't trolled here Arturo. Look, scholars have investigated a sub-system of classical calculus known as equivalential calculus, which still only has two truth values. There exists plenty there involving material equivalence, with nothing there which concerns the conjunction of two conditionals, because the notion of a material conditional simply isn't coherent within such a system, nor does the notion of a conjunction of any wffs come as coherent there. – 2011-08-14
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.
-
0hmmm.. Making sense to me. Lets wait for some more time. – 2010-11-15
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.
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$.
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).
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 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".
-
0@Bwkapla$n$ 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". – 2011-08-14