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

De Morgan's Law

By Robert Laing

What I took to calling copula notation because I read somewhere that the ∧ and ∨ symbols are called copulas (but I can’t find the reference again) is a handy mnemonic for remembering two substitution rules commonly called De Morgan’s Laws:

  1. ¬(p ∧ q) can be substituted with ¬p ∨ ¬q
  2. ¬(p ∨ q) can be substituted with ¬p ∧ ¬q

There’s an interesting relationship with set theory in that

  1. (P ∩ Q)c can be substituted with Pc ∪ Qc
  2. (P ∪ Q)c can be substituted with Pc ∩ Qc

A handy feature of De Morgan’s Law is it isn’t just binary. It applies to any number of propositions:

p1 · p2 · … · pi = p1 + p2 + … + pi