Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Задачи для самостоятельного решения.

Читайте также:
  1. Gt; во-вторых, когнитивной оценкой (cognitive appraisal), которую человек дает событию, требующему разрешения.
  2. I. Задачи настоящей работы
  3. I. Цели и задачи проекта
  4. II. Основные цели и задачи Программы, срок и этапы ее реализации, целевые индикаторы и показатели
  5. II. Упражнения и задачи
  6. II. Упражнения и задачи
  7. II. Упражнения и задачи
  8. II. Цели и задачи проекта
  9. II. Цели и задачи службы .
  10. III. Для обеспечения проверки исходного уровня Ваших знаний-умений необходимому, предлагаем решить 2 задачи.

ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ

________________________________________________________

 

ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И ЭЛЕКТРОНИКИ

КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ И ИНФОРМАЦИОННОЙ ТЕХНИКИ

 

Алексеев В.В.

 

Элементы теории множеств и теории графов

Сборник задач и упражнений по курсу “Дискретная математика”

 

 
 

 


 

 

Саров

Г.

 

 

1. Элементы теории множеств

 

1.1 Теоретико-множественные операции

По определению Г. Кантора, основоположника теории множеств, множество есть любое собрание определенных и различимых между собой объектов нашей интуиции или интеллекта, мыслимое нами как единое целое. Между отдельными объектами и множествами существует отношение принадлежности. Если предмет х принадлежит множеству А, то это записывают в виде хÎА, если не принадлежит множеству А, то пишут хÏА.

Для обозначение множества служит пара фигурных скобок {….}, внутри которых перечисляются элементы множества.

Существует три способа задания множества: перечисление описание, порождающие процедуры. Во втором случае элементы множества определяются по заданному закону (правилу). Например, А={x|(утверждение об х)}, которое читается как: “А есть множество таких элементов х, для которых (утверждение об х) верно”. Или можно записывать и так: А={x|P(x)}, которое читается как “А есть множество таких элементов х, которые обладают свойством Р”.

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

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

Между различными множествами может существовать отношение включения, как отношение “быть подмножеством”. Множество А является подмножеством В, если любой элемент множества А принадлежит множеству В. Это определение записывают в виде АÌВ, где символ Ì означает включение. Для подмножеств справедливо свойство рефлексивности (АÍА) и транзитивности [(АÍВ и ВÍС)®АÊС]. Кроме того, для любого множества А справедливо ÆÊА.



Два множества называются равными, если они состоят из одних и тех же элементов, т.е. АÍВ и ВÍА.

Если А – конечное n-элементное множество, тогда имеется ровно 2n различных подмножеств, составленное из элементов множества А, включая несобственные подмножества Æ и А.

Множество всех подмножеств данного множества А называется степенью множества А или булеаном b(А).

Если при некотором рассмотрении участвуют только подмножества некоторого фиксированного множества I, то это самое большое множество называется универсальным (полным) множеством и графически обозначается в виде точек прямоугольника, отдельные области которого обозначают различные подмножества I. Такое изображение множеств называется диаграммой Эйлера – Венна.

Основные операции над множествами:

Ø Объединение: АÈВ={x|xÎA или xÎB};

Ø Пересечение: АÇВ={x|xÎA и xÎB};

Ø Разность: А\В={x|xÎA и xÏB};



Ø Симметрическая разность: АDВ=(А\В)È(В\А);

Ø Дополнение: =I\A={x|xÎI и xÏA}.

Система множеств X={X1, X2,….Xn} называется разбиением множества А, если она удовлетворяет следующим условиям:

Ø XiÎX и XÌA;

Ø XiÎX, XjÎX и XiÇXj=Æ;

Ø .

Свойства операций пересечения и объединения являются двойственными при замене знаков È на Ç, Æ на I и наоборот, поэтому основные тождества и законы алгебры множеств можно записать следующим образом:

1. , ;
2. , ;
3. , ;
4. , ;
5. , ;
6. .  
7. , ;
8. , ;
9. , .
10.
11.

 

