TIFR CSE 2021 | Part B | Question: 1

Question

Consider the following statements about propositional formulas.

1. $\left ( p\wedge q \right )\rightarrow r$ and $\left ( p \rightarrow r \right )\wedge \left ( q\rightarrow r \right )$ are $\textit{not }$ logically equivalent.
2. $\left ( \neg a\rightarrow b \right )\wedge \left ( \neg b\vee \left ( \neg a \vee \neg b \right )\right )$ and $\neg \left ( a\leftrightarrow b \right )$ are $\textit{not }$ logically equivalent.

• A. Both $\text{(i)}$ and $\text{(ii)}$ are true.
• B. $\text{(i)}$ is true and $\text{(ii)}$ is false.
• C. $\text{(i)}$ is false and $\text{(ii)}$ is true.
• D. Both $\text{(i)}$ and $\text{(ii)}$ are false.
• E. Depending on the values $p$ and $q$, $\text{(i)}$ can be either true or false, while $\text{(ii)}$ is always false.

Comments

(i) is true, put p = F, q = T and r = F. LHS will give T and RHS will give F. Thus, they are not equivalent.

(ii) is false, both LHS and RHS are equivalent to a ⊕ b

Answer 1

1. $(p \wedge q) \rightarrow r \\ \quad \Rightarrow \neg(p \wedge q) \vee r \\ \quad \Rightarrow \neg (p) \vee \neg (q) \vee r \\ \> \\  \left ( p \rightarrow r \right )\wedge \left ( q\rightarrow r \right ) \\ \quad \Rightarrow (\neg p \vee r) \wedge (\neg q \vee r) \\ \quad \Rightarrow \neg (p) \wedge \neg (q) \vee r \\ \quad \quad \textbf{they are not logically equivalent.} \\ \>$ 
2. $\left ( \neg a\rightarrow b \right )\wedge \left ( \neg b\vee \left ( \neg a \vee \neg b \right )\right ) \\ \quad \Rightarrow (a \vee b) \wedge (\neg (a) \vee \neg(b)) \\ \quad \Rightarrow  (a \wedge \neg a) \vee (a \wedge \neg b) \vee (\neg a \wedge b) \vee ( b \wedge  \neg b) \\ \quad \Rightarrow (a \wedge \neg b) \vee (\neg a \wedge b) \\ \> \\  \neg \left ( a\leftrightarrow b \right ) \\ \quad \Rightarrow \neg ((a \rightarrow b) \wedge (b \rightarrow a)) \\ \quad \Rightarrow \neg ((\neg a \vee b) \wedge ( \neg b \vee a)) \\ \quad \Rightarrow (a \wedge \neg b) \vee (\neg a \wedge b)  \\ \quad \quad \textbf{they are logically equivalent.} \\ \>$

$\text{ (i) is true, (ii) is false} \\ \textbf{B is correct.}$

 

Answer 2

Solved by using by case method.