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

2), а затем, подставляя на места соответствующих переменных 0 и 1, получим нужные нам подфункции функции 1'(ха) и сравним их между собой. Сначала воспользуемся эквивалентностями х — 4 у = х Ч у, х = х, х у=хегу и х~гу=хЧу1. Получаем г (Х ) = ((2'1Х2 Ч УЗ) 1Э (Х1У4 Ч Х2ХЗ)) Ч (хг 9 хл) Ч хз Ч х1 Хг Ч (хз чг Х4)) ° Далее применяем эквивалентности хбзу=хуЧйу, хЧу=х р, хсоу=х у=хуЧху, х.у =йЧу, х = х, хц1у = хиз уВ1 = х111у = хуЧху. Это приводит нас к такому соотношенинх 1(х ) = (хгхг Ч хз)х124 Ч хгхз Ч хзхг Ч хз(хгх4 Ч хгхз) Ч Ч (хгхл Ч хгхл)хз Ч хг Ч хг(хзхл Ч хзхл). лак как Х1Х4 Ч Х2ХЗ = Х1Х4 ' У2ХЗ = (У1 Ч Т4) ' (Хг '1 Хз) и Х1хг Ч хз = хзхг хз = (Х1 Ч хг)хз, то из последнего выражения для 1(х 4) после раскрытия скобок получаем формулу х1хг 'Ч х1хгхз Ч х1хгхл Ч х1хгхзхл Ч х1хгхз Ч Ч Х1ХЗ Ч Х2ХЗХ4 Ч Хзхл Ч 21хзх4 Ч Хгхглз Ч хгхгхзх4 Ч Ч х2хз Ч Х2хзх4 Ч х2хзтл х1 Ч 22хзх4 Ч х2хзх4.

С помощью правила поглощения йЧй121 = й эта формула можот быть преобразована к следующему виду: х1 Ч хзх4 Ч 2:гхз Ч хгхзх4 Ч хгхзхл Ч хгхзх4. С использованием эквивалентностей х Ч х = 1 и х 1 = х получаем г (Х ) = Х1 Ч ХЗХ4 Ч Х2ХЗ Ч Х1ХЗХ4 Х2ХЗ(Х4 Х4) = х1 Ч хзх4 Ч х1хзх4 Ч хз(х2 Ч х2) = х1 Ч хзх4 Ч х1узх4 Ч хз. у 1. Функции алгебры логики. Операция суиериаэиции 35 Наконец, применяя еще раз правило поглощения и эквивалентность ХУЧХ =УЧу, имеем 1(х ) =Х1 ЧхзЧХ4. Отсюда сразу следует, что переменная хг фиктивная. Далее, так как 1(0, О, 1, Ц = О, а 2'(1, О, 1, 0) = г'(О, О, О., Ц = 2'(О, О, 1, 0) = 1, то остальные три переменные у функции 1(х~) существенные. П р и м е р 15. Выяснить, можно ли, отождествляя и переименовывая переменные в функции ((х~) = (Х1 Чхг Чхз)У4Ч хгхгх4, получить функцию д1(Х1, хг) = х1 Ч хг или функцию дг(Х1, хг) = х1 ~ хг.

Решение. Легко заметить, что у(0) = 1 и 4"(Ц = О. Следовательно, всякая функция, которая получается из функции 1(х ) путем отождествления и переименования переменных, на нулевом наборе равна 1, а на единичном О. В то же время функция д1(х ) этому условик1 не удовлетворяет (д1(0, 0) = 0 и д1(1, Ц = Ц. Значит, функцию д1 из функции 1 описанным выше способом построить нельзя.

Далее, хотя функция дг на 0 равна 1 и на 1 равна О, отсюда еще не следует, что ее можно получить из функции 1, отождествляя и переименовывая переменные. Чтобы выяснить, получается или нет указанным способом из функции 1 функция дг, можно, естественно, перебрать все возможности построения из функции 1 двуместных функций (с помощью отождествления н переименования переменных) и сравнить полученные функции с функцией дг.

При этом нужно будет рассмотреть семь вариантов: Ц х1 = хг = хз = х, х4 = У; 2) хг=хг=хл=х, хз=у; 3) хг=хз=хл=х, хг=у; 4) хг= Хз Х4 х~ Х1 У '1) х! Х2 Х1 Хз Х4 У~ б) Х1 Хз хг х4 У 7) х1 х4 х хг хз У. Такая процедура несколько утомительна. Можно поступить иначе. Предположим, что функцию дг указанным путем из функции 1 построить можно.

