Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике, страница 10

Среди функций, зависящих только от двух переменных х1 и хсп найти те, которые имеют наибольшее число разных подфункций. (Каждая подфункция функции Дхы хз) рассматривается как функция, зависящая от обеих переменных х1 и хз.) Решение. Эту задачу можно решать следующим (громоздким, переборным) способом: выписать все функции, зависящие от переменных хз и хз (их 16!), затем для каждой из них найти все ее подфункции и выяснить, сколько среди них разных.

Привлекая некоторые дополнительные утверждения, удается сократить перебор. Например, можно воспользоваться следующими фактами (см. задачу 2.6): 1) если функция д(х ") может быть получона из функции г'(хб ") переименованием переменных без отождествления, то число различных подфункций у функции 1(хи) и д(х") одинаковое: 2) у двойственных функций число различных подфункций одинаковое; 3) если д(х") = 1(хп), то число различных подфункций у функций 1(х") и д(х") одинаковое. Принимая во внимание зти три утверждения, достаточно ограничиться рассмотрением пяти функций: О, хы хзхх, хз Ю хз и хз -ь хз. 44 Гл, 1.

Способы задания и свобства фупкиий алгебре~ логики Е1етрудно установить, что у функции 0 все подфункции равны ей самой, а у функции хг три разные подфункции: О, 1 и хы У функции х>хг разных подфункций пять: хгхг, О, хы хг и 1. У функции хг ~В хг семь разных подфункций: хс Ю хг, хы хг, хс Ю 1, хг Ю 1, 0 и 1. Наконец, у функции хг — о хг пять подфункций: хг -л хг, 1зхг =та, хс-гО=хы 1-о0=0 и 0-гхг =хг -г1=0-+О:— =Оэ1=1э1=1. Итак, наибольшее число разных подфункций (семь) имеют следующие функпии, зависящие от хг и хг, хг ~Эхг и хг 9 хг 91 = х~ хг Привсдом ещо одно решение данной задачи.

Сначала заметим, что у функции, зависящей существенно хотя бы от одной переменной, число различных подфункций нс меньше трех (она сама и две константные подфункции всегда отличны друг от друга). Поэтому тот случай, когда исходная функция есть константы, можно не рассматривать (ибо все ее подфункции просто совпадают с ней самой). Палое, если функция Д(т") зависит существенно только от одной переменной, то она имеет вид х,, где и Е (О, 1) (1 = 1, 2). Очевидно, что у такой функции три различные подфункции: х,, 0 и 1.

Теперь займемся исследованием функций, у которых обе переменные существенные. Возможны два подслучая: а) функция Дхг) принимает некоторое значение о на трех наборах значений переменных, а другое значение о на одном наборе); б) функция 1" (х г) принимает каждое значение (О и 1) ровно на двух наборах. В случае а) в каждой паре подфункций ®О, хг), 1(1, хг)) и (Д(хм 0), 1(хы 1Н ровно одна подфункция является константой о, а другая есть соотвстствснно х и х' (где гб т Е (О, 1)). Отсюда следует, что у данной функции 1(х ) ровно пять различных подфункций: сама функция 1" (хТг), х(, х,, 0 и 1.

Перейдем к подслучаю б). Здесь ни одна из подфункций ((О, хг), 1(1, хг), 1 (хеы 0) и 1 (хы 1) не может быть константой. В самом деле, если, например. 1(0, хг) = сг, то функция г"(1, хг) должна быть равна тождественно а; но тогда (см. формулу (2)) (х~ при о = О, г(х ) =хгогхго= )— ~хг при о =1, т.е, фУнкциЯ 1(х ) зависит несУщественно от пеРеменной хг, что противоречит условию.

наложенному на функцию Г" (ха). Палее, так как функция 1(хг) существенно зависит от обеих переменных. то 1"(О, х ) ф 1'(1, хг) и 1'(хы 0) ф 1'(х, 1). действительно, если, например, ДО, хг) = 1(1, хг), то, используя формулу (2), получаем (ср. с решением примера 4): 1"(х ) = хг1"(О, хг)'дхг1'(1, хг) = хг1"(О, хг) Ч У хг1'(О.,хг) = (хг Ч хг) 1'(О, хг) = 1 4с 1'(О,хг) = 1(О,хг), т.е. переменная хз фиктивная. Это противоречит условию, наложенному на функцию 1(хзг). Из всего сказанного относительно функций 1(0, хг), 1'(1, хг) 1'(хы 0) и 1'(хы 1) следует,. что ДО, хг) = хг, .1'(1, хг) = = хго = хг — — хг, 1 (хы 0) = хг и ~(хы Ц = х' = х'. Отсюда вытекает, что у функции у(юг) семь разных подфункций: она сама., О., 1, хсы у ец Специальные представления булевых функции 45 хы хг и х,.

Нетрудно получить и выражение для функции 1(х ), воспользовавшись, например, формулой (10): з (х ) = хзх2 и хзх2 = (Х1 ч' 1) Х2 ® хз(Х2 йз 1) = хгх2 ~~ Х2 л' хзх2 ~~ хз х! ~~~ 22 (Х4 хг, если П = О, = хз ег хг е4 и ев 1 = 4( (хзйхг, если п=1. (Здесь, как и выше, мы использовали эквивалентности х, = х" Ю 1, а также очевидные тождества х = х - и = хааа.й 1.) 2.1. 1зассматривая соответствующую компоненту функции 7'(хп) как функцию, зависящую от всех переменных хы хг, ..., Хп, представить ее в векторной форме: 1) з (Х ): Хз + (Х2 чг Хзхз), Х2-КОМПОНОНту 2) ((х ) = Хзхг ~ (Хг — 4 хгхз), хз-компоненту; 3) 7 (х ) = (Уз '4 х2 ~l хз) 4 (хз 4 (У2 е хз)), хыкомпоненту; 4) 2'(х ) = (01110100), хыкомпоненту; 5) 2 (х ) = (11001110), хг-компоненту; 6) з (х ) = (10011110), хз-компоненту; 7) з (х ) = (хз ез хг) — > (хз — 4 хзх4), хгхл-компоненту; 8) з (х ) (хз дх2хз Ч х4) аг (хзхгхз е х4), х1у2хз компоненту; 9) 7'(х~) = (0101011011100011), Угхв-компоненту; 10) ((х ) = (1101101100001001), хгхзх4-компоненту.

2.2. Используя хз — и У,-компоненты функции 7" (хп), построить в векторной форме ее х -компоненту, причом эту компоненту следует рассматривать как функцию, зависящую от всех перемен- НЫХ Хмхг~ . ~ Ха' Ц (1( 3) х > хз 74(хз) — Х2 хз кОмпоненту 2) л ( ) х е (х ) хз хз, хыкомпоненту; 3) лз(.-з) (00111100), фх ) = (Ш10000), хг-компонентУ ) 2(хз) (10101111) у2(хз) х, ~ хз, уз-компоненту; 5) ~~(Х ) = Т ЯЗХ4,(~ (Х ) = Х2 лхл Х2 У1 6) у2(х4) — х ) х Х4 Д(х4) = Узхзхв, х4"кОмшшснту~ 7) зо(х ) = хгхз ~Э х4, з'4 (х ) = (1011011110110111), хз-компоненту.

2.3. Представить в совершенной д.н.ф. следующие функции: 1) з (Х ) (хз ПХ2) е Хз 2) з (х ) (Х1 е Х2) е (хз ~ хгхЗ)~ 3) Д(х з) (01010001) 4) Д(х з) (01111000) 5) з'(х~) = (10001111); 6) з'(х~) = (хз -4 хгхзхл) (хз — + хзхг); 7) 1(х~) = (хзйзхг) (хз — 4 хгх4); 8) 1(х~) = (0100100011000010); 9) 7(х~) = (1000011100110001); 10) 7(х~) = (1100100010010011). 46 Га.

1. Способы задания и свойыпва угупкиий ааеебрь~ возики 2.4. Представить в совершенной к.н.ф. следующие функции: 1) 7(х~) = хг 9 хг, 2) 7(хг) = хе .( хг., 3) 1(х') =х,хг гх,хз 1х,х,; 4) Дх') = х,х, Юхе; 5) 7'(х з) (01011101). 6) 7(х з) (0010П 10 7) 7(х ) = (хг У хг У хз) . х4 У хгхгхз,' 8) 1(х ) = хг — > (хг — > хзх4); 9) 7(х ) = (010111110111001Ц: 10) 7(хв) = (0110111011100101).

