Остаточний посібник з умовної логіки в JavaScript

Я фахівець-інженер і математик. Я щодня покладаюсь на свою математичну підготовку в написанні коду. Я використовую не статистику чи числення, а моє глибоке розуміння логічної логіки. Часто я перетворював складну комбінацію амперсандів, труб, знаків оклику та знаків рівності на щось простіше і набагато читабельніше. Я хотів би поділитися цими знаннями, тому написав цю статтю. Це довго, але я сподіваюся, це буде для вас таким же корисним, як і для мене. Насолоджуйтесь!

Значення істинності та хибності в JavaScript

Перш ніж вивчати логічні вирази, давайте розберемося, що в JavaScript є "неправдивим". Оскільки JavaScript вільно набирається, він примушує значення в логічні вирази. ifзаяви, &&, ||, і потрійні умови всіх значень примушувати в булеві. Зауважте, що це не означає, що вони завжди повертають логічне значення операції.

Є тільки шість falsy значення в JavaScript - false, null, undefined, NaN, 0, і ""- і все інше truthy . Це означає, що []і {}вони обидва, які, як правило, спотикають людей.

Логічні оператори

У формальній логіці існує лише декілька операторів: заперечення, сполучення, диз'юнкція, імплікація та бікондіція. Кожен з них має еквівалент JavaScript: !, &&, ||, if (/* condition */) { /* then consequence */}, і ===, відповідно. Ці оператори створюють усі інші логічні твердження.

Таблиці правди

Спочатку давайте розглянемо таблиці істинності для кожного з наших основних операторів. Таблиця істинності говорить нам, на чому правдивість виразу базується на правдивості його частин . Таблиці правди важливі. Якщо два вирази генерують одну і ту ж таблицю істинності, то ці вирази еквівалентні і можуть замінювати один одного .

Таблиця заперечень дуже проста. Заперечення - єдиний одинарний логічний оператор, який діє лише на один вхід. Це означає, що !A || Bце не те саме, що !(A || B). Дужки діють як позначення групування, яке ви знайдете в математиці.

Наприклад, перший рядок таблиці істинності заперечень (нижче) слід читати так: "якщо твердження А є Істинним, тоді вираз! А хибний."

Отримати просте твердження не складно. Заперечення «йде дощ» є «він НЕ йде дощ» і заперечення примітивного в JavaScript true, звичайно, false. Однак заперечення складних висловлювань або виразів не так просто. Що означає заперечення “ завжди йде дощ” чи isFoo && isBar?

Таблиця сполучень показує, що вираз A && Bє істинним, лише якщо і A, і B є істинними. Це слід добре знати з написання JavaScript.

Таблиця диз’юнкцій також повинна бути дуже знайомою. Діз'юнкція (логічне твердження АБО) є істинною, якщо одна або обидвіз А і В відповідають дійсності.

Таблиця значень не така звична. Оскільки A передбачає B, A якщо істинно означає, B є істинним. Однак B може бути істинним з причин, відмінних від A, саме тому два останні рядки таблиці відповідають дійсності. Єдиний час, коли значення помилкове, це коли A є істинним, а B - хибним, оскільки тоді A не означає B.

Хоча ifоператори використовуються для імплікації в JavaScript, не всі ifоператори працюють таким чином. Зазвичай ми використовуємо ifяк регулятор потоку, а не як перевірку істинності, де наслідки також мають значення при перевірці. Ось архетипічне твердження про підтекстif :

function implication(A, B) { if (A) { return B; } else { /* if A is false, the implication is true */ return true; }}

Не хвилюйтеся, що це дещо незручно. Існують простіші способи кодування наслідків. Однак через цю незграбність я продовжуватиму використовувати як символ для наслідків у цій статті.

Оператор Bicondition , який іноді називають if-and-only-if (IFF), оцінює істину лише в тому випадку, якщо два операнди, A і B, мають однакові значення істинності. Через те, як JavaScript обробляє порівняння, використання ===для логічних цілей слід використовувати лише на операндах, відтворених на логічні значення. Тобто замість A === B, ми повинні використовувати !!A === !!B.

Застереження

Існує два великі застереження щодо лікування коду JavaScript, як логіка пропозицій: коротке замикання та порядок операцій .

Коротке замикання - це те, що роблять двигуни JavaScript, щоб заощадити час. Щось, що не змінить результат усього виразу, не оцінюється. Функція doSomething()в наступних прикладах ніколи не викликається, оскільки, незалежно від того, що вона повернула, результат логічного виразу не зміниться:

// doSomething() is never calledfalse && doSomething();true || doSomething();

