Шпоры по дискре (2 семестр)

1. (1 из 1) Понятие множества. Операции над множествами. Примеры.

2. (1 из 2) Отображения. Виды отображений. Ассоциативность композиции отображений.

Опр: Мн-во – это совокупность некоторых объектов.

Опр: 1). S  T, т.е. sS, sT;

2). S=T, т.е. S  T и T  S;

3).  - пустое мн-во;

4). S  T={xxS и xT};

5). S  T={xxS  xT};

6). S\T={xxS  xT};

7). X*Y – декартово произведение – это новое множество, состоящме из: X*Y={(x,y)xX, yY};

8). X – конечное множество и Х - количество элементов множества X (конечное).

Пр.: X, Y – конечное, Х=n, Y=m; X*Y=nm. XY=n+m — XY.

Отображение:

Опр1: f:XY – отображает с области знач. Y и области определения Х, если каждому элементу хХ поставлен в соответствие единственный элемент из множества Y – f(x);

Опр2: Если Y=X, то f называется преобразованием множества Х;

Опр3: Im (образ) f={f(x)xX} – образ множества Х при действ. отобр. f;

f ^—1(y)={xXf(x)=y} – полный прообраз элемента yY;

Опр4: f: XY – сюрьективное (или отображение на), если Im f=Y, т.е. yY xX: f(x)=y;

