1. Множества и операции над ними. Отношение эквивалентности. Фактор множества.

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

Операции: пересечение, объединение, разность (дополнение), прямое произведение.

Отношение называется отношением эквивалентности, если выполнены 3 условия:

X~X

X~Y =>Y~X

X~Y ,Y~Z =>X~Z

Фактормножество: Пусть задано некоторое множество Х с отношением ~. Тогда множество всех классов эквивалентности называется фактормножеством и обозначается X/~

2. Отображения. Произведение отображений. Обратимые отображения.

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

Даны отображения g: xyи f:yz

Произведением fи gназывают их композицию (fg)(x)=f(g(x)) fg:xz

f: xyназывается обратимым, если существует g:yx, такое, что fg=e_yи gf=e_x. gобратимо к fи обозначается g=f^-1

3. Множество перестановок. Бинарная операция на множестве.

Перестановкой порядка N называют биекцию множества первых n натуральных чисел в себя. Множество всех перестановок порядка nобозначают S_n

Бинарной операцией на А называют отображение f: A²A

A*AA

4. Множество с одной операцией. Полугруппа. Группа. Примеры.

Группоидом называют множество (М;*) на котором определена бинарная операция *

Например (N;+)

Полугруппой называют группоид с ассоциативной операцией

Например: (2+5)+3=2+(5+3)

Группой называют группоид (G;*) такой, что:

1. * ассоциативна (a*b)*c=a*(b*c)

2. на G существует e€G a*c=e*a=a

3. для любых g€G существует g^-1€Gg*g^-1= g^-1*g=e

5. Множество с двумя операциями. Кольцо. Поле. Примеры

Кольцом (К, +, x) называют множество с двумя бинарными операциями, которые обычно назначают с + и *, обладающее следующими свойствами:

1. (К, +) – абелева группа (есть ассоциативность, нулевой элемент, противоположный элемент)

2. (К, x) полугруппа. Т.е. x ассоциативна

3. Операция x дистрибутивна (лево и право) относительно сложения +

a(b+c)=ab+ac

(a+b)c=ac+bc

Полем называют коммутативное кольцо с единицей, в котором каждый не нулевой элемент обратим:

1. (Р, +, х) поле, если (Р, +) абелева группа

2. (Р \{0}, +) абелева группа

3. х дистрибутивно относительно сложения

6. Изоморфизм алгебраических структур

(G, *), (H, x) называется изоморфными, если существует φ: GH такое, что:

1. φ – биекция

2. φ сохраняет операцию, т.е. φ(g₁*g₂)= φ(g₁)*φ(g₂)

7. Натуральные числа. Нод. Деление с остатком и алгоритм Евклида.

Натуральные числа – целые положительные числа.

НОД(a₁,a_2,…,a_n) называется d, такое, что: эти числа нацело делятся на d, и dнаибольший из положительных делителей этих чисел.

Алгоритм Евклида:

(5,4)=1

5=4*1+1

4=4*1+0 НОД(5,4)=1

8. Нок. Решение уравнений в целых числах.

М называется НОК(a₁,a_2,…,a_n)если М нацело делится на все эти числа, М наименьший общий кратный чисел a₁,a_2,…,a_n.

Целочисленным решением уравненияax+by=c называется пара чисел x,y€Z, такая, что при подстановке ее в уравнение получается верное равенство.

1. Если с dто целочисленные решения существуют

2. Если с d и (a,b)=1, то общее решение будет: x=x₀-bt

y=y₀+at

162x+15y=6

162=15*10+12

15=12*1+3

12=3*4+0

(162,15)=3 6 3 решение существует

54x+5y=2

(54,5)=1

54x+5y=1

54=5*10+4

5=4*1+1

1=1*5-1*4=1*5-(1*54-5*10)=-1*54+11*5

(x₀,y₀)=(-1,11)

(x₁,y₁)=(-2,22)

x=-2-5t

y=22+54t

Решение уравнения ax+by+cz=d

d=(a, b, c)

Для нахождения целочисленных значений:

1. kd₁+cz=d

d₁=(a,b)

2. ax+by=kd₁