Boolean Algebra Theorems (BACKSLASH IS ASTERISK)

Identity Theorem

X + 0 = X/X \ 1 = X

Domination/Null Theorem

X + 1 = 1/X \ 0 = 0

Idempotency Theorem

X + X = X/X \ X = X

Inverse Theorem

X + X' = 1/X \ X' = 0

Commutative Theorem

X + Y = Y + X/X \ Y = Y \ X

Associativity Theorem

(X + Y) + Z = X + (Y + Z)/(X \ Y) \ Z = X \ (Y \ Z)

Involution (Double Negation) Theorem

(X')' = X

Distributivity Theorem

X \ (Y + Z) = (X \ Y) + (X \ Z)/X + (Y \ Z) = (X + Y) \ (X + Z)

Uniting Theorem

X \ Y + X \ Y' = X/(X + Y) \ (X + Y') = X

Absorption Theorem

X + X \ Y = X/X \ (X + Y) = X

Factoring Theorem

(X + Y) \ (X' + Z) = X \ Z + X' \ Y/X \ Y + X' \ Z = (X + Z) \ (X' + Y)

Consensus Theorem

X \ Y + Y \ Z + X' \ Z = X \ Y + X' \ Z/(X + Y) \ (Y + Z) \ (X' + Z) = (X + Y) \ (X' + Z)

De Morgan's Theorem

(X + Y + …)' = X' \ Y' \ …/(X \ Y \ …)' = X' + Y' + …

Modus Ponens

Premises: p, p→q

Conclusion: q

Modus tollens

Premises: p→q, q’

Conclusion: p’

Hypothetical syllogism

Premise: p→q, q→r

Conclusion: p→r

Disjunctive syllogism

Premise: p + q, p’

Conclusion: q

Addition

Premise: p

Conclusion: p + q (or any var)

Simplification

Premise: p \ q

Conclusion: p

Conjunction

Premises: p, q

Conclusion: p \ q

Resolution

Premise: p + q, p’ + r

Conclusion: q + r

Constructive dilemma

Premises: p→q, r→s, p + r

Conclusion: q + s

Universal instantiation

Premise: AxP(x)

Conclusion: P(k)

Universal generalization

Premise: P(k) for arbitrary k

Conclusion: AxP(x)

Existential instantiation

Premise: ExP(x)

Conclusion: P(k)

Existential generalization

Premise: P(k)

Conclusion: ExP(x)

Quantifier negation

(AxP(x))’ = Ex(P(x))’

Quantifier distribution

Ax(P \ Q) = AxP \ AxQ/Ex(P + Q) = ExP + ExQ

Four Conditional Laws

1) p→q = p’ + q

2) p→q = q’→p’

3) p← → q = (p→q) \ (q→p) = (p \ q) + (p’ \ q’)

4) (p→q)’ = p \ q’