9
$\begingroup$

I found something that boggles me ( I'm really a beginner in symbolic logic, so maybe it's very trivial).

I was practicing with truth-tables, and I found that:

  1. "p->p" is a tautology

  2. "(p->p)->p" is not a tautology.

I decided to go further, and:

  1. "((p->p)->p)->p" is again a tautology, but

4."(((p->p)->p)->p)-> p" is not, and it keeps alternating.

I checked with an online logic calculator, and it seems correct.

Now, do you know why is that? Is there any particular reason for this pattern?

Cheers

$\endgroup$
  • 3
    $\begingroup$ Check this by subsituition $$\color{red}{p\to p}\equiv\top\tag{1}$$ $$\boxed{\color{red}{(p\to p)}\to p}\equiv\top \to p\equiv p\tag{2}$$ $$\underline{\boxed{(\color{red}{(p\to p)}\to p)}\to p}\equiv p\to p\equiv \top\tag{3}$$ $$(\underline{\boxed{(\color{red}{(p\to p)}\to p)}\to p)}\to p\equiv\top\to p\tag{4}$$ $$\vdots$$ $\endgroup$ – Manx May 29 at 20:34
  • 2
    $\begingroup$ An astute observation. You have a good eye :) $\endgroup$ – BrianO Jun 3 at 4:00
11
$\begingroup$

1) For any formula $p$, $p \to p$ is a tautology.
2) For any tautology $T$, $T \to p$ is logically equivalent to $p$. (Check it out with a truth table.)

So an even amount of occurrences of $p$ will give you tautologies (by 1)); appending another $p$ will give you something that behaves like p (by 2)). And if you take that $p$-equivalent proposition and append another $p$, you will, by 1), get the tautology again, etc.

The core answer to your question lies in 2).

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

I love @lemontree's explanation (and @Manx's terser version of the same point). It may be useful to see the point in a different way, though:

$(p \rightarrow p) \rightarrow p$ is equivalent to $\neg (\neg p \lor p) \lor p$, which by one of De Morgan's laws is equivalent to $(\neg \neg p \,\&\, \neg p) \lor p$.

That last expression is equivalent to $(p \,\&\, \neg p) \lor p$.

The left disjunct of that expression is a contradiction, though; it's always false, so the truth value of the whole expression is the same as the truth value of $p$.

lemontree's answer shows that you can apply this conclusion to understand the longer expressions.

For example, $((p \rightarrow p) \rightarrow p) \rightarrow p$ embeds the original 3-$p$ expression on the left side of the arrow, and we saw that that was equivalent to $p$, so the whole expression is equivalent to $p \rightarrow p$.

| cite | improve this answer | |
$\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.