🏠 JavaScript Logic

Enjoying a free online course, General Game Playing, given by Michael Genesereth, got me interested in classical logic and the interesting history of the Victorians who created it.

Thanks to Christine Ladd, what’s generally known as Boolean Algebra is a very simple subject with just five operators. Ladd’s reward from Johns Hopkins University in 1882 was both she and her teacher Charles Sanders Peirce got kicked out.

What I’ve been wrapping my head around doing various database projects is how sets, logic’s five operators, and relational algebra are related, leading to a couple of Aha! moments of how they creep up in various guises in computer coding.

Copulatives ∧, ∨ and ≤

As is sadly common in maths, a subject most people already find intimidating is made incomprehensible by no two textbooks using the same symbols. I favour what’s known as copula notation of ∧ for and and ∨ for or. A reason these are nice is they are handy mnemonics for their set level counterparts, ∩ and ∪.

The most difficult of the five boolean operators to understand is implication. Thanks to picking this notation, I figured out it’s simply ≤ with a corresponding ⊆.

Boolean Algebra’s Five operators

The JavaScript implication only works if we use 1 and 0 instead of true and false.

What is a predicate?

Predicates are functions of zero or more variables that return Boolean values. — Al Aho and Jeff Ullman, Foundations of Computer Science, Chapter 14 Predicate Logic

I tend to use Aho and Ulman’s textbook as my “Oxford Dictionary” for computer jargon, and in coding a function that returns true or false is the general definition of a predicate. Pedantically this isn’t correct since the word originated in grammar where a predicate is the part of the clause of a sentence which is not the subject or object, and in Prolog a predicate is a compound data structure, what JavaScript would call an object.

To confuse things further, there are lots of different conventions for what the two values in Boolean “two value” algebra are. In electrical circuits, true is on and false is off, with conjunction being switches in series and disjunction switches in parallel. JSON includes true and false (along with null) as types, so it’s usually a good choice in JavaScript. However, sometimes it’s more convenient to work with 0 and 1.

If 1 is in the context of a predicate, JavaScript treats it as truthy, and similarly if 0 is in the context of a predicate, JavaScript treats it as falsy.

function pred(n) {
  if (n) {
    return true;
  }
  return false;
}

  it ('1 is true', function () {
    expect(pred(1)).toBe(true);
  });

  it ('0 is false', function () {
    expect(pred(0)).toBe(false);
  });

In JavaScript, not just 1, but any value other than 0 is truthy, while null and undefined are falsy.

Conjunction as in AND

Conjunction in programing is generally though of as AND. It terms of program flow, it can be thought of as nesting an if statement inside another:

  it ('p and q', function() {
    function and(p, q) {
      return (p && q);
    }
    expect(and(true, true)).toBe(true);
    expect(and(true, false)).toBe(false);
    expect(and(false, true)).toBe(false);
    expect(and(false, false)).toBe(false);
  });

  it ('and as nested ifs', function() {
    function and(p, q) {
      if (p) {
        if (q) {
          return true;
        }
      }
      return false;
    }
    expect(and(true, true)).toBe(true);
    expect(and(true, false)).toBe(false);
    expect(and(false, true)).toBe(false);
    expect(and(false, false)).toBe(false);
  });

Disjunction as in OR

Conjunction in programing is generally though of as OR. It terms of program flow, it can be thought of as if statements on the same level:

  it ('p or q', function() {
    function or(p, q) {
      return (p || q);
    }
    expect(or(true, true)).toBe(true);
    expect(or(true, false)).toBe(true);
    expect(or(false, true)).toBe(true);
    expect(or(false, false)).toBe(false);
  });

true or 1, false or 0?

As explained in the next session, the usual rules of algebra apply to Boolean alebra if we think of variables p and q holding 0 or 1. Implication is completely incomprehensible unless p and q are thought to be 0 or 1.

Conjunction as in times and disjunction as in plus

Something I wished I knew back in college where I wasted time in exams writing out truth tables to check if two logic expressions were equivalent was this can be done much more quickly and easily if we think of AND as multiplication and OR as addition.

  it ('and as p * q', function() {
    function and(p, q) {
      return p * q;
    }
    expect(and(1, 1)).toBe(1);
    expect(and(1, 0)).toBe(0);
    expect(and(0, 1)).toBe(0);
    expect(and(0, 0)).toBe(0);
  });

  it ('or as p + q', function() {
    function or(p, q) {
      return p + q;
    }
    expect(or(1, 1)).toBe(2);
    expect(or(1, 0)).toBe(1);
    expect(or(0, 1)).toBe(1);
    expect(or(0, 0)).toBe(0);
  });

