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.

Dark Mode

342 views

1 vote

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

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

7 votes

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.

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.

1

edited
Oct 6, 2022
by ASNR1010

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

0

6 votes

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$

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

0