ВВЕДЕНИЕ

1.4. Граф F - полный неориентированный и имеет n вершин. Скольким рёбрам инцидентна вершина в графе F? Сколько всего рёбер содержит граф F?

1.5. На плоскости имеется 87 точек. Сколько существует отрезков с концами в этих точках?

1.6. Сколько рёбер надо добавить к графу, чтобы он стал полным (рис. 1.1)?

Рис. 1.1.

1.7. Сколько диагоналей в выпуклом 92-угольнике?

1.8. Существует ли полный неориентированный граф, имеющий

а) 107 рёбер? б) 120 рёбер?

1.9. Можно ли устроить такой тренировочный турнир, чтобы в нём участвовало 33 команды, и каждая команда сыграла ровно 3 матча?

1.10. В компании из n человек у каждого ровно трое друзей. Докажите, что n чётно.

1.11. Доказать, что если каждый из 5 человек переписывается ровно с двумя другими, то не найдется трёх человек, которые все переписываются между собой.

Изоморфные графы

1.12. Доказать, что графы изоморфные (рис. 1.2).

1.13. Нарисуйте диаграммы всех неизоморфных неориентированных графов

а) с 3 вершинами (их четыре); б) с 4 вершинами (их 11).

1.14. Доказать, что все полные графы с n вершинами изоморфны.

Рис. 1.2.

1.15. Доказать, что графы не являются изоморфными (рис. 1.3).

Рис. 1.3.

1.16. Исследовать графы на изоморфизм (рис. 1.4).

Рис. 1.4.

1.17. Доказать, что изоморфизм графов представляет собой отношение эквивалентности.

Количество графов на N помеченных вершинах

1.18. Сколько существует неориентированных графов с 5 помеченными вершинами (т.е. среди этих графов могут быть и изоморфные) и

а) 3 ребрами; б) не более чем с 3 ребрами;

в) с произвольным количеством ребер; г) 8 ребрами;

д) не менее чем с 8 ребрами; е) хотя бы с одним ребром?

1.19. Сколько существует ориентированных графов с 4 помеченными вершинами (т.е. среди этих графов могут быть и изоморфные) и

а) 10 ребрами; б) не менее чем с 10 ребрами;

в) с произвольным количеством ребер; г) 3 ребрами;

д) не более чем с 3 ребрами; е) хотя бы с одним ребром?

1.20. Известно, что на n помеченных вершинах можно построить 990 различных неориентированных графов с 2 рёбрами. Определить n.

Операции над графами

1.21. Нарисуйте граф, являющийся дополнением к графу:

а)изображенному на рис. 1.2, а;

б)изображенному на рис. 1.2, б;

в) к полному графу с 8 вершинами.

1.22. Граф F имеет 174 вершины. Скольким рёбрам инцидентна вершина в дополнении к графу F, если в F она инцидентна:

а) 173 рёбрам? б) 70 рёбрам?

1.23. Граф F называется самодополнительным, если он изоморфен своему дополнению . Нарисуйте самодополнительный граф

а) с 4 вершинами, б) с 5 вершинами.

1.24. Докажите, что количество вершин самодополнительного графа должно быть равно 4k или 4k+1, где kÎ N.

1.25. Имеется n_i точек. Каждая пара из них соединена отрезком либо синего, либо красного цвета. Всегда ли можно выбрать из этих точек такие три, что все отрезки, соединяющие их друг с другом, будут одного цвета? а) n₁ = 4; б) n₂ = 5.

1.26. Задача Рамсея. Доказать, что среди любых шести человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых.

1.27. Пусть каждая пара из 6 точек соединена отрезком либо синего, либо красного цвета. Всегда ли можно найти два треугольника, образованных отрезками одного цвета (разрешается, чтобы эти треугольники имели общую сторону)?

1.28. На географическую карту нанесено 5 городов. Из любых трех найдутся 2 города, соединенные авиалиниями, и два - несоединенные. Доказать, что

