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
Laws
Truth Sets

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) \}$