Из всего множества действующих факторов. Бинарные отношения. Отношение эквивалентности, фактор-множество. Элементы логической символики

102 страницы (Word-файл)

Посмотреть все страницы

Фрагмент текста работы

2.1. Структура курса. Основные термины и определения. Структура единой сети электросвязи (ЕСЭ) РФ. Методы коммутации в сетях передачи данных. Виды сигналов. Параметры цифровых сигналов данных.

2.2. Структурная схема системы передачи дискретных сообщений. Непрерывный канал и КПТ. Краевые искажения и дробления. Методы регистрации. Дискретный канал. Каналы с памятью. Расширенный дискретный канал и его параметры. Характеристики СПДС.

2.3. Принципы эффективного кодирования. Метод Хаффмана. Словарные методы ZLW.

2.4. Помехоустойчивое кодирование. Линейные коды. Производящая и проверочная матрицы линейного кода Хемминга. Кодер. Декодер. Циклические коды. Построение кодера и его работа. Декодер с обнаружением ошибок.

Алгоритм определения ошибочного разряда. Декодеры с исправлением ошибок. Кодек Рида-Соломона. Итеративные и каскадные коды. Сверточные коды. Построение кодера и его работа. Диаграмма состояний и решетчатая диаграмма. Декодирование по алгоритму Витерби.

2.5. Адаптивные системы. Системы с ИОС. Системы с РОС-ОЖ. Расчет достоверности и скорости передачи информации.

2.6. Методы сопряжения источника дискретных сообщений с дискретным каналом. DTE/DCE, RS-232 и др.

2.7. Синхронизация. Виды поэлементной синхронизации. Техническая реализация. Расчет параметров синхронизации. Групповая, цикловая синхронизация.

2.8. УПС. Классификация. Перекодирование. АМ, ЧМ, ФМ. Модуляторы и демодуляторы. Относительная фазовая модуляция. Многопозиционная фазовая и амплитудно-фазовая модуляции. DMT, Треллис модуляция. Обзор xDSL технологии. OFDM. Радиомодемы, спутниковые модемы.

2.9. Компьютерные сети ПД. Принципы построения. Классификация. Назначение ЛВС. Типы ЛВС. Топологии сетей. Основные среды передачи в ЛВС. Технологии сетей передачи данных в операторских сетях. Корпоративные сети ПД, VPN. Модель взаимодействия открытых систем. Сетевые модели OSI и IEEE. Взаимодействия между уровнями. Примеры протоколов разных уровней. Стеки протоколов. Методы доступа к среде передачи. Сетевые архитектуры: Ethernet, Token Ring. Устройства расширения ЛВС. Репитер, мост, коммутатор, маршрутизатор, IP адресация.

Методы маршрутизации. Взаимодействие прикладных процессов через протокол TCP. Шлюзы.

ОСНОВЫ ПЕРЕДАЧИ ДИСКРЕНЫХ СООБЩЕНИЙ

Лекция №1.

Структура курса. Основные термины и определения.

Лекций 34 часа;

Практические занятия 17 часов;

Лабораторные работы 17 часов.

Темы лекций:

1. Структура курса. Основные термины и определения;

2. Структурная схема системы ПДС;

3. Принцип эффективного кодирования;

4. Помехоустойчивое кодирование;

5. Методы сопряжения источника дискретных сообщений и дискретным каналом;

6. Синхронизация;

7. Устройства преобразования сигналов (УПС);

8. Адаптивные системы;

9. Методы коммутации в сети ПДС;

10. Компьютерные сети передачи данных.

Документальная электросвязь – это такой вид электросвязи, где сообщение можно отобразить на какой-либо носитель (бумага, экран монитора).

Службы:

Телеграфные ТГСОП;

Телефонные;

Телексные АТ/Телекс;

Факсимильные СФС:

Факс-сервер; сети

Дэйтафакс;

Передача газетных полос ПГП;

Видеотекст (электронная почта).

Телематические.

Способы распределения информации в сетях ПДС:

1. Коммутация каналов;

2. Коммутация с накоплением:

Коммутация сообщений;

Коммутация пакетов.

Коммутация каналов (КК) – установка соединения, передача сообщения в обе стороны, разрушение.

Коммутация каналов:

Коммутация с накоплением. ТФСОП :