а) каждый город соединен только с двумя городами;

б) вылетев из любого города, можно облететь остальные, побывав в каждом по одному разу, и вернуться назад.

1.29. Над графами F₁ и F₂ (рис. 1.5) выполнить операции объединения F₁ È F₂, соединения F₁ + F₂, произведения F₁ ´ F₂ , композиции F₁ [F₂] и F₂ [F₁].

Рис. 1.5.

1.30. Пусть F₁ и F₂ - полные неориентированные графы с 4 и 5 вершинами соответственно. Подсчитать количество вершин и рёбер в графах F₁ÈF₂, F₁+F₂, F₁´F₂, F₁ [F₂] и F₂ [F₁].

1.31. Доказать или опровергнуть: если F₁ и F₂ - однородные графы, то таковы же графы:

а) F₁ + F₂; б) F₁ ´ F₂; в) F₁ [F₂].

1.32. Доказать или опровергнуть:

а) = + ; б) = ´ ; в) = [ ].

Степени вершин графа

1.33. Существует ли полный неориентированный граф с 5 вершинами, степени которых все различны между собой, т.е. равны 0, 1, 2, 3, 4?

1.34. Нарисуйте неориентированный граф с 5 вершинами, у которого ровно 2 вершины имеют одинаковую степень.

1.35. Все вершины неориентированного графа F(V, E)(|V| = n, |E| = m) имеют степень k или k+1. Доказать, что если F имеет n_k вершин степени k и n_k+1 вершин степени k+1, то n_k = (k+1)n - 2m.

1.36. Доказать, что в любом неориентированном графе количество вершин нечётной степени чётно.

1.37. В тренировочном турнире участвовало 12 команд, причём между каждыми двумя командами было сыграно по 3 матча. Сколько всего было проведено матчей?

1.38. Если в неориентированном графе с 5 вершинами ровно 2 вершины имеют одинаковую степень, то могут ли они обе быть изолированными или обе иметь степень 4?

1.39. Доказать, что в любой компании, состоящей из 11 человек, найдутся 2 человека, имеющих одинаковое количество знакомых в этой компании.

1.40. Во всякой ли компании найдутся 3 человека, у которых одинаковое количество знакомых в этой компании?

Способы задания псевдографов

1.41. Для псевдографа, изображённого на рисунке 1.6, а, составить матрицу смежности, матрицу инцидентности, список рёбер, списки смежности. Определить степени всех его вершин.

1.42. Для графа, изображённого на рисунке 1.6, б, составить матрицу смежности, матрицу инцидентности, список рёбер, списки смежности. Определить степени всех его вершин.

Рис. 1.6.

1.43. Без помощи диаграммы по известной матрице инцидентности неориентированного псевдографа восстановить его список ребер и матрицу смежности.

а б в

1.44. Без помощи диаграммы по известной матрице инцидентности ориентированного псевдографа восстановить его список ребер и матрицу смежности.

а б в

1.45. Без помощи диаграммы по известной матрице смежности неориентированного псевдографа восстановить его матрицу инцидентности и определить степени всех вершин.

а б в

1.46. Без помощи диаграммы по известной матрице смежности ориентированного псевдографа восстановить его матрицу инцидентности и определить степени всех вершин.

а б в

1.47. Без помощи диаграммы по известному списку рёбер ориентированного псевдографа восстановить его матрицу инцидентности и матрицу смежности, а также определить степени всех вершин.

1.48. Пусть C^r обозначает r-ю степень матрицы смежности ориентированного псевдографа F. Доказать, что (i, j)-й элемент матрицы C^r равен количеству всех путей длиной r из u_i в u_j.

1.49. Пользуясь утверждением задачи 1.48, по заданной матрице C смежности ориентированного псевдографа F определить

а) количество путей длины 2 из вершины 1 в вершину 5;

