Boolean Algebra

Boolean algebra is the branch of algebra in which the values of the variables are the truth values true and false

Expressions

Operators

Exclusive Or

P or Q, but not both: P + Q = (P \land \lnot Q) \lor (\lnot P \land Q) .

P Q P + Q P \land \lnot Q \lnot P \land Q
F F F F F
F T T F T
T F T T F
T T F F F

Nor

Neither P nor Q: P \downarrow Q = \lnot P \land \lnot Q .

P Q P \downarrow Q \lnot P \lnot Q
F F T T T
F T F T F
T F F F T
T T F F F

Negative And (NAND)

P and Q are not both true: P \mid Q = \lnot P \lor \lnot Q .

P Q P \mid Q \lnot P \lnot Q
F F T T T
F T T T F
T F T F T
T T F F F

Conditional

If P, then Q: P \rightarrow Q = \lnot P \lor Q . It is sometimes described like this:

P Q P \rightarrow Q \lnot P
F F T T
F T T T
T F F F
T T T F

A conditional can also be expressed in the following form, called contrapositive: P \rightarrow Q = \lnot Q \rightarrow \lnot P .

P Q \lnot Q \rightarrow \lnot P \lnot Q \lnot P
F F T T T
F T T F T
T F F T F
T T T F F

Proof:

\begin{align} P \rightarrow Q &= \lnot Q \rightarrow \lnot P \\ &= Q \lor \lnot P \\ &= \lnot P \lor Q \\ &= P \rightarrow Q \end{align}

Biconditional (iff)

P if and only Q: P \iff Q = (P \rightarrow Q) \land (Q \rightarrow P) .

P Q P \iff Q P \rightarrow Q Q \rightarrow P
F F T T T
F T F T F
T F F F T
T T T T T

Laws

DeMorgan’s Laws

\lnot (P \land Q) = \lnot P \lor \lnot Q \\ \lnot (P \lor Q) = \lnot P \land \lnot Q

Commutative Laws

P \land Q = Q \land P \\ P \lor Q = Q \lor P

Associative Laws

P \land (Q \land R) = (P \land Q) \land R \\ P \lor (Q \lor R) = (P \lor Q) \lor R

Idempotence Laws

P \land P \iff P \\ P \lor P \iff P

Unit Element Laws

P \land true \iff P \\ P \lor true \iff true

Zero Element Laws

P \land false \iff false \\ P \lor false \iff P

Complement Laws

P \land \lnot P \iff false \\ P \lor \lnot P \iff true

Distributive Laws

P \land (Q \lor R) = (P \land Q) \lor (P \land R) \\ P \lor (Q \land R) = (P \lor Q) \land (P \lor R)

Absorption Laws

P \lor (P \land Q) = P \\ P \land (P \lor Q) = P

Double Negation Law

\lnot \lnot P = P

Truth Sets

The truth set of a statement P(x) is the set of all values of x that make the statement P(x) true.