Опр5: Отображение f: XY – инъективное (отображение в), если из xx`  f(x)f(x`), x, x` X;

Опр6: Отображение f: XY – биективное отображение, если f - сюрьективное и f – инъективное, т.е. взаимнооднозначное отображение.

Опр7: Отображение f: XY , g: . f совпадает с g, если

а). и ;

б). xX, f(x)=g(x).

Пример:

- не сюръективно, не инъективно;

- сюръективно; - биективно.

Опр8: e_X: XX – единичное отображение на множествово Х, если xX, e_X(x)=x.

2. (2 из 2) Отображения. Виды отображений. Ассоциативность композиции отображений.

3. (1 из 1) Обратное отображение. Критерий обратимости отображения.

Опр9: f: XY, g: X`Y. Если X` X, то g – ограничением f на Х` и f – продолжением g, если g(x)=f(x), xX`.

Опр10: Произведение (композиция) отображение g: UV, f: VW называется fog: UW: fog(u)=f(g(u))  uU

Утв: Композиция отображений – ассоциативно, т.е. если h:UV, g:VW, f:WT, то f(gh)=(fg)h.

Доказательство:

nU f(gh)(u)=f((gh)u)=f(g(h(u)))=fg(h(u))=((fg)h)(u). #

Св-во: f: XX, g: XX. Композиция отображение вообще говоря не коммутативна, т.е. f*gg*f.

Определение: Обратные отображения. Пусть , . Если , то – левое обратное отображение к , – правое обратное отображение к . Если , , то – двухстороннее обратное отображение к или обратное отображение. Обозначается .

Утв: Обратное отображение единственное.

Док-во: От противного . Пусть такой, что , , но . Тогда . Получим противоречие. #

Утв: Отображение – обратимо  – биективно.

Док-во: Лемма 1: Если , такое, что , то – иньективно, – сюрьективно.

а) Допустим, что – не инъективное отображение, т.е. , такое, что . Но противоречие; - инъективно .

б) Пусть , , т.е. – сюрьективно #.

4. (1 из 1) Критерий обратимости отображения для случай конечного множества.

5. (1 из 2) Бинарные отношения на множествах. Отношение эквивалентности. Примеры.

“>” Если – обратимо, то - биективно. – обратимо и .

Т.к. , (по лемме) - инъективно и сюръективно - биективно.

“” - биективно, т.е. по определению такой, что . Заметим, что , т.е. – обратимо.

Следствие 1° Если - биективно, то - биективно.

Следствие 2° ; - биективны, то - биективна, причем .

Утверждение.

Если и - инъективно, то - биективно.

Доказательство:

Надо показать, что сюръективно, т.е такое, что . Рассмотрим отображение вида: и последовательность вида: элементов множества .

Т.к. , то есть - конечное, то в бесконечной последовательности будут одинаковые элементы или существуют такие, что .

Пусть . Из , т.к. - инъективно и т.д. .

Рассмотрим , т.е. . #

Определение: Множества X и Y имеют одинаковую мощность (или равномощны), если существует φ: X→Y такое, что φ-биективно.

Множество М счетное, если М и N₀ равномощны.

Отношение на множестве.

Определение: Пусть X,Y – множества.

Всякое – бинарное отношение на множествах X и Y.

Если Х = Y, то O - бинарное отношение на Х. Элемент хХ находится в отношении к yY, если (х,у) О; обозначение: хОу.

Пример: “<” бинарное отношение на R, такое, что

Пример:

1-a

коорд.

Пример:

П

Определение: Бинарное отношение “~” на множестве Х называется отношением эквивалентности, если:

1. , – рефлективность

2. , из – симметричность

5. (2 из 2) Бинарные отношения на множествах. Отношение эквивалентности. Примеры.

6. (1 из 1) Разбиение множества и классы эквивалентности.

3) такое, что справедливо - транзитивность

Пример:

1. Выполняется.

2.

3.

Пример:

Т

Определение:

Множество класс эквивалентности. Любой – представитель класса эквивалентности .

Свойства отношения эквивалентности.

1° Множество классов эквивалентности по отношению “~” на множестве Х – разбиение множества Х есть разбиение множества .

!– разбиение множества Х, если :

1)

2) т.е. не пересекаются

Док-во:

1. Т.к хто X=, где - класс эквивалентности.

2. Класс эквивалентности однозначно определяется своими представителями, т.е.

: и .

: Пусть и .

Допустим, что классы эквивалентности пересекаются:

и , т.е. . #

Пример:

a, b, c – множество

{a}, {b,c}- классы эквивалентности

{a, b, c} = X

X = {a}{b, c}{c, b} = {a}{b, c}

7. (1 из 1) Основное свойство отношения эквивалентности.

8. (1 из 1) Фактор-множество. Примеры.

Свойство 2°

Пусть - разбиение Х. Тогда отношение эквивалентности «~» такое, что - классы эквивалентности относительно «~».

Док-во:

Рассмотрим отношение такое, что такое, что .

Покажем, что - отношение эквивалентности.

а) – рефлективно, т.е., т.к.

б) – симметрично, т.е.

в) – транзитивно, т.е. , . #

Определение

Разбиение множества X соответствующее некоторому отношению эквивалентности называется фактор-множеством множества X относительно отношения эквивалентности

Обозначается

Пример:

. Рассмотрим бинарное отношение на множестве X, такое что .

Очевидно, что - отношение эквивалентности. разбивается на классы эквивалентности :

Можно ввести: ;

Пример:

Все студенты одинакового роста.

а) Доказано для (но про одного студента нельзя сказать, что он одинакового роста, надо как минимум для ).

б) Для n студентов доказано. Докажем для n+1. Возьмем других n студентов:

.

9. (1 из 2) Алгебраические структуры- Определения и примеры полугрупп и моноидов.

9. (2 из 2) Алгебраические структуры- Определения и примеры полугрупп и моноидов.

Основные алгебраические структуры

Определение: n-арной операцией на множестве A называется любое отображение .

Если n=2, то - бинарная операция

n=1 – унарная операция

n=0 – считается, что выделяет фиксированный элемент из A.

Далее будем рассматривать бинарные операции.

Определение: Множество A с заданными на нём бинарными операциями называется алгеброй сигнатуры типа 2.

Далее будем рассматривать алгебры с 1 или 2мя бинарными операциями.

Определение: Бинарная операция “*” заданная на множестве A ассоциативна, если , коммутативна, если .

Определение: [множество с бин. операцией “”] называется единичным элементом, если .

Определение: X(*) – полугруппа, если “*” – ассоциативно.

X(*) – моноид, если

1) X(*) полугруппа

2) , - единичный элемент.

Свойство: Если в есть -единичный элемент, то он единственный.

Док-во: Допустим , -единичный элемент.

. Пусть. Тогда . Противоречие. #

Пример: .

“*” – коммутативна, не ассоциативно.

1)

2) #

10. (1 из 1) Определения и примеры групп.

11. (1 из 1) Определения и примеры колец.

Определение. Группой называется непустое множество А с бинарной алгебраической операцией (*) (будем называть умножением) такой, что выполняются следующие аксиомы:

1. - замкнутость относительно операции (*).

2. - ассоциативность операций (*).

3. - существование единичного элемента е.

4. - существование обратного элемента .

Определение. Группа называется коммутативной, если выполняется аксиома коммутативности:

5. - коммутативность операций (*).

Примеры групп.

1. - группа с операцией сложения чисел, где -множество целых чисел. Действительно, 0 – единица группы; - обратный элемент к

2. - группа с операцией сложения чисел.

3. - группа с операцией умножения чисел.

4. - множество квадратных матриц порядка n , определитель которых не равен нулю, является группой с операцией умножения матриц.

Определение

Кольцо – множество с двумя бинарными операциями К(+,*);

1. К(+) – абелева группа

2. К(*) – полугруппа

3. 

- дистрибутивность

- абелева группа, если (группа)

Если К(*) – моноид, то К(+,*) – кольцо с единицей

Если , то К(+,*) – коммутативное кольцо

Пример:

, где ,

- кольцо.

а)

б) ассоциативность.

в) Найдем единичный элемент в pZ относительно «». Пусть .

- коммутативное кольцо без единицы.