Subjects logic

Tautology Proof

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Search Solutions

Tautology Proof


1. **State the problem:** Show that the logical expression $R \to \sim[(\sim R \wedge X) \lor \sim(R \lor X)]$ is a tautology. 2. **Rewrite the expression:** The expression is an implication: $R \to \sim[(\sim R \wedge X) \lor \sim(R \lor X)]$. 3. **Recall that an implication $A \to B$ is logically equivalent to $\sim A \lor B$.** So rewrite: $$ R \to \sim[(\sim R \wedge X) \lor \sim(R \lor X)] \equiv \sim R \lor \sim[(\sim R \wedge X) \lor \sim(R \lor X)] $$ 4. **Apply De Morgan's law to the negation inside:** $$ \sim[(\sim R \wedge X) \lor \sim(R \lor X)] = \sim(\sim R \wedge X) \wedge \sim\sim(R \lor X) $$ which simplifies to $$ (\sim\sim R \lor \sim X) \wedge (R \lor X) = (R \lor \sim X) \wedge (R \lor X) $$ 5. **Substitute back:** $$ \sim R \lor [(R \lor \sim X) \wedge (R \lor X)] $$ 6. **Distribute $\lor$ over $\wedge$ using distributive laws:** $$ \sim R \lor [(R \lor \sim X) \wedge (R \lor X)] = (\sim R \lor (R \lor \sim X)) \wedge (\sim R \lor (R \lor X)) $$ 7. **Simplify each part:** - $\sim R \lor R \lor \sim X$ simplifies to $\text{True} \lor \sim X = \text{True}$ because $\sim R \lor R$ is a tautology. - Similarly, $\sim R \lor R \lor X$ simplifies to $\text{True} \lor X = \text{True}$. 8. **Therefore:** $$ (\text{True}) \wedge (\text{True}) = \text{True} $$ 9. **Conclusion:** The original expression simplifies to True for all truth values of $R$ and $X$, so it is a tautology. **Final answer:** The expression $R \to \sim[(\sim R \wedge X) \lor \sim(R \lor X)]$ is a tautology.