Лекции по дискретке (1021001), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Решение. 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). Так как аВ, а В – трехэлементное множество, то имеется 2³=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 студентов.

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

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

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

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

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

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

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

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

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

Из АВ  если аА, то аВ. (1)

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

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

  =, т.е. получили противоречие.

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

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

Пример 10. {(1,2), (2,2), (Иванов, Петров)} есть функция с областью определения {1, 2, Иванов} и областью значений {2, Петров}.

Пример 11. {(1,2), (1,3), (2,5)} не является функцией, т.к. различные элементы (1,2) и (1,3) имеют одинаковую первую координату.

Пример 12. Множество {(a,b), (c,b), (e,d), (k,m)} есть функция, а подмножество этого множества {(a,b), (e,d)} является сужением этой функции на множество {a,e}.

Отображение представляет собой отображение множества Х в самого себя и определяется парой (Х, R), где . В этом случае для обозначения данного отображения используется термин отношение и вводят специальную символику: yRx – у находится в отношении R к х.

Подмножество называется n-местным отношением между А₁, А₂, …..A_n. Если n=2, то R называется бинарным отношением.

Пример 13. Множество {(3,4), (4,6), (7,9), (4,12)} будучи множеством упорядоченных пар натуральных чисел, есть бинарное отношение на N, где N – множество натуральных чисел.

Отношение R называется ( ):

рефлексивным, если для любого имеет место ;

антирефлексивным, если ни для какого не выполняется ;

симметричным, если для пары из aRb следует bRa;

антисимметричным, если из a_iRa_j и a_jRa_i следует, что a_i=a_j;

транзитивным, если для любых a, b, c из aRb и bRc следует aRс.

Отношение R называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Обозначается символом .

Пример 14. Докажите, что отношение равенства «=» на любом множестве является отношением эквивалентности.

Решение. Действительно, для данного отношения выполняются свойства: рефлексивности (а=а); симметричности (а=в в=а); транзитивности [(а=в и в=с) а=с].

Отношением предпорядка на множестве А называется отношение , если оно рефлексивно и транзитивно.

Отношением порядка называется отношение, если оно рефлексивно, антисимметрично и транзитивно.

Отношением строгого порядка называется отношение, если оно антирефлексивно, антисимметрично и транзитивно.

Пример 15. Задано бинарное отношение R на множестве М={1, 2, 3, 4}. Является ли оно рефлексивным, симметричным, антисимметричным, транзитивным? Найти область определения _R, область значений _R, обратное отношение R^-1, пересечение и объединение отношений R и R^-1

R={(1,1), (1,2), (1,3), (1,4), (4,1), (4,2), (4,3), (4,4).

Решение.

Отношение R, заданное на множестве М, называется рефлексивным, если для всякого х из этого множества хRх истинно. Заданное отношение не является рефлексивным, так как нет пар (2,2) и (3,3).

Отношение R, заданное на множестве M называется симметричным, если на этом множестве из xRy следует yRx. Заданное отношение не является симметричным, т.к., например, пара (1,2) R, а (2,1) R.

Отношение R, заданное на множестве M называется антисим-метричным, если на этом множестве из xRy и yRx следует x=y. Заданное отношение не является антисимметричным, так как ему принадлежат пары (1,4) и (4,1), но 14.

Отношение R, заданное на множестве M называется антирефлексивным, если для любого xRx ложно. Заданное отношение антирефлек-сивно, так как (уже было показано) нет пар (2,2) и (3,3).

Отношение R, заданное на множестве M называется транзитивным, если на этом множестве из xRy и yRz следует xRz. Заданное отношение является транзитивным, так как для любых двух пар (a,b) и (b,c) следует, что (a,c) R, где а, в, с М.

Областью определения отношения R называется множество _R ={x| (у) xRy}. Следовательно, областью определения R является двухэлементное множество {1, 4}.

Областью значений отношения R называется множество _R={y|(x) xRy}. Следовательно, областью значений является все множество М={1, 2, 3, 4}.

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

Обратное отношение R^-1={(1,1), (2,1), (3,1), (4,1), (1,4), (2,4), (3,4), (4,4)}.

Пересечение R и R^-1 равно R R^-1={(1,1), (4,1), (1,4), (4,4)}.

Объединение R и R^-1 равно R R^-1={(1,1), (1,2), (1,3), (1,4), (4,1), (4,2), (4,3), (4,4), (2,1), (3,1)}.

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

№ 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.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={a₁, a₂, a₃}, причем известно, что , A={a₁, a₂}; , B={a₂, a₃}; ; C={a₂}. Найти элементы следующих множеств:

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

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

Характеристики

Список файлов лекций