Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 3
Текст из файла (страница 3)
Замечание. Аналогично определяется понятие формулы над любым нспустым подмножеством бз множества 9; п. 1) из определения 2 надо оставить неизменным, а и. 2) видоизменить естественным образом: берутся только связки из Ям и формулы й и Й1 должны быть формулами над бм Обычно принимаются следующие соглашения для сокращения записи формул над множеством связок б: а) внешние скобки у формул опускаются; б) формула (1 й) записывается в виде й; в) формула (й ее Цз) записывается в виде (Й 21) или (Й'.о); г) считается, что связка 1 сильнее любой двухместной связки из множества б; д) связка Й считается сильнее, чем любая другая двухместная связка из множества б.
Эти соглазпения позволязот, например, записать формулу ((((1 х) 9 9 у) (е г) -+ Их Й (1 у))у г)) в вице (х 9 у)г — з (ху у з). Употребляется также «смешанная» запись формул, например, х 9 ~У, г) или хзф(хг, О, хз) З хам(х,, хг, 1) Пусть каждому функциональному символу 1~ * из множества Ф = (Гзш, Д "", ... ) сопоставленанекотоРаафУнкциЯ г,: Вп* — Р— р В = (О, 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 Г.П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
