Boolean Logic

Value

True (T), False (F)

Operators

, negation, not , conjunction, and , disjunction, or , exclusive or, xor , material implication

Laws

De Morgan's Law

Normal forms

Any complex proposition can be represented by propositions that only include AND, OR as well as NOTs. Given a Boolean Function For each line in its truth table

Then we have

Disjunction Normal Form, DNF

Every -variable proposition can be represented by a disjunction normal form

Conjunction Normal Form, CNF

Similarly, we have

e.g.

This is a natural result of De Morgan's Law

Representation with Least Operators

One could use and only use

  1. AND, NOT
  2. OR, NOT
  3. IMPLICATION to represent all Boolean expressions.