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

 

2.1Булево выражение

 

Для логических схем, представляющих собой соединение нескольких логических элементов, в левой части таблицы истинности перечисляются все возможныекомбинации входных сигналов, а в правой части – соответствующие значения на выходе логической схемы. Очевидно, что левые части таблицы будут одинаковыми для всех функций двух переменных, для всех функций трёх переменных и т. д.Традиционно комбинации сигналов в нихрасполагают в порядке возрастания соответствующих двоичных кодов. На рисунке 3.7 приведен пример логической схемы и таблица истинности, полностью описывающая ее работу.

 

 

Рисунок 3.7 – Логическая схема и соответствующая ей таблица истинности

 

Вероятность ошибки уменьшается, если не решать задачу "в лоб", а проанализировать её работу с точки зрения уже известных нам правил логического сложения, умножения и инверсии. Очевидно, что в рассматриваемой схеме осуществляется логическое сложение нескольких логических произведений. Можно записать логическое выражение, соответствующее данной схеме:

 

.                             (3.1)

Булево выражение в виде суммы произведений называется дизъюнктивно нормальной формой (ДНФ).

Булево выражение в виде произведения сумм называется конъюнктивной нормальной формой (КНФ).

По правилу логического сложения выражение (3.1) имеет на выходе логическую 1 (f =1) только в том случае, если равно 1 хотя бы одно из четырех произведений, входящих в сумму.

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

* Произведение  будет равно 1 только тогда, когда будет выполняться условие: и , и . При этом от значений остальных входных переменных –  и  – значение данного произведения не зависит. Поэтому логические 1 будут в строках, соответствующих полным произведениям , в которых , а переменные  и  перечисляются во всех четырех возможных комбинациях: = 0101, 0111, 1101 и 1111.

* Произведение  будет равно 1 только тогда, когда будет выполняться условие: и  (т. е. ), и , и . От значения не вошедшей в данное произведение переменной  произведение  не зависит. Поэтому логические 1 будут в строках таблицы истинности, соответствующих полным произведениям , в которых  и одновременно , а переменная  перечисляется во всех двух возможных комбинациях: = 0011 и 0111.

* Произведение  будет равно 1 только тогда, когда будет выполняться условие: и  (т. е. ), и , и . От значения не вошедшей в данное произведение переменной  произведение  не зависит. Поэтому логические 1 будут в строках таблицы истинности, соответствующих полным произведениям , в которых  и одновременно , а переменная  перечисляется во всех двух возможных комбинациях: = 0101 и 0111.

* Произведение  будет равно 1 только тогда, когда будет выполняться условие: и  (т. е. ),  (т. е. ), и  и . Поэтому логическая 1, соответствующая данному полному произведению всех переменных, будет только в той строке таблицы истинности, где = 0011.

Анализ всех этих возможностей показывает, что они могут совпадать для нескольких произведений. Например, комбинация входных переменных 0011 встречается в произведениях  и . А сочетание 0111 встречается даже в трех произведениях: и в , и в , и в . Это говорит о том, что для данного логического выражения есть возможности минимизации.

 

2.2 Основные законы и правила алгебры логики

 

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

Законы коммутативности (переместительные) для дизъюнкции и конъюнкции

.

    Законы ассоциативности (сочетательные) для дизъюнкции и конъюнкции

.

    Первый и второй законы дистрибутивности (распределительные)

.

    Законы идемпотентности (повторения) для дизъюнкции и конъюнкции

.

    Законы отрицания (инверсии)

.

    Законы двойственности  или «правило де Моргана»

.

    Правило свертки

.

    Правила поглощения

.

    Правила полного склеивания

.

    Правило неполного склеивания

.

    Правило Порецкого

.

    Правила операций с константами

                             

    Доказательство большинства законов и правил алгебры логики очевидны.

    Например,