Приоритеты операций. 
Булева алгебра

Приоритеты основных логических операций соответствуют приоритетам аналогичных операций в элементарной алгебре. Приоритет исключающего ИЛИ совпадает с приоритетом дизъюнкции. Импликация и эквивалентность обладают равными низшими приоритетами.

Основные законы Булевой алгебры

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

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

Ассоциативность. Ассоциативность конъюнкции и дизъюнкции выражается следующими формулами:

(А?В) ?С=А? (В?С)=А?В?С (А?В) ?С=А? (В?С)=А?В?С На практике это означает, что можно опускать те скобки, которые определяют, в каком порядке должна выполняться конъюнкция в выражениях вида А₁? А₂ ??? А_n и дизъюнкция в выражениях А₁?А₂???А_n

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

Конъюнкция и дизъюнкция являются коммутативными операциями:

А?В=В?А А? В=В?А Дистрибутивность Свойство дистрибутивности одной операции относительно другой позволяет «раскрывать» скобки аналогично процедуре из элементарной алгебры. Конъюнкция и дизъюнкция дистрибутивны друг относительно друга, что выражается в следующих формулах:

А?(В?С)=А?В?А?С A? B?C=(А?В)?(А?С).

Свойства единицы и нуля Конъюнкция и дизъюнкция «по-особому» реагируют на единицу или ноль в качестве одного из операндов независимо от значения второго. Эти свойства похожи на знакомые из элементарной алгебры умножение на единицу, умножение на ноль, сложение с нулем:

А?0=0 А?1=1 А?0=А А?1=1.

Идемпотентность Операция называется идемнотентной, если, применяя ее к двум равным операндам, получается тот же самый операнд. Идемпотентность позволяет «выкидывать» лишние повторные применения операции из формулы. Конъюнкция и дизъюнкция идемпотентны:

А?А=А А? А=А Поглощение Если к выражению применяется с одним и тем же операндом сначала одна операция, а потом, с тем же самым операндом, поглощающая ее, то значение выражения поглощается, становясь равно операнду. Таким образом поглощающие друг друга пары операций можно «выкидывать» во время упрощения. Конъюнкция и дизъюнкция поглощают друг друга:

А?В?В=В (А?В) ?В=В Законы де Моргана Законы де Моргана позволяют применять отрицания к целой скобке, позволяя перейти к так называемым тесным отрицаниям, когда ни одно отрицание не стоит перед скобкой.

(А?В)=А?В (А?В)=А?В Дополнение Отрицание операнда называется его дополнением. Конъюнкция или дизъюнкция операнда со своим дополнением дает однозначные результат независимо от значения операнда:

А?А=0 А? А=1.

Двойное отрицание Двойное отрицание компенсирует само себя. Таким образом в форме с тесными отрицаниями у каждой переменной в выражении либо не стоит ни одного отрицания, либо только одно. А=А Советы по упрощению логических выражений.

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

I. Логические элементы компьютера Во всех современных компьютерах применяется логическая система, изобретенная Джорджем Булем. Тысячи микроскопических электронных переключателей в кристалле интегральной схемы сгруппированы в системы «вентилей», выполняющих логические операции, т. е. операции с предсказуемыми результатами. На приведенных ниже рисунках показаны элементарные логические вентили НЕ, ИЛИ-НЕ и И-НЕ. Все остальные логические схемы компьютера могут быть построены на основе вентилей этих трех типов.