Из соотношений дг(0, Ц = дг(1, 0) = 1 следует, что должна существовать пара противоположных наборов Й = (а1, аг, аз ал) и 14 = (о1, 412, аз, ол), на которых функция 1 обращается в 1, т.е. функция Зг(хг хг, хз, х4) = ((Х1; хг: хз, Х4) Йу(хг, хг, хз Х4) не должна быть равна О. Тот набор (любой), на котором функция уг(хл) равна 1 (если уг ф и: 0), и определит соответствующее отождествление переменных. Имеем з'(ХХ ) = ((Х1 Ч Х2 Хз)Х4 Ч Х1Х2Х4) ' ((Х1 1 Х2 Хз)Х4 Ч Х1112Х4) = хз хгх4(х1 Ч хг Ч хз) Ч хгхгх4(У1 Ч хг Ч хз) = Х1 хгх4 Ч хгхгх4. Очевидно, что 42(х4) равна 1 только на наборах (1, 1, О, 0), (1, 1, 1, 0), (О, О, О., Ц и (О, О, 1, Ц. Взяв, например, набор (1, 1, О, 0), приходим к такому отождествлению; х1 = хг —— х и хз = х4 = у; оно дает 1(х, т, у, у) = (хЧ х Ч у)у Ч х ху = ху Ч уЧ Уу = ХЧ у = х ~ у.

Набор (1, 1, 1, 0) дает отождествление Х1 — — хг = хз = х и хг = у и функцию 2(х, х, х, у) = (х Чх ЧУ) у Чх У у = у ЧУУ = х Чу = х ~ у. 36 Га. 1. Способы задания и свояапва у1упииий ааеебры аоеиии других отождествлений (с точностью до переименования переменных), дающих функцию дг, нет, итак, функцию дг(Х1, хг) из функции 1(х4) с помощью отождествления и переименования переменных получить можно, а именно дг(х1, хг) = 7'(х1, Х1, хг, хг) = 1 (Х1, Х1, У1, Х2). 1.28. Указать все фиктивные переменные функции 1: Ц 1(хз) (10101010). 2) Д(з з) (01100110 3) 1"(Уз) = (11110011) 4) 1(* 4) = (1011010110110101) ос) У(х4) = (010ШП010ПШ); 6) 7(х4) = (П00П0000П00П).

1.29. Показать,. что у1 -- фиктивная переменная функции (реализовав для этой цели функцию 1 формулой, не содержащей явно переменную х1); 1) ~(хг) = (хг «х1) ' (У2 4 х2)~ 2) 1(х ) = (У1 х2) (' 1 ~ 2) 3)1(Х )=((Х11ЭУ2) «ХЗ)'Уз «Х2 4) ~(хз) = (х1 «ухг) — «х1 тз)) ' х1 + (х2 ' хз) 5) 1(х~) = (х1 «ухг . хз) (х1 — «хг . Хз)) . (Хг 4 хз); 6) ~(х~) = ((Х1 «Ухг Ч хз) — «(х1 хг ~ хз)) 6« (х2 -+ х1) хз 7) 1(х ) = (Х1 Ф ((х2 «хз) — «ХЗИ х1 (х2 — «хз) ' х4 8) 1(х~) = (х1 ' хг Ч хз) хг «сх1 ' х4) «(Х1 «(хг «хз)) 0) 1(х ) = (х1хг Ч Узх4) ' (У1 чз х2 из хз) — «х4) Ю «1«(х«хг(хз — «ХЗЬ хзх4), 10) 1(х ) = ((Х1 ~ Х2) ф ((Х1 ф Х4) ~ (ХЗ ф Х4))) ~ (( 1.30.

