Boolean logic
Two-valued system
Boolean logic involves truth values, variables, and connectives. Truth values are limited to true or false (often T or F).
Complex 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
We often 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.
SAT: Boolean satisfiability
Generally, satisfiability is the problem of finding whether an assignment truth values to Boolean variables in a given Boolean expression can be made such that the entire expression evaluates to true (or not).
For example, which of the following are satisfiable?
- (p_1 \lor (p_2 \land \neg p_2)
- (p_1 \lor p_2) \land (p_1 \implies p_2)
- (p_1 \land p_2) \land (\neg p_2 \land p_3)
- \neg(p_1 \land p2) \land \neg(\neg p_1 \land p_3)
Here are the solutions:
(p_1 \lor (p_2 \land \neg p_2) can be satisfied with p_1 true and either true or false for p_2 (doesn't matter what we assign to p_2).
(p_1 \lor p_2) \land (p_1 \implies p_2). This can be rewritten as (p_1 \lor p_2) \land (\neg p_1 \lor p_2). So this can be satisfied with p_2 true. It doesn't matter what we assign to p_1.
(p_1 \land p_2) \land (\neg p_2 \land p_3) is unsatisfiable.
\neg(p_1 \land p2) \land \neg(\neg p_1 \land p_3) can be rewritten:
(\neg p_1 \lor \neg p_2) \land (\neg\neg p_1 \lor \neg p_3) which is
(\neg p_1 \lor \neg p_2) \land (p_1 \lor \neg p_3).
So this, too, is satisfiable with the assignment p_2 false and p_3 false (the assignment to p_1 doesn't matter).
3SAT
3SAT is a special form of satisfiability, in which the Boolean expression is in 3CNF, conjunctive normal form.
3SAT is the first \mathsf{NP}-complete problem (Cook / Levin). All problems in \mathsf{NP} can be reduced to 3SAT in polynomial time, and solutions can be verified in polynomial time. However, producing a solution (apart from trivial cases) requires exponential time.
Conjunctive normal form (CNF)
All Boolean satisfiability problems can be rendered in conjunctive normal form.
Example: (p_1 \lor p_2 \lor p_3) \land p_4 \land (p_3 \lor p_4 \lor \neg p_2) \land (\neg p_1 \lor \neg p_6) \land (\neg p_1 \lor p_2 \lor \neg p_5)
Notice each clause is a disjunction, and clauses are connected by conjunction.
3CNF
3CNF normalizes CNF further, requiring that all clauses have exactly three Boolean variables. Rewriting any Boolean expression to 3CNF can be done in polynomial time. For example,
- we rewrite P \Longleftrightarrow Q as (P \implies Q) \land (Q \implies P),
- we rewrite P \implies Q as \neg P \lor Q,
- we "push" negation down to the level of atomic formulas,
- we apply distributive laws, etc.., and
- we add "dummy" variables as needed.
For example, the formula given earlier can be rendered in 3CNF as
(p_1 \lor p_2 \lor p_3) \land (p_4 \lor \neg q \lor q) \land (p_3 \lor p_4 \lor \neg p_2) \land (\neg p_1 \lor \neg p_6 \lor \neg r) \land (\neg p_1 \lor p_2 \lor \neg p_5).
Copyright © 2023–2026 Clayton Cafiero
No generative AI was used in producing this material. This was written the old-fashioned way.