С.Н. Селезнева - Основы дискретной математики (1060725)
Текст из файла
Московский государственный университетимени М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиС.Н. СелезневаОсновы дискретной математикиМосква, 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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