Перечислить существенные переменные следующих функций: 1) «(Х ) = ((Х1 «схг) + Х1 'Х2) чз (У1 « Х2) ' (Х2 « Х1):, 2) г (х ) = (х1 †« ((хг -+ х1) †« хг)) - (х1 «с хг); 3) Дх ') = (х, Е (х, -+ (х, - х,))) «?х, -« х.; 4) 1(ХУ~) = (Х1 хг 6З(х1 †« хг)) †« (Х1 Х1 хг); 5) 7(х~) = (х1 хг †« (х1 †« хг)) -« Х1 х ; 6) Пх ) = (Х1 †« хг .Хз) (хг †« Х1 хз)«1(У1 хг); 7) Д(х ) = ((х1 †« хг) 6« (хг †« хз)) 6«(хг †« хз); 8) з'(х~) = ((Х1 «Ухг хз) †« (хг -« Х1 хз)) †« (х1 «Ухз); 0) 1'(х ') = ((х 4 (х ~ ' з)) 4 ( ~ (х 4 хз))) 4 (х ~ хг); 10) 1(х ) = (х1 хг ег хз 'ХЗЬ ((Х1'хз хг) « Х4)«Ух1 хз. 1.31. 1) Показать, что если у функции 7'(хо) (и > 1) имеются фиктивные переменные, то она принимает значение 1 на четном числе наборов. 2) Выяснить, верно ли утверждение, обратное к 1).

3) Пусть функция Д(ха) такова, что ~ЗУ1~ = 2 (21 — 1), где т > 0 и 1 > 1. Каково максимально возможное число фиктивных переменных у этой функции? у д Функции алгебрег логики. Оиерацггя еуиериозиции 37 1.32. Пусть функция 7(хп) задана вектором оу = (оо, о«г... ..., ог- 1). Локазать, что если хь . фиктивная переменная, то ОЛ = Огп-гю дпя ВСЕХ 1, удОВЛЕтнпряЮщИХ УСЛОВИЮ З. 2" 'Я+~ < 1 < < (2з+ 1) 2и "' — 1г где з = О, 1, ... 21 1 — 1. 1.33. С использованием результатов задач 1.31, 1) и 1.32 выяснить, какие переменные функции 1 являются существенными: 1) 7(х4) = (1001001100ПО010); 2) ((х~) = (01100П10П10110); 3) У(хл) = (ПООООПООППОО); 4) У(Х4) = (000100010ШОШ); 5) 1(ХС~) = (0011110000111100); 6) 1(х~) = (0001100101101по); 7) 1(х~) = (01101101101101П); 8) ((х~) = (000000011П1П10); О) ~(Х4) = (ОП101ШО101010).

1.34. Выяснить, при каких 11, (п > 2) функция ("(хгг) зависит существенно от всех своих переменных: 1) У'(х и) = (х, («х, «7... Ч *,) -« ИХ1 ггХ2) ' (Х2 ггХЗ) ' ° ' (Х вЂ” 1 гг Х ) ' Х ггХ1)); 2) 2 (Х ) = (Х!Х2 г' Х2ХЗ гг ° ° ° г' Хп — 1Хгг у ХиХ1) — «(х«хг (Э хзхз (Э... (Э х «хи (Э хих1)' 3) 7(хп) = ((х1 «7Х2 2..Лхп) — «х1 хг ... хп) -« — «(Х1 гЭ хз гЭ... ЭЗ хгг це 1); 4) «(Т.и) = (Х1 — «(Х2 — « . — «(,Хп — 1 — «Хп) .)) -«(Х1 — «Хп)(Х2 -«Хи)...

(Хи 1 -«Хи); 5) У(хи) = (х ~ хз) Е (хг ~ хз) Э " 6 (хп — ~ х.) Е (х. ~ х ); 6) У(Х ) = (Х1 «Х2)(Х2 «ХЗ) ° ° ° (Хп — 1 «Хп)(Хп «Х1) (Х1 (Э Х2 и« ° ° ° гЭ хгг). 1.35. Булевы функции Дх") (и > 1) и д(у™) (т > 1) существенно зависят от всех своих переменных. Переменные Х1, ..., Х„„у«, ... ..., уп, попарно различные. Показать., что функция 1(д(у«г ..., у ), Хг г ..., Х„) СУЩЕСТВЕННО ЗаВИСИт От ВСЕХ СВОИХ ПЕРЕМЕННЫХ. 1.36. Локазать, что всякая булева симметрическая функция (см.

задачу 1.6, 7)), отличная от константы, существенно зависит от всех своих переменных. 1.37. Пусть п > 1 и функции ахти) и д(хп) таковы, что сумма 2'(хи) (Э д(хи) обращается в 1 на нечетном числе наборов. Доказать, что длЯ всЯкого 1 = 1, ..., п пеРеменнал хг ЯвлЯетсЯ сУществснной хотя бы у одной из функций, 2" или д.

1.38. Через Р" (Х") (и > 1) обозначим множество всех булевых фУНКЦИй, ЗаВИСЯЩИХ От ПЕРЕМЕННЫХ Х1, Хз, ..., Хи И ПРИ ЭТОМ От каждой из них существенным образом. 1) ВЫПИСатЬ ВСЕ фуНКцИИ МНОжЕСтВа Ре(Х2). 2) Найти число элементов множества Р'(Хз). и 3) Локазатьг что ~Р" (Х")) = 2 ( — 1)" („) 22 я=а 4) Показать, что 1пп „= 1. )Р'(Х")) и — гж 22" 38 Гл, 1. Способы задавил и свойапва функций алгебры логики 1.39. Выяснить, можно ли из функции 1, отождествляя и переименовывая в ней переменные, получить функцию д: 1) ((;з) (11001011) (-г) (1011). 2) 1(х ') = (10101100), д(хг) = (1000); 3) 7"(хз) = (00110010), д(хг) = (0110); 4) 1'(х~) = (011011011110001Ц, д(хз) = (01100111); 5) 1(хл) = (1111110100011011), д(хг) = (100Ц; 6) 1 (Х ) Х1Х2 Ч Х1ХЗ Ч Х2ХЗ .У(х ) Х1хг~ 7) 1(х~) = (Х1 ''хг)хз сохгхг, д(хг) = Х1 нхг,' 8) У(х ) = (х1 -+ (хг -+ хз)) -+ (х1 -4 хз), д(хг) = х1 -+ хг,' 9) 1 (Х ) = (Х1Х2 М ХЗХ4) 1 (Х1Х2 е (ХЗ Ч Х4)), д(т ) = х1 — 4 (хг 11 хз); 10) ((х') = (х,х, 11 х,х,) 111(х,,х, 11 х,х,), д(х ') = х, ~ х,.