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

Министерство образования Республики Беларусь

Учреждение образования

«Белорусский государственный университет

информатики и радиоэлектроники»

кафедра ЭТТ

РЕФЕРАТ

На тему:

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

МИНСК, 2008

Из множества функционально полных наборов рассмотрим только те, которые имеют наибольшее практическое значение.

1. Основная функционально полная система логических функций. Наибольшее распространение получил набор, в состав которого входят три логические функции:

· f₁₀ – инверсия (логическая связь НЕ, логическое отрицание);

· f₁ – конъюнкция (логическая связь И, логическое умножение),

· f₇ – дизъюнкция (логическая связь ИЛИ, логическое сложение).

Этот набор получил название функционально полной системы логических функций (ОФПС). Из теоремы о функциональной полноте следует, что основная функционально полная система логических функций является избыточной, так как условиям теоремы отвечают наборы функций f₁₀ и f₁ или f₁₀ и f₇. Свойства этих функций были рассмотрены ранее.

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

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

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

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

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

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

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

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

Справедливость выражения (5.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)

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

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

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

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

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

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

(5)

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

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-го рода и доказывается путем вынесения за скобку общей части слагаемых, являющихся соседними конъюнкциями. Тогда в скобках остается логическая сумма некоторого аргумента и его инверсии, равная единице, что и доказывает справедливость правила.