Boolean Algebra

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

Expressions

• Consistent: if it cannot be both true and false
• Complete: if every fully instantiated expression if true or false
• Tautology: if it evaluates to true for every combination of its propositional variables
• Contradiction: if it evaluates to false for every combination of its propositional variables

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 only if Q
• P is a sufficient condition of Q
• Q is a necessary condition for P
$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.

• The truth set of $P(x)$: $\{ x \mid P(x) \}$
• The truth set of $\lnot P(x)$: $U \setminus \{ x \mid P(x) \}$