б) количество путей длины 3 из вершины 1 в вершину 4;

в) количество циклов чётной длины l (l £ 4), проходящих через вершину 1.

Связность. Достижимость

1.50. Для псевдографа, изображённого на рисунке 1.6, а, составить матрицу отношения связности.

1.51. Для псевдографа, изображённого на рисунке 1.6, б, составить матрицу отношения достижимости. Разбить множество его вершин на классы эквивалентности.

1.52. Доказать, что в неориентированном псевдографе из всякого цикла можно выделить простой цикл.

1.53. Замкнутый путь, в котором все дуги попарно различны, называется контуром. Контур, в котором для каждой вершины u справедливо равенство r₁(u) = r₂(u) = 1, называется простым. Доказать, что в ориентированном псевдографе из всякого замкнутого пути можно выделить простой контур.

1.54. Для графа, изображённого на рис. 1.7, указать все точки сочленения и все мосты.

Рис. 1.7.

1.55. Всегда ли компанию из n человек, в которой у каждого ровно трое знакомых, можно разбить на n / 2 пар так, чтобы люди в каждой паре были друзьями?

1.56. Доказать, что вершина u является точкой сочленения графа F тогда и только тогда, когда в F найдутся такие вершины u и w, отличные от u, что u принадлежит любой простой (u, w)-цепи.

1.57. Доказать, что если u - точка сочленения в графе F, то она не является точкой сочленения в .

1.58. Доказать, что если неориентированный граф F не является связным, то связно его дополнение .

Эйлеровы и гамильтоновы графы

1.59. Какой из графов является эйлеровым или гамильтоновым (рис. 1.8)?

Рис. 1.8.

1.60. Выписать все эйлеровы цепи графа F, изображенного на рис. 1.9 (их восемь). Показать, что в F нет эйлерова цикла, а в подграфе F* с множеством вершин {1, 2, 3, 4} их ровно два. Доказать, что ни F, ни F* не являются гамильтоновыми.

Рис. 1.9.

1.61. Проверить, существуют ли в графах, заданных матрицами смежности, эйлеровы цепи и циклы? Если “да”, то найти их.

а б

1.62. Составить маршрут для автотуристов так, чтобы каждый населенный пункт (рис. 1.10) посещался бы в точности один раз.

Рис. 1.10.

1.63. Какой из графов обязательно содержат гамильтонов цикл:

а) плоский, б) эйлеров, в) полный, г) связный?

1.64. Сколько различных гамильтоновых a) цепей, б) циклов содержит полный ориентированный граф, имеющий n вершин?

1.65. Сколько различных гамильтоновых a) цепей, б) циклов содержит полный неориентированный граф, имеющий n вершин?

1.66. Доказать, что эйлеров граф не содержит мостов.

1.67. Доказать, что если в неориентированном графе F с n ³ 3 вершинами для любой пары несмежных вершин u и w выполняется соотношение: r(u)+r(w) ³ n, то F гамильтонов.

1.68. Доказать, что если в неориентированном графе F с n > 3 вершинами для любой вершины u степень r(u) ³ n/2, то F гамильтонов.

1.69. Привести пример не гамильтонова графа с n = 10 вершинами, у которого r(u)+r(w) ³ n - 1 для любой пары несмежных вершин u и w.

Дерево, лес. Свойства деревьев

1.70. Нарисовав диаграммы неизоморфных деревьев, показать, что

а)на 6 вершинах их шесть; б) на 7 вершинах их одиннадцать.

1.71. Доказать, что лес, состоящий из k деревьев и содержащий n вершин, имеет n-k рёбер.

1.72. Сколько рёбер следует удалить из связного графа F, имеющего m рёбер и n вершин, чтобы получить дерево, содержащее все вершины F?

1.73. Из дерева Т удалено не концевое ребро. В результате образовался новый граф Т*. Доказать, что Т* - лес.

