4
$\begingroup$

$((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?

$\endgroup$
  • 1
    $\begingroup$ Your question doesn't really match the title. Are you really asking why $X' + X$ is a tautology? $\endgroup$ – Stefan Smith Oct 26 '13 at 21:29
  • 1
    $\begingroup$ $(\lnot X \lor X)$ is a tautology because under all assignments of values to the propositional variables (in this case just $X$), it comes out true. If X is true, then it's true by definition of $\lor$. If X is false, then it's true by definitions of $\lnot$ and $\lor$. $\endgroup$ – Hunan Rostomyan Oct 26 '13 at 21:45
  • $\begingroup$ How did you or the author convert (((X→Y)→X)→X) to (X ′+X)? $\endgroup$ – Doug Spoonwood Oct 26 '13 at 21:54
  • $\begingroup$ Good question @Doug. When I reduce Peirce law to its DNF I get: $(\lnot X \lor X \lor Y)$, but it's equivalent to $(\lnot X \lor X)$, or in fact, to any other tautology. But you're right, the excluded middle is not the DNF (I think). $\endgroup$ – Hunan Rostomyan Oct 26 '13 at 22:06
  • $\begingroup$ @HunanRostomyan Actually (¬X∨X) is in DNF. I more wanted to hint at well... I guess I'll just make it into an answer. $\endgroup$ – Doug Spoonwood Oct 27 '13 at 1:49
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you want to refer to Peirce's law instead. $\endgroup$ – Lord_Farin Oct 26 '13 at 21:27
  • $\begingroup$ @Lord_Farin Thanks, I fixed it. I have been reading that wrong my whole life! $\endgroup$ – Trevor Wilson Oct 26 '13 at 21:28
  • 1
    $\begingroup$ Peirce's law does not require law of the excluded middle for its proof. There's several purely implicational calculi which can prove it which do NOT have any connective for disjunction. You can also prove CCCpqpp from this axiom set under detachment and uniform substitution: 1. CpCqp 2. CCpCqrCCpqCpr 3. CCNpKqNqp 4. CpCqKpq. Peirce's law does hold in one of Bochvar's three-valued logics. $\endgroup$ – Doug Spoonwood Oct 26 '13 at 21:50
  • 1
    $\begingroup$ @DougSpoonwood All I meant was that in the context of intuitionistic logic, Peirce's law implies LEM. If we take $Y = \bot$ and note that $\neg X \to X$ is equivalent to $\neg X \to \bot$, then we see that Peirce's law gives us double negation elimination, which is equivalent to LEM in the context of intuitionistic logic, right? $\endgroup$ – Trevor Wilson Oct 26 '13 at 22:04
2
$\begingroup$

$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$.

$\endgroup$
  • 1
    $\begingroup$ Why do you keep editing to remove the OP's final "$\implies X$"? $\endgroup$ – Trevor Wilson Oct 26 '13 at 21:29
  • 1
    $\begingroup$ @Trevor I was second-guessing my initial edit, where after erasing to format, I lost track of the original expression. $\endgroup$ – Namaste Oct 26 '13 at 21:32
1
$\begingroup$

$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. :(

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

If you have already defined the implication operator this is easy to show. $X\rightarrow Y$ is only false when $X$ is true and $Y$ is not.

If $X$ is true this gives $((X\rightarrow Y)\rightarrow X)\rightarrow X\equiv \text{___}\rightarrow\top$ which is not false, it's true.

If $X$ is false the expression is equivalent to $((\bot\rightarrow Y)\rightarrow\bot)\rightarrow\bot\equiv(\top\rightarrow\bot)\rightarrow\bot\equiv\bot\rightarrow\bot\equiv\top$ so it still holds when $X$ is not true.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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