That in logic 1 + 1 = 1 has caused rows dating back to the field’s Victorian pioneers George Boole and William Stanley Jevons.

In 1863 Jevons wrote to Boole that surely Boole’s operation of addition should be replaced by the more natural ‘inclusive or’ (or ‘union’), leading to the law X+X=X. Boole completely rejected this suggestion (it would have destroyed his system based on ordinary algebra) and broke off the correspondence. — The Algebra of Logic Tradition.

I hadn’t heard of Jevons until I got interested in classical logic. While his contemporary Charles Babbage became popularly known as a computing pioneer, few people have heard of Jevons even though his logic piano was actually the first digital (as in four bit) computer ever built.

Conjunction as in minimum and disjunction as in maximum

Reading Robert Kowalski’s Logic for Problem Solving, something that confused me was he referred to “and-or trees” as opposed to the more usual “minimax trees”.

Then I had a bit of an epiphany: assuming one thinks in terms of 0 and 1, and is the same as min and or the same as max, sidestepping the 1 + 1 = 1 debacle.

  it ('and as min(p, q)', function() {
    function and(p, q) {
      return Math.min(p, q);
    }
    expect(and(1, 1)).toBe(1);
    expect(and(1, 0)).toBe(0);
    expect(and(0, 1)).toBe(0);
    expect(and(0, 0)).toBe(0);
  });

  it ('or as max(p, q)', function() {
    function or(p, q) {
      return Math.max(p, q);
    }
    expect(or(1, 1)).toBe(1);
    expect(or(1, 0)).toBe(1);
    expect(or(0, 1)).toBe(1);
    expect(or(0, 0)).toBe(0);
  });

And and or aren’t necessarily just binary operators. As with multiplication and addition, there could be any number of predicates to aggregate with these operators. Thinking of or as addition could result in a very higher sum (which is ok in JavaScript since anything other than 0 is true). Using Math.max() handles that since it can take any number of ones and zeros.

anding and oring arrays of booleans

A way to handle any number of predicates to and or or, we could put them in an array and use reduce:

  it ('anding a list of booleans true', function () {
    expect([true, true, true, true]
           .reduce((a, b) => a && b, true)).toBe(true);
  });

  it ('anding a list of booleans false', function () {
    expect([true, true, true, false]
           .reduce((a, b) => a && b, true)).toBe(false);
  });

  it ('oring a list of booleans false', function () {
    expect([false, false, false, false]
           .reduce((a, b) => a || b, false)).toBe(false);
  });

  it ('oring a list of booleans true', function () {
    expect([false, false, false, true]
           .reduce((a, b) => a || b, false)).toBe(true);
  });

A thing to note is the choice of initial value for the accumulator. Again the similarity with and and sum is shown in that we start with false or 0.

If wanted to take the product of an array of numbers, we would make the initial value of the accumulator 1, and with or it’s true.

Implication

A convention I’ve addopted (which I haven’t seen elsewhere) is to use p ≤ q instead of p ⇒ q. As the truth table shows, it gives the expected results for 1 and 0. Writing p ≤ q has a further advantage of again being a spiky version of its set rounded counterpart P ⊆ Q.

  it ('implication', function() {
    function implication(a, b) {
      return a <= b;
    }
    expect(implication(1, 1)).toBe(true);
    expect(implication(1, 0)).toBe(false);
    expect(implication(0, 1)).toBe(true);
    expect(implication(0, 0)).toBe(true);
  });

The meaning of the implication operator ⇒ may appear unintuitive, since we must get used to the notion that “falsehood implies everything.” We should not confuse ⇒ with causation. That is, p ⇒ q may be true, yet p does not “cause” q in any sense. For example, let p be “it is raining,” and q be “Sue takes her umbrella.” We might assert that p ⇒ q is true. It might even appear that the rain is what caused Sue to take her umbrella. However, it could also be true that Sue is the sort of person who doesn’t believe weather forecasts and prefers to carry an umbrella at all times. — Al Aho and Jeff Ullman, Chapter 12 Propositional Logic

Unlike and and or which we can think of as aggregator functions which take any number of

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Logical_NOT

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Strict_equality

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/some