С.Н. Селезнева - Основы дискретной математики

Московский государственный университетимени М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиС.Н. СелезневаОсновы дискретной математикиМосква, 2010УДК 510.52:519.712(075.8)ББК 22.18.я73С29Печатается по решению Редакционно-издательского советафакультета вычислительной математики и кибернетикиМосковского государственного университета имени М.В. ЛомоносоваР е ц е н з е н т ы:Алексеев В.Б. – д.ф.-м.н., профессорМарченков С.С. – д.ф.-м.н., профессорСелезнева С.Н.C 29 Основы дискретной математики: Учебное пособие. – М.: Издательский отдел факультета ВМК МГУимени М.А. Ломоносова (лицензия ИД N 05899 от24.09.2001 г.); МАКС Пресс, 2010.

– 60 с.ISBN 978-5-89407-416-0ISBN 978-5-317-03239-5Пособие поддерживает курс Основы дискретной математики“, чита”ющийся автором на факультете вычислительной математики и кибернетики МГУ имени М.В. Ломоносова для студентов по направлению Ин”формационные технологии“. Оно содержит задачи по темам: элементарная теория множеств, элементы комбинаторики, булев куб, возвратныепоследовательности.

В него включены как элементарные, так и болеесложные задачи. По каждой теме приведены необходимые определенияи теоремы, разобраны примеры решения задач. Для студентов младшихкурсов вузов и школьников старших классов.УДК 510.52:519.712(075.8)ББК 22.18я73ISBN 978-5-89407-416-0ISBN 978-5-317-03239-5c Факультет ВМК МГУ имениМ.В. Ломоносова, 2010c С.Н.

Селезнева, 20102ПредисловиеВ настоящем пособии собраны задачи, поддерживающие курс Осно”вы дискретной математики“, читающийся автором на факультете вычислительной математики и кибернетики МГУ имени М.В. Ломоносова для студентов по направлению Информационные технологии“ (1-й”курс).

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

К задачам на определения и подсчет предложены ответы.Пособие может быть полезно студентам младших курсов вузов и школьникам старших классов.Автор надеется, что каждый читатель отыщет в этом задачникечто-то интересное для себя.Автор благодарит доцента Романова Дмитрия Сергеевича и к.ф.м.н. Дайняка Александра Борисовича за идеи некоторых задач. Такжеавтор благодарит профессора Марченкова Сергея Серафимовича и к.ф.м.н.

Дайняка Александра Борисовича за ценные замечания по текступособия. Автор признательна своим близким за поддержку.Селезнева Светлана Николаевна.5 марта 2010 года.31Элементы теории множеств1.1Основные понятияМножество – это совокупность объектов любой природы, рассматриваемых как одно целое (по Кантору1 ). При этом каждый такой объект является элементом этого множества. Или говорят, что он принадлежитэтому множеству. Если какой-то объект не входит в рассматриваемую совокупность, то говорят, что он не принадлежит этому множеству, иличто он не является элементом этого множества.Обозначения:a ∈ A – a – элемент множества A;b∈/ A – b не является элементом множества A.Когда идет речь об объекте, который является элементом какого-томножества, часто употребляют синонимы к слову принадлежит“.

Го”ворят, что он содержится в множестве, или входит в множество, илииз множества. В противном случае говорят, что объект не содержитсяв множестве, или не входит в множество, или не из множества.Чтобы задать множество, достаточно перечислить все его элементыили каким-то образом их описать.Примеры описаний множеств:A = {1, 2, 3} – множество A состит из элементов 1, 2 и 3. Это прямоеперечисление элементов множества.A = {x | x − четное число} – множество A состит из всех четныхчисел. Это описание элементов множества при помощи некоторого свойства, которым все они и только они обладают.Множество, не содержащее ни одного элемента, называется пустым.Пустое множество обозначается как ∅.Данное выше определение множества неформально, множество определено интуитивно. Все дальнейшие понятия будут даны строго математически.Определение 1.1. Множества A и B называют равными, если они состоят из одних и тех же элементов.Обозначение:A = B – множества A и B равны.1Георг Кантор (Cantor) – немецкий математик XIX-XX веков.4Определение 1.2.

Множество A называют подмножеством множества B, если каждый элемент множества A является также и элементоммножества B.Обозначение:A ⊆ B – множество A является подмножеством множества B.Для любого множества A верно, что ∅ ⊆ A и A ⊆ A.Определение 1.3. Множество A называют собственным подмножеством множества B, если каждый элемент множества A является элементом множества B, но не каждый элемент множества B является элементом множества A.Обозначение:A ⊂ B – множество A является собственным подмножеством множества B.Другими словами, A ⊂ B, если A ⊆ B и A 6= B.Определение 1.4.

