634 views
5 votes
5 votes
How many assignments of truth values to distinct $P_1,P_2,P_3,...,P_n$ with $n \geq 5$ are there for which $(...(((P_1 \rightarrow P_2) \rightarrow P_3 ) \rightarrow P_4)\rightarrow... \rightarrow P_{n-1}) \rightarrow P_n $ is $\textit{true}$ ?    
It is given that there are $5$ assignments of truth values for $(P_1 \rightarrow P_2) \rightarrow P_3$ and there are $11$ assignments of truth values for $((P_1 \rightarrow P_2) \rightarrow P_3) \rightarrow P_4.$     
       
  1. $\dfrac{1}{5}\left((-1)^n + 2^n\right)$      
          
  2.  $\dfrac{1}{3}\left((-1)^n + 2^n\right)$     
            
  3.  $\dfrac{1}{5}\left((-1)^n + 2^{n+1}\right)$      
           
  4.  $\dfrac{1}{3}\left((-1)^n + 2^{n+1}\right)$     
    ($\textbf{Hint}:$ Try to construct the recurrence for the given problem and then solve it)

2 Answers

Best answer
1 votes
1 votes

Let’s assume T(n) is number of assignments of truth value to P$_{1}$, P$_{2}$, … , P$_{n}$ so that 
(...(((P$_{1}$ → P$_{2}$) → P$_{3}$) → P$_{4}$) → … → P$_{n-1}$) → P$_{n}$ is true.

Case 1 : P$_{n}$ is true => (...(((P$_{1}$ → P$_{2}$) → P$_{3}$) → P$_{4}$) → … → P$_{n-1}$) → P$_{n}$ is true. 

=> P$_{1}$, P$_{2}$, … , P$_{n-1}$ can have any truth value.

=> 2$^{n-1}$ possible assignments.

Case 2 : P$_{n}$ is false => (...(((P$_{1}$ → P$_{2}$) → P$_{3}$) → P$_{4}$) → … → P$_{n-2}$) → P$_{n-1}$ is false.

=>  (...(((P$_{1}$ → P$_{2}$) → P$_{3}$) → P$_{4}$) → … → P$_{n-3}$) → P$_{n-2}$ is true and P$_{n-1}$ is false.

=> (...(((P$_{1}$ → P$_{2}$) → P$_{3}$) → P$_{4}$) → … → P$_{n-3}$) → P$_{n-2}$ is true

=> T(n-2) is number of assignments of truth value to P$_{1}$, P$_{2}$, … , P$_{n-2}$ so that 
(...(((P$_{1}$ → P$_{2}$) → P$_{3}$) → P$_{4}$) → … → P$_{n-3}$) → P$_{n-2}$ is true.

$_{\therefore }$ T(n) = 2$^{n-1}$ + T(n-2). (recurrence relation)

selected by
2 votes
2 votes

p1→ p2 is true on 3 assignments   

p1  p2

T   T

F   T

F   F

(p1 → p2) → p3 is true on 5 assignments

  1.           p1→ p2 is true on 3 assignments and P3 can be only false for making this                                                                      expression true.
  2.           p1→ p2 is False on 1 assignment and P3 can be T/F (2 choices) for making this                                                          expression true.

(3*1)+(1*2)=5 

(p1→ p2)→ p3)→ p4 is true on 11 assignments    (5*1)+(3*2)=11 

((p1→ p2)→ p3)→ p4)→ p5 is true on 21 assignments   (11*1)+(5*2)=21 

After getting this idea we can solve it by eliminating the option.

 

At n=3   a) 7/5   b) 7/3   c)3   d)5

Therefore, d) correct

Answer:

Related questions