Лекции и учебные пособия по системному анализу

Системный анализ

«Теория систем и системный анализ»

И. Б. Родионов

Оглавление    
Лекция 12, «Основные понятия теории множеств» Лекция 14, «Соответствие и функции»

Лекция 13: Операции над множествами. Упорядоченное множество

1. Объединение множеств

Объединение множеств X и Y — это множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств X или Y, т.е. принадлежат X или принадлежат Y.

Объединение X и Y обозначается через X∪Y

Формально x∈X∪Y ⇔ x∈X или x∈Y

Пример 1. Если X={1,2,3,4,5} и Y={2,4,6,8}, то

X∪Y={1,2,3,4,5,6,7,8}

Пример 2. Если X={x:x — отл.гр.}, и Y={x:x — gib.}, то

X∪Y={x:x — или отл., или gib}.

Пример 3. Если X — множество точек левого круга и Y — множество точек правого круга, то

X∪Y — заштрихованная область, ограниченная обоими кругами.

Понятие объединения можно распространить и на большее число множеств, на систему множеств. Обозначим через М={X1,X2, ...,Xn} совокупность n множеств X1,X2, ...,Xn, называемую иногда системой множеств. Объединение этих множеств

∪Xi=∪(X∈M), Х=X1∪X2∪...∪Xn

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

Для объединенных множеств справедливы:

  • X∪Y = Y∪X — коммутативный закон
  • (X∪Y)∪Z = X∪(Y∪Z) = X∪Y∪Z — ассоциативный закон,

справедливость которых вытекает из того, что левая и правая части равенств состоят из одних и тех же элементов.

Очевидно, что X∪∅ = X. Отсюда можно видеть, что ∅ играет роль нуля в алгебре множеств.

2. Пересечение множеств

Пересечение множеств X и Y — это множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству X, так и множеству Y.

Пересечение множеств обозначается X∩Y.

Формально x∈X∩Y ⇔ x∈X и x∈Y

Пример 4. X={1,2,3,4,5} Y={2,4,6,8} X∩Y = {2,4}

Пример 5. Если Х — множество точек левого круга, а Y — множество точек правого круга, то X∩Y представляет собой заштрихованную область, являющуюся общей частью обоих кругов.

Множества X и Y называются непересекающимися (дизъюнктными), если они не имеют общих элементов, то есть если X∩Y=∅.

Пример 7. {1,2,3} и {4,5,6}

В отличие от алгебры чисел, где могут быть три возможности: a<b, a=b, b<a между двумя множествами X и Y может быть одно из 5 cотношений:

X=Y; X⊂Y; Y⊂X; X∩Y=∅ и X и Y находятся в общем положении.

Говорят, что множества X и Y находятся в общем положении, если выполняются три условия:

  1. существует элемент множества X, не принадлежащий Y;
  2. существует элемент множества Y, не принадлежащий X;
  3. существует элемент, принадлежащий как X, так и Y.

Аналогично объединению понятие пересечения можно распространить на систему множеств:

∩X=∩Xi=X1∩X2∩...∩Xn

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

Для пересечения множеств справедливы:

  • X∩Y=Y∩X — коммутативный закон
  • (X∩Y)∩Z = X∩(Y∩Z) = X∩Y∩Z — ассоциативный закон

Заметим также, что имеет место соотношение X∩∅=∅.

Пример 8. A={a,b}, B={b,c}, C={a,c}.

A∩B∩C=∅, хотя A∩B={b}, B∩C={c}

3. Разность множеств

Разность множеств определена только для двух множеств. Разностью множеств X и Y называется множество, состоящее из всех тех и только тех элементов, которые принадлежат X и не принадлежат Y.

Обозначается: X\Y.

Формально: x∈X\Y ⇔ x∈X и x∉Y

Пример 9. (см. Пример 1) X={1,2,3,4,5}, Y={2,4,6,8}, X\Y={1,3,5}, Y\X={6,8}

Разность множеств не обладает свойством коммутативности.

X\Y≠Y\X

Если A\B=∅, то A⊂B — поставить ? обратно

при A∩B≠∅

4. Универсальное множество

Роль нуля в алгебре множеств играет пустое множество. А нет ли такого множества, которое играет роль «1», т.е. удовлетворяет условию: X∪I = X, что означает, что пересечение или «общая часть» множества I и множества X для любого множества X совпадает с самим этим множеством. Это возможно лишь в том случае, если множество I содержит все элементы, из которых может состоять множество X, так что любое множество X полностью содержится в множестве I.

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

Если при некотором рассмотрении участвуют только подмножества некоторого фиксированного множества, то это самое большое множество будем считать универсальным и обозначать I.

Пример 12 (Пример 1). I — множество целых чисел

Пример 13 (Пример 2). I — множество студ. гр.

Пример 14 (Пример 3). I — лист бумаги, доска

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

Универсальное множество обладает интересным свойством, которое не имеет аналогии в обычной алгебре, а именно, для любого множества X справедливо соотношение X∪I = I.

5. Дополнение множества

Множество, определяемое из соотношения X¯ = I\X, называется дополнением множества X (до универсального множества I).

На диаграмме множество X¯ представляет собой незаштрихованную область.

Формально: X = {x: x∈I и x∉X}.

Из определения следует, что X и X¯ не имеют общих элементов. Х∩X¯=∅.

Кроме того, не имеется элементов I, которые не принадлежали бы ни X, ни X¯ (его дополнению), так как те элементы, которые не принадлежат X, принадлежат X¯ (его дополнению). Следовательно, Х∪X¯=I.

Из симметрии данной формулы относительно Х и X¯ следует не только то, что X¯ является дополнением Х, но и что Х является дополнением X¯. Но дополнение X¯ есть X¯ ¯. Таким образом, X¯ ¯=X¯.

С помощью операции дополнения представим разность множеств:

X\Y = {x: x∈X и x∉Y} ={ x: x∈X и x∈Y¯ }, т.е. X\Y= Х∩Y¯.

Порядок выполнения операций:

  1. дополнение;
  2. пересечение;
  3. объединение, разность.

Для изменения порядка используют скобки.

6. Разбиение множества

Одной из наиболее часто встречающихся операций над множествами является операция разбиения множества на систему подмножеств.

Так, система курсов данного факультета является разбиением множества студентов факультета; система групп данного курса является разбиением множества студентов курса.

Пример. Продукция предприятия: — высший сорт, I, II, брак.

Рассмотрим некоторое множество M и систему множеств

М = {X1, X2, ..., Xn}

Система множеств M называется разбиением множества M, если она удовлетворяет следующим условиям:

  1. Любое множество X из M является подмножеством множества М

    ∀X∈M: X⊆M;

  2. Любые два множества X и Y из М являются непересекающимися

    ∀X∈М, ∀Y∈M: X≠Y → X∩Y=∅.

  3. Объединение всех множеств, входящих в разбиение, дает множество M

    X1∪X2∪...∪ Xn=M.

7. Тождества алгебры множеств

С помощью операций объединения, пересечения и дополнения из множеств можно составлять различные алгебраические выражения.

Если алгебраические выражения V(X,Y,Z) и S(X,Y,Z) представляют собой одно и то же множество, то их можно приравнять друг другу, получая алгебраическое тождество вида V(X,Y,Z) = S(X,Y,Z)

  1. (X∪Y)∩Z = (X∩Z)∪(Y∩Z) (аналогичное дистрибутивному закону (a+b)c=(a+c)(b+c) в обычной алгебре).
  2. (X∩Y)∪Z = (X∪Z)∩(Y∪Z)
  3. Если Y⊆X, то X∩Y=Y, X∪Y=X. Действительно, все элементы множества Y являются в то же время и элементами множества X. Значит пересечение этих множеств, то есть общая множеств Х и Y совпадает с Y. В объединение множеств X и Y множество Y не внесет ни одного элемента, который уже не входил бы в него, будучи элементом множества Х. Следовательно, X∪Y совпадает с X.
  4. Пусть в примере 3 Y=X. Тогда, учитывая, что X⊆X, то X∩Х=Х, X∪Х=X. (идемпотентность).
  5. Докажем тождество (X∪Y)¯=X¯∩Y¯. Предположим, что х∈(X∪Y)¯, то есть х∉X∪Y. Это значит, что х∉X и х∉Y, то есть и x&isinX¯ и x&isinY¯;. Следовательно, x∈X¯∩Y¯. Предположим теперь, что y∈X¯∩Y¯, то есть y∈X¯ и y∈Y¯. Это значит, что y∉X и y∉Y, то есть что y∉X∪Y. Следовательно, y∈(X∪Y)¯.
  6. Тождество (X∩Y)¯=X¯∪Y¯. Обычно тождества 5) и 6) называются тождествами де-Моргана.
  7. (A\B)∩C=(A∩C)\B=(A∩C)\(B∩C)
  8. A\B=A\(A∩B)
  9. A=(A∩B)∪(A\B)

Дополнение к занятию «операции над множествами»

Множество элементов, принадлежащих или A, или B, называют симметричной разностью или дизьюнктивной суммой.

S = A⊕B = (A\B)∪(B\A) = (A∩B¯)∪(A¯∪B) = (A∪B)∩(A∩B)¯

Для симметрической разности выполняются следующие законы:

  1. 1) A⊕B = B ⊕A — коммутативность,
  2. 2) A⊕(B⊕С) = (A⊕B)⊕С — ассоциативность,
  3. 3) A⊕∅ = А=∅⊕A — существование нейтрального элемента,
  4. 4) A ⊕А = ∅
  5. 5) A∩(B⊕С) = (A∩B)⊕(А∩С) — дистрибутивность относительно пересечения.

Упорядоченное множество

Упорядоченным множеством (или кортежем) называется последовательность элементов, то есть совокупность элементов, в которой каждый элемент занимает определенное место. Сами элементы — компоненты кортежа.

Пример 1. Множество людей, стоящих в очереди, множество слов в фразе, алфавит. Во всех этих множествах место каждого элемента является вполне определенным и не может быть произвольно изменено.

Число элементов кортежа называется его длиной. Обозначают кортеж скобками «< >», иногда круглыми «( )». А=<a1, a2, ..., an>. Кортежи длины 2 называются упорядоченными парами, 3 — тройками, n-ками.

Частный случай: кортеж длины 1 — <a>

кортеж длины 0 — < > или ∧ — пустой кортеж.

Отличие кортежа и обыкновенного множества: в кортеже могут быть одинаковые элементы.

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

Так, кортеж <a1, a2> может рассматриваться как точка на плоскости или вектор, проведенный из начала координат в данную точку. Тогда компоненты a1, a2 — проекции вектора на оси 1 и 2.

Пр1 <a1, a2> = a1, Пр2 <a1, a2> = a2, Прi <a1, a2, a3>= ai, Пр12 <a1, a2, a3>= <a1, a2> — двухэлементный кортеж. Проекция кортежа на пустое множество осей — пустой кортеж.

Обобщая эти понятия, будем рассматривать упорядоченное n-элементное множество вещественных чисел (a1, ..., an) как точку в воображаемом n–мерном пространстве (иногда называемом гиперпространством), или как n-мерный вектор. При этом компоненты n-элементного кортежа а будем рассматривать как проекции этого кортежа на соответствующие оси.

Прi a = ai, i=1,2,...,n

Прi,j,...,l a = <ai, aj, ..., al>, i=1,2,...,n

Два вектора равны, если они имеют одинаковую длину и соответствующие координаты их равны.

<a1, ..., am> = <b1, ..., bn> ⇔ m = n и a1 = b1, b1 = b2, ...

Компонентами кортежа (вектора) могут быть также компоненты кортежи (векторы):

Пример. Слова в предложении,

A = < <a1, a2>, <a1, a3>, <a2, a3> >

Прямое произведение множеств

Прямым (декартовым) произведением множеств X и Y называется множество, состоящее из всех тех и только тех упорядоченных пар, первая компонента которых принадлежит множеству X, а вторая принадлежит множеству Y.

Формально: X*Y = {<x,y>: x∈X, y∈Y}

Пример 2. Пусть X=<1,2>, Y=<1,3,4>

Тогда X*Y={<1,1>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4> } См. рис. а).

Пример 3. Пусть X и Y — отрезки вещественной оси. Прямое произведение X*Y изображается заштрихованным прямоугольником. См. рис. б).

Прямое произведение изменяется при изменении порядка сомножителей т.е.

X*Y ≠ Y*X

Прямое произведение множеств X1, X2, ..., Xn — это множество, обозначаемое X1*X2*...*Xn и состоящее из всех тех и только тех кортежей длины n, правая компонента которых принадлежит X1, вторая — X2 и т.д.

Очевидно X*Y = ∅ ⇔ X = ∅ или Y = ∅.

Аналогично X1*X2*...*Xn = ∅ тогда и только тогда, когда хотя бы одно из множеств X1, X2, ..., Xn является пустым.

Частным случаем прямого произведения является понятие степеней (декартовых) множества — прямое произведение одинаковых множеств

Ms=M*M*...*M, M1=M, M0=∧.

Обычно R — множество вещественных чисел, тогда R2=R*R — вещественная плоскость и R3=R*R*R — трехмерное вещественное пространство.

Пример. A={a,b,c,d,e,f,g,h}, B={1,2,3, ...,8}

Тогда A*B ={a1, a2, a3, ..., h7, h8} — множество обозначающее все 64 клеток шахматной доски.

Пример. Пусть A — конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания и т.д.). Такие множества обычно называют алфавитами. Элементы множества an называются словами длины n в алфавите A. Множество всех символов в алфавите A — это множество A* = ∪Ai = A1∪A2∪A3... . При написании слов не принято пользоваться ни запятыми, ни скобками, ни разделителями.

СЛОВО ⇔ <С,Л,О,В,О>

Теорема. Пусть a1, a2, ..., an — конечные множества и |a1| = m1, |a2|=m2, ..., |an|=mn. Тогда мощность множества a1*a2*a3*...*an равна произведению мощностей a1, a2, ..., an

|a1*a2*...*an|=|a1|*|a2|*|a3|*...*|an|= m1*m2*...*mn

Следствие |an|=|A|n

Проекция множества.

Операция программирования множества тесно связана с операцией проектирования кортежа и может применяться лишь к таким множествам, элементами которых являются кортежи одинаковой длины.

Пусть M — множество, состоящее из кортежей длины S. Тогда пролинией множества M будем называть множество пролиний всех кортежей из М

Пример. Пусть М={<1,2,3,4,5>,<2,1,3,5,5>,<3,3,3,3,3>,<3,2,3,4,3>}

тогда Пр2М={2,1,3}, Пр3M={3}, Пр4M={4,5,3}, Пр24M={<2,4>,<1,5>,<3,3>}, Пр13M={<1,3>,<2,3>,<3,3>}, Пр15M={<1,5>,<2,5>,<1,3>}, Пр25M={<2,5>,<1,5>,<3,3>,<2,3>}.

Очевидно что если М=Х*Y то Пр1М=Х, Пр2М=Y

и если Q⊆Х*Y то Пр1Q⊆Х и Пр2Q⊆Y

Пример. V={<a,b,d>,<c,b,d>,<d,b,b>}

Пр1V={a,c,d}

Пр2V={b}

Пр3V={d,b}

Пр12V={<a,b>,<c,b>,<d,b>}

Пр23V={<b,d>,<b,b>}

Пр13V={<a,d>,<c,d>,<d,b>}

Пусть V — множество векторов одинаковой длины S.

ПрiV ={Прiv/v∈Y}, Прii...ikv = { Прii...ikv/v∈Y}.

Если V =A1*A2*...*An, то Прii...ikV=Ai1*Ai2*...*Aik.

В общем случае ПрiV — вовсе не обязательно прямое произведение: оно может быть подмножеством.

Оглавление    
Лекция 12, «Основные понятия теории множеств» Лекция 14, «Соответствие и функции»