1.74. Какое максимальное и какое минимальное число концевых вершин может иметь дерево, обладающее 9-ю вершинами?

1.75. Пусть F₁ - неориентированное дерево с 4 вершинами, а F₂ - полный неориентированный граф с 3 вершинами. Подсчитать количество вершин и рёбер в графах F₁ÈF₂, F₁+F₂, F₁´F₂, F₁ [F₂] и F₂ [F₁].

1.76. С помощью алгоритма Прюфера восстановите по вектору дерево. Сделайте проверку.

а) (3, 3, 7, 1, 1, 1); в) (7, 11, 11, 6, 6, 6, 2, 2, 10, 1);

б) (1, 2, 2, 4, 9, 5, 5, 5); г) (2, 3, 1, 4, 4, 4, 1, 2, 6, 6).

1.77. В дереве с n концевыми вершинами нет вершин степени 2 (исключение может составлять только корень). Доказать, что общее число вершин такого дерева не превосходит 2n-1.

Двудольный граф

1.78. Показать, что дерево является двудольным графом.

1.79. Показать, что граф, изображенный на рис. 1.11, а является двудольным и составить его матрицу смежности.

Рис. 1.11.

1.80. Охарактеризовать матрицу смежности произвольного двудольного графа.

1.81. Доказать, что наибольшее число рёбер у графов, имеющих n вершин и не содержащих треугольников, равно [n²/4].

1.82. Доказать, что граф F с n вершинами не является двудольным, если он имеет более n²/4 ребер.

1.83. Доказать, что если в графе F с n вершинами отсутствуют циклы нечетной длины и число ребер превышает (n-1)²/4, то граф связный.

1.84. Доказать или опровергнуть: если F₁ и F₂ - двудольные графы, то таковы же графы: а) F₁ + F₂; б) F₁ ´ F₂; в) F₁ + [F₂].

1.85. Доказать, что граф F двудольный тогда и только тогда, когда для любого нечетного числа n все диагональные элементы матрицы Сⁿ равны нулю (С - матрица смежности графа F).

Планарность. Плоский граф

1.86. Доказать, что графы планарные (рис. 1.11) и проверить для них формулу Эйлера.

1.87. Существует ли граф с 4 вершинами, не являющийся планарным?

1.88. Является ли планарным граф, который может быть изображен проволочной моделью куба?

1.89. Неориентированный граф задан матрицей смежности. Является ли он планарным?

а б

1.90. Проверить формулу Эйлера для графа, образованного 8´8 квадратными полями шахматной доски. Обобщить результат на случай доски l´l.

1.91. Привести пример такого графа F с 8 вершинами, что графы F и одновременно планарные.

1.92. Доказать, что в графе F с не менее чем 11 вершинами F и не могут быть планарные одновременно.

1.93. Доказать, что в графе F с не менее чем 9 вершинами F и не могут быть планарные одновременно.

Раскраска графа

1.94. Определить хроматические числа графов, изображённых на рис. 1.11.

1.95. Определить хроматическое число связного однородного графа степени 2 с n вершинами.

1.96. Доказать, что хроматическое число любого n-вершинного дерева (n ³ 2) равно 2.

1.97. Доказать, что граф 2-хроматический тогда и только тогда, когда каждый его цикл имеет чётную длину.

1.98. Определить хроматическое число графа, полученного из полного n-вершинного графа удалением: а) одного ребра; б) двух рёбер; в) трёх рёбер, составляющих треугольник.

1.99. В плоскости проведено конечное число прямых линий, которые разбили эту плоскость на конечное число областей. Доказать, что достаточно два цвета для такой раскраски всех этих областей, когда любые две смежные области окрашиваются в разные цвета.

1.100. Доказать, что хроматическое число c(F) графа F не превышает 1+D(F), где D(F) - максимальная из степеней вершин.

Остовное дерево

1.101. Привести пример графа, из которого нельзя выделить остовное дерево.

