Question

A logician proves that \((P \land Q) \rightarrow (P \lor Q)\) is a tautology in the following steps: 

i. \((P \land Q) \rightarrow (P \lor Q)\) 
ii. \(\langle X \rangle \langle OP \rangle (P \lor Q)\) 
iii. \((\neg P \lor P \lor Q \lor \neg Q)\) 
iv. \(T\) (TRUE) 

Other symbols are standard logic operators: \(\neg\) stands for NEGATION; \(\land\) for AND; \(\lor\) for OR; and \(\rightarrow\) for IMPLIES. 

Which of the following is/are the set of correct values of \(X\) and \(OP\)?

• A. \(\ \ \ \ \ \neg P \lor \neg Q \ \ \text{and} \ \lor\)
• B. (B) \(\ \ \ \ \ \ \neg (P \land Q) \ \ \text{and} \ \lor\)
• C. (C) \(\ \ \ \neg (P \land Q) \ \ \text{and} \ \land\)
• D. (D) \(\ \ \ \ \neg P \lor \neg Q \ \ \text{and} \ \land\)

Hint:

Remember: \(P \rightarrow Q \equiv \neg P \lor Q\). For compound statements, always expand using equivalence laws like De Morgan's to find alternative correct forms.

Answer 1

The Correct Option is A, B

Step 1: Recall the equivalence of implication. \[ (P \land Q) \rightarrow (P \lor Q) \ \equiv \ \neg (P \land Q) \lor (P \lor Q) \] 

Step 2: Identify the value of \(X\). Here, \(X = \neg (P \land Q)\). This matches option (B). 

Step 3: Apply De Morgan's law to \( \neg (P \land Q) \). \[ \neg (P \land Q) \equiv \neg P \lor \neg Q \] So we can also write the expression as: \[ (\neg P \lor \neg Q) \lor (P \lor Q) \] Thus, \(X = \neg P \lor \neg Q\). This matches option (A). 

Step 4: Confirm the operator \(OP\). In both cases, the operator is OR (\(\lor\)), not AND. Therefore, \(OP = \lor\). 

Step 5: Final tautology check. \[ (\neg P \lor \neg Q \lor P \lor Q) \equiv T \] Hence, the proof is valid. \[ \boxed{\text{Both (A) and (B) are correct.}} \]