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

Цель работы: Изучить основные операции над множествами: объединение, пересечение, разность, дополнение.

Теоретические сведения

В математике понятие “множество” является исходным и не подлежит точному определению. Поэтому набор или совокупность каких-либо объектов, обладающих общими свойствами, на интуитивном уровне, называют множеством. Например, в математике такими множествами являются множество целых чисел Z (INTEGER), множество вещественных чисел R (REAL) и др. “Нематематические” объекты также формируют множества. Объекты, включаемые в множество, называют его элементами

Общим обозначением множества служит пара фигурных скобок {, }, между которыми перечисляют все элементы множества или указывают свойства, которыми должны обладать элементы формируемого множества. Для обозначения множества в тексте используют прописные буквы латинского алфавита A, B, C, ...X, Y, Z. Для обозначения элементов множества в тексте используют строчные буквы латинского алфавита a, b, c,...x, y, z.

Для обозначения принадлежности элемента x множеству X используют знак ““ - знак принадлежности, т.е. xX. Если элемент х не принадлежит множеству Х, то используют знак ““, т.е. хХ.

Число элементов счетного конечного множества Х называют его мощностью и обозначают так: |X|=n.

Если всякий элемент множества Х является также элементом другого множества Y, то множество X называют подмножеством множества Y. Для обозначения этого в тексте используют знак ““ - знак включения, т.е. ХY. Если множество Х не включено в множество Y, т.е. не все его элементы принадлежат Y, то используют знак ““ - знак невключения, т.е. XY.

Если XY и YX, то X=Y.

Если XY и XY, то множество Х называют собственным подмножеством множества Y. Для указания в тексте этого факта используют знак строгого включения - ““, т.е. XY.

Множество, не содержащее ни одного элемента, называют пустым множеством и обозначают знаком , т.е. ={ }. Пустое множество может быть подмножеством любого множества.

Множество, содержащее все элементы всех подмножеств, принимающих участие в решении какой-либо задачи, называют основным или универсальным множеством и обозначают символом U, т.е. если в решении какой-либо задачи принимают участие множества А={a} и B={b,c}, то U ={a,b,c}.

Максимально возможное число подмножеств универсального множества называют семейством подмножеств универсального множества. Это семейство включает пустое подмножество, само универсальное множество и множества, сформированные по одному, два, три и т.д., элементов универсального множества. Семейство подмножеств универсального множества обозначают символом B(U) и называют булеаном множества U.

Например, если U={a,b,c}, B(U)={, {a}, {b}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c}}.

Легко видеть, что число элементов булеана B(U) зависит от числа элементов универсального множества U по формуле: |B(U)|=2^|U|.

Задание множества может быть выполнено перечислением элементов внутри фигурных скобок, либо описанием его характеристических свойств.

При задании множества описанием его характеристических свойств между фигурными скобками после указания текущего значения элемента множества Х, т.е. хХ, ставится знак ““, вслед за которым указывают характеристическое свойство элементов множества, т.е. Р(х). При подстановке конкретного значения х=а выражение Р(а) принимает значение “истина” или “ложь”, т.е. Р(х) есть логическая функция, которую иначе называют-“предикат”.

Множество значений х=а1, х=а2, х=а3 и т.д., для которых Р(х=а_i)=“истина” формирует множество Х={а1, а2, а3,...}.

Множество может быть задано характеристическим вектором – вектором, размерность которого равна количеству элементов в универсальном множестве. Каждый компонент характеристического вектора множества А равен либо 1 (если соответствующий элемент универсального множесва содержится в А), либо 0 (если соответствующий элемент универсального множесва не содержится в А).

Над множествами можно проводить ряд традиционных действий. А именно:

1.Объединение. Так называется множество C, которое строится по заданным множествам A и B следующим образом: в него включаются все элементы из A и все элементы из B. Обозначение:

2. Пересечение. Так называется множество C, которое строится по заданным множествам A и B следующим образом: в него включаются все элементы, принадлежащие одновремен-но множеству A и множеству B. Обозначение:

3.Вычитание. Так называется множество C, которое строится по заданным множест

вам A и B следующим образом: в него включаются все элементы из A, не принадлежащие мно-жеству B. Обозначение: C=A\B Часто при включении вместо A\B пишут и говорят о дополнении подмножества B.

