342 views

Consider the following proposition :

$A_n=\underbrace{(p\rightarrow (q\rightarrow (p\rightarrow (q\rightarrow (\dots )))))}_{\text{number of p's+ number of q's = n}}$

Which of the following is true for $A_n$ :

1. For every $n \geq 2$, $A_n$ is a tautology.
2. For every $n \geq 2$, $A_n$ is a contradiction.
3. For every $n \geq 2$, $A_n$ is a contingency.
4. For every $n \geq 2$, $A_n$ is either a tautology or a contingency.

For $n = 2 : A_2 = p \rightarrow q$ , which is a contingency.
For $n = 3 : A_3 = p \rightarrow ( q \rightarrow p )$ , which is a tautology.
For $n = 4 : A_4 = p \rightarrow ( q \rightarrow (p \rightarrow q) )$ , which is a tautology.
So, for $n = 2$, $A$ is contingency, and for any value $n>2$, $A$ is tautology.

So, for n=2, A is contingency, and for any value n>2, A is tautology.

you have not proved it. How do I know whether this statement is correct or not.

edited by

An = ( p → ( q → ( p → …...)))        (For n>2 )

a.  Anything  → T = T              (Anything means either true or False)

b.  F → Anything = T

1.  p= true  (2 cases possible)

Case 1:

( p → ( q → ( p → ……...( p → (q → (p → q)))))

= ( p → ( q → ( p → ……...(q → (T→ q)))))

= ( p → ( q → ( p → ……...(q → q))))

= ( p → ( q → ( p → ……...(p → (T))))  (Anything → T = True and will go back)

= T

Case 2:

( p → ( q → ( p → ……….(q → p))))

= ( p → ( q → ( p → ……….(q → T)))) = T

2.  p= False

( p → ( q → ( p → …...)))

= ( F → ( q → ( p → …...)))    (F → Anything = True)

= T

Since, $(p \rightarrow (q \rightarrow$ is repeating. I can consider it as a recurrence problem and write the recurrence as:

$$A_n = (p \rightarrow (q \rightarrow A_{n-2}))$$

where $A_{n-2}$ has $\#p + \#q = n-2$

Now, $A_n =\; \sim p \; \vee \; \sim q \; \vee A_{n-2}$

$A_n =\; \sim p \; \vee \; \sim q \; \vee \; \sim p \; \vee \; \sim q \;\vee A_{n-4} = \; (\sim p \; \vee \sim p) \vee \; (\sim q \; \vee \sim q) \vee A_{n-4}$

$A_n =\; \sim p \; \vee \; \sim q \; \vee A_{n-4}$

If we keep unrolling $A_{n-k}$ and write it as $\sim p \; \vee \sim q \; \vee A_{n-(k-2)}$, so each time we get $\sim p$ and $\sim q$ which will be combined with already presented $\sim p$ and $\sim q$ and give $\sim p \; \vee \sim p = \sim p$ and $\sim q \vee \sim q = \sim q$ and at the end we get $\sim p \; \vee \; \sim q \; \vee \; A_{something}$

If we keep doing this, at the end we get,

$$A_n =\; \sim p \; \vee \sim q \; \vee A_2$$

Since, $A_2 = \; \sim p \; \vee q$

Hence, $A_n = \; \sim p \; \vee \sim q \; \vee \; \sim p \; \vee q = \; \sim p \; \vee (\sim q \; \vee \; q) = True, n>2$

Wow ! ..how could you even think about proving like this

@Hareesh22 Mentioned in first line of the answer.

@ankitgupta.1729  I meant that it is sometimes difficult to think how to approach a problem and it was a nice approach using recursion
Ohh accha. You were appreciating the answer. I thought you were asking the question. Sorry.