Основы теории множеств

Бийский технологический институт (филиал)

О.Д. Ростова, Т.М. Тушкина, В. С. Фролов

Дискретная математика

Методические рекомендации с вариантами заданий к типовому расчету по математике для студентов специальностей 071900, 351400, 170600, 171200

Бийск 2005

УДК 519.1

Ростова О.Д., Тушкина Т.М., Фролов В.С. Дискретная математика: Методические рекомендации к типовому расчету по математике с вариантами заданий для студентов специальностей 071900, 351400, 170600, 171200

Алт. гос. техн. ун-т, БТИ. – Бийск:

Изд-во Алт. гос. техн. ун-та, 2005. – 57 с.

В методических рекомендациях приведены программа курса «Дискретная математика», основные понятия и формулы по каждому разделу курса, примеры решения задач и варианты расчетных заданий для изучающих данный курс.

ВВЕДЕНИЕ

На современном этапе исследование, моделирование и проектирование, особенно автоматизированное, в науке и технике практически невозможно без применения математических методов.

В высшей школе базовой математической дисциплиной является «Высшая математика». Однако при анализе и синтезе сложных систем, например, таких как химико-технологические, создание и эксплуатация ЭВМ, автоматизированных систем проектирования и управления, знаний только высшей математики недостаточно. Поэтому в учебные планы многих специальностей введена дисциплина «Дискретная математика».

Методы дискретной математики позволяют достаточно просто решать задачи проектирования технологических систем, логических устройств, решать задачи планирования и управления.

Данная методическая разработка предназначена для студентов факультетов ИТАУ и ХТиМ, изучающих курс дискретной математики. Для выполнения заданий типового расчета необходимо изучить вопросы, указанные в программе курса. Для помощи при выполнении контрольной работы в разработке приведены основные формулы и примеры решения аналогичных задач.

Выбор номера N варианта каждой задачи проводится по формуле:

N=(10·n+m) mod₃₀ +1,

где

n - предпоследняя цифра номера зачетной книжки;

m - ее последняя цифра;

mod₃₀ - операция деления по модулю 30 (остаток от деления числа на 30).

Например:

Две последние цифры есть 00. Тогда N=0+1=1.

Две последние цифры есть 05. Тогда N=5+1=6.

Последние цифры есть 35. Тогда N=15+1=16.

ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ

1. Множества и подмножества.

2. Основные операции над множествами и их свойства.

3. Диаграммы Эйлера – Венна.

4. Мощность множеств.

5. Равномощные множества.

6. Счетные множества. Континуальные множества.

7. Декартово произведение множеств.

8. Бинарное отношение.

9. Композиция отношений.

10. Степень отношения.

11. Свойства отношений.

12. Транзитивное замыкание отношения.

13. Основные принципы теории расстановок.

14. Перестановки, размещения, сочетания.

15. Расстановки с повторениями.

16. Бином Ньютона.

17. Полиномиальная формула.

18. Формула включений-исключений.

19. Формулы алгебры логики.

20. Таблицы истинности.

21. Функции алгебры логики.

22. Логические константы.

23. Равносильность функций алгебры логики.

24. Нормальные логические формы (ДНФ, КНФ).

25. Совершенные нормальные формы (СДНФ, СКНФ).

26. Упрощение нормальных форм.

27. Принципиальные схемы.

28. Определение графов и орграфов.

29. Подграфы.

30. Матрицы смежности и инцидентности.

31. Плоские графы.

32. Деревья и леса.

33. Остовное дерево связного графа.

34. Цикломатическое число.

35. Сети. Основные понятия.

36. Алгоритм определения критического пути в сети.

Основы теории множеств

Основные понятия и операции

Множество - это любая определенная совокупность объектов, которые называются элементами множества. Элементы множества различны и отличимы друг от друга.

Приняты следующие обозначения. Если a - элемент множества А, то пишут: а А. В противном случае: а А или а А.

Два множества А и В равны, если они содержат одни и те же элементы: А=В.

Множество А всех элементов, обладающих свойством Н(x), обозначается А= или А= .

Множество, не содержащее ни одного элемента, называется пустым и обозначается Æ.

Если все элементы множества В являются элементами множества А, то это обозначают В А или А В (В содержится в А или А содержит В). Множество В называется подмножеством множества А. Если В А, то В называется собственным подмножеством множества и обозначается: В А. Считается, что Æ является подмножеством любого множества.

