Boolean algebra cheat sheet
Operator Precedence First operators in this list bind stronger:
¬ \neg ¬ (Negation)∧ \wedge ∧ (And)⊕ \oplus ⊕ (Xor)∨ \vee ∨ (Or)→ \rightarrow → (Implication)↔ \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 ¬ a we will write a ˉ \bar{a} a ˉ . Sometimes the equality sign (= = = ) is used to denote syntactic equality, but here we will denote sematic equivalence with = = = .
Axioms a + b = b + a a ⋅ b = b ⋅ a } commutativity a ( b + c ) = a b + a c a + b c = ( a + b ) ( a + c ) } distributivity a + 0 = a a ⋅ 1 = a } neutral elements a + a ˉ = 1 a ⋅ a ˉ = 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} a + b a ⋅ b = b + a = b ⋅ a } a ( b + c ) a + b c = a b + a c = ( a + b ) ( a + c ) } a + 0 a ⋅ 1 = a = a } a + a ˉ a ⋅ a ˉ = 1 = 0 } commutativity distributivity neutral elements complement Basic laws a + a = a a ⋅ a = a } idempotency a + 1 = 1 a ⋅ 0 = 0 } killer elements a + a b = a a ( a + b ) = a } absorbtion ( a + b ) + c = a + ( b + c ) ( a ⋅ b ) ⋅ c = a ⋅ ( b ⋅ c ) } associativity a + b ‾ = a ˉ ⋅ b ˉ a ⋅ b ‾ = a ˉ + b ˉ } De Morgan a ˉ ˉ = a } involution a b + b c + a ˉ c = a b + 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} a + a a ⋅ a = a = a } a + 1 a ⋅ 0 = 1 = 0 } a + a b a ( a + b ) = a = a } ( a + b ) + c ( a ⋅ b ) ⋅ c = a + ( b + c ) = a ⋅ ( b ⋅ c ) } a + b a ⋅ b = a ˉ ⋅ b ˉ = a ˉ + b ˉ } a ˉ ˉ = a } a b + b c + a ˉ c ( a + b ) ( b + c ) ( a ˉ + c ) = a b + a ˉ c = ( a + b ) ( a ˉ + c ) } idempotency killer elements absorbtion associativity De Morgan involution consensus Implication properties Simplification rules 0 → a = 1 1 → a = a a → 1 = 1 a → 0 = a ˉ a → a ˉ = a ˉ a → a = 1 a ⋅ b → a = 1 a → a ⋅ b = a → b a → ( a → b ) = a → b a → ( b → a ) = 1 ( a → b ) → a = a ( a → b ) ( b → c ) → ( a → c ) = 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} 0 → a 1 → a a → 1 a → 0 a → a ˉ a → a a ⋅ b → a a → a ⋅ b a → ( a → b ) a → ( b → a ) ( a → b ) → a ( a → b ) ( b → c ) → ( a → c ) = 1 = a = 1 = a ˉ = a ˉ = 1 = 1 = a → b = a → b = 1 = a = 1 Rewrite rules a → b = a ˉ + b a → b ‾ = a b ˉ a → b = b ˉ → a ˉ a → b ⋅ c = ( a → b ) ( a → c ) a → b + c = ( a → b ) + ( a → c ) ( a + b ) → c = ( a → c ) ( b → c ) a → ( b → c ) = a ⋅ b → c ( a → b ) → c = ( a ˉ → c ) ( b → c ) \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} a → b a → b a → b a → b ⋅ c a → b + c ( a + b ) → c a → ( b → c ) ( a → b ) → c = a ˉ + b = a b ˉ = b ˉ → a ˉ = ( a → b ) ( a → c ) = ( a → b ) + ( a → c ) = ( a → c ) ( b → c ) = a ⋅ b → c = ( a ˉ → c ) ( b → c ) Implication in an operator basis a ˉ = a → 0 a ⋅ b = a → b ˉ ‾ a ⋅ b = ( a → ( b → 0 ) ) → 0 a + b = ( a → b ) → 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} a ˉ a ⋅ b a ⋅ b a + b = a → 0 = a → b ˉ = ( a → ( b → 0 ) ) → 0 = ( a → b ) → b XOR and equivalence properties a ⊕ 0 = a a ⊕ 1 = a ˉ a ⊕ a = 0 a ⊕ b = a b ˉ + a ˉ b a ⊕ b = a ˉ ⊕ b ˉ a ⊕ b = a ˉ ↔ b = a ↔ b ˉ a ⊕ b = a ↔ b ‾ a ⋅ ( b ⊕ c ) = a b ⊕ a c a + b = a b ⊕ a ⊕ b a → b = a b ⊕ a ⊕ 1 a ↔ b = a ⊕ b ⊕ 1 a ↔ a = 1 a ↔ a ˉ = 0 a ↔ b = ( a → b ) ( b → a ) a ↔ b = a ⋅ b + a ˉ ⋅ b ˉ a ↔ b = ( a ˉ + b ) ( a + b ˉ ) a ↔ b = a ˉ ↔ b ˉ a ↔ b = a ˉ ⊕ b = a ⊕ b ˉ \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} a ⊕ 0 a ⊕ 1 a ⊕ a a ⊕ b a ⊕ b a ⊕ b a ⊕ b a ⋅ ( b ⊕ c ) a + b a → b a ↔ b a ↔ a a ↔ a ˉ a ↔ b a ↔ b a ↔ b a ↔ b a ↔ b = a = a ˉ = 0 = a b ˉ + a ˉ b = a ˉ ⊕ b ˉ = a ˉ ↔ b = a ↔ b ˉ = a ↔ b = a b ⊕ a c = a b ⊕ a ⊕ b = a b ⊕ a ⊕ 1 = a ⊕ b ⊕ 1 = 1 = 0 = ( a → b ) ( b → a ) = a ⋅ b + a ˉ ⋅ b ˉ = ( a ˉ + b ) ( a + b ˉ ) = a ˉ ↔ b ˉ = a ˉ ⊕ b = a ⊕ b ˉ NAND and NOR a ˉ = a ⊼ a a ˉ = a ⊻ a a ⊼ b ‾ = a ˉ ⊻ b ˉ a ⊻ b ‾ = a ˉ ⊼ b ˉ a ⋅ b = ( a ⊼ b ) ⊼ ( a ⊼ b ) a ⋅ b = ( a ⊻ a ) ⊻ ( b ⊻ b ) a + b = ( a ⊼ a ) ⊼ ( b ⊼ b ) a + b = ( a ⊻ b ) ⊻ ( a ⊻ b ) a ⊕ b = ( a ⊼ ( a ⊼ b ) ) ⊼ ( ( a ⊼ b ) ⊼ b ) a ⊕ b = ( a ⊻ b ) ⊻ ( ( a ⊻ a ) ⊻ ( b ⊻ b ) ) a ↔ b = ( a ⊼ b ) ⊼ ( ( a ⊼ a ) ⊼ ( b ⊼ b ) ) a ↔ b = ( a ⊻ ( a ⊻ b ) ) ⊻ ( ( a ⊻ b ) ⊻ 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} a ˉ a ˉ a ⊼ b a ⊻ b a ⋅ b a ⋅ b a + b a + b a ⊕ b a ⊕ b a ↔ b a ↔ b = a ⊼ a = a ⊻ a = a ˉ ⊻ b ˉ = a ˉ ⊼ b ˉ = ( a ⊼ b ) ⊼ ( a ⊼ b ) = ( a ⊻ a ) ⊻ ( b ⊻ b ) = ( a ⊼ a ) ⊼ ( b ⊼ b ) = ( a ⊻ b ) ⊻ ( a ⊻ b ) = ( a ⊼ ( a ⊼ b ) ) ⊼ ( ( a ⊼ b ) ⊼ b ) = ( a ⊻ b ) ⊻ ( ( a ⊻ a ) ⊻ ( b ⊻ b ) ) = ( a ⊼ b ) ⊼ ( ( a ⊼ a ) ⊼ ( b ⊼ b ) ) = ( a ⊻ ( a ⊻ b ) ) ⊻ ( ( a ⊻ b ) ⊻ b ) 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. x ↔ a ˉ = ( x ˉ + a ˉ ) ( x + a ) x ↔ a ⋅ b = ( x ˉ + a ) ( x ˉ + b ) ( x + a ˉ + b ˉ ) x ↔ a + b = ( x + a ˉ ) ( x + b ˉ ) ( x ˉ + a + b ) x ↔ a ⊕ b = ( x + a + b ˉ ) ( x + a ˉ + b ) ( x ˉ + a + b ) ( x ˉ + a ˉ + b ˉ ) x ↔ a → b = ( x + a ) ( x + b ˉ ) ( x ˉ + a ˉ + b ) x ↔ a ↔ b = ( 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} x ↔ a ˉ x ↔ a ⋅ b x ↔ a + b x ↔ a ⊕ b x ↔ a → b x ↔ a ↔ b = ( x ˉ + a ˉ ) ( x + a ) = ( x ˉ + a ) ( x ˉ + b ) ( x + a ˉ + b ˉ ) = ( x + a ˉ ) ( x + b ˉ ) ( x ˉ + a + b ) = ( x + a + b ˉ ) ( x + a ˉ + b ) ( x ˉ + a + b ) ( x ˉ + a ˉ + b ˉ ) = ( x + a ) ( x + b ˉ ) ( x ˉ + a ˉ + b ) = ( x ˉ + a ˉ + b ) ( x ˉ + a + b ˉ ) ( x + a ˉ + b ˉ ) ( x + a + b )
Copyright © 2019 — 2022 Alexander Mayorov. All rights reserved. Cookies Policy