Пример 1. Задать различными способами множество А всех четных чисел 2, 4, 6, …., не превышающих 1000.

Решение. 1. Перечислением: А={2, 4, 6, 8, 10, …, 998, 1000};

1. Описанием: А={x|xÎN и х/2ÎN, N£1000}; (N – множество натуральных чисел 1, 2, 3, ….)

2. Порождающей процедурой: а) 2ÎА; б) если хÎА, то (х+2)ÎА;

в) х£1000.

 

Пример 2. Верно ли, что: 1). {{1,2}, {2,3}}={1,2,3}? 2).{{1,2}}={1,2}?

Решение. 1). Нет, так как элементами первого множества являются подмножества {1,2} и {2,3}, а второго – элементы 1,2,3.

2). Нет, так как первое множество одноэлементное, состоящее из одного элемента - подмножества, а второе имеет два элемента 1 и 2.

 

Пример 3. Перечислить элементы следующих множеств:

1). А={a|aÍB, B={1,2,3}};

2). A={a|aÎB, B={1,2,3}}.

Решение. 1). Так как аÍВ, а В – трехэлементное множество, то имеется 23=8 подмножеств: А={{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, Æ}.

2). Так как аÎВ, то А=В={1,2,3}.

 

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

Решение. Используя тождества алгебры множеств, получаем

 

Пример 5. Упростить выражение

Решение. Используя законы и тождества алгебры множеств, получаем:

 

Пример 6. Построить диаграммы Венна для множеств А, В, С, DÌI, если АÈВÌСÈD, , .

Решение. Одно из возможных решение может быть представлено следующей диаграммой:

 
 

Пример 7. Опрос 100 студентов, изучающих иностранные языки, показал: английский язык изучают 29 студентов, немецкий –30, французский –9, только французский - 1, английский и немецкий – 10, немецкий и французский – 4, все три языка – 3 студента. Сколько студентов не изучают ни одного языка? Сколько студентов изучают только немецкий язык? При решении использовать диаграммы Венна.

Решение. Введем обозначения: I – множество всех опрошенных студентов; А – множество студентов, изучающих английский язык; Н – множество студентов, изучающих немецкий язык; Ф – множество студентов, изучающих французский язык (См. диаграмму Эйлера-Венна на рис. 1.1)

По условию задачи очевидно, что =3, тогда =4-3=1; 10-3=7. В таком случае только немецкий язык изучают 30-7-3-1=19 студентов.

 
 

Из условия задачи также слежует, что 9-1-1-3=4, а поэтому только английский язык изучают 29-4-3-7=15 студентов. Тогда число студентов, не изучающих ни одного языка, будет равно 100-(1+1+3+4+7+15+19)=50 студентов.

 

Рис. 1.1

 

Пример 8. Доказать аналитически: .

Решение. Введем обозначения: ; .

а). Пусть , тогда имеет место либо , либо . Если , тогда и и в таком случае и или, что тоже самое, , т.е. . Если , тогда можно записать и одновременно. Откуда, очевидно, и в этом случае , т.е. .

Итак, если , то . Следовательно,

б). Пусть . Тогда и . Если , то либо либо Но если , то (см. п.а) . Если же , тогда Из последнего следует, что и т.е. , или, что тоже самое, , т.е. .

Итак, если то . Следовательно, .

Из пп. а и б следует, что и . Следовательно, D=E, т.е. . Тождество доказано.

 

Пример 9. Доказать, что для произвольных множеств А и В имеет место соотношение .

Решение. Для доказательства используем метод от противного, т.е. предположим, что . Тогда

Из АÍВ Þ если аÎА, то аÎВ. (1)

С другой стороны, из Ë Þ существует такой элемент а, что и Þ . (2)

Но с учетом (1) и (2)

Þ Þ =Æ, т.е. получили противоречие.

Следовательно, предположение ложно и поэтому , т.е. .

Аналогично можно показать, что и, значит, , что и требовалось доказать.

 

Задачи для самостоятельного решения.

 

