Все материалы курса высшей математики в 91 школе, год выпуска 1987

Листок N 1. МНОЖЕСТВA.

Выдан 12.09.84.

"Множество есть многое, мыслимое как целое"
Георг Кантор 1845-1918

Опр. 1 Два множества A и В называются равными (A = B), если A и В содержат одни и те же элементы.

Опр. 2 Множество A называется подмножеством множества В, если каждый элемент из A содержится в В (A⊂В).

Опр. 3 Объединение: A∪B = { х | x∈A или x∈B}
Пересечение: A∩В = { х| x∈A и x∈B}
Разность: A\В = { х| x∈A и x∉B}

1. Написать определение дополнения A' и симметрической разности AΔВ.

2. Доказать, что для любых множеств A и В:
A⊂В ⇔ A∪В = В ⇔ A∩В = A.

3. Уяснить, что:
A∪A = AA∩A = A
A∪B = B∪AA∩B = B∩A
(A∪B)∪C = A∪(B∪C)(A∩B)∩C = A∩(B∩C)

4. Доказать, что:
а) A∪(B∩C) = (A∪B) ∩ (A∪C)
b?) A∩(B∪C) = (A∩B) ∪ (A∩C)
с) A\B= A \(A∩В) = (A ∪В)\В
d?) (A\В) ∪ (В\A) ≠ 0

5. Используя A∪A' = U и A∩A' = 0, доказать, что:
a) (A')' = A
b) (A∪B)' = A' ∩ B'
с) (A∩B)' = A' ∪ B'

6* Доказать и нарисовать рисунки
a) A\(A\В) = A∩В
b) A\(B∪C) = (A\B)∩(A\C)
c) A⊂В ⇒ A∩C ⊂ В∩C
d) A⊂C ⇒ A∪(B∩C) = (A∪B) ∩ C
e) A∩B = A∪B ⇔ A = В
f) A⊂В⊂C ⇔ A∪B = B∩C.

Листок 2. ЛОГИКА.

Выдан 19.09.84.

Логические операции: NOT = "не", AND = "и", OR = "или", ⇒ = "следствие", ⇔ = "эквивалентность".

1. Построить матрицы истинности:
а) для логических операций
б) для логической функции (a. AND. b) ⇒(с.AND.а).

2. Доказать:
а).NOT. (p. OR. q) ⇔ (.NOT.p .AND. .NOT.q)
b) ( (p⇔q) .AND. (q ⇔ r) )⇒ (p ⇔ q) транзитивность
с) ( (.NOT.p ⇒ q) .AND. (.NOT.p ⇒ .NOT. q) > ⇒ р ДОК. от против.

3. Выразить эквивалентность через остальные логические операции
б) "следствие" через NOT, AND, OR
в) OR через NOT, AND

4?. Уяснить и доказать, что всегда справедливы:
a) р ⇔ р
b) (p. OR. р) ⇔ (p. AND. p) ⇔ р
c) (p. AND. q). AND. г ⇔ p. AND. (q. AND. r)
d) p. AND. (q.OR. r) ⇔ (p. AND. q). OR. (p. AND. r)
e,f) справедливы ли эти формулы в случае OR ←→ AND ?

5*. Из некоторого сложного выражения A получили высказвание В заменой OR←→ AND и всех простых высказываний на их отрицния. Доказать,что .NOT.A ⇔ В всегда истинно.

6*. Брауну,Смиту и Джонсу предъявлено обвинение в соучастии в ограблении банка. Похитители скрылись на поджидавшем их автомобиле. На следствии Браун показал , что преступники были на синем "Бьюике", Джонс сказал что это был черный "Крайслер", а Смит утверждал, что это был "Форд Мустанг" и ни в коем случае не синий. Стало известно, что желая запутать следствие каждый из них указал правильно либо марку машины, либо ее цвет. Какого цвета был автомобиль и какова его марка?

Листок 3. ЛОГИКА.

Выдан 6.09.84.

Законы логикиЗаконы теории множеств.
1.a.OR.а ⇔ аидемпотентностьA∪A = A
2.а. AND. а ⇔ аидемпотентностьA∩A = A
3.a. OR. b ⇔ b. OR. акоммутативностьA∪B = B∪A
4.a. AND. b ⇔ b.AND.а коммутативностьA∩B = B∩A
5.a.OR. (b. OR. с) ⇔ (a. OR. b). OR. сассоциативность A∪(B∪C) = (A∪B)∪C
6.a. AND. (b. AND.c) ⇔ (a. AND. b). AND. сассоциативность A∩(B∩C) = (A∩B)∩C
7.a. OR. (b. AND.c) ⇔ (a. OR. b). AND. (a. OR.c)дистрибутивность A∪(B∩C) = (A∪B) ∩ (A∪C)
8.a. AND. (b. OR. c) ⇔ (a. AND. b). OR. (a. AND. c) дистрибутивность A∩(B∪C) = (A∩B) ∪ (A∩C)
9.NOT.NOT.a ⇔ аЗакон двойного отрицания(A')' = A
10(p⇔q) ⇔ (q⇔p)
11.(p⇒q) ⇔ (.NOT.q ⇒ . NOT.p)
12..NOT. (p. AND. q) ⇔ . NOT.p .OR..NOT.q
13.NOT. (p. OR. q) ⇔ NOT.p .AND. .NOT.q
14.(p⇔q) ⇔ (.NOT. ⇔.NOT.q)
15.p⇒(q⇒r) ⇔ q⇒(p⇒r) закон перестановки посылок
16.(p .AND. (p⇒q) )⇒q закон заключения
17.p ⇒ (p.AND.q) закон введения
18.(p.OR.q).AND. (.NOT.q) ⇒ pзакон удаления
19.(. NOT.p ⇒ q). AND. (.NOT.p ⇒ .NOT.q) ⇒ p закон док. от противного
20.(p⇒q).AND.(q⇒г).AND.(г⇒р) ⇔ (p⇔q⇔r)
21.(p⇒q).AND.(p⇒r) ⇒ (p ⇒ (q.AND.r))

1. Путешественик приехал в один ио двух городов М или N. Он задает вопрос, на который может получить ответ "да" или "нет", причем ответ может быть правдой или ложью. Что следует спросить что бы определить путешественику, куда он попал ?

2. Контрольная работа называется легкой, если каждую задачу решил хотя бы один ученик. Контрольная работа называется простой, если хотя бы один ученик решил все задачи. Бывают ли а) нелегкие простые и б) легкие непростые работы?

3. Известно, что процент психов среди математиков выше, чем среди остальных людей. Доказать, что процент математиков среди психов больше, чем среди других людей.

4. Запишите отрицание высказывания без частицы "не" "В некотором поезде Москва -Владивосток в каждом вагоне найдется свободное место".

5.Найдите X, если .NOT.(X .OR. A) .OR. .NOT.(X. OR. .NOT.A) = B

Опр. Последовательность называется ограниченной сверху, ЕСЛИ:
∃ С такое, что для ∀ xn: xn < С.

6. Записать, используя кванторы, определения:
а) последовательности, ограниченной снизу
б) ограниченной последовательности.
в) неограниченной последовательности.

7.* Даны три неопределеных высказывания, заданых на множестве всех действительных чисел.
A(x) = {x - целое число}
В(х) = {х2 - 3*х - целое отрицательное число }
С{x) = { х+1/х - целое положительное число }
При каких х ложно одно и только одно из этик высказываний?

8.В следующих теоремах выделите условие, заключение и разъяснительную часть. Для каждой теоремы сформулируйте обратную противоположную и противоположную обратной. Укажите, какие из этих теорем верны.
а) Если в четырехугольник можно вписать окружность, то этот четырехугольник представляет собой ромб.
b) Если параллелограм является прямоугольником, то вокруг него можно описать окружность.
в) Если квадратное уравнение не имеет двух различных корней, то дискриминант этого квадратного уравнения неположителен.

ЛИСТОК 4. ИНДУКЦИЯ.

Срок выдачи 2.10.84.

1. а) 1+2+3+...+n = n(n+l)/2
b) 12+22+32+. . - +n2 =n (n+1)(2n+l)/6
c) 12-22+32-42+...+(-1)n+1*n2 = (-1)n+1*n(n+1)/2
d) 13+23+33+...+n3
е) 1*2+2*3+... +n(n+l) = n(n+l)(n+2)/3
f) 1*4+2*7+...+n(3n+1)
g)(1-1/4)(1-1/9).....(1-1/(n+1)2)

2. Найти: а) 1/(1*2)+1/(2*3)+...+1/n/(n+1)
b) 1+3+5+...+(2n-1)
с) 1/1/3+1/2/4+1/3/5+...+1/n/(n+2)

3. а) 1*1!+2*2!+...+n*n!=(n+l)! - 1
b) 1/2!+2/3!+...+n/(n+1) !

4. "Доказать", что все треугольники подобны.

5. Составить таблицу для первых 5 членов, вывести и доказать формулы для суммы ряда
а) 1+2+22+23+...+2k-1
b) 1/3+1/15+.. .+l/(4n2 - l)
с*) 1/1/2/3+1/2/3/4+ ... +1/(k-l)/k/(k+1)

6. Дано: а > -1. Доказать: (l+a)n ≥ 1+n*a

7. a) n5 - n делится на 5
b) 62n - l делится на 35

8. a) 2*n½ > 1+2+3+...+n > n½
b) 1/(n+1) + 1/(n+2) + ... 1/(3n+1) > 1
c)4n/(n+1) < (2n)!/n!2

9.* ak+a+l/a целое ⇒ ak + a-k ТОЖЕ ЦЕЛОЕ

10. Доказать,что любую сумму денег, большую 7 копеек можно уплатить без сдачи монетами по 3 и 5 копеек.

11. На какое максимальное число областей делит
а) n прямых плоскость?
b) n плоскостей пространство ?

12.** 16 + 26 + 36 +...+ n6
1k + 2k + 3k +...+ nk

Листок N5 (Дополнительный). Разная ЛОГИКА

Выдан 3.10.84

- Нужно всегда говорить то, что думаешь, - заметил Мартовский Заяц.
- Я так и делаю, - поспешила объяснить Алиса. По крайней мере... По крайней мере я думаю то, что говорю... а это одно и тоже...
- Совсем не одно и тоже, - возвразил Болванщик. Так ты ещё чего доброго скажешь, будто "Я вижу то, что ем" и "Я ем то, что вижу" - одно и тоже!
- Так ты ещё скажешь, будто "Что имею, то люблю" и "Что люблю, то имею" - одно и тоже! - подхватил Мартовский Заяц.
- Так ты ещё скажешь, - проговорила, не открывая глаз Соня, - будто "Я дышу, пока сплю" и "Я сплю, пока дышу" - одно и тоже!
Льюис Кэролл. "Алиса в стране чудес".

1. Справедливо или ложно высказыванние на следующей строчке:
"Высказывание, записанное на этой строчке, ложно".

2. Верно ли рассуждение: "Если матанализ не труден, то он полезен. Матанализ не интересен или бесполезен. Однако матанализ интересен. Следовательно, матанализ труден."

3. Верно ли объявление о макулатуре на первом этаже нашей школы?

4. В моей комнате свет даёт только одна лампа дневного света, зато включать и выключать её я могу независимо при входе в комнату, около дивана и над письменныи столом. Нарисуйте принципиальную схему проводки в моей комнате.

5. Известно (задача 3 из Л-2), что все логические операции можно выразить через операции "не" и "и". Придумать операцию, через которую (и только её!) можно выразить "не" и "и", а следовательно и всё остальное. Записать некоторые законы логики, использую только одну эту операцию.

6. Записать, используя кванторы:
а) Множество М содержит хотя бы один элемент
б) в M не более одного элемента
в) в М ровно один элемент
г) ровно два элемента
д) ровно три элемента

7. Приведите следующие формы к нормальному виду:
а) форма "и":
(Х или У) (Х или не У), Х и (не У или Z), (Х след Z) и Х и У
б) форма "или":
XYZ или неXнеYнеZ (X Тогда и только т. У) и не (Х и Z)

Листок 6. ДЕЛИМОСТЬ

Выдан 20.10.84.

В этом и следующем листочках а...z - натуральные!

Опр.1. Для любого a, b: a⋮b ⇐df⇒ ∃k: a=kb.
Опр.2. d общий делитель a, b ⇐df⇒ a⋮d.AND.b⋮d
Onp.3. d=H0Д(a, b) ⇐df⇒ d - общий делитель a, b AND d делится на любой общий делитель а,b.
Опр.4. a, b -взаимно просты ⇐df⇒ НОД(а,b)=1.
Опр.5. Р ∋ р-простое ⇐df⇒ ∀k (k<р) НОД(k,p)=1
Опр.6. l - составное ⇐df⇒ l - не простое.

1. Сформулировать опр 6 без отрицания.

1.Доказать,что если р не делится на ∀ k: (1 < k ≤ √р)⇒ p ∊P.

2*. Для ∀ а1, а2,. ., an ∃ только один НОД(а1, а2,. ., an). Для этого
а) Расмотреть функцию ( линейную комбинацию) y=а1y1 + а2x2+...+anxn и док., что она делится на люб. общ. делитель
б) разделив аi с остатком на min у, доказать: min у =НОД(а1, а2,. ., an)

3. ДОК. A = {а1, а2,. ., an}.AND. A = A1A∪A2A∪. .∪An .AND. Ai≠0 ⇒
НОД(A) = НОД(НОД(A1), НОД(A2),. ., НОД(An))
Указание св-во 3

4. а,b, с -вз. просты ⇔ ∃х,у,z: ax+by+cz=1

5. bc⋮a .AND. НОД(а,b)=1 ⇒ c⋮a

6** Для док-ва алгоритма Евклида расмотрим следующую програму на языке BASIC91.

  1. Ввести a, b
  2. Присвоить i=1
  3. Найти такие q[i] and r[i], что a=q[i]*b+r[i]
  4. Если r[i]=0, то перейти к строке 7
  5. Переобозначим a=b, b=r[i], i = i + l
  6. Вернуться к 3 строке.
  7. Напечатать: "НОД(а, b)= r[i-1] Докажите !"

Опр. 7. Каноническим разложением КРАЗом для a наз. a = p1i1 * p2i2 * ... * pnin, где все pi простые.

7* Используя КРАЗ сформулировать и доказать критерий взаимной простоты n чисел.

8.Способ получения НОД из КРАЗа.

9. Аналогично НОД определите НОК, сформулируйте утверждения аналогичные 3, 5, 8
b* докажите их

10! НОК(а,b)=а*b/НОД(а,b)

11. а2 - b2 = 1985

11. Док., что простым чисел бесконечно много.

12* Для ∀ k ∃ простое р k≤p≤2k.

13.Решить урав. относительно х, у: а*х + b*у = с
b)** Когда и как можно найти все его решения.

Листок 7. ЦЕЛЫЕ ЧИСЛА И СРАВНЕНИЯ.

Выдан 27.10.84.

В листке: m, n - натуральные, p, q - простые, остальные - целые, если не оговорено особо.

1. ЦЕЛЫЕ ЧИСЛА.

10. Если записать в обратном порядке цифры любого натурального числа, то разность исходного и нового ⋮ 9.

11. аx2 + bx + c для любого k РАВНО ЦЕЛОМУ ⇔ 2а, а+b, с ∋ Z.

12. Сумма кубов трех последовательных чисел ⋮ 9.

13. 222333 + 333222 ⋮ 13

14. ∀n ∃x : nx+1 - составное.

15. Найти все n: в 22n + 5 = m2.

16. 9n+1 кончается не более 1 нулём.

17. n ≥ 2 ⇒ 22n+1 оканчивается на 7.

18. (2k+1)2≡1 (mod 8)

19.Найти две последние цифры 7999.

2.ПРОСТЫЕ ЧИСЛА.

20. 2р+1 ∈ Р, р >3 ⇒ 4р+1 ∉ Р.

21. Сколько разных n: n<p3 .AND. НОД(p3,n)=1 ?

22. 8*р2 + 1 ∈ Р ⇔ p=3

23. 2n+1 ∈ Р ⇒ n - степень 2.

24. "Малая теорема Ферма". Доказать, что для любых m, p: mp-m⋮p

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

26. p = m2 - n2 : p=?

27. ВСЕГДА НОД(21n+4,14n+3)=1

28. НОД(m,n)=1. Доказать, что mx+ny=mn не имеет решения в натур.

29. НОД(a3+2a,a4+3a2+1)=1 ВСЕГДА

3. УРАВНЕНИЯ В ЦЕЛЫХ ЧИСЛАХ.

30. x*y = x + y

31. 60x -77y =1

32. 6x2 + 7y2 = 74

33. 2ху+3у2 = 24

34. x2 + xy + y2 = (xy)2

35. m2 -nm + 2m -3n = 11

36. (m+n) = (m - n)2

37* xy + 1 = z (x,y,z - простые)

38. 2x2 - 5y2 = 7 не имеет решений.

ТЕОРЕМЫ О СРАВНЕНИЯХ

Если два числа а, b при делении на m дают один и тот же остаток r: 0≤r<m то числа a, b называются сравнимыми по модулю m: a≡b(mod m)

40. a≡b(mod m) ⇒ a=b+mt .AND. a-b ⋮ m

41? Обратная 40.

42?Сравнения по одному модулю можно почленно складывать:
a1≡b1(mod m), a2≡b2(mod m),..., aN≡bN(mod m)⇒ a1 + a2 + ... + aN ≡ b1 + b2 + ... + bN (mod m)

43?Сравнения по одному модулю можно почленно перемножать:
a1≡b1(mod m), a2≡b2(mod m),..., aN≡bN(mod m)⇒ a1 * a2 * ... * aN ≡ b1 * b2 * ... * bN (mod m)

44. Обе части сранения можно разделить на их общий делитель, если этот делитель и модуль - взаимно простые числа.

45.Обе части сравнения и модуль можно умножить на одно и то же число.

46. Обе части сравнения и модуль можно разделить на их общий делитель.

47. ЕСЛИ сравнение a≡b имеет место по нескольким модуляи, то оно имеет место по модулю, равному НОК этих модулей.

48. Если сравнение имеет место по модулю m, то оно имеет место по любому делителю числа m.

49. Если одна часть сравнения и модуль ⋮z ⇒ другая часть ⋮z.

5. ЗАДАЧИ НА СРАВНЕНИЯ

50.Найти остаток от деления 520 на 24

51. 3105 + 4105 ⋮ 181

