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

Гаврилов, А.А. Сапозкепко 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. Фуикции алгебры логики. Операция еуиериагиции 19 противоположных наборов); например, если о и В пара противоположных наборов, то либо ДН) = О, а Щ) = 1, либо Д~Н) = 1, а Щ) = О.

Таким образом, каждой паре противоположных наборов соответствуют три допустимые возможности. Остается заметить, что существует 2"?2 = 2" ' пар противоположных наборов длины п, и тогда получаем: число функций в Рз(Х'), не удовлетворяющих описанному выше условию, равно 32 . Следовательно, искомое число 2'* 21 20 функцийесть 22 — Зз . (Например, при и = 1 имеем 22 — 32 = 1, 22 21 а при п = 2 получаем 22 — 32 = 16 — 9 = 7.) Пример 8. По каналу связи могут передаваться три сообщения: А, В и С. Известно, что к данному моменту времени осуществилось каждое из следующих событий: 1) передано не более чем одно из сообщений А и В; 2) сообщение А могло быть передано в том и только том случае, если были переданы оба сообщения В и С; 3) передано хотя бы одно из сообщений А и С.

Вытекает ли отсюда, что сообщение В не передавалось, а сообщение С было передано'? Решение. Сопоста.вим сообщениям А, В и С булевы переменные х, у и 2 соответственно. Считаем, что х = 1 (аналогично у = 1 и 2 = 1) в том и только том случае, если сообщение А (соответственно сообщение В и сообщение С) было передано по каналу связи. Событиям Ц, 2) и 3) отвечают следующие булевы функции: ху, х уг и х Ч г (это надо понимать так: второе событие, например1 осуществляется тогда и только тогда, когда х уг = 1).

Булева функция ?'1х, у, 2)1 соответствующая всем трем событиям, имеет вид ху . (х уг) (х Ч 2). Преобразуем это выражение; )?х, д, 2) = (УЧу) (У узах уг) (х'42) = = (У- уз ЧУ у. уг) х Ч 2) = У (дгЧ2у (у МУ)) 2 = = У . (у 1? У) . 2 = У у . 2. Отсюда следует, что у(х, у, 2) = 1 тогда и только тогда, когда х = О, у = 0 и х = 1, т.е. когда сообщения А и В не передавались, а сообщение С было передано. Таким образом, на вопрос, поставленный в задаче, ответ утвердительный. Последний шаг в решении данной задачи можно расписатыюдробнее: для выяснении того, вытекает ли событие, указанное в вопросе задачи, из осуществимости событий Ц, 2) и 3), надо посмотреть, выполняется ли эквивалентность 2"(х, у, 2) 2 д 2 = 1 (функция у 2 соответствует событии> «сообщение В не передавалось, а сообщение С было передано»).

Имеем У.у 2 — гд.г=У.у гг?у.2=хЧу.гЧд 2=хЧ1= 1, т.е. действительно Дх, у, 2) — > у . 2 = 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 у", Гдс Удп И у" — — дВа фИКСИрОВаННЫХ НабОра И р()д", уп) = 1С (и > и > Ц; 6) число наборов Нп из В" таких, что р(азз, ~3 "з) + р(Н»з, узз) ф ~ р(У» уп) где Уэп, пуп два фикс с '1 ' бо ни (Рп -п) (и >1> Ц,.

у д Функции алгебры логики. Операция гуперпогиции 21 7) число наборов оз'" = (оы ..., оз ) из ВЯ, удовлетворяющих — ~+1 условию: < 2,' о, < для каждого [ = 1,2, ..., 2пп (гл > 1); 8) число наборов Й" в В„",, у которых между любыми единичны- ми компононтами находится нс менее г нулевых компонент (О < г < <и — 2, 2<й<п). 1.5. Показать, что: 1) два различных набора в В", имеющих одинаковый вес, несрав- нимы (и > 2):, 2) в В" существует только два сравнимых противоположных на- бора (и > 1); ( 3) в В" существует множество, состоящее из ( попарно 1,[(п — 1 /2) несравнимых наборов, не сравнимых с набором (10...0) (и > 2); 4) всякое подмножество в В", содержащее не менее и+ 2 наборов, содержит пару несравнимых наборов (и > 2); 5) число наборов в В", не сравнимых с фиксированным набо- ром Н"', имеющим вес й, равно 2" — 2" Я вЂ” 2" +1 (и > 1 и п > > й > 0); 6) если оп и рл -- два несравнимых набора из Ви (и > 2), .имею- щих 1 общих единичных компонент Д > 0), и [[Ни[[ = г, [[В" [[ = г, то число наборов, которые не сравнимы ни с одним из наборов а' и В равно 2" + 2'чг ' '+ 2'+ 2 — 2" ' — 2и ' — 2" — 2' (в частности, ес- ли наборы Йи и До противоположные, то имеем 2' — 2" "г 1 — 2"+з+ 4 наборов).

1.6. Найти число функций в Рз(Х") (т. е. функций, зависящих от переменных ям тз, ..., х„), удовлетворяющих условию: 1) на данных 1 наборах значения функции фиксированы, а на ос- тальных произвольные (1 < 1 < 2" — 1, и > 1); 2) функция Д(йи) равна 1 на всяком наборе о", вес которого удовлетворяет неравенствам (п — 1) /2 < [[а и[[ < и/2, а на остальных наборах значения функции произвольные (и > 2); 3) на противоположных наборах функция принимает одинаковые значения (и > 1); 4) на каждой паре соседних наборов функция принимает противо- положные значения (и > 1); 5) функция равна 0 не менее чем на половине наборов (и > 1); 6) функция ДйР') совпадает с функцией, получаемой из нос при перестановке переменных хз и хз (и > 2); 7) функция 7(йи) симметрическая, т. е.