1. Transformations using Logical Equivalence

Transformations using Logical Equivalence

Fundamental Equivalences

$$\begin{array}{rlrl}P\vee P& \equiv P& & \text{idempotency}\\ P\wedge P& \equiv P& & \text{idempotency}\\ P\vee Q& \equiv Q\vee P& & \text{commutativity}\\ P\wedge Q& \equiv Q\wedge P& & \text{commutativity}\\ P\vee (Q\vee R)& \equiv (P\vee Q)\vee R& & \text{associativity}\\ P\wedge (Q\wedge R)& \equiv (P\wedge Q)\wedge R& & \text{associativity}\\ P\wedge (Q\vee R)& \equiv (P\wedge Q)\vee (P\wedge R)& & \text{distributivity}\\ P\vee (Q\wedge R)& \equiv (P\vee Q)\wedge (P\vee R)& & \text{distributivity}\\ \neg (P\wedge Q)& \equiv (\neg P\vee \neg Q)& & \text{De Morgan’s law}\\ \neg (P\vee Q)& \equiv (\neg P\wedge \neg Q)& & \text{De Morgan’s law}\\ P\vee \neg P& \equiv \text{1}& & \text{excluded middle}\\ P\wedge \neg P& \equiv \text{0}& & \\ \neg \neg P& \equiv P& & \\ P\vee 1& \equiv 1& & \\ P\wedge 1& \equiv P& & \\ P\vee 0& \equiv P& & \\ P\wedge 0& \equiv 0& & \\ P\to Q& \equiv \neg P\vee Q& & \\ P\to Q& \equiv \neg Q\to \neg P& & \text{contraposition}\\ \neg (P\to Q)& \equiv P\wedge \neg Q& & \\ 1⟺P& \equiv P& & \\ 0⟺P& \equiv \neg P& & \\ 1\to P& \equiv P& & \\ P\to 1& \equiv 1& & \\ 0\to P& \equiv 1& & \\ P\to 0& \equiv \neg P& & \\ P⟺P& \equiv 1& & \\ p⟺\neg Q& \equiv \neg (P⟺Q)& & \\ P\vee (P\wedge Q)& \equiv P& & \text{absorption}\\ P\wedge (P\vee Q)& \equiv P& & \end{array}$$