2.5. Представить в указанной форме соответствующую компонен- ту функции 1(хо) (рассматривая эту компоненту как функцию от «оставшихся» переменных): 1) 1(х ) = хгхг -Ф хз, хз-компоненту в совершенной к.н,фц 2) У(хз) = (хз ~ хг) хз, хз-компоненту в совершенной д.н.фб 3) ((х ) = хгхг (хг тз), хг-компоненту в совершенной д. н. фд 4) 7(х ) = (11101101), хг-компоненту в совершенной д.

н. ф.; 5) 7(х5з) = (01011011), хз-компоненту в совершенной к.н.фл 6) Дхха) = (хг М хг Ч хз)х4 Н хгхгхз, хгхз-компоненту в совершен- ной д. н. фл 7) У(хд~) = хг — > ((хгхз -+ х4) — > хг), хг-компоненту в совершен- ной к. н. фд 8) У(х ) — ((хг ~ хг) (хз) ~ (хг.(х4), хз-компоненту в совершен- ной к.

н. фд 9) Дх~) = (0110111010110111), хгхв-компоненту в совершенной д. н. ф.; 10) 7(х~) = (1011011101111000), х4-компоненту в совершенной к. н. ф. 2.6. Показать, .что число различных подфункций у функций 1" (хи) и д(ха) одинаковое, если: 1) функция д(ха) получается из функции 7(ха) переименованием переменных без отождествления; 2) функция д(х") получается из функции Д(х") заменой некото- рых (быть может, всех) переменных на ик отрицания; 3) д(хп) = 1'(х"); 4) функции 1"(х") и д(х") двойственные. 2.7. Подсчитать число различных подфункций у функции Дхо), хд- и хюкомпоненты которой известны (напоминаем, что подфунк- ции функции Д(х") следует рассматривать как функции, зависящие от всех переменных хы хг, ..., х„): 1) Д(хо) =хг 'д...'~хп, Й(х, ) = 1 (и Э 2); 2) уо(х") = хг 61 ..

61 ха Л(хп) = хг бз .. 6зхп (и ~ )2), 3) 1о(х ) =*я . хо Л(х ) = хг ..хо (и 3 2); 4) уо(хп) = тг ..хоЧхг...хп, Д(хп) = хг...х, (и > 2); 5) 1о(х ) = хг . хо; Л (х ) = хг у ... у х, (и 3 2); 5) Д(х ) =гг дхп Л(х ) хз о ° Лхо (п~)3)~ у в. Савциальиыв представления булевых функций 47 7) ув)Хь) = ХЗ...Хь, Д)Х") = Х2'4 ХЗ )П ~ )3); 8) Уо~1х в) = хз -+ х„, 21 1хв) = хз... х„1п > 3). 2.8.

Найти число функций 11х"), удовлетворяющих условию: 2во21х") = Я1х") при всех 4, у таких, что 1 < 1 < у < и. 2.9. Показать, что число различных функций 2'1х"), для которых данная функция 21хь) является цодфункдией, не меньше 22 — 122 — 1)2 1к < и). 2. Днзъюнктнвные н конъюнктнвные нормальные формы. ФоРмУла х,'вгх;ьвв ...

ввх;', где ов 6)0, 1), х, — ха х, — хп~ 1ьс11,2,...,11), 1=1,2,...,г )г>1 и п>1), называется конъюнкцией иад множеством Х" = 1х1, хэ, ..., х„). Аналогично, формула х~,' 12 х~,' 42... 42х," называется диэьюнкцией над .ииожествои Х". Если х,, у'. -х;,„при у ~ в, то конъюнкция 1соответственно дизъюнкция) называется элементарной (сокращенно э. к. и э.

д, соответственно). Выражения вида х, ' называются буквами. Число букв в э. к. 1и в э. д.) называется рангом э. к. 1соответственно э. д.). Константа 1 считается по определению э. к. нулевого рангоь а константа 0— э. д. нулгвого ранга. Формула вида оь К уК 12 12К 113) ( краткая запись 1„4 К4), где К; .. попарно различные элементарные конъюнкции 11 = 1,2,..., в) и в > 1, называется диэъюиктивной нормальной формой 1сокра4ценно д.