Lesson 2

It is possible to ensure that two formulas are equivalent by comparing their truth tables. This method works if the formulas depend on a small number of variables. However, if the number of variables is large, the problem of checking equivalence becomes complex. Nevertheless, one can attempt to transform one formula into another using simple rules, some of which are listed below.

• Commutativity:  \((x \lor y) \equiv (y \lor x)\); \((x \land y) \equiv (y \land x)\).


• Associativity:  \(((x \lor y) \lor z) \equiv (x \lor (y \lor z))\); \(((x \land y) \land z) \equiv (x \land (y \land z))\).


• Distributivity:  \((x \lor (y \land z)) \equiv ((x \lor y) \land (x \lor z))\); \((x \land (y \lor z)) \equiv ((x \land y) \lor (x \land z))\).


• De Morgan's laws:  \(\neg (x \lor y) \equiv (\neg x \land \neg y)\); \(\neg (x \land y) \equiv (\neg x \lor \neg y)\).


• Absorption laws:  \((x \lor (x \land y)) \equiv x\); \((x \land (x \lor y)) \equiv x\).


• Contrapositive principle:  \((x \Rightarrow y) \equiv (\neg y \Rightarrow \neg x)\).


• Law of double negation:  \((\neg \neg x) \equiv x\).