GO Classes 2023 | Weekly Quiz 3 | Question: 13

Answer 1

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.

Comments

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.  

---

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

Answer 2

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$

Comments

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.