🏠 JavaScript Logic

By Robert Laing

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

Name Predicate Set JavaScript
Conjunction p ∧ q P ∊ Q p && q
Disjunction p ∨ q P ∪ Q p || q
Implication a ≤ b A ⊆ B a <= b
Equivalence a ⇔ b A ⇔ B a === b
Negation p PC !p

The number of operators could actually be reduced to three by rewriting implication and equivalence in conjunctive normal form.

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.

Boolean Coercion

Before I discovered JavaScript’s builtin Boolean(p) coercion function, I tested if something was truthy or falsy like this:

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

Returning true from an if block is generally considered a nooby mistake in computer coding because if n wasn’t true, return true wouldn’t be called anyway, so one could simply return n; to get true or false. But since 1 is only true in the context of say, if (1) {...}, I thought JavaScript was an exception to this rule. Then I discovered that rather than my pred(n) function, I could use Boolean(n);

As explained in negation, since JavaScript’s unary operator ! converts truthy values to false and falsy values to true, !!p does the same as Boolean(p), but I’m ideologically opposed to multiple exclamation marks.

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

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

In JavaScript, not just 1, but any value is truthy except 0, false, null, undefined, the empty string "", and NaN which are falsy.

  it ('2 is true', function () {
    expect(Boolean(2)).toBe(true);
  });

  it ('-2 is true', function () {
    expect(Boolean(-2)).toBe(true);
  });

  it ('null is false', function () {
    expect(Boolean(null)).toBe(false);
  });

  it ('undefined is false', function () {
    expect(Boolean(undefined)).toBe(false);
  });

  it ('NaN is false', function () {
    expect(Boolean(NaN)).toBe(false);
  });

  it ('"any text" is true', function () {
    expect(Boolean("any text")).toBe(true);
  });

  it ('"" is false', function () {
    expect(Boolean("")).toBe(false);
  });

Because an empty string is false, I wrongly assumed empty arrays and objects would be false:

  it ('an empty array is true', function () {
    expect(Boolean([])).toBe(true);
  });

  it ('an empty object is true', function () {
    expect(Boolean({})).toBe(true);
  });

I use Array.length to check:

  it('empty array is false', function() {
    expect([].length > 0).toBe(false);
  });

  it('empty object is false', function() {
    expect(Object.keys({}).length > 0).toBe(false);
  });

Jasmine’s logic matchers

Since I’m using Jasmine as my testing framework, I could use some of its many matchers to avoid Boolean coercion:

Jasmine has too many matchers to remember, with lots of synonyms like toBeTrue() for toBe(true) etc. Personally I find expect(a < b).toBe(true) easier than expect(a).toBeLessThan(b), but I guess there are use cases where these many options are handy.

Conjunction as in AND

Conjunction in programing is generally thought of as AND.

  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);
  });

As discussed in true or 1, false or 0?, && only returns true and false in the above examples because those were its inputs. If given other truthy or falsy values, it returns one of those with possibly unexpected results:

  it('p && q returns last truthy or first falsy value', function() {
    expect(2 && 1).toBe(1);
    expect(1 && 2).toBe(2);
    expect(null && undefined).toBe(null);
  });

It terms of program flow, conjunction can be thought of as nesting an if statement inside another:

  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

Disjunction in programing is generally though of as OR.

  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);
  });

As with && above, || only returns true and false in the above examples because those were its inputs. If given other truthy or falsy values, it returns one of those with possibly unexpected results:

  it('p || q returns first truthy or last falsy value', function() {
    expect(2 || 1).toBe(2);
    expect(1 || 2).toBe(1);
    expect(null || undefined).toBe(undefined);
  });

It terms of program flow, disjunction can be thought of as if statements on the same level:

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

How ∧ is related to ∊ 

  it ('AND and intersection using &&', function() {
    const U = ["a","b","c","d","e","f","g","h","i",
               "j","k","l","m","n","o","p","q","r",
               "s","t","u","v","w","x","y","z"];
    const A = ["a","b","c","d","e","f"];
    const B = ["e","f","g","h","i","j"];
    const I = U.filter((e) => A.includes(e) && B.includes(e));
    expect(I).toEqual(["e","f"]);
  });

The above example is mainly for illustrative purposes. Using JavaScript’s set intersection, we can do it without defining a universal set U:

  it ('Intersection of two arrays using Set', function() {
    const A = new Set(["a","b","c","d","e","f"]);
    const B = new Set(["e","f","g","h","i","j"]);
    expect(A.intersection(B)).toEqual(new Set(["e","f"]));
    expect(B.intersection(A)).toEqual(new Set(["e","f"]));
  });

Another way is to think of the intersection as a subset (ie filtered array in JavaScript):

  it ('Intersection of two arrays uing filter', function() {
    const A = ["a","b","c","d","e","f"];
    const B = ["e","f","g","h","i","j"];
    expect(A.filter((e) => B.includes(e))).toEqual(["e","f"]);
    expect(B.filter((e) => A.includes(e))).toEqual(["e","f"]);
  });