Нагадаємо, що сполучники ( &&) є істинними лише тоді, коли обидва твердження є істинними , а диз’юнкції ( ||) є хибними, лише якщо обидва твердження хибні. У кожному з цих випадків, після прочитання першого значення, більше не потрібно робити обчислень, щоб оцінити логічний результат виразів.

Через цю функцію JavaScript іноді порушує логічну комутативність. За логікою A && Bце еквівалентно B && A, але ви б порушили свою програму, якщо перейшли window && window.mightNotExistна window.mightNotExist && window. Це не означає, що правдивість заміненого виразу є якоюсь іншою, просто JavaScript може викликати помилку, намагаючись проаналізувати його.

Порядок операцій у JavaScript застав мене зненацька, бо мене не навчили, що формальна логіка мала порядок операцій, крім групування та зліва направо. Виявляється, багато мов програмування вважають &&вищим, ніж ||. Це означає, що &&спочатку групується (не оцінюється) зліва направо, а потім ||зліва направо. Це означає, що A || B && Cоцінюється не так, як (A || B) && C, а як A || (B && C).

true || false && false; // evaluates to true(true || false) && false; // evaluates to false

На щастя, групування , ()має найвищий пріоритет у JavaScript. Ми можемо уникнути сюрпризів та двозначності, об’єднавши вручну твердження, які ми хочемо оцінити, у дискретні вирази. Ось чому багато лінтерів коду забороняють мати як одну , так &&і ||одну групу.

Обчислення складних таблиць істинності

Тепер, коли правдивість простих тверджень відома, можна обчислити істинність складніших виразів.

Для початку підрахуйте кількість змінних у виразі та напишіть таблицю істинності, яка має 2ⁿ рядка.

Next, create a column for each of the variables and fill them with every possible combination of true/false values. I recommend filling the first half of the first column with T and the second half with F, then quartering the next column and so on until it looks like this:

Then write the expression down and solve it in layers, from the innermost groups outward for each combination of truth values:

As stated above, expressions which produce the same truth table can be substituted for each other.

Rules of replacements

Now I’ll cover several examples of rules of replacements that I often use. No truth tables are included below, but you can construct them yourself to prove that these rules are correct.

Double negation

Logically, A and !!A are equivalent. 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. 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. The following pairs are logically equivalent, but may change the program’s computation because of short-circuiting.

