Logic Equivalences

Definition

Compound propositions that have the same truth values in all possible cases are called logically equivalent.

The compound propositions $p$ and $q$ are called logically equivalent if $p\leftrightarrow q$ is a tautology (i.e. always be true under any circumstances). The notation $p⟺q$ (also $p\equiv q$) denotes that $p$ and $q$ are logically equivalent

Logic Equivalences

Distributive laws

$$\begin{array}{c}p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)\\ p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)\end{array}$$

De Morgan's laws

$$\begin{array}{c}\neg (p\wedge q)\equiv \neg p\vee \neg q\\ \neg (p\vee q)\equiv \neg p\wedge \neg q\end{array}$$

Absorption laws

$$\begin{array}{c}p\vee (p\wedge q)\equiv p\\ p\wedge (p\vee q)\equiv p\end{array}$$

Conditional distributive laws

$$\begin{array}{c}(p\vee q)\to r\equiv (p\to r)\wedge (q\to r)\\ (p\wedge q)\to r\equiv (p\to r)\vee (q\to r)\end{array}$$

Normal Forms

See Normal Forms The linked page above introduces how to construct basic logic expressions via listing out their truth tables. However, sometimes we could just easily do this work by applying known logic equivalences

For example, $\neg (p\to q)\equiv \neg (\neg p\vee q)\equiv \neg (\neg p)\wedge \neg q\equiv p\wedge \neg q$

Satisfiability

A compound propositions is satisfiable if there is an assignment of truth values to its variables that makes it true (that is, when it is a tautology or contingency). When no such assignments exist, that is, when the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable

When we find a particular assignment of truth values that makes a compound proposition true, such an assignment is called a solution of this particular satisfiability problem