УУ – Управляющее устройство;

НУ – Накопительное устройство;

ВЗУ – Внешнее запоминающее устройство.

Сообщение передается по участкам сети, запоминается в УК. Состоит из заголовка и данных. Отсутствует фаза установления и разъединения.

Заголовок читается Находится адрес УК Получатель

Коммутация сообщений (КС) ТГСОП.

Заголовок состоит из семи уровней. На каждом уровне сообщение обрабатывается и хранится во внешней памяти.

Основной минус КС в том, что необходимо иметь большую память, так как передаются сообщения разных длин.

Примечание: ЦКС на ЭВМ (ЦКС – центр. ком. сообщ.).

В компьютерных сетях, телематических службах (почтовые сообщения).

Коммутация пакетов:

Сообщение разбивается на пакеты. Отсутствует НУ. Время задержки сообщений меньше. Высокая скорость обработки.

Применяется в:

Компьютерных сетях;

Ethernet: на 1 и2 уровне заголовок сохраняется, а затем нет;

ТФСОП; ССПО

Используют коммутацию пакетов протоколов.

NGN – Next Generation Network (пакетная сеть);

IP – телефония.

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

ТСР (с установлением виртуального соединения (виртуальный канал));

UDP – (без установления соединения (датаграммный режим)).

ВВК – Временной виртуальный коммутатор (устанавливается пользователем).

ПВК – Постоянный временной канал (устанавливается администратором).

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

Протокол ТСР более надежный.

Перемешивание пакетов – пакеты проходят по разным путям, появляются в разное время.

Лекция №2.

Структурная схема системы ПДС.

В основном система передачи данных использует коммутацию пакетов.

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

е.э – единичный элемент.

Такой сигнал поступает в канал связи, в зависимости от канала необходимо делать преобразование. В канале связи на сигнал действуют помехи – внешние и внутренние. Поэтому используется помехоустойчивое кодирование.

Источник ДС (0:1) Канал связи (0:1) ДС Получатель

В телеграфной связи помехоустойчивое кодирование применяется редко.

Для телематических служб и СПД – обязательно.

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

Структурная схема системы ДЭС:

ИС – источник сообщения, поступ. дискр. сообщ., еще называется кодером источника или оборудованием обработки данных.

УЗО – устройство защиты от ошибок, добавляет проверочные «r» битов к битам информации «к», еще называется канальным кодером.

УПС – устройство преобразования сигнала – преобразует сигнал в форму, подходящую для передачи в канал связи.

УЗО и УПС объединяются в АПД – аппаратуру передачи данных.

ПС – приемник сообщений.

ДК – дискретный канал.

КПД – канал передачи данных.

В качестве первичного кода используется МКТ-2 (n=5, ).

На муждугородной связи – МКТ-5 (СКПД) =128.

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

Пусть R – бинарное отношение на множестве X. Отношение R называется рефлексивным , если (x, x) Î R для всех x Î X; симметричным – если из (x, y) Î R следует (y, x) Î R; транзитивным числу 23 соответствует вариант 24 если (x, y) Î R и (y, z) Î R влекут (x, z) Î R.

Пример 1

Будем говорить, что x Î X имеет общее с элементом y Î X, если множество
x Ç y не пусто. Отношение иметь общее будет рефлексивным и симметричным, но не транзитивным.

Отношением эквивалентности на X называется рефлексивное, транзитивное и симметричное отношение. Легко видеть, что R Í X ´ X будет отношением эквивалентности тогда и только тогда, когда имеют место включения:

Id X Í R (рефлексивность),

R -1 Í R (симметричность),

R ° R Í R (транзитивность).

В действительности эти три условия равносильны следующим:

Id X Í R, R -1 = R, R ° R = R.

Разбиением множества X называется множество А попарно непересекающихся подмножеств a Í X таких, что UA = X. С каждым разбиением А можно связать отношение эквивалентности ~ на X, полагая x ~ y, если x и y являются элементами некоторого a Î A.

Каждому отношению эквивалентности ~ на X соответствует разбиение А, элементами которого являются подмножества, каждое из которых состоит из находящихся в отношении ~. Эти подмножества называются классами эквивалентности . Это разбиение А называется фактор-множеством множества X по отношению ~ и обозначается: X/~.