1.102. Найти минимальное остовное дерево, используя алгоритм

1) Крускала, 2) Прима (рис. 1.12).

Рис. 1.12.

1.103. Доказать, что в любом нетривиальном связном неориентированном графе F есть, по крайней мере, две вершины, которые не являются точками сочленения.

1.104. Каково наибольшее число точек сочленения в графе с n вершинами?

Кратчайшие пути

1.105. Найти кратчайшие пути от вершины-источника s до всех остальных вершин как методом Форда-Беллмана, так и методом Дейкстры (рис. 1.13).

Рис. 1.13.

Максимальный поток

1.106. Перераспределить заданный начальный поток по сети так, чтобы он стал максимальным (рис. 1.14).

Рис. 1.14.

1.107. Найти максимальный поток в сети (рис. 1.15).

Рис. 1.15.

ЧАСТЬ II. БУЛЕВЫ ФУНКЦИИ

Таблицы значений булевых функций

2.1. Решить булевы уравнения:

а) x Ú y = x × y; д) ~ y = x×y Ú ;

б) x | y = 0; е) ­ y = 1;

в) x Å y = x ® y; ж) x× Ú y = ;

г) ® x = 0; з) (y ® (xÚz))® x z = (x Ú (y~z)) × (xz ® y)

2.2. Решить системы булевых уравнений:

а) ; б) .

2.3. Построить таблицы значений для следующих булевых функций:

а) f(x, y) = (x®y) Ú ( x®y×x); г) f(x, y, z) = (x­ ) | (x×y Ú z);

б) f(x, y) = (x× (yÚ )) ~ (( ®x)Úx); д) f(x, y, z) = ((x|y) ® ) ­ (zÚ );

в) f(x, y) = (x Å ( x)) ­ (y® ); е) f(x, y, z) = x ( | z)(y­z) ® .

2.4. Проверить, выполняются ли законы коммутативности и ассоциативности для сложения по модулю 2, стрелки Пирса и штриха Шеффера.

2.5. Булева функция n переменных принимает значение «1» на восьми наборах переменных. На скольких наборах переменных эта функция принимает значение «0», если

а) n = 3; б) n = 4; в) n = 5; г) n = 6?

2.6. Подсчитайте количество различных булевых функций n переменных, если

а) n = 1; б) n = 2; в) n = 3; г) n = 4.

Совершенные нормальные формы

2.7. Разложить булевы функции, представленные в таблице 1, в совершенную дизъюнктивную и совершенную конъюнктивную нормальные формы.

Таблица 1.

2.8. Используя таблицы значений, разложить данные функции в совершенную дизъюнктивную и совершенную конъюнктивную нормальные формы:

а) f(x, y) = x ~ y; д) f(x, y) = x ® y;

б) f(x, y) = x Å y; е) f(x, y) = (x Ú y) ~ (x × y);

в) f(x, y) = x ­ y; ж) f(x, y, z) = y ~ (x Ú y× );

г) f(x, y) = x | y; (з) f(x, y, z) = (x × ( ®z)) ­ ( | z).

2.9. Используя таблицы значений, разложить данные функции в совершенную дизъюнктивную нормальную форму:

а) f(x) = 1; б) f(x, y) = 1; в) f(x, y, z) = 1.

2.10. Используя таблицы значений, разложить данные функции в совершенную конъюнктивную нормальную форму:

а) f(x) = 0; б) f(x, y) = 0; в) f(x, y, z) = 0.

Двойственная функция

2.11. Построив таблицы значений для заданных функций f, составить таблицы значений для двойственных функций f*. Восстановить вид f* с помощью наиболее экономичной совершенной нормальной формы.

а) f(x, y) = (x ~ ( Åx)) | ( ®0); в) f(x, y, z) = ( Å ) ­ (xy~z);