Объединением множеств A и B называют множество, состоящее из всех тех элементов, которые содержатся или в множестве A, или в множестве B. Объединение множеств A и B обозначаетсякак A ∪ B.Обозначение:A ∪ B = {x | x ∈ A или x ∈ B} – объединение множеств A и B.Определение 1.5. Пересечением множеств A и B называют множество,состоящее из всех тех элементов, которые содержатся одновременно и вмножестве A, и в множестве B. Пересечение множеств A и B обозначается как A ∩ B.Обозначение:A ∩ B = {x | x ∈ A, x ∈ B} – пересечение множеств A и B.Определение 1.6. Разностью множеств A и B называют множество,состоящее из всех тех элементов множества A, которые не содержатсяв множестве B.

Разность множеств A и B обозначается как A \ B.Обозначение:A \ B = {x | x ∈ A, x ∈/ B} – разность множеств A и B.5Определение 1.7. Дополнением к множеству A называют множество,состоящее из всех тех элементов, которые не содержатся в множестве A.При этом считается, что все возможные элементы принадлежат какомуто универсальному множеству U . Дополнение к множеству A обозначается как A.Обозначение:A = {x | x ∈ U, x ∈/ A} – дополнение к множеству A.Определение 1.8.

Прямым, или декартовым2 произведением множествA и B называют множество, состоящее из всех возможных упорядоченных пар, первый элемент в которых из множества A, а второй элемент –из множества B. Произведение множеств A и B обозначается как A × B.Обозначение:A × B = {(x, y) | x ∈ A, y ∈ B} – произведение множеств A и B.Замечание 1.1. Операции объединения, пересечения, умножения множеств можно рассматривать для произвольного конечного числа множеств. Определения вводятся аналогично.Определение 1.9.

n-й декартовой степенью множества A (где n ≥ 2 –натуральное число) называют множество, состоящее из всех возможныхупорядоченных наборов из n элементов, каждый из которых принадлежит множеству A. n-я декартова степень множества A обозначаетсякак An .Обозначение:An = {(x1 , . . . , xn ) | xi ∈ A, i = 1, .

. . , n} – n-я декартова степеньмножества A.Определение 1.10. Множеством всех подмножеств множества A называют множество, состоящее из всех подмножеств множества A. Множество всех подмножеств множества A обозначается как P (A) (иликак 2A ).Обозначение:P (A) = {B | B ⊆ A} – множество всех подмножеств множества A.Для любого множества A верно, что ∅ ∈ P (A) и A ∈ P (A).2Рене Декарт (Descartes) – французский математик, философ, физик и физиолог XVI-XVII веков.6Определение 1.11.

Разбиением множества A называют систему егонепустых подмножеств A1 , . . . , Am , если они попарно не пересекаются и в объединении дают все множество A. В этом случае говорят, чтомножество A разбито на подмножества A1 , . . . , Am .A1 , . . . , Am , где Ai 6= ∅, i = 1, . . . , m, – разбиение множества A, если1) A1 ∪ . . . ∪ Am = A;2) Ai ∩ Aj = ∅ при i 6= j.Пример 1.1. Выразить принадлежность произвольного элемента множеству D через его принадлежность или непринадлежность множествамA, B, C, если D = A ∩ B \ C.Решение. Рассмотрим произвольный элемент x ∈ U . Он может принадлежать или не принадлежать каждому из множеств A, B, C.

Обозначим как 1 и 0 соответственно случаи его принадлежности или непринадлежности этим множествам. Все возможные варианты запишем в таблицу и построим соответствующие значения для множества D:A00001111B00110011C A∩B A∩B001101001101001101010110C10101010D01010100Из таблицы видно, что x ∈ D, если x ∈/ A, B, x ∈ C, или x ∈/ A,x ∈ B, C, или x ∈ A, C, x ∈/ B.Ответ: произвольный элемент принадлежит множеству D = A ∩ B \C, если он принадлежит множеству C и не принадлежит хотя бы одномуиз множеств A и B.Пример 1.2. Объяснить, почему свойство (A\B)\C = A\(B\C) не верно для произвольных множеств A, B, C. Указать, при каких условияхна множества A, B, C оно выполняется.Решение.

Рассмотрим произвольный элемент x ∈ U . Он может принадлежать или не принадлежать каждому из множеств A, B, C. Обозна7чим как 1 и 0 соответственно случаи его принадлежности или непринадлежности этим множествам. Все возможные варианты запишем в таблицу и построим соответствующие значения для левой и правой частейсвойства:A B C A \ B (A \ B) \ C B \ C A \ (B \ C)0 0 000000 0 100000 1 000100 1 100001 0 011011 0 110011 1 000101 1 10001Из таблицы видно, что значения левой и правой частей отличаютсяна таких элементах x, что x ∈ A, C, x ∈/ B или x ∈ A, B, C.