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 = x1x2 x3) = (x1 x2)x3= x2( x1 x3).
Доказательство этого закона также не представляет никаких труд-ностей и может быть выполнено простой подстановкой.
Распределительный закон. В отличие от обычной алгебры алгебра логики симметрична. В ней справедливы два распределительных закона:
для логического умножения относительно логического сложения (рас-пределительный закон 1-го рода) и для логического сложения относи-тельно логического умножения (распределительный закон 2-го рода).
1. Распределительный закон 1-го рода записывается следующим образом:
(x1x2)x3=(x1x3) ( x2 x3) . (3)
Справедливость формулы (5.3), а также и ее более общего случая, когда в скобках заключена сумма любого количества слагаемых, можно доказать путем установления идентичности условий обращения в 0 или 1 ее левой и правой частей. Условием обращения в нуль левой части выражения (5.3) состоит в том, чтобы нулю равнялся либо один аргумент х3, либо одновременно аргументы x1 и x2. Условия обращения в нуль правой части выражения (5.1) такие же. Следовательно, распределительный закон 1-го рода справедлив для алгебры логики.
2. Распределительный закон 2-го рода имеет вид
(x1x2)x3=(x1x3) ( x2x3). (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) = =x1x3 в логичес-кую сумму конституент единицы.
Решение. Ранг конституенты единицы для данной функции равен 4. Произ-водим развертывание исходной конъюнкции поэтапно в соответствии с правилом развертывания:
1-й этап-- f(x1,x2,x3,x4) = x11x31.
2-й этап -- f(x1,x2,x3,x4) =
3-й этап -- f(x1,x2,x3,x4)=
= что и тре-бовалось получить.
Если членами преобразуемого выражения являются элементарные дизъюнкции, то переход от них к конституентам нуля производится также в три этапа по следующему правилу:
в развертываемую элементарную дизъюнкцию ранга r в качестве дополнительных слагаемых вводится п-r нулей;
каждый нуль представляется в виде логического произведения некоторой, не имеющейся в исходной дизъюнкции переменной, и ее отри-цания:
получившееся выражение преобразуется на основе распределитель-ного закона второго рода таким образом, чтобы произвести раз-вертывание исходной элементарной дизъюнкции ранга r в логическое произведение конституент нуля.
Пример. Развернуть элементарную дизъюнкцию f(x1,x2,x3,x4)= =x3x4 в логическое произведение конституент нуля.
Решение. Ранг конституенты нуля п = 4. Далее производим развертывание исходной дизъюнкции поэтапно в соответствии с правилом развер-тывания:
1-й этап -- f(x1,x2,x3,x4) =00x3x4;
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)= x1x2…xn = (10)
Для представления переключательной функции в базисе Шеффера необходимо выполнить следующие действия:
представить переключательную функцию f в дизъюнктивной нормальной форме;
полученное выражение представить в виде (поставить два знака отрицания);
применить правило Де Моргана.
Например, для того чтобы представить функцию
в базисе Шеффера, необходимо выполнить следующие преобразования:
Для представления полученного выражения в базисе Шеффера воспользуемся соотношением (5.9):
f(x1,x2,x3,x4)=(x4x2)(x3x1).
ЛИТЕРАТУРА
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, заключительный).
| ! |
Как писать рефераты Практические рекомендации по написанию студенческих рефератов. |
| ! | План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом. |
| ! | Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач. |
| ! | Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты. |
| ! | Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ. |
| → | Виды рефератов Какими бывают рефераты по своему назначению и структуре. |