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?
-
9The negation happens to be equivalent to "X is true if and only if Y is false". – 2010-11-15
-
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.$$
-
5@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. – 2010-11-15
-
0Both are equivalent. As an Engineer I would prefer Gabe's but as a student of Mathematics, I'd prefer yours. Oh the dilemma.. :-( – 2010-11-15
-
6@Dilawar: As an engineer, just toss a coin, then. (-: – 2010-11-15
-
0Lol.. But you should allow me accept both of the answers. It wouldn't hurt anyone. Besides it does not abuse this forum policies. – 2010-11-15
-
1@Dilawar: It's not up to me; them's the rules. I think Gabe posted first, so if you truly find both answers equally helpful, or incomparably maximally helpful, then accept Gabe's. – 2010-11-15
-
0The response here works for classical logic. However, Epq is not necessarily KCpqCqp once we have more than two truth values at work. Additionally, the negation of Cpq is by no means necessarily KpNq. Say we don't have double negation in the logic. Well then we might have Cpq as equivalent to NKpNq, but it doesn't necessarily follow that NCpq comes as logically equivalent to KpNq since double negation fails. – 2011-08-12
-
4@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. – 2011-08-12
-
1As noted in other answers, this $(X\wedge \neg Y) \vee (Y\wedge \neg X)$ is also called "symmetric difference" or "xor" of $X$ and $Y$. Sometimes written $X \oplus Y$. – 2011-08-12
-
0@Arturo No, there's nothing idiosyncractic here. How do logical equivalence, conjunction, and conditional work in the context of a logic with truth set of {0, .5, 1} where 0 means classical falsity, and 1 classical truth? Well, as long as some operation X on {0, .5, 1} satisfies 00X=1, 01X=0, 10X=0, 11X=1, you can use it as a logical equivalence, if 00Y=01Y=10Y=0, 11Y=1, Y qualifies as a conjunction, and if 00Z=01Z=11Z=1, 10Z=0 it qualifies as a conditional. I would hope it clear that for all combinations of these operations the *classical* equivalences you used don't generally hold. – 2011-08-12
-
5@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. – 2011-08-12
-
0@Arturo I didn't assume that the question did not refer to the usual meanings of "and", "if", and "negation". All truth-functional n-valued, and infinite-valued meanings of "and", "if", and "negation", refer to the usual meanings of those terms, because when truth values get restricted to {0, 1}, everything happens as it does in classical logic. And why do you keep talking about me instead of the content? I'll stick to discussing the content here. – 2011-08-12
-
2@Doug: You stick to discussing the pseudo-content that you think will justify your criticism; your continued trolling is at best tiresome, and your proclamations of innocence doubly so. You criticized and downvoted my answer on the basis that it doesn't apply if we don't work in the standard meaning of the words, so don't try to hide now behind self-serving proclamations. And if you don't like my attitude, rest assured I dislike yours more and you can stop commenting. – 2011-08-12
-
0@Arturo No, I didn't criticize your answer on the basis that it doesn't apply if we don't work in the standard meaning of the words. The usual meaning of the words is not even that of classical logic. I criticized it on the basis that it doesn't work necessarily if the context under discussion was something other than the context of classical logic. There do exist other problems, which we've both ignored to this point, that even though in classical logic though Epq comes as logically equivalent to KCpqCqp, they are simply not the same there, but rather only truth-functionally equivalent. – 2011-08-12
-
4@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. – 2011-08-12
-
0@Arturo No, I did not interpret in a context of non-classical logic. I didn't interpret it in either a classical or non-classical context. You don't need either context for the formulas to get written and read. – 2011-08-14
-
1@Spoonwood: Stop trolling, or go away. And tell it to a mirror, since it's just self-serving prattle anyway. I have no interest in anything you might have to say, and am sorry that this site does not have a killfile. – 2011-08-14
-
0@Arturo I haven'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
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).
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 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".
-
2There 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. – 2011-08-13
-
0@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". – 2011-08-14