52. (32995+6)18 ⋮ 112

53. 1919 + 6969 ⋮ 44

54. 260 + 730 ⋮ 13

55. p2 - q2 ⋮ 24 (p,q > 3)

56. .NOT.((a2+3a+5)⋮ 121)

57. x+y ⋮ 7 ⇒ x7 + y7 ⋮ 49

58. n≡1(mod 3) .AND. n≡33(mod 37) .AND. n≡m (mod 111) Найти m.

Листок 8. Классы вычетов.

Выдан 21.11.84 Закрытие 1.12.84

"Кто не с нами, тот против нас!"

Опр.1 B1,B2, ...,Bn -разбиение мн-ва B на классы ⇐df⇒ (B1∪B2∪...∪Bn = B) .AND. (∀i,j: i≠j ⇒ Bi∩Bj = ∅)

Onp.2 "i"-классом по модулю m (пишем Ai,m OR Ai OR A[i]) называется Ai={a| a≡i (mod m), a≥0}

1. Доказать , что существует m различных классов по mod m.

2. а)(∀ x∈ Ai и y∈ Aj)⇒(x+y)∈ Ai+j
Это означает, что Ai+Aj=Ai+j
b) A0 + Ai = Ai

3. Аналогичные утверждения для Ai*Aj

5. а)∀i,j ∃k,h: Ai+Aj=Ak .AND. Ai+Aj=Ah
b) ∃A0, A1: A0 + Ai = Ai; A1 * Ai = Ai
c) Ai+Aj = Aj+Ai; Ai*Aj = Aj*Ai
d) Ai + (Aj+Ak) = (Ai + Aj) + Ak; Ai * (Aj*Ak) = (Ai * Aj) * Ak;
e) (Ai + Aj) * Ak = Ai * Ak + Aj * Ak
f) ∀i ∃j: Ai+Aj=A0
Примечание: ∀ {Ai} удовлетворяющее 2,3,5 называется Комутативным Кольцом с Единицей.

Опр. 3* n*Ai =df= Ai + Ai + ... +Ai n слагаемых
Ain =df= Ai * Ai * ... * Ai - n сомножителей

6. Функция f(a) -"правильная", т. е. ∀ i ∃ j ∀ a: а∈Аi ⇒ f(а)∈Аj записываем: f(Аi)=Аj
а) ∃ci: f(Ai)=c0*Ain +c1*Ain-1+...+cn*Ai
b)* f(Ai)=A[f(i)]
с) опишите множество правильных функций.

7. Пример, когда Ai*Aj=A0 , но Ai≠A0 AND Aj≠A0

8. р∈Р ⇔ ( (Ai,p≠A0,p .AND. Aj,p≠A0,p) ⇒ (Ai,p*Ai,p≠A0,p))

Опp 4. Полной системой вычетов по некоторому модулю (PSV) называется мн-во чисел, взятый по одному из каждого класса по этому mod.

9. Написать примеры PSV по модулю 12,7.

10. НОД (a, m)=1; x1, х2,... xm - попарно не сравнимы по модулю m: yi=a*xi+b ⇒ {y1, y2,... ym} = PSV(mod m)

11. НОД (a, m/d)=d; x1, х2,... xm - попарно не сравнимы по модулю m/d; y1, y2,... ym: yi=a/d*xi+b ⇒ {y1, y2,... ym} = PSV(mod m/d)

12. НОД (m, n)=1; {x1, x2,... xm} = PSV(mod m); {y1, y2,... yn} = PSV(mod n)⇒ {z | z = m*xi+n*yj} = PSV(mod m*n)

13. s=s1*s2*...*sn и все si и sj попарно взаимно просты; xi пробегает все значения PSV(mod si) ⇒ {z | z = s/s1*x1+s/s2*x2+...+ s/sn*xn} = PSV(mod s)

Опр.5 НОД(Ai)=d ⇐df⇒ ∃ d ∀ a∈Ai НОД(a,m) =d

14. Доказать существование и единственость НОД(Ai)

15. НОД(A8,6) и доказательство его единственности.

16. Верно ли,что НОД(Ai)=d ⇔ {а,b}⊂Ai: НОД(а,b)=d?

Опр 6. приведеной (неполной) системой вычетов (NSV) по модулю m называется мн-во чисел, взятых по одному из каждого класса Ai причем НОД(Ai)=1

17. Написать по 3 NSV anm m=4; 5; 18

18. Сформулировать (?) и доказать (*) для NSV свойства, аналогичные свойствам PSV.

19* Теорема ЭЙЛЕРА
NSV(mod m) содержит k чисел; а≥1; НОД (a, m)=1 ⇒ аk≡1 (mod m)
Указание: {x1, x2,... xk}=NSV ⇒{a*x1, a*x2,... a*xk}=NSV

20. Остаток от деления 1358964 на 44

21. ∀a: f(a)≡ 0(mod m) ⇒ ∀b ≡ a (mod m): f(b) ≡ 0 (mod m)

"Практика -критерий истинности"

22. Решить с помощью 21
a) х3 - 2х + 6 ≡ 0 (mod 11)
b) х4 - х3 - х2 + 5х - 2 ≡ 0 (mod 6)
c) х3 - х ≡ 0 (mod 6)
d) 3020 ≡ х (mod 7)
e) 15х + 11 ≡ 4 (mod 10)
f) х2≡ 2 (mod 9) .AND. х3 + 3 ≡ x (mod 9)

23 a) x ≡ 9 (mod 34) .AND. x ≡ 4 (mod 19)
b) x ≡ 29 (mod 29) .AND. x ≡ 9 (mod 35)
c) 7x ≡ 5 (mod 11) .AND. 3x ≡ 2 (mod 5)

24. (∃ k ≡ a (mod n) .AND. k ≡ b (mod m)).AND. НОД(m,n) = d) ⇒ | a - b | ⋮ d

25. a) x ≡ 2 (mod 7) .AND. x ≡ 5 (mod 9) .AND. x ≡ 11 (mod 15)
b) x ≡ 6 (mod 17) .AND. x ≡ 4 (mod 11) .AND. x ≡ 13 (mod 8)
c) x ≡ a (mod 25) .AND. x ≡ b (mod 27) .AND. x ≡ c (mod 59)

26. a) 9x2 + 29x + 62 ≡ 0 (mod 64)
b) x3 + 2x + 2 ≡ 0 (mod 125)

Листок 9. Системы счисления и признаки делимости.

Выдан 30.11.84 Закрытие 10.2.84

1. Выполнить действия над римскими цифрами:
a) CCCLXVI + XLVIII b) LVII * XCI с) CDXLIV + CLVI

2. Составить таблицу умножения и сложения для n = 6.

3. Записать числа 91, 57, 1953, 1984, 444 в
a)двоичной b)восьмеричной c) шестнадцатиричной d) двоично-десятичной

4. Составить алгоритм умножения двоично-десятичного числа на двоично-десятичное число 10.

Далее все числа шестнадцатиричные.

5. Сложить столбиком:
1234 + ABB1 ; 1E00 + 598 ; 5DD1 - 7EEF

6. Отбрасывая пятый и старше разряды сложить числа:
1234 + ЕЕЕЕ; FFE1 + FFEE; AAAA + 8888 ; FFFF + 1; FFF0 + 11

7. ---//--- умножить числа: FFFF * 2; E012 * 10

Таким образом, при сложении и умножении число FFFF ведет себя как -1, FFFE как -2, FFFO как -F. Поэтому будем считать числа начинающиеся с 0...7 > 0, а числа начинающиеся с 8...F < 0. Эта запись называется записью в дополнительном коде.

8. а)3аписать в доп. коде 1EF; -111; -2ABF
b) Обосновать правомерность записи в доп. коде
c)* Найти условие, когда машина должна выдавать сообщение об ошибке.

9*. Раскажите СВОЕМУ студенту об устройстве других систем счисления: славянской, норманской, вавилонской и других.

Их премущества и недостатки. "Сначала в клетке делится ядро..."

10. Представляя число в обычной десятичной системе, вывести признаки делимости на а) 2,5,10 б) 3,9,11

11. Представля число в системе с основанием 100, вывести признаки делимости на а) 25, 4 б) 101

12. Тоже самое в системе с основанием 1000 для
a) 8, 125 b) 7, 11, 13 c) 37, 27 ( 8 * 125 = 1000; 7 * 11 * 13 = 1001; 37 * 27 = 999)

13* Вывести другие признаки делимости.

14* Разложить на множители а) 244943325 b) 282312246671737 с) свой телефон

Зачёт в 8В по теории чисел

Листок 6

Определение простых, взаимно простых и попарно взаимно простых чисел. Разница и общее. Понятие линейной комбинации, доказательство (полное) задачи. Использование этой теоремы для решения задач типа N5. Алгоритм Евклида: что он и(или) как делает. НОД и НОК: их определения и общие черты.

Листок 7

Если за контрольную оценка 1 - 2 или 3=2, то контрольную надо переписать. Если за контрольную 3 или 3-, то решить одну задачу из раздела 1 -2. Если не решены задачи (не более 5) то потребовать доказательства теорем о сравнениях (в два раза большем колличестве)
В любом случае человек должен доказать не менеее двух теорем о сравнениях

Листок 8

Все определения. Их понимание. Интерпритация задачи N5 (зачем ?) Примеры полной и неполной системы вычетов по одному модулю. Их связь. Как из неполной получить полную и наоборот. Когда из обоих частей сравненя можно извлекать корень. Формулировка теоремы Эйлера и её применение или формулировка теоремы (возможно, с доказательством). Китайская теорема об остатках.

Листок 9

Почему применяются другие системы счисления? Почему запись в дополнительном коде - корректная математическая операция? Пример применения всевозможных признаков делимости при разложении длинного натурального числа

ЛИСТОК 10. Дополнительный. Теория чисел.

1. Решить в целых числах
a) 19*x2 + 28*y2 = 729
b) x*y/z + x*z/y + y*z/x = 3
c) a4 + 4*b4 = 2*c4 + 8*d4
d) 1 + x + x2 + x3 = 2y
e) 1! + 2! + ... + x! = y2
f) x + y + z = x*y*z в натуральных числах.

2. Доказать: НОК(1,2,3,...,2*m) = НОК(m+1,m+2,...,2*m)

3. Доказать: если a - число делителей натурального числа b, то произведение всех делителей равно квадратному корню из ba

4. В десятичной записи числа встречаются цифры 1, 3, 7, 9. Доказать, что можно переставить цифры так, что получится число, делящееся на 7.

4. Доказать, что если натуральные числа f, b, c удовлетворяют условию an + bn = cn (теорема Ферма), то a, b, c больше или равно m

5. Доказать, что если целые числа a, b удовлетворяют соотношению 2*a2 + a = 3*b2 + b, то (a - b) и (2*a + 2*b - 1) - квадраты целых чисел.

6. Найти все простые числа p, для которых 4*p2+1 и 6*p2 - 1 - тоже простые.

7. Решить в рациональных числах 1/x + x = целому числу.

8. Найти число различных счастливых билетов

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

10. а) Если бы четверть от двадцати равлялась четырём, то чему бы равнялась треть от десяти?
б) добавьте 3 к 182, что бы результат получился меньше 20
в) Какие три цифры при умножении на 5 дают 6?
г) Найдите дробь, у которой числитель был меньше знаменателя и это свойство сохранялось бы при переворачивании дроби.
д) напишите 5 нечетных цифр, которые в сумме дают 14.

11. Можно ли найти числа a и b, что ab + ba = 1984 (пример 37 + 73 = 1844)

12. Съезд Объединенного общества странствующих попрошаек собрался, что бы решить вопрос о том, следует ли объявлять забастовку, требуя сокращения рабочего дня и увеличения податей. Было решено, что при голосовании те члены общества, которые отдадут свои голоса в пользу забастовки, останутся стоять, а те, кто против, сядут.
- Джентельмены, - сказал председатель собрания после подсчета голосов, - имею удовольствие сообщить, что забастовка утверждена большинством, состовляющим 1/4 опозиции (громкие возгласы одобрения)
- Господин председатель, - крикнули сзади, - кое кто из нас не сиог сесть!
- Почему?
- Да здесь нет стульев
- Тогда, быть может те, кто хотел, но не смог сесть, не откажутся поднять руки... Я вижу, вас 12 человек, так что забастовка отменяется большинством в один голос (свистки и беспорядок в зале). Сколько членов Общества попрошаек участвовало в голосовании?

ЛИСТОК 11. (Группы) ОТОБРАЖЕНИЯ И ПОДСТАНОВКИ.

Выдан 12.01.85. Закрытие 20.01.85

Отображения.

"Кесарю - кесарево...!"

Говорится, что задано отображение (функция) f из множества A в множество B, если каждому элементу х из A поставлен в соответствие некоторый элемент из В, обозначаемый f(x). f(x) называется образом элемента x. Пусть y ∈ B. Всякий элемент x из A, для которого f(x) = у называется прообразом элемента у.

Опр. 1 Отображение f A→В называется
а) на(ложением, если каждый элемент из B имеет хотя бы один прообраз
б) в(ложением ,----------:---//-----------не более одного---//
в) взаимо-однозначным(обратимым)----//----ровно один ---//----

1. Пусть f ставит в соответствие каждому городу Советского Союза первую букву его названия на русском языке. Будет ли f отображением НА русский алфавит?

2. Расмотрим отображение целых чисел в множество неотрицательных целых чисел:
a) f(n) = n2       b) f(n) = |n|
с) f(n) = { 2n, если n ≥ 0 AND 2|n| - 1, если n < 0 }
Какие из них отображения на, в,обратимые?

3. Привести свои примеры наложений, вложений, взаимо-однозн. отоб.

4.Пусть A - конечно и f:A → A. Тогда f-наложение ⇔ f-вложение. Верна ли зта теорема , если A - бесконечно?

Опр. 2 Бинарным отношением с операцией &, называется отображение & A⊗A в A.

5. На множестве 1) всеч четных 2) всей нечетных 3) всех отрицательных целых чисел расмотрите операцию а) вычитания б)умножения. В каких случаях получается бинарная операция ?

Подстановки.

Опр. 3. Подстановкой называется взаимо-однозначное отображение множества {1, 2, 3,..., n} в себя. Подстановку можно обозначать так
f = 3124
2314
( при этом f(3) = 2, f(1) = 3 и так далее)

6. Являются пи подстановками?

1234
2431
;
4123
1224
;
1432
4513
;
12345
24315
;
3124
3241

Какие из них совпадают? (вспомните,когда две функции равны)

Опр.4 Произведением подстановок f, g называтся их композиция (Последовательное выполнение f, а потом g. У нас (f*g) (x)=g(f(x)). Очевидно, что операция "произведение подстановок" есть бинарное отношение на множестве подстановок одной длины

7. Чему равно: а)
231
321
*
132
321
b)
132
321
*
2312
321
c)
2341
4123
*
2341
4123
Опр 5. Расширением подстановки
123...m
x1x2x3...xm
до любой произвольной длины n ≥ m называется подстановка
123...m m+1m+2...n
x1x2x3...xm m+1m+2...n
В дальнейшем будем формально полагать любую подстановку равной ее расширениям, а операцию * заданой на соответствующим образом расширенных подстановках.

8. Доказать,что "новое" произведение есть биекция множества всех подстановок.

9. Пусть f, g, h - подстановки, которые возможно перемножать. Всегда ли верно a) f*(g*h) = (f*g)*h b) f*g=g*f ?

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

10. Известно f * g = e Найти g (обратную), если
f = 1234
3241

11. Доказать, что для каждой f найдется единственная g, такая что f*g = g*f = e. Такая подстановка называется обратной и обозначается f'.

Циклы

Опр 7. Циклом называется подстановка вида:

x1x2 x3...xk-1xk xk+1xk+2... xn
x2x3 x4...xkx1 xk+1xk+2...xn

Обозначение (x1, x2, x3, ..., xk). k - длина цикла

12. Пусть а = (1,2,3); b = (2,4); с=(4,5); Найти a*b b*a а*c c*a.

Циклы (1,2,3) и (4,5) называются независимыми,так как они "передвигают" разные элементы. Ясно, что если a и b независимые то a*b = b*а.

13.Представить подстановку

123456
354126
в виде независимых циклов.

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

Опр 8. Транспозицией называется цикл из 2х элементов.

14. Доказать,что любой цикл можно разложить в произведение транспозиций (и не одним способом). Привести примеры.

15.Доказать,что число транспозиций в различных разложениях одного и того же цикла или всегда четно или всегда нечетно.

Уважаемый товарищ преподаватель

Дорогой Друг!!!

Прежде всего, позволь пожелать Тебе успешной сдачи всех оставшихся экзаменов. Ответим отличной успеваемостью на повышение обороноспособности нашей Родины! Дв здраствует советское студенчество - самое студенческое во всём мире! Шире связь науки и производства, города и деревни, вуза и школы, Сов. Армии и XV Всемирного Фестиваля Молодёжи и Студенчества!

Однако школьники уже пошли в школу. У них начался "матанализ". Поэтому просьба: выбрать за время сдачи очередного листочка время, сообщить своим школьникам о том, когда ты придёшь в школу и осуществить приём задач в указанный срок. А теперь

Указания по приёму 11 листка

N1. Нет, потому что f(города) ≠ Ъ

N2. а) = "в" b) "на", но не взаимюодноз. c) Взаимооднозначное

N3. Просите, что бы эти примеры не были похожи, как близнецы.

N4. Чисто по определению.

N5. В случае 1б 2б получается бинарная операция, в остальных случаях мы выходим за пределы множества.

N6. б) не подстановка (22) в) не подстановка есть 5; первая подстановка равна последней
7a
231
213
b
132
231
c
2341
2341
=
1234
1234

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

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

10. Постепенно привести к мысли, что достаточно перевернуть подстановку

11. требовать доказательства того, что перевернутая подстановка - тоже подстановка.

12. Предварительно записать циклы в виде обычной подстановки, а затем произвести действия.
ab =
1234
4312
ba =
1234
2413
ac = ca =
12345
23154

13. (1 3 4)(2 5)(6)

14. Одним из способов, которым можно представить, это произведение транспозиций из первого элемента цикла со всеми остальными последовательно, слева направо. Очевидно, что существуют и другие способы.

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

Следующий листочек "Определения и примеры групп" будет выдан тоже на неделю 18 - 22 января.

Спасибо!!!

да, совсем забыл:

С новым годом!

Пусть наступивший 1985 не будет 1984!