б) f(x, y, z) = (x|1)®(y­ ( Úx)); г) f(x, y, z) = (x| ) × (y­( y Ú Úx)).

2.12. С помощью таблиц значений выяснить, какие функции являются двойственными к следующим функциям:

а) эквивалентности, в) стрелке Пирса,

б) сложению по модулю 2, г) штриху Шеффера?

2.13. Используя принцип двойственности, найти функции f*, двойственные к данным функциям f.

а) f(x ,y, z) = (xÚ ) × x × ( Ú x×y); в) f(x, y, z) = x × Ú x×y;

б) f(x, y, z) = × ( Åx); г) f(x, y, z) = (x | ) ~ (y ­ ( Úx)).

Эквивалентные преобразования

2.14. Найдите x, если Ú º b.

2.15. Упростить формулы:

а) x Ú(x®y) × (x® ); д) (x®z) ® (((y®z)®xy)®z);

б) xz Ú x Ú yz Ú yz; е) (x Å ( &x)) ­ (y® );

в) (x~y) × (xÚy); ж) ((x­y)® ) | (zÚ );

г) (y®x) Ú (y®yx); з) (xÚ ®(z®yÚ Úx)) × (xÚ ) ® y.

2.16. Используя эквивалентные преобразования, разложить данные функции в совершенную дизъюнктивную и совершенную конъюнктивную нормальные формы:

а) f(x, y) = x (x®y); г) f(x, y, z) = ( ­y) Å ;

б) f(x, y) = (x®y) ® (y®x); д) f(x, y, z) = ( Úx) ~ (xy );

в) f(x, y, z) = (xÚ ) ® yz; е) f(x, y, z) = (x (y® )) ­ .

2.17. По таблицам значений (см. таблицу 1) найдите формулы, реализующие функции f₁, f₂, f₃, f₄, и придайте им более простой вид.

Релейно-контактные схемы (РКС)

2.18. Составить наиболее простые РКС для формул:

а) x ( z Ú у) ; в) (x ® (zÚ )) ~ (( ®x) Ú z);

б) (x®y) ® (yÚz); г) (z Å ( x)) Ú (y ® ).

2.19. Упростить РКС:

2.20. Построить наиболее простые РКС по заданным условиям работы:

а) f(0,0,1) = f(1,0,1) = f(1,1,1) = 1;

б) f(0,0,0) = f(0,1,0) = f(0,1,1) = f(1,1,1) = 1;

в) f(0,0,0,0) = f(0,0,1,1) = f(1,1,0,0) = 1;

г) f(0,1,0,1) = f(1,1,1,1) =1,

а на остальных наборах значения функции f равны нулю.

2.21. Комитет состоит из пяти человек. Решение выносится большинством голосов. Если председатель голосует “против”, решение не принимается. Постройте такую схему, чтобы, голосуя “за”, каждый из пяти человек нажимал бы на кнопку, и в случае принятия решения зажигалась бы сигнальная лампочка.

2.22. Требуется, чтобы включение света в комнате осуществлялось с помощью трех различных переключателей таким образом, чтобы нажатие на любой из них приводило к включению света, если он перед этим был выключен, и к его выключению, если он был включен. Построить простую цепь, удовлетворяющую такому заданию.

Полином Жегалкина

2.23. Используя таблицы значений, разложить данные функции двух переменных в полином Жегалкина.

а) f(x, y) = y; в) f(x, y) = (y ® ) | (xÚy);

б) f(x, y) = x ­ y; г) f(x, y) = xyÚ .

2.24. Разложить в полином Жегалкина функции f₁, f₂, f₃, f₄, представленные в таблице 1.

2.25. Используя таблицы значений, разложить данные функции трёх переменных в полином Жегалкина.

а) f(x, y, z) = x ­ (yz); в) f(x, y, z) = ;

б) f(x, y, z) = (xz ® y) × (xy ® z); г) f(x, y, z) = (x Å ) Ú ( | z).