Определим отношение ~ на множестве w натуральных чисел, полагая x ~ y, если остатки от деления x и y на 3 равны между собой. Тогда w/~ состоит из трёх классов эквивалентности, соответствующих остаткам 0, 1 и 2.

Отношение порядка

Бинарное отношение R на множестве X называется антисимметричным , если из x R y и y R x следует: x = y. Бинарное отношение R на множестве X называется отношением порядка , если оно рефлексивно, антисимметрично и транзитивно. Легко видеть, что это равносильно выполнению следующих условий:

1) Id X Í R (рефлексивность),

2) R Ç R -1 (антисимметричность),

3) R ° R Í R (транзитивность).

Упорядоченная пара (X, R), состоящая из множества X и отношения порядка R на X, называется частично упорядоченным множеством .

Пример 1

Пусть X = {0, 1, 2, 3}, R = {(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (3, 3)}.

Поскольку R удовлетворяет условиям 1 – 3, то (X, R) – частично упорядоченное множество. Для элементов x = 2, y = 3, неверно ни x R y, ни y R x. Такие элементы называют несравнимыми . Обычно отношение порядка обозначают £. В приведенном примере 0 £ 1 и 2 £ 2, но неверно, что 2 £ 3.

Пример 2

Пусть < – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество.

Элементы x, y Î X частично упорядоченного множества (X, £) называются сравнимыми , если x £ y либо y £ x.

Частично упорядоченное множество (X, £) называется линейно упорядоченным или цепью , если любые два его элемента сравнимы. Множество из примера 2 будет линейно упорядоченным, а из примера 1 – нет.

Подмножество A Í X частично упорядоченного множества (X, £) называется ограниченным сверху , если существует такой элемент x Î X, что a £ x для всех a Î A. Элемент x Î X называется наибольшим в X, если y £ x для всех y Î X. Элемент x Î X называется максимальным, если нет отличных от x элементов y Î X, для которых x £ y. В примере 1 элементы 2 и 3 будут максимальными, но не наибольшими. Аналогично определяются ограничение снизу подмножества, наименьший и минимальный элементы. В примере 1 элемент 0 будет и наименьшим и минимальным. В примере 2 этими свойствами также обладает 0, но в (w, £) нет ни наибольшего, ни максимального элемента.

Пусть G={p 0 =e, p 1 , …, p r } есть некоторая группа подстановок, определенная на множестве X = {1, 2, …, n} с единицей e=p 0 тождественной подстановкой. Определим отношение x~y, положив x~y равносильно, что существует p принадлежащее G(p(x)=y). Введенное отношение есть отношение эквивалентности, то есть оно удовлетворяет трем аксиомам:

1) x~x;
2) x~y→y~x;
3) x~y&y~z→x~z;

Пусть А – произвольное множество.
Определение : Бинарное отношение δ=A*A есть отношение эквивалентности (обозначается a ~ b), если они удовлетворяет следующим аксиомам:
∀ a, b, c ∈ A
1) a ~ a – рефлексивность;
2) a ~ b ⇒ b ~ a – коммутативность;
3) a ~ b & b ~ c → a ~ c — транзитивность

обозначается a ~ b, σ(a,b), (a,b) ∈ σ, a σ b

Определение : Разбиение множества А есть семейство попарно не пресекающихся подмножеств из А, в объединении (в сумме) дающих все А.
А= ∪А i , А i ∩А j = ∅, ∀i ≠ j.

Подмножества А i называются смежными классами разбиения.

Теорема : каждое отношение эквивалентности, определенное на А, соответствует некоторому разбиению множества А. Всякое разбиение множества А соответствует некоторому отношению эквивалентности на множестве А.

Коротко: между классами всех определенных на множестве А отношений эквивалентностей и классом всех разбиений множества А существует взаимнооднозначное соответствие.

Доказательство : пусть σ — есть отношение эквивалентности на множестве А. Пусть а ∈ А.

Построим множество: К a ={x ∈ A,: x~a } – всех элементов, эквивалентных а. Множество (обозначение) называется классом эквивалентности относительно эквивалентности σ. Заметим, что если b принадлежит K a , то b~a. Покажем, что a~b⇔K a =K b . В самом деле, пусть a~b. Возьмем произвольный элемент c принадлежит K a . Тогда c~a, a~b, c~b, c принадлежит K b и потому K b принадлежит K a . То, что K a принадлежит K b , показывается аналогично. Следовательно, K b =K a .
Пусть теперь K b =K a . Тогда a принадлежит K a = K b , a принадлежит K b , a~b. Что и требовалось показать.

