Задачи И Упражнения По Дискретной Математике, Гаврилов, Сапоженко, страница 4

Пример 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, если лампочка В, горит, и я, = О, если лампочка В, не горит. 5) Лля оценки гипотез Н1 и Нз проводятся пять разнотипных экспериментов: Аы Аз, Аз, Ал, Аз.

Каждый эксперимент упорядочивает гипотезы по предпочтению относительно некоторого признака. Гипотеза Нз принимается только в следующих случаях: а) в большинстве экспериментов предпочтение отдавалось НП б) в экспериментах А1 и Аз предпочтение отдавалось гипотезе Нз, но в эксперименте Ал предпочтение отдано гипотезе Ны Гипотеза Нз принимается в случаях, когда: в) в экспериментах Аз и Аз предпочтение отдавалось ей, а в экспериментах Ас и Ал гипотезе Нп г) в экспериментах Аг и Аз предпочтение отдавалось гипотезе Нз, а в экспериментах Аз и Ал ..

гипотезе Нь Полагаем я, = О, если эксперимент А, «поддерживает» гипотезу Н„и х = 1, если в эксперименте А. предпочтение отдано гипотезе Нз (у = 1, ..., 5). Записать в виде булевых функций ул, (тв) и Гно(ха) условия принятия гипотез Нг и Нз (1д, (сез) = 1) тогда и только тогда, когда по набору Нз принимается гипотеза Н, (1 = 1, 2). Выяснить, возможна ли такая ситуация, когда окажутся принятыми обе гипотезы. 6) Четырем членам Вы Вз, Вз, Вл некоторой комиссии сформулированы следующие условия посещения заседаний (хотя бы одно из них они должны выполнить): а) в заседании не участвует ни Вы ни Вз, но должен быть Вз, б) в заседании принимают участие Вэ и Вл, но отсутствует Вз, .в) на заседании должны присутствовать Вз и В».

у 1. Функции алгебры логики. Операция гуперпогиции 23 Выяснить, обязан ли присутствовать на заседании комиссии член Вз, если в нем не участвует Вз. 7) Проект принимается, если большинство из шести экспертов Сы ..., Св высказалось в его пользу. Кроме того, проект все же принимается, если указанное условие не выполнено, но за, принятие проекта высказались: а) либо эксперты Сы Сз, Сз, б) либо эксперты Сз, Сл, Св, .в) либо эксперты Сы Св, Св. Записать в виде булевой функции «" (о в) условие принятия проекта, считая, что оц = 1 в том случае, когда 1-й эксперт высказывается за принятие проекта, и л; = 0 в противном случае.