Boolean logic

Author

Clayton Cafiero

Published

2025-08-07

Two-valued system

Boolean logic involves truth values, variables, and connectives. Truth values are limited to true or false (often T or F).

Complext Boolean expressions are constructed from variables and connectives.

Connectives:

  • and \land
  • or \lor
  • not \neg
  • implies \implies
  • if and only if \iff
    • also iff, or logical equivalence
  • xor \oplus

I will use these words and their corresponding symbols interchangeably.

Given variables p and q, the following are Boolean expressions:

  • p \land q (p and q, called a conjunction),
  • p \lor q (either p or q or possibly both, called a disjunction),
  • \neg p (not p, called a negation),
  • p \implies q (p implies q, or equivalently if p then q, called an implication or sometimes material implication),
  • p \iff q (p if and only if q, called logical equivalence or biconditional), and
  • p \oplus q (either p or q but not both, called exclusive or).

Connectives are best defined / demonstrated with truth tables.

Truth table: Logical OR (disjunction)

\begin{array}{|c c|c|} p & q & p \lor q\\ \hline T & T & T\\ T & F & T\\ F & T & T\\ F & F & F\\ \end{array}

Either p or q or both are true.

Truth table: Logical AND (conjunction)

\begin{array}{|c c|c|} p & q & p \land q\\ \hline T & T & T\\ T & F & F\\ F & T & F\\ F & F & F\\ \end{array}

Both p and q are true.

Truth table: Logical NOT (negation)

\begin{array}{|c |c|} p & \neg p \\ \hline T & F\\ F & T\\ \end{array}

Truth table: Implication

\begin{array}{|c c|c|} p & q & p \implies q\\ \hline T & T & T\\ T & F & F\\ F & T & T\\ F & F & T\\ \end{array}

Admittedly, these last two take a little getting used to. Think of this as: if p \implies q and p is logically impossible, then anything goes for q—it could be true or false, thus the entire implication is true.

Truth table: Logical IFF (if and only if; biconditional)

We use \iff to indicate implication in both directions. That is

p \iff q

is equivalent to

(p \implies q) \land (q \implies p).

\begin{array}{|c c|c|} p & q & p \iff q\\ \hline T & T & T\\ T & F & F\\ F & T & F\\ F & F & T\\ \end{array}

When we get to proofs, we’ll see that (in virtually all cases) we have to prove each direction separately.

Truth table: Logical XOR (exclusive or)

\begin{array}{|c c|c|} p & q & p \oplus q\\ \hline T & T & F\\ T & F & T\\ F & T & T\\ F & F & F\\ \end{array}

Either p or q but not both.

De Morgan’s laws

De Morgan’s laws come in handy in many proofs

  • The negation of a disjunction is the conjunction of the negations.

  • The negation of a conjunction is the disjunction of the negations.

That is,

\neg (p \lor q) \iff (\neg p) \land (\neg q),

and

\neg (p \land q) \iff (\neg p) \lor (\neg q).

Modus ponens

We’ll see this quite a bit, and it is intuitive.

If p \implies q, and p is true, then q is true.

Copyright © 2023–2025 Clayton Cafiero

No generative AI was used in producing this material. This was written the old-fashioned way.