А.А. Вороненко - Решение избранных задач по курсу дискретной математики (1115192), страница 2
Текст из файла (страница 2)
П-й способ: Разобьем вектор ау на две равные цо числу компонент части: % = ЯурЯу1), 1 = хь(о Ч Х1Л. ау, = съ = (0110 1001), так что Д = уь переменная хз фиктивна и У(хьхзрхз,х4) = Яхзрхз,Х4). Повторив процедуру для 4зуц, получим пару противоположных векторов ау = (0110) и ау»1 = (1001), так что переменная хз —. существенная, Яхз,хзцх4) = хз 4Э уоо(хз,х4). Функция 1оо(хз, Х4) имеет вектор значений ау„, = (0110) и потому является суммой по шос) 2 переменных хз и Х4 — линейной функцией, так что окончательно Дх11 тз, хз, х4) = хз к~ хз 9 Х4 линейная функция. и' П.3,2(11). Выяснить, является ли линейной функция с вектором значений ау = (1010 0101 1001 1100). М Предположим, что функция у линейна. Тогда переменная х| фиктивная, так как )'(0,0,0, 0) = у(1,0, О, 0).
Но тогда должны совпэдать и, например, ДО, 1,0,0) и у(1, 1,0,0), что не соблюдается. Пришли к противоречию, следовательно, предположение о том, что ~ — линейная функция неверно, то есть (' — нелинейна. П.З.З(4). Заменить в векторе а = (-001 — -1 — ) прочерки символами 0 и 1 так, чтобы получился вектор значений некоторой линейной функции 1. Выразить у' полиномом. ~ 1) В силу линейности, значения функции на наборах, различающихся значением только одной существенной переменной должны быть различными. Так как 1'(О, 1, 0) ф 7(0,1, 1), то переменная хз существенная, следовательно, у (О, О, О) = 1, у (1, 1, 1) = О.
Так как 1(О, 1, 1) ф у(1, 1» 1), то переменнэя х1 существенная, следовательно, вектор значения функции а = (1001 0110), 2) Функция ~ линейна» фиктивных переменных нет, ~(0,0,0) = 1, следовательно г" = хя (Э хг Ь хз Ю 1. Занятие №4 ЗАМКНУТЫЕ КЛАССЫ П.1.9(1,2,5,6). Выяснить, является ли множество А замкнутым клас- сом. Предполагается, что вместе с каждой функцией 1 из А множеству А принадлежат и все функции из Рг, конгруэнтные 1": 1.
А=(О,Ц; 2. А=(х); 5. А =- (хя ... х„, п = 1,2,...), б. А = (хя 9... Ж х„, п = 1, 2„...). 1. Множество А = (0,1) является замкнутым, так как замыканием множества является само множество, т.е. суперпозициями функций тождественный нуль и тождественная единица являются функции, тождественно равные нулю и единице; 2. Множество А = (х1 не замкнуто, так как суперпозиция функций х и х есть функция (х) = х, не принадлежащая множеству А; 5. Множество А = (хя ...
х„,п = 1,2,...) является замкнутым, так как при суперпозиции функций из А получаем функцию из А. Действительно при подстановке вместо любого хо1 б М, 1 < 12 г < и функции из А мы лишь заменяем этот множитель на группу множителей, а после замены всех произведений вида хя . хь па хь получим функцию из А; б. Множество А = (хя ... х„, и = 1,2,...) не замкнуто, так как при суперпозиции хя 9 хг и хя получим хя 9 хя = Π— функцию, нс принадлежащую множеству А. 9 11.1.13(1,3). Выяснить какое нз отношений С, », =, выполняется для множеств Кы Кг из Рг (отношение означает, что не выполнено ни одно из отношений С»», =): 1.
Кя = [А, Г~ А,], К, = [А,] д [А,]; 3. К1 = [Ая О (Аг П Аз~], Кг = [Ая О Аг] П [Ая О Аз]. ° 1, Так как А| ПАг С Аь то [Ая г 1Аг]».. [Ая]. Аналогично [Ая йАг] С [Аг]. Откуда следует, что [Ая П Аг] С [Аг] О [Аг]. 3. ПеРепишем К1 в виде К1 = [(Ая О Аг) О (Ая Г1 Аз)] и обозначим А~ П Аг = Вы Ая О Аз = Вг. При этом Кя = [Вя П Вг],Кг =- [Вя] О [Вг], а из предыдущего пункта получим [Кя]»- [Кг]. )ь 11.4.1(1).
Выяснить, принадлежит ли функция ~ = (хя — хгИхг— хз) (хз -» хя) множеству 71 '~ 7с. М Функция принадлежит множеству Тя»~ Тс, если на единичном и на нулевом наборах она принимает значение 1, г.е. 1(0, О, 0) = ~(1, 1, 1) = 1. Для данной функции У = (Π— » 0)(0-» 0)(0 - 0) = 1 и 7" = (1- 1)(1- 1)(1 » 1), поэтому 1" Е Т1 я, 7с. в П.2.1(1,12). Вьшснитть является лн функция 7" самодвойственной: 1. ~ = х,хг Чхгхз »» хзхя, 12, ~ = х1 хгхз Я~ х1 хг 9 хгхз 63 хзхь 1. Функция является самодвойствеппой, так как по принципу двойственности,~ = (хя У хг)(хг У хз)(хз Ч хя) = г . 12. Функция не является самодвойственной, так как она отличается от самодвойственной функции хяхг Ф хгхз 9 хзхя только на наборе (111), так что вектор ее значений содержит нечетное число единиц, Замечание для последующих задач: для самодвойственных функций, задаваемых вектором ау = (сяс» сяы..., сгг я) должно выполняться следующее условно: сгу '= (сяс»ся1»»пг" '-ысяг" '-1>»~я»»яо) (*) 11.2.2(3,11).
Выяснить, является ли самодвойственпой функция у, заданная векторно: 3. ау = (1001 ОПО); П. ау = (ПОО ООП 1010 0101). «2 3. Вектор зпа 1епий функции ау = (0001 ОП1) удовлетворяет условию (*) и позтому функция является самодвойственной П. Функция не является самодвойственной, так как У(0,0,0) = У(1,1, 1) = Х(0,0,0). > П.2,7. Доказать, что не существует самодвойственных функций, существенно зависящих в точности от двух переменных. «$ Количество самодвойсгвенных функций двух переменных равно 22 ' 4 -- это х, р, х, р. Таким образом, не существует самодвойственной функции, существенно зависящей ровно от двух переменных. 11.2.8(2).
Выясш1тгь при каких и > 2 функция 1(х«) = Ч х1х,:. 1<1<за« ° Очевидно, что прн и = 2 функция не является самодвойственной. При и = 3 функция является медианой — самодвойствеппой функцией. При и, > 3 выполнено соотношение 1 (ПОО а»... а„) = ~(ООП аь... а„) = 1, следовательпо» функция пе является самодвойственной, Таким обрезом, только прн и = 3 функция 1'(х") является самодвойственной.
Занятие №5 Кллсс М. Подсчкт числл Функций Эамечание для последующих задач: проверку на монотонность функции 1(х '), заданной своим вектором значений а1 (ас,а1,...,а2» 1), можно осуществить следующим образом. Функция 1 монотонна тогда и только тогда, когда она монотонна на каждой паре соседних наборов. 11,5.1(1,3,8). По вектору значений ау выяснить, является лп функция у'монотонной: 1. ау = (ОПО); 3. ау = (0101 ОП1); 8. ау = (0001 0101 ОП1 ОП1). 1, Монотонность нарушается на наборах (10) и (П), 3,5.
Следуя алгоритму проверки из замечания, получим, что функция является монотонной. П.5.2(3). Проверить, является ли функция Г" = х1 - (х1 - хв) монотонной. ° В Функция не является монотонной, так как )'(О,х2) = 1„ а ((1, х2) = Х2 11.5.4(б), Пусть ̄— множество тех векторов а = (ас, а1,..., а2. 1), которые являются векторами значений монотонной фу1п1цин. Найти чис- ло векторов из М„, которые можно получить из вектора уа = ( — — — 1 — -Π— ) заменой символа — на 0 нли 1, ° в В силу монотонности у(1» 1, 1) = 1, ДО, О, О) = 1(О, 1, О) = Д1, О, 0) = О, так что вектор значений должен иметь вид (Π— 01 0-01). При доопределении функции на оставшихся двух наборах возможны три варианта: (0001 0001), (0001 0101).
(0101 0101). 11,5,5(4). Пусть Мо„— множество тех векторов а2 = (ас, а1,...,а2 ~), которые являются векторами значений функции из класса М О Я. Най- ти число векторов из МЯ„, которые можно получпть, заменяя в векторе 12 = (-00- 0---) символы — на 0 или 1. ° в Так как функция является самодвойствепной, то вектор значений функции примет вид (-001 ОП вЂ” ). Исходя из монотонности фупкпин, окончательно получим (0001 ОП1), 11,5.21(2,3). Подсчитать число функций в каждом из следующих множеств: 2, М" 1~ (Т1 ПТс)' 3, М" и Ь. 2.
Так как 1(Г') ф Т1 О Тс, то ау может иметь вид (О--...— — 0), (1- —...— — О) или (1 — —...— — 1). Функция монотонна, значит, (1- —... — -0) не подходит. Вектор (О-- ... --0) соответствует единственной монотонной функции 1(х") = О, а вектор (1- — ...
--1) — 1(х") = 1. Получаем, что в множестве М" ~ (Т~ П То) всего 2 функции. 3. Линейная функция, имеющая не менее двух существенных переменных, пе монотонна. Это следует из того, что при подстановке констант вместо остальных переменных получается немонотонная функция у~ Ю уз или у~ 9 уо 9 1 Следовательно, исходному множеству принадлежат всего и+ 2 функции. 11.4.3(1,5,15,30). Подсчитать число функций, зависящих от перемен- ных хм хо,..., х„и принадлежащих множеству А: 1. А = ТойТ~., 5. А=То0Х; 15 А = (То ~ Т~) П о; ЗО. А=(Х~(Тоит))Г~Я.
1. Вектор значений функции Х Е А = То йТ~ имеет вид (О--... --1). Длина вектора значений функции и переменных равна 2". В нашем случае 2 элемента вектора значений уже известны, значит, доопределить вектор значений функции можно 2~ о способами. 5 !А! = !То!+ !Х !- !ТойХ ! !То! = 2о" ' (см. П.5.2ЦЗ)); !Х ! = 2"+', так как лля Х е Х функция имеет вид Х'(х") = ао Ы агх~ Ю... 9 а„х„, и количество функций в Х такое, сколькими способами можно выбрать различные наборы (ао,ам...,а„); !То П Х! = 2", так как ,Х б То, то Х(0, О,..., 0) =- 0 =ь ао =- О, а значит, остается выбрать и значений ам..., а„, а зто можно сделать 2" способами.
В итоге получим !А! =. 2о" '+ 2"+' — 2" = 2з" '+ 2" 15. Таккак Х 6 То,то Х(0,0...,,0) =О.ТаккакХ ф Тын Х(1,1,...,1) = О. Но тогда У(0,0,..., 0) = Х(0,0,..., 0), а следовательно, функция не является самодвойственной. Значит,множество А пустое. ЗО. Е Лх") ФТо ОТ~ Х(р~) Х =о,Х(х ) = 1 ~ а~хг 9 ° ° 9 аох аХ = (1 — —...--0) =о количество существенных переменных нечетно. Докажем, что такая функция Х(х") е Б. Пусть Х = 1 9 уо 61... 9 уь,+ь Непосредственной проверкой убеждаемся, что Х' = Х. Среди наборов козффициептов ам..., а„, находим те, в которых число единиц печетно. Таких наборов ровно половина.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
