Функционально полные системы логических функций Алгебраический подход (стр. 2 из 2)

Например,

.

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

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

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

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

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

Например:

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

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

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

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

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

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

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

;

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

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

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

1-й этап— f(x₁,x₂,x₃,x₄) = x₁×1×x₃×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₄) =0Ú0Úx₃Úx₄;

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

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

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

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

3. Функционально полные системы логических функций. Анализ принадлежности переключательных функций замкнутым классам показывает, что существуют две переключательные функции f₈ и f₁₄, не принадлежащие ни одному классу. Согласно теореме о функциональной полноте, каждая из этих функций образует функционально полную систему логических связей и используя только одну из них можно представить любую, сколь угодно сложную переключательную функцию.

Операция Пирса (стрелка Пирса) реализует функцию, которая принимает значение, равное единице только в том случае, когда все ее аргументы равны 0 (ИЛИ-НЕ), что может быть записано в ОФПС для функции двух переменных следующим образом:

(7)

Используя операции суперпозиции и подстановки можно показать, что операция Пирса может быть реализована для n аргументов:

(8)

Для представления переключательной функции в базисе Пирса необходимо выполнить следующие действия:

· представить переключательную функцию f в конъюнктивной нормальной форме;

· полученное выражение представить в виде

(поставить два знака отрицания);

· применить правило Де Моргана.

Например, для того чтобы представить функцию

в базисе Пирса, необходимо выполнить следующие преобразования:

Для представления полученного выражения в базисе Пирса воспользуемся соотношением (7):

.

Операция Шеффера (штрих Шеффера) реализует функцию, которая принимает значение, равное нулю, только в том случае, когда все ее аргументы равны 1 (И-НЕ), что может быть записано в ОФПС для функции двух переменных следующим образом:

(9)

Используя операции суперпозиции и подстановки, можно показать, что операция Пирса может быть реализована для n аргументов:

f(x₁,x₂,…,x_n)= x₁½x₂½…½x_n =

(10)

Для представления переключательной функции в базисе Шеффера необходимо выполнить следующие действия:

· представить переключательную функцию f в дизъюнктивной нормальной форме;

· полученное выражение представить в виде

(поставить два знака отрицания);

· применить правило Де Моргана.

Например, для того чтобы представить функцию

в базисе Шеффера, необходимо выполнить следующие преобразования:

Для представления полученного выражения в базисе Шеффера воспользуемся соотношением (5.9):

f(x₁,x₂,x₃,x₄)=(x₄½x₂)½(x₃½x₁).

ЛИТЕРАТУРА

1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).

2. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.– М.: Наука, Физматлит, 2000.– 544 с.– ISBN 5-02-015238-2.

3. Петрова В.Т. Лекции по алгебре и геометрии. Учебник для ВУЗов: в 2 ч.– М.: Гуманит. изд. центр ВЛАДОС.– ч. 1 – 312 с., ч. 2 – 344 с. ISBN 5-691-00077-2. ISBN 5-691-00238-4 (I), ISBN 5-691-00239-2 (II).

4. Зарубин В.С. Математическое моделирование в технике: Учеб. для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.– 496 с. (Сер. Математика в техническом университете; вып. XXI, заключительный).