Упростите логические условия, используя законы де Моргана, без всех этих странных символов булевой алгебры

Если вы хоть немного занимаетесь программированием, то, несомненно, в той или иной форме использовали логическое условие. Логические выражения приводят к значению (булеву) true или false и регулярно используются для разветвления потока управления в программе.

В логическом выражении используется комбинация следующих основных операторов:

• NOT, преобразует true в false и false в true, и иногда известен как «инвертор».
• AND, принимает два значения и возвращает true только тогда, когда оба значения истинны, в противном случае возвращает false.
• OR, также принимает два значения, но возвращает false только тогда, когда оба входа ложны, в противном случае возвращает true.

Обратите внимание, что это «фундаментальные» операции (иногда называемые логическими воротами), так как существуют и другие, такие как XOR, NAND, NOR и т.д. Но они являются комбинацией первых трех и выходят за рамки данной статьи. Добавьте комментарий, если хотите узнать больше.

Удобным способом визуализации булевых операторов является отображение входов на выходы с помощью таблицы истинности; самым простым является NOT, поскольку он имеет только один вход и выход.

Когда у нас есть более одного входа, полезнее сформировать столбцы и строки из входов и выразить выходы в ячейке, где они пересекаются.

Завершить тройку:

Логические выражения могут быстро усложняться, когда вы объединяете более пары терминов, поэтому полезно знать пару приемов для упрощения логики. Здесь мы должны поблагодарить математика 19 века Августа де Моргана.

Закон де Моргана

В основных терминах г-н де Морган заметил, что существует комбинация булевых операторов, которые эквивалентны, и это можно использовать для преобразования одного выражения в другое без изменения результата/вывода.

Рассмотрим выражение:

NOT(A) AND NOT(B)

Вот таблица истинности:

Это должно выглядеть аналогично таблице истинности ИЛИ, приведенной выше, за исключением того, что все значения инвертированы. Это означает, что, как заметил г-н де Морган, следующие выражения эквивалентны.

NOT(A) AND NOT(B)   is the same as       NOT(A OR B)

Возможно, NOT(A OR B) проще с точки зрения количества используемых логических операторов и легче для понимания.

Пример из практики

Вы можете сказать, что большинство моих условий не содержат булевых значений. Это такие выражения, как:

• hourlyPay > 1000
• !stringValue.length
• object != null.

Однако результатом всех трех вышеперечисленных условий является булево значение true или false. Итак, рассмотрим следующий оператор if.

if (not(A) and (B or not(C)) then
    /* Do nothing */
else 
    /* Do something */

Подобные случаи возникают чаще, чем вы думаете, когда очевидное логическое выражение прямо противоположно тому, что вам на самом деле нужно, но его отмена выглядит слишком сложной. Одним из вариантов может быть «не много».

if (not(not(A) and (B or not(C))) then  /* Do something */

Но это делает выражение еще более сложным для понимания, но тут на помощь приходит закон де Моргана. Прежде чем применить этот закон, давайте начнем с таблицы истинности с тремя входами: A, B и C.

Из таблицы истинности видно, что результат должен быть истинным, если A истинно или если B ложно, а C истинно. Это означает, что мы можем переписать выражение как:

if (A or (not(B) and C)) then   /* Do something */

Вычислить таблицу истинности с тремя терминами не так-то просто, и, честно говоря, я воспользовался электронной таблицей, чтобы сделать это за меня, используя следующую формулу для выходного столбца O1.

O1  =not(and(not(A2),or(B2,not(C2))))

Использование закона де Моргана

1. Начиная с выражения not(not(A) и (B или not(C)), применим закон, чтобы удалить внешнюю операцию not без изменения результата.a. Удалите внешнее not => (not(A) и (B или not(C))b. Инвертируйте левый и правый термины => (A и not(B или not(C))c. Поменяйте местами операции между двумя терминами, чтобы получить: (A или not(B или not(C)).
2. Далее применим закон к внутреннему выражению not, используя те же три шага, что и выше, чтобы получить: (A или (not(B) и C)).

Мы можем проверить результат с помощью функции электронной таблицы:

O2  =or(A2,and(not(B2),C2))

Вывод

Точно так же, как вы можете изменить (a*b + b*c) на (a+c)*b, или наоборот, чтобы сделать его более читабельным, закон де Моргана предоставляет полезный способ упрощения логических выражений. Надеюсь, эта статья продемонстрировала его полезность и то, как применять этот закон.

Лично я нахожу составление таблиц истинности трудоемким и чреватым ошибками, особенно когда в таблице больше трех терминов; даже если у вас под рукой есть электронная таблица. Нахождение возможностей для применения закона де Моргана становится второй натурой, и, я надеюсь, вы согласитесь, что применение этих шагов является тривиальным.

Бонусный материал

Ленивая оценка

Многие языки программирования поддерживают возможность «ленивой» оценки условных выражений. Рассмотрим следующее:

A and B

Благодаря операции And, если A ложно, то не имеет значения значение B, результат всегда будет ложным. Если A истинно, результатом будет значение B. И наоборот, в выражении Or,

A or B

Если A истинно, то не имеет значения значение B, результат всегда будет истинным. Если A ложно, то результатом будет любое значение B.

Избегайте возврата булевых значений, полученных в результате выполнения условия

Просматривая код, я иногда вижу, что булевы значения возвращаются из условного оператора следующим образом.

if (A === B) {
    return true;
}
else {
    return false;
}

В более современной форме я также вижу следующее, что лишь немного лучше.

return (A === B) ? true : false;

Даже когда логика обратная, использование условного выражения излишне, и следующее выражение эквивалентно обоим приведенным выше примерам.

return (A === B);