Тема 22. Законы алгебры логики в ОФПС и их следствия. Правило выполнения совместных логических действий, правило склеивания, правило поглощения, правило развертывания.

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

переместительный (коммутативный);

сочетательный (ассоциативный);

распределительный (дистрибутивный);

инверсии (правило Де Моргана).

Переместительный закон. Этот закон справедлив как для дизъюнкции, так и для конъюнкции:

x₁ x₂ = x₂ x₁; x₁ x₂ = x₂ x₁. (1)

Справедливость выражения (1) нетрудно доказать простой подстановкой в него различных значений x₁ и x₂. Поскольку любую перестановку большего количества слагаемых можно свести к последовательности перестановок слагаемых в отдельных парах, то переместительный закон будет справедлив при любом числе слагаемых.

Сочетательный закон. Этот закон, так же как и переместительный, является симметричным, т. е. справедливым и для дизъюнкции, и для конъюнкции:

x₁ x₂ x₃ = x₁(x₂ x₃) = (x₁ x₂)x₃= x₂( x₁ x₃); (2)

x₁ x₂ x₃ = x₁x₂ x₃) = (x₁ x₂)x₃= x₂( x₁ x₃).

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

Распределительный закон. В отличие от обычной алгебры алгебра логики симметрична. В ней справедливы два распределительных закона:

для логического умножения относительно логического сложения (распределительный закон 1-го рода) и для логического сложения относительно логического умножения (распределительный закон 2-го рода).

1. Распределительный закон 1-го рода записывается следующим образом:

(x₁x₂)x₃=(x₁x₃) ( x₂ x₃) . (3)

Справедливость формулы (3), а также и ее более общего случая, когда в скобках заключена сумма любого количества слагаемых, можно доказать путем установления идентичности условий обращения в 0 или 1 ее левой и правой частей. Условием обращения в нуль левой части выражения (3) состоит в том, чтобы нулю равнялся либо один аргумент х₃, либо одновременно аргументы x₁ и x₂. Условия обращения в нуль правой части выражения (1) такие же. Следовательно, распределительный закон 1-го рода справедлив для алгебры логики.

2. Распределительный закон 2-го рода имеет вид

(x₁x₂)x₃=(x₁x₃) ( x₂x₃). (4)

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

Закон инверсии (правило Де Моргана). Этот закон, так же как и все предыдущие, симметричен относительно логических сложения и умножения.

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

(5)

Доказательство закона не представляет трудностей, поскольку условие обращения в нуль как левой, так и правой частей выражения (5) состоит в том, чтобы был истинным хотя бы один аргумент.

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

(6)

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

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

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

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

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

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

Правило склеивания. Если имеется некоторый конечный набор логических аргументов x₁, x₂, … x_n, то логическое произведение любого их числа называется элементарным в том случае, когда сомножителями в нем являются либо одиночные аргументы, либо отрицания одиночных аргументов. Так, например, f₁(х₁, х₂, x₃, х₄)= х₁ х₂ x₃х₄ -элементарное произведение (элементарная конъюнкция); --не является элементарным произведением.

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

Два элементарных произведения одинакового ранга r называются соседними, если они являются функциями одних и тех же аргументов и отличаются только знаком отрицания (инверсии) одного из сомножителей. Например, элементарные конъюнкции

f₁(х₁, х₂, x₃, х₄)= х₁× х₂× x₃×х₄ и f₃(х₁, х₂, x₃, х₄)=

являются соседними, так как отличаются только одной инверсией в переменной x₂, а элементарные конъюнкции

f₃(х₁, х₂, x₃, х₄)= и f₄(х₁, х₂, x₃, х₄)=

соседними не являются.

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

Это правило является следствием распределительного закона 1-го рода и доказывается путем вынесения за скобку общей части слагаемых, являющихся соседними конъюнкциями. Тогда в скобках остается логическая сумма некоторого аргумента и его инверсии, равная единице, что и доказывает справедливость правила.

Например,

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

Если имеется некоторый конечный набор логических аргументов, то логическая сумма (дизъюнкция), зависящая от любого их числа, называется элементарной в том случае, когда слагаемыми в ней являются либо одиночные аргументы, либо отрицания одиночных аргументов.

Количество слагаемых в элементарной дизъюнкции называется ее рангом. Две элементарные суммы одинакового ранга называются соседними, если они являются функциями одних и тех же аргументов и отличаются только знаком отрицания (инверсии) одного из слагаемых.

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

Это правило является следствием распределительного закона 2-го рода и применяется для упрощения логических выражений.

Например:

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

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

Например,

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

Это правило является следствием распределительного закона 2-го рода и также находит широкое применение для упрощения логических функций.

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

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

· каждая единица представляется в виде логической суммы некоторой, не имеющейся в исходной конъюнкции переменной и ее отрицания: ;

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

Пример. Развернуть элементарную конъюнкцию f(x₁,x₂,x₃,x₄) = =x₁x₃ в логическую сумму конституент единицы.

Решение. Ранг конституенты единицы для данной функции равен 4. Производим развертывание исходной конъюнкции поэтапно в соответствии с правилом развертывания:

1-й этап-- f(x₁,x₂,x₃,x₄) = x₁1x₃1.

2-й этап -- f(x₁,x₂,x₃,x₄) =

3-й этап -- f(x₁,x₂,x₃,x₄)=

= что и требовалось получить.

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

· в развертываемую элементарную дизъюнкцию ранга r в качестве дополнительных слагаемых вводится п-r нулей;

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

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

Пример. Развернуть элементарную дизъюнкцию f(x₁,x₂,x₃,x₄)= =x₃x₄ влогическое произведение конституент нуля.

Решение. Ранг конституенты нуля п = 4. Далее производим развертывание исходной дизъюнкции поэтапно в соответствии с правилом развертывания:

1-й этап -- f(x₁,x₂,x₃,x₄) =00x₃x₄;

2-й этап -- f(x₁,x₂,x₃,x₄) =

3-йэтап--f(x₁,x₂,x₃,x₄)=

что и требовалось получить.

Проверить правильность проведенных преобразований можно при помощи правила склеивания.