How ∨ is related to ∪ 

  it ('OR and union using ||', function() {
    const U = ["a","b","c","d","e","f","g","h","i",
               "j","k","l","m","n","o","p","q","r",
               "s","t","u","v","w","x","y","z"];
    const A = ["a","b","c","d","e","f"];
    const B = ["e","f","g","h","i","j"];
    const I = U.filter((e) => A.includes(e) || B.includes(e));
    expect(I).toEqual(["a","b","c","d","e","f","g","h","i","j"]);
  });

Again the above is just for illustrative purposes, and in practice we would use JavaScript’s union set operator so as to avoid defining the universal set U:

  it ('Union of two arrays using Set', function() {
    const A = new Set(["a","b","c","d","e","f"]);
    const B = new Set(["e","f","g","h","i","j"]);
    expect(A.union(B)).toEqual(new Set(["a","b","c","d","e","f","g","h","i","j"]));
    expect(B.union(A)).toEqual(new Set(["a","b","c","d","e","f","g","h","i","j"]));
  });

true or 1, false or 0?

As explained in the next section, an advantage of using 1 and 0 instead of true and false is the usual rules of algebra apply to Boolean algebra. Implication is completely incomprehensible unless p and q are thought to be 0 or 1.

Switching is fairly easy thanks to a subtlety of JavaScript’s && and || operators: they aren’t strictly predicates (ie things that return true or false), but rather polymorphic in that they return whatever truthy or falsy values they were handed.

  it ('p && q with 0 and 1', 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 ('p || q with 0 and 1', function() {
    function or(p, q) {
      return (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);
  });

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);
  });

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 results in a bigger number than 1 which is ok in JavaScript since anything other than 0 is true.

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.

The issue of whether OR can add up to more than one creeps up in program control flow. For instance, JavaScript’s switch statement is a form of disjunction. A convention JavaScript adopted from C (which C’s creators have dropped in their newer language Go) is that a matching case needs to have a terminating return or break, else it continues to try match futher cases — ie ORs to possibly several values.

Usually we want OR to result in one thing or nothing, so that’s a common source of bugs.

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);
  });

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 or and sum is shown in that we start with false or 0, while and is product in that we start with true or 1.

Implication p ≤ q

Implication and equivalence differ from the other three logical operators in that instead of having booleans as their inputs, these can have numbers, text, arrays, objects, … whatever as their inputs but return a boolean. Each type of input represents a different example, but the return value is always a boolean.

