Boolean algebra cheat sheet

Operator Precedence

First operators in this list bind stronger:

  1. ¬\neg (Negation)
  2. \wedge (And)
  3. \oplus (Xor)
  4. \vee (Or)
  5. \rightarrow (Implication)
  6. \leftrightarrow (Equivalence)

From this point on we will use multiplication (\cdot) instead of \wedge and ++ instead of \vee. Also, instead of writing ¬a\neg a we will write aˉ\bar{a}. Sometimes the equality sign (==) is used to denote syntactic equality, but here we will denote sematic equivalence with ==.

Axioms

a+b=b+aab=ba}commutativitya(b+c)=ab+aca+bc=(a+b)(a+c)}distributivitya+0=aa1=a}neutral elementsa+aˉ=1aaˉ=0}complement\begin{aligned} \left.\begin{aligned} a + b &= b + a \\ a \cdot b &= b \cdot a \end{aligned}\right\rbrace &\text{commutativity} \\ \left.\begin{aligned} a(b + c) &= ab + ac \\ a + bc &= (a + b)(a + c) \end{aligned}\right\rbrace &\text{distributivity} \\ \left.\begin{aligned} a + 0 &= a \\ a \cdot 1 &= a \end{aligned}\right\rbrace &\text{neutral elements} \\ \left.\begin{aligned} a + \bar{a} &= 1 \\ a \cdot \bar{a} &= 0 \end{aligned}\right\rbrace &\text{complement} \end{aligned}

Basic laws

a+a=aaa=a}idempotencya+1=1a0=0}killer elementsa+ab=aa(a+b)=a}absorbtion(a+b)+c=a+(b+c)(ab)c=a(bc)}associativitya+b=aˉbˉab=aˉ+bˉ}De Morganaˉˉ=a}involutionab+bc+aˉc=ab+aˉc(a+b)(b+c)(aˉ+c)=(a+b)(aˉ+c)}consensus\begin{aligned} \left.\begin{aligned} a + a &= a \\ a \cdot a &= a \end{aligned}\right\rbrace &\text{idempotency} \\ \left.\begin{aligned} a + 1 &= 1 \\ a \cdot 0 &= 0 \end{aligned}\right\rbrace &\text{killer elements} \\ \left.\begin{aligned} a + ab &= a \\ a(a + b) &= a \end{aligned}\right\rbrace &\text{absorbtion} \\ \left.\begin{aligned} (a + b) + c &= a + (b + c) \\ (a \cdot b) \cdot c &= a \cdot (b \cdot c) \end{aligned}\right\rbrace &\text{associativity} \\ \left.\begin{aligned} \overline{a + b} &= \bar{a} \cdot \bar{b} \\ \overline{a \cdot b} &= \bar{a} + \bar{b} \end{aligned}\right\rbrace &\text{De Morgan} \\ \left.\begin{aligned} \bar{\bar{a}} &= a \end{aligned}\right\rbrace &\text{involution} \\ \left.\begin{aligned} ab + bc + \bar{a}c &= ab + \bar{a}c \\ (a + b)(b + c)(\bar{a} + c) &= (a + b)(\bar{a} + c) \end{aligned}\right\rbrace &\text{consensus} \end{aligned}

Implication properties

Simplification rules

0a=11a=aa1=1a0=aˉaaˉ=aˉaa=1aba=1aab=aba(ab)=aba(ba)=1(ab)a=a(ab)(bc)(ac)=1\begin{aligned} 0 \rightarrow a &= 1 \\ 1 \rightarrow a &= a \\ a \rightarrow 1 &= 1 \\ a \rightarrow 0 &= \bar{a} \\ a \rightarrow \bar{a} &= \bar{a} \\ a \rightarrow a &= 1 \\ a \cdot b \rightarrow a &= 1 \\ a \rightarrow a \cdot b &= a \rightarrow b \\ a \rightarrow (a \rightarrow b) &= a \rightarrow b \\ a \rightarrow (b \rightarrow a) &= 1 \\ (a \rightarrow b) \rightarrow a &= a \\ (a \rightarrow b)(b \rightarrow c) \rightarrow (a \rightarrow c) &= 1 \end{aligned}

Rewrite rules

ab=aˉ+bab=abˉab=bˉaˉabc=(ab)(ac)ab+c=(ab)+(ac)(a+b)c=(ac)(bc)a(bc)=abc(ab)c=(aˉc)(bc)\begin{aligned} a \rightarrow b &= \bar{a} + b \\ \overline{a \rightarrow b} &= a\bar{b} \\ a \rightarrow b &= \bar{b} \rightarrow \bar{a} \\ a \rightarrow b \cdot c &= (a \rightarrow b)(a \rightarrow c) \\ a \rightarrow b + c &= (a \rightarrow b) + (a \rightarrow c) \\ (a + b) \rightarrow c &= (a \rightarrow c)(b \rightarrow c) \\ a \rightarrow (b \rightarrow c) &= a \cdot b \rightarrow c \\ (a \rightarrow b) \rightarrow c &= (\bar{a} \rightarrow c)(b \rightarrow c) \end{aligned}

Implication in an operator basis

