Факторизация отображения

Пусть f – отображение X в Y, если х₁φх₂  f(х₁)=f(х₂); Это отношение эквивалентности, которое порождает разбиение множества X:

1. из рефлексивности: "_x1 х₁φх₁ f(х₁)= f(х₁);

2. из симметричности: "_x1_x2 f(х₁)=f(х₂)  f(х₂)=f(х₁);

3. из транзитивности "_x1_x2_x3 f(х₁)=f(х₂) и f(х₂)=f(х₃)  f(х₁)=f(х₃); x/φ – факториальное множество.

g является отображением x на x/; g – соответствие, ставящее в соответствие каждому х в соответствие класс. Соответствие h: x/f(x) обладает свойствами 1,2,3,4, т.о. h – биекция. Обозначим e(y)=y – вложение, где e является отображением f(x) на Y. Взаимнооднозначное отображение f=ghe.

Пример:

Пусть X={a,b,c}; Y={1,2,3,4}; f(a)=f(c)=1; f(b)=3. X/={{a,c},{b}}.

g(a)=g(c)={a,c}; g(b)={b};

h({a,c})=1;

h({b})=3;

f(x)={1,3};

e(1)=1; e(3)=3.

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

Отношение порядка – это отношение, обладающие свойствами антисимметричности и транзитивности.

Отношение частичного порядка – это отношение, обладающие свойствами рефлексивности, антисимметричности и транзитивности; обозначается символом “ ”. Выражение a b обозначает, что a предшествует b или a минорирует b. A BAB

1. _A: A A;

4. "_A_B: если A B и B A, то A=B;

5. "_{A B C}: если A B и B C, то A C.

Пример:

Пусть x y  х делится на у, причем х, уN. Тогда:

1. _х: х х;

4. _х,у: х у, у х =>x=y;

5. _х,у,z: х у, у z =>x z.

Множество с введённым на нем отношением частичного порядка называется частично упорядоченным множеством (ЧУМ). Элемент О называется наименьшим элементом ЧУМ если ОА,_xA O x, т.е. он предшествует всем остальным элементам. Наибольший элемент ЧУМ – I – если IА,_xA x I.

Теорема (о единственности наибольшего (наименьшего) элемента ЧУМа): если наибольший (наименьший) элемент существует, то он единственный.

Док-во:

1. Пусть I и I*– два различных наибольших элемент в ЧУМе.

Т.к. I – наибольший, то I* I. Но I* тоже наибольший, а значит I I*. Тогда по свойству антисимметричности I=I*. Следовательно, мы пришли к противоречию.

2. Пусть О и О*– два различных наибольших элемент в ЧУМе.

Т.к. О – наименьший, то О О*. Но О* тоже наименьший, а значит О* О. Тогда по свойству антисимметричности О=О*. Следовательно, мы пришли к противоречию.

ч.т.д.

Пусть m и M – минимальный и максимальный элементы ЧУМа А. Тогда

_xA: х m → x=m;

_xA: M x → x=M.

П ример:

m{1,4} – стрелки только выходят;

M{2,3} – стрелки только входят.

Опр: Отношение линейного порядка обладает свойствами 1, 4, 5, 6.

Пример: зададим отношение на множестве R: x yx y. Тогда:

1. _х: х х;

4. _х,y: х y, y x => x=y;

5. _х,y,z: х y, y z => x z;

6. _х,y: х≠y => y x или x y.

Опр: Отношение строгого порядка обладает свойствами 2, 4, 5.

Опр: Отношение строгого линейного порядка обладает свойствами 2, 4, 5, 6.

Теория алгоритмов. Понятие алгоритма.

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

2. существует элементарный шаг;

3. детерминированность алгоритма (на каждом шаге мы знаем, что делать дальше);

4. массовость (должен решать класс задач);

5. результативность (существует условие окончания работы);

6. алгоритм обладает памятью.