(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 Bis a necessary condition for A (recall from the truth table for implication that if B is true, A must also 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 → BandB → 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 reduced into a single statement where the conditional is a conjunction of the two previous conditions:

if (A) { if (B) { C }}// is equivalent toif (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якщо-то-інше визначення

A ? !B : B є ексклюзивним або (xor) у JavaScript

Як варіант,

1. "А або В, але не як А, так і В"

2. (A || B) && !(A && B)прямий переклад

3. (A || B) && (!A || !B)Закони ДеМоргана

4. (A && !A) || (A && !B) || (B && !A) || (B && !B)подвійний розподіл

5. (A && !B) || (B && !A)протиріччя заміни

6. A === !Bабо A !== Bматеріальна еквівалентність

A === !BабоA !== B xor в JavaScript

Встановити логіку

До цього часу ми розглядали твердження щодо виразів, що включають два (або декілька) значень, але зараз ми звернемо свою увагу на набори значень. Подібно до того, як логічні оператори у складених виразах зберігають правдивість передбачуваними способами, функції предикатів на множинах зберігають правдивість передбачуваними способами.

A predicate function is a function whose input is a value from a set and whose output is a boolean. For the following code examples, I will use an array of numbers for a set and two predicate functions:isOdd = n => n % 2 !== 0; and isEven = n => n % 2 === 0;.

Universal Statements

A universal statement is one that applies to all elements in a set, meaning its predicate function returns true for every element. If the predicate returns false for any one (or more) element, then the universal statement is false. Array.prototype.every takes a predicate function and returns true only if every element of the array returns true for the predicate. It also terminates early (with false) if the predicate returns false, not running the predicate over any more elements of the array, so in practice avoid side-effects in predicates.

Як приклад, розглянемо масив [2, 4, 6, 8]та універсальне твердження: "кожен елемент масиву парний". Використовуючи isEvenта вбудовану універсальну функцію JavaScript, ми можемо запустити [2, 4, 6, 8].every(isEven)і виявити, що це так true.

Array.prototype.every - це Універсальне твердження JavaScript

Екзистенційні висловлювання

Екзистенціальне твердження робить конкретну вимогу про набір: щонайменше , один елемент в наборі повертає істину для функції предиката. Якщо предикат повертає false для кожного елемента набору, тоді екзистенціальне твердження є false.

JavaScript також надає вбудований екзистенціальне твердження: Array.prototype.some. Подібно до every, someповернеться рано (з true), якщо елемент задовольняє своєму предикату. Як приклад, [1, 3, 5].some(isOdd)буде виконана лише одна ітерація предиката isOdd(споживання 1та повернення true) та return true. [1, 3, 5].some(isEven)повернеться false.

Array.prototype.some - це екзистенційне твердження JavaScript

Універсальне значення

Перевіривши універсальний вислів щодо набору, скажімо nums.every(isOdd), спокусливо думати, що ви можете захопити елемент із набору, який задовольняє предикату. Однак є одна фішка: у булевій логіці справжнє універсальне твердження не означає, що множина не порожня. Універсальні твердження про порожні набори завжди відповідають дійсності , тому, якщо ви хочете захопити елемент із набору, що задовольняє певній умові, використовуйте замість цього екзистенційну перевірку. Щоб довести це, запустіть [].every(() => false). Це буде правдою.

Універсальні твердження про порожні множини завжди відповідають дійсності .

Заперечення універсальних та екзистенційних тверджень

Негатування цих тверджень може викликати подив. Заперечення універсального твердження, скажімо nums.every(isOdd), не є nums.every(isEven), а навпаки nums.some(isEven). Це екзистенційне твердження з запереченим присудком. Так само заперечення екзистенціального висловлювання є універсальним висловлюванням із запереченим присудком.

!arr.every(el => fn(el)) === arr.some(el => !fn(el))

!arr.some(el => fn(el)) === arr.every(el => ! fn (el))

Встановити перехрестя

Два набори можуть бути пов’язані між собою лише кількома способами стосовно їх елементів. Ці взаємозв'язки легко діагностуються за допомогою діаграм Венна і можуть бути (в основному) визначені в коді за допомогою комбінацій універсальних та екзистенціальних тверджень.

Два набори можуть поділяти деякі, але не всі їх елементи, як типова сполучена діаграма Венна:

A.some(el => B.includes(el)) && A.some(el => !B.includes(el)) && B.some(el => !A.includes (el)) описує поєднану пару множин

Один набір може містити всі елементи іншого набору, але мати елементи, не розділені другим набором. Це відношення підмножини , що позначається як Subset ⊆ Superset.

B.every(el => A.includes(el)) описує відношення підмножини B ⊆ A

Два набори не можуть містити жодних елементів. Це несуміжні набори.

A.every(el => !B.includes(eл)) описує непересічну пару множин

Нарешті, два набори можуть спільно використовувати кожен елемент. Тобто вони є підмножинами один одного. Ці набори рівні . У формальній логіці ми б писали A ⊆ B && B ⊆ A ⟷ A === B, але в JavaScript із цим виникають певні ускладнення. У JavaScript an Arrayє упорядкованим набором і може містити повторювані значення, тому ми не можемо припустити, що двонаправлений код підмножини B.every(el => A.includes(el)) && A.every(el => B.includes (el)) передбачає, що rпромені Aта B рівні l. Якщо Aі B - це набори (тобто їх було створено with newSet ()), тоді їх значення є унікальними, і ми можемо зробити двонаправлену перевірку підмножини на s ee if A=== B.

(A === B) === (Array.from(A).every(el => Array.from(B).includes(el)) && Array.from(B).every(el => Array.from(A).includes (el)), враховуючи, що Aі Bare побудував using newSet ()

Переклад логіки на англійську мову

This section is probably the most useful in the article. Here, now that you know the logical operators, their truth tables, and rules of replacement, you can learn how to translate an English phrase into code and simplify it. In learning this translation skill, you will also be able to read code better, storing complex logic in simple phrases in your mind.

Below is a table of logical code (left) and their English equivalents (right) that was heavily borrowed from the excellent book, Essentials of Logic.

Below, I will go through some real-world examples from my own work where I interpret from English to code, and vice-versa, and simplify code with the rules of replacement.

Example 1

Recently, to satisfy the EU’s GDPR requirements, I had to create a modal that showed my company’s cookie policy and allowed the user to set their preferences. To make this as unobtrusive as possible, we had the following requirements (in order of precedence):

  1. If the user wasn’t in the EU, never show the GDPR preferences modal.
  2. 2. If the app programmatically needs to show the modal (if a user action requires more permission than currently allowed), show the modal.
  3. If the user is allowed to have the less-obtrusive GDPR banner, do not show the modal.
  4. If the user has not already set their preferences (ironically saved in a cookie), show the modal.

I started off with a series of if statements modeled directly after these requirements:

const isGdprPreferencesModalOpen = ({ shouldModalBeOpen, hasCookie, hasGdprBanner, needsPermissions}) => { if (!needsPermissions) { return false; } if (shouldModalBeOpen) { return true; } if (hasGdprBanner) { return false; } if (!hasCookie) { return true; } return false;}

To be clear, the above code works, but returning boolean literals is a code smell. So I went through the following steps:

/* change to a single return, if-else-if structure */let result;if (!needsPermissions) { result = false;} else if (shouldBeOpen) { result = true;} else if (hasBanner) { result = false;} else if (!hasCookie) { result = true} else { result = false;}return result;
/* use the definition of ternary to convert to a single return */return !needsPermissions ? false : (shouldBeOpen ? true : (hasBanner ? false : (!hasCookie ? true : false)))
/* convert from ternaries to conjunctions of disjunctions */return (!!needsPermissions || false) && (!needsPermissions || ((!shouldBeOpen || true) && (shouldBeOpen || ((!hasBanner || false) && (hasBanner || !hasCookie))))
/* simplify double-negations and conjunctions/disjunctions with boolean literals */return needsPermissions && (!needsPermissions || ((!shouldBeOpen || true) && (shouldBeOpen || (!hasBanner && (hasBanner || !hasCookie))))
/* DeMorgan's Laws */return needsPermissions && (!needsPermissions || ((!shouldBeOpen || true) && (shouldBeOpen || ((!hasBanner && hasBanner) || (hasBanner && !hasCookie))))
/* eliminate tautologies and contradictions, simplify */return needsPermissions && (!needsPermissions || (shouldBeOpen || (hasBanner && !hasCookie)))
/* DeMorgan's Laws */return (needsPermissions && !needsPermissions) || (needsPermissions && (shouldBeOpen || (hasBanner && !hasCookie)))
/* eliminate contradiction, simplify */return needsPermissions && (shouldBeOpen || (hasBanner && !hasCookie))

I ended up with something that I think is more elegant and still readable:

const isGdprPreferencesModalOpen = ({ needsPermissions, shouldBeOpen, hasBanner, hasCookie,}) => ( needsPermissions && (shouldBeOpen || (!hasBanner && !hasCookie)));

Example 2

I found the following code (written by a coworker) while updating a component. Again, I felt the urge to eliminate the boolean literal returns, so I refactored it.

const isButtonDisabled = (isRequestInFlight, state) => { if (isRequestInFlight) { return true; } if (enabledStates.includes(state)) { return false; } return true;};

Sometimes I do the following steps in my head or on scratch paper, but most often, I write each next step in the code and then delete the previous step.

// convert to if-else-if structurelet result;if (isRequestInFlight) { result = true;} else if (enabledStates.includes(state)) { result = false;} else { result = true;}return result;
// convert to ternaryreturn isRequestInFlight ? true : enabledStates.includes(state) ? false : true;
/* convert from ternary to conjunction of disjunctions */return (!isRequestInFlight || true) && (isRequestInFlight || ((!enabledStates.includes(state) || false) && (enabledStates.includes(state) || true))
/* remove tautologies and contradictions, simplify */return isRequestInFlight || !enabledStates.includes(state)

Then I end up with:

const isButtonDisabled = (isRequestInFlight, state) => ( isRequestInFlight || !enabledStates.includes(state));

In this example, I didn’t start with English phrases and I never bothered to interpret the code to English while doing the manipulations, but now, at the end, I can easily translate this: “the button is disabled if either the request is in flight or the state is not in the set of enabled states.” That makes sense. If you ever translate your work back to English and it doesn’t make sense, re-check your work. This happens to me often.

Example 3

While writing an A/B testing framework for my company, we had two master lists of Enabled and Disabled experiments and we wanted to check that every experiment (each a separate file in a folder) was recorded in one or the other list but not both. This means the enabled and disabled sets are disjointed and the set of all experiments is a subset of the conjunction of the two sets of experiments. The reason the set of all experiments must be a subset of the combination of the two lists is that there should not be a single experiment that exists outside the two lists.

const isDisjoint = !enabled.some(el => disabled.includes(el)) && !disabled.some(el => enabled.includes(el));const isSubset = allExperiments.every( el => enabled.concat(disabled).includes(el));assert(isDisjoint && isSubset);

Conclusion

Hopefully this has all been helpful. Not only are the skills of translating between English and code useful, but having the terminology to discuss different relationships (like conjunctions and implications) and the tools to evaluate them (truth tables) is handy.