Листок 12. ПРИМЕРЫ ГРУПП.

Выдан 19.01.85 Закрытие 29.01.85

"От абстрактного к конкретному ..."

В этом листочке все a, b, c, x, у,... принадлежат множеству G.

Опр. ГРУППЫ. Множество G называется группой , если
а) на нем задана бинарная операция
б) для любых a, b, c: a*(b*c) = (a*b)*c (ассоциативность)
в) в G имеется элемент е, называемый единичным, такой что для любого элемента a: е*а = е (левая единица)
г) для любого элемента а сущ. а', такой что: а'*а=е (левый обратный)

Опр.2 Абелевой или коммутативной группой называется группа, для любых элементов a, b: a*b = b*а

1. Являются ли группами и абелевыми группами:
а, б) Множество целых чисел относительно операции + или *;
в, г) Множество целых чисел без нуля относительно операции + или *;
д) Множество действительных чисел без нуля по умножению
е) множество всех перемещений плоскости
ж) множество подстановок
з) множество всех линейных функций f(x) = kx + b с k≠0 с операц. композиция

4. а) Доказать единственность единичного элемента т. е. если х≠е, то существует b b*x≠b.
б) обратного элемента для каждого а.

тоже 4. Найти а) e'' 6) a''
в)Доказать: (ab)' = b'a'
(Пиджак надевают после рубашки, а снимают раньше...)

5.Для любых элементов а и b найдется ровно
один х такой что а*x = b
один x и один y, такие что ax = b и ya = b
(вспомните, что такое ровно один)

6. Упростите b'a'bb'aba b) найти у: ayba'= baab'a'

Опр 3.
m-натуральное: a1 =df= a; am+1 = a * am;
m = 0: a0 =df= e;
m - целое отрицательное am = (a-m)'

7. (am)' = (a')m

Докажите, что для всех натуральных m, n:
8. am * an = am+n; a0 = e
9. (am)n = am*n

10. Построить группу на основе PSV
mod 5 с операцией сложение
mod m с операцией сложение

0пр.4 Симметрией фигуры Ф называтся любое перемещение F: F(Ф)=Ф. Композиция двух симметрии фигуры Ф есть снова симметрия Ф, и множество всех симметрий образуют группу (проверьте). Если фигура Ф многоугольник, то, занумеровав его вершины, можно каждой его симметрии поставить в соответствие подстановку, где каждому номеру вершины ставится в соответствие номер образа.

11. Записать в подстановкак все симметрии
а) правильного треугольника
б) квадрата

Опр. 5 Группа всех симметрий правильного n-угольника называется группой ДИЭДРА и обозначается Hn

12. Показать,что композиция симметрии соответствует произведение подстановок.

1. G - группа из двух элементов: ее = е,еа=а, ае=а. Найти аа.

2. Для любого элемента а: ае=а (представить е=а'a а и воспользоваться ассоциативностью)

3. аа' = е ( расмотрите а''a'аа' )

4 → 2, 3

5 → 5

6. Существует b: ab=b ⇒ a=e

10. (a1 * a2 * ... * an)' = an' * ... * a2' * a1'

11. Построить группу на основе NSV mod m с операцией умножение

13. Пусть для любых a: a*a=e. Доказать G-абелева.

Листок 13. Циклические группы.

Выдан 26.01.85 Закрытие 5.02.85

Феникс - священная птица египтян, прилетающая умирать каждые 500 лет из Аравии в Илинополь... Здесь его сжигают, из пепла он возрождается снова, сначала в форме гусеницы, которая на 3 день начинает превращаться в птицу и на 40 улетает домой в Аравию.
сл. Брокгауза и Ефрона.
Где начало того конца, которым оканчивается начало?
К. Прутков

Опр.1. Число элементов конечной группы называется ее порядком. Обозначение: |G|.

Опр. 2. Пусть а-произвольный элемент группы. min n∈N: an=e ⇒ n -def- порядок элемента a. Запись: |a| = n.

1. Определение элемента бесконечного порядка в кванторах?
б) Бывают ли элементы бесконечного порядка в конечн. группах?

2. Найти порядок указаных элементов известных групп: а)

1234
3142

b) (1 2 3 4)
с) (1 2 3 ... n)
d) Элементов групп симметрии ромба и квадрата.
Укажите порядок групп ↑↑↑

3. а) |a| = n ⇒ ∀k,l 0 < k < l < n ak ≠ аl
b) m ∈ N ⇒ ∃ k ∈ N: 0 ≤ k < n am = аk

4. Пусть f = a*b - разложение подстановки в произведение независимых циклов. Доказать |f| = Н0К( |а|,|b|).

Опр 3. Если каждый элемент группы G есть степень элемента а ⇒ G называется циклической, |G| = n, а элемент a - ее образующим.

5. Доказать, что повороты, переводящие правильный n-угольник в себя, образует циклическую группу порядка n.

6. |a| = n am=e ⇔ m ⋮ n

7. |a| = p р∈Р ∀ m-целого ⇒ am=e .OR. |am| = p

8. Н0Д(m,n) = d; |a| = n ⇒ am = n/d

9. В любой группе |a*b| = |b*a|

10!? Любая циклическая группа - абелева.

11! |G|=р∈Р ⇒ G - циклическая

12. Привести 3 примера циклический групп, (конечным и бесконеч. ) Найти все им образующие.

Найти образующие в группе
а) PSM - по сложению ( см. 12 N10)
б) NSV - по умножению ( см. 12 N11)

Опр.4 G порождается системой образующих a1, a2,... an ⇐df⇒ ∀g из G представим в произведений степеней этик элементов. Например: g=a2*a1*a22*a5-5

14. |Gn| = n! (Gn -группа подстановок длины n)

15. (1 2), (1 3), ..., (1 n) порождает Gn.

16! Найти систему из min образующих в группах симметрии:
а) правильного треугольника
б) квадрата
в) правильного n-угольника
г) правильного тетраэдра
д) куба и октаэдра
е) икосаэдра и додекаэдра
Каковы порядки этих групп?

17. Q порождается a, b причем а4=е; a*a = b*b; a*b = b*a3. Какой порядок она имеет? Составьте ее таблицу умножения. (см лекцию)

Антилисток 13. Циклические группы

Пусть это прочтёт каждый принимающий!

1a. Элемент бесконечного порядка - это, по определению, элемент, любая степень (целая) которого не равна ему самому.
б) Поскольку в группе конечеое число элементов, то колличество различных элементов в ряду a0, a1, a2, ... an... конечно. Поэтому можно выбрать из него два одинаковых an = am n ≠ m. Сократив на меньшую степень, получаем противоречие.

2. а и б) Порядок равен 4. Нужно это проверять непосредственным вычислением.
c) Порядок равен длине цикла. Доказательство по индукции.
d) В группе ромба все элементы: различные симметрии, поэтому они 2 степени. В группе квадрата - тоже самое, но повороты на 90° вправо и влево имеют порядок 4. В группе ромба 4 элемента, а в группе квадрата - 8.

3 a) Сократим на ak - получаем, что n - не наименьший.
б) По теореме о делении с остатком находим k, а потом доказываем.

4. Пусть |f|=c Тогда ck=ak*bk, а т.к. циклы a, b отвечают за разные части одной подстановки и независимы, то ak и bk должны быть независимы и равны e. После этого применяются определение НОК

5. Нужно проверять все аксиомы группы.

6. Доказывать туда и обратно!

7. Пусть порядок |am|=n. Тогда am*n=e. По предыдущей задаче m*n делится на p. А это бывает в одном из двух случаев:
а) m делится на p. Применяем ещё раз 6.
б) n делится на p. Тогда нам надо выбрать наименьшее n: n=p.

8. Простое обобщение 7.

9. Пусть n: (a*b)n = e = a*b*a*b*..*a*b = a*(b*a)n-1*b (b*a)n-1 = (b*a)-1 - домножим на b*a

10. Представить элемент как степени и воспользоваться предыдущим листком.

16! Найти систему из min образующих в группах симметрии:
а) поворот на 120 и симметрия относительности прямой через центр тяжести - 6 элементов.
б) поворот на 90 и симметрия относительно диагонали - 8 элементов
в) поворот на 360/n и симметрия относительно прямой, проходящей через любую вершину и центр. Порядок группы 2*n
г) поворот на 120 относительно некоторой высоты, относительно другой высоты и симметрия относительно некоторой плоскости - 24 элемента.
д) Поворот на 90 относительно прямой соединяющей центры двух противоположных граней, поворот на 120 относительно диагонали и симметрия относительно некоторой плоскости - 48 элементов.

Листок 14. Подгруппы и смежные классы.

Выдан 2.02.85. Закрытие 12.02.85.

Множество- подмножество
полковник- подполковник...

Расмотрим в группе G некоторое подмножество H. Может оказаться, что Н само является группой относительно той же бинарной операции, заданой на G.
Опр. 1. В этом случае говорят, что H - подгруппа G.

1. H - подгруппа G ⇒
а) единичные элементы в H и G совпадают;
б) если a - элемент H, то элементы,обратные к f в G и H - совпадают.

2. Н - подгруппа G ⇔
1) ∀ a, b ∈ H ⇒ a*b ∈ H .AND.
2) e (единичный элемент G): e ∈ H .AND.
3) ∀ a ∈ H ⇒ a' ∈ H
Замечание : 1) .AND. 2) ⇒ 3)

3. Н - подгруппа G ⇔ ∀ a, b ∈ H: a*b' ∈ H

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

5.Найти все подгруппы в группам Z5, Z8, Z15.

6. Доказать,что все подгруппы в Zn имеют вид:
{e, ad, a2*d, ..., a(n/d-1)*d, где n⋮d, a - образующий Zn
b) Докажите ваше обобщение на случай бесконечных циклических групп.

7. Пересечение двух подгрупп группы G - снова подгруппа G.

8. Рассмотрим бесконечное поле в квадратную клеточку. Найти все подгруппы группы симметрий этого поля.

9. Найти все подгруппы в группе перемещений плоскости сохраняющих ориентацию.

10. Подмножество группы симметрии, сохраняющих ориентацию, образуют подгруппу, (опр.2),называемую группой вращений.

11. В группе вращений многограника найти подгруппы порядков:
*Если возможно,то циклические и нециклические
2, 3, 4, 6, 12
2, 3, 4, 6, 8, 12, 24
2, 3, 4, 5, 6, 10, 12, 20, 30, 60
Если какой-нибудь подгруппы нет, то покажите это.

Опр.3. Пусть H - подгруппа G; g∈G. Множество {g*h | h∈H} обозначается gH и называется левым смежным классом по подгруппе H.

12. Найти все левые смежные классы в группе многоугольника (л13N16) по подгруппе
а) вращений
б) отражений относительно одной оси

13! Докажем,что это разбиение на классы. Для этого:
а) ∀ x ∈ G ∃ g*H: x ∈ g*H
b)! g*H ∩ q*H ≠ 0 ⇔ g*H = q*H

14! (Теорема Лагранжа) Если Н - подгруппа G ⇒ |G|⋮|H|

Onp. 4 j = |G|/|H| называтся индексом подгруппы.

15. Доказать, что порядок любого элемента - делитель порядка его группы.

16. Доказать,что всякая группа простого порядка циклическая и любой элемент ≠е - ее образующий.

17. Определить правые смежные классы
б) найти правые смежные классы из N12

18. Найти все левые и правые классы
а) группы симметрии многограника по подгруппе вращений
б) группы вращений многограника по одной из подгрупп пор. 3.

Листок 15. Перестановки и сортировки (дополнительный)

"Нет дела более трудного по замыслу, более сомнительного по успеху, более оасного при осуществлении, чем вводить новые порядки"
Николо Макъявелли "Государь" (1513 г.)

0. Сколько перестановок у множества из n элементов?

Опр.1 Пусть множество P состоит из n элементов: p1, p2,..., pn. Множеством Ключей К над множеством Р называется множество К, если:
а) взаимно-однозначное отображение К в Р и
б) на множестве К введено отношение порядка "меньше", т.е.

  1. любые два элемента или равны между собой, или один меньше другого
  2. если один элемент меньше другого и больше третьего, то другой больше третьего

(В математике множестао К называется линейно упорядоченным)

Опр.2 Сортировка - подстановка элементов нашего множества в порядке не убывания ключей.

Опр.2 Сортировка называется устойчивой, если элементы с равными ключами остаются на месте
Примечание 1. Далее, если не оговоренно, то сортировка устойчивая.

1. Доказать единственность подстановки, рашающую задачу сортировки

2. Пусть К и G - два различных множества ключей над Р. Введём "словарный порядок" на множестве пар (ki,gj):
(ki,gj) меньше (km,gl) если ki меньше km и если ki = km, то gj меньше gl
ABC сначало отсотрировал по К ключам, а затем в группах с одинаковыми К-ключами по G - ключам, а Олег отсортировал, как указано выше.
а) получилось ли у них одно и тоже?
б) что будет в случае неустойчивой сортировки

3. Пусть на множестве К определено отношение порядка 1, а свойство 2 не выполняется
а) доказать, что и в этом случае возможна устойчивая сортировка
б) найти сортирующий алгоритм
в) единственен ли получаемый результат?

Инверсии

Опр. 4 Пусть в перестановке a1,a2,..., an: i<j, а ai>aj. Пара (ai,aj)называется инверсией

Опр. 5. Подпишем под перестановкой a1,a2,..., an числа, равные количестыу инверсий, которое образует элемент над ним в перестановке А. Получившаяся таблица называется таблицей инверсий.

4. Построить таблицу и найти все инверсии в перестановке (5, 9, 1, 8, 2, 6, 4, 7, 3)

5. Построить алгоритм построения таблицы инверсий по перестановке
б) наоборот

6. Насколько изменится число инверсий во всей перестановке, если поменять местами \ два соседних члена?
б) что вы можете сказать об изменении числа инверсий при других преобразованиях перестановки (т.е. при действии различных подстановок)

7. Рассмотрим две подстановки: в первой верхняя строчка 1, 2,.. n, а нижняя - произвольная перестановка, а другая обратна к первой, причем верхняя строчка тоже 1, 2,.. n. Доказать, что число инверсий в нижних строчках этих подстановок совпвдают.

8. Сколько существует перестановок n - порядока, имеющих k инверсий.

Перестановки мультимножества.

Опр.6. Мультимножество - это множество, для каждого элемента которого дополнительно указано количество копий этого элемента в мультимножестве.

9. Пусть М - мультимножество, содержащее n различных элементов ak, причем для всех k число копий ak равно mk. Сколько существует перестановок такого мультимножества? (Перестановки различны, если их можно отличить)

Опр. 7. На множестве перестановок одного и того же множества введём операцию по следующему правилу (соединённое произведение)

  1. Для двух перестановок взять соответсветсвующие им подстановки в смысле задачи № 7
  2. Перемножить эти подстановки
  3. Устойчиво отсортировать нижнюю строчку - это и есть произведение

10. Доказать, что перестановки множества образуют группу по этой операции.

11. Когда выполняется коммутативность?

12. Образуют ли перестановки мультимножества с этой операцией группу? Абелеву группу?

Опр. 8. Циклы в подстановках мультимножества определяются аналогично обычным циклам

13. Всегда ли (x1,x2,..., xn) = (x2,x3,..., xn,x1)?

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

Отрезки

Опр. 9. Элементы ak,...,an образуют отрезок ⇐def⇒ ak-1>ak≤ak+1 ≤...≤an>an+1

15. Найти все отрезки в перестановке (5 7 1 6 8 9 4 2 3)

16. Скольео перестановок множества (1, 2,..., n) содержит ровно k отрезков?

17. Говорят, что подстановка требует k чтений, если её надо просмотреть k раз слева направо, с тем что бы выписать все её элементы в неубывающем порядке
а) найти связь между отрезками и чтениями
б) докажите ваше предположение

Табло Янга и инволюции

Опр. 11 Запишем на нескольких первых строчках таблицы некоторое коллличество по-парно различных натуральных чисел. Если при этом:
1) Колличество элементов в строчке не меньше, чем во всех строчках её ниже
2) Каждый элемент меньше своего соседа справа и снизу и справа (если они есть)
- то таблица называется табло Янга (просто табло)

20. Найти все табло из элементов (1, 2, 3, 4)

21. Построить алгоритм:
а) определения места в табло нового элемента (введение)
б) Изменения табло после исключения заданного элемента
в) Посторения табло из заданных элементов.

22. Установить соответствие между упорядоченными парами табло одинаковой формы и подстановками.

23. Доказать, что если прямой подстановке соответсвует табло Р,0, то обратной 0,Р???????????

24. Найти связь между числом различных табло и инволюций данного множества.

Лиcток 16 - Изоморфизм и автоморфизм.

Выдан 12.02.85 Закрытие 22.02.85

Опр. 1. Пусть имеются две группы G и Q. Они называются изоморфными, если существует взаимно-однозначное отображение f:G→Q, при котором для ∀ a,b из G:f(a*b)=f(a)*f(b). Такое отображение называется изоморфизмом.

Примеры изоморфизмов

1.Какие из следующих групп изоморфны:
1) вращений квадрата
2) симметрии ромба
3) симметрии прямоугольника
4) PSV mod 4 по сложению
5) группы вращений многограников
6) подгруппы из задачи 8,9 листка 14.

2. Привести примеры двух групп одного порядка и не изоморфных.

3** Группа R по сложению изоморфна R>0 no умножению

Общие свойства изоморфизмов.

4. Свойства как отображений
a) f:G→Q - изоморфизм ⇒ f':Q→G - также изоморфизм
6) f:G→Q .AND. - ф:Q→H - изоморфизмы ⇒ fф:G→H - также изоморфизм.

5. Отображения единичного и обратного элементов.
a) е - единица G, э - единица Q; f:G→Q - изоморфизм ⇒ f(e)=э
б) f:G→Q - изоморфизм; ⇒ ∀g∈G: f(g') = (f(g))'

6. Порядки элементов в изоморфных группах:
f:G→Q - изоморфизм; ⇒ |f(g)| = |g|, где g∈G

7. Циклические группы изоморфны соответственно:
a) Zk - конечного порядка изоморфна PSV mod k
б) Z - бесконечного порядка изоморфна группе целых по +.

8!(Теорема Кэли)!! Любая группа порядка n изоморфна некоторой подгруппе Sn, (Sn - группа подстановок длины n).

