Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 8
Текст из файла (страница 8)
Решение. Для решения данной задачи можно действовать так же, как при решении прсдыдущей, т.е. сравнивать значения функции на парах соседних наборов, чтобы выяснить, совпадают или нет соответствующие подфункции функции 1(х~) (ибо переменная х, фиктивна тогда и только тогда, когда Д'(х ) = 11'(х~)). Однако при 3 Г. П. Гаврилов, А. А. Сапожонка 34 Гл, 1.
Способы задавил и свойапва фупкиий алеебры логики задании булевой функции в «аналитической форме» для выяснения того, какие переменные у нее существенные (а какие фиктивные), иногда бывает полезно преобразовать исходное выражение к некоторому специальному виду, например к совершенной диэъюнктивной нормальной форме или полиному Жегалкина (см. з 2, пп. 2 и 3). Оказывается, что переменная х, функции 1 (х") является фиктивной тогда и только тогда, когда; 1) в совершенной д.н.
ф. этой функции вместе с каждой элементарной конъюнкцией вида х, ' К содержится и элементарная конъкгнкция хо'К (см. задачу 2.16) или 2) в полиноме Жегалкина, реализующем эту функцию, переменная хг отсутствует. Для решения сформулированной задачи мы сначала преобразуем (с помощью основных эквивалентностей) исходное аналитическое задание функции 1(х~) к достаточно простой дизъюнктивной нормальной форме (см. э 2,п. 2), а затем, подставляя на места соответствующих переменных 0 и 1, получим нужные нам подфункции функции 1'(ха) и сравним их между собой.
Сначала воспользуемся эквивалентностями х — 4 у = х Ч у, х = х, х у=хегу и х~гу=хЧ11. Получаем г (Х ) = ((2'1Х2 Ч УЗ) 1Э (Х1У4 Ч Х2ХЗ)) Ч (хг 9 хл) Ч хз Ч х1 Хг Ч (хз чг Х4)) ° Далее применяем эквивалентности х 64 у = ху Ч йу, х Ч у = х у, х со гу = х у = ху Ч х у, х.у =йЧд, х = х, хц1р = хиз уВ1 = х111у = хуЧху. Это приводит нас к такому соотношеник1: 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 хг ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
