Закон исключения третьего (дополнительности)
Закон противоречия (дополнительности)
Правила (законы) де Моргана
Свойства констант
x & 1 = x; (законы универсального множества)
x Ú 1 = 1;
x & 0 = 0; (законы нулевого множества)
x Ú 0 = x;
`0 = 1;
`1 = 0;
`x x = 0;
`x Ú x = 1;
Доказательства всех этих формул тривиальны. Один из вариантов –построение таблиц истинности левой и правой частей и их сравнение.
Конъюнкция любого числа переменных из конечного набора n переменных называется элементарной, когда в нее входят либо переменные, либо их отрицания. Например, x3`x2`x1 x0 является элементарной,
- - ==¾----
а (`x3 v x2)`x0, x3 x2 x1 x0 не являются элементарными.
Дизъюнкция любого числа переменных из конечного набора n переменных называется элементарной, когда в нее входят либо переменные, либо их отрицания. Например, сумма `x3 v x2 v x1 v`x0 является элементарной, а `x 1 x2+x0; `x 3 + x 2 x1 +x0 нет.
Рангом дизъюнкции (конъюнкции) называется количество ее операндов.
Элементарная дизъюнкция всех n переменных называется конституентой нуля.
Элементарная конъюнкция всех n переменных называется конституентой единицы.
Две элементарные дизъюнкции (конъюнкции) одинакового ранга r называются соседними, если они являются функциями одних и тех же переменных и отличаются только знаком инверсии лишь у одной переменной. Например, суммы `x2 v x1 v`x0 и x2 v x1 v`x0 являются соседними, а `x2 v x1 v`x0 и `x2 v`x1 v x0 нет.
Сформулируем теперь важнейшие следствия из основных законов булевой алгебры, представив их в виде правил.
Правила склеивания
Правило склеивания для элементарных конъюнкций следует из распределительного закона, закона дополнительности и закона универсального множества: дизъюнкцию двух соседних конъюнкций можно заменитьодной элементарной конъюнкцией, являющейся общей частьюисходных конъюнкций.
Пример: y = x2`x1`x0 v x2`x1x0 = x2`x1 (`x0 v x0) = x2`x1·1 = x2`x1.
Правило склеивания для элементарных сумм следует из распределительного закона второго рода, закона дополнительности и закона нулевого множества: конъюнкцию двух соседних дизъюнкций можно заменить одной элементарной дизъюнкцией, являющейся общей частьюисходных дизъюнкций.
Пример: y = (`x2 v x1 v `x0)(x2 v x1 v `x0) = (x1 v `x0) v `x2x2 = (x1 v `x0) v 0 = x1 v `x0.
Правило поглощения
Правило поглощения для суммы двух элементарных произведений следует из распределительного закона первого рода и законов универсального множества: дизъюнкцию двух элементарных конъюнкций, из которых одна является составной частью другой, можно заменить конъюнкцией, имеющейменьшее количество операндов.
Пример: y = x3`x1 v x3`x2`x1 x0 = x3`x1 (1 v `x2x0) = x3`x1·1 = x3`x1.
Правило поглощения для произведения элементарных сумм следует из распределительного закона второго рода и законов нулевого множества: конъюнкцию двух элементарных дизъюнкций, из которых одна является составной частью другой, можно заменить элементарной дизъюнкцией, имеющей меньшее количество операндов.
Пример: y = (`x3 v `x1)( x3 v `x2 v `x1 v x0) =(`x3 v `x1 v 0)(`x3 v `x2 v `x1 v x0) = (`x3 v `x1) v 0(`x2 v x0) = (`x3 v `x1) v 0 = `x3 v `x1.
Правило развертывания
Это правило определяет действие обратное склеиванию.
Правило развертывания элементарного произведения в логическую сумму элементарных произведений большего ранга (в пределе до r = n, т.е. до конституент единицы, как и будет рассмотрено ниже) следует из законов универсального множества, распределительного закона первого рода и производится в три этапа:
- в развертываемое элементарное произведение ранга r вводится в качестве сомножителей n-r единиц, где n- ранг конституенты единицы;
- каждая единица заменяется логической суммой некоторой, не имеющейся в исходном элементарном произведении переменной и ее отрицания: xi v `xi = 1;
- производится раскрытие всех скобок на основе распределительного закона первого рода, что приводит к развертыванию исходного элементарного произведения ранга r в логическую сумму 2n-r конституент единицы.
Пример: развернуть элементарное произведение x3`x1 в логическую сумму конституент единицы, зависящих от 4-х переменных. Последнее следует из того, что максимальный индекс у переменной равен 3; отсутствуют переменные x2 и x0.
Решение: x3`x1 = x3.1.`x1.1 = x3(x2 v `x2)`x1(x0 v `x0) = (x3 x2`x1 v x3`x2`x1) (x0 v `x0) = x3 x2`x1 x0 v x3 `x2`x1 x0 v x3 x2`x1`x0 v x3`x2`x1`x0.
Пусть n = 3. Из преобразования (развертывания) 1 = 1·1·1 = (x2 v `x2) (x1 v `x1) (x0 v `x0) = `x2`x1`x0 v `x2`x1x0 v `x2x1`x0 v `x2x1x0 v x2 `x1`x0 v x2 `x1x0 v x2x1`x0 v x2x1x0 следует смысл термина "конституента (составляющая) единицы".
Правило развертывания элементарного произведения используется для минимизации функций алгебры логики (ФАЛ).
Пример: пусть y = x2`x1+x1 x0 + x2 x0. Видно, что все элементарные произведения имеют ранг r = 2, следовательно правило поглощения нельзя применить; кроме того ни одна пара произведений не является соседней, так как произведения имеют различные переменные. Если же развернуть произведение x2x0 до конституент единицы (в данном случае n = 3), то выражение упростится: y = x2 `x1 v x1 x0 v x2. 1 .x0 = x2`x1 v x1x0 v x2 (x1 v `x1) x0 = x2`x1 v x1x0 v x2x1x0 v x2`x1x0 = x2`x1 (1 v x0) v x1x0 (1 v x2) = x2`x1.1 v x1x0.1 = x2`x1 v x1x0, т.е. произведение x2x0 оказалось лишним. Общие формальные правила определения лишних произведений будут рассмотрены в последующих статьях.
Правило развертывания элементарной суммы ранга r до произведения элементарных сумм ранга n (конституент нуля) следует их законов нулевого множества (6) и распределительного закона второго рода (14) и производится в три этапа:
- в развертываемую сумму ранга r в качестве слагаемых вводится n-r нулей;
- каждый нуль представляется в виде логического произведения некоторой, не имеющейся в исходной сумме переменной и ее отрицания: xi·`xi = 0;
-получившееся выражение преобразуется на основе распределительного закона второго рода (14) таким образом, чтобы исходная сумма ранга r развернулась в логическое произведение 2n-r конституент нуля.
Пример: развернуть элементарную сумму x3+x2 в логическое произведение конституент нуля, зависящих от 4-х переменных. Последнее следует из того, что максимальный индекс равен 3; отсутствуют переменные x1 и x0.
Решение: x3 v`x2 = x3 v`x2 v 0 v 0 = x3 v`x2 v x1`x1 v x0`x0 = (x3v`x2vx1)·(x3v`x2vx1) v x0`x0 = (x3 v`x2 v x1 v x0)·(x3 v`x2 v x1 v`x0)·(x3 v`x2 v`x1 v x0)·(x3 v`x2 v`x1 v`x0).
Пусть n = 2. Из преобразования (развертывания) 0 = 0 v 0 = x1`x1 v x0 `x0 = (x1`x1v x0)(x1`x1v`x0) = (x1 v x0)(`x1 v x0)(x1 v`x0)(`x1 v`x0) следует смысл термина "конституента (составляющая) нуля".
Пример: пусть y = (x2 v`x1) (x1 v x0) (x2 v x0). Ясно, что операции склеивания и поглощения здесь применить нельзя. Однако, если развернуть сумму x2 v x0 до конституент нуля (в данном случае n = 3), то выражение упростится: y = (x2v
1) (x1 v x0) (x2 v 0 v x0) = (x2 v`x1) (x1 v x0) (x2 v x1`x1 v x0) = (x2 v`x1 v 0)(x1 v x0 v 0)(x2 v x1 v x0) (x2 v`x1 v x0) = (x2 v`x1 v 0·x0) (x1 v x0 v 0·x2) = (x2 v`x1) (x1v x0), т.е. сумма x2 v x0 оказалась лишней.