9. Найти все (с точностью до изоморфизма) группы порядка 2, 3, 4
b) 5, 6, 7
с)*** n > 7

10. Пусть a - произвольный элемент группы G. Элементом множества Q, соответствующим a, является отображение группы G в себя фа ( фа = а*х для ∀ x из G ). Доказать, что Q с операцией композиция - группа, изоморфная G.

Прямые произведения

Опр 2. Прямым произведение двух групп G⊗H называется множество G⊗H со следующей бинарной операцией: (g1,h1)*(g2,h2) = (g1g2,h1h2) произведение g1g2 берется в группе G, a h1h2 - H.

11. Доказать,что G⊗H - группа.

12. Группа симметрии ромба изоморфна Z2⊗Z2.

13. G⊗H изоморфна H⊗G.

14. G, Н - абелевы ⇒ G⊗H - тоже абелева.

15. G1- подгруппа G и H1 - подгруппа Н ⇒ G1⊗H1 - подгруппа G⊗H.

16. K - подгруппа G⊗H ⇒ ∃G1 - подгуппа G .AND. H1 - подгруппа Н: K=G1⊗H1.

17. Zm⊗Zn - изоморфна Zm*n ⇔ Н0Д(m, n) = 1.

Автоморфизм.

Опр.З. Пусть g - фиксированный элемент группы G. Отображение f:G→G(в себя), определяемое правилом: ∀ х∈G: f(x) = g*x*g' - называется внутреним автоморфизмом группы, порожденным g (автоморфизмом)

18. f - автоморфизм ⇒ f - изоморфизм группы на себя.

19. Во что переходят при всевозможных автоморфизмах группа симметрии вашего многоугольника
а) группа отображений относительно одной из осей симметрии
б) группа вращений
**. Какие 2 элемента группы симметрии многограника можно перевести друг в друга автоморфизмами. Тот же вопрос для группы вращений.

Листок 17. Нормальные делители и факторгруппы.

Выдан 19.02.85 Закрытие 2.03.85

"- Ты что, ненормальный ?!!
- Нет, я нормальный, это ты ненормальный!!!"
(из разговора)

СОПРЯЖЕННЫЕ

Опр 1. x и у сопряженные (запись x≅y) ⇐def⇒ ∃ a∈G: y = a*x*a' т.е. существует внутрений автоморфизм f:a(x)=y

1. Доказать ,что ≅ - отношение эквивалентности, т.е.
а) x≅x
b) x≅у ⇒ y≅x
с) x≅у .AND. y≅z ⇒ x≅z

2. G разбивается на кпассы сопряженный элементов (КСЭ) (вспомните, что такое разбиение на классы)

3. Найти эти классы для
а) группы вращений n-угольника
б) группы диэдра квадрата
в) Zn
г) группы подстановок длины 4
д) группы икосаэдра

4. a∈G и Н -произвольная подгруппа G. Верно ли, что а*Н*а' - подгруппа G?

НОРМАЛЬНЫЕ ПОДГРУППЫ

Опр. 2. H - нормальная подгруппа G ⇐def⇒ она переходит в себя при всех внутренних автоморфизмах G (обоозначение Н⊳G)

5. Придумать ненормальную подгруппу. Бывают ли они в циклических группах?

6. В коммутативной группе всякая подгруппа нормальна

7. Н⊳G ⇔ Н - объединение нескольких КСЭ группы G ⇔ левые смежные классы совпадают с правыми.

8. |G|:|H| = 2 ⇒ Н⊳G

9. Пересечение любого числа нормальных подгрупп группы G являются нормальной подгруппой G.

10. a) H1⊳G1 .AND. H2⊳G2 ⇒ H1⊗H2 ⊳ G1⊗G2
b) индукционное обобщение на произведение n групп

Факторгруппа

11. Расмотрим смежные классы по Н в G (x∈qH .AND. y∈gH ) ⇒ ( x*y ∈ (qg)H )

12. Доказать, что мн-во смежных классов по нормальной подгруппе с бинарной операцией xH*yH = (ху)Н образуют группу.

Опр.З. Эта группа называется факторгруппой G по H или G/H

13. Будет ли факторгруппа группы D4 по подгруппе центральных симметрий изоморфна группе вращений квадрата или группе симметрии ромба?

14. Найти все факторгруппы в
a) D3
b) D4
c) Z2⊗Z2
d)* Zn - описать см Л13,Л14
е) вращения тетрадра

ГОМОМОРФИЗМ

Опр. 4. Гомоморфизмом М в N называется отображение f:M→N: ∀ a, b ∈ M f(a)*f(b) = f(ab). Здесь M и N - множества с бинарной операцией, а произведения берутся в соответствующих мн-вах

0пр. 5. Эндоморфизм - гомоморфизм группы в себя

Опр. 6. Гомоморфизм называетсся гомоморфизмом НА ⇐def⇒ ∀(a*x)∈ N ∃ а∈М: f(a) = x

16. G1 - группа и f - eё гомоморфизм ⇒ f(G1) = G2 - группа.

17. Рассмотрим все элементы G1, которые при гомоморфизме f переходят в элемент x и обозначим их Ax. э - единица G2. Тогда
a) Aэ ⊳ G1 (Aэ - ядро гомоморфизма )
b) Ax = х*Aэ

18 Н⊳G1, построить гомоморфизм, чтобы f(H)=э, f(gH)=х; т.е. решить задачу, обратную 17)

Зададим отображение f(G1)=G2 где G2 состоит из смежных классов по H (G/H).

Опр.7. G/H - факторгруппа

19. f(a) = aH ⇒ f - гомоморфизм т.е. f(a)*f(b)=f(ab).
Верно ли это, если H - ненормальная?

20. Zn a - образующий |H| =n/m ⇒ Zn/H = Zm

21. Верно ли, что для ∀ H⊳Z по +: H ={n*q | n∈Z} , где q∈N. Найти факторгруппы по этим группам.

Листок 18. Гомоморфизм.

Выдан 21.03.85. Закрытие 13.04-85.

"...И ядрам пролетать мешала гора кровавый тел..."

Опр. 1. Гомоморфизмом группы G в группу F ⇐def⇒ отображение f:G→F такое, что f(ab) = f(a)*f(b) для люб. а,b∈G. При гомоморфизме, в отличии от изоморфизма, не требуется взаимооднозначности.
Множество Ker f = {g∈G | f(g)=э} -def- ядро гомоморфизма.

1. Проверить св-ва гомоморфизмов, аналогичные св-вам изоморфизмов из л 16 N4,5.

2. Н⊳G. f сопостовляет каждому элементу g из G смежный класс по подгруппе Н, который содержит g.
Доказать, что f:G→G/H -гомоморфизм G НА G/H.

Опр. 2. Этот гомоморфизм называется естественным.

ТЕОРЕМА 0 ГОМОМОРФИЗМЕ.

3. f: G→F - гомоморфизм ⇒
a) Ker f - подгруппа G
b) Ker f ⊳ G
c) r∈ g*Ker f .AND. s ∈ g*Ker f ⇔ f(r) =f(s)
Формулировка теоремы: "Отображение ф:G/Ker f → F, сопостовляюшее каждому смежному классу g*Ker f → f(g), является изоморфизмом. Для док-ва:
d) ф - отображение на
e) ф - взаимооднозначное
f) ф - изоморфизм
h)?? Расшифруйте: "Гомоморфизм изоморфен некоторому естественному гомоморфизму".

ПРИМЕРЫ НА ТЕОРЕМУ О ГОМОМОРФИЗМЕ.

4. В группе симметрии тетраэдра подмножество H = {(1), (12)(34), (13)(24), (14)(23)} образует нормальную подгруппу.

5. В группе вращений куба подмножество Н = {(1), (13)(24)(1'3')(2'4'), (12')(21')(34')(43'), (14')(41')(23')(32') } образует нормальную подгруппу.

6а) Dn⊳R. ( R - повороты плоскости отн. центра многоугольника)
b) R/Dn изоморфна R.

В дальнейшем "=" для групп обозначать изоморфизм.

7. H1⊳G1 .AND. H2⊳G2 ⇒ (G1⊗G2)/(H1⊗H2) = (G1/H1)⊗(G2/H2)
(Если вам доставляет эстетическое удивольствие формулировка задачи, то из вас может получиться математик)

8. Три качественых вопроса.
∀ G1, G2, H1, H2 H1⊳G1 .AND. H2⊳G2:
a) (G1≠G2) .AND. (H1=H2).AND. G1/H1=G2/H2
b) (G1=G2) .AND. (H1≠H2).AND. G1/H1=G2/H2
a) (G1=G2) .AND. (H1=H2).AND. G1/H1≠G2/H2

Опр. 3. Пусть f:G→F - гомоморфизм. Тогда
M⊂G ⇒ f(M) -def- мн-во образов при гомоморфизме всех элементов M
P⊂F ⇒ f'(P) -def- мн-во прообразов при гомоморфизме всех элементов P

9! f(f'(M))≠М

10. Н -подгруппа G .AND. f:G→F - гомоморфизм ⇒ f(H) -подгруппа F.

11. P -подгруппа F .AND. f:G→F - гомоморфизм ⇒ f'(P) -подгруппа G.

АД.МИНИСТРация приветствует решающих 12-28 задачи

ЦЕНТР И ЦЕНТРАЛИЗАТОР

Опр. 4. Пусть g∈G. Централизатор g Ц(g)=def= {x∈G |xgx' = g}.

12. а) Ц(g) - подгруппа G
b) |G|/|Ц(g)| = числу элементов в подмножестве G, все x из которого сопряжены g (x≅g)

13. Найти Ц(g) в группе подстановок длины 6, если
а) g=(1 2 3 4)
b) g=(1 2 3)(4 5 6)
Выразить порядок Ц(g) через длины циклов в разложении g.

Опр. 5. Центр группы Ц(G) - мн-во элементов G, коммутирующих со всеми элементами.

14. а) Выберем из G все элементы имеющие сопряженые ⇒ Ц(G) - пересечение централизаторов этик элементов.
b) Ц(G)⊳G

15. Может ли G/Ц(G) быть а) абелевой b) циклической?

КОММУТАНТ И КОММУТАТОР

0пр.6. Элемент a*b*a'*b' называется коммутатором элементов а и b. Подгруппа , порожденная всеми коммутаторами элементов из G называется коммутантом G'.

16. а) G'⊳G
b) G/G' - абелева.

17. Н⊳G .AND. G/Н -абелева ⇔ G' ⊂ H

18. Указать, каким известным группам изоморфны центр и коммутант в группам:
a) Zn, Dn
b) вращений куба, тетраэдра.

РАЗРЕШИМЫЕ ГРУППЫ

0пр. 7. G1= G'; Gn+1=Gn'. Gn - называется n-коммутантом. Если некоторый n-коммутант равен {e}, то группа называется разрешимой.

19. G - неабелева и не имеет нормальных подгрупп, кроме {e} и G ⇒ G - неразрешима.

20. Группа вращений додекаэдра неразрешима.

21. H⊳G .AND. H и G/H - разрешимы ⇒ G - разрешима.

22. |G|=pk ⇒ а) Ц(G)≠{e}
b) G - разрешима

23. |G|=р2 ⇒ G - абелева.

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

24* Сколько существует неабелевых групп порядка р3?

25* |G|=p*q (p,q - простые) ⇒ G содержит подгруппу порядка р (использовать 12)

26*!! G - разрешима ⇔ ∃ G1,G2,...,Gn:
         1) Gn⊳... ⊳G2⊳G1⊳G0=G
.AND. 2) ∀i Gi/Gi-1 - абелева
.AND. 3) Gn - абелева

27* Условие 2) из задачи 26 можно записать иначе:
"Каждая Gi содержит абелеву Ni такую, что Ni⊳Gi .AND. Gi/Ni изоморфна Gi+1.

28**. Задача - исследование.
Группа Hn подстановок с n > 4 - неразрешима.

Листок 21. Счетные множества.

Выдан 3.09.85 Закрытие 15.09.85

EST MODVS IN REVS
(есть мера в вещах. - лат.)

Опр. 1. Если существует взаимно-однозначное отображение множества A на множество B, то A и B равномощны. |A|=|B| (A~B)

Опр. 2. Пусть Jn - множество первых n-натуральным чисел:
Jn = {1,2,...,n}; N- множество всех натуральных чисел.
(а) A - конечно ⇐def⇒ ( ∃n: A~Jn ) OR (A = ∅)
(b) A - бесконечно ⇐def⇒ NOT (A- конечно)
(c) A - счетно ⇐def⇒ A~N
(d) A - несчетно ⇐def⇒ NOT ( A - конечно OR A - счетно)
(e) A - не более чем счетно ⇐def⇒ ( A - конечно OR A - счетно)

Напоминание

Установить взаимно-однозначное отображение A→В в случае бесконечных числовым множеств означает указать формулу фукции (или объединение формул), заданную на A и имеющую значение в B, а потом доказать взаимооднозначность, т. е. указать формулу обратной функкции, и при необходимости доказать, что это тоже функция. Отсутствие взаимной однозначности тоже надо доказывать.

1. а) Записать без отрицания в кванторам (b),(d) из опр 2
b) Определить отношение "менее мощно" ( |A|<|B|).

2. Когда два конечных множества равномощны?

3. Равномощны ли:
(а) {1,2,3,...} и {2,3,4,...}
(b) { ученики бывшего 8в } и { ученики 9в }
(c) Множества добрых и злых волшебников
(d) Множество сказок и сказочников
(е)* {умные} и -{дураки} (см. Окуджаву)

4. Доказать равномощность (разрешается графическое решение)
а) [0 ; 1 ] и [ 0 ; 2 ]
b)* [0 ; 1 ] и ] 0 ; 1 [
c) Прямой и полуокружности без концов
d) ] -1 ; 1 [ и числовой прямой
e) Точек графиков у=2*х2 и у=х-5
f)* Множество точек круга без центра и разности всей плоскости и круга
g)**Множество ваших точек и точек окружающего пространства.

5. a) Z0~N b) {2,4,6,8,...}~N с) Z~N
d) A⊂N ⇒ A не более чем счетно (Указание: в A существует наименьшее число)
e) P~N ( P - множество простых чисел)
f) A - бесконечно; В-не более чем счетно ⇒ (A∪B)~A
h) A - бесконечно ⇔ ∃B⊂A: B~A

6. а) Объединение или разность счетного и конечного - счетно
b) Объединение двум счетных множеств счетно
c) Объединение конечного числа счетных множеств счетно
d) Объединение счетного числа конечных множеств не более чем счетно (верно ли, что оно всегда счетно ?)

7. а)!! Обединение счетного числа счетных множеств - счетно
b) Множество N⊗N - счетно
c) Множество N⊗N⊗...⊗N = Nm - счетно (индукция)
d) Q~N ( Q - множество рациональных чиисел)
e) Множество точек n-мерного пространства с целыми (рациональными координатами) счетно

8 а) Множество непересекающихся интервалов внутри отрезка [0 ; 10] не более, чем счетно
b) Множество непересекающихся кубов не более, чем счетно
c) Множество ваших потомков никогда не будет более, чем счетно

9*. Множество алгебраических чисел счетно

10! а)! Мн-во конечных последовательностей но 0 и 1 счетно
b)!!*Мн-во бесконечных последовательностей но 0 и 1 несчетно

11*? Множество биологических клеток живших, живущих и будущих жить во Вселеной не более , чем счетно.

Указание: Выпишите элементы этих множеств в бесконечную

Листок 22-23. ЧИСЛА (экспериментальный)

Выдан 21.09.85 Закрытие 5.10.85

"Ба, знакомые все лица!..."

В этом листке нельзя использовать все то, что вы знали о числах раньше.

НАТУРАЛЬНЫЕ ЧИСЛА (множество N)

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ....

a, b, с, d - произвольные натуральные числа

I

Аксиомы Пеано (основные свойства натуральный чисел)

(A) 1 - натуральное число
(B) Для любого a ∃ единственное следующее за ним a+
(C) a+ ≠ 1
(D) a+=b+ ⇒ a=b
(E) "Принцип индукции" Любое подмножество натуральным чисел, которое содержит 1 и вместе с любым a еще и a+, содержит все натуральные числа.

II

СЛОЖЕНИЕ: Зададим бинарную операцию сложения свойствами (1), (2)

(1) а + 1 = a+
(2) а + b+ = (а + b)+

Тогда доказываются:
(3) (a+b)+c=a+(b+c)
(4) a+b=b+a

III

УМНОЖЕНИЕ: Зададим бинарную операцию умножения свойствами (6),(7)

(6) а*1=а
(7) а * b+ = a*b + a

Тогда доказываются:
(8) (a*b)*c=a*(b*c)
(9) a*b = b*a
(10) a*(b+c)=a*b+a*c
(11) a*b=a*c ⇒ b=c

IV

БОЛЬШЕ-МЕНЬШЕ: Зададим отношения порядка:

а > b ⇐def⇒ b < a ⇐def⇒ a=b+c Тогда доказываются:

(12) Всегда справедливо только одно из высказываний a=b ; a<b ; a>b
(13) a<b AND b<c ⇒ a<c
(14) a<b ⇒ a+c< b+c
(15) a<b ⇒ a*c<b*c

ТЕОРЕМА (16) Каждое непустое множество натуральный чисел содержит наименьшее число, т.е. число, которое меньше всек остальных.

VII

Задача 1. Докажите указанные вам св-ва натуральных чисел,опираясь на все предыдущие свойства.

Упражнение 2. а) 2*2=4 b) 2<5 с) 5≠7

ЦЕЛЫЕ ЧИСЛА

I

Задача 2. Пусть на множестве N⊗N задана эквивалентность: (a,b)=(c,d) ⇐def⇒ a+d=b+c. Доказать, что этим задается разбиение на классы эквивалентности.

Определение. Множество этих классов называются целыми числами (Z), и мы будем их обозначать m, n, k

II

СЛОЖЕНИЕ: Зададим операцию сложения: (а,b)+(с,d)=def=(а+с,b+d)

Задача 3. Целые числа образуют абелеву группу по сложению:
(1) бинарность
(2) существует нулевой элемент (а,а)
(3)(m+n)+k=m+(n+k)
(4) m+n = n+m
(5) ∀m ∃! ед. (-m): m + (-m) = нулевому элемент.

III

УМНОЖЕНИЕ. Зададим операцию умножения (а,b)*(с,d)=def=(ac+bd,ad+bc)