2.26. Путём эквивалентных преобразований преобразовать данные формулы в полином Жегалкина.

а) ; в) ( ~ y) × (xz ® );

б) xÚy; г) × (z®y) Ú ((yÚ Ú ) ® xy ).

Функционально замкнутые классы

2.27. Какие из булевых функций f₁, f₂, f₃, f₄, представленных в таблице 1, принадлежат:

а) классу Т₀ функций, сохраняющих константу 0;

б) классу Т₁ функций, сохраняющих константу 1;

в) обоим классам - и Т₀, и Т₁?

2.28. Среди булевых функций от одной и двух переменных найти все функции, сохраняющие 1, и все функции, сохраняющие 0.

2.29. Подсчитайте количество булевых функций от n переменных, сохраняющих константу 0, если n = 4.

2.30. Найти число булевых функций от n переменных, принадлежащих одновременно классам Т₀ и Т₁.

2.31. Какие из булевых функций f₁, f₂, f₃, f₄, представленных в таблице 1, являются самодвойственными?

2.32. Показать, что функция f(x, y, z) = xy Ú yz Ú zx является самодвойственной.

2.33. Булева функция четырёх переменных самодвойственна. На скольких наборах переменных она принимает значение “1”?

2.34. Подсчитайте количество самодвойственных булевых функций от n переменных, если n = 4.

2.35. Какие из булевых функций f₁, f₂, f₃, f₄, представленных в таблице 1, являются монотонными?

2.36. Построить все монотонные функции от двух переменных.

2.37. Какие из функций монотонны?

а) f(x, y, z) = xy Ú xz Ú ;

б) f(x, y, z) = ( Ú Úz) ® z×(xÚy);

в) f(x, y, z) = ~ Ú .

2.38. Среди булевых функций от одной и двух переменных найти все линейные функции.

2.39. Подсчитайте количество линейных булевых функций от n переменных, если n = 9.

2.40. К каким классам принадлежат данные булевы функции?

а) f(x, y) = x Å y; в) f(x, y, z) = z× (xÚy) Ú xy ;

б) f(x, y) = x | y; г) f(x, y, z) = × (z~y) Ú x× (yzÚ ).

2.41. Доказать, что пересечение двух функционально замкнутых классов есть функционально замкнутый класс.

2.42. Доказать, что класс функций, сохраняющих константу 0, но не сохраняющих константу 1, не является функционально замкнутым.

2.43. Доказать, что объединение функционально замкнутых классов может не быть функционально замкнутым.

2.44. Доказать, что совокупность функций, двойственных функциям из функционально замкнутого класса, образует функционально замкнутый класс.

Полные системы

2.45. Преобразовать данные формулы таким образом, чтобы в их записи остались только: 1) отрицание и конъюнкция; 2) отрицание и дизъюнкция; 3) штрих Шеффера; 4) стрелка Пирса.

а) x ~ y; в) xy Ú ; д) (xÚy) × ;

б) x Å y; г) Ú yz; е) xÚ Úz.

2.46. Используя теорему о функциональной полноте, проверить, являются ли полными следующие системы функций:

а) { , x₁®x₂}; в) {x₁Åx₂, x₁Úx₂, 1}; д) {0, x₁®x₂}.

б) { , 1}; г) {x₁×x₂, x₁Úx₂, x₁®x₂};

2.47. Используя теорему о функциональной полноте, проверить, являются ли полными следующие системы, состоящие из одной функции:

а) f(x) = ; в) f(x,y,z) = ×(x®y) Ú z×((xÚ ) ® x );

б) f(x,y)= × ; г) f(x,y,z) = ×(y~z) Ú x×(yÅz).

2.48. Доказать, что единственными полными системами, состоящими из одной булевой функции от двух переменных, являются системы {x₁­x₂} и {x₁ | x₂}.

2.49. Привести пример полной системы функций, состоящей из одной функции n переменных.