Register

GO Classes 2023 | Weekly Quiz 3 | Question: 13

• retagged by
632 views
2 votes
2 votes

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.
• retagged by
User Avatar

2 Answers

9 votes
9 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
User Avatar
8 votes
8 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$
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

Link Copied!