Prolog Cookbook

  1. Documenting, testing, and moduling
  2. Classical Logic
    1. Negation
      1. Not
      2. Difference
      3. Fill Values
      4. De Morgan's Law
    2. Conjunction
      1. And
      2. Intersection
      3. Inner Join
      4. Product
      5. Series
    3. Disjunction
      1. Or
      2. Union
      3. Outer Join
      4. Sum
      5. Parallel
    4. Implication
      1. Proofs
    5. Equivalence
  3. Automata
  4. Graph Traversal
    1. Depth First
    2. Breadth First
    3. Transitive Closures
  5. Route Finding
  6. Puzzle Solving

Product

By Robert Laing

2 Value Algebra

Since conjunction is closely associated with the word and, it jarred me a bit to discover that it is logic’s equivalent of multiplication, while disjunction — commonly thought of as or — is logic’s addition, the arithmetic operator I associate with and.

Why conjunction equates to multiplication is best illustrated by its truth table:

pqp · q
111
100
010
000

Moving from binary to any number of propositions, the universal quantification symbol ∀(p) tends to be used, as in

∀(p) = p1 · p2 · … · pn

Laws Analogous to Arithmetic

  1. The commutative law for AND: pq ≡ qp
  2. The associative law for AND: p(qr) ≡ (pq)r
  3. The distributive law of AND over OR: p(q + r) ≡ (pq + pr)
  4. 1 (TRUE) is the identity for AND: (p AND 1) ≡ p
  5. 0 is the annihilator for AND: (p AND 0) ≡ 0

How conjunction differs from multiplication

  1. The distributive law for OR over AND: (p + qr) ≡ ((p + q)(p + r))
  2. Idempotence of AND: pp ≡ p