4. Произведение. Так называется множество C, которое строится по заданным множествам A и B следующим образом: в него включаются все упорядоченные пары , где . Обозначение: Если , то называется декартовым квадратом множества A.

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

A E E - универсальное множество

B А, В - множества

Рис.1 Диаграмма Венна.

Пусть E = {b, c, d, e}; A = {b, c, d} B = {c, e} (рис.1)

Задание

1. Пусть U={a,b,c,d,e,f,g,h,k}

Задать пересечение, объединение, разность множеств S и T, декартово произведение S и T, дополнение множества S до множества U, дополнение множества S∩T до множества U. Изобразить с помощью диаграмм Венна.

Привести множество всех подмножеств множества S.

Варианты заданий.

1) S={a,b,c} T={b,c,f}

2) S={d,f,g} T={d,g,h}

3) S={a,b,c,d} T={d,e,f,g}

4) S={h,g,d} T={a,b,d,g}

5) S={g,d,b,c} T={b,c,d}

6) S={g,d,f,a} T={b,c,e}

7) S={a,b,e,f} T={с,e,f,g}

8) S=u T={c,k,b,h}

9) S={a,b,c,k} T={k,b,c,f}

10) S={d,f,g,k} T={k,d,g,h}

11) S={a,b,c,d,k} T={k,d,e,f,g}

12) S={h,g,d,k} T={k,a,b,d,g}

13) S={g,d,b,c,k} T={k,b,c,d}

14) S={g,d,f,a,k} T={k,b,c,e}

15) S={a,b,e,f,k} T={k,b,c,f}

16) S={k,a,b,c} T={b,c,f,k}

17) S={k,d,f,g} T={d,g,h,k}

18) S={k,a,b,c,d} T={d,e,f,g,k}

19) S={k,h,g,d} T={a,b,d,g,k}

20) S={k,g,d,b,c} T={b,c,d,k}

21) S={k,g,d,f,a} T={b,c,e,k}

22) S={a,b,k} T={b,k,f}

23) S={a,b,k,d} T={d,e,f,g}

24) S={g,d,b,k} T={b,k,d}

25) S={d,k,g} T={d,g,h}

26) S={g,d,k,a} T={b,k,e}

27) S={k,g,d} T={a,b,d,g}

28) S={a,b,k,f} T={e,f,g}

Контрольный тест

1. Заданы множества: A = {a, b, c, d}, B = {c, d, e}, C = {a, c, f, k}. Вычислить (A U C)∩ B.

• {a, c, d, e, f, k}

• {a, c, d, e}

• {c, d, f}

• {c, d}

2. Заданы множества: A = {a, b, c, d}, B = {c, d, e}, C= {a, c, f, k}. Вычислить (A\B)UC.

• {c, d, e, f, k}

• {a, b, c, d, e, f, k}

• {a, b, c, f, k}

• {b, d, k}

3. Заданы множества: A = {a, b, c, d}, B = {c, d, e}, C = {a, c, f, k}. Вычислить (B ∩ C)\A.

• {a, b, c}

• {c, d, e, f}

• {b, d, k}

• Ø

4. Заданы множества: A = {a, b, c, d}, B = {c, d, e}, C = {a, c, f, k}. Вычислить (A ∩ B)X(A ∩ C).

• {a, b, c, d, e, f, k}

• {(c, a), (c, c), (d, a), (d, c)}

• {(c, a), (c, d), (a, c), (c, c)}

• Ø

5. Перечислите элементы множества A: A = {x: x ε Z, 10 < = x < = 17}.

• A = Ø

• A = {11, 12, 13, 14, 15, 16}

• A = {-17, -16, ..., 15, 16, 17}

• A ={10, 11, 12, 13, 14, 15, 16, 17}

6. Перечислите элементы множества A: A = {x: x ε Z, x ^ 2 < 24}.

• A = {1, 2, 3, 4}

• A = {0}

• A = {-4, -3, -2, ..., 3, 4}

• A = {0, 1, 2, 3, 4}

7. Перечислите элементы множества A: A = {x: x ε Z, x ^ 2 - 5* x + 5 = 0}.