Если 2 класса K a и K b имеют общий элемент с, то K a = K b . В самом деле, если с принадлежит K a и K b , то b~c, c~a, b~a => K a = K b .

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

Обратное: Пусть А = сумма по или A i – есть разбиение А. Введем на А отношение a~b, как a~b ⇔ a,b принадлежат одному и тому же классу разбиения. Это отношение удовлетворяет следующим аксиомам:

1) a ~ a (лежат в одном классе);
2) a ~ b → b ~ a;
3) a ~ b & b ~ c → a ~ c, т.е. введенное отношение ~ есть отношение эквивалентности.

Замечание :
1) разбиение множества А на одноэлементные подмножества и разбиение А, состоящие только из множества А, называется тривиальными (несобственным) разбиением.

2) Разбиение А на одноэлементные подмножества соответствует отношению эквивалентности которое есть равенство.

3) Разбиение А, состоящие из одного класса А, соответствует отношению эквивалентности, содержащему A x A.

4) a σ b → [a] σ = [b] σ — всякое отношение эквивалентности определенное на некотором множестве разбивает это множество на попарно не пересекающиеся классы называемые классами эквивалентности.

Определение : Совокупность классов эквивалентности множества А называется фактор-множеством A/σ множества А по эквивалентности σ.

Определение : Отображение p:A→A/σ, при котором p(A)=[a] σ , называется каноническим (естественным) отображением.

Всякое отношение эквивалентности, определенное на некотором множестве, разбивает это множество на попарно не пересекающиеся классы, называемые классами эквивалентности.

Математическим анализом называется раздел математики, занимающийся исследованием функций на основе идеи бесконечно малой функции.

Основными понятиями математического анализа являются величина, множество, функция, бесконечно малая функция, предел, производная, интеграл.

Величиной называется все что может быть измерено и выражено числом.

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

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

Если элемент x принадлежит множеству X , то записывают x ∈ Х (∈ — принадлежит).
Если множество А является частью множества В, то записывают А ⊂ В (⊂ — содержится).

Множество может быть задано одним из двух способов: перечислением и с помощью определяющего свойства.

• А={1,2,3,5,7} — множество чисел
• Х={x 1 ,x 2 ,...,x n } — множество некоторых элементов x 1 ,x 2 ,...,x n
• N={1,2,...,n} — множество натуральных чисел
• Z={0,±1,±2,...,±n} — множество целых чисел

Множество (-∞;+∞) называется числовой прямой , а любое число — точкой этой прямой. Пусть a — произвольная точка числовой прямой иδ — положительное число. Интервал (a-δ; a+δ) называется δ-окрестностью точки а .

Множество Х ограничено сверху (снизу), если существует такое число c, что для любого x ∈ X выполняется неравенство x≤с (x≥c). Число с в этом случае называется верхней(нижней) гранью множества Х. Множество, ограниченное и сверху и снизу, называется ограниченным . Наименьшая (наибольшая) из верхних (нижних) граней множества называется точной верхней (нижней) гранью этого множества.

Основные числовые множества

Если множество не содержит ни одного элемента, то оно называется пустым множеством и записывается Ø .

Элементы логической символики

Запись ∀x: |x|<2 → x 2 < 4 означает: для каждого x такого, что |x|<2, выполняется неравенство x 2 < 4.

При записи математических выражений часто используются кванторы.

Квантором называется логический символ, который характеризует следующие за ним элементы в количественном отношении.

• ∀- квантор общности , используется вместо слов "для всех", "для любого".
• ∃- квантор существования , используется вместо слов "существует", "имеется". Используется также сочетание символов ∃!, которое читается как существует единственный.

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

Два множества А и В равны (А=В), если они состоят из одних и тех же элементов.
Например, если А={1,2,3,4}, B={3,1,4,2} то А=В.

Объединением (суммой) множеств А и В называется множество А ∪ В, элементы которого принадлежат хотя бы одному из этих множеств.
Например, если А={1,2,4}, B={3,4,5,6}, то А ∪ B = {1,2,3,4,5,6}

