Понятия множества

Определения понятия  множества не существует, т.к. более  простых понятий нет. Множество – это совокупность объектов, обладающих одним и тем же определённым свойством. Отдельные объекты, из которых состоит множество, называются элементами множества.        Заметим, что элементы множества сами могут являться множествами.

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

 Общим обозначением  множества служит пара фигурных  скобок: { }.

Внутри этих скобок перечисляются элементы множества.        

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

A₁, A₂ ...        

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

a, s, x ...

Операции: объединение  множеств – множество, состоящее  из элементов, которые принадлежат A или B; пересечение множеств – множество элементов, которые принадлежат и А и В; разность множеств ; симметричная разность , дополнение множества , где омега – «универсальное» множество, декартово произведение множеств – множество, состоящее из всех пар, где первый элемент принадлежит первому множеству, а второй – второму.

Если указан закон, сопоставляющий каждому элементу один элемент , то говорят, что имеет однозначное отображение . Отображение числовых множеств обычно называют функциями. Отображение называется многозначным если элементу a может быть сопоставлено несколько элементов b. Отображение называется инъективным, если разные элементы переходят в разные. Отображение называется сюръективным, если каждый элемент из B имеет прообраз, т.е. существует a . Если отображение инъективно и сюръективно, то оно биективно.

Всякое подмножество декартового  произведения называется отношением на множестве A. Вместо записи обычно пишут .

Свойства отношений:

Отношение Г называется: рефлексивным, если аГа выполняется для любого а; симметричным, если из аГв следует вГа; транзитивным, если аГв, вГс –> аГс. Если отношение рефлексивно, транзитивно и симметрично, то оно называется отношением эквивалентности. Если на множестве задано отношение эквивалентности, то множество распадается на объединение непересекающихся классов эквивалентности, в каждом из которых все элементы эквиваленты друг другу.

Если отношение Г  рефлексивно, асимметрично (аГв, вГа -> а=в) и транзитивно, то оно называется отношением нестрогого порядка. Если отношение Г антирефлексивно (аГа не выполняется), антисимметрично (аГв и вГа одновременно невозможно) и транзитивно, то оно называется отношением строгого порядка. Если на множестве введено отношение строго или не строгого порядка, то множество называется упорядоченным. Если в упорядоченном множестве любые два элемента можно сравнить, то множество называется вполне упорядоченным, в противном случае множество называется частично упорядоченным.

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

 Пусть A и B –  некоторые числа, A+B – их сумма, AB – их произведение. Сумма и  произведение чисел обладают  следующими свойствами:

A+B=B+A; AB=BA – коммутативный или переместительный закон

(A+B)+C=A+(B+C); (AB)C=A(BC) – ассоциативный или сочетательный закон

(A+B)C=AC+BC – дистрибутивный или распределительный закон

Если дано множество  Х и многозначное отображение  , то говорят, что задан ориентированный граф (орграф). Элементы называются вершинами орграфа, а пары (x,y)  - дугами. Вершины соединенные дугой называются смежными. Если в орграфе отождествить пары (x,y) и (y,x) т.е. стереть стрелки, то возникает неориентированный граф (граф). В графе дуга переименовывается в ребро. Путь – последовательность дуг, такая что конец каждой дуги есть начало следующей. Если начало пути совпадает с его концом то он называется контуром. В графе путь переименовывается в цепь, а контур в цикл. Если любые две вершины графа можно соединить цепью, то граф называется связным. В несвязном графе существуют максимальные связные подграфы – компоненты связности.

2.1. Схема данных

2.1.1. Схемы данных отображают  путь данных при решении задач  и определяют этапы обработки, а также различные применяемые носители данных.

2.1.2. Схема данных состоит из:

1) символов данных (символы данных  могут также указывать вид  носителя данных);

2) символов процесса, который следует  выполнить над данными (символы  процесса могут также указывать функции, выполняемые вычислительной машиной);

3) символов линий, указывающих  потоки данных между процессами  и (или) носителями данных;

4) специальных символов, используемых  для облегчения написания и  чтения схемы.

2.1.3. Символы данных предшествуют и следуют за символами процесса. Схема данных начинается и заканчивается символами данных