А.А. Вороненко, В.С. Федорова - Дискретная математика. Задачи и упражнения с решениями (1060726), страница 3
Текст из файла (страница 3)
Найти числовекторов из M Sn , которые можно получить, заменяя в векторе γe8 =(−00− 0−−−) символы «−» на 0 или 1.J Так как искомые функции являются самодвойственными, то их векторы значений примут вид (−001 011−). Исходя из монотонности функций, окончательно получим (0001 0111) — единственный вектор из M Sn ,удовлетворяющий условию.III.5.21(2, 3).
Подсчитать число функций в каждом из следующихмножеств:2) M n \ (T1 ∩ T0 );3) M n ∩ L.J2. Так как f (exn ) ∈/ T1 ∩ T0 , то её вектор значений αef может иметьвид(0−− . . . −−0), (1−− . . . −−0) или (1−− . . . −−1).Функция монотонна, значит, случай (1−− . . . −−0) не подходит.Вектор (0−− . . . −−0) соответствует единственной монотоннойфункции f (exn ) ≡ 0, а вектор (1−− . . .
−−1) — f (exn ) ≡ 1.Получаем, что в множестве M n \ (T1 ∩ T0 ) всего 2 функции.3. Линейная функция, имеющая не менее двух существенных переменных, не монотонна. Это следует из того, что при подстановкеконстант вместо остальных переменных получается немонотонная16функция y1 ⊕ y2 или y1 ⊕ y2 ⊕ 1. Следовательно, исходному множеству принадлежат всего n + 2 функции: 0, 1, x1 , x2 , . . . , xn . III.4.3(1, 5, 15, 30). Подсчитать число функций, зависящих от переменных x1 , x2 , . . .
, xn и принадлежащих множеству A:1) A = T0 ∩ T1 ;5) A = T0 ∪ L;15) A = (T0 \ T1 ) ∩ S;30) A = (L \ (T0 ∪ T1 )) ∩ S.J1. Вектор значений функции f ∈ A = T0 ∩ T1 имеет вид(0−− . . . −−1).Длина вектора значений функции n переменных равна 2n . В нашем случае 2 элемента вектора значений уже известны, значит,nдоопределить вектор значений функции можно 22 −2 способами.5. |A| = |T0 | + |L| − |T0 ∩ L|.n|T0 | = 22 −1 , рассуждая аналогично предыдущему пункту.|L| = 2n+1 , так как произвольная линейная функция n переменных имеет видf (exn ) = α0 ⊕ α1 x1 ⊕ .
. . ⊕ αn xn ,и количество функций в L совпадает с количеством способов выбора наборов (α0 , α1 , . . . , αn ).|T0 ∩ L| = 2n , так как если f ∈ T0 , то f (0, 0, . . . , 0) = 0 ⇒ α0 = 0,а значит, остается выбрать n значений α1 , . . . , αn , а это можносделать 2n способами.nnВ итоге получим |A| = 22 −1 + 2n+1 − 2n = 22 −1 + 2n .15.
Так как f ∈ T0 , то f (0, 0, . . . , 0) = 0. Поскольку f ∈/ T1 , тоf (1, 1, . . . , 1) = 0. Но тогда f (0, 0, . . . , 0) = f (0, 0, . . . , 0), а следовательно, функция не является самодвойственной. Значит, множество A пустое.30. Произвольная линейная функция n переменных имеет вид f (exn ) =α0 ⊕α1 x1 ⊕. . .⊕αn xn . Так как f (exn ) ∈/ T0 ∪T1 , то α0 = 1 и α1 ⊕. . .⊕αn = 1, причем количество существенных переменных нечетно.Такая функция f (exn ) самодвойственна, в чем можно убедитьсянепосредственнойпроверкой.LnУсловиеi=1 αi = 1 можно переписать в виде αn = 1 ⊕ α1 ⊕. .
. ⊕ αn−1 , откуда получаем, что при переборе всех наборов длиныn − 1 будут перечислены все наборы, содержащие нечетное числоединиц. Следовательно, множество A содержит ровно 2n−1 функций.I17Занятие № 1.6Полнота и шефферовость в алгебре логикиII.6.1(1). Выяснить, полна ли система функцийA = {xy, x ∨ y, x ⊕ y, xy ∨ yz ∨ zx}.J Составим критериальную таблицу:T0xy+x∨y+x⊕y+xy ∨ yz ∨ zx +T1++−+L−−+−S−−−+M++−+Из таблицы видно, что система А не полна, так как A ⊆ T0 .III.6.2(4). Выяснить, полна ли система функцийA = {f1 = (0101), f2 = (1110 1000), f3 = (0110 1001)}.J Составим критериальную таблицу:T0f1 = (0101)+f2 = (1110 1000) −f3 = (0110 1001) +T1+−+L+−+S+++M+−−Из таблицы видно, что система А не является полной, так как A ⊆ S. III.6.3(1).
Выяснить, полна ли система A = (S ∩ M ) ∪ (L \ M ).J Рассмотрим функцию m(x, y, z) = xy ∨ yz ∨ xz из множества S ∩ M ,а также функции x ∼ y = x ⊕ y ⊕ 1 и x = x ⊕ 1 из множества L \ M .Составим критериальную таблицу:T0m(x, y, z) +x∼y−x−T1++−L−++S+−+M+−−Ясно, что [A] ⊇ [{m(x, y, z), x ∼ y, x}] = P2 , так что система A полна вP2 .III.6.11. Доказать, что если f монотонна и зависит существенно неменее чем от двух переменных, то система {0, f } полна в P2 .18J Функция g ≡ 0 ∈/ T1 ∪ S. Так как функция f монотонна и зависитсущественно хотя бы от одной переменной, то f (0, .
. . , 0) = 0, так какиначе f ≡ 1 и не зависит существенно ни от одной переменной. Таким/ T0 . Так как f (0, . . . , 0) = 1 и функцияобразом, f (0, . . . , 0) = 1 и f ∈существенно зависит от хотя бы одной переменной, то существует набор,на котором функция принимает значение 0, но тогда она не является/ M . Поскольку множество M ∩ L немонотонной; таким образом, f ∈содержит функций, существенно зависящих от двух переменных, то fнелинейна, а значит, нелинейна и f ⊕ 1 = f .Таким образом, рассматриваемая система функций является полной вP2 .III.6.5(1). Из полной в P2 системыA = {1, x, xy(x ⊕ y), x ⊕ y ⊕ xy ⊕ yz ⊕ zx}выделить всевозможные базисы.J Составим критериальную таблицу:T0f1 = 1−f2 = x−f3 = xy(x ⊕ y) ≡ 0+f4 = x ⊕ y ⊕ xy ⊕ yz ⊕ zx +T1+−−+L+++−S−+−+M+−+−f4 войдет в базис в любом случае, а из оставшихся функций можно выбрать любые две.
Искомые базисы B1 = {f1 , f2 , f4 }, B2 = {f1 , f3 , f4 },B3 = {f2 , f3 , f4 }.III.6.8(4, 8). Выяснить, можно ли расширить до базиса в P2 множество А:4) A = {x ∨ y, xy};8) A = {x ⊕ y, x ∼ y}.J4. Составим критериальную таблицу:T0 T1 L S Mx∨y + + − − +xy + + − − +Множество А дополнить до базиса нельзя, так как функции x ∨ yи xy принадлежат одним и тем же предполным классам.8. Составим критериальную таблицу:T0 T1 L S Mx⊕y + − + − −x∼y − + + − −19Из таблицы видно, что множество А можно дополнить до базисанелинейной функцией, принадлежащей T0 и T1 (например, конъюнкцией xy).III.6.15.
Доказать, что если f ∈/ T0 ∪ T1 ∪ S, то f — шефферовафункция.J Утверждение следует из того, что M ⊆ T0 ∪ T1 и L ⊆ T0 ∪ T1 ∪ S. III.6.16. Подсчитать число шефферовых функций в P2 (X n ).J Если f ∈/ T0 ∪ T1 ∪ S, то f — шефферова функция, а значит, числошефферовых функций в P2 (X n ) равно числу всех возможных функций,не принадлежащих T0 ∪ T1 , без всех самодвойственных функций, не приn−1nn−1nIнадлежащих T0 ∪ T1 : 22 −2 − 21 · 22 = 22 −2 − 22 −1 .II.6.10(4).
Выяснить, при каких n > 2 функцияMnxi xjf (ex )=1⊕16i<j6nявляется шефферовой.J Очевидно, что f ∈/ T0 . Кроме того, f ∈/ T1 тогда и только тогда, когдаколичество слагаемых xi xj , 1 6 i < j 6 n, нечётно. Количество слагаемых n2 = n(n−1)нечётно при n = 4k + 2 или n = 4k + 3. Двойственная2nLфункция имеет вид f ∗ = f ⊕ (n − 1) xi ⊕ 1 ⊕ n2 (mod 2) , поэтомуi=1f самодвойственна при n = 4k + 3. Окончательно имеем, что функцияявляется шефферовой при n = 4k + 2.IЗанятие № 1.7Графы: изоморфизм, связностьVI.1.34(6.1, 6.2, 6.3).
Среди пар графов, изображённых на рисунках, указать пары изоморфных и пары неизоморфных графов.Рис. 6.120Рис. 6.2Рис. 6.3J Для любой из пар графов нужно либо построить взаимно однозначноесоответствие между вершинами и рёбрами, либо указать, почему дваданных графа неизоморфны.— Рис. 6.1. Строим взаимно однозначное соответствие так, как показано на рисунке.453465261213— Рис.
6.2. Графы неизоморфны, так как в левом графе на рис. 6.2вершины степени 4 смежны с двумя различными вершинами степени 2, а в правом графе на рис. 6.2 — с одной.— Рис. 6.3. Рассмотрим дополнения этих графов (см. рисунок ниже). Нетрудно видеть, что дополнения графов изоморфны, поэтому изоморфны и сами графы.I21VI.1.2(1). Обозначим через ni (G) число вершин степени i в графеG. Построить все попарно неизоморфные графы без петель и кратныхрёбер, у которых n2 (G) = 1, n3 (G) = n4 (G) = 2 и ni (G) = 0 при i 6= 2,3, 4.J Число вершин графа равно 5. Пусть q — число рёбер в графе.nXdeg vi = 2q ⇒ q = 8.i=1В полном графе с n вершинами n(n − 1)/2 рёбер, что при n = 5 составляет 10 рёбер.
Следовательно, исходный граф может быть получениз полного удалением двух рёбер. Возможны два случая: существуетвершина, инцидентная обоим удаляемым рёбрам, либо её не существует.Во втором случае невозможно получить из вершины степени 4 вершинустепени 2. Следовательно, такой граф только один:BEСDAIVI.1.13(1). Пусть δ(G) — наименьшая из степеней графа G, не имеющего петель и кратных рёбер и содержащего n вершин (n > 2). Доказать, что если δ(G) > (n − 1)/2, то граф связен.J Пусть граф G не связен. Тогда в нем есть два множества вершин, между которыми нет рёбер.
Выберем по одной вершине из каждого множества. По условию, степени этих вершин не меньше чем n−12 . Следовательно, минимальное число вершин в таком графе равно 2 · ( n−12 + 1) = n + 1,что противоречит условию (в графе ровно n вершин). Значит, граф Gсвязный.IVI.1.12. Доказать, что в мультиграфе всякий замкнутый маршрутнечётной длины l > 3 содержит простой цикл. Справедливо ли аналогичное утверждение для маршрутов чётной длины?J В мультиграфе замкнутый маршрут из трёх рёбер всегда являетсяпростым циклом:22Предположим, что для других натуральных l (l = 2k + 1, k ∈ N, k > 2)это не так.
Значит, существует замкнутый маршрут наименьшей длины,не содержащий простых циклов:v0 , . . . , vi , vk , . . . , vi , . . . , v0 .Тогда если длина маршрута vi , . . . , vi чётная, то удалим из первоначального маршрута замкнутый маршрутvi , . . . , vi ,иначе удалим маршрутvk , . . . , vi .В результате полученный маршрут будет иметь нечётную длину.Если полученный маршрут не содержит простой цикл, то мы пришли кпротиворечию, поскольку изначально выбирался маршрут наименьшейдлины.Если же полученный маршрут содержит простой цикл, то мы такжеприходим к противоречию, так как, по предположению, исходный маршрут не содержит простых циклов. Следовательно, в мультиграфе всякийзамкнутый маршрут нечётной длины l > 3 содержит простой цикл.Для маршрутов чётной длины утверждение неверно.
Например, маршрут v0 , v1 , v0 для графа, изображённого ниже, не содержит простых циклов:IVI.1.22. Пусть у графа без петель и кратных рёбер n вершин и sкомпонент связности. Доказать, что число рёбер в нем не меньше n − sи не превосходит (n−s)(n−s+1). Вывести отсюда, что если у n -вершинного2графа (n > 2) число рёбер больше (n−2)(n−1), то он связный.2J Докажем, что для графа G = (V, E) справедливо |E| > n − s. Обозначим через Vi , Ei число вершин и число рёбер в i-той компонентесвязности графа G соответственно. Тогда|E| = |E1 | + . . . + |Es | > (|V1 | − 1) + . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