• A = Ø

• A = {3, -1}

• A = {1,5}

• A={1}

8. Упростить (A ∩ C) U B.

• (A U B) ∩ (C U B) .

• (A ∩ B) U (C ∩ B)

• (A U C) ∩ (C U B)

• (B ∩ C) U (C ∩ B)

9. Упростить (A ∩ B) ∩ C

• A ∩ B ∩ C

• A U B U C

• A U B ∩ C

• A ∩ B U C

10. Упростить (A \ B) \ C.

• (A U B) \ C

• (A ∩ B) \ (A∩ C)

• A \ (B U C)

• (A U B) \ (A U C)

11. U = {1,2,3,4,5,6} - универсальное множество. A = {1,2,4,5}. Найти характеристический вектор для A.

• (0, 1, 1, 0, 0, 1)

• (0, 1, 1, 1, 1, 0)

• (1, 1, 0, 1, 1, 0)

• (1, 1, 1, 1, 0, 0)

12. U = {1, 2, 3, 4, 5, 6} - универсальное множество. B = {3, 5}. Найти характеристический вектор для B.

• (1, 0, 0, 0, 0, 1)

• (0, 0, 1, 0, 1, 0)

• (1, 0, 1, 0, 0, 0)

• (0, 1, 0, 0, 1, 0)

13. U = {1,2,3,4,5,6} - универсальное множество. A = {1,2,4,5}, B = {3,5}. Найти характеристический вектор для A ∩ B.

• (0, 0, 0, 0, 0, 1

• (0, 0, 1, 0, 0, 0)

• (1, 1, 1, 1, 1, 0)

• (1, 1, 0, 1, 0, 1)

14. U = {1,2,3,4,5,6} - универсальное множество. A = {1,2,4,5}, B = {3,5}. Найти характеристический вектор для A Δ B.

• (0, 1, 1, 1, 1, 1)

• (1, 1, 1, 1, 0, 0)

• (1, 1, 0, 1, 1, 1)

• (1, 1, 0, 0, 1, 1)

15. Множество S = {2, 5, 8, 11, ...} записать в виде порождающей процедуры.

• S = {x : x = n + 3, n ε N}

• S = {x : x = 2n + 3, n ε N}

• S = {x : x = 3n - 1, n ε N}

• S = {x : x = 3n + 1, n ε N}

Лабораторная работа № 2 Отношения и функции.

Цель работы: Изучить основные определения отношений и функций и научиться определять их свойства

Теоретические сведения

Если элементы двух множеств X и Y различной природы сопоставить между собой по какому-либо правилу, т.е. для каждого хХ указать один или несколько элементов множества Y, то может быть сформировано множество пар (х;y), являющееся подмножеством прямого произведения множеств Х и Y, т.е.

{(x;y)|xX, yY}(X  Y).

Множество Х чаще всего называют областью определения, а множество Y-областью значения. Значение yY называют образом для конкретного значения х_iХ, а значение хХ - прообразом для конкретного значения y_jY.

Сопоставление двух множеств Х и Y, когда для каждого элемента х_iХ существует несколько образов, т.е. |{y}_xi|>1, называют соответствием. Множество пар (x;y) соответствия обозначают Q, т.е.

Q={(x;y)|xX, yY}(X  Y).

Правило соответствия удобно записать в операторной форме q:XY, где q-оператор соответствия.

Проекция на первую компоненту Пр₁{(x;y)} формирует область определения Х⁰, где Х⁰Х, а на вторую компоненту Пр₂{(x;y)}- область значений Y⁰, где Y⁰Y.

Область определения соответствия может быть задана на прямом произведении множеств Х, т.е. _i=1ⁿХ_i=Хⁿ.

В этом случае

Q={(x₁;x₂;...;x_n;y)|x_iX;yY}XⁿY

q:XⁿY.

Каждому соответствию q может быть найдено обратное соответствие q^-1. Для этого достаточно поменять местами компоненты пары соответствия, т.е.

Q^-1={(y;x)|xX;yY}YX;

Q^-1={(y;x₁;x₂;...x_n)| x_iX_i;yY}YXⁿ.

Для двух соответствий q₁:XY и q₂:YZ можно найти их композицию, т.е. сформировать новое соответствие q=(q_1q₂):XZ при условии, что элементы области значений первого соответствия есть элементы области определения второго соответствия: {(x;z)|xX; zZ; Пр₂{(x;y)|xX; yY}=Пр₁{(y;z)|yY; zZ}}.

Например, если Х={1;3;5}, Y={2;4;6}, Z={7;9} и

для q₁:XY имеем Q₁={(1;2);(1;4);(3;4);(5;6)}(XY),

для q₂:YZ имеем Q₂={(2;9);(4;7);(4;9);(6;7)}(YZ), то

для q:XZ имеем Q={(1;9);(1;7);(3;7);(3;9);(5;7)}(XZ).

Соответствие, когда каждому прообразу найдется единственный образ, но не наоборот, называют отображением. То есть отличительной особенностью отображения является условие |{y}_xi|=1.

Форма записи отображения не отличается от записи соответствия.

В математике часто отображение называют функцией и обозначают символом f. В этом случае оператор функции есть f:XY или f:XⁿY.

Часто вместо такой записи используют запись:

y=f(x), где xX, yY или y=f(x₁;x₂;...;x_n), где (x₁;x₂;...;x_n)Xⁿ, yY, для которых элементы (х) или (x₁;x₂;...;x_n) называют аргументами функции или ее независимыми переменными, y -значением функции.

При этом, если для каждого значения xX или (x₁;x₂;...;x_n)Xⁿ имеется один элемент yY, то функция называется всюду определенной, в противном случае -частично определенной. Если область значения функции совпадает с множеством Y, то функция называется сюръективной. В случае, когда каждому образу соответствует единственный прообраз, функция называется инъективной. Функция, одновременно обладающая свойствами инъективности и сюръективности, называется биективной.

Если представить два множества Х и Y в прямоугольной системе координат (см. рис.2), то узлы прямоугольной решетки есть элементы прямого произведения (x;y)=(XY). Подмножество, ограниченное линией на рис. 2а), не является функцией, т.к. для х₄ есть два значения y₂ и y₃; подмножество, ограниченное линией на рис. 2б), является всюду определенной биективной функцией, т.к. каждому x_iX соответствует единственное значение yY; подмножество, ограниченное линией на рис. 2в), является частично определенной функцией, т.к. для х₃ нет значения yY.