Задача 4. Целые числа образуют коммутативное кольцо с единицей, т.е. вместе со свойствами (1)-(5) справедливы и
(6) m*n принадлежит Z
(7) существует единичный элемент
(8) (m*n)*k = m*(n*k)
(9) m*n = n*m
(10)m*(n+k) = m*n + m*k
(11)m*n=m*k ⇒ n=k

IV

БОЛЬШЕ-МЕНЬШЕ. Зададим отношения порядка: (a,b)<(c,d) ⇐def⇒ (с,d)>(a,b) ⇐def⇒ a+d < b+с

Задача 5. Для целых справедливы св-ва натуральный чисел (12)-(14). Обобщите и докажите (15) и на случай "с" < (а,а)

VI

Определение. Число (a,a) назовем нулем 0. Числа, большие нуля - положительные целые числа, а меньше - отрицательные.

Задача 5. Положительные целые числа изоморфны натуральным и по сложению и по умножению.

В дальнейшем положительные числа (а,b) будем обозначать а-b, а отрицательные -(b-а)

VII

Упражнение 7. а) 5-7=? b) m*m>0 с) (m-n)*(m+n)=?

РАЦИОНАЛЬНЫЕ ЧИСЛА

I

Задача 8. Пусть на множестве Z⊗N задана эквивалентность: (m,a)=(n,b) ⇐def⇒ m*b=n*a. Тогда:
a) это разбиение на классы эквивалентности
b) действует закон сокращениз дробей: (a*m, a*b)=(m, b)

Определение. Множество этик классов называется множеством рациональный чисел Q. Рациональные числа обозн. р, q, r.

II

СЛОЖЕНИЕ. Зададим операцию сложения: (m,а)+(n,b)=def=(mb+na,ab)

Задача 9. Q образует абелеву группу по сложению.

III

УМНОЖЕНИЕ. Зададим операцию умножения: (m,а)*(n,b)=def=(m*n, a*b)

Задача 10. Q образует поле, кроме задачи 9:
a) Q\(0,а) образует абелеву группу по умножению
b) p*(q+r) = p*q + p*r - дистрибутивность

IV

БОЛЬШЕ-МЕНЬШЕ. Зададим отношение порядка: (n,b)>(m,a) ⇐def⇒ (m,a)<(n,b) ⇐def⇒ m*b < n*a

Задача 11. Q - упорядоченное поле, т.е. справедлива задача 5 для рациональным чисел.

VI

Задача 12. Подмножество {(m,1)} изоморфно множеству Z и по сложению и по умножению.

В дальнейшем рациональное число (m,a) будем обозначать m/a, а число m/1=m

VII

Задача 13. p<q ⇒ ∃r: p<r AND r<q.

Упражнение 14. а) 22/7 < 28/8 b) 1/2 >91/179

СЕЧЕНИЯ ДЕДЕКИНДА

х,у,z,u - множества рациональных чисел, "∈"=принадлежит ("элемент" ∈ "множеству")

Определение: х - сечение ⇐def⇒ 1)∃р∈х AND сущ. r∉x
AND 2) (р∈х AND q<p )⇒ q∈х
AND 3) в х нет наибольшего элемента

Задача 15. (р∈х AND q∉x) ⇒ p<q

Опр. Рац. числа ∈х называют нижними числами сечения;
Рац. числа ∉х называют верхними числами сечения;

Задача 16. u={p| p<r (r фиксированно)} ⇒ u - сечение AND r - наименьшее из верхних чисел.

Определение. Такие сечения называются рациональными.Запись: u=r*

IV

БОЛЬШЕ-МЕНЬШЕ.

Зададим отношение порядка:
(a) (х<у) ⇐def⇒ (y>x) ⇐def⇒ (∃p: (р∈у AND p∉x)
(b) (x≤y) ⇐def⇒ (y≥x) ⇐def⇒ x<y OR x=y
(c) х - положительно ⇐def⇒ x >0*

Задача 17. Докажите для сечений а)св. 12 b) св. (13)

II

СЛОЖЕНИЕ. Зададим операцию сложения: x+y = {p| p=r+s; p∈х, s∈y}

Задача 18. Сечения образуют абелеву группу по сложению:
а)бинарность b)ассоц. с) 0* d)обратный е)коммутативна f) кроме того, выполняется (14) для сечений

III

УМНОЖЕНИЕ

Определение. Модуль |x| ⇐def⇒ (х, если x≥0*; -x, если х<0*

Зададим операцию умножения следующими соотношениями:
x*y = {p| р=r*s, r∈х, s∈y}, если х≥0*, у≥0*;
x*y = -(x*|y|), если х≥0*, у<0*;
x*y = -(|x|*y), если x<0*, у≥0*;
x*y = |x|*|y|, если х<0*, у<0*.

Задача 19. Сечения без 0* образуют абелеву группу по умнож.:
а)бинар. b) ассоц. с) 1* d) х' е) коммутативность
f)кроме того, выполняется для сечений (15) и его обобщение.

Определение. x-y =def= x + (-y); x/y =def= x*y'

VI

Замечание. Из задач 16,17,18 следует, что сечения образуют упорядоченное поле. В дальнейшем сечения будем называть вещественными или действительнными числами, а множество действительных чисел обозначать R.

Задача 20. х < у ⇒ ∃r: x<r<y

V

ПОЛНОТА вещественых чисел

Задача 21. Пусть A и B - разбиение R на два непустых класса AND ( x∈A AND y∈B ⇒ x<y). Тогда ∃ единст. z: ∀x∈A: x≤z AND ∀у∈В z≤у )

Упражнение 22. ∃! единственное x>0: x2=2
b) этот x∉Q

Определение. R\Q называется множеством иррациональных чисел.

VI

Определение. Множество M ограничено сверху ⇐def⇒ ∃x: ∀y∈M: y<x. x называется верхней гранью
b) Множество M ограничено ⇐def⇒ ∃x: ∀y∈M: |y|<x

Определение. x - точная верхняя грань M ⇐def⇒ x - верхняя грань M AND x - наименьшая из верхних граней.
Она обозначается supM

Упражнение 23. Запишите в кванторах определения supM и infM (точной нижней грани)

Задача 24! Пусть E - непустое множество вещественных чисел, ограниченное сверху ⇒ ∃ supE

VII

Упражнение 25. Найти supM и infM (если они существуют)
a) A = {xa | xa = 1 + 1/6a}
b) A = {z | z = x+y; -1≤x<1; -3≤y≤2}
c) A = {z | z = x*y; -1<x<10; -1≤y<2}
d) A = {xa | xa = (2a+1 + 3a)/3a}
e) A = {xa | xa = 1 + 1/2 + 1/3 + ...+ 1/a}

ЛИСТОК 24. ЧИСЛА.

ВЫДАН 23.10.85

В ЛИСТКЕ ПО УМОЛЧАНИЮ I,J∈N, N∈Z, X,Y,Z∈R.

ЗАДАЧА 1. ПРИНЦИП АРХИМЕДА,
A) ∀Х>0 И ∀Y>0 ∃N: (N-l)*X≤Y<N*X
B) ∀Х>0 И ∀Y>0 ∃N: XN-1≤X<XN
C) INF{Y/I|Y>0;I∈N}=0

ОПРЕДЕЛЕНИЕ. А) НАЗОВЕМ Х∈R - ТОЧКОЙ, R - ЧИСЛОВОЙ ПРЯМОЙ (ИЛИ ПРОСТО ПРЯМОЙ). (НА ЭТОМ ПУТИ МОЖНО ПОСЛЕДОВАТЕЛЬНО СФОРМУЛИРОВАТЬ И ДОКАЗАТЬ АКСИОМЫ И ТЕОРЕМЫ МОНОМЕТРИИ (ГЕОМЕТРИИ ПРЯМОЙ),ЗАТЕМ ПЛАНИМЕТРИИ И СТЕРЕОМЕТРИИ).
B) ОТРЕЗОК [X,Y] ⇐def⇒ {Z| X≤Z≤Y}
C) ИНТЕРВАЛ (X,Y) ⇐def⇒ {Z| X<Z<Y} ПРИ ЭТОМ ЧИСЛО (Y-X) НАЗЫВАЕТСЯ ДЛИНОЙ ОТРЕЗКА (ИНТЕРВАЛА).

ОПРЕДЕЛЕНИЕ. МНОЖЕСТВО ОТРЕЗКОВ (ИНТЕРВАЛОВ) [XI,YI] НАЗЫВАЕТСЯ СИСТЕМОЙ ВЛОЖЕННЫХ ОТРЕЗКОВ (ИНТЕРВАЛОВ) ⇐def⇒ I∈N: [XI,YI]⊂[XI-1,YI-1]

ЗАДАЧА 2. А) СИСТЕМА ВЛОЖЕННЫХ ОТРЕЗКОВ ИМЕЕТ ОБЩИЙ ЭЛЕМЕНТ.
В) СИСТЕМА ВЛ0ЖЕННЫХ ИНТЕРВАЛОВ МОЖЕТ НЕ ИМЕТЬ ОБЩЕГО ЭЛЕМЕНТА.

ЗАДАЧА 3. А) ПЕРЕСЕЧЕНИЕ СИСТЕМЫ ВЛОЖЕННЫХ ОТРЕЗКОВ СОСТОИТ ИЗ ОДНОЙ ЕДИНСТВЕННОЙ ТОЧКИ ⇔ ДЛЯ ∀Е>0 ∃I: YI-XI<E.

ОПРЕДЕЛЕНИЕ. А) КОНЕЧНОЙ ПОСЛЕДОВАТЕЛЬНОСТЬЮ НАЗЫВАЕТСЯ ФУНКЦИЯ F: J→R
B) ПОСЛЕДОВАТЕЛЬНОСТЬЮ НАЗЫВАЕТСЯ ФУНКЦИЯ F: N→R.
C) "ПОЧТИ BCE"⇐def⇒"BCE, КРОМЕ КОНЕЧНОГО ПОДМНОЖЕСТВА"
D) "СТАЦИОНАРНАЯ ПОСЛЕДО8АТЕЛЬНОСТЬ"⇐def⇒"ПОСЛЕДОВАТЕЛЬНОСТЬ, ПОЧТИ ВСЕ ЧЛЕНЫ КОТОРОЙ РАВНЫ ОДНОМУ И ТОМУ ЖЕ ЧИСЛУ".

ПОЗИЦИОННАЯ ЗАПИСЬ.

ОПРЕДЕЛЕНИЕ. 2=1+1; 3=2+1; 4=3+1; 5=4+1; 6=5+1; 7=6+1; 8=7+1; 9=8+1; 10=9+1.
T = {0,1,2,3,4,5,6,7,8,9} - МНОЖЕСТВО ЦИФР. ЗАДАДИМ СООТВЕТСТВИЕ ФI: Тi → N: ФI((Аii-1,...,А1)) = АN*10i-1 + АN-1*10i-2 + ... + А1
В ДАЛЬНЕЙШЕМ (Аii-1,...,А1) БУДЕМ ЗАПИСЫВАТЬ КАК АiАi-1Аi-2...А1 И НАЗЫВАТЬ ДЕСЯТИЧНОЙ ЗАПИСЬЮ НАТУРАЛЬНОГО ЧИСЛА.

ЗАДАЧА 4, А) ПУСТЬ Ф - ОБЪЕДИНЕНИЕ ВСЕХ ФI И Ф0 ⇒ ф - ОТОБРАЖЕНИЕ ...?
B) ЗАДАЙТЕ ЕСТЕСТВЕННЫЕ ОПЕРАЦИИ СЛОЖЕНИЯ И УМНОЖЕНИЯ ДЕС. ЗАПИСЕЙ НАТУРАЛЬНЫХ ЧИСЕЛ И ДОКАЖИТЕ, ЧТО Ф СОХРАНЯЕТ СЛОЖЕНИЕ И УМНОЖЕНИЕ.
C) ЕСЛИ ДОПОЛНИТЕЛЬНО ПОТРЕБОВАТЬ, ЧТО ПЕРВЫЙ ЧЛЕН ПОСЛЕДОВАТЕЛЬНОСТИ АI НЕ ЦИФРА 0, ТО Ф - ВЗАИМНО-ОДНОЗНАЧНО.

УПРАЖНЕНИЕ 5. СФОРМУЛИРУЙТЕ ОПРЕДЕЛЕНИЕ ДЕСЯТИЧНОЙ ЗАПИСИ ЦЕЛОГО ЧИСЛА.

ОПРЕДЕЛЕНИЕ. ЗАДАДИМ СООТВЕТСТВИЕ МНОЖЕСТВА W: Z⊗Z⊗(N\{9,99,999,...}∪{0})→Q W(k,n,a) = 10k*(n + a/10L(a)) где L(a) - НАИМЕНЬШАЯ СТЕПЕНЬ 10, ПРЕВОСХОДЯЩАЯ a (L(0)=0)

УПРАЖНЕНИЕ 6. СФОРМУЛИРУЙТЕ СПОСОБ ПОЛУЧЕНИ ДЕС. ЗАПИСИ РАЦИОНАЛЬНОГО ЧИСЛА ИЗ (k,n,a)

ЗАДАЧА 6. A) W - ГОМОМОРФИЗМ.
в) ЗАДАЙТЕ ЕСТЕСТВЕННЫЕ ОПЕРАЦИИ СЛОЖЕНИЯ И УМНОЖЕНИЯ ДЕС. ЗАПИСИ РАЦИОНАЛЬНЫХ ЧИСЕЛ, И ДОКАЖИТЕ, ЧТО W - ГОМОМОРФИЗМ И ПО СЛОЖЕНИЮ И ПО УМНОЖЕНИЮ,
c) если дополнительно потребовать: (|n|≡a (mod 10)) ⇒ L(|n|)=k) то W - изоморфизм

Определение. Зададим соответсвие V: Z⊗{последовательность цифр, не равные станционано 9} в множество R:
V((±b,А1, А2, А3,...,АN,...)) = ±sup{b+А1*10-12*10-2+...+АN*10-n}, где N принимает все натуральные значения. Элемент этого множества Z⊗{последовательность} называется десятичной записью действительного числа.

Задача 7. a) V - взаимооднозначное отображение.
b)** Задайте естественные операции сложения и умножения десятичных записей действительных чисел и докажите, что V - изоморфизм и ро сложению и по умножению.

в ы в о д. всякому действительному числу из отрезка [0, 1] СООТВЕТСТВУЕТ ЕДИНСТВЕННАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ 0,А1А2...АN...

КОНТИНУУМ.

ОПРЕДЕЛЕНИЕ. МОЩНОСТЬЮ КОНТИНУУМА НАЗЫВАЕТСЯ МОЩНОСТЬ МНОЖЕСТВА А01 - БЕСКОНЕЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ 0 И 1.

ЗАДАЧА 8. ТЕОРЕМА КАНТОРА (БЕЗ ДОК-ВА), МНОЖЕСТВО ВСЕХ ПОДМНОЖЕСТВ МНОЖЕСТВА X БОЛЕЕ МОЩНО, ЧЕМ X. МНОЖЕСТВО ВСЕХ ПОДМНОЖЕСТВ МНОЖЕСТВА X ОБОЗНАЧАЕТСЯ П(Х)

Задача 9. a) П(N) континуально
в) А01⊗А01 континуально
c) R континуально
d) [0,1] континуально
e) множество точек квадрата континуально
f) множество всех отрезков прямой континуально
g) подмножество R, в десятичной записи которого отсутствует цифра 7 континуально

задача 10. можно ли построить на плоскости континуум непересекающихся: а) окружностей b) кругов с) восьмерок d) букв T

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

аксиома (континуум-гипотеза): не существует множества, промежуточного по мощности между счетным и континуумом.

расширенная система вещественных чисел.

добавим к R еще два элемента: R = R ∪ {-∞, +∞}
зададим правила обращения с этими элементами:
А) ∀x∈R: x+∞ = +∞; x-∞ = -∞ x/+∞ = x/-∞ = 0
В) ∀x>0: x*(+∞)=+∞; x*(-∞)=-∞
С) ∀x<0: x*(+∞)=-∞; x*(-∞)=+∞
D) УМНОЖЕНИЕ И СЛОЖЕНИЕ КОММУТАТИВНО.
ПРИМЕЧАНИЕ: ВЫРАЖЕНИЯ ВИДА А+В, А-В, А*В, А/В, ГДЕ A=±∞, B=±∞ НЕ ОПРЕДЕЛЕНЫ.

УПРАЖНЕНИЕ 12. В R СОХРАНЯЮТСЯ СВОЙСТВА УПОРЯДОЧЕННОСТИ (СВ-ВА 12 - 15)
R НЕ ЯВЛЯЕТСЯ ГРУППОЙ НИ ПО СЛОЖЕНИЮ* НИ по умножению.

УПРАЖНЕНИЕ 13. СФОРМУЛИРОВАТЬ АКСИОМУ О ВЕРХНЕЙ ГРАНИ И ПРИНЦИП ВЛОЖЕНИЯ ОТРЕЗКОВ В R.

ЗАЧЕТ ПО ТЕОРИИ ЧИСЕЛ В 9В

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

2.Студент..............................(заполняется Сокирко)

3. Обязательные определени я знает: подпись
а) разбиение на классы
б) отношение эквивалентности
в) определение группы
г) определение кольца
д) определение тела и поля
Нужно знать определения и уметь давать по два - три примера

4. Теория множеств
Определение конечного, бесконечного, счетного, несчетного, и не более чем счетного множеств.
Счетное множество счетных множеств
Теорема Кантора ( с доказательством)
Теорема Кантора-Бернштейна ( с доказательством)
Примеры счетных множеств ( не менее 10)
Примеры континуальных множеств ( не менее 5 )
Пример гиперконтиннуального множества.
(Приводить примеры самим и уметь доказывать предложенные)

Натуральные числа:
Формулировки аксиом Пеано. Свойства натуральный чисел, ТВ,

Целые числа: определение, сложение, умножение. Изоморфизм положительных целых чисел натуральным.

Рациональные числа: определение, сложение, умножение. Изоморфизм

Действительные числа: определение сечений, сложение, умножение и неравенства действительных чисел. Плотность дей. чисел

УМЕТЬ ДОКАЗЫВАТЬ ВСЕ СВОЙСТВА ЧИСЕЛ, КАК И ОБЯЗАТЕЛЬНЫЕ В ЛИСТОЧКЕ, ТАК И ИМ АНАЛОГИЧНЫЕ.

Точные грани:

Определение ограниченого сверху, ограниченого множеств, sup, inf. Существование sup у ограниченого сверху множества. Уметь находить sup, inf у любых множеств.
Принцип Архимеда: его формулировка (1а) и доказательство
Принцип вложеных отрезков и интервалов
Расширенная система комплексных чисел

ОГЛАВЛЕНИЕ

ОЦЕНКА.........(просьба записать все замечания по ответу на обороте)

ЛИСТОК 26. КОМПЛЕКСНЫЕ ЧИСЛА.

Выдано 11.11.85

В это листке z, u, v, w - комплексные числа, n∈N; k∈Z, остальные - действительные.

ПОЛЕ КОМПЛЕКСНЫХ ЧИСЕЛ

На множестве C=R⊗R называется множеством комплексным чисел, если на нем заданы операции сложения и умножения.

II

СЛОЖЕНИЕ. Зададим операциию сложения: (a, b) + (c, d) =def= (a+c, b+d)

Задача 1.?а) С образует абелеву группу по сложению
b) Определите разность комплексных чисел.

III

УМНОЖЕНИЕ. Зададим операцию умножения: (a, b)*(c, d) =def= (ac-bd, ad+bc)

Задача 2. С образует поле, т. е. кроме задачи 1:
a) С\(0,0) образует абелеву группу по умножению
b) z*(u+v)=z*u + z*w - дистрибутивность.
c) определите частное двух комплексных чисел

IV

БОЛЬШЕ-МЕНЬШЕ для комплексных чисел не определено !!!!

МОДУЛЬ комплексного числа |(a, b)|=def= √(a2+b2)

Задача 3. а) |z|=0 ⇔ z=(0,0)
b) |u*v| =|u|*|v|

V

Задача 4. Докажите, что подмножество {(а, 0)} изоморфно R:
а) относительно операции сложения
b) относительно операции умножения
с) относительно операции взятия модуля
В дальнейшем комплексное число (а,0) будем записывать просто как а

АЛГЕБРАИЧЕСКАЯ ФОРМА

Определение: i=def=(0, 1)

Задача 5. a) i*i=-1 b) (a,b)=a+b*i

Запись a+bi называется алгебраической формой комплексного числа. Эти числа можно перемножать и складывать, как обычные числа, с учетом того, что i*i=-1

Определение: а) Функция "действительная часть" ℜ(a+bi) =def= a
b) Функция " мнимая часть" ℑ(a+bi)=def= b
с) Функция "взятие комплексносопряженного": z =def= ℜz - ℑz*i

Задача 5. а) u+v=u + v b) u*v=u * v c) u/v=u / v
d) u*u=|u|2 e) (u+u)∈R f) u∈R ⇔ u=u

Задача 6. Функция взятия комплексносопряженного является автоморфизмом

ГЕОМЕТРИЧЕСКАЯ ФОРМА

Множество R⊗R иногда называют координатной плоскостью, а его элемент (х,у) - точками или (свободными) векторами. Для векторов задано сложение с помощью правила паралелограма, совпадающее (проверьте!) со сложением комплексный чисел, а модуль комплексного числа совпадает с длиной соответствующего вектора.

Задача 8. |u+v| ≤ |u| + |v| b) |u-v| ≥ ||u|-|v||
В каких случаям имеем равенство?

Упражнение 9. Докажите с помощью комплексных чисел, что в произвольном параллелограме сумма квадратов длин диагоналей равна сумме квадратов длин всей сторон.

МАТРИЧНЯЯ ФОРМА

Задача 10. Докажите, что все матрицы с действительными элементами вида
ab
-ba
; образуют поле, изоморфное С.

ПОЛЯРНЫЕ КООРДИНАТЫ на (обычной) плоскости

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

{x = r * cosφ {r = √(x2+y2)
y = r * sinφtgφ = y/x
;

Функция взятия аргумента определена для всех (r,φ), где r≠0.
Arg((r,φ) = φ + 2πk где π - число "пи",
т.е. она имеет бесконечное число значений для каждой точки. Запись Arg z = φ означает, что одно из значений этой функции равно φ. Когда потребуется однозначная функция, будем писать arg(r,φ)= φ (0≤φ<2π) и называть главным аргументом.

Упражнение 11. Изобразите на координатной плоскости множества точек (r,φ):
a)r = const b) φ = const с)r = φ (спираль Архимеда)
d) r = sin 3φ (роза) е) r = 1/cosφ f) r = √cos 2φ (леминиската)
g) r = 1 + cosφ (кардоида) h) r = 1/cosφ - cosφ (циссоида)

Упражнение 12. Напишите уравнение кривых в полярных координатах:
а) х2 + у2 = 1 b) у = х2 с) (х-1)2 + у2 = 1

ТРИГОНОМЕТРИЧЕСКАЯ ФОРМА КОМПЛЕКСНОГО ЧИСЛА

ЗАПИСЬ КОМПЛЕКСНОГО ЧИСЛА В ВИДЕ z = r*(cosφ + i*sinφ) НАЗЫВАЕТСЯ ТРИГОНОМЕТРИЧЕСКОЙ ФОРМОЙ.

УПРАЖНЕНИЕ 13. ЗАПИШИТЕ В ТРИГОНОМЕТРИЧЕСКОЙ ФОРМЕ:
А) 3 + 3*I B) -3 - √27 * I С) -1 D)I E) А + BI

УПРАЖНЕНИЕ 14. ИЗОБРАЗИТЕ НА КОМПЛЕКСНОЙ ПЛОСКОСТИ МНОЖЕСТВА ТОЧЕК:
A)ℜ(z)> 0 В) |Z - Z1| = A С) |Z - Z1| < A
D) A < |z| < B E) |Z-I| = |Z-1|

ЗАДАЧА 15. U=r*(cosφ + i*sinφ), V=s*(cosψ + i*sinψ):
A) U*V = r*s(cos(φ + ψ)+ i*sin(φ + ψ))
B) U/V = r/s(cos(φ - ψ)+ i*sin(φ - ψ))

ЗАДАЧА 16, (ФОРМУЛА МУАВРА)
(r*(cosφ + i*sinφ))n = rn*(cos(n*φ) + i*sin(n*φ))

УПРАЖНЕНИЕ 17. ВЫЧИСЛИТЕ:
A) (1+i)100 B) (1- i* √3)100/2100
...С ПОМОЩЬЮ ФОРМУЛЫ ГЕОМЕТРИЧЕСКОЙ ПРОГРЕССИИ СУММЫ ПО К ОТ 1 ДО N ОТ:
С) СОS(К*φ) D) SlN((2K-1)*φ) Е) Z + 1/Z = 2*COSφ ⇔ Zn + 1/Zn = 2*COS(n*φ)

ИЗВЛЕЧЕНИЕ КОРНЕЙ.

ЗАДАЧА 18. А) СКОЛЬКО РАЗЛИЧНЫХ РЕШЕНИЙ У УРАВНЕНИЯ (cosφ + i*sinφ)n = 1? НАЙДИТЕ ИХ И ОБОЗНАЧЬТЕ НА ПЛОСКОСТИ, МНОЖЕСТВО РЕШЕНИЙ ЭТОГО УРАВНЕНИЯ НАЗЫВАЕТСЯ МНОЖЕСТВОМ КОРНЕЙ N-НОЙ СТЕПЕНИ ИЗ 1.
B) ВСЕ КОРНИ ИЗ 1 N-НОЙ СТЕПЕНИ ОБРАЗУЮТ ЦИКЛИЧЕСКУЮ ГРУППУ ПО УМНОЖЕНИЮ.
C) НАЙДИТЕ ВСЕ РЕШЕНИЯ УРАВНЕНИЯ z =(r*(cosφ + i*sinφ))n

УПРАЖНЕНИЕ 19, НАЙДИТЕ ВСЕ А) КОРНИ 3 СТЕПЕНИ ИЗ -8
B) КОРНИ 3 СТЕПЕНИ ИЗ i
C) КОРНИ 4 СТЕПЕНИ ИЗ i.

Листок 27ПМ. Многочлены (обобщающий)

В этом листке рекомендуется использовать идеи $3 гл. 2 Агебры 9, избегая, однако, прямых ссыпок на учебник. Повторите также листки 6-8. Доп. литература: В. L. Van-der-Waerden

Определение: Многочленом P(х) над кольцом K называется конечная последовательность козфицентов ai∈K, записаная в виде: Р(х)=a0*x0+a1*x1+...+аnn

Множество многочленов над K обозначается К[x]. Если среди коэффицентов существуют ненулевые, то наибольший их индекс называется степенью многочлена. Обозначение многочлена степени n: Pn(x). Два многочлена равны, если равны все их ненулевые коэффиценты с одинаковыми индексами. Козфиценты Pn(x) обозначим через ai, Qm(x) - bi, Tk(x) - ci (i,j,k,l,m,n ∈ Z0)

I

СЛОЖЕНИЕ. Pn(x) + Qm(x) = Tk(x) ⇐def⇒ для ∀i ai + bi = ci

Задача 1. Многочлены образуют абелеву группу по сложению.

II

УМНОЖЕНИЕ (столбиком ) Pn(x) * Qm(x) = Tk(x) ⇐def⇒ для ∀i ci = a0*bi + a1*bi-1 +...+ ai*b0

Задача 2. Многочлены образуют кольцо.

IV

Задача 3. Многочлены нулевой степени и ноль образуют кольцо, изоморфное K. Поэтому a0*x0 будем записывать просто как a0.

V

св-во ЦЕЛОСТНОСТИ -def- a*b=0 ⇔ a=0 OR b=0

Задача 4. а)приведите пример нецелостного кольца
b) Z, Q, R, С - целостные кольца (во всех последующих задачах будем рассматривать только целостные кольца)
с) многочлены над целостным коммутативным кольцом с единицей образуют также целостное коммутативное кольцо с един.

Задача 5. Напишите программу, доказывающую, что деление многочленов один на другой с остатком всегда выполнимо и однозначно.

Определение: Многочленом от двух переменых (x,y) над кольцом К называется (K[x])[y]; обозначается K[х,у]. Аналогично определяется мночлен от n переменых.

Задача 6.(связь с учебником).
Многочлен по учебнику -def- функция f:K→K: для ∀ x∈K: f(x)=a0+a1*x+...+аnn
а) Многочлены совпадают как функции ⇔ они равны
b) Известно, что P(х) меньше 5*(х2+1)3 + 1000 при всех х. Что можно сказать о степени P?

Определение:P a - корень Pn(x) ⇐def⇒ Pn(a)=0

Задача 7. Теорема Безу. Pn(x) делится на x-a ⇔ a - корень Pn(x).

Упражнение 8. При делении многочлена Pn(x) на (x-1) получается остаток 2, а при делении на х-3 - остаток 1. Найти остаток при делении на (х-1)*(х-3).

Если Pn(x) делится на (х-a)k, но не делится на (х-a)k+1, то a называют корнем кратности k и рассматривают как k штук совпадающих корней.

Задача 9 а) xl, x2,..., xn - корни Pn(x) ⇔> Pn(x) = an*(x - x1)*(x - x2)*...* (x - xn)
b) отличный от нуля многочлен степени n имет не более n корней

Упражнение 10. Разложите на линейные множители над С: а) х2+1 b)x2-2*x+5 с)х3+1 d)x3+x-2
е) x4+1 f)x4+x2+l g)xn-1

ИНТЕРПОЛЯЦИЯ. Часто от графика некоторой неизвестной функции известно только n точек. Интерполяцией называется проведение через известные точки (х,у) некоторой функции, задаваемой, скажем, многочленом.

Задача 11. Интерполяция по Лагранжу
а) Докажите, что многочлен n-степени

(x - d0)*(x - d1)*...* (x - di-1)*(x - di+1)*...* (x - dn)
fn = ---------------------------------------------------------------
(di - d0)*(di - d1)*...* (di - di-1)*(di - di+1)*...* (di - dn)

в точке di принимает значение 1, а во всей остальных точках dj (j≠i) равен 0
b) получите многочлен, проходящий через n+1 точку (d0,y0),... (dn,yn) как линейную комбинацию fi(x)
c) найти многочлен степени 3, для которого P(1)=1 ,P(2)=5, P(3)=0, Р(4)+P(5)=8

Задача 12. Интерполяция по Ньютону
f(x) = g0 + g1*(x-d0) + g2*(x-d0)*(x-d1)+ ... + gn*(x-d0)*(x-d1)*...*(x-dn-1)
Определите коэффициенты g0, g1,..., gn так, что бы в точках di f(x) принимала значение yi путем последовательной подстановки x = d0, d1,..., dn
a) n=2 b) n=3 с) произвольное натуральное n.

Упражнение 13. (Ван-дер-Морд) Доказать, что система

x +y +z +t= a
x +2y +3z +4t= b
x +4y +9z +16t= c
x +8y +27z +64t= d

при любых a,b,c,d ∈ R имеет единственное решение в действ. числах. Почему тут дана эта задача?

Упражнение 14. Нарисовать множество тех пар (р,q), при которых квадратныый трехчлен x2 + p*x + q имеет 2 положительных корня

Задача 15. Рациональные корни многочлена с целыми коэффицентами
а)Пусть несократимая дробь m/q - корень многочлена с целыми козффицентами ⇒ q делит старший член AND m делит младший
b) старший член равен 1 ⇒ рациональный корень является целым
c) Корень натуральной степени из натурального рационален ⇒ он цел
d) Р(х)∈ Z[x]; Р(0) и P(1) - нечетные числа ⇒ Р(х) не имеет целых корней

Задача 16. а)Определите НОД(Pn(x),Qm(x)) и НОК(Pn(x),Qm(x)) (Л6)
b) С помощью алгоритма Евклида докажите, что НОД(Р,Q) - единственен

Упражнение 17. а)НОД(хm-1,хn-1)=хНОД(m,n) - 1
b) Найти НОД и НОК х4 - 4х3 + 1 и х3 - 3х2 + 1

Задана 18. Pn(x) и Qm(x) не имеют общих делителей ⇒
а) Существуют многочлены R(x); T(x): Pn(x)*R(x) + Qm(x)*Т(х) = 1
b) ∀Sk(x) степени k/<(n+m) ∃ многочлены R(x) степени меньше m и Т(х) степени меньше n: Sk(x) = Pn(x)*R(x) + Qn(x)*Т(х)
с) Следствие: Sk(x)/(Pn(x)*Qm(x)) = R(x)/Qm(x) + Т(х)/Pn(x)
Применяя это св-во несколько раз, получаем разложение дроби S(x)/G(x) на столько дробей, сколько элементарных сомножителей содержится в раззложении G(x) на простые множители.

Задача 19. Однозначность разложения на множители
Любой многочлен разлагается в произведение неприводимых (т.е. таких, которые невозможно разложить дальше) единственным образом, если дополнительно потребовать, чтобы коэффиценты при их старших степенях быыли равны 1.

Определение: Производной(формальной) многочлена Рn(х) = a0+a1x+...+аnn называется многочлен Р'n(х) = a1 + 2*a2*x+...+n*аnn-1
k-ая производная -def- производная от k-1 производной

Задача 20 а) a - корень кратности k>1 Рn(х) ⇒ a - корень кратности k-1 Р'n(х)
b) Напишите выражение для k-ой производной Рn(х)

Упражнение 21. Найдите кратность корня x=1 для многочлена x2n - n*xn+1 + n*xn-1 - 1

Задача 22 а) Формула Тейлора для многочленов:
P(x+a) = P(а) + Р'(а)*x/1! + Р''(а)*x2/2! + ... + Р''...'(a)*xn/n!
b) Рn(х)= 1 + x/1 + x2/2! + ... + xn/n! не имеет корней кратности больше 1.

ОСНОВНАЯ ТЕОРЕМА АЛГЕБРЫ (без доказательства) Любой многочлен из С[х] имеет хотя бы один корень

Задача 23. а) Если все козффиценты комплексного многочлена действительны и a - корень ⇒ a - тоже корень
b) Рn(х)∈R[x], n - нечетно ⇒ существует хотя бы один корень
c) Любой многочлен из R[x] можно разложить в произведение действительных многочленов 1 и 2 степени

Упражнение 24. Многочлен степени 4 имеет 3 различных действительных корня. Может ли его производная иметь 1 (один) действительный корень?

Упражнение 25. Разложите на линейные и квадратичные множители с вещественными коэффицентами:
а) х6 + 27 b) х4 + 4*х3 + 4*х2 + 1
с) x2n - l d) x2n+1 + 1

СИММЕТРИЧЕСКИЕ МНОГОЧЛЕНЫ.

Многочлен кольца K[x1,..,xn] называется симметрической функцией переменных x1,..,xn, если он переходит в себя при любой перестановке переменных x1,..,xn.

Задача 26. Теорема Виета.
(x - x1)*(x - x2)*...*(x - xn) = xn - s1*xn-1 + s2*xn-2 + ...(-1)n*sn
а) выразите si через x1,..,xn
b?) s1,..,sn - симметрические функции x1,..,xn. Они называются элементарными

Задача 27. Основная теорема о симметрических многочленах
а) Любой симметрический многочлен из кольца K[x1,..,xn] может быть записана в виде многочлена от n переменых s1,..,sn
b) причем единственным образом

Упражнение 28. Представить в виде многочлена от s1,..,sn
а) х12 + х22 +...+ хn2
b) х13 + х23 +...+ хn3

Упражнение 29. s1,s2,s3 ∈ Z ⇒ х13 + х23 + х33 ∈ Z

ЭТО ПОСЛЕДНИЙ ОБЯЗАТЕЛЬНЫЙ ЛИСТОК ПО АЛГЕБРЕ В ЭТОМ ГОДУ

1 2 3 4 a b с 5 a b с 6 7 8 9 а 10 11 а b с 13 14 15 a b с d


16 a b 17 а b 18 а b с 19 20 а b 21 22 а b 23 a b с 24 25 abcd


26 a b 27 a b 28 a b 29 ЗАКРЫТИЕ


Листок 28. ПРЕДЕЛЫ.

Отрезок [a,b] - ловушка для последовательности {xn} -def- если почти все xn лежат в [a,b].
Отрезок [a,b] - кормушка для последовательности {xn} -def- если бесконечно много xn лежат в [a,b].

Задача 1. [a,b] - ловушка ⇒ он кормушка. Верно ли обратное?

Упражнение 2. Могут ли [0,1] и [2,3] являться одновременно для {xn} а) кормушками b) ловушками?

