How to construct truth tables and prove logical equivalence in propositional logic?

**De Morgan's Laws:** $$\neg(p \land q) \equiv \neg p \lor \neg q$$ $$\neg(p \lor q) \equiv \neg p \land \neg q$$ **Truth table for $\neg(p \lor q) \leftrightarrow (\neg p \land \neg q)$:** \begin{array}{cc|c|c|c|c} p & q & p \lor q & \neg(p \lor q) & \neg p \land \neg q & \leftrightarrow \\ \hline T & T & T & F & F & T \\ T & F & T & F & F & T \\ F & T & T & F & F & T \\ F & F & F & T & T & T \end{array} All entries in the last column are True, making this a **tautology** (always true), confirming De Morgan's law. **Algebraic proof (no truth tables) of $\neg(p \lor q) \equiv \neg p \land \neg q$:** You can prove this by showing each side implies the other using natural deduction, but the most common approach is using truth tables or Venn diagrams. **Tautology vs Contradiction vs Contingency:** - **Tautology:** True for all truth assignments (e.g., $p \lor \neg p$) - **Contradiction:** False for all truth assignments (e.g., $p \land \neg p$) - **Contingency:** True for some, false for others (e.g., $p \land q$) **Simplifying $(p \to q) \land (p \to r)$:** Using the equivalence $p \to q \equiv \neg p \lor q$: $$(\neg p \lor q) \land (\neg p \lor r) \equiv \neg p \lor (q \land r) \equiv p \to (q \land r)$$ So: $(p \to q) \land (p \to r) \equiv p \to (q \land r)$ — if $p$ implies both $q$ and $r$, then $p$ implies their conjunction.