А.А. Вороненко, В.С. Федорова - Дискретная математика. Задачи и упражнения с решениями (1060726), страница 2
Текст из файла (страница 2)
Построить СФЭ для функции из номера I.1.17(1) с уменьшением числа элементов:((x → y) ∨ (x ⊕ z)) · (y | z).J Упростим формулу:((x → y) ∨ (x ⊕ z)) · (y | z) == ((x ∨ y) ∨ xz ∨ xz) · (y ∨ z) == (x ∨ y ∨ z) · (y ∨ z) == y ∨ z = y & z.Строим схему из функциональных элементов:8xyz&¬fIЗадание. Построить СФЭ для функции из номера I.2.3(3) с уменьшением числа элементов:f (x, y, z) = (0101 0001).Jf (x, y, z) ====x·y·z∨x·y·z∨x·y·z =x·y·z∨y·z =z · (y ∨ x · y) =z · (y ∨ x).Строим схему из функциональных элементов:IЗанятие № 1.3Полиномы и линейные функцииI.2.22(5). Методом неопределённых коэффициентов найти полиномЖегалкина для функции f (ex3 ) = (0110 1001).9J Для функции трёх переменных полином Жегалкина имеет вид:α ⊕ β1 x1 ⊕ β2 x2 ⊕ β3 x3 ⊕ γ1 x1 x2 ⊕ γ2 x1 x3 ⊕ γ3 x2 x3 ⊕ δx1 x2 x3 .Составим систему:x100001111x200110011x301010101f0 = α,1 = α ⊕ β3 ,1 = α ⊕ β2 ,0 = α ⊕ β2 ⊕ β3 ⊕ γ3 ,1 = α ⊕ β1 ,0 = α ⊕ β1 ⊕ β3 ⊕ γ2 ,0 = α ⊕ β1 ⊕ β2 ⊕ γ1 ,1 = α ⊕ β1 ⊕ β2 ⊕ β3 ⊕ γ1 ⊕ γ2 ⊕ γ3 ⊕ δОтсюда получим коэффициенты полинома Жегалкина:α = 0, β1 = 1, β2 = 1, β3 = 1, γ1 = 0, γ2 = 0, γ3 = 0, δ = 0.Полином Жегалкина исходной функции имеет вид f = x1 ⊕x2 ⊕x3 .
II.2.23(7). Преобразуя вектор значений функцииf (ex4 ) = (0000 0100 0110 0111),построить полином Жегалкина для этой функции.J Будем преобразовывать вектор значений функции с помощью определённой по индукции операции T (подробнее см. [2, с. 53]):— Если n = 1 и αe = (α0 , α1 ), то T (eα) = (α0 , α0 ⊕ α1 ).— Предположим, что операция T уже определена для каждого векnn+1тора σe из B 2 , и рассмотрим произвольный вектор αe из B 2 .Пусть αe = (β0 , β1 , . .
. , β2n −1 , γ0 , γ1 , . . . , γ2n −1 ) иT (β0 , β1 , . . . , β2n −1 ) = (δ0 , δ1 , . . . , δ2n −1 ),T (γ0 , γ1 , . . . , γ2n −1 ) = (ε0 , ε1 , . . . , ε2n −1 )(δi и εj по индуктивному предположению известны). ТогдаT (eα) = (δ0 , δ1 , . . . , δ2n −1 , δ0 ⊕ ε0 , δ1 ⊕ ε1 , . . . , δ2n −1 ⊕ ε2n −1 ).10В процессе преобразований получаются векторы:(0000 0100 0110 0111),(0000 0100 0111 0110),(0000 0101 0110 0111),(0000 0101 0110 0001),(0000 0101 0110 0100).Получили вектор коэффициентов полинома Жегалкина:βef = (0000 0101 0110 0100).Таким образом,f = x2 x4 ⊕ x2 x3 x4 ⊕ x1 x4 ⊕ x1 x3 ⊕ x1 x2 x4 .II.2.28. Найти функцию f (exn ), у которой длина полинома Жегалкинав 2n раз превосходит длину её совершенной ДНФ (n > 1).J Так как длина полинома не превосходит 2n , то длина совершеннойДНФ не превосходит 1.
Значит, длина полинома — 2n , а вектор коэффициентов полинома βef = (1111.{z. . 1111}). Такой вектор соответствует|2nфункции f = (x1 ⊕ 1) · . . . · (xn ⊕ 1) = x1 · . . . · xn .III.3.1(6). Представив функцию f = ((x → y)(y → x)) ∼ z полиномом,выяснить, является ли она линейной.J Преобразуем функцию f :f ====((x → y)(y → x)) ∼ z =((x ∨ y)(y ∨ x)) ∼ z =(x ∼ y) ∼ z =x ⊕ y ⊕ z.Следовательно, функция f линейна.III.3.7. 1) Показать, что если функцию f (exn ) можно представить ввиде f (exn ) = xn ⊕ ϕ, где ϕ не зависит от xn , то |Nf | = 2n−1 .2) Показать, что если f линейна и отлична от константы, то |Nf | =n−12 .J 1) При фиксированных x1 , . .
. , xn−1 функция xn ⊕ ϕ принимает значение 1 ровно для одного значения xn . Следовательно, |Nf | = 2n−1 .2) Так как функция f линейна и отлична от константы, то можно выделить слагаемое xk . Оставшаяся часть не зависит от xk , следовательно,11можно воспользоваться фактом, доказанным в предыдущем пункте. Таким образом, |Nf | = 2n−1 .III.3.2(10). Выяснить, является ли линейной функция с вектором значений αef = (0110 1001 0110 1001).J I-й способ: Найдем вектор βef коэффициентов полинома Жегалкина для функции f . Получим βef = (0110 1000 0000 0000). Отличны отнуля лишь компоненты β1 , β2 , β4 с номерами, являющимися степенямидвойки. Следовательно, функция линейна.II-й способ: Разобьём вектор αef на две равные по числу компонентчасти:αef = (eαf0 , αef1 ), f = x1 f0 ∨ x1 f1 .αef0 = αef1 = (0110 1001), так что f0 ≡ f1 , переменная x1 фиктивна иf (x1 , x2 , x3 , x4 ) = f0 (x2 , x3 , x4 ).
Повторив процедуру для αef0 , получимпару противоположных векторов αef00 = (0110) и αef01 = (1001), так чтопеременная x2 — существенная, f0 (x2 , x3 , x4 ) = x2 ⊕ f00 (x3 , x4 ). Функцияf00 (x3 , x4 ) имеет вектор значений αef00 = (0110) и потому является суммой по модулю два переменных x3 и x4 — линейной функцией, так чтоокончательно f (x1 , x2 , x3 , x4 ) = x2 ⊕ x3 ⊕ x4 — линейная функция.III.3.2(11). Выяснить, является ли линейной функция с вектором значений αef = (1010 0101 1001 1100).J Предположим, что функция f линейна.
Тогда переменная x1 фиктивная, так как f (0, 0, 0, 0) = f (1, 0, 0, 0). Но тогда должны совпадатьи, например, f (0, 1, 0, 0) и f (1, 1, 0, 0), что не соблюдается. Пришли кпротиворечию, следовательно, предположение о том, что f — линейнаяфункция, неверно, то есть f нелинейна.III.3.3(4). Заменить в векторе αe = (−001 −−1−) прочерки символами 0 и 1 так, чтобы получился вектор значений некоторой линейнойфункции f .
Выразить f полиномом.J 1) В силу линейности значения функции на наборах, различающихсязначением только одной существенной переменной, должны быть различными.Так как f (0, 1, 0) 6= f (0, 1, 1), то переменная x3 существенная, следовательно, f (0, 0, 0) = 1, f (1, 1, 1) = 0.Так как f (0, 1, 1) 6= f (1, 1, 1), то переменная x1 существенная, следовательно, вектор значений функции αe = (1001 0110).2) Функция f линейна, фиктивных переменных нет, f (0, 0, 0) = 1,следовательно, f = x1 ⊕ x2 ⊕ x3 ⊕ 1.I12Занятие № 1.4Замкнутые классыII.1.9(1, 2, 5, 6). Выяснить, является ли множество A замкнутымклассом.
Предполагается, что вместе с каждой функцией f из A множеству A принадлежат и все функции из P2 , конгруэнтные f :1) A = {0, 1};2) A = {x};5) A = {x1 · . . . · xn , n = 1, 2, . . .};6) A = {x1 ⊕ . . . ⊕ xn , n = 1, 2, . . .}.J1. Множество A = {0, 1} является замкнутым, так как суперпозициями функций 0 и 1 являются только функции, тождественноравные нулю и единице.2. Множество A = {x} не замкнуто, так как суперпозиция функцийx и x есть функция (x) = x, не принадлежащая множеству A.5. Множество A = {x1 · . .
. · xn , n = 1, 2, . . .} является замкнутым,так как при суперпозиции функций из A получаем функцию изA. Действительно, при подстановке вместо любого xi , 1 6 i 6 n,функции из A мы лишь заменяем этот множитель на группу множителей, а после замены всех произведений вида xk · xk на xkполучим функцию из A.6. Множество A = {x1 ⊕ . . .
⊕ xn , n = 1, 2, . . .} не замкнуто, так какпри суперпозиции x1 ⊕ x2 и x1 получим x1 ⊕ x1 ≡ 0 — функцию,не принадлежащую множеству A.III.1.13(1, 3). Выяснить какое из отношений: ⊆, ⊇, = или ни одно изних, — выполняется для множеств K1 , K2 из P2 :1) K1 = [A1 ∩ A2 ], K2 = [A1 ] ∩ [A2 ];3) K1 = [A1 ∪ (A2 ∩ A3 )], K2 = [A1 ∪ A2 ] ∩ [A1 ∪ A3 ].J1.
Так как A1 ∩A2 ⊆ A1 , то [A1 ∩A2 ] ⊆ [A1 ]. Аналогично [A1 ∩A2 ] ⊆[A2 ]. Откуда следует, что [A1 ∩ A2 ] ⊆ [A2 ] ∩ [A2 ].Покажем, что отношение ⊆ в общем случае не переходит в равенство. Для этого рассмотрим A1 = {↓}, A2 = {|}. Тогда K1 =∅ ⊂ P 2 = K2 .3. Перепишем K1 в виде K1 = [(A1 ∪ A2 ) ∩ (A1 ∪ A3 )] и обозначимA1 ∪ A2 = B1 , A1 ∪ A3 = B2 . При этом K1 = [B1 ∩ B2 ], K2 =[B1 ] ∩ [B2 ], а из предыдущего пункта получим [K1 ] ⊆ [K2 ].I13II.4.1(1). Выяснить, принадлежит ли функцияf = (x1 → x2 )(x2 → x3 )(x3 → x1 )множеству T1 \ T0 .J Функция принадлежит множеству T1 \ T0 , если на единичном и на нулевом наборах она принимает значение 1, то есть f (0, 0, 0) = f (1, 1, 1) =1.
Для данной функции f = (0 → 0)(0 → 0)(0 → 0) = 1 и f = (1 → 1)(1 →1)(1 → 1) = 1, поэтому f ∈ T1 \ T0 .III.2.1(1, 12). Выяснить, является ли функция f самодвойственной:1) f = x1 x2 ∨ x2 x3 ∨ x3 x1 ;12) f = x1 x2 x3 ⊕ x1 x2 ⊕ x2 x3 ⊕ x3 x1 .J1. Функция является самодвойственной, так как согласно принципу двойственности f ∗ = (x1 ∨ x2 )(x2 ∨ x3 )(x3 ∨ x1 ) = f .12. Функция не является самодвойственной, так как она отличаетсяот самодвойственной функции x1 x2 ⊕ x2 x3 ⊕ x3 x1 только на наборе(1, 1, 1), так что вектор её значений содержит 4 ± 1 – не половинуединиц.IЗамечание для последующих задач: самодвойственная функциязадана вектором αef = (α0 , α1 , .
. . , α2n −1 ) тогда и только тогда, когдавыполняется следующее условие:αef = (α0 , α1 , . . . , α2n−1 −1 , α2n−1 −1 , . . . , α1 , α0 ).(S)II.2.2(3, 11). Выяснить, является ли самодвойственной функция f ,заданная векторно:3) αef = (1001 0110);11) αef = (1100 0011 1010 0101).J3.
Вектор значений функцииαef = (1001 0110)удовлетворяет условию (S), поэтому функция является самодвойственной.11. Функция не является самодвойственной, так какf (0, 0, 0) = f (1, 1, 1) = f (0, 0, 0).III.2.7. Доказать, что не существует самодвойственных функций, существенно зависящих в точности от двух переменных.14J Количество самодвойственныхфункций, которые зависят от двух пеn−1 = 4 — это x, y, x, y. Таким образом, не суременных, равно 22 n=2ществует самодвойственной функции, существенно зависящей ровно отдвух переменных.III.2.8(2). Выяснить, при каких n > 2 является самодвойственнойфункция_nf (ex )=xi xj .16i<j6nJ Очевидно, что при n = 2 функция f (x1 , x2 ) = x1 · x2 не являетсясамодвойственной.При n = 3 функция представляет из себя медиануf (x1 , x2 , x3 ) = x1 x2 ∨ x2 x3 ∨ x3 x1 = x1 x2 ⊕ x2 x3 ⊕ x3 x1 ,которая является самодвойственной функцией.При n > 3 выполнено соотношениеf (1100 α5 .
. . αn ) = f (0011 α5 . . . αn ) = 1,следовательно, функция не является самодвойственной.Таким образом, только при n = 3 функция f (exn ) самодвойственна. IЗанятие № 1.5Класс М. Подсчёт числа функцийЗамечание для последующих задач: проверку на монотонностьфункции f , заданной своим вектором значений, можно осуществить следующим образом: f монотонна тогда и только тогда, когда она монотонна на каждой паре соседних наборов.II.5.1(1, 3, 8). По вектору значений αef выяснить, является ли функция f монотонной:1) αef = (0110);3) αef = (0101 0111);8) αef = (0001 0101 0111 0111).J1.
Монотонность нарушается на наборах (10) и (11).3, 8. Следуя алгоритму проверки из замечания, получим, что функцияявляется монотонной.I15II.5.2(3). Проверить, является ли функция f = x1 → (x1 → x2 ) монотонной.J f не является монотонной, поскольку f (0, 0) = 1, а f (1, 0) = 0.III.5.4(6).
Пусть Mn — множество векторов αe = (α0 , α1 , . . . , α2n −1 ), являющихся векторами значений монотонной функции. Найти число векторов из Mn , которые можно получить из вектора γe8 = (−−−1 −−0−)заменой символа «−» на 0 или 1.J В силу монотонности f (1, 1, 1) = 1, f (0, 0, 0) = f (0, 1, 0) = f (1, 0, 0) =0, так что вектор значений должен иметь вид (0−01 0−01).При доопределении функции на оставшихся двух наборах возможнытри варианта:(0001 0001),(0001 0101),(0101 0101).III.5.5(4). Пусть M Sn — множество векторов αe = (α0 , α1 , . . . , α2n −1 ),являющихся векторами значений функций из класса M ∩S.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
