Boolean Logic in JavaScript

Part 2: Logical Equivalencies

This is part of a series. Read parts 1, 3, and 4.

Photo by Chris Lawton on Unsplash

As stated in the previous article, expressions which produce the same truth table can be substituted for each other. This article covers several examples of Rules of Replacements that I often use. No truth tables are included here, but you can construct them yourself to prove that these rules are correct.

Double Negation

Logically, A and !!A are equivalent, so you can always remove a double negation or add a double negation to an expression without changing its truthiness. Adding a double-negation comes in handy when you want to negate part of a complex expression, perhaps using DeMorgan’s Laws. The one caveat here is that in JavaScript, !! also acts to coerce a value into a boolean, which may be an unwanted side-effect.

A === !!A

Commutation

Any disjunction (||), conjunction (&&), or bicondition (===) can swap the order of its parts*.

(A || B) === (B || A)
(A && B) === (B && A)
(A === B) === (B === A)

Association

Disjunctions and conjunctions are binary operations, meaning they only operate on two inputs. While they can be coded in longer chains — A || B || C || D — they are implicitly associated from left to right — ((A || B) || C) || D. The rule of association states that the order in which these groupings occur make no difference to the logical outcome.

((A || B) || C) === (A || (B || C))
((A && B) && C) === (A && (B && C))

Distribution

Association does not work across both conjunctions and disjunctions. That is, (A && (B || C)) !== ((A && B) || C). In order to disassociate B and C in the previous example, you must distribute the conjunction — (A && B) || (A && C). This process also works in reverse. If you find a compound expression with a repeated disjunction or conjunction, you can un-distribute it, akin to factoring out a common factor in an algebraic expression.

(A && (B || C)) === ((A && B) || (A && C))
(A || (B && C)) === ((A || B) && (A || C))

Another common occurrence of distribution is double-distribution (similar to FOIL in algebra):
1. ((A || B) && (C || D)) === ((A || B) && C) || ((A || B) && D)
2. ((A || B) && C) || ((A || B) && D) ===
((A && C) || B && C)) || ((A && D) || (B && D))

(A || B) && (C || D) === (A && C) || B && C) || (A && D) || (B && D)
(A && B) ||(C && D) === (A || C) && (B || C) && (A || D) && (B || D)

Material Implication

Implication expressions (A → B) typically get translated into code as if (A) { B } but that is not very useful if a compound expression has several implications in it. You would end up with nested if statements — a code smell. Instead, I often use the material implication rule of replacement, which says that A → B means either A is false or B is true.

(A → B) === (!A || B)

Tautology & Contradiction

Sometimes during the course of manipulating compound logical expressions, you’ll end up with a simple conjunction or disjunction that only involves one variable and its negation or a boolean literal. In those cases, the expression is either always true (a tautology) or always false (a contradiction) and can be replaced with the boolean literal in code.

(A || !A) === true
(A || true) === true
(A && !A) === false
(A && false) === false

Related to these equivalencies are the disjunction and conjunction with the other boolean literal. These can be simplified to just the truthiness of the variable.

(A || false) === A
(A && true) === A

Transposition

When manipulating an implication (A → B), a common mistake people make is to assume that negating the first part, A, implies the second part, B, is also negated — !A → !B. This is called the converse of the implication and it is not necessarily true. That is, having the original implication does not tell us if the converse is true because A is not a necessary condition of B. (If the converse is also true — for independent reasons — then A and B are biconditional.)

What we can know from the original implication, though, is that the contrapositive is true. Since B is a necessary condition for A (recall from the truth table for implication that if B is true, A must also be true for the implication to be true), we can claim that !B → !A.

(A → B) === (!B → !A)

Material Equivalence

The name biconditional comes from the fact that it represents two conditional (implication) statements: A === B means that A → B and B → A. The truth values of A and B are locked into each other. This gives us the first material equivalence rule:

(A === B) === ((A → B) && (B → A))

Using material implication, double-distribution, contradiction, and commutation, we can manipulate this new expression into something easier to code:
1. ((A → B) && (B → A)) === ((!A || B) && (!B || A))
2. ((!A || B) && (!B || A)) ===
((!A && !B) || (B && !B)) || ((!A && A) || (B && A))
3. ((!A && !B) || (B && !B)) || ((!A && A) || (B && A)) ===
((!A && !B) || (B && A))
4. ((!A && !B) || (B && A)) === ((A && B) || (!A && !B))

(A === B) === ((A && B) || (!A && !B))

Exportation

Nested if statements, especially if there are no else parts, are a code smell. A simple nested if statement can be simplified into a single statement where the conditional is a conjunction of the two previous conditions:

if (A) {
  if (B) {
    C
  }
}
// is equivalent to
if (A && B) {
  C
}

(A → (B → C)) === ((A && B) → C)

DeMorgan’s Laws

DeMorgan’s Laws are essential to working with logical statements. They tell how to distribute a negation across a conjunction or disjunction. Consider the expression !(A || B). DeMorgan’s Laws say that when negating a disjunction or conjunction, negate each statement and change the && to || or vice versa. Thus !(A || B) is the same as !A && !B. Similarly, !(A && B) is equivalent to !A || !B.

!(A || B) === !A && !B
!(A && B) === !A || !B

Ternary (If-Then-Else)

Ternary statements (A ? B : C) occur regularly in programming, but they’re not quite implications. The translation from a ternary to formal logic is actually a conjunction of two implications, A → B and !A → C, which we can write as: (!A || B) && (A || C), using material implication.

(A ? B : C) === (!A || B) && (A || C)

XOR (Exclusive Or)

Exclusive Or, often abbreviated xor, means, “one or the other, but not both.” This differs from the normal or operator only in that both values cannot be true. This is often what we mean when we use “or” in plain English. JavaScript doesn’t have a native xor operator, so how would we represent this?
1. “A or B, but not both A and B”
2. (A || B) && !(A && B) direct translation
3. (A || B) && (!A || !B) DeMorgan’s Laws
4. (!A || !B) && (A || B) commutativity
5. A ? !B : B if-then-else definition

A ? !B : B is exclusive or (xor) in JavaScript

Alternatively,
1. “A or B, but not both A and B”
2. (A || B) && !(A && B) direct translation
3. (A || B) && (!A || !B) DeMorgan’s Laws
4. (A && !A) || (A && !B) || (B && !A) || (B && !B) double-distribution
5. (A && !B) || (B && !A) contradiction replacement
6. A === !B or A !== B material equivalence

A === !B or A !== B is xor in JavaScript

Next: Universal and Existential Statements.