Задача 3. а) Существуют ли последовательность, не имеющая ни одной кормушки?
b) Существуют ли последовательность, для которой любой отрезок является кормушкой?

Упражнение 4. [0,1];[9,10] - кормушки для {xn}. Существуют ли для этой последовательности а) ловушка длины 1 b) ловушка длины 9?

ОПРЕДЕЛЕНИЕ ПРЕДЕЛА

Число a называется пределом последовательности {xn}, если для ∀ε>0 ∃k∈N такое, что для ∀ n>k |xn-а|<ε. Обозначение lim x = a n→∞ или xn→a при n→∞.

Задача 5. xn→a при n→∞ ⇔ любой отрезок с центром в точке a является ловушкой для {xn}

Задача 6. а) xn→a при n→∞ ⇒ любой отрезок с центром в в точке a - кормушка, а никакой отрезок, не содержащий а, не является кормушкой.
b) верно ли обратное?

Упражнение 7. Какие из следующих последовательностей имеют пределы:
а)1;-1/2;1/3;-1/4;1/5;...
b) 1;1+1/2; 1 + 1/2+1/4;...
с) 1; 2; 3; 4;...
d) -1; 1; -1; 1;...
е) 1; 1; 1; 1;...
f) 0.2; 0.22; 0.222; 0.2222;....
g) 0; 1; 0; 1/2; 0; 1/3; 0; 1/4;... f) 0; 3/2; -2/3 ; ....; (-1)n+1/n;....

Задача 8. Могут ли два различных числа быть пределом одной и той же последовательности?

Определение предельной точки.
Число а называется предельной точкой последовательности {xn} если ∀ε>0 ∀k∈N ∃ n>k |xn-а|<ε.

Задача 9. а - предельная точка последовательности {xn} ⇔ любой отрезок с центром в а является кормушкой для {xn}.

Задача 10. а - предел {xn} ⇒ а - предельная точка {xn} AND у {xn} нет других предельный точек, кроме а.

Упражнение 11. Для каждой из следующих последовательностей укажите все ее предельные точки:
a) xn = (n+1)/n b) xn = (-1)n c) xn = sin n
d) xn = n(-1)n е) xn = n
f) 1/2; 1/3; 2/3; 1/4; 2/4; 3/4; 1/5; 2/5; 3/5; ...

Задача 12.а) Докажите, что всякая ограниченая последовательность имеет хотя бы одну предельную точку.
b) справедливо ли а) в случае не действительных, а рациональных последовательностей?

Задача 13. дайте определение последовательности, стремящейся к ∞.

Упражнение 15. Какие из следующих последовательностей ограничены, не ограничены, стремятся к ∞:
a) n = n b) xn = n*(-1)n с) xn = (-1)(-1)n
d) xn = { n при четном n и √n при нечетном n }
e) xn = 100*n/(100 + n2)

1 2 a b 3 a b 4 a b 5 6 a b 7 a b c d e f g h 8 9 10 11 a b c12 a b 13 15 a b с d e f


Листок 28. ПРЕДЕЛЫ.(альтернативный)

Интервал (а-ε;а+ε), где ε>0 назыывается ε-окресностью точки а и обозначается Oε(а)

ОПРЕДЕЛЕНИЕ ПРЕДЕЛА

Число a называется пределом последовательности {xn}, если для ∀ε>0 ∃k∈N такое, что для ∀ n>k |xn-а|<ε. Обозначение lim x = a n→∞ или xn→a при n→∞.

Задача 5. xn→a при n→∞. ⇔ любая ε-окресность а содержит почти все члены этой последовательности.

Упражнение 6. Что означает, что число а не является пределом последовательности {xn}?

Упражнение 7. Какие из следующих последовательностей имеют пределы:
а)1;-1/2;1/3;-1/4;1/5;...
b) 1;1+1/2; 1 + 1/2+1/4;...
с) 1; 2; 3; 4;...
d) -1; 1; -1; 1;...
е) 1; 1; 1; 1;...
f) 0.2; 0.22; 0.222; 0.2222;....
g) 0; 1; 0; 1/2; 0; 1/3; 0; 1/4;... f) 0; 3/2; -2/3 ; ....; (-1)n+1;....

Задача 8. Могут ли два различный числа быть пределом одной и той же последовательности?

Определение предельной точки.
Число а называется предельной точкой последовательности {xn} если ∀ε>0 ∀k∈N ∃ n>k |xn-а|<ε.

Упражнение 9, Докажите, что любая ε-окресность предельной точки содержит бесконечно много членов последовательности.

Упражнение 11. Для каждой из следующих последовательностей укажите все ее предельные точки:
a) xn = (n+l)/n b) xn = (-1)n c) xn = sin n
d) xn = n(-1)n е) xn = n
f) 1/2; 1/3; 2/3; 1/4; 2/4; 3/4; 1/5; 2/5; 3/5; ...

Задача 12.а) Докажите, что всякая ограниченая последовательность имеет хотя бы одну предельную точку.
b) справедливо ли а) в случае не действительных, а рациональных последовательностей?

Задача 13. дайте определение последовательности, стремящейся к ∞.

Упражнение 15. Какие из следующих последовательностей ограничены, не ограничены, стремятся к ∞:
a) n = n b) xn = n*(-1)n с) xn = (-1)(-1)n
d) xn = { n при четном n и √n при нечетном n }
e) xn = 100*n/(100 + n2)

5 6 7 a b c d e f g h 8 9 11 a b c d e f 12 a b 13 15 a b с d e f


Листок 29. Пределы

1) Пусть сущ. lim xnn→∞, lim ynn→∞:

a) xn = yn ⇒ lim xnn→∞ = lim ynn→∞:

b) xn ≥ yn ⇒ lim xnn→∞ ≥ lim ynn→∞:

c) верно ли, что xn > yn ⇒ lim xnn→∞ > lim ynn→∞:

2) lim xnn→∞ = a, lim ynn→∞ = b,

a) ∃ lim {xn ± yn) n→∞ = a ± b

b) ∃ lim {xn * yn) n→∞ = a * b

c) ∃ lim {xn / yn) n→∞ = a/b, b≠0

d) Обобщите теоремы для {a,b}∈R

3) Найти пределы для n→∞:
a) {xn} = (a*n2 + b*n + c)/(a*n2 + e*n + f)
b) {xn} = √(n2 + 1) - √(n2 - 1)
c) {xn} = sgn(n2 - 5*n -7)
d) {xn} = (2n + 3n+1 + 5n-1)/(3n + 5n+1)
e) {xn} = n *(√(n2 + 1) - n)

4. lim xnn→∞ = lim znn→∞ = a

∃k∈N такое, что для ∀ n>k xn≤yn≤zn ⇒ lim ynn→∞ = a (принцип милиционеров)

b) Лювая ограниченная монотонная последовательность имеет предел

5. Найти пределы при n→∞
a) xn: ∀n: n/(3n+5) < xn < (n4 + 15)/(3*n4 + 7)
b) xn = 1/(n2+1) + 1/(n2+2) + ... + 1/(n2+n)
c) xn = √(n2 + 1) - ∛(n3 + 1)
d) xn+1 = √(3*xn); x1=a
e) xn = cn
f) xn+1 = (xn + 1)/n2; x1=a

6) xn - ограничена, lim ynn→∞ = 0 ⇒ ∃ lim (xn*yn)n→∞ = 0

7) Найти пределы при n→∞
a) xn = {π;n}/n b) xn = [π;n]/n
c) xn = (cos n2 + 2* log n)/(4 * log n)2

8) a) Пусть ∀n xn>0 и lim {xn+1/xn)n→∞=a, a<1, тогда ∃ lim xnn→∞ = 0

b) что будет если a>1?
c) а=1?

9) Найти пределы:
а) xn = (na)/(an), a>1?
b) xn = (2n)!/an!
c) xn = (4*7*10*...*(3*n+1))/(2*6*10*...*(4*n+2))

10) Найти сумму геометрической прогрессии: x1 = b, xn+1 = xn + b*qn, lim xnn→∞ = ? Расмотреть разные q.

11) Найти lim sn = n→∞

a) sn = k=1 n∑ 1/(2k)

b) sn = k=1 n∑ (2k+1)/(22k)

c) sn = k=1 n∑ (-1)k/3k

d) sn = k=1 n∑ ((1 + 3 + 9 + ... 3k)/5k+2

e) w=0,a1a2a3...ak(b1b2...bm) - периодическая дробь; a = a1*10k-1 + a2*10k-2 + ak; b = b1*10m-1 + b2*10m-2 + bm; Выразить w через a и b

12) f - возрастающая функция, xn = f(xn-1), n>1
a) Докажите, что если x1≤x2, то xn - возрастает, x1≥x2, то убывает.
b) Если f - ограничена, то ∃ lim xnn→∞

13) Найти пределы при x1
а) xn = √(3 + xn-1) (n>1, x≥-3)
b) xn = - √(1 - xn-1) (n>1, x≤1)
c) xn = - xn-1 - xn-12 (n≥2, 0≤x≤1)
d) xn = 0.5*(xn-1 + a/xn-1) (n>1, a>0; x>0)
e) xn = 1/3*(2*xn-1 + a/xn-12) (n>1, a>0; x>0)
f) xn = xn-12 + 3*xn-1 +1 (n>1)

14) f - убывающая функция. xn = f(xn-1), n>1
а) x2n-1 и xn - монотонны, одна убывает, другая возрастает.

15) Найти пределы:
а) xn = cos(xn-1), x1=1
b) xn = (1-xn-1)2, x1=0.5
c) xn = 1/(xn-1+1), x1=1
d) xn = (xn-1+a)/(xn-1+1), x1≥0, a>0

Листок 30. Топология

МЕТРИЧЕСКИЕ ПРОСТРАНСТВА.

Упражнение 1. Являются ли метрическими пространствами:
a) R с метрикой ρ(x,y) = sin2(x-y)
b) R с метрикой ρ(x,y) = arctg|x-y|
c) Окружнось с метрикой: кратчайшая длина дуги между точками
d) Произвольное множество с метрикoй ρ(x,x)=0; ρ(x,y)=1 при x≠y,
е) Множество всех ограниченных на множестве М функций с метрикoй ρ(f,g)= sup { f(x)-g(x) | x - любое из M}

Упражнение 2.а) ρ - метрика на M ⇒ ξ(x,y) = min(1, ρ(x,y)) - также метрика на M
b) На R введена норма : ||x|| = x/(1+|x|); ||+∞||= +1; ||-∞||=-1 Постройте метрику, соответствующую этой норме.
c) Постройте метрику с диаметром d, которой принадлежит ε-окрестность точки, причем 2*ε > d.

Задача 3. ρ - метрика на М, ξ - метрика на К ⇒
a) φ=ρ+ξ b) φ = max { ρ ξ } c) φ = √(ρ22)
- метрики на M⊗K

ТОПОЛОГИИ

Упражнение 4. Придумайте 2-3 интересных примера топологий

В этом разделе все будет происходить во множестве Х с топологией Ξ

Задача 5 а) Пересечение любого семейства замкнутых множеств замкнуто
б) Объединение конечного семейства замкнутых множеств замкнуто
с) Х и пустое множество замкнуты.
d) δА - замкнута

а) Окрестность (просто) точки -def- любое открытое множество содержащие эту точку.
б) х - точка прикосновения для А, если любая окрестность х пересекается с А
с) Замыкание А (обозначается [A]) -def- объединение всех точек прикосновения А
d) Внутреность А (обозначается Int A ) =def= Х\[X\A]
e) Граница А (обозначается δА ) =def= [A]\A

Задача 6 а) А - замкнуто ⇔ [A] = A
b) открытое А пересекается с В ⇔ А пересек. с [B]
c) A ⊂ [A] d) A ⊂ B ⇒ [A] ⊂ [B] e) [A ∪ B] = [A] ∪ [B]
f) [[A]]=[A] g) [A] ⊂ A ⇒ A - замкнуто

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

а) х - внутреняя для А -def- x ∈ Int A
b) x - граничная для А -def- x ∈ δА
с) х - предельная для А -def- в любой окрестности х существуют точки А, отличные от х ( в чем отличие от точки прикосновения?)

Задача 7. а) Int A - открыто
b) Множество предельных точек A - замкнуто
c) Множество предельных точек A, объединенное с А, - замкнуто
d) δА - замкнута.

Предельные точки и точки прикосновения

Пусть (М,ρ) - метрическое пространство. Топологией, порожденной метрикой ρ, называется семейство всех множеств U= {для ∀х∈U: ρ(x,U)>0}

Задача 8. a) Докажите, что порожденая топология - действительно топология
b) Постройте порожденые топологии на R и С с естественными метриками

Задача 9а) Для любых ∀х,y ∈ М x≠y ∃ их непересекающиеся окрестности
б) Приведите пример топологии, в которой а) не выполняется

Задача 10. A - открыто ⇔ вместе с любой точкой х А содержит и некоторую ε-окрестнось точки х.
b) А - замкнуто ⇔ {всех точек прикосновения А} ⊂ A

Задача 11. ПРИНЦИП Больцанно-Веейрштрасса
Любое ограниченное бесконечное множество имеет хотя бы одну предельную точку.

Задача 12. Опишите а) все замкнуто-открытые множества
б) все открытые(замкнутые) множества в R
с) все открытые(замкнутые) множества в Q

ПРЕДЕЛ ПОСЛЕДОВАТЕЛЬНОСТИ

Определение
Последовательнсть {xn} сходится в М к а (обозначается xn→а при n→∞) ⇐def⇒ для ∀ε>0 ∃k: для ∀n>k: ρ(a,xn)<ε.
Иначе xn→а при n→∞ -def- в любом шаре с центром в а лежат все x, начиная с некоторого.

Задача 13. Если предел последовательности существует ⇒
а) он единственен б) последовательность ограничена

Задача 14. xn→а; yn→b при n→∞ ⇒
a) лемма о непрерывности расстояния: ρ(xn, yn) → ρ(a,b) при n→∞
b) лемма о мажорировании: если для ∀n xn < yn ⇒ a≤b
c) сумма (xn + yn) → а+b при n→∞

Задача 15. а) Последовательность сходится в R с естественной метрикой ⇔ она сходится в метрике из 1b,OR 2a OR 2b
b) Тот же вопрос для R⊗R и метрик из задачи 3
Такие метрики называются эквивалентными

Задача 16* Докажите, что ρ(x,y)= | ||x|| - ||y|| | на R эквивалентна естественной на R (норма в смысле 2b)

Определение: а - предельная точка последовательности {xn}, если для ∀ε>0, ∀k∈N ∃ n>k: ρ(xn,a)<ε
(Чем отличается предельная точка последовательности от предела последовательности и от предельной точки мнoжества?)

Задача 17. Последовательность имеет предел ⇒ она имеет ровно одну предельную точку. Верно ли обратное?
b) Последовательность имеет предельную точку ⇒ можно выбрать подпоследовательность, сходящуся к а.

Задача 18.а) Сформулируйте и докажите Б-В для последовательностей в R
b) Справедлив ли он для последовательностей в Q?

1 a b c d e 2 a b c 3 a b c 4 5 a b c 6 a b c d e f g 7 a b c d


8 a b 9 a b 10 a b 11 12 a b c 13 a b 14 a b c 15 ab 16 17ab18ab


Листок 31. Число e

1. Последовательность аn = (1 + 1/n)n возрастает, а bn = (1 + 1/n)n+1 - убывает. (Указание: рассмотреть аn+1n и bn/bn-1 и воспользоваться неравенством Бернулли.)

2. {аn} и {bn} сходятся, причём lim ann→∞ = lim bnn→∞. Назовём этот придел числом e.

3. Пусть cn = 1 + 1/1! + 1/2! + ... + 1/n!. Докажите, что - {cn} сходится. Обозначим lim cnn→∞ = э.

4. э = e

5. Докажите, что e - cn ≤ 1/(n*n!). Вычислите первые 6 знаков числа e

6. Найти пределы последовательностей:
а) (1 + 1/(n+10))n б) (1 - 1/n)n в) (1 + 1/n2)n г)(1 + 1/(3*n))n

Возведение в степень (по мотивам 22 листка)

7. Для ∀x>0 x∈R и ∀n∈N ∃!y>0; y∈R: yn = x
Указание: Рассмотрите числа вида y ± (x - yn)/((1+y)n- yn) . Число будем называть арифметическим корнем из x. Обозначение: y = n√x. = x1/n

8. (x1/n)m = (x1/(k*n))(k*m) для любых x∈R; k,n,m∈Z. Поэтому правомерна запись (x1/n)m = xm/n

9. а= x1/n*y1/n = (x*y)1/n для x,y>0 и n∈N
б) x>1, p>q p,q∈Q ⇒ xp > xq

Определим теперь xy для x,y∈R и x>1 (для 1<x<1 определение аналогично):
xy =def= sup xp{p≤y|p∈Q}; 1y =def= 1

10. Основные свойства степенной функции:
а) x>1; y<z ⇒ xy < xz - монотонность
б) 1<x<z; y<0 ⇒ xy < zy
в) xy+z = xy*xz
г) (xy)z = xy*z
д) f(x) = xα - непрерывная функция.

Дальнейшие свойства e

11. α∈R\{0} а) исследуйте {(1 + α/n)n} на монотонность

б) lim (1 + α/n)nn→∞ = eα

в) (1 + α) < eα
г) lim xα*e-xn→∞ = 0

12. e - иррационально. Указание: n!*e ∉ Z

13**. Формула Стирлинга
аn = √(2*π*n)*(n/e)n: аn < n! < аn*e1/(12*n)
Эта формула используется очень широко в науке.

14. Какова приблизительно вероятность того, что в классе из 30 человек найдутся хотя бы двое, у кого совпадают днм рождения? При каком количестве человек эта вероятность больше 1/2?

ЛИСТОК 32. Бином Ньютона.

"Что есть лучшего? -
сравнив прошедшее, свести его с настоящим"
К.Прутков.

ОБЯЗАТЕЛЬНАЯ ЧАСТЬ.

1. Докажите формулу для Сnk по индукции для n.

2. Для ∀ n сумма Сnk с четными k равна сумме Сnk с нечетными k.

3. k=0 n-1∑ Сnknk+1 = С2*nn+1

4. Задача 473 2).3) из Алгебры 9.

5. Найти k,n, если Сn+1k: Сnk+1: Сnk-1 =6:5:2

6.Докажите а) тождество: Сnk + 3*Сnk-1 + 3*Сnk-2 + Сnk-3 = Сn+3k
б) неравенство: С2n+kn * С2n-kk ≤ (С2nn)2
в) Найти max (1+x)36 + (1-x)36 при |x|≤1

ДОПОЛНИТЕЛЬНАЯ ЧАСТЬ.

"-Ну да, неизвестно, - послышался все тот же дряной голос из кабинета,- подумаешь, бином Ньютона!"
М.Булгаков "Мастер и Маргарита"

7. ГЕОМЕТРИЧЕСКИЕ ЧИСЛА

а) Выложите из трех кругов правильный треугольник со стороной 2. Сколько потребуется кругов для треугольника со стороной три, четыре... Докажите, что эти числа (т. н. треугольные) лежат во втором столбце прямоугольногго треугольника Паскаля.

б) Тот же вопрос для правильных тетраэдров, выложенных из шаров (см. 3 столбец)

в) Сколько мячей содержится в пирамиде, у которой в основании выложен квадрат n*n, в следующем слое (n-1)*(n-1) мяч и наверху только один мяч

8. ЧИСЛА ФИБОНАЧИ

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

б) Расмотрите суммы Gn чисел стоящих на линиях, паралельных линии 1-5-3 и докажите, что Gn =Gn-1 + Gn-3 при n>3

9. СЛУЧАЙНЫЕ ПРОЦЕСЫ (их нравы)

а) Игрок имеет 1 долллар и в каждой игре с вероятностью р выигрывает 1 доллар, а с вероятностью 1-р проигрывает 1 доллар. С какой вероятностью он обанкротится?

б) На тропе в k шагах от пропасти стоит пьяница, который равновероятно делает шаг вперед и назад. Какова вероятность того, что он свалится в пропасть за n шагов или быстрее?

10. СТАТИСТИЧЕСКАЯ ФИЗИКА (из опыта работников зоопарка)

Сколько существует способов рассадить n зверей в m нумерованных клеток, если мы имеем дело со стадом а) бармаглотов б) фермионов в) бозонов. Биологи сообщают, что все бармаглоты отличаютстя между собой, а фермионы и бозоны - нет. Кроме того, очень опасно сажать более одного фермиона в клетку. Как изменится ответ, если клетки будут ненумерованны (неразличимы)?

"Не в совокупности ищи единства, но более - единообразии разделения" К.Прутков

11. ТРИНОМИНАЛЬНЫЕ КОЭФФИЦЕНТЫ

Выпишите в треугольник коэффиценты разложения тринома (1+x+x2)n Исследуйте св-ва триноминального треугольника, аналгичные св-вам тр. Паскаля.

12. ТРЕУГОЛЬНИК ЛЕЙБНИЦА

Откинув в тр. Паскаля 1 и заменив числа на обратные, получаем тр. Лейбница. В тр. Лейбница:
а) число равно сумме двух стоящих под ним (в тр.П. "над" ним)
б) сумма k-го (k>1) столбца в прямоугольном треуголльнике Лейбница равна числу 1/(k-1) (столбцы нумеруем с первого)
в) исследуйте другие св-ва треугольника Лейбница.

13. ОПТИКА

Напомните в 10 классе.

14. ПОЛИНОМИАЛЬНЫЕ КОЭФФИЦЕНТЫ

(x+y+z)n =def=∑ Dk,nm,l * xk * ym * zl
a) k+m+l=n
б) Dk,nm,l = n!/(k!*m!*l!)
в) Какой смысл имеют полиномиальные коэффиценты в задаче с шарами
г) обобщите на случай i переменых

"Усердие все превозмогает" К.Прутков

15. В автобусе

а) Сколькими способами можно разменять 20 коп?
Указание: рассмотрите (x1+x2+x3+x5+x10+x15)20

б) Сколько существует счастливых билетов от 000000 до 999999?
Указание: воспользуйтесь производящими функциями.

16. ДЕЛИМОСТЬ

Для ∀k: 0<k<n Сnk⋮p ⇔ p∈P AND n=pm

1 2 3 4 2) 3) 5 6 а б в 7 а б в 8 а б 9 а б 10 а б б 11


12 а б 14 а б в г 15 а б


Листок 36. Последний

Finita la comedia.

8 класс. 1 семестр.

Множества.

Равные. Подмножества и включение. Объединение, пересечение, разность, симметрическая разность.

Логические операции

"и", "или", "не", следствие, эквивалентность, матрицы истиности, сведение друг к другу. Закон доказательства от противного.

Связь законов логики и теории множеств.

Законы идемпотентности, коммутативности, ассоциативности, дистрибутивности, двойного отрицания, заключения, введения, удаления, применение их к решению задач.

Кванторы. Обратная и противоложная теоремы в кванторах. Определение ограниченных и неограниченных множеств.

Индукция.

Две формы полной математической индукции. Задачи на индукцию. Формула Бернули.

Целые числа

Делимость.

Общий делитель, НОД и НОК (их связь), взаимно простые, простые и составные числа - определения и простейшие свойства. Понятие линейной комбинации. Алгоритм Евклида. КРАЗ - определение, существование и единственность. Теоремы о простых числах, о сравнениях. Задачи на целые, простые числа, на сравнения, уравнения в целых числах.

Классы вычетов.

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

Системы счисления.

Римская и прочие, n-ричная. Двоичная, восьмиричная, шестнадцатиричная, двоично-десятичная. Запись в дополнительном коде.

Признаки делимости в десятичной системе на 2,5,10,3,9,11; в сторичной на 4,25,101; в тысячеричной на 8,125,7,11,13,27,37.

Функции целая часть, дробная часть, знак.

Геометрические перемещение

Паралельный перенос, симметрия относительно прямой, поворот, скользящая симметрия. Групповые свойства перемещений. Теорема Шаля, ее значение.

8 класс. 2 семестр. Теория групп.

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

в, на, наложение, вложение, взаимооднозначное.

Подстановки.

Определение, композиция, расширение, групповые свойства подстановок. Представление подстановок в виде произведения независимых циклов. Четность и нечетность числа транспозиций в разложении цикла.

Полугруппы.

Декартово произведение, бинарная операцния. Ассоциативность. Полугруппы.

Группа.

Единичный элемент, обратный элемент. Определение и примеры групп. Абелевы группы. Свойства обратный и единичный элементов, операции возведения в целую степень. Связь групп диэдра с группой подстановок.

Циклическая группа.

Порядок группы, порядок элемента, циклические группы и ее образующие. Группы простого порядка. Системы образующих, в частности порождение группы подстановок элементарными транспозициями; в группе диэдра и пифагоровых многограников.

Подгруппа.

Определение, свойства, примеры. Левые и правые смежные классы. Теорема Лагранжа и индекс подгруппы. Примеры смежных классов.

Перестановки и сортировки. Ключи. Сортировка. Устойчивость. Инверсии, таблица инверсий. Мультимножество, его перестановки. Соединенное произведение. Отрезки. Инволяции и табло Янга.

Изоморфизм групп.

Примеры, общие свойства. Теорема Кэли. Автоморфизмы и изоморфизмы группы в себя.

Факторгруппа.

Сопряженные элементы, св-во отношения эквивалентности для них. Классы сопряженный элементов, примеры. Нормальные подгруппы. Признаки нормальности подгрупп. Факторгруппа как множество смежный классов по нормальной подгруппе.

Гомоморфизм.

Гомоморфизм, гомоморфизм "на", эндоморфизм, ядро гоморфизма, естественный гомоморфизм. Другое определение факторгруппы. Примеры фактор-групп. Основная теорема о гомоморфизме, примеры на нее.

Дополнительные разделы теории групп.

Центр и централизатор, коммутант и коммутатор, разрешимые группы. Теорема: группа порядка р*р, где р - простое - абелева. Сложные задачи на теории групп.

9 класс. 3 семестр.

Матрицы.

Преобразование плоскости, формулы преобразований. Линейные преобразования. Вектор. Матрица. Матрицы перемещений и преобразований подобия плоскости, их определители. Композиция перемещений.

Матрицы как кольцо.

Матрицы n-гo порядка. Вырожденные матрицы и их геометрическая интерпритация.

Определители.

Определитель n-гo порядка, его св-ва. Его определение через сумму всевозможный перестановок. Четность и нечетность перестановок. Миноры и алгебраические дополнения. Использование ик для вычисления определителей и обратных матриц. Определитель Ван-дер-Морда. Правило Крамера.

Специальная теория относительности.

Постоянство скорости света, изотропия времени и пространства. Инвариант. Преобразование Галилея. Преобразование Лоренца - поворот в плоскости x,it. Преобразование длин, времени, скорости при переходе к другой системе координат.

Мощность множеств.

Счетность.

Равномощность. Конечные, бесконечные, счетные, несчетные, не более чем счетные. Доказательства равномощности различных множеств. Теорема Кантора-Бернштейна. Построение отображения счетного числа счетных множеств в счетное множеств.

Континуум.

Несчетность множества бесконечных последовательностей 0 и 1. Теорема Кантора. Примеры континуальных множеств. Примеры гиперконтинуальных множеств.

Натуральные числа N.

Аксиомы Пеано. Сложение, умножение, отношения порядка. Существование min элемента в любом подмножестве N.

Целыые числа Z.

Определение как классов эквивалентности N⊗N. Z - абелеева группа по сложению. Умножение. Отношение порядка. Изоморфизм положительных целых и натуральных чисел.

Рациональные числа Q.

Определение как классов эквивалентности Z⊗N. Сокращение дробей. Q - поле. Отношение порядка. Изоморфизм рациональных чисел со знаменателем 1 целым.

Сечение Дедекинда.

Определение сечения. Рациональные сечения. Множество сечений R - упорядоченное поле. Плотность рациональными чисел. Полнота вещественных чисел. Иррациональные числа. Существование и единственность арифметического корня на примере квадратного корня из 2.

Грани.

Верхняя и нижняя грани (sup и inf). Существование sup и inf у непустого множества вещественных чисел.

Последовательности.

Принцип Архимеда. Принцип вложенных отрезков. Последовательности: конечные, бесконечные, станционарные.

Позиционая запись.

Цифры. Изоморфизм натуральных чисел множеству конечных последовательностей цифр. Рациональное число как тройка целой непериодической части, периода, и десятичной степени. Период 9. Десятичная запись действительного числа как бесконечной последовательности цифр.

Расширенная система вещественных чисел.

Комплексные числа C.

Комплексные числа как декартово произведение R⊗R Комплексные числа как неупорядоченное поле. Модуль комплексного числа. i. Алгебраическая форма комплексного числа. Функции взятия действительной и мнимой части, комплексно-сопряженного, их св-ва. Геометрическая форма. Неравенство треугольника. Матричная форма. Группа кватернионов.

Полярные координаты.

Формулы перехода от полярных координат к декартовым и обратно. Функция взятия аргумента и ее главное значение. Тригонометрическая форма компексного числа. Сложение и умножение чисел. Формула Муавра. Применение геометрической прогресии для суммирования тригонометрических рядов.

Циклическая группа корней п степени из комплексного числа.

Многочлены.

Многочлен как конечная последовательность коэффицентов. Кольцо многочленов. Деление с остатком. Целостность. Многочлен от нескольких переменных.

Многочлен как функция. Корень многочлена. Теорема Везу. Интерполяция по Лагранжу, по Ньютону. Рациональные корни многочлена с целыми коэффицентами. НОД и НОК. Взаимопростые многочлены. Представление отношения многочленов в виде многочлена и простых дробей. Однозначность разложения многочлена на неприводимые. Многочлен n степени имеет не более n корней. Основная теорема алгебры (без док-ва).

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

Симметрические многочлены. Теорема Виета. Элементарные симметрические функции. Основная теорема о симметрических многочленах.

9 класс. 4 семестр.

Топология.

Метрические пространства. Примеры метрик.

Определение топологии. Св-ва замкнутых множеств. Окрестность точки, точки прикосновения: замыкание, внутренность и граница. Топологии, порожденные метрическими пространствами. Хаусдорфовость. Критерий открытости и замкнутости в порожденной топологии. Предельные точки и принцип Больцанно - Вейрштрасса.

Определение предела последовательности,

его единственность. Лемма о непрерывности расстояния. Эквивалентные метрики. Предельные точки и подпоследовательности.

Вычисление пределов.

Леммы о мажорировании, сумме, разности, произведении и частном пределов последователеностей. Принцип двух милиционеров и теорема Веейрштасса. Предел произведения ограниченной и сходящейся к нулю последовательности. Мажорирование суммой геометрической прогрессии. Суммы рядов. Пределы рекурентно заданых последовательностей. Теоремы о рекурентно заданных последовательностях.

Предел.функции.

Предел по Коши, по Гейне, их эквивалентность. Свойства, следующие из св-в пределов последовательности. Правые, левые пределы, классификация точек разрыва.

Непрерывность функции.

Непрерывность по Коши, по Гейне, по книге Рудина; их эквивалентность. Непрерывность на множестве; суммы и разности, произведения и частного; композиции функций и обратной. Функции Дирихле и Римана.

Определение компактности. Ограниченность и замкнутость компакта. Компактность отрезка.

Непрерывные функции в R.

Связность, всюду плотность множеств. Теорема Больцано-Коши. Отображения компакта. Теоремы Вейерштрасса. Функции, непрерывные на всюду плотном подмножестве.

Равномерная непрерывность

Определение. Теорема Кантора о непрерывности на компакте.

Дифференцирование.

Определение производной. Производная суммы, произведения, частного функций. Производная степенной функции, его совпадение с формальной производной многочленов. Производная сложной функции. Теоремы Рояля и Лагранжа. Пример всюду непрерывной и всюду недифференцируемои функции.

Правило Лопиталя. Понятие о формуле Тейлора для функций.

Комбинаторика

Треугольник Паскаля, его свойства. Бином Ньютона. Число сочетаний. Применение комбинаторики к решению школьный задач

Геометрические числа, числа Фибоначи, статистическая физика, триномиальные и полиноиинальные коэффиценты, треугольник г Лейбница, теория игр.

Приближенные вычисления.

С помощью бинома Ньютона, в тон числе и вещественной степени. Понятие о определении элементарным функций. Решение уравнений методом деления пополам, методом корд, методом касательным по Ньютону.

10 класс. 5 семестр. Факультативные курсы

ЭЛЕМЕНТАРНЫЕ ФУНКЦИИ

Число e

Определение числа e как предела последовательности (1+1/n)n, доказательство существования и единственности. Определение e как суммы ряда, доказательство эквивалентности определений. Числовая оценка для e. Пределы с е.

Возведение в степень.

Существование, единственность арифметического корня. Возведение чисел в любую рациональную степень, свойства операции возведения в степень. Возведение действительного числа в действительную степень, определенное как соответствующее как соответсвующее сечение, его свойства.

Показательная функция.

Свойство функции "число e в степени x"

Признак Даламбера сходимости рядов. Показательная функция как ряд, доказательство его сходимости. Тождественность двух определений показательной функции.

Иррациональность e.

Формула Стирлинга.

Тригонометрические функции.

Определение комплексных рядов их сходимости. Признак Даламбера сходимости комплексных рядов. Экспонента от комплексного числа ее свойства. Косинус и синус как действительные и мнимые части экспоненты чисто мнимого аргумента. Дифференцирование экспоненты, синуса и косинуса. Теорема о существовании числа π, в котором exp(2*π*k*i)=1.

Тригонометрические функции комплексного аргумента.

Гиперболические функции.

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

Логарифм

Логарифм положительного числа. Логарифм по действительному основанию. Свойство вещественной функции логарифма. Логарифмирование комплексный чисел. Главное значение логарифма. Возведение комплексного числа в комплексную степень. Обратные тригонометрические функции.

Комфорные отображения комплексной плоскости.

Перенос, поворот, растяжение. Любая линейная функция осуществляет преобразование подобия комплексной плоскости на себя

ИНВЕРСИЯ. Определение симметрии относительно окружности. Дробно-линейная функция; ее однозначность и круговое свойство. Примеры комфорных отображений плоскости.

Интеграл Римаиа.

Введение: недостатки школьного определения интеграла. Разбиение. Верхняя и нижняя суммы Дарбу, верхний и нижний интеграл. Функция по определению интегрируема, если совпадают верхний и нижний интегралы. Интеграл существует ⇔ верхняя и нижняя суммы Дарбу отличаются на бесконечно малую величину. Интегрируемость непрерывной функции. Интегрируемость монотонной функции. Свойства интеграла: интеграл от суммы функций, вынесение константы, неравенства, мажорирование интеграллов.

Интеграл как предел интегральных сумм.

Интеграл с переменным верхним пределом, его непрерывность и дифференцируемость. Формула Ньютона-Лейбница.

Понятие об интеграле Римана-Стильерса, его связь с интегралом Римана. Понятие об интеграле векторной функции.

Интегрирование по частям.

Теоремы о среднем значении интегралов, о замене переменный.

Ряды (продолжение).

Сходимость рядов.

Критерий Коши сходимости рядов. Признак сравнения. Геометрическая прогресия. Сходимость рядов из степеней натуральным чисел и произведений с логарифмами.

Признаки Коши и Даламбера, вопрос об их применимости.

Комплексные степенные ряды.

Радиус круга сходимости комплексного степеного ряда. Суммирование по частям. Теорема о сходимости произведения стремящейся к нулю последовательности и последовательности, имеющей ограниченные частичные суммы. Признак Лейбница сходимости знакопеременного ряда.

Абсолютная сходимость.

Определение абсолютной сходимости. Определение суммы и произведения рядов. Пример произведения двух сходящихся рядов, которые расходятся; теорема о сходимости произведения двух рядов, если один из них сходится абсолютно.

Безусловная сходимость.

Определение безусловной сходимости (перестановки сходятся). Теорема Римана о перестановке неабсолютно сходящегося ряда, приводящей к любому значению суммы. Эквивалентность абсолютной и безусловной сходимости.

Интегральный признак сходимости.

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

20а- Линейные пространства(авт. М. Вировец)
20b- Линейная алгебра(авт. А. Шень)
25- Плохие функции(авт. Л. Чехов)
30a- Мера Жордана (авт. М. Вировец)
33- Приложение мат. анализа(авт. А. Коган)
34- Применение определеного интеграла(авт. из 179 шк.)
35- Аксиома выбора(авт. М. Вировец)

Необычные интегралы.

Несобственные, от разрывных 1-го рода функций, главное значение интеграла.

θ-функция, δ-функция, ее производная.

UTEC прощается с вами.