Отношения и называются включением и собственным включением.

Объединение множеств А и В обозначается А В и представляет собой множество элементов, принадлежащих или множеству А, или множеству В.

Пересечение множеств А и В обозначается А В и представляет собой множество элементов, принадлежащих и множеству А, и множеству В (их общая часть).

Если множества А и В не имеют общих элементов, то есть их пересечение есть пустое множество: А В=Æ, то они называются непересекающимися или дизъюнктными.

Справедливы следующие соотношения:

;

;

;

, ;

;

Æ=А, Æ=Æ.

Разность множеств А и В обозначается А\В, это есть множество элементов множества А, которые не принадлежат множеству В.

Симметрическая разность АDВ множеств А и В представляет собой множество, состоящее из элементов, принадлежащих в точности одному из множеств А и В: АDВ=(А\В)È(В\А).

Если А U, то дополнение множества А относительно множества U определяется как =U\А.

Для более наглядного представления операций над множествами и их свойств применяют диаграммы Эйлера - Венна (рисунок 1). Каждое множество предсталяется множестом точек на плоскости.

\

Рисунок 1 – Диаграммы Эйлера – Венна

Приняты следующие обозначения для числовых множеств:

N – множество натуральных чисел;

Z – множество целых чисел;

R – множество действительных чисел;

Q – множество рациональных чисел;

С – множество комплексных чисел.

Множества А и В называются эквивалентными или равномощными (А~В), если между ними можно установить взаимно однозначное соответствие.

Множество А является бесконечным, если оно эквивалентно некоторому собственному подмножеству.

Всякое бесконечное множество, эквивалентное множеству натуральных чисел N, называется счетным.

Всякое бесконечное множество, эквивалентное множеству действительных чисел Q, называется множеством мощности континуума. Мощность континуума обозначается через .

Множество А, состоящее из конечного числа n элементов, называется конечным. Мощность конечного множества А равна: |А|=n.

Если АÇВ¹Æ, то |АÈВ|=|А|+|В| - |АÇВ|.

Для дизъюнктных множеств (АÇВ=Æ) |АÈВ|=|А|+|В|.

Пусть A_i (i =1,2,...,n; n>1) – конечные множества. Имеет место формула включений-исключений:

|А₁ÈА₂È...ÈА_n|=(|A₁|+|A₂|+...+|A_n|) –...

... - (|A₁ÇA₂|+|A₁ÇA₃|+...+|A_n-1ÇA_n|) +...

...+ (|A₁ÇA₂ÇA₃|+|A₁ÇA₂ÇA₄|+...+|A_n-2ÇA_n-1ÇA_n|) --...

...+(-1)ⁿ⁺¹|A₁ÇA₂Ç...A_n|.

Универсальным множеством U по отношению к конечному множеству А называется множество всех подмножеств множества А. Мощность универсального множества U равна |U|=2ⁿ, где n=|A|.

Примеры

Пример 1. А – множество делителей числа 15; В – множество простых чисел, меньших 10; С - множество четных чисел, меньших 9. Описать каждое множество перечислением. Найти: АÈВ, АÇС, ВÇС,

(АÈС)ÇВ, АÇВÇС.

Решение

Исходя из условия находим А={1;3;5;15},B={2;3;5;7}, C={2;4;6;8}. Тогда AÈB={1;2;3;5;7;15}, BÇC={2}, AÇC=Æ, AÈC={1;2;3;4;5;6;8;15}, (AÈC)ÇB={2;3;5}, AÇBÇC=Æ.

Пример 2. В группе из 100 туристов 70 человек знают английский язык, 45 – французский, 25 человек знают оба языка. Сколько туристов не знают ни английского, ни французского языка?

Решение

Пусть A – множество туристов, знающих английский язык, F – французский. По условию |А|=70, |F|=45, количество туристов, знающих оба языка, равно |AÇF|=25. Множество туристов, знающих хотя бы один язык – это следующее AÈF. Тогда по формуле находим |AÈF|=|A|+|F|-|AÇF|=70+45-25=90. Так как всего туристов 100, а из них знают хотя бы один язык 90, то не знают ни английского, ни французского языка 100-90=10 туристов.

Варианты задачи №1

