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

) сопоставленанекотоРаафУнкциЯ г,: Вп* — Р— р В = (О, 1). Понятие функции ези, реализуемой формулой й над .множеством Ф, определяется (как и понятие формулы) по индукции: 1) если Й вЂ” 1. (ххт ххт ..., х ), то для ~с~~о~о набора (оы Оь1 оз, ..., оп,) значений переменных х,, х,, ..., х „значение функции ~ри равно г';(пы оз, ..., оп,); 2) если й = й(уы ..., Уя) = ф(йы йз, ..., Йт), где.

ф 9 Ф и Й~ либо формула над Ф, либо переменная из Х, то уи(оы ..., оь) = = Е(А, )дг, ...,. р1т), где Г функция, сопоставленная функциональному символу З", и ~3р ". значение функции еои, (р = 1, 2, ..., тп), причем ыю если Йр — — ую )др = ~ри„(ор,, ..., ор,), если Йр — — Йр(ур,,...., ур,) (здесь в зависит, естественно, от р). Если й = у,п* (х,, х:„..., х „), то функция ~ри, реализуемая (пд формулой й, обычно обозначается через У';(х,, х „..., х.„). Если же й = Дйм Йз, ..., Й,„), то ези обозначается через Р(ези, (ум, Узз Уме)' ляг (У21 У22 ° Узег) Фи, (Утз Утз ° Уте ))~ 14 Гл, й Способы задания и свойс1пва функций алгебры логики здесь Р функция, сопоставленная функциональному символу 1, а 1ри (у,1, у,з, ..., у„) — функция, реализуемая формулой й, (1 = =1,2, ..., .т).

Понятие функции дги, ре лизувмой формулой й над множеством связок Ь, вводится (также по индукции) следующим образом; 1) формуле й = х, где х Е Х, сопоставляется тождественная функция дгн(х) = х; 2) ЕСЛИ й = (З 22) ИЛИ й = (Ж л К), Гдс л Е 1 Й, Ч', Ю, -, -Л, /, Ц, то соответственно д1и = 1ов, и 1ои = 01в лвгс (здесь символ л надо понимать уже как обозначение для соответствующей элементарной булевой функции: см. табл. 1.3 и табл. 1.4). Пусть Й = й(Х1,, ..., х,,), 22 = З(Х1,, ..., х,) и (Х1, хг, ... ..., Хп) МНОжЕСтВО тЕХ ПЕРЕМЕННЫХ, КОТОРЫЕ ВСтРЕЧангтСЯ ХОТЯ бы в ОДНОЙ из формул Й и З, Т.е.

(Х1, х2, . ° Хп) — 1хн .. ° Хм) ~-~ 0(Х1,, ..., хд). Формулы й и Ж называются эквивалентными (обозначение; й = З или й = 22), если на всяком наборе (О1, Ог, ... ..., О„) значений пероменных х1, хз, ..., х„значения функций д2и и д1в, реализуемых соответственно формулами й и З, совпадают, т.е. ц1и(оп,..., о;„) = ~р~(О1,, ..., Оз).

