Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 4
Текст из файла (страница 4)
Функции алгебры логики. Операция еуперпозиции 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). Решение. Число наборов [из Вп), на которых значения функ- ции 1 зафиксированы, равно 2" если и нечетное, [)(2"'+ — [), На каждом из остальных наборов значение функции 7' можно задавать произвольно [полагая его равным О или 1). Следовательно, число различных функций, удовлетворякгщих сформулированному вы— 1 2" — з[ ".) ше условию, равно 2г при и нечетном и 2 '[" м) при п четном.
Пример 7. Найти число функций в Рг[Хи), удовлетворяющих условию: существует пара противоположных наборов, на которых функция 1" обращается в 1 [для разных функций 1" такие пары наборов могут не совпадать). Решение. При решении данной задачи проще поступить сле- дующим образом: подсчитать число функций в Рг[Хо), но удовлетво- ряюгцих сформулированному условию, а затем вычесть полученное число из [Рз[Хп)[ = 2з . Функция г[т") не удовлетворяет указанно- му выше условию, если, какова бы ни была пара противоположных наборов, функция 7'[тЗп) на них либо принимает разные значения, либо обращается в О.
Причем в том случае, когда соответствующие значения разные, надо различать две возможности [для каждой пары у 1. Функции алгебры логики. Оиера2еин еупериоэиции 19 противоположных наборов); например, если а и В пара противоположных наборов, то либо ДН) = О, а Щ) = 1, либо Д~а) = 1, а Щ) = О. Таким образом, каждой паре противоположных наборов соответствуют три дог2устимые возможности.
Остается заметить, что существует 2"?2 = 2" ' пар противоположных наборов длины и, И тОГДа ПОЛУЧаЕМ: ЧИСЛО фУНКЦИй В Рг(Хо), НЕ УДОВЛЕТВОРЯЮЩИХ описанному выше условию, равно 32 . Следовательно, искомое число 2'* 21 20 функцийесть 22 — Зг . (Например, при и = 1 имеем 22 — 32 = 1, 22 21 а при и = 2 получаем 22 — 32 = 16 — 9 = 7.) Пример 8. По каналу связи могут передаваться три сообщения: А, В и С.
Известно, что к данному моменту времени осуществилось каждое из следующих событий: 1) передано не более чем одно из сообщений А и В; 2) сообщение А могло быть передано в том и только том случае, если были переданы оба сообщения В и С; 3) передано хотя бы одно из сообщений А и С. Вытекает ли отсюда, что сообщение В не передавалось, а сообщение С было передано'? Решение.
Сопоставим сообщениям А, В и С булевы переменные х, у и г соответственно. Считаем, что х = 1 (аналогично у = 1 и г = 1) в том и только том случае, если сообщение А (соответственно сообщение В и сообщение С) было передано по каналу связи. Событиям Ц, 2) и 3) отвечают следующие булевы функции: ху, х уг и х2?г (это надо понимать так: второе событие, например1 осуществляется тогда и только тогда, когда х уг = 1). Булева функция ?'1х, у, г)1 соответствующая всем трем событиям, имеет вид ху. (х уг) (х 2? 2).
Преобразуем это выражение; )?х, у, г) = (У2? у) (У уг'2? х уг) (х'4г) = = (У- уз 2?У у. уг) х 2?2) = У (ух 2? у (у 2?У)) г = = У . (у 2? У) . г = У у . г. Отсюда следует, что у(х, у, г) = 1 тогда и только тогда, когда х = О, у = 0 и г = 1, т.е. когда сообщения А и В не передавались, а сообщение С было передано. Таким образом, на вопрос, поставленный в задаче, ответ утвердительный. Последний шаг в решении данной задачи можно рас22исатыюдробнее: для выяснения того, вытекает ли событие, указанное в вопросе задачи, из осуществимости событий Ц, 2) и 3), надо посмотреть, выполняется ли эквивалентность 2"(х, у, г) — е у г = 1 (функция у г соответствует событик2 «сообщение В не передавалось, а сообщение С было передано»). Имеем У.у г — гу.г=У.у гг?у.2=х'2еу.г2?у 2=х2?1=1, т.е. действительно Дх, у, г) — > у .
г = 1. 3 а м е ч а н и е. Преобразовывая выражения, задающие булевы функции, мы использовали основные эквивалентности алгебры логики (см. и. 3 после задачи 1.20). 20 Гл. й Способы задания и свойства фуикций алгебры логики 1.1. Найти номера следующих двоичных наборов: Ц (101Ц; 2) (1100Ц; 3) (1100110Ц; 4) (01011110Ц; 5) (10. ОЦ, т > 1; т раз 2т ра» зи раз т раз пэ раэ 1.2.
Найти двоичный набор длины 1, являющийся разложением числа пл Ц1=5, и=28; 2)1=8, и=231; 3) 1 = т + 1, п = 2т + 1 (т > Ц; 4) 1 = т, и = 3 2"' 2 — 1 (т > 2). 1.3. На множестве наборов А из В" указать естественный час- тичный порядок 4. Выяснить, .есть ли в множестве А соседние и противоположные наборы, и, если они имеются, выписать их: Ц А = ((0011Ц, (0101Ц, (00110), (10110), (11010), (01010), (11100), (1101Ц); 2) А = ((01010Ц, (11001Ц, (10110Ц, (01011Ц, (11011Ц, (101010), (100010)); и -2 раз и-2 ра» п — З раэ и — 1 раз и — 2 раз (01...10Ц), п>4; т — 1 раз и — т раз т — 2 ра» и — т — 1 раз 1и раз и — т — 1 раз п — т — 1 раз т — 2 ра» т раз и — т — 2 раз и — т раз т — 1 раз 1.4.
Найти: Ц число ~Ви~ наборов оп веса й (и > 1, и > и > О); 2) число наборов о" из В", удовлетворяющих условию 2" 1 ( ,(„и) ~2п ( 3) число упорядоченных пар соседних наборов в В" (и > Ц; 4) число упорядоченных пар (Н"', Д") наборов из В" таких, что р(Н", у»и) т к (и > й > Ц; 5) число наборов Н" из В", удовлетворяющих условию,9'" 4 Нп 4 4 у", где Удп и у" — — два фиксированных набора и р(У»", уп) = Ус (и > и > Ц; 6) число наборов Нп из В" таких, что р(аи, У)и) + р(Нп, уи) ~ (Удп,уи), Зп И, п,сф . 1,1, бО а фи узз) (и >1> Ц, у д Функции алгебры логики. Операция гуперпогиции 21 7) число наборов оз'" = (оы ..., оз ) из ВЯ, удовлетворяющих — ~+1 условию: < 2,' о, < для каждого [ = 1,2, ..., 2пп (гл > 1); 8) число наборов Й" в В„",, у которых между любыми единичны- ми компононтами находится нс менее г нулевых компонент (О < г < <и — 2, 2<й<п).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
