Homepage

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:

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

Commutative Laws

Associative Laws

Idempotent Laws

Absorption Laws

Double Negation Law

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.