Пусть Ф множество функциональных символов или логических связок, а Р множество соответствующих им функций. Суперпозицией над,инооквством Р называется всякая функция Е, которую можно реализовать формулой над множеством Ф. Пусть й = й[~~"'1,..., ~~"'1) и 22 = З~д~п'1, ..., д~"'1). Говорят, что формулы й и З имеют одинаковое строение, если формула й может быть получена из формулы З путем замены каждого вхождения функционального символа д, * на символ (1 = 1, ..., в). Строение формулы отражает индуктивный процесс ее порождения в соответствии с определением формулы (см. определения 1 и 2).

Строение формулы можно естественным образом характеризовать диаграммой (специальным графом, являющимся обычно ориентированным графом), вершинам которой приписаны функциональные символы (или логические связки) и символы переменных. Например, если формулы й у(21( (21( й~11( )) 121(( Й ) ф(01)) щ ~ (01 с — д~ 1(х, х), З вЂ” 1"1 1(1о~ ~1(АХ Ч у) 1В 2), у, й1 1(х Й 2)) рассматриваются над некоторым множеством Ф, содержащим логические связки Й, М, ~3 и функциональные символы ~~~1, д1~1, пр1, д11~1 и фу1щ1 (и, возможно, что-то еще), то их строение описывается диаграммами, изображенными на рис. 1.2.

у д Функции алгебры логики. Оиерацин суиериозиции 15 у<2) 12) А, Рис. 1.2 Если нужно обратить внимание именно на строение формулы 21 = = 2[11, ..., Я, то используют запись Ж = С[21, ..., Я. 2. Элементы булева куба. Первичные представления о булевых функциях. Пример 1. Найти номер двоичного набора зо раз т раз т раз Решение. Плина данного набора равна Зт+ 1, а его 1-я компонента равна 1 при 1 = 1, ..., т, пз + 2, ..., 2ьч + 1 и равна 0 в противном случае. Следовательно, З З-1 зо 2т-~-1 ~, ' 2з з-1 — зо ~ 22 з-1 — 1+ ~~, 2з з-1 — 1 з=1 з.=1 У=за-~-2 22елз. 1 [2ззз 1) + 2ы [2ы 1) 2оз [22оз 1-1 2оз 1) Пример 2. Найти двоичный набор, являющийся разложением числа 325 (первая слева цифра в наборе должна быть равна 1).

и Решение. Так как р(Н) = 2 оз 2" ', то для нахождения ком- з=1 понент набора а, имеющего номер р(а), можно применить процедуру «последовательного деления с остатком на число 2»: а) ДЕЛИМ у[а) На 2, ОетатОК ЕетЬ аа, а ЧаСтНОЕ З11 = а1 2" 2+... ... + 11, — 2 2+ аи 1,.

б) частное д1 делим на 2з остаток равен ао 1, частное 112 = = а1 2и + ... + а„ з делим на 2, остаток равен а„ 2 и т.д. 16 Гл. 1. Способы задания и сводсзпва узуикиий алгебры логики до тех пор, пока на некотором ((и — 1)-м) шаге нс получим частное уи 1 — — о1 и остаток оз. В нашем случае р(Н) = 325. Используем описанную процедуру: 1) делим 325 на 2, находим частное 91 и остаток о„; 91 — — 162, ои = 1: 2) делим 162 на 2, частное равно 81, в остатке О, т.

е, ои 1 — — О, 92 =81; 3) делим 81 на 2, за = 40, оо 2 = 1; 4)делим40на2, 94=20, ои з=О; 5) делим 20 на 2, 93 —— 10, ои 4 = 0; 6)делим10на2, с73=5, ои;=0; 7) делим 5 на 2, с12 = 2з ои — в 1; 8) делим 2 на 2, частное равно 1, в остатке О, т.е, о„г — — 0 и оа 3=аз — — 1. Следовательно, и = 9 и Н = (1з Оз 1, О, О, О, 1, О, 1). зз Замеч анно. Из формулы р(Н) = 2 оз 2" ' видно, что для з=1 получения координаты о, набора Н можно поступать следующим образом: а) используя неравенство 2" 1 < р(Н) < 2",находим и; б) делим р(сз) на 2" 141 и получаем остаток и, = о,.2" ' + + о,41 . 2" ' 1 +...

+ ои 1 2+ ои; в) делим р(Н) на 2"' 1 и получаем остаток г,.е1 = о,4.1 2" ' 1 4-... ..,+пи 1 2+па; г) вычисляем разность т, — гзл 1 и делим ее на 2" Полученное частное и есть значение координаты оо Например, если р(о) = 325 и нужно найти оз (см. пример 2), то имеем; а)2и 1(325<2",значит, п=9,таккак 2 =256<325<2 = 512; б) делим 325 на 23 за1 = 22 = 128, получаем остаток, равный 69; в) делим 325 на 2о 3 = 23 = 64 и получаем в остатке 5; г) гз — гз — — 64, и поэтому оз = 64/64 = 1. Пример 3. Найти двоичный набор длины т, являющийся разложением числа 2'" 1 — 2 (т ) 3).

Решение. Представим число 2и' 1 — 2 в виде суммы степеней двойки: 2т — 1 2 2с2из — 2 ц 212зи — 3+2т — 4+ +2+1) -2+2 — з+ +22+2 Значит, соответствующий числу 2 1 — 2 двоичный набор длины т таков: (01 ... 10). ш — 2 раз Пример 4. На множестве наборов и — 2 раз и — 3 раз и — 3 раз и — 3 раз и — 3 раз у 1.

