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

Решение. Число наборов [из Вп), на которых значения функ- ции 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(йи) симметрическая, т.

е. ~(иы хз ..., х„) = = Д(х„, и„..., и,„) при любой подстановке .. ''' ., и > 1; /1 2 ... п1 -)' 8) если функция обращается в 1 на некотором наборе веса й (О < й < и — 1), то она равна 1 и на всяком наборе большего веса (п > 1). 22 Гл, 1. Способы задания и свобства угуикиий алгебры логики 1.7.

1) Булева функция Д(хз) определяется так. Она равна 1 только в тех случаях, когда яз = 1 либо когда выполняется следующее условие: переменные яз и яз принимают разные значения, а значение переменной яс меньше значения переменной яз, в остальных случаях функция обращается в О. Построить таблицы Т(у) и Пз з( г) функции г(хз) и выписать наборы множества Лгу. 2) Булева функция )'(х~) задается следующим образом: она равна О только на таких наборах П = (пы сгз, пз, сел), для которых справедливо неравенство 2оп + скз ) сгз + 2скл, на остальных наборах она обращается в 1.

Построить таблицы Т(() и Пз з® этой функции и выписать наборы множества Яу. 3) Пусть наборы (яы хз) и (хз, ял) задают двоичные разложения чисел ис и из соответственно. Обозначим через (в(хл) 1-й разряд двоичного РазложениЯ (уз, ~с) числа ~ос — оз1 1 = 1, 2. ПостРоить прямоугольные таблицы Пз з функций ул(й ) и гз(й ). 4) Па аварийном пульте системы расположены четыре сигнальные лампочки: Вы Лз, Лз, Л4.

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