14  Predicate Logic and Boolean Algebra

15 Predicate Logic and Boolean Algebra

Week 6, Session 2. CSS 342.

15.1 Warmup

Translate into precise English: ∀x ∃y (y > x). Now negate it. What does the negation say in English?

Original: “for every x there exists a y greater than x.” Negation: ∃x ∀y (y ≤ x), i.e., “there is some x such that every y is at most x.” Equivalently: “there is a largest element.”

That negation rule is the centerpiece of this chapter.

15.2 Learning objectives

  1. Translate English statements into predicate logic using ∀ and ∃.
  2. Correctly negate universally and existentially quantified statements.
  3. Simplify Boolean expressions using algebraic laws (De Morgan, absorption, distribution).
  4. Convert a Boolean expression to CNF or DNF.
  5. Relate Boolean algebra to the logic inside C++ conditionals.

15.3 Predicates and quantifiers

A predicate is a proposition with parameters: P(x) is “x is even.” P(4) is true; P(5) is false.

Two quantifiers turn a predicate into a statement:

  • Universal ∀x P(x): “for all x, P(x) holds.”
  • Existential ∃x P(x): “there exists x such that P(x) holds.”

In code:

#include <algorithm>

bool allEven = std::all_of(v.begin(), v.end(),
                          [](int x){ return x % 2 == 0; });

bool anyEven = std::any_of(v.begin(), v.end(),
                          [](int x){ return x % 2 == 0; });

all_of is ∀; any_of is ∃. The STL handed you the quantifiers and named them in English.

15.4 Negating quantifiers

The key identities:

\[ \neg(\forall x \; P(x)) \equiv \exists x \; \neg P(x) \]

\[ \neg(\exists x \; P(x)) \equiv \forall x \; \neg P(x) \]

In words: “not all are P” means “at least one is not P.” “Not any is P” means “every one is not P.”

In code:

bool notAllEven = !std::all_of(v.begin(), v.end(), isEven);
// is equivalent to:
bool atLeastOneOdd = std::any_of(v.begin(), v.end(),
                                [](int x){ return x % 2 != 0; });

“Not all” does not mean “none.” Students conflate these all the time. “Not all swans are white” allows one white swan. “No swans are white” allows zero.

15.5 Nested quantifiers

Order matters.

  • ∀x ∃y P(x, y): for every x, some y (which may depend on x) makes P true.
  • ∃y ∀x P(x, y): there is one y that works for every x.

Example. P(x, y) = “y is greater than x.”

  • ∀x ∃y (y > x): “for every number there is a bigger one.” True (over integers).
  • ∃y ∀x (y > x): “there is a number greater than every number.” False (there is no biggest integer).

Swap the quantifiers, change the meaning.

15.6 Boolean algebra

Same operators, expressed as algebra. Variables are 0/1; operators are AND (·), OR (+), NOT (¬ or overbar).

Axioms (selection):

Law Statement
Commutative a + b = b + a, a·b = b·a
Associative (a + b) + c = a + (b + c)
Distributive a · (b + c) = a·b + a·c
Identity a + 0 = a, a · 1 = a
Null a + 1 = 1, a · 0 = 0
Idempotent a + a = a, a · a = a
Complement a + ¬a = 1, a · ¬a = 0
De Morgan ¬(a · b) = ¬a + ¬b, ¬(a + b) = ¬a · ¬b
Absorption a + a·b = a, a · (a + b) = a

The absorption laws are the most surprising. Worth proving on a truth table.

15.7 CNF and DNF

Disjunctive Normal Form (DNF): OR of ANDs. (a · b) + (a · ¬c) + (¬b · c).

Conjunctive Normal Form (CNF): AND of ORs. (a + b) · (¬a + c) · (b + ¬c).

Every Boolean expression has an equivalent DNF and an equivalent CNF. You derive DNF from a truth table by OR-ing together the “true rows” and CNF by AND-ing the negations of the “false rows.”

DNF for the truth table:

a b f
0 0 0
0 1 1
1 0 1
1 1 0

True rows: (a=0, b=1) and (a=1, b=0). DNF: (¬a · b) + (a · ¬b). (This is XOR.)

15.8 Simplifying a circuit

Given (a + b) · (a + ¬b). Distributive law:

(a + b)(a + ¬b)
= a·a + a·¬b + b·a + b·¬b
= a + a·¬b + a·b + 0
= a + a·(¬b + b)
= a + a·1
= a + a
= a

Simplification can save real gates in hardware. In software it usually saves clarity, which matters more than instruction count for the size of code you write in this class.

15.9 Try it

Use std::all_of or std::any_of to write everyElementPositive(const vector<int>&) and someElementNegative(const vector<int>&). Note the relationship: someElementNegative(v) is !everyElementNonNegative(v).

15.10 Self-check

1. Negate ∀x (x > 0 → x² > 0):
c. Push the negation through: ¬∀ becomes ∃; ¬(P → Q) becomes P ∧ ¬Q.
2. std::all_of(v.begin(), v.end(), pred) formalizes which quantifier?
b. All elements satisfy pred.

15.11 Challenges

  1. Translate “every nonempty vector has a maximum element” into predicate logic and write the contrapositive.
  2. Derive the DNF for “exactly two of (a, b, c) are true.”
  3. Implement noneOf using only all_of (hint: use the predicate’s negation).

15.12 Where this fits

We now have the vocabulary to talk about correctness — invariants, preconditions, postconditions. Next chapter switches gears: we need a way to talk about how fast algorithms run.

You are here Coming up
Predicates, quantifiers, Boolean algebra, normal forms Chapter 13: big-O, big-Omega, big-Theta