Закон исключения третьего (дополнительности)

Закон противоречия (дополнительности)

Правила (законы) де Моргана

Свойства констант

x & 1 = x; (законы универсального множества)

x Ú 1 = 1;

x & 0 = 0; (законы нулевого множества)

x Ú 0 = x;

`0 = 1;

`1 = 0;

`x x = 0;

`x Ú x = 1;

Доказательства всех этих формул тривиальны. Один из вариантов –построение таблиц истинности левой и правой частей и их сравнение.

Конъюнкция любого числа переменных из конечного набора n переменных называется элементарной, когда в нее входят либо переменные, либо их отрицания. Например, x₃`x<sub>2</sub>`x₁ x₀ является элементарной,

- - ₌₌¾----

а (` x <sub>3</sub> v x <sub>2</sub>)` x ₀, x ₃ x ₂ x ₁ x ₀ не являются элементарными.

Дизъюнкция любого числа переменных из конечного набора n переменных называется элементарной, когда в нее входят либо переменные, либо их отрицания. Например, сумма `x<sub>3</sub> v x<sub>2</sub> v x<sub>1</sub> v`x₀ является элементарной, а `x <sub>1</sub> x<sub>2</sub>+x<sub>0</sub>; `x ₃ + x ₂ x₁ + x ₀ нет.

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

Элементарная дизъюнкция всех n переменных называется конституентой нуля.

Элементарная конъюнкция всех n переменных называется конституентой единицы.

Две элементарные дизъюнкции (конъюнкции) одинакового ранга r называются соседними, если они являются функциями одних и тех же переменных и отличаются только знаком инверсии лишь у одной переменной. Например, суммы `x<sub>2</sub> v x<sub>1</sub> v`x₀ и x₂ v x₁ v`x<sub>0</sub> являются соседними, а `x₂ v x₁ v`x<sub>0</sub> и `x₂ v`x₁ v x₀ нет.

Сформулируем теперь важнейшие следствия из основных законов булевой алгебры, представив их в виде правил.

Правила склеивания

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

Пример: y = x₂`x<sub>1</sub>`x₀ v x₂`x<sub>1</sub>x<sub>0</sub> = x<sub>2</sub>`x₁ (`x<sub>0</sub> v x<sub>0</sub>) = x<sub>2</sub>`x₁·1 = x₂`x₁.

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

Пример: y = (`x<sub>2</sub> v x<sub>1</sub> v `x₀)(x₂ v x₁ v `x<sub>0</sub>) = (x<sub>1</sub> v `x₀) v `x<sub>2</sub>x<sub>2</sub> = (x<sub>1</sub> v `x₀) v 0 = x₁ v `x₀.

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

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

Пример: y = x₃`x<sub>1</sub> v x<sub>3</sub>`x₂`x<sub>1</sub> x <sub>0</sub> = x<sub>3</sub>`x₁ (1 v `x<sub>2</sub>x<sub>0</sub>) = x<sub>3</sub>`x₁·1 = x₃`x₁.

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

Пример: y = (`x<sub>3</sub> v `x₁)(x₃ v `x<sub>2</sub> v `x₁ v x₀) =(`x<sub>3</sub> v `x₁ v 0)(`x<sub>3</sub> v `x₂ v `x<sub>1</sub> v x<sub>0</sub>) = (`x₃ v `x<sub>1</sub>) v 0(`x₂ v x₀) = (`x<sub>3</sub> v `x₁) v 0 = `x<sub>3</sub> v `x₁.

Правило развертывания

Это правило определяет действие обратное склеиванию.

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

- в развертываемое элементарное произведение ранга r вводится в качестве сомножителей n-r единиц, где n- ранг конституенты единицы;

- каждая единица заменяется логической суммой некоторой, не имеющейся в исходном элементарном произведении переменной и ее отрицания: x_i v `x_i = 1;

- производится раскрытие всех скобок на основе распределительного закона первого рода, что приводит к развертыванию исходного элементарного произведения ранга r в логическую сумму 2^n-r конституент единицы.

Пример: развернуть элементарное произведение x₃`x₁ в логическую сумму конституент единицы, зависящих от 4-х переменных. Последнее следует из того, что максимальный индекс у переменной равен 3; отсутствуют переменные x₂ и x₀.

