XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 71
Текст из файла (страница 71)
Заметим, что это полное множество двойственно к базису Жегалкина в том смысле, что каждая из его функций двойственна к соответствующей функции базиса Жегалкина: эквивалентность двойственна к сумме по модулю 2, дизъюнкция— к конъюнкции, константа 0 — к константе 1.
Полезно заметить также, что никакое собственное подмножество заданного множества не будет полным. б. Функция ~1 задана картой Карно (рис. 6.21), а вектор значений функции у2 есть (0,1,0,0). Для функции у2 очень просто находятся ДНФ и полипом Жег алкина: ~2 = Х1Х2 = (Х1 Щ 1)Х2 = Х1Х2 Щ Х2~ откуда следует нелинейность функции 5. Легко показать также, что эта функция принадлежит лишь классу Тд.
445 6.7. Теорема Поста Ох01 ОООх 01х1 1х10 10хО х000 Рис. 6.21 Так как ЯО,О,О,О) = 1, а Я1,1,1,1) = О, то функция ~1 не сохраняет ни константу О, ни константу 1. Далее, зта функция несамодвойственна, поскольку ЯО,1,1,1) = Я1,0,0,0) = 1; не- монотонность ее следует из того, что, например, ЯО,О,О,О) =1, но ~1(0,1,0,0) = О. Вопрос о нелинейности функции у1 оставим пока открытым, так как даже из частично заполненной критериальной таблицы (табл.
6.8) вытекает, что множество (~1, Я полно. Таблица б.б Формулы для отрицания и констант находятся легко: х = 11(х х х х) О =.6(х,х), 1 = ЛУ2(х~х)~ У2(х,х)~ У2(х~х)~ У2(х~х)). Формулу для конъюнкции проще всего построить прямо по ДНФ для функции Уг.' Х1 ' Х2 = ЯХ1~Х2) = 12(11(Х1>Х1,Х1~Х1)~ Х2). 446 б. БУЛЕВЫ ФУНКЦИИ Вернемся теперь к отложенному вопросу о нелинейности функции 2'1. По приведенной на рис. 6.21 карте Карно можно построить одну иэ минимальных ДНФ, представляющих эту функцию в виде 21 Х1Х2Х4 Ч Х1ХЗХ4 ЧХ1Х2ХЗ ЧХ1Х2Х4.
Подставляя в последнюю формулу 0 вместо х1, х вместо х2, 1 вместо хз и у вместо х4, получаем х у =ЯО,х,1,р), что доказывает нелинейность функции у1 и одновременно полноту множества (Я. Константы же можно представить формулами над базисом (Я, используя несамодвойственность функции у1 (см. разбор второго случая в доказательстве достаточности условия теоремы Поста): мы уже видели, что у1(0,1,1,1) = 11(1,0,0,0) = 1, т.е.
набор а из упомянутого места в доказательстве теоремы Поста есть 0111, и тогда функция Ь, фигурирующая в том же месте доказательства и равная в данном случае константе 1, будет иметь вид Й(х) = у1(х,х,х,х). Но так как х = 11(х,х,х, х), то получаем 1 = ЯЯх, х,х,х), х, х, х), 0 = ~1Щ11(х,х,х,х),х,х,х), ~1Щх,х,х,х),х,х,х), ~1Щх,х,х,х),х,х,х), уЯ1(х,х,х,х),х,х,х)). Подставив эти формулы в написанную вьппе формулу для конъюнкции, получим окончательно формулу над базисом Щ для конъюнкции. Мы не выписываем эту формулу ввиду ее громоздкости. 6.8. Схемы вз функциональных элементов 6.8.
Схемы нз функциональных элементов Представлению булевых фуккииб формулами можно придать следующий „инженерно-конструктивный" смысл. Будем рассматривать формулу Ф(х1,...,х„) кад каким-то произвольно фиксированным множеством Р как „черный ящик", некое устройство, на вход которого подаются всевозможные наборы значение переменных, а на выходе появляются соответствующие этим наборам значения функции у, представляемой формулой Ф (рис.
6.22). Рис. 6.22 Чтобы понять, как устроен „черный ящик", мы должны разобрать процесс построения формулы из нодформул. Добираясь до „базисных" подформул, т.е. элементов множества Р, мы приходим к „кирпичикам", структурным элементам, из которых собран „черный ящик", вычисляющий функцию ~. Каждая функция „базиса" Р вычисляется соответствующим „узлом", который рассматривается как мельчайшая структурная единица нашего „черного ящика", и его внутренняя структура уже не анализируется. Пример 6.22.
Выберем в качестве множества Р стандартный базис. Тогда формула над стандартным базисом, представляющая функцию ° (эквивалентность), строится следующим образом: Х1 Х2 Х1Х2 ЧХ1хэ. (6.21) 448 б. БУЛЕВЫ ФУНКЦИИ Вычисление по этой формуле (и процесс ее построения из элементов стандартного базиса) можно схематически изобразить так, как показано на рис. 6.23.
Ряс. 6.23 Переменное х1 (точнее, значение этого переменного) подается на вход структурного элемента, называемого пяверпюром (рис. 6.24, а) и вычисляющего отирипанпе. Снимаемое с выхода инвертора отрицание хм т.е. функция ям подается на один из входов кояъюяятиоро (рис. 6.24, б), на второй вход которого подается переменное хз.
На выходе конъюнктора появляется функция х1хз. Аналогично прослеживается вычисление функции х1яз. Обе эти функции подаются на входы дпзъюккпьора (рис. 6.24, в), с выхода которого снимается функция х1яз Чк1зз (это не что иное, как сумма ао модулю й я1 Е хз). И наконец, эта функция подается на вход инвертора, на выходе которого уже получается функция ° (эквивалентность). ф ~;> ~ ~ ° ) ~ф~ьл б в Рис. 6.24 Таким образом, мы приходим к идее „схемы" — математической модели вычислителя булевой функции, представленной некоторой формулой, собранного из структурных элементов, 6.6. Схемы вэ фуиклвоюиьвых элементов 449 Определение 6.14. Пусть фиксированы множества: Р (булевых функций) и Х (булевых переменных). Схемой иэ функииональньтх элементное над базисом РОХ (СФЭ), или просто схемой над базисом РОХ, также (Р,Х)-схемой, называют бесконтпурный ориентированный граф (т.е.
сетпь), каждая вершина которого помечена одним из элементов множества Р 0 Х так, что выполняются следующие требования: 1) каждый вход сети помечен либо некоторым переменным иэ Х, либо некоторой константой из Фв); 2) если вершина е сети помечена функцией у от и переменных (т.е. ~ й Р®), то ее полустпвпень захода равна и, причем на множестве дуг, заходящих в вершину е, задана (взаимно однозначная) нумерация, при которой каждая дуга получает номер от 1 до и. От У При изображении схем входы обозначаются кружочками, а вершины, не являющиесл входами, — треугольниками, внутри которых записано обозначе.
ние функции, помечающей данную вершину. Выходы отмечаются „выходными" стрелками. На рис. 6.25 приведена СФЭ над базисом Ц, х, у1. Рнс. 6.25 !5 — ИВь! каждый из которых вычисляет одну из „базисных" булевых функций. В общем случае „схема" вычисляет булев оператпр, причем каждая координатпнал функция этого оператора снимается с одного из выходов схемы. Математически „схема" определяется как ориеншированный граф специального вида, в котором и вершины, и дуги снабжены некоторыми метпками. Введем обозначение: если Р— какое-то множество булевых функций, то через Р<") обозначаем подмножество Р, состоящее из всех функций от и переменных (и ) 0).
450 б. БУЛЕВЫ ФУНКЦИИ Если базис подразумевается, то мы будем говорить просто „схема". Кроме того, если множество переменных фиксировано „раз и навсегда" и при рассмотрении различных схем мы меняем только множество функций Р, то, как зто мы делали, вводя понятия формулы и суиериозииии над заданным базисом, будем говорить о СФЭ над базисом г', полагая каждый раз, что подразумевается однажды фиксированное множество переменных Х, которое (если это не вредит точности) не упоминается. Определим теперь по индукции понятие йулеаой 4рунн44ии, вычисляемой вершиной схемы.
Определение 6.15. Пусть задана СФЭ 8 над базисом г'0 Х, множество вершин которой есть У. 1. Принимается, что каждый вход СФЭ вычисляет булеву функцию, которой он помечен (т.е. некоторое переменное или константу). 2. Если вершина и Е У помечена функцией у' 6 Ф">, заходящая в нее дуга с номером 4' (1 ( 4 ( н) исходит из вершины и; Е У, которая вычисляет функцию д;, то вершина и вычисляет суперпозиция ~(д1,...,д„). Таким образом, если каждая вершина СФЭ над Р вычисляет некоторую функцию, то порядок, в котором перечисляются функции дм ..., д„, подставляемые на места переменных функции у, в общем случае существен. Естественно назвать булаву функцию у от и переменных номмушап4ианой, если она сохраняет значение при произвольной перестановке ее переменных. В этом случае мы можем не заботиться о нумерации дуг, заходящих в вершину схемы, помеченную такой функцией.
Пример 6.23. Рассмотрим СФЭ на рис. 6.25. Вершины о4 и из — входы СФЭ. Эти вершины вычисляют соответственно функции х и у. Тогда вершина из, равно как и вершина о4, согласно определению 6.15, вычисляет функцию х~у (инарих Ше44ера), а вершина ив (выход сети) — функцию (х~у)~(х~у), которая, как известно, равна конъюнкции х у. 461 8.8. Схемм нэ фуннлнонвльнмх элементов Рис. 6.26 СФЭ, изображенная на рис.
6.26, имеет два выхода, вычисляющие функции (х!х)Щу) = х Ч у и (х~у)~(х~у) = х у. Определение 6.16. Булева функция, вычисляемая СФЭ над базисом е'О Х, — это функция, вычисляемая каким- либо иэ ее выходов. Таким образом, СФЭ вычисляет ровно столько булевых функций, сколько имеет выходов. СФЭ на рис. 6.26 вычисляет одну функцию, а СФЭ на рис. 6.26 — две.
В общем случае, если (хм ..., хн) — множество всех переменных, которые служат метками входов схемы о над базисом Р15Х, имеющей еп выходов, СФЭ о определяет отображение булееа куба В" в булез куб Внэ, т.е. булев опера5пор. Замечание 6.10. В некоторых случаях функцию, вычисляемую данной СФЭ, определяют несколько иначе, полагая, что это функция, вычисляемая любой вершиной иэ подмножества выделенных вершин СФЭ. В частности, это могут быть и выходы. В любом случае договоримся иэ выделенных (в только что указанном смысле) вершин схемы проводить „выходную" стрелку.
ф ! 5' 452 6. БУЛЕВЫ ФУНКЦИИ Таким образом, каждая схема из функциональных элементов вычисляет некоторый булез оператор, в частности, если число выходов схемы равно 1, то она вычисляет некоторую булеву функцию. Можно доказать и обратное: по любому булеву оператору может быть построена СФЭ над базисом Г, где Р— полное множес1пео, вычисляющая данный оператор. уаб и а 6 у Пример 6.24. Зададим таблицей булез оператор, отображающий ВЗ в В2 (табл. 6.9). Из таблицы легко увидеть, что у1 = х1Х2 Ч х1хз Ч хгхз~ у2 = х1 9Х2 ЩХЗ (функция у1 есть не что иное, как махсорин2арнал функция от переменных х1, х2, хз, и вьппе написана минимальнал ДНФ для нее, см. пример 6.12). Представим функцию у1 в базисе Жегалкина.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
