in Mathematical Logic retagged by
342 views
1 vote
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$ :

  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.
in Mathematical Logic retagged by
342 views

2 Answers

7 votes
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.
edited by

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

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

0
0
6 votes
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$

4 Comments

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

@Hareesh22 Mentioned in first line of the answer.

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

Related questions