Predicates and Quantifiers

Why This Matters

Propositional logic lets you reason about specific true/false statements. But what if you need to say "every user in this list has a valid email" or "there exists a product with price under ten dollars"? You need predicates -- statements whose truth value depends on a variable. Predicates turn static propositions into flexible templates that can be applied across entire collections.

The universal quantifier ("for all") and the existential quantifier ("there exists") let you make claims about every element or at least one element in a domain. In code, array.every() is the universal quantifier and array.some() is the existential quantifier. In SQL, a WHERE clause with a subquery uses EXISTS for the same purpose.

Understanding quantifiers is essential for writing correct loop invariants, specifying API contracts, and reasoning about database constraints. Every time you write a validation rule that must hold for all items or check if any item matches, you are using predicate logic.

Define Terms

Visual Model

Code Example

// A predicate is a function that returns boolean
const isEven = (x) => x % 2 === 0;
const isPositive = (x) => x > 0;

const numbers = [2, 4, 6, 8, 10];

// Universal quantifier: for all x, isEven(x)
console.log("All even?", numbers.every(isEven));       // true
console.log("All positive?", numbers.every(isPositive)); // true

// Existential quantifier: there exists x, isEven(x)
const mixed = [1, 3, 4, 7, 9];
console.log("Any even?", mixed.some(isEven));    // true (4 is even)
console.log("All even?", mixed.every(isEven));   // false

// Custom forAll and exists functions
function forAll(arr, predicate) {
  for (const item of arr) {
    if (!predicate(item)) return false;
  }
  return true;
}

function exists(arr, predicate) {
  for (const item of arr) {
    if (predicate(item)) return true;
  }
  return false;
}

console.log("forAll even:", forAll([2,4,6], isEven));  // true
console.log("exists even:", exists([1,3,5], isEven));  // false

// Negation: NOT forAll P === exists NOT P
const data = [1, 2, 3, 4, 5];
const notAllEven = !forAll(data, isEven);
const existsOdd = exists(data, x => !isEven(x));
console.log("NOT forAll even:", notAllEven);   // true
console.log("exists odd:", existsOdd);          // true
console.log("They match:", notAllEven === existsOdd); // true

Interactive Experiment

Try these exercises:

• Define a predicate isAdult(age) that returns true if age is at least 18. Test it with forAll on [20, 25, 30] and [15, 20, 25].
• Verify the negation rule: show that !arr.every(p) gives the same result as arr.some(x => !p(x)) for several arrays and predicates.
• Write a predicate isPrime(n) and use exists to check if any number in [10, 11, 12, 13] is prime.
• What happens when you apply forAll to an empty array? What about exists on an empty array? Why do these results make logical sense?
• Use nested quantifiers: for a 2D array, check if "for all rows, there exists a value greater than 5."

Quick Quiz

Coding Challenge

Real-World Usage

Predicates and quantifiers are at the heart of data processing:

• Form validation: "Every field must be non-empty" is a universal quantifier over form fields. fields.every(f => f.value !== "").
• Database constraints: CHECK constraints and foreign key rules are universal quantifiers: for all rows, this condition must hold.
• API contracts: "There must exist at least one admin user" is an existential quantifier used in system health checks.
• Testing: Test frameworks use expect(arr).toSatisfyAll(pred) for property-based testing, applying universal quantification.
• Search: Finding any match in a collection (arr.find(), SQL EXISTS) is the existential quantifier in action.

Connections