Игошин Математическая логика и теория алгоритмов (1019110), страница 25
Текст из файла (страница 25)
Хь 4.!0 — 4.24). Выражение одних булевых функций через другие. О взаимозависимостях булевых функций возникает много вопросов. Как выражаются одни булевы функции в виде суперпозиций других бу- 99 левых функций? Можно ли все булевы функции выразить через какие-то одни и те же функции? Существует ли такая булева функция, через которую выражаются все остальные? И так далее. В следующей теореме приводятся основные выражения одних булевых функций через другие, которые можно использовать при получении новых зависимостей между булевыми функциями. Теорема 9.5. Справедливы следующие равенства, выражающие одни булевы функции через другие: а) х у= (х' ы у')', б) х ы у = (х' .
у')'; в) х ы у = (х — э у) -э у; г) хм у=х' — >у; д) х -э у = х' ы у; е) х с-> у = (х -+ у) (у -+ х); До к азател ьств о. Для а) и б) доказательства равенств легко следуют из законов де Моргана (теорема 9.3, з), если на обе части каждого из них «навесить» знак отрицания, а затем к левым частям полученных равенств применить равенство из теоремы 9.3, к.
Для и) и г) равенства можно проверить с помощью общего метода таблиц, а можно воспользоваться равенством д), преобразуя, например, правую часть первого равенства. Тогда (х «у) — > у = = (х 'ч у) -э у =(х'ч у)' ы у = (х". у') ы у = (х у') ы у = (х ы у) . (у' ы г у) = (х ы у) 1 = х ы у. При доказательстве были использованы, кроме того, соотношения теоремы 9.3, з, к, е, и, г. д) Равенство легко проверяется с помощью таблиц. е) Докажите, построив таблицы.
ж) и к) Соотношения непосредственно видны из таблиц, определяющих функции штрих Шеффера и стрелку Пирса. з) и л) Равенства уже отмечались при определении функций штрих Шеффера и стрелка Пирса. и) Можно составить таблицы, а можно рассуждать следующим образом: х' ~ у' = (х'. у')' = хм у. В первом равенстве использовано предыдущее соотношение з).
м) Докажите равенство подобно тому как было доказано равенство и), используя при этом соотношение л). П В 10. Булевы функции от н аргументов Понятие булевой функции. В предыдущем параграфе мы уже говорили о булевых функциях от одного и от двух аргументов. Введем понятие булевой функции от произвольного конечного числа аргументов. Определение 10.1. Булевой функцией от п аргументов называется функция 1', заданная на множестве (О, 1)" и принимающая значения в двухэлементном множестве (О, 1).
Другими словами, булева 100 функция от и аргументов сопоставляет каждому упорядоченному набору длины л, составленному из элементов 0 и 1, либо О, либо 1. Булева функция 1 от л аргументов хп х,, ..., х„обозначается так: У(хь хг, х„). Две булевы функции от л аргументов 1(хп хг, ..., х„) и я(х„ х, ..., х„) называются равными, если любым одинаковым наборам значений аргументов хп х,, ..., х„обе эти функции сопоставляют одинаковые элементы из множества (О, 1), т.е. 1(ап а„..., а„) = =е(ап аг, ..., а„) для любых элементов ап аг, ..., а„е (О, Ц. В в 9 уже встречались булевы функции от трех аргументов, например .)~(«1 Хгр Х3) = (Х~ р4 Хг); Хзр.~~(Х|р Х» Х3) = Х,,/ (Хг р. Х,), ф(Х»р Хг, Хз) = Х| 4 (Хг .
Хз), ф(«3, Хг, Хз) = (Х! "' Хг) . (Х» 4 Хз) В частности, было показано, что Я«3, хгр хз) = зг(«3, хг хз) и ед(«3, хг, хз) = яг(хн хг, хз). Перечисленные функции построены с помощью суперпозиций (или последовательного применения) более простых функций. Определение 10.2. Суперпозицией булевых функций й,(у,', уг, ..., у, р), ., я„(у„', уг, ..., у„) в булеву функцию 1(хн х,, ..., х„) называется новая булева функция, получающаяся из функции 1'(хь хг, ..., х„) подстановкой вместо (всех или некоторых) аргументов хп хг, ..., х„функций яь яг, ..., я„соответственно Яй»(у,', ..., у, '), ..., й„(у„', ..., у„")). Полученная функция Г(у,', ..., у, р, ..., у„', ..., у„'" ) зависит от т» + тг + ...
+ лг„аргументов. Например, если 3(и, хз) = и р4 хз, 133(хн хг) = х| м хг, то У~(«3, хг, «3) = 4'(13|(хн «,), хз) = (», 4 хг) 4 «». Или если Я(и, и) = и и, 1»г(х», хг) = х~ Р4 хг, Ьз(хп хз) = х» 4 хз, ТО г(Х»р Хг Х3) Я(Ьг(»~р Хг)р Ьз(«рр Хз)) (Х~ 4 Хг) ' (Х1 I ХЗ)' Опишем еще одну процедуру, которую можно проделывать с булевыми функциями.
Зафиксировав один из аргументов булевой функции Яхн хг, ..., х„) от л аргументов, т.е. придав этому аргументу какое-нибудь конкретное постоянное значение (из двухэлементного множества (О, 1)), получим функцию от л — 1 аргументов. Так, фиксируя в функции 1"(хп х,, ...р х„) /с-й аргумент (1 < к < л), можем получить две новые булевы функции от л-1 аргументов: ,1(хь ..., х» „О, х», „..., х„) и 1'(«3, ...„»» ь 1, х„, н ..., х„).
Например, из функции от трех аргументов гг(хп хг, хз) = (х, р4 х,) . (х~ 4 х,) фиксированием первого аргумента получаем следующие функции от двух аргументов: 3 (хг х3) = Рг(0, хгр х3) = (О 4 хг) ' (О 4 х3) = хг ' хз )г"(хгр хз) = Гг(1, хг, хз) = (1 Р4 х ) . (1 Р4 х ) = 1 1 = 1. Предлагаем посмотреть самостоятельно, какие получатся функции из функции Рг(хп хг, х,) при последовательном фиксировании остальных ее аргументов хг, хз. Число булевых функций. Перечислив в 5 9 все булевы функции от одного аргумента и от двух аргументов, мы видели, что первых 10! имеется всего четыре, а вторых — шестнадцать.
Возникает вопрос, сколько будет разных булевых функций от трех аргументов, от четырех аргументов и т.д. Нельзя ли указать формулу, по которой вычислялось бы число булевых функций от и аргументов? Ответ на поставленный вопрос дает следующая теорема. Теорема 10.3 (о числе булевых функций от и аргументов). Число различных булевых функций от и аргументов равно 2~ .
Доказательство. Чтобы задать булеву функциюЯхь ..., х„) от и аргументов, нужно перечислить все наборы (аь ..., а„) из нулей и единиц значений, которые могут принимать ее аргументы хь ..., х„, и для каждого такого набора указать значение функции 1: которое она принимает на этом наборе. Выясним сначала, сколько существует различных наборов (а„..., а„), составленных из нулей и единиц, значений для и аргументов х,, ..., х„.
Покажем, что это число равно 2". Доказательство будем вести методом математической индукции по числу и. В самом деле, для и = 1 имеется всего два набора значений переменного хь Это 0 и 1. Так что для и = 1 число наборов равно 2'. Предположим, что для ?с аргументов имеется точно 2» различных наборов (а„..., а»), составленных из 0 и 1, значений для lс аргументов. Тогда среди всевозможных различных наборов (а„..., а», а»„) значений для /с+ 1 аргумента имеется, согласно предположению индукции, точно 2' наборов вида (а„..., аы 0) и точно 2» наборов вида (аь ..., а», 1).
Следовательно, всего будет 2»+ 2» = 2 2»= 2»" различных наборов. Тем самым доказано с помощью индукции утверждение о числе различных наборов. Таким образом, для задания функции 1 от и аргументов нужно указать ее значение для каждого из 2" различных наборов значений ее аргументов. Если каждое значение функции равно нулю, то такая функция постоянна. Она называется константа О. Если каждое значение функции равно единице, то это вторая постоянная функция, называемая константа 1.
Мы указали лишь две различные функции от и аргументов. Сколько же их существует всего? Ровно столько, сколько имеется разных наборов длины 2", составленных из нулей и единиц (см. таблицу). 102 Разных наборов длины 2"„составленных из нулей и единиц, как показано в начале доказательства теоремы, имеется 2', где 1= — 2 — длина набора. Таким образом, число т разных булевых функций от и аргументов равно точно 2'= 2'" . Теорема доказана. С) Выражение булевых функций через конъюнкцию, дизъюикцию и отрицание. У нас уже возникали вопросы относительно выражения одних булевых функций через другие, и на некоторые из них мы уже дали ответ.
Как будет показано ниже, существуют такие булевы функции (уже хорошо известные нам), через которые выражаются все (вообще все, от любого числа аргументов!) булевы функции. Этим замечательным свойством обладают взятые вместе конъюнкция, дизъюнкция и отрицание. Прежде чем сформулировать и доказать основную теорему этого пункта, обратимся к следующей важной лемме, Лемма 10.4 (о разложении функции по переменной). Лля произвольной булевой функции г (хь хь ..., х„) справедливы следующие формулы, называемые формулами разложения этой функции по переменной х,: ~(»ь х„..., хи) = (х, . Л1, х„..., хл)) ~(»1' . У(0, хъ ..., «л)); )(хь хъ ..., х„) = (х| и ЛО, хъ ..., х„)) (х|' ч Я1, хъ ..., х )).
Доказательство.Докажемсправедливостьпервой формулы. Нужно проверить, что функции, стоящие в обеих частях равенства, при одинаковых значениях их аргументов принимают равные значения. Рассмотрим сначала всевозможные наборы значений аргументов следующего вида (О, аъ ..., а„), т.е. будем придавать аргументам х„хъ ..., х„значения: х, = О, х, = а„..., х„= а„. При этом безразлично, каковы именно значения аъ ..., а„. Вычислив, какое значение принимает на наборах такого вида функция, стоящая в правой части доказываемого равенства, убедимся, что оно совпадает со значением, принимаемым функцией, стоящей в левой части этого равенства, на том же наборе значений аргументов. В самом деле, (О з(1, аь ..., а„)) ~ (О' . ЯО, аъ, а„)) = О ы (1 /"(О, ац ..., а„)) = = 0 чЯО, а„..., а„) =г(0, а,, ..., а„).
Теперь рассмотрим всевозможные наборы значений аргументов вида (1, а,, ..., а„), т.е. будем придавать аргументам хь х„..., х„ значения: х, = 1, х, = а„..., х„= а„. Аналогично вычисляем значение, принимаемое функцией, стоящей в правой части доказываемого равенства, на наборах такого вида: (1 ~(1, ац ..., а„)) ~~ ' (1' г(0, аъ ..., а„)) =г(1, а„..., а„) ч (О г(0, аъ ..., а„)) =г(1, аз, ..., а„) ~~ 0 = )"(1, а,, ..., а„). Итак, функции из обеих частей равенства принимают одинаковые значения при одинаковых значениях их аргументов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