Рис. 2. Графики функций y=f(x).

Соответствие, заданное между двумя или несколькими элементами одного множества Х, называют отношением.

Формальная запись отношения не отличается от записи для соответствий, если принять вместо Y множество Х. Множество пар отношений обозначают символом R. Например,

R={(x₁;x₂)|x_1,2X}X²;

R={(x₁;x₂;...;x_n+1)|x_iX}XⁿX=Хⁿ⁺¹.

Если (n+1)=1, то отношение называют унарным или одноместным. Такое отношение выделяет в множестве подмножество, удовлетворяющее заданному свойству.

Если (n+1)=2, то отношение называют бинарным или двухместным. Такое отношение позволяет сравнить или упорядочить попарно элементы заданного множества.

Если (n+1)=3, то отношение называют тернарным или трехместным, если равно 4, то четырехместным и т.д.. Наибольшее распространение имеют бинарные отношения в связи с удобством их описания.

Отношения можно задавать перечислением всех его элементов, т.е. формированием списков, или с помощью матриц. При матричном описании бинарного отношения удобно воспользоваться квадратной матрицей (ХХ), строки и столбцы которой есть элементы множества Х, а на пересечении i-ой строки и j-го столбца ставят знак “1”, если предикат Р²(x_i;x_j)=“истина” и знак “0”, если предикат Р²(x_i;x_j)=”ложь”, т.е.

Например, для множества целых чисел Z и отношения r₄(x₁;x₂) матрица представлена в таблице 2

Таблица 2.

При графическом представлении отношения все элементы множества Х изображаются точками на плоскости листа и называются вершинами графа, а отношения между i-ым и j-ым элементами множества Х-линиями, которые называют ребрами ( или дугами) графа. В целом фигура, полученная на плоскости листа, называется графом. На рис.3 представлен граф для заданного множества целых чисел и отношения r₄(x_i;x_j).