Initially limiting to 0 and 1 as input type, a convention I’ve adopted (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

p ≤ q = p ∨ q

Implication can be rewritten in conjunctive normal form as

p ≤ q = p ∨ q

In JavaScript:

  it ('implication with not and or', function() {
    function implication(p, q) {
      const notP = ((p === 1) ? 0 : 1);
      return notP || q;
    }
    expect(implication(1, 1)).toBe(1);
    expect(implication(1, 0)).toBe(0);
    expect(implication(0, 1)).toBe(1);
    expect(implication(0, 0)).toBe(1);
  });

This is a handy formula to remain in the domain of 0 and 1 without switching to true and false, and can also be used for equivalence if we think of it as reciprocal implication.

How ≤ is related to ⊆

Here isSubsetOf helps a lot:

  it ('isSubsetOf', function() {
    const U = new Set(["a","b","c","d","e","f","g","h","i",
               "j","k","l","m","n","o","p","q","r",
               "s","t","u","v","w","x","y","z"]);
    const A = new Set(["a","b","c","d","e","f"]);
    const X = new Set([1,2,3,4]);
    expect(A.isSubsetOf(U)).toBe(true);
    expect(U.isSubsetOf(U)).toBe(true);
    expect(X.isSubsetOf(U)).toBe(false);
  });

Implication for various types in JavaScript

The concept of “less than or equal to” which is what logical implication boils down to comes up in many different guises in computer coding. Here’s a list of some of JavaScript’s implication functions:

“string”.includes(“substring”)
It has more specialised relatives startsWith(“prefix”) and endsWith(“suffix”). Before I discovered this handy builtin predicate, I checked that indexOf wasn’t -1. This is much easier.
[1,2,3,4].includes(5)
x ∈ A in JavaScript.
new Set([1,2,3,4]).has(5)
According to the documentation, this is a more efficient way of doing x ∈ A in JavaScript.
Array.isArray(myArr)
I find I need this type checker a lot to see if an element is a leaf or a branch in recursive tree or graph traversal.
typeof x
Handy to test if a variable contains a “string”, “number”, “boolean”, or “function”. Arrays are seen as “object”, which is why isArray is needed.

Equality

When dealing with atoms like true === true or 1 === 1, equality is easy and obvious, ignoring all the confusion in programing languages by one equal sign being commonly used to allocate values to variables, two for equality, and then JavaScript’s three for strict equality.

  it ('"1" == 1', function() {
    expect("1" == 1).toBe(true);
  });

  it ('"1" === 1', function() {
    expect("1" === 1).toBe(false);
  });

When it comes to compound data structures, things get very complicated by JavaScript along with most other programing languages comparing memory addresses instead of values as explained in object and array equality.

Equality is reciprocal implication

Of the four binary operators in Boolean algebra, implication is the only one that is not commutative, ie which side of the operator a variable goes matters.

This allows a trick of defining equality as meaning we get the same result for switching the variables around in implication. A handy Boolean equality to remember is:

If a ≤ b ∧ b ≤ a is true, a = b

More practical is the set equivalent because we often need to check if the results of two database queries are the same irrespective of the order of results:

If A ⊆ B ∧ B ⊆ A is true, A = B

 it ('set equality', function() {
   const A = new Set([1,2,3,4]);
   const B = new Set([4,3,2,1]);
   const C = new Set([1,2,3,4,5]);
   expect(A.isSubsetOf(B) && B.isSubsetOf(A)).toBe(true);
   expect(A.isSubsetOf(C) && C.isSubsetOf(A)).toBe(false);
 });

Negation

JavaScript’s unary operator ! always returns true or false, ie it converts truthy values to false and falsy values to true. So an alternative way of Boolean coercion is !!p, but I find Boolean(p) more understandable.

Something that’s cost me marks in a couple of online multiple choice exams is failing to spot the word “not” had been slipped into answers that on a quick read looked correct.

We as humans seem wired to misunderstand negatives, though that may be more of a problem for English and German speakers since latin languages like French make it clearer if a sentence is negative by repeating the “not”.

Because of our common trouble parsing NOT, it’s generally good advice to write predicates in a “positive way” by avoiding !p whenever possible.

For instance, instead of

function myFunc(a) {
  if (!p) {
    // code goes here
  }
}

do

function myFunc(a) {
  if (p) {
    return;
  }
  // code goes here
}

Set difference A - B

The first MooC I ever did was Jennifer Widom’s course on SQL. One of the problems, answering the question “which students did not apply for CS”, illustrated the various pitfalls in what initially seems easy.

An easy way to translate the SQL to JavaScript is to treat the tables as an array of arrays. This means remembering which index number corresponds to which field. Making it an array of object literals would make referencing the columns by name easier, but this takes less space.

const Student = [
[123, 'Amy', 3.9, 1000],
[234, 'Bob', 3.6, 1500],
[345, 'Craig', 3.5, 500],
[456, 'Doris', 3.9, 1000],
[567, 'Edward', 2.9, 2000],
[678, 'Fay', 3.8, 200],
[789, 'Gary', 3.4, 800],
[987, 'Helen', 3.7, 800],
[876, 'Irene', 3.9, 400],
[765, 'Jay', 2.9, 1500],
[654, 'Amy', 3.9, 1000],
[543, 'Craig', 3.4, 2000]
];

const Apply = [
[123, 'Stanford', 'CS', 'Y'],
[123, 'Stanford', 'EE', 'N'],
[123, 'Berkeley', 'CS', 'Y'],
[123, 'Cornell', 'EE', 'Y'],
[234, 'Berkeley', 'biology', 'N'],
[345, 'MIT', 'bioengineering', 'Y'],
[345, 'Cornell', 'bioengineering', 'N'],
[345, 'Cornell', 'CS', 'Y'],
[345, 'Cornell', 'EE', 'N'],
[678, 'Stanford', 'history', 'Y'],
[987, 'Stanford', 'CS', 'Y'],
[987, 'Berkeley', 'CS', 'Y'],
[876, 'Stanford', 'CS', 'N'],
[876, 'MIT', 'biology', 'Y'],
[876, 'MIT', 'marine biology', 'N'],
[765, 'Stanford', 'history', 'Y'],
[765, 'Cornell', 'history', 'N'],
[765, 'Cornell', 'psychology', 'Y'],
[543, 'MIT', 'CS', 'N']
];

I did a Venn diagram in SVG as a learning exercise:

Venn Diagram of college data

Pitfall #1 is to think this can be solved with Apply[2] !== "CS".

  it('Apply[2] !== "CS"', function() {
    const A = new Set(Apply
          .filter((row) => row[2] !== "CS")
          .map((row) => row[0]));
    expect(A).toEqual(new Set([123,234,345,678,765,876]));
  })

The students with IDs 123, 345, 876 appear in the list because they applied for subjects besides “CS”. So here again is an example of why negation is very tricky to get right.

To solve this, we need to create a subset of students who did apply for CS, and then cross them off the list which JavaScript’s difference set operator makes easy. But this leads us to pitfall #2:

  it('Apply.difference(CS)', function() {
    const ApplyIDs = new Set(Apply.map((row) => row[0]));
    const CS = new Set(Apply
                      .filter((row) => row[2] === "CS")
                      .map((row) => row[0]));
    expect(ApplyIDs.difference(CS).toEqual(new Set([234,678,765]));
  });

The reason that’s still the wrong answer is there’s students with IDs 456, 567, 654, and 789 who haven’t applied for anything yet, so should be on the list of students who haven’t applied for CS. Using the wrong superset is a very common mistake.

  it('Student.difference(CS)', function() {
    const StudentIDs = new Set(Student.map((row) => row[0]));
    const CS = new Set(Apply
                      .filter((row) => row[2] === "CS")
                      .map((row) => row[0]));
    expect(StudentIDs.difference(CS).toEqual(new Set([234,456,567,654,678,765,789]));
  });