Реферат: Функционально полные системы логических функций. Алгебраический подход
Министерствообразования Республики БеларусьУчреждениеобразования
«Белорусскийгосударственный университет
информатики ирадиоэлектроники»
кафедра ЭТТ
РЕФЕРАТ
На тему:
«Функциональнополные системы логических функций. Алгебраический подход»
МИНСК, 2008
Из множествафункционально полных наборов рассмотрим только те, которые имеют наибольшеепрактическое значение.
1. Основная функционально полнаясистема логических функций. Наибольшее распространение получил набор, в состав которого входят трилогические функции:
· f10 – инверсия (логическаясвязь НЕ, логическое отрицание);
· f1 – конъюнкция (логическая связь И,логическое умножение),
· f7 – дизъюнкция (логическая связь ИЛИ, логическоесложение).
Этот набор получил название функциональнополной системы логических функций (ОФПС). Из теоремы о функциональнойполноте следует, что основная функционально полная система логических функцийявляется избыточной, так как условиям теоремы отвечают наборы функций f10 и f1 или f10 и f7. Свойства этих функций были рассмотрены ранее.
Из определения представленияпереключательной функции в виде дизъюнктивной или конъюнктивной нормальнойформы следует, что эти представления реализуются в основной функциональнополной системе логических функций.
2. Законы алгебры логики в ОФПС и ихследствия. В алгебрелогики имеются четыре основных закона, регламентирующих порядок производстваопераций НЕ, И, ИЛИ в любом логическом выражении:
· переместительный(коммутативный);
· сочетательный(ассоциативный);
· распределительный(дистрибутивный);
· инверсии (правилоДе Моргана).
Переместительный закон. Этот закон справедлив как для дизъюнкции,так и для конъюнкции:
x1 Úx2 = x2 Úx1; x1 Ùx2 = x2 Ùx1. (1)
Справедливость выражения (5.1)нетрудно доказать простой подстановкой в него различных значений x1 и x2. Поскольку любую перестановку большего количестваслагаемых можно свести к последовательности перестановок слагаемых в отдельныхпарах, то переместительный закон будет справедлив при любом числе слагаемых.
Сочетательный закон. Этот закон, так же как ипереместительный, является симметричным, т. е. справедливым и для дизъюнкции, идля конъюнкции:
x1 Úx2 Úx3 = x1Ú(x2 Úx3) = (x1 Úx2)Úx3= x2Ú( x1 Úx3); (2)
x1 Ùx2 Ùx3 = x1Ùx2 Ùx3) = (x1 Ùx2)Ùx3= x2Ù( x1 Ùx3).
Доказательство этого закона также непредставляет никаких трудностей и может быть выполнено простой подстановкой.
Распределительный закон. В отличие от обычной алгебры алгебралогики симметрична. В ней справедливы два распределительных закона:
для логического умноженияотносительно логического сложения (распределительный закон 1-го рода) и длялогического сложения относительно логического умножения (распределительныйзакон 2-го рода).
1.Распределительный закон 1-го рода записывается следующим образом:
(x1Úx2)Ùx3=(x1Ùx3)Ú ( x2 Ùx3). (3)
Справедливость формулы (5.3), а такжеи ее более общего случая, когда в скобках заключена сумма любого количестваслагаемых, можно доказать путем установления идентичности условий обращения в 0или 1 ее левой и правой частей. Условием обращения в нуль левой части выражения(5.3) состоит в том, чтобы нулю равнялся либо один аргумент х3,либо одновременно аргументы x1<sub/>и x2. Условия обращения в нуль правойчасти выражения (5.1) такие же. Следовательно, распределительный закон 1-города справедлив для алгебры логики.
2. Распределительный закон 2-го рода имеет вид
(x1Ùx2)Úx3=(x1Úx3)Ù ( x2Úx3). (4)
Cправедливость формулы (4) (при любомколичестве аргументов) нетрудно доказать посредством установления идентичностиусловий обращения обеих ее частей в единицу.
Закон инверсии (правило Де Моргана). Этот закон, так же как и всепредыдущие, симметричен относительно логических сложения и умножения.
1. Отрицание логической суммынескольких аргументов равно логическому произведению отрицаний этих жеаргументов:
/> (5)
Доказательство закона не представляеттрудностей, поскольку условие обращения в нуль как левой, так и правой частейвыражения (5) состоит в том, чтобы был истинным хотя бы один аргумент.
2. Отрицание логического произведения нескольких аргументов равнологической сумме отрицаний этих же аргументов:
/> (6)
Справедливость этого закона следуетиз того, что условие обращения в единицу обеих частей формулы (6) заключается втом, чтобы был ложным хотя бы один аргумент.
Следствия из законов алгебры логики. Из доказанных выше законов можновывести ряд следствий, которые сформулируем в виде правил.
Правило выполнения совместныхлогических действий (правило старшинства логических функций). При решении логических задач приходитсявстречаться с выражениями, содержащими действия отрицания, конъюнкции идизъюнкции в любом сочетании. По аналогии с арифметическими действиями будемсчитать отрицание логическим действием первой ступени (старшей логической операцией),конъюнкцию — действием второй ступени, а дизъюнкцию — действием третьей ступени(младшей логической операцией).
Старшинство операции инверсиивытекает из закона инверсии, в соответствии с которым логическая суммаотрицаний некоторых аргументов не равна отрицанию их суммы (это справедливо идля логического произведения). Это значит, что ни операцию дизъюнкции, ниоперацию конъюнкции нельзя проводить, игнорируя знак отрицания над каким-либоиз логических аргументов, т. е. операцию отрицания надо проводить в первую очередь.
Относительно операций логическогосложения и умножения на основании симметричности законов алгебры логики можносказать, что они «равноправны». Из этого следует, что можно условиться считатьболее старшей операцией любую из них, но, приняв какое-либо условие, надопридерживаться его все время. На практике оказалось удобнее считать болеестаршей операцию логического умножения, так как это соответствует правиламобычной алгебры и для нас более привычно.
На основе изложенного можносформулировать следующее правило выполнения совместных логических действий: еслив логическом выражении встречаются только действия одной и той же ступени, тоих принято выполнять в том порядке, в котором они написаны; если в логическомвыражении встречаются действия различных ступеней, то сначала принято выполнятьдействия первой ступени, затем — второй, и только после этого — третьей. Всякоеотклонение от этого порядка должно быть обозначено скобками.
Правило склеивания. Прежде чем сформулировать самоправило, введем некоторые новые понятия. Если имеется некоторый конечный наборлогических аргументов x1, x2, … xn, то логическое произведение любого их числа называетсяэлементарным в том случае, когда сомножителями в нем являются либоодиночные аргументы, либо отрицания одиночных аргументов. Так, например, f1(х1, х2, x3, х4)= х1×х2×x3×х4 — элементарное произведение(элементарная конъюнкция); />—не является элементарным произведением.
Cимвол любого аргумента в элементарнойконъюнкции может встречаться только один раз, поскольку произведение аргументасамого на себя равно этому же аргументу, а произведение аргумента на своеотрицание равно нулю. Количество сомножителей в элементарной конъюнкции называетсяее рангом.
Два элементарных произведенияодинакового ранга rназываются соседними, если они являются функциями одних и тех жеаргументов и отличаются только знаком отрицания (инверсии) одного из сомножителей.Например, элементарные конъюнкции
f1(х1, х2, x3, х4)= х1×х2×x3×х4и f3(х1, х2, x3, х4)= />
являются соседними, так какотличаются только одной инверсией в переменной x2, а элементарные конъюнкции
f3(х1, х2, x3, х4)= /> и f4(х1, х2, x3, х4)= />
соседними не являются.
Правило склеивания для элементарныхконъюнкций может быть сформулировано следующим образом: логическую суммудвух соседних произведений некоторого ранга rможно заменить одним элементарнымпроизведением ранга r-1,являющимся общей частью исходных слагаемых.
Это правило является следствием распределительногозакона 1-го рода и доказывается путем вынесения за скобку общей части слагаемых,являющихся соседними конъюнкциями. Тогда в скобках остается логическая сумманекоторого аргумента и его инверсии, равная единице, что и доказываетсправедливость правила.
Например,
/>.
Поскольку алгебра логики являетсясимметричной, то все определения, данные для конъюнкции, будут справедливы идля дизъюнкции.
Если имеется некоторый конечный наборлогических аргументов, то логическая сумма (дизъюнкция), зависящая от любого ихчисла, называется элементарной в том случае, когда слагаемыми в ней являютсялибо одиночные аргументы, либо отрицания одиночных аргументов.
Количество слагаемых в элементарнойдизъюнкции называется ее рангом. Две элементарные суммы одинаковогоранга называются соседними, если они являются функциями одних и тех жеаргументов и отличаются только знаком отрицания (инверсии) одного изслагаемых.
Правило склеивания двух элементарныхдизъюнкций формулируется так: логическое произведение двух соседних суммнекоторого ранга rможно заменить одной элементарной суммой ранга r-1, являющейся общей частью исходных сомножителей.
Это правило является следствием распределительногозакона 2-го рода и применяется для упрощения логических выражений.
Например:
/>
Правило поглощения. Так же как и склеивание, поглощениеможет быть двух видов. Правило поглощения для двух элементарных конъюнкцийформулируется так: логическую сумму двух элементарных произведений разныхрангов, из которых одно является собственной частью другого, можно заменитьслагаемым, имеющим меньший ранг.
Это правило является следствием распределительногозакона 1-го рода. Доказывается оно посредством вынесения за скобку общей частислагаемых. В скобках останется логическая сумма некоторого выражения и единицы,равная в свою очередь также единице, что и доказывает справедливость правила.Например,
/>
Правило поглощения для двухэлементарных дизъюнкций: логическое произведение двух элементарных суммразных рангов, из которых одна является общей частью другой, можно заменитьсомножителем, имеющим меньший ранг.
Это правило является следствием распределительногозакона 2-го рода и также находит широкое применение для упрощения логических функций.
Правило развертывания. Это правило регламентирует действие,обратное склеиванию. Иногда требуется представить некоторое логическоевыражение в виде совокупности конституент единицы или конституент нуля. Есличленами преобразуемого выражения являются элементарные конъюнкции, то переходот них к конституентам единицы производится в три этапа по следующему правилу:
· в развертываемую элементарнуюконъюнкцию ранга rв качестве дополнительных сомножителей вводится п-rединиц, где п — ранг конституенты;
· каждая единицапредставляется в виде логической суммы некоторой, не имеющейся в исходнойконъюнкции переменной и ее отрицания: />;
· производитсяраскрытие всех скобок на основе распределительного закона первого рода, чтоприводит к развертыванию исходной элементарной конъюнкции ранга rв логическую сумму кон-ституент единицы.
Пример Развернуть элементарнуюконъюнкцию f(x1,x2,x3,x4)= =x1×x3 в логическую сумму конституент единицы.
Решение. Ранг конституенты единицыдля данной функции равен 4. Производим развертывание исходной конъюнкциипоэтапно в соответствии с правилом развертывания:
1-й этап— f(x1,x2,x3,x4) = x1×1×x3×1.
2-й этап — f(x1,x2,x3,x4) =/>
3-й этап — f(x1,x2,x3,x4)=
=/> что и требовалось получить.
Если членами преобразуемого выражения являютсяэлементарные дизъюнкции, то переход от них к конституентам нуля производитсятакже в три этапа по следующему правилу:
· в развертываемую элементарнуюдизъюнкцию ранга rв качестве дополнительных слагаемых вводится п-r нулей;
· каждый нульпредставляется в виде логического произведения некоторой, не имеющейся висходной дизъюнкции переменной, и ее отрицания:/>
· получившеесявыражение преобразуется на основе распределительного закона второго рода такимобразом, чтобы произвести развертывание исходной элементарной дизъюнкции рангаrв логическое произведение конституентнуля.
Пример. Развернуть элементарнуюдизъюнкцию f(x1,x2,x3,x4)= =x3Úx4 влогическое произведениеконституент нуля.
Решение. Ранг конституенты нуля п= 4. Далее производим развертывание исходной дизъюнкции поэтапно в соответствиис правилом развертывания:
1-й этап — f(x1,x2,x3,x4) =0ÚÚx3Úx4;
2-й этап — f(x1,x2,x3,x4) =/>
3-йэтап—f(x1,x2,x3,x4)=
/>
что и требовалось получить.
Проверить правильность проведенных преобразованийможно при помощи правила склеивания.
3. Функциональнополные системы логических функций. Анализ принадлежности переключательныхфункций замкнутым классам показывает, что существуют две переключательныефункции f8 и f14, не принадлежащие ниодному классу. Согласно теореме о функциональной полноте, каждая из этихфункций образует функционально полную систему логических связей и используятолько одну из них можно представить любую, сколь угодно сложнуюпереключательную функцию.
Операция Пирса (стрелка Пирса) реализует функцию,которая принимает значение, равное единице только в том случае, когда все ееаргументы равны 0 (ИЛИ-НЕ), что может быть записано в ОФПС для функции двухпеременных следующим образом:
/> (7)
Используя операции суперпозиции и подстановки можнопоказать, что операция Пирса может быть реализована для nаргументов:
/> (8)
Для представления переключательной функции в базисеПирса необходимо выполнить следующие действия:
· представить переключательнуюфункцию f в конъюнктивной нормальной форме;
· полученное выражение представить ввиде />(поставить два знака отрицания);
· применить правило Де Моргана.
Например, для того чтобы представить функцию
/>
в базисе Пирса, необходимо выполнить следующиепреобразования:
/>/>
Для представления полученного выражения в базисе Пирсавоспользуемся соотношением (7):
/>.
Операция Шеффера (штрих Шеффера) реализует функцию,которая принимает значение, равное нулю, только в том случае, когда все ее аргументыравны 1 (И-НЕ), что может быть записано в ОФПС для функции двух переменныхследующим образом:
/> (9)
Используя операции суперпозиции и подстановки, можнопоказать, что операция Пирса может быть реализована для nаргументов:
f(x1,x2,…,xn)= x1½x2½…½xn =/> (10)
Для представления переключательной функции в базисеШеффера необходимо выполнить следующие действия:
· представить переключательнуюфункцию f в дизъюнктивной нормальной форме;
· полученное выражение представить ввиде />(поставить два знака отрицания);
· применить правило Де Моргана.
Например, для того чтобы представить функцию
/>
в базисе Шеффера, необходимо выполнить следующиепреобразования:
/>/>
Для представления полученного выражения в базисеШеффера воспользуемся соотношением (5.9):
f(x1,x2,x3,x4)=(x4½x2)½(x3½x1).
ЛИТЕРАТУРА
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, заключительный).