Функции алгебры логики. Операция еуперпозиции 17 где т! > 3, указать естественный частичный порядок 4 и выяснить, имеются ли в этом множестве соседние и противоположные наборы. Решение. Решая данную задачу, удобно просматривать наборы в порядке возрастания (или убывания) их весов, т.е. начинать с наборов меньшего (или большего) веса и переходить последовательно к наборам с ббльшим (соответственно с меньшим) весом. Сначала рассмотрим случай п = 3. Множество А состоит из следующих наборов: (ООЦ, (100), (11Цз (01Ц, (000). Очевидно, что (000) 4 (ООЦ 4 (01Ц 4 (!1Ц н (000) 4 (100) 4 (11Ц.

Соседними являются наборы (000) и (ООЦ, (000) и (100), (ООЦ и (01Ц, (01Ц н (111). Пары противоположных наборов таковы; (000) и (11Ц, (100) и (01Ц. Пусть теперь п = 4. Тогда множество А выглядит так; ((ООП), (1010), (101Ц, (010Ц, (0010)). Имеем (0010) 4 (001Ц 4 (101Ц и (0010) 4 (1010); набор (010Ц не сравним ни с одним нз остальных наборов. Соседними являкется наборы (0010) и (001Ц, (0010) и (1010), (001Ц и (101Ц.

Противоположных наборов только два: (010Ц и (1010). Предположим, что п > 5. Тогда А = ((00111... Ц з (1011... 10), (100... 01Ц, (0100... ОЦ з (0011... 10) ), ! раз ! раз 1 раз ! раз ! раз где 1 = и — 4 > 1. Обозначим эти наборы (в соответствии с порядком, в котором они выписаны выше) через Н!, ейз, аз, аа и ае. Возьмем набор а4 = (0100...0Ц (его вес равен 2) и посмотрим, сравним ли ! раз он с каким-либо другим набором. Так как у всех остальных наборов вторые компоненты нулевые, а веса не меньше 2, то они не могут быть сравнимы с набором а4. Затем переходим к набору аз сравниваем его с наборами Н„аз и аз. Нетрудно заметить, что начальные отрезки длины 3 наборов а! и аз, а также наборов аз и оз не сравнимы.

Значит, набор аз не сравним ни с аз, ни с аз. Далее, рассматривая третьи и последние компоненты наборов аз и Йз, видим, что эти наборы тоже не сравнимы. Берем теперь набор а! и сравниваем его с наборами аз и ае, Очевидно, что ае 4 аз, но а! и аз несравнимые наборы (достаточно обратить внимание на первые и последние компоненты этих двух наборов). Наконец, легко видеть, что Не 4 аз.

Итак, имеем ое 4 а! и ае 4 аз. Соседними являются наборы а! и ае, а также аз и ае. Противоположных наборов два. оз и о4. Пример 5. Найти формулу для числа наборов аа из В", удовлетворяющих условию р(а "з 11а) = [(и+ Ц,!2[ и р(ех", уа) < [ге!!2[, где !1" и 7" фиксированные наборы и р()1", ул) = [ге!!2[+ 1. Решение. Не ограничивая общности рассуждений, можно считать, что Д" = 0" и у" = (1 ... 10...0).

Пусть аа такой набор, ~ и / 2~ -!- ! раз что Р(етл,Оа) = [(и+ Ц/2[ и Р(Н"'з У") < [в[2[. ПРедположим, что 2 Г.П. Гаврилов, А.А. Сапозкепко 18 Га, 1. Способы задавая и своде[пва д[упкиий аагебры логики сРсди псРвых его [пс[2) + 1 компонент Ровно 1 единичных [1 > 1). Тогда из остальных и — [пс[2] — 1 компонент единичными будут [[и+ 1) [[2) — 1 штук. Следовательно, при фиксированном о набор Нп сс [и/2) + 11 [с и, — [сс/2) — 1 1 можно выбрать [ .

) [ . [ способами, но при этом должновыполнятьсяусловие р[сг", 7") = [в[[2) + 1 — в'+ [[и+ 1)1[2)— — 1 ( [гс/2), т.е. 2з > [[и+ 1)С2) + 1. Таким образом, искомое число наборов равно [[ [г[+ 1) [ — [ [2[ — ! ) Г".'1-'"--.'(-"Г "1) В частности, при и = 1 имеем 2 (.) ( .) = 1 [если Д~ = О 1>о>1 1 — 1 то 7з = 1з и Нг = 7з), анри и = 2 получаем 2 (.) (1 .) = 2 сйг>з [если Дг = О, то 7~ = 1 и Нз = [01) и [10)). Здесь полагаем, как обычно, (~) = 1. П р и м е р 6. Найти число функций, зависящих от перемен- ных ты ха, ..., то, [т.е. принадлежащих множеству Рз[Х")) и удов- летворяющих условию: функция Дт") равна О на каждом наборе Н", вес которого не превосходит сз[2, а на всех остальных наборах значе- ния функции произвольные [и > 1).