Пересечением (произведением) множеств А и В называется множество А ∩ В, элементы которого принадлежат как множеству А, так и множеству В.
Например, если А={1,2,4}, B={3,4,5,2}, то А ∩ В = {2,4}

Разностью множеств А и В называется множество АВ, элементы которого принадлежат множесву А, но не принадлежат множеству В.
Например, если А={1,2,3,4}, B={3,4,5}, то АВ = {1,2}

Симметричной разностью множеств А и В называется множество А Δ В, являющееся объединением разностей множеств АВ и ВА, то есть А Δ В = (АВ) ∪ (ВА).
Например, если А={1,2,3,4}, B={3,4,5,6}, то А Δ В = {1,2} ∪ {5,6} = {1,2,5,6}

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

A ∪ B = B ∪ A
A ∩ B = B ∩ A

(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)

Счетные и несчетные множества

Для того, чтобы сравнить два каких-либо множества А и В, между их элементами устанавливают соответствие.

Если это соответствие взаимооднозначное, то множества называются эквивалентными или равномощными, А В или В А.

Множество точек катета ВС и гипотенузы АС треугольника АВС являются равномощными.

Теория множеств. Основные понятия

Теория множеств является основополагающим определением современной математики. Она была создана Георгом Кантором в 1860-х гг. Он писал: «Множество есть многое, мыслимое как единое целое». Понятие множества принадлежит к числу основных, неопределяемых понятий математики. Оно не сводится к другим, более простым понятиям. Поэтому его нельзя определить, а можно лишь пояснить. Таким образом, множество – объединение в одно целое объектов, хорошо различимых нашей интуицией или нашей мыслью; совокупность некоторых объектов, определенных общим признаком.

Например,

1. Множество жителей г. Воронежа

2. Множество точек плоскости

3. Множество натуральных чисел ℕи др.

Множества обычно обозначаются большими латинскими буквами(A, B, C и т.д.). Объекты, составляющие данное множество, называются его элементами. Элементы множества обозначаются малыми латинскими буквами(a, b, c и т.д.). Если Х – множество, то запись х∈Х означает, что х есть элемент множества Х или что х принадлежит множеству Х , а запись х∉Х , что элемент х не принадлежит множеству Х . Например, пусть ℕ–множество натуральных чисел. Тогда 5 ℕ , а 0,5∉ℕ .

Если множество Y состоит из элементов множества Х , то говорят, что Y является подмножеством множества Х и обозначают Y⊂Х (или Y⊆Х ). Например, множество целых чисел ℤ является подмножеством рациональных чисел ℚ .

Если для двух множеств Х и Y одновременно имеют место два включения Х Y и Y Х , т.е. Х есть подмножество множества Y и Y есть подмножество множества Х , то множества Х и Y состоят из одних и тех же элементов. Такие множества Х и Y называют равными и пишут: Х=Y .

Часто используется термин пустое множество - Ø - множество, не содержащее ни одного элемента. Оно является подмножеством любого множества.

Для описания множеств могут использоваться следующие способы.

Способы задания множеств

1. Перечисление объектов. Используется только для конечных множеств.

Например, Х={x1, x2, x3… x n } . Запись Y={1, 4, 7, 5} означает, что множество состоит из четырех чисел 1, 4, 7, 5 .

2. Указание характеристического свойства элементов множества.

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

Х={х: Р(х)}

(множество Х состоит их таких элементов х , для которых выполняется свойство Р (х) ).

Пустое множество можно задать, указав его свойства: Ø={х: х≠х}

Построить новые множества можно с помощью уже заданных, используя операции над множествами.

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

1. Объединением(суммой) называется множество, состоящее из всех тех элементов, каждый из которых принадлежит хотя бы одному из множеств А или В .

А∪ В={х: х А или х В}.

2. Пересечением(произведением) называется множество, состоящее из всех элементов, каждый из которых одновременно принадлежит как множеству А , так и множеству В .

А∩В={х: х А и х В}.

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

А\В={х: х А и х В}

4. Если А – подмножество множества В . То множество В\А называют дополнением множества А до множества В и обозначают А’ .

5. Симметрической разностью двух множеств называют множество А∆В=(А\В) (В\А)