Найти для вариантов 1 – 10.

1. .

2. .

3. .

4. .

5. .

6. .

7. .

8. .

9. .

10. .

Изобразить на координатной плоскости множества для вариантов 11 – 26.

Условие, которому удовлетворяют координаты точек, принадлежащих множеству
	А	В
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.

Найти для вариантов 27 – 30.

27. U – множество целых чисел, A – множество четных чисел, B – множество чисел, которые кратны 4.

28. U – множество натуральных чисел, A – множество нечетных чисел, B – множество корней уравнения .

29. , А – множество простых чисел, В – множество корней уравнения .

30. , А – множество составных чисел, В – множество степеней числа 2.

Варианты задачи №2

Доказать тождества

1. .

2. .

3. .

4. .

5. .

6. .

7. .

8. .

9. .

10. .

11. .

12. .

13. .

14. .

15. .

Доказать, что

16. .

17. .

18. .

19. .

20. .

21. .

22. .

23. .

24. .

25. .

26. .

27. .

28. .

29. .

30. .

ОТНОШЕНИЯ

Основные понятия и формулы

Если а и b – объекты, то через (а, b) обозначим упорядоченную пару. Равенство упорядоченных пар определяется следующим образом:

(a, b)=(c, d) тогда и только тогда, когда a=b и c=d.

Прямым (декартовым) произведением множеств А и В называется множество упорядоченных пар

А В ={(a, b): a A, b B}.

Аналогично определяется упорядоченная n-ка эелементов и декартово произведение n множеств.

n-ой степенью множества А называется его прямое n-кратное произведение на себя и обозначается так: .

Бинарным отношением между элементами множеств A и B называется любое подмножество R множества А B. Если А=B, то отношение называется бинарным отношением на A. Вместо (x,y) R часто пишут xRy.

Областью определения бинарного отношения R называется множество

= { x: существует y такое, что (x,y) R}.

Областью значений бинарного отношения R называется множество

= { y: существует x такое, что (x,y) R}.

Для бинарных отношений определены обычным образом теоретико-множественные операции объединения, пересечения и т.д.

Дополнением бинарного отношения R между элементами A и B называется отношение =(A B) \ R.

Обратным отношением для бинарного отношения R называется отношение R ^-1={(x,y): (y,x) R}.

Композицией (произведением) отношений R₁ и R₂ называется отношение R₁ R_n ={(x,y): существует z такое, что (x,z) R₁ и (z,y) R₂}.

Пусть и множество A состоит из n элементов, пронумеруем их. Тогда элементы бинарного отношения R можно представить матрицей ||R|| порядка n n такой, что ее элементы r_ij находятся из условия:

Элементы r_ij матрицы ||R|| композиции отношений P и S, т.е. , определяются следующим образом: .

Здесь и - логические операции: дизъюнкция и конъюнкция соответственно.

Бинарное отношение R на множестве A называется рефлексивным, если

(x, x) R для всех x A,

иррефлексивным (антирефлексивным), если

(x, x) R для всех x A.

Бинарное отношение R на множестве A называется симметричным, если для всех х, у A:

из того, что <x, y> R, следует <y, x> R,

антисимметричным, если для всех х, у A:

из того, что <x, y> R и <y, x> R, следует x=y.

Бинарное отношение R на множестве A называется транзитивным, если для всех х, у, z A:

из того, что <x, y> R и <y, z> R, следует <x, z> R.

Рефлексивное, транзитивное и симметричное отношение на множестве A называется эквивалентностью на A.

Бинарное отношение R на множестве A называется предпорядком на A, если оно рефлексивно и транзитивно. Рефлексивное, транзитивное и антисимметричное отношение на множестве A называется частичным порядком на A. Частичный порядок часто обозначается символом ≤. Пишут: x<y, если x≤ y и x≠ y. Частичный порядок ≤ на множестве A называется линейным, если любые два элемента из A сравнимы по отношению ≤, т.е. x≤ y или y≤ x для любых x, y A. Множество A с заданным на нем частичным (линейным) порядком ≤ называется частично (линейно) упорядоченным.

Транзитивным замыканием R⁺ отношения R является объединение всех его положительных степеней, т.е. R⁺= . Под n-ой степенью отношения R понимается его n-кратная композиция с самим собой, т.е. .

Примеры

Пример 1. На множестве А={1, 2, 3, 4, 5} задано отношение R ={(x; y): x < y}. Найти область определения, область значений R. Задать матричным способом R ^-1; ; . Указать свойства отношения.

Решение

Укажем сначала все упорядоченные пары элементов множества А, которые принадлежат отношению R: R = {(1, 2), (1. 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)}.

Область определения отношения = {1, 2, 3, 4}, область значений отношения = {2, 3, 4, 5}.

={(у; х): (x; y) R }={(x; y): y<x}={(x; y): x>y}.

={(х; у): (x; y) R }={(x; y): x y}

Матрицы отношений R, R ^-1; и представлены ниже:

; ;

; .

Поясним способ определения элементов r_ij матрицы композиции отношения R с самим собой, изложенный выше в 2=.1, на нескольких примерах:

;

;

.

Аналогично определены и остальные элементы матрицы .

Отношение R является антирефлексивным, так как для любого элемента x R не выполняется условие x<x.

Отношение R - несимметрично, так как для любых x, y А из того, что x<y, не следует, что y<x.

Отношение R обладает свойством антисимметричности. Оно также и транзитивно, так как для любых x, y, z А, если x<y и y<z, значит x<z.

Пример 2. Найти транзитивное замыкание отношения R, заданного на множестве А={1, 2, 3}. Матрица отношения имеет вид

.

Решение

Найдем матрицы положительных степеней отношения. Результаты занесем в таблицу 1.

Таблица 1 - Степени отношения R

Номер степени отношения	Матрица степени отношения	Степень отношения
Первая		R ={(1, 2), (2, 3), (3, 2)}
Вторая		R2= {(1,3), (2, 2), (3, 3)}
Третья		R3= {(1, 2), (2, 3), (3, 2)}
Четвертая		R4= {(1,3), (2, 2), (3, 3)}

Для данного отношения характерно равенство всех нечетных степеней друг другу и равенство четных степеней. Объединим степени отношения, в результате чего получим транзитивное замыкание отношения R⁺={(1, 2), (1,3), (2, 2),(2, 3), (3, 2), (3, 3)}.

Варианты задачи №3

Дано множество M={1; 2, 3; 4, 5, 6} и бинарное отношение . Найти область определения, область значений R. Задать матричным способом R ^-1; ; ^-1; ^-1 . Указать свойства (рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность). Для нетранзитивного отношения найти транзитивное замыкание.

1. = {(a; b): a - b = 3, а, b }.
2. = {(a; b): a > 2b, а, b }.
3. = {(a; b): a + b > 5, а, b }.
4. = {(a; b): a при делении на b дает в остатке 1, а, b }.
5. = {(a; b): a делитель b, а, b }.
6. = {(a; b): a и b имеют одинаковые остатки от деления на 3, а, b }.
7. = {(a; b): a + b – четное, а, b }.
8. = {(a; b): a +b+1 M, а, b }.
9. = {(a; b): 3a b, а, b }.
10. = {(a; b): a = b² или а+3=b, а, b }.
11. = {(a; b): или a = b² , а, b }.
12. = {(a; b): |b-1| = |a-3|, а, b }.
13. = {(a; b): a делится на b без остатка и а – четно, а, b }.
14. = {(a; b): |a – b| = 3, а, b }.
15. = {(a; b): b = 2a + 1, а, b }.
16. = {(a; b): a = 3b ± 1, а, b }.
17. = {(a; b): M, а, b }.
18. = {(a; b): a+1 b, а, b }.
19. = {(a; b): a – остаток от деления b на 5, а, b }.
20. = {(a; b): a делит b или b делит a, а, b }.
21. R= {(a; b): b – остаток от деления a на 3, а, b }
22. R= {(a; b): |a – b| 3, а, b }
23. R= {(a; b): a делится на b без остатка и b – нечетно, а, b }
24. R= {(a; b): b = 2a - 1, а, b }
25. R= {(a; b): a = 3b + 1, а, b }
26. R= {(a; b): M, а, b }
27. R= {(a; b): a – остаток от деления b на 4, а, b }
28. R= {(a; b): |3 - b| < |a + 2|, а, b }
29. R= {(a; b): a – b + 2 M, а, b }
30. R= {(a; b): b = 5a - 1, а, b }

Поиск по сайту: