Множества и операции над ними

Вид материала

Документы

Содержание R – множество всех действительных чисел; N N и x делит y}; 2)   = {(x,y) | x,y R Z, R={(a,b), | a+b = 0}; в) A={1,2,3,4,5,6,7,8,9,10}, aRb, если a+b > 0; г) A={1,2,3,4,5,6,7,8,9,10}, aRb, если a+b четное; д) A Работа программы Работа программы

Подобный материал:

• Тема №1. Множества и операции над ними, 74.19kb.
• Повторение: множества и операции над ними; рациональные выражения (Мерзляк, 4.69kb.
• Программа курсу «Математический анализ», 69.36kb.
• Программа вступительного экзамена в аспирантуру цэми ран по специальности 08. 00., 84.35kb.
• Для кафедр пм и к вопросы по курсу «Дискретная математика». 19. 05. 2010г, 52.29kb.
• Программа курса "Основы дискретной математики", 14.41kb.
• Календарно-тематический план учебная дисциплина: «Математика», 34.71kb.
• Вопросы к экзамену по математическому анализу (зимняя сессия), 53.55kb.
• Программа по математике для поступающих в рамэк, 92.57kb.
• Множества, 45.64kb.

Тема 1 Множества и операции над ними Занятие 1

1. Какой способ использован при задании множеств:
   а) IVT = {множество групп факультета ИВТ}; б) P42 = {множество студентов группы П-42}? Верно ли, что: P42  IVT? P42  IVT?
   
2. Перечислить все элементы множества {x | x – целое и x² < 49}.
   
3. Описать множество {3, 6, 9, 12, 15, 18, 21, 24} при помощи характеристического свойства.
   
4. Перечислить все подмножества множества {a,b,c}.
   
5. Справедливо ли равенство: {{a,b},{b,c}} = {a,b,c}?
   
6. Пусть E = {0, 2, 4, 6,…} – множество всех целых четных чисел; N = {1,2,3,…} – множество натуральных чисел. Определить, из каких чисел будут состоять множества: E  N, E  N, E \ N, N \ E?
   
7. Доказать, что   {}.
   
8. Установить истинность или ложность каждого из следующих утверждений: а)    ; б)    A, где A – произвольное множество; в)    ; г)    ; д)    A, где A – произвольное множество.
   
9. Определить количество элементов в каждом множестве:
   а)  {,{}}; б)  {{,{}}}; в)  {1,2,3,{1,2,3}}; г)  {,{},a,b,{a,b},{a,b,{a,b}}}; д)  {,{},{,{}}}.
   
10. Доказать, что если множества A  B и B  C, то A  C.
    
11. Пусть даны множества A = {1,2,3,4,5,6,7}, B = {4,5,6,7,8,9,10}, C = {2,4,6,8,10}, U = {1,2,3,4,5,6,7,8,9,10}. Определить множества:
    а)  A  C; б)  A  B; в)  (A  B)  C; г)  A \ B; д)  U\(A  B); е) A B; ж)  A  (B  C); з)  A Δ B; и)  (A  C) \B; к)  B Δ C; л)  (A \ )  (A \ A).
    
12. Определить, какие из следующих утверждений верны, а какие – нет:
    а)  A   = A; б)  A Δ A = ; в)  если A  B, то A  B = A; г)  A \ A = A; д)  A   = A; е)  если A  B = A, то B  A; ж)  A \  = A; з)  A Δ  = A; и)  если A  B, то A  B = A;
    к)  A  B =A B; л)  A   = A; м)  если A  B = A, то  B  A.
    
13. Доказать, используя определения операций  и , что для любых множеств A, B, C выполняется: а) A(BC) = (AB)(AC); б) (A  B)  A = A; в) (A  B)  A = A; г) A \ B = A B.
    
14. Определить операции , , \ через: а) Δ, ; б) Δ, ; в) \, Δ.
    
15. Доказать, что A\(A\B) = AB. Проиллюстрировать графически.
    
16. Доказать, что A\B = A\(AB). Проиллюстрировать графически.
    
17. Пусть множества A, B, C удовлетворяют соотношениям: B  A, A  C = . Решить систему уравнений:
    
18. Пусть множества A, B, C удовлетворяют соотношениям: B  A  C. Решить систему уравнений: .
    
19. Пусть множества A, B, C удовлетворяют соотношениям: B  A  C. Решить систему уравнений: .
    
20. Доказать аналитически, используя свойства операций над множествами, и проиллюстрировать графически:
    а) A\(A\B)=AB; б) A\B=A\(AB); в) AΔ(AΔB)=B;
    г) AΔB=A\B, если BA; д) (AB)\(AB)(A\B)(B\A).
    
21. Указать такие множества A, B, C, что (A\B)\С  A \ (B \ С).
    
22. При каком условии на множества A, B, C выполняется
    (A\B)\С = A \ (B \ С)?
    
23. Пусть A={a,b,c,d}. Какие из следующих классов множеств составляют разбиение или покрытие множества A? а) {{a,b},{a,c},{c,d}}; б) {{a,d},{c},{d},{b}}; в) {{a},{c,d}}; г) {{a},{b,c,d}}.
    
24. Выписать все варианты непустых разбиений множества A={a,b,c,d}.
    

Тема 2 Отношения и функции Занятие 2

25. Пусть A = {1,2,3}, B = {a,b}. Определить:
    а) A  B; б) B  B; в) A  ; г) B  A; д) A Δ B.
    
26. Выяснить, справедливы ли равенства. Если нет – привести контрпример.
    а)  (AB)C = (AB)(BC); б)  (AB)C = (AС)(BC);
    в)  (AB)(CD) = (AB)(CD); г)  (AB)(CD) = (AC)(BD); д)  (AB)(CD) = (AC)(AD)(BC)(BD).
    
27. Найти область определения и множество значений отношений:
    а)  {(a,1),(a,2),(c,1),(c,2),(c,4),(d,5)}; б)  {(1,2),(2,4),(3,6),(4,8),…};
    в)  {(x,y) | x,yR и x = y²}; г)  {(x,y) | x,yI и x² + y² 16}.
    
28. Установить, какие из приведенных совокупностей элементов составляют разбиение множества A={1,2,3,4,5,6,7}. Для тех, что составляют, перечислить элементы соответствующего отношения R, такого, что aRb  a,b одному A_i: а) {{1,2},,{3,4,5},{6,7}}; б) {{1,2},{3,4,5},{6,7}}; в) {{1,7},{3,4,6}}; г) {{1,5},{3,4,5},{2,6,7}}; д) {{1,2,3,4,5,6,7}}.
    
29. На плоскости задана декартова прямоугольная система координат. Указать точки плоскости, соответствующие элементам отношения R  N², если: а) R = {(x,y) | x  6, y  4, x > y}; б) R = {(x,y) | x  10, y  10, x делит y}.
    
30. Представить заданное бинарное отношение R на множестве А списком пар; построить его графически; выписать область определения и область значений: А={1,2,3,4,5}, R={(x,y)| остаток от деления y на x равен 1}.
    
31. Пусть А={1,2,3,4}, отношения R₁,R₂  А²: R₁={(x,y) | 2x  y}, R₂={(x,y)| x+3y четно}. Построить R₁, R₂, R = R₂◦R₁, выписать области определения и области значений всех трех отношений.
    

Занятие 3

32. Даны множества: A = {1,2,3,4,5}, B = {6,7,8,9}, C = {10,11,12,13}; отношения: R  AB, S  BC: R ={(1,7),(4,6),(5,6),(2,8)}, S={(6,10),(6,11),(7,10),(8,13)}. Определить: а)  R^–1 и S^–1; б)  S◦R; в)  R^–1◦S^–1; г)  S◦S^–1 и S^–1◦S.
    
33. Пусть R – множество всех действительных чисел; N = {1,2,3,…}. Найти:
    а) ^–1; б) ◦; в) ^–1◦; г) ◦^–1, если отношение  определено:
    1)   = {(x,y) | x,y N и x делит y};
    2)   = {(x,y) | x,y R и x+y  0};
    3)   = {(x,y) | x,y R и 2x3y };
    
34. Определить, являются ли указанные отношения на множестве N рефлексивными, транзитивными, симметричными, антисимметричными?
    а) {(m,n) | m и n взаимно просты}; б) {(m,n) | m делится на n}; в) {(m,n) | m – n =3}; г) {(m,n) | (m + 2n ) кратно 3}.
    
35. Определить на множестве {a,b,c} отношение:
    а) эквивалентности; б) частичного порядка;
    в) рефлексивное, симметричное, не транзитивное;
    г) рефлексивное, транзитивное, не симметричное;
    д) симметричное, транзитивное, не рефлексивное.
    
36. Является ли каждое из приведенных ниже отношений R  A² отношением эквивалентности? Если да – построить классы эквивалентности:
    а) A=P (M), если M={a,b,c,d}, sRt, если s и t имеют одинаковую мощность;
    б) A= Z, R={(a,b), | a+b = 0};
    в) A={1,2,3,4,5,6,7,8,9,10}, aRb, если a+b > 0;
    г) A={1,2,3,4,5,6,7,8,9,10}, aRb, если a+b четное;
    д) A=Z, R={(a,b), если kZ | a–b = 5k};
    е) A={множество прямых на плоскости}, nRm, если прямые n и m пересекаются;
    ж) A={множество прямых на плоскости}, nRm, если прямые n и m параллельны.
    
37. Пусть C = {1,2,3} и X – булеан множества C с заданным на нем отношением частичного порядка . Определить (если это возможно):
    а) точную верхнюю грань для подмножества X {,{1},{2}};
    б) подмножество X, для которого точной верхней гранью является {1,3};
    в) точную нижнюю грань для X и подмножеств из а) и б).
    
38. Пусть X – множество с заданным на нем отношением частичного порядка . Определить максимальные и минимальные элементы; точные верхнюю и нижнюю грани (если возможно):
    а) X = {,{1},{2},{3},{1,2},{1,3},{2,3}}; б) X = {{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.
    

Занятие 4

39. Пусть f  RR. Найти область определения и область значений следующих функций:
    а) f(x)=x²+4; б) f(x)=(x–2); в) f(x)=1/(x–2); г) f(x)=1/(x²+4).
    
40. Для функций f и g, заданных на множестве действительных чисел, найти f(g(x)) и g(f(x)), если:
    а) f(x) = x²+1; g(x) = x + 3; б) f(x) =x²+2; g(x) = x² + 3;
    в) f(x) = 1 / x; g(x) = 2x + 3.
    
41. Выяснить, какие из следующих функций, у которых область определения и область значений совпадает с действительной числовой осью, являются инъективными, сюръективными, имеют обратную функцию:
    а) f(x) = |x|; б) f(x) = x²+4; в) f(x) = x³+6; г) f(x) = x+|x|; д) f(x) = x(x–2)(x+2).
    
42. На множестве {0,1,2,3,4,5} задать функцию:
    а) не инъективную; б) биективную.
    
43. На множестве N задать функцию: а) не инъективную; б) инъективную, но не сюръективную; в) сюръективную, но не биективную; г) биективную.
    
44. Используя принцип математической индукции, доказать:
    а) неравенство Бернулли: (1+a)ⁿ  1 + an n  N и a > –1, aR;
    б)  n  Z, n > 0 n³ – n делится на три;
    в) ;
    г) ;
    д) 1 + 2 + 2² + 2³ + … + 2^n–1 = 2ⁿ–1;
    е) 1 + 3 + 5 + 7 + … + (2n – 1) = n ².
    

При выполнении лабораторных работ необходимо предусматривать обработку возможных ошибок ввода. Программа не должна «зависать» или вести себя иным некорректным образом ни при каких начальных данных!

Лабораторная работа № 1 Множества и операции над ними

Написать программу, в которой для конечных упорядоченных множеств реализовать все основные операции (, , , \) с помощью алгоритма типа слияния (по материалам лекции 1). Допустима организация множеств в виде списка или в виде массива.

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

1. На вход подаются два упорядоченных множества A и B (вводятся с клавиатуры, элементы множеств – буквы латинского алфавита).

2. После ввода множеств выбирается требуемая операция (посредством текстового меню, вводом определенного символа в ответ на запрос – выбор по желанию автора). Операции: вхождение AB, AB, AB (дополнительно: A\B, B\A, AB).
   
3. Программа посредством алгоритма типа слияния определяет результат выбранной операции и выдает его на экран с необходимыми пояснениями.
   
4. Возврат на п.2 (выбор операции).
   
5. Завершение работы программы – из п.2 (например, по ESC).
   

Дополнительно: возможность возврата (по выбору пользователя) на п.2 или п.1. Выход в таком случае должен быть предусмотрен из любого пункта (1 или 2).

Лабораторная работа № 2 Отношения и их свойства

Бинарное отношение RA² (A – конечное множество) задано списком упорядоченных пар вида (a,b), где a,bA. Программа должна определять свойства данного отношения: рефлексивность, симметричность, антисимметричность, транзитивность (по материалам лекции 3).

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

1. На вход подается: а) множество A из n элементов; б) список упорядоченных пар, задающий отношение R (ввод с клавиатуры).

2. Результаты выводятся на экран (с необходимыми пояснениями) в следующем виде:

а) матрица бинарного отношения размера nn;
б) список свойств данного отношения.

Дополнительно: после вывода результатов предусмотреть возможность изменения списка пар, определяющих отношение. Например, вывести на экран список пар (с номерами) и по команде пользователя изменить что-либо в этом списке (удалить какую-то пару, добавить новую, изменить имеющуюся), после чего повторить вычисления.