N - множество всех натуральных чисел;
Z - множество всех целых чисел;
Q - множество всех рациональных чисел;
R - множество всех действительных чисел;
C - множество всех комплексных чисел;
Z 0 - множество всех неотрицательных целых чисел.

Свойства операций над множествами:

1. А В=В А (коммутативность объединения)

2. А В=В А (коммутативность пересечения)

3. А(В С)=(А В) С (ассоциативность объединения)

4. А (В С)=(А В) С (ассоциативность пересечения)

5. А (В С)=(А В) (А С) (1 закон дистрибутивности)

6. А (В С)=(А В) (А С) (2 закон дистрибутивности)

7. А Ø=А

8. А U= U

9. А Ø= Ø

10. А U=А

11. (А В)’=А’ В’ (закон де Моргана)

12. (А В)’=А’ В’ (закон де Моргана)

13. А (А В)=А (закон поглощения)

14. А (А В)=А (закон поглощения)

Докажем свойство №11. (А В)’=А’ В’

По определению равных множеств, нам необходимо доказать два включения 1) (А В)’ ⊂А’ В’ ;

2) А’ В’⊂(А В)’ .

Для доказательства первого включения, рассмотрим произвольный элемент х∈(А В)’=Х\(А∪В). Это означает, что х∈Х, х∉ А∪В . Отсюда следует, что х∉А и х∉В , поэтому х∈Х\А и х∈Х\В , а значит х∈А’∩В’ . Таким образом, (А В)’⊂А’ В’

Обратно, если х∈А’ В’ , то х одновременно принадлежит множествам А’, В’ , а значит х∉А и х∉В . Из этого следует, что х∉ А В , поэтому х∈(А В)’ . Следовательно, А’ В’⊂(А В)’ .

Итак, (А В)’=А’ В’

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

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

Декартово произведение – произвольное множество X 1 , X 2 ,…,X n упорядоченных наборов из n элементов, где x 1 X 1 , x 2 X 2 ,…, x n X n

Х 1 Х n

Если множества X 1 , X 2 ,…,X n совпадают(X 1 = X 2 =…=X n) , то их произведение обозначается Х n .

Например, ℝ 2 – множество упорядоченных пар вещественных чисел.

Отношения эквивалентности. Фактор-множества

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

В ряде вопросов рассматривают класс таких подмножеств данного множества А , которые не пересекаются и объединение которых совпадает с А . Если данное множество А можно представить в виде объединения своих попарно не пересекающихся подмножеств, то принято говорить, что А разбито на классы. Разбиение на классы осуществляют на основе какого-либо признака.

Пусть Х – не пустое множество, тогда любое подмножество R из произведения Х Х называется бинарным отношением на множестве Х . Если пара (х,у) входит в R, говорят, что элемент х находится в отношении R с у .

Например, отношения х=у, х≥у являются бинарным отношениями на множестве ℝ.

Бинарное отношение R на множестве Х называется отношением эквивалентности, если:

1. (х,х) R; х Х (свойство рефлексивности)

2. (х,у) R => (у,х) R (свойство симметричности)

3. (х,у) R, (у,z) R, то (x,z) R (свойство транзитивности)

Если пара (х,у) вошла в отношения эквивалентности, то х и у называют эквивалентными(х~у).

1.Пусть ℤ – множество целых чисел, m≥1 – целое число. Зададим отношение эквивалентности R на ℤ так, чтобы n~k , если n-k делится на m . Проверим, выполняются ли свойства на данном отношении.

1. Рефлексивность.

Для любого n∈ℤ ℤ такого, что (p,p)∈R

р-р=0 . Так как 0∈ ℤ , то (p,p)∈ℤ .

2. Симметричность.

Из (n,k) ∈R следует, что существует такое р∈ ℤ , что n-k=mp ;

k-n =m(-p), -p∈ ℤ , следовательно (k,n) ∈R .

3. Транзитивность.

Из того, что (n,k) ∈R , (k,q) ∈R следует, что существуют такие р 1 и р 2 ∈ ℤ , что n-k=mp 1 и k-q=mp 2 . Сложив данные выражения, получаем, что n-q=m(p 1 + p 2), p 1 + p 2 =p, p∈ ℤ . Поэтому (n,q) ∈ ℤ .

2.Рассмотрим множество Х всех направленных отрезков пространства или плоскости. =(А, В) . Введем отношение эквивалентности R на Х .