Решение: x₃`x<sub>1</sub> = x<sub>3</sub><sup>.</sup>1<sup>.</sup>`x₁^.1 = x₃(x₂ v `x<sub>2</sub>)`x₁(x₀ v `x<sub>0</sub>) = (x<sub>3</sub> x<sub>2</sub>`x₁ v x₃`x<sub>2</sub>`x₁) (x₀ v `x<sub>0</sub>) = x<sub>3</sub> x<sub>2</sub>`x₁ x₀ v x₃ `x<sub>2</sub>`x₁ x₀ v x₃ x₂`x<sub>1</sub>`x₀ v x₃`x<sub>2</sub>`x₁`x₀.

Пусть n = 3. Из преобразования (развертывания) 1 = 1·1·1 = (x ₂ v ` x <sub>2</sub>) (x <sub>1</sub> v ` x ₁) (x ₀ v ` x <sub>0</sub>) = ` x ₂` x <sub>1</sub>` x ₀ v ` x <sub>2</sub>` x ₁ x ₀ v ` x <sub>2</sub> x <sub>1</sub>` x ₀ v ` x <sub>2</sub> x <sub>1</sub> x <sub>0</sub> v x <sub>2</sub> ` x ₁` x <sub>0</sub> v x <sub>2</sub> ` x ₁ x ₀ v x ₂ x ₁` x ₀ v x ₂ x ₁ x ₀ следует смысл термина "конституента (составляющая) единицы".

Правило развертывания элементарного произведения используется для минимизации функций алгебры логики (ФАЛ).

Пример: пусть y = x ₂` x <sub>1</sub>+ x <sub>1</sub> x <sub>0</sub> + x <sub>2</sub> x <sub>0</sub>. Видно, что все элементарные произведения имеют ранг r = 2, следовательно правило поглощения нельзя применить; кроме того ни одна пара произведений не является соседней, так как произведения имеют различные переменные. Если же развернуть произведение x<sub>2</sub>x<sub>0</sub> до конституент единицы (в данном случае n = 3), то выражение упростится: y = x <sub>2</sub> ` x ₁ v x ₁ x ₀ v x ₂^. 1 ^. x ₀ = x ₂` x <sub>1</sub> v x <sub>1</sub> x <sub>0</sub> v x <sub>2</sub> (x <sub>1</sub> v ` x ₁) x ₀ = x ₂` x <sub>1</sub> v x <sub>1</sub> x <sub>0</sub> v x <sub>2</sub> x <sub>1</sub> x <sub>0</sub> v x <sub>2</sub>` x ₁ x ₀ = x ₂` x <sub>1</sub> (1 v x <sub>0</sub>) v x <sub>1</sub> x <sub>0</sub> (1 v x <sub>2</sub>) = x <sub>2</sub>` x ₁^.1 v x ₁ x ₀^.1 = x ₂` x ₁ v x ₁ x ₀, т.е. произведение x₂x₀ оказалось лишним. Общие формальные правила определения лишних произведений будут рассмотрены в последующих статьях.

Правило развертывания элементарной суммы ранга r до произведения элементарных сумм ранга n (конституент нуля) следует их законов нулевого множества (6) и распределительного закона второго рода (14) и производится в три этапа:

- в развертываемую сумму ранга r в качестве слагаемых вводится n-r нулей;

- каждый нуль представляется в виде логического произведения некоторой, не имеющейся в исходной сумме переменной и ее отрицания: x _i ·`x _i = 0;

-получившееся выражение преобразуется на основе распределительного закона второго рода (14) таким образом, чтобы исходная сумма ранга r развернулась в логическое произведение 2^n-r конституент нуля.

Пример: развернуть элементарную сумму x₃+x₂ в логическое произведение конституент нуля, зависящих от 4-х переменных. Последнее следует из того, что максимальный индекс равен 3; отсутствуют переменные x₁ и x₀.

Решение: x₃ v`x<sub>2</sub> = x<sub>3</sub> v`x₂ v 0 v 0 = x₃ v`x<sub>2</sub> v x<sub>1</sub>`x₁ v x₀`x<sub>0</sub> = (x<sub>3</sub>v`x₂vx₁)·(x₃v`x<sub>2</sub>vx<sub>1</sub>) v x<sub>0</sub>`x₀ = (x₃ v`x<sub>2</sub> v x<sub>1</sub> v x<sub>0</sub>)·(x<sub>3</sub> v`x₂ v x₁ v`x<sub>0</sub>)·(x<sub>3</sub> v`x₂ v`x<sub>1</sub> v x<sub>0</sub>)·(x<sub>3</sub> v`x₂ v`x<sub>1</sub> v`x₀).

Пусть n = 2. Из преобразования (развертывания) 0 = 0 v 0 = x₁`x<sub>1</sub> v x<sub>0</sub> `x₀ = (x₁`x<sub>1</sub>v x<sub>0</sub>)(x<sub>1</sub>`x₁v`x<sub>0</sub>) = (x<sub>1</sub> v x<sub>0</sub>)(`x₁ v x₀)(x₁ v`x<sub>0</sub>)(`x₁ v`x₀) следует смысл термина "конституента (составляющая) нуля".

Пример: пусть y = (x₂ v`x<sub>1</sub>) (x<sub>1</sub> v x<sub>0</sub>) (x<sub>2</sub> v x<sub>0</sub>). Ясно, что операции склеивания и поглощения здесь применить нельзя. Однако, если развернуть сумму x<sub>2</sub> v x<sub>0</sub> до конституент нуля (в данном случае n = 3), то выражение упростится: y = (x<sub>2</sub>v <sub>1</sub>) (x<sub>1</sub> v x<sub>0</sub>) (x<sub>2</sub> v 0 v x<sub>0</sub>) = (x<sub>2</sub> v`x₁) (x₁ v x₀) (x₂ v x₁`x<sub>1</sub> v x<sub>0</sub>) = (x<sub>2</sub> v`x₁ v 0)(x₁ v x₀ v 0)(x₂ v x₁ v x₀) (x₂ v`x<sub>1</sub> v x<sub>0</sub>) = (x<sub>2</sub> v`x₁ v 0·x₀) (x₁ v x₀ v 0·x₂) = (x₂ v`x₁) (x₁v x₀), т.е. сумма x₂ v x₀ оказалась лишней.

Дата добавления: 2014-01-03