TIFR CSE 2025 | Part B | Question: 2

Question

Let $\varphi$ be a propositional formula on $n$ variables, with $n \geq 1$. Consider the following statements.

1. $\varphi$ is satisfiable
2. $\neg \varphi$ is unsatisfiable
3. $\varphi$ is a tautology
4. $\neg \varphi$ is a contradiction

Which of the following is ALWAYS TRUE for all such formulas $\varphi?$

• A. (i) $\not \Leftrightarrow$ (ii), and (ii) $\Leftrightarrow$ (iii) $\Leftrightarrow$ (iv)
• B. (i) $\not \Leftrightarrow$ (ii), and (ii) $\not \Leftrightarrow$ (iii), and (iii) $\Leftrightarrow$ (iv)
• C. (i) $\not \Leftrightarrow$ (ii), and (iii) $\not \Leftrightarrow$ (iv), and (ii) $\Leftrightarrow$ (iii)
• D. (i) $\not \Leftrightarrow$ (ii), and (ii) $\not \Leftrightarrow$ (iii), and (iii) $\not \Leftrightarrow$ (iv)
• E. (i) $\Leftrightarrow$ (ii) $\Leftrightarrow$ (iii) $\Leftrightarrow$ (iv)

   

Answer 1

I think option A is correct. Let's go through all the statements and find out. I’ll refer to the propositional formula as x for simplicity.

First, let's simplify some statements so that it's easier to use them later.

• Statement (ii) says [¬x] is unsatisfiable, which means there is no interpretation where ¬x is true. This implies that ¬x is always false, which means x must be always true. In other words, x is a tautology.

• A tautology is always logically equivalent to statement (iii), which presumably states that x is a tautology.

• Now, statement (iv) says [¬x] is a contradiction, which means all interpretations of ¬x are false. Again, this implies that all interpretations of x are true—so x is a tautology, which again is equivalent to statement (iii).

So far, we know that statements (ii), (iii), and (iv) are logically equivalent.

Now, statement (i) says x is satisfiable, which means there is at least one interpretation where x is true. However, it doesn't say anything about the other interpretations—they might be false. So, x is not necessarily a tautology.

That means statement (i) is not logically equivalent to the others.

---

Final Conclusion:

Statements (ii), (iii), and (iv) are equivalent.
Statement (i) is not equivalent to them.