aˉ=a0ab=abˉab=(a(b0))0a+b=(ab)b\begin{aligned} \bar{a} &= a \rightarrow 0 \\ a \cdot b &= \overline{a \rightarrow \bar{b}} \\ a \cdot b &= (a \rightarrow (b \rightarrow 0)) \rightarrow 0 \\ a + b &= (a \rightarrow b) \rightarrow b \end{aligned}

XOR and equivalence properties

a0=aa1=aˉaa=0ab=abˉ+aˉbab=aˉbˉab=aˉb=abˉab=aba(bc)=abaca+b=ababab=aba1ab=ab1aa=1aaˉ=0ab=(ab)(ba)ab=ab+aˉbˉab=(aˉ+b)(a+bˉ)ab=aˉbˉab=aˉb=abˉ\begin{aligned} a \oplus 0 &= a \\ a \oplus 1 &= \bar{a} \\ a \oplus a &= 0 \\ a \oplus b &= a\bar{b} + \bar{a}b \\ a \oplus b &= \bar{a} \oplus \bar{b} \\ a \oplus b &= \bar{a} \leftrightarrow b = a \leftrightarrow \bar{b} \\ a \oplus b &= \overline{a \leftrightarrow b} \\ a \cdot (b \oplus c) &= ab \oplus ac \\ a + b &= ab \oplus a \oplus b \\ a \rightarrow b &= ab \oplus a \oplus 1 \\ a \leftrightarrow b &= a \oplus b \oplus 1 \\ a \leftrightarrow a &= 1 \\ a \leftrightarrow \bar{a} &= 0 \\ a \leftrightarrow b &= (a \rightarrow b)(b \rightarrow a) \\ a \leftrightarrow b &= a \cdot b + \bar{a} \cdot \bar{b} \\ a \leftrightarrow b &= (\bar{a} + b)(a + \bar{b}) \\ a \leftrightarrow b &= \bar{a} \leftrightarrow \bar{b} \\ a \leftrightarrow b &= \bar{a} \oplus b = a \oplus \bar{b} \end{aligned}

NAND and NOR

aˉ=aaaˉ=aaab=aˉbˉab=aˉbˉab=(ab)(ab)ab=(aa)(bb)a+b=(aa)(bb)a+b=(ab)(ab)ab=(a(ab))((ab)b)ab=(ab)((aa)(bb))ab=(ab)((aa)(bb))ab=(a(ab))((ab)b)\begin{aligned} \bar{a} &= a \barwedge a \\ \bar{a} &= a \veebar a \\ \overline{a \barwedge b} &= \bar{a} \veebar \bar{b} \\ \overline{a \veebar b} &= \bar{a} \barwedge \bar{b} \\ a \cdot b &= (a \barwedge b) \barwedge (a \barwedge b) \\ a \cdot b &= (a \veebar a) \veebar (b \veebar b) \\ a + b &= (a \barwedge a) \barwedge (b \barwedge b) \\ a + b &= (a \veebar b) \veebar (a \veebar b) \\ a \oplus b &= (a \barwedge (a \barwedge b))\barwedge ((a \barwedge b) \barwedge b) \\ a \oplus b &= (a \veebar b) \veebar ((a \veebar a) \veebar (b \veebar b)) \\ a \leftrightarrow b &= (a \barwedge b) \barwedge ((a \barwedge a) \barwedge (b \barwedge b)) \\ a \leftrightarrow b &= (a \veebar (a \veebar b)) \veebar ((a \veebar b) \veebar b) \end{aligned}

Linear clause forms

These minimum conjunctive normal forms are often used to construct a linear clause form of some formula. The CNF is then typically passed to a SAT-solver. xaˉ=(xˉ+aˉ)(x+a)xab=(xˉ+a)(xˉ+b)(x+aˉ+bˉ)xa+b=(x+aˉ)(x+bˉ)(xˉ+a+b)xab=(x+a+bˉ)(x+aˉ+b)(xˉ+a+b)(xˉ+aˉ+bˉ)xab=(x+a)(x+bˉ)(xˉ+aˉ+b)xab=(xˉ+aˉ+b)(xˉ+a+bˉ)(x+aˉ+bˉ)(x+a+b)\begin{aligned} x \leftrightarrow \bar{a} &= (\bar{x} + \bar{a})(x + a) \\ x \leftrightarrow a \cdot b &= (\bar{x} + a)(\bar{x} + b)(x + \bar{a} + \bar{b}) \\ x \leftrightarrow a + b &= (x + \bar{a})(x + \bar{b})(\bar{x} + a + b) \\ x \leftrightarrow a \oplus b &= (x + a + \bar{b})(x + \bar{a} + b)(\bar{x} + a + b)(\bar{x} + \bar{a} + \bar{b}) \\ x \leftrightarrow a \rightarrow b &= (x + a)(x + \bar{b})(\bar{x} + \bar{a} + b) \\ x \leftrightarrow a \leftrightarrow b &= (\bar{x} + \bar{a} + b)(\bar{x} + a + \bar{b})(x + \bar{a} + \bar{b})(x + a + b) \end{aligned}


Copyright © 2020 Alexander Mayorov. All rights reserved.