Решение.

Построим для F остовное дерево Т. В дереве Т существуют, по крайней мере, две концевые вершины: u и w. Удаление этих вершин вместе с инцидентными им рёбрами превратит дерево Т в дерево Т*, граф F в граф F*. Но Т* - остовное дерево для F*. Значит, F* имеет одну компоненту связности. Итак, u и w не являются точками сочленения.

2.1.(а) x = y = 0, x = y = 1; (б) x = y = 1; (в) x = 0, y = 1; (г) x = y = 0;

(д) x = 1, y = 0; (е) x = 1, y = 0; (ж) x = 1, y = 0, z = 0; (з) x = 0, y = 1, z = 1.

2.2. (а) x = y = 1; (б) x = y = 1, z = 0.

2.3. (б) [1001]; (в) [0000]; (г) [10101111]; (е) [11111111].

2.5. (г) 56.

2.6. (г) 65536.

2.8. (а) СДНФ: xy Ú ; СКНФ: ( Úy) (xÚ ).

2.9.(б) Ú y Ú x Ú xy .

2.10. (б) (xÚy) (xÚ ) ( Úy) ( Ú ).

2.11. (а) ; (б) x Ú x z Ú xyz.

2.13. (г)(x ­ ) Å (y | ( Ú x)).

2.15. (а) 1; (б) x Ú yz; (в) xy; (г) x Ú ; (д) x Ú Ú z; (е) 0; (ж) y;

(з) Ú y.

2.19.

2.23.(а) xyÅy; (б) xyÅxÅyÅ1; (в) xÅyÅ1; (г) xyÅxÅ1;

2.25. (а) xyzÅyzÅxÅ1; (б) xyÅxzÅ1; (в) xyzÅxyÅxzÅyzÅxÅyÅzÅ1;

2.27. (а) f₂; (б) f₂, f₄; (в) f₂.

2.29. 32768. 2.31. f₂, f₃. 2.33.8. 2.34. 256. 2.35. f₂.

2.39. 1024. 2.40. (а) Т₀, L; (б) -.

2.42. Указание.Составить, например, суперпозицию вида:

((xÅy) Å z).

2.43. Указание. Показать, например, что Т₀ È S ≠ [Т₀ È S].

ЛИТЕРАТУРА

1. Березина Л.Ю. Графы и их применение. М.: Просвещение, 1979. 143 с.

2. Войткунская А.Я. Методическое обеспечение индивидуальной работы студентов-судостроителей по дискретной математике. Часть I: Метод. указания. СПб.: ППО «Пегас», 1993. 70 с.

3. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. - М.: Лаборатория базовых знаний, 2001. 288 с.

4. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Наука, 1984. 224 с.

5. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. СПб.: Издательство «Лань», 1998. 288 с.

6. Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учеб. пособие. М.: Изд-во МАИ, 1992. 264 с.

7. Сборник упражнений по курсу «Дискретная математика» для практических и индивидуальных занятий по специальности 220400: Методические указания. / Составитель – Н.Р. Ланина. Мурманск: Изд-во МГТУ, 2000. 31 с.

8. Харари Ф. Теория графов. М.: Едиториал УРСС, 2003. 296 с.

9. Яблонский С.В. Введение в дискретную математику: Учеб. пособие для вузов. М.: Высш. шк., 2001. 384 с.