Реферат: Функционально полные системы логических функций Алгебраический подход

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

(6)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например,

.

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

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

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

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

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

Например:

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

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