№ 1.1. Пусть А={{1,2,3}, {1,3}, 1, 2}. Верно ли, что {1, 2}ÎА?

{1, 2}ÌA?

№ 1.2. Перечислить элементы множества

, n=1, 2,…}.

 

№1.3. Перечислить элементы следующих множеств:

 

№ 1.4. Перечислите все элементы множества

 

№1.5. Пусть А – произвольное множество. Что представляют собой следующие множества:

 

№ 1.6. Множество А состоит из натуральных чисел, делящихся на 4, множество В – из натуральных чисел, делящихся на 10, множество С – из натуральных чисел, делящихся на 75. Из каких чисел состоит множество

 

№ 1.7. Даны произвольные множества А, В, С такие, что:

1. и

2. и

Чему равно

 

№ 1.8. Даны произвольные множества А, В и С такие, что . Чему равно

 

№ 1.9. Даны множества:

а). А={h,o,t} и B={t,o,o,t,h};

б). A={r,e,s,t} и В={s,t,r,e,e,t}.

Верно ли, что

 

№ 1.10. Известно, что а). б). . Каковы следствия из этих уравнений?

 

№ 1.11. Задано, что S={a1, a2, a3}, причем известно, что , A={a1, a2}; , B={a2, a3}; ; C={a2}. Найти элементы следующих множеств:

 

№ 1.12. Пусть I={1,2,3,4,5}, X={1,5}, Y={1,2,4}, Z={2,5}.

Найти множества:

а) ; б) в) ; г)

д) е) ж) з) и)

к) л)

 

№ 1.13. Пусть I={a,b,c,d,e,f}, A={a,b,c}, B={f,e,c,a}, C={d,e,f}.

Найти множества:

а) б) в) г) д) е) ж)

з) и)

 

№ 1.14. Даны два произвольных множества А и В такие, что Что представляют собой множества и

 

№ 1.15. Даны два произвольных множества С и D такие, что Что можно сказать о множествах и

 

№ 1.16. Дано произвольное множество Х. Найти множества: б) в) г) .

 

№ 1.17. Какие из следующих утверждений справедливы:

а) б) в) г) д)

 

№ 1.18. Сформулируйте следующее утверждение на языке множеств: даны множества А, В и С; определить множество, включающее в себя только два из этих множеств.

 

№ 1.19. Решите предыдущую задачу при условии, что множества А, В и С взаимно не пересекаются.

 

№ 1.20. Даны множества V, W, Y, X и Z. Определить множество, включающее по крайней мере два из множеств V, W, X и Y и не включающее Z.

 

№ 1.21. Упростить выражения:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

16)

17) .

 

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

1)

2)

3)

4)

5)

 

№ 1.23. Для произвольных множеств А, В, С, D Ì I построить диаграммы Эйлера-Венна при условии:

1)

2)

3)

4) .

 

№1.24. С помощью диаграмм Эйлера-Венна установить справедливость каждого из следующих утверждений относительно произвольных множеств А, В, С Ì I:

1)

2) если и , то

3) если и то

4)

 

№ 1.25. показать с помощью диаграмм Эйлера Венна, какое из двух множеств и является подмножеством другого.

 

№ 1.26. Как можно представить следующие множества, используя диаграммы Эйлера-Венна:

{A, {A}}, {{a}, {b}}, {X, Y, Z},

где Х={x|х=1 или (х-2)ÎХ},

Y={х|х=3 или (х-3)ÎY},

Z={x|x=2 или (х-2)ÎZ}?

 

№ 1.27. Пусть даны множества А, В и С. С Í ВДоказать, что:

а) б) в) г) ;

д)

 

№ 1.28. Доказать, что если то .

 

№ 1.29. Доказать, что

 

 


Дата добавления: 2015-02-10; просмотров: 90; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
Создание объектов спецификации в сборочном чертеже | В) Сколько студентов изучают немецкий и французский язык, но не
lektsii.com - Лекции.Ком - 2014-2019 год. (0.043 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты