How is $((X\to Y)\to X)\to X$ a tautology?

Question

$((X \rightarrow Y ) \rightarrow X) \rightarrow X$ converted to its disjunctive normal form is $X' + X$.

Why/how does this show me why this formula a tautology?

Answer 1

$X' + X$ is a tautology because we know that $X' + X$ means either $X$ or not $X$, which is always true, regardless of the truth-value of $X$.

If $X$ is true, then so is $X \lor \lnot X.\;$ If $X$ is false, then $\lnot X = X'$ is true, and thus, so is $\;\lnot X \lor X$. And please note that indeed, $$\text{True}\;\equiv X' + X \equiv X' + X + Y \equiv X' + X + Y' \equiv ((X \rightarrow Y) \rightarrow X)\rightarrow X \equiv \text{ TRUE}$$

So we have that the original expression does not depend on the truth-values of $X$ or of $Y$. The each equivalence above is true for any truth-value assignment we give to $X$ and $Y$.

Answer 2

The formula in question is called Peirce's law. It is notable in that its proof requires (in some form or other) the law of excluded middle, which says that every statement is either true or false. So you can argue as follows:

Either $X$ is true, in which case..., or $X$ is false, in which case..., and in either case it follows that $(((X \to Y)\to X)\to X)$ is true.

EDIT: I just noticed that the question asks how looking at the disjunctive normal form in particular shows that Peirce's law is a tautology. Well, the disjunctive normal form as you have written it says "not-$X$ or $X$", which is an instance of the law of excluded middle.

Answer 3

$X + X' = \top$. (or maybe you use $1$ instead of $\top$)

I would have said $\top$ is also a DNF... but the definition on wikipedia excludes empty products, and I would be unsurprised if this is standard. :(

Answer 4

On what basis can you convert (((X→Y)→X)→X) to (X′+X)? What makes such a process valid in the first place? What do you use when you perform such a conversion process?

Let's see how we might do such. We can start with

(((X→Y)→X)→X)

and obtain

(((X'+Y)→X)→X).

We did this on the basis of the equivalence which says that for all X, for all Y, [(X→Y)==(X'+Y)]. Using it a few more times we can then obtain:

(((X'+Y)'+X)'+X).

Then using another logical equivalence which says for all X, for all Y, [(X+Y)'==(X'$\land$Y')] we can obtain:

(((X''$\land$Y')+X)'+X).

Now, in order to answer why this conversion process will work, we don't have to feel interested in actually seeing the conversion take place. We could have gone on, but realizing that more than one equivalence at work here I think suffices. Now I will point out that such a conversion either involves such equivalences or comes as equivalent to a process which involves such equivalences.

Why do these equivalences work? Because the equivalence, in the context of classical logic, entails that whatever truth value the original formula has, the final formula will have that truth value also. Similarly, because we only used equivalences or used a process which comes as equivalent to using those equivalences, whatever truth value the final formula has, the original formula has also. Consequently, such a conversion shows you why such a formula as (((X→Y)→X)→X) qualifies as a tautology, because every single step of the conversion process ensures that you don't make any steps which result in any formulas which have a distinct truth value, and you ended with a tautology. In other words,

We start with

(((X→Y)→X)→X) which has an unknown truth value in {True, False}.

We then us some equivalence which ensures that whatever we get next N will have the same truth value as (((X→Y)→X)→X). Since we only use equivalences, and eventually obtain a formula which always has a truth value of true, then we know that the second to last formula has the same truth value as the last formula obtained. Since we used an equivalence to get from the third to last formula to the second to last formula, we know that the second to last formulas has the same truth value as the third to last formula. By transitivity, the third to last formula has the same truth value as the last formula. Eventually, we can tell that if the last formula has truth value of True, and we only used equivalences to obtain the last formula from the first, then the first formula will also have truth value of True.

To see how it works in more detail we had

(((X''$\land$Y')+X)'+X), which we didn't know its truth value. We do have the equivalence X''==X which gives us

(((X$\land$Y')+X)'+X), as having the same truth value as the original formula. Then since we have the equivalence ((X$\land$Y')+X)==X we obtain

(X'+X).

Now since we know (X'+X) qualifies as a tautology by the last equivalence, we know

(((X$\land$Y')+X)'+X) qualifies as a tautology. Then by the second to last equivalence, we know

(((X''$\land$Y')+X)'+X) qualifies as a tautology. And we can reason exactly like this, until the first formula, which was

(((X→Y)→X)→X). So, (((X→Y)→X)→X) qualifies as a tautology.