Математика. Лекция 1 Множества и отображения
 Скачать 6.9 Mb.
|
ЛЕКЦИЯ №1 Множества и отображения. Множество – понятие, неопределяемое в математике. Более сложные объѐмы определяются через более простые, поэтому некоторые основные понятия не определяются. Их смысл поясняется на примерах: 1) Множество книг, стоящих на полке 2) Множество букв в слове ―книга‖ 3) Множество всех треугольников на плоскости Множества обычно обозначаются заглавными латинскими буквами Множество состоит из элементов (латинские буквы) Также существует знак принадлежности. Он обозначается развернутой в право буквой ―Э‖ Множество можно задать перечислением элементов М = {a, b, k …} Другой способ задания с помощью свойства, характеризующего элемента множества. N = {x\x – буквы, входящие в слово ―книга‖} Вертикальную черту в создании множества можно рассматривать ―таких, что‖ Множество Aявляется подмножеством множества B, если каждый элемент Aпринадлежит B. Заметим, что множество тоже является своим подмножеством. Множество, в котором нет ни одного элемента, называется пустым. Операции над множествами. Пересечением множеств Aи Bназывается множество, состоящее из элементов, входящих и в A, и в B.A Объединением множеств A и Bназывается множество, состоящее из элементов, которые принадлежат хотя бы одному из множеств A, B. Разностью множеств Aи Bназывают множество тех элементов, которые не входят в B. Дополнением к множеству Aназывается множество, состоящее из элементов, не входящих в A. При этом всегда считается, что подмножества, участвующие в решении данной задачи, являются некоторыми подмножествами некоторого универсального множества U. Наглядно представить операции над множествами можно с помощью диаграмм Эйлера – Венна: Пусть A – множество целых чѐтных чисел, а B–множество целых чисел: 5 В качестве универсального множества рассмотрим множество целых чисел Z Aпересекает B = {xпринадлежитZ| x–чѐтно и : 5} = {xпринадлежит Z| x - : 10} AUB = {xпринадлежит Z| x– чѐтно или :5} = {xпринадлежит Z| x– оканчивается на 0, 2, 4, 6, 8} A \ B = {xпринадлежит Z| x – чѐтно и не делится на 5} = {xпринадлежит A| x– оканчивается на 2, 4, 6, 8} B \ A = {xпринадлежит Z| x - : 5 и нечѐтно} = {xпринадлежит A| x - : 5 и оканчивается на 5} Дополнение A = {xпринадлежит Z| x- нечѐтно} – множество нечѐтных чисел. Декартово произведение – это множество, элементами которого являются все возможные упорядоченные пары элементов исходных множеств. Упорядоченными называют пару элементов, у которых важен порядок элементов. Их ставят в ( ). Если порядок не важен, то в { }. Лекция №2 Отображения Если каждому элементу множества A по некоторому определенному правилу ставится в соответствие единственный элемент из множества B называется отображением или функци- ей множества A в множество B. Эти слова лишь поясняют понятие отображения, но не могут служить его определением. Понятие отображения, как и понятие множества, также является неопределяемым . Тот факт, что отображение f действует из множества A в множество B, обозначают f : A → B. Если отображение ϕ элементу x из A ставит в соответствие элемент y из B, то y называется образом элемента x и обозначается fx или f(x). Также пишут x f −→ y Множество (А) – область отображения (f) – функция Примеры: Пусть (Т) – множество треугольников (S) – множество окружностей S(t) – окружность описанная около треугольника T:T → S Получили отображения соответствующие каждому треугольника описанную около него окружность Отметим . что - для всех квантор всеобщности ∃- квантор существования Любое отображение f:A→B удовлетворяет 2м требованиям для любого B из А можно найти значения f(a)=b a A ∃b B : f(a) = b И значения f(a) определяются единственным образом f(a) : a A f(x) = b , таких что , A(a) = b2 b2→b1=b2 Пример: Покажем, что множество R равномощно множеству точек произвольно выбранного на числовой прямой интервала (a, b), где a 6= b. Действительно, равномощность множеств R и (0, 1) устанавливается, например, взаимно однозначным отображением ϕ(x) = 1 π arcctg x, а равномощность множеств (0, 1) и (a, b) (а так же *0, 1+ и *a, b+) — биекцией ψ(x) = a + (b − a)x Функции ϕ(x) и ψ(x) — строго монотонные и, следовательно, как известно из математического анализа, — взаимно однозначные. g(x) = x^2 График (g) – это подмножество декартовом произведении RxR=R^2 изображение параболы Мощность множества Подведем итог. Мы рассмотрели несколько бесконечных множеств. Оказалось, что |N| = |Z| = |Q| и |R| = |(a, b)|, однако пока не решен вопрос “|N| ?= |R|”. Так как N ⊆ R, то, конечно, |N| ≤ |R|. Скоро мы увидим, что биекции N → R не существует и, таким образом, |N| < |R|. Множества, равномощные множеству натуральных чисел называются счетными, или множествами мощности ℵ0 (читается ‘алеф-0’). Множества, равномощные множеству дей- ствительных чисел называются континуальными (мощности континуума), или множествами мощности ℵ1 (читается ‘алеф-1’). Теорема Кантора Доказательство. Сперва установим равномощность множеств 2 N и *0, 1+. Пусть6 для любого A ∈ 2 N ϕ(A) = (0, α1α2α3 . . .) 2 , где αi = ( 0, если i ∈ A, 1, если i /∈ A . В частности, ϕ(∅) = 0), ϕ(N) = 1). Очевидно, что ϕ — сюръекция, однако, следующие приме- ры: ϕ({1, 3}) = (0, 101(0))2 = 1 2 + 1 8 = 5 8 , ϕ({1, 4, 5, 6, . . .}) = (0, 100(1))2 = 1 2 + 1 16 + 1 32 + . . . = 1 2 + 1 8 = 5 8 — показывают, что ϕ не является инъекцией: двум разным подмножествам множества нату- ральных чисел соответствует одно и то же число, или, что эквивалентно, существует α ∈ [0, 1], обладающее двумя прообразами. Это возможно, если в двоичной системе счисления α пред- ставимо как бесконечная дробь с периодом (1) или (0). Легко видеть, что множество N таких чисел счетно: оно есть объединение счетного числа конечных множеств, состоящих из чисел, период (1) которых начинается с первого, второго и т. д. места после запятой. Счетным яв- ляется также множество M прообразов всех чисел из N (M = x ∈ 2 N : ϕ(x) ∈ N ). Пусть ψ — некоторая биекция из M в N. Скорректируем теперь отображение ϕ. Для любого A ∈ 2 N положим θ(A) = ( ψ(A), если A ∈ M, ϕ(A), если A /∈ M. Легко видеть, что θ — биекция из 2 N в *0, 1+. Так как |*0, 1+| = |R|, то = |R|. |R| > |N| Для множеств с конечным числом элементов, мощность множества является фактически количеством элементов этого множества. Иначе можно сказать, что множество A является конечным , если существует такое натуральное число n, что A {k, k ∈ N ∧ k ≤ n}. В противном случае, множество называется бесконечным. Между двумя конечными множествами A и B существует взаимно однозначное соответствие тогда и только тогда, когда их мощности совпадают, т.е. | A | = | B |. Пусть A = {a 1, a 2, ..., a n} - конечное множество с n элементов (| A | = n), тогда количество всех подмножеств множества A равна 2 n, т.е. 2 | A |. Множество всех подмножеств некоторого множества A (конечной или бесконечной) часто обозначают через β (A) (или B (A) или 2 | A |) и называют Булеан множества A. Очевидно, что для конечного множества A выполняется | B (A) | = 2 | A |. В общем случае, справедливом и для бесконечных множеств, множества A и B является равномощных, или имеют одинаковую мощность, если можно установить взаимно однозначное соответствие между элементами этих множеств, т.е. если существует биекции f: A → B. Равномощных множества обозначаются как A B. Отношение ривнопотужности есть рефлексивным, симметричным и транзитивным, то есть отношением эквивалентности. Для бесконечных множеств мощность множества может совпадать с мощностью ее собственной подмножества. Примеры: Множество натуральных чисел N равномощных множестве S = {1,4,9,16, ...}, состоящая из квадратов натуральных чисел. Необходима биекции устанавливается по закону (n, n 2), n ∈ N, n 2 ∈ S. Множество Z всех целых чисел равномощных множестве P всех четных чисел. Здесь взаимно однозначное соответствие устанавливается следующим образом: (n, 2n), n ∈ Z, 2n ∈ P = |R|. Теперь из теоремы Кантора получаем Утверждение 1.12. |R| > |N| Лекция №4 "Кольцо" Кольцом называется алгебраическая система с двумя двухместными операциями. По аналогии с арифметическими действиями их называют "сложением" и "умножением". Они могут быть заданы различными способами. Важно лишь выполнение определённых свойств. 〈 K; +; • 〉 если выполнены следующие требования (аксиомы кольца): 1. ∀ x,y,z ∈ K (x+y)+z = x+(y+z) - "сложение" ассоциативно (сочетательность) 2. Существует нейтральный элемент 0. ∃ 0 ∈K, x ∈K, x+0=0+x=x, 0 - нейтральный элемент для "сложения". 3. Для ∀x∈K ∃ x∈K, что x+(-x) = 0 . Существует обратный элемент для "сложения". Эти аксиомы показывают, что кольцо относительно операции "сложение" образует группу. 4.Для любых x,y∈K выполняется коммутативность сложения x+y= y+x 5.Для любых x,y,z∈K выполняется ассоциативность относительно умножения - (x•y)•z = x•(y•z) 6.Для любых x,y,z∈K выполняется дистрибутивность умножения относительно сложения. x•(y+z) = x•y + x•z Пример: Z с обычными операциями "Сложение" и "умножение" образует кольцо 〈 Z; +; •〉. Действительно, все условия выполнены, имеет место коммутативность умножения. Поэтому〈 Z; +; •〉коммутативное кольцо x•y = y•x. Существует ещё один важный тип алгебраических систем - поля. Поле - коммутативное кольцо с единицей(нейтральный элемент для умножения), в котором любой не нулевой x имеет обратный x -1 такой, что x•x -1 =1. Другими словами: поле - алгебраическая система 〈 P; +; •〉, в которой выполняются аксиомы кольца(1-6) и кроме того, выполняются условия: 7.Для любых x,y∈P x•y = y•x - умножение коммутативно. 8.Существует 1 - нейтральный элемент относительно умножения. ∃1 элемент такой, что ∀ x∈P выполняется x• 1 = x. 9.Любой элемент отличный от нуля имеет обратный элемент. ∀ x≠0 ∃ x -1 ∈P x•x -1 =1 Пример: R с обычными операциями: умножение и сложение чисел, образует поле, так как все аксиомы поля выполнены. Пример: 〈 Z; +; •〉 не является полем. Это кольцо коммутативно и имеет единицу(т.е. выполнены восемьаксиом кроме девятой). Не для всех чисел существует обратный элемент: 2•x ≠ 1 т.к. для 2 нет обратного элемента для умножения. Метод математической индукции. Как известно: математические утверждения т.е. теоремы должны быть доказаны. Метод математической индукции является одним из методов доказательств. В широком смысле индукция - это способ рассуждений, позволяющий переходить от частных утверждений к общим. Обратный переход от общих утверждений к частным называется дедукцией. Дедукция всегда приводит кправильным выводам. Пример: Общий результат: все числа, оканчивающиеся на 0 делятся на 5. ⇒ Частное любое конкретное число, оканчивающееся на 0 делится на 5. В тоже время индукция может привести к неверным выводам. Заметим: 60 делится на 1, 2, 3, 4, 5, 6, можем сделать вывод, что 60 делится на любое число. Метод математической индукции позволяет во многих случаях строго доказать справедливость общего утверждения P(n), в формулировку которого входит натуральное число n. Применение метода включает три этапа: 1.База индукции: проверяем справедливость утверждения P(n) для n=1 или для другого частного значения n, начиная с которого предполагается справедливость P(n). 2.Предположение индукции: предполагаем, что P(n) справедливость для n=k ≠1. 3.Шаг индукции: используя предположение, доказываем, что P(n) справедливо для n=k+1. В результате можно сделать вывод о справедливости P(n) для любого n натурального. 1)P(n) для n=1 2)P(n) для n=k 3)P(n) для n=k+1 P(n) ∀n ∈N Действительно для n=1 P(n) - справедливо, согласно базе индукции ⇒ всё верно и для n=2 , т.к. переход от n=1 кn=2 обоснован (шаг индукции). Применяя шаг индукции снова, получаем справедливость P(n) для n= 3,4,5... ,т.е. справедливость P(n) для всех n Пример: Сумма первых n – нечётных натуральных чисел равна n 2 (1+3+5... +(2n- 1)=n 2 ). Доказательство проведём методом математической индукции. 1)База при n=1. Слева только одно слагаемое 1=1. 2)Предположение: полагаем, что для некоторого k: 1+3+5... +(2k-1)=k 2 3)Шаг индукции: докажем, что утверждение верно для n=k+1, т.е. 1+3+5...+(2k-1) +(2k+1) = (k+1) 2 Учитывая предположение, сумма первых k слагаемых равна k 2 , значит то, что требуется доказать можно записать так : k 2 +(2k+1) = (k+1) 2 очевидно. ЧТД. Лекция №5 Комплексные числа Комплексным числом называется любое выражение вида, где x, y, e, r, i – мнимая единица со свойствами i 2 = -1, Выражение 1 – это алгебраическая формула комплексного числа Сумма и разность двух комплексных чисел определяется путем операций с их действительными и мнимыми частями. Для определения произведения комплексных чисел сначала определим квадрат мнимой единицы: i 2 =1, а затем - произведение двух произвольных комплексных чисел z 1 = x 1 + y 1 i и z 2 = x 2 + y 2 i как результат почленного умножения z 1 = x 1 + y 1 i на z 2 = x 2 + y 2 i с использованием соотношения i 2 = -1 и последующего сложения полученных результатов: z 1 z 2 = (x 1 + y 1 i)(x 2 + y 2 i) = x 1 x 2 + y 1 x 2 i + x 1 y 2 i + y 1 y 2 i 2 = (x 1 x 2 - y 1 y 2 ) + (x 1 y 2 +x 2 y 1 )i. Любое комплексное число может быть записано в виде: z = r (cos + isin ) r= =arctgy/x x=rcos , y=rsin Если n принадлежит N, то z^n=(r^n)(cos +isin ) при этом W(n)= корень n- ой степени из Z= (корень n-ой степени из r)(cos( +2пk/n) +isin( +2пk/n), k=1,2,3… Т.е. имеется n различных корней. i=корень квадратный из -1, i^2=-1 Z=x+iy x-действительная часть, у- мнимая часть. Правила 1. (a + ib) + (c + id) (x(1) + iy(1)) + ((x(2) + iy(2)) = x(1 )+ x(2) + i(y(1) + y(2)). 2. Z(1)+Z(2)=(x(1)+iy(1))*(x(2)+iy(2))=x(1)x(2)-y(1)y(2)+i(x(1)y(2)+x(2)y(1)). 3. Z(1)/Z(2)= Лекция 6 Математическая логика. Высказывание- некоторое осмысленное выражение языка, т.е. выражение языка о котором имеет смысл говорить истинно оно или ложно, т.е. верно оно или не верно. И- истинно, Л-ложно, S- четное число (Л). При этом предполагаем, что высказывание удовлетворяет закону исключенного третьего и закону противоречия, т.е. каждое высказывание или истинно или ложно. Высказывание не может быть истинным и ложным. Понятно, что истинные и ложные высказывания образуют соответствующие множества. С помощью простых высказываний можно составлять более сложные, соединяя простые высказывания союзами ―и‖, ―или‖. Таким образом, операции с высказываниями можно описывать с помощью некоторого математического аппарата. Вводятся следующие логические операции (связки) над высказываниями 1) Отрицание. Отрицанием (логическим ―не‖) высказывания Р называется высказывание, которое истинно только тогда, когда высказывание Р ложно. Обозначается Р или Соответствие между высказываниями определяется таблицами истинности. В нашем случае эта таблица имеет вид: P Р И Л Л И 2) Конъюнкция. Конъюнкцией (логическим ―и‖) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания. Обозначается P&Q или РÜQ. P Q P&Q И И И И Л Л Л И Л Л Л Л 3) Дизъюнкция. Дизъюнкцией (логическим ―или‖) двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны. Обозначается PÚQ. P Q PÚQ И И И И Л И Л И И Л Л Л 4) Импликация. Импликацией (логическим следованием) двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда высказывание Р истинно, а Q – ложно. Обозначается PÉQ (или РÞQ). Высказывание Р называется посылкой импликации, а высказывание Q – следствием. P Q PÞQ И И И И Л Л Л И И Л Л И 5) Эквиваленция. Эквиваленцией (логической равносильностью) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинности высказываний совпадают. Обозначается РQ или РÛQ. P Q PQ И И И И Л Л Л И Л Л Л И С помощью этих основных таблиц истинности можно составлять таблицы истинности сложных формул. Запись можно рассматривать как обозначение бинарной операции умножения переменных и , а, с другой стороны, так же обозначается функция двух переменных Пример 1. С помощью таблиц истинности проверить, являются ли эквивалентными формулы j и y. Составим таблицы истинности для каждой формулы: p r (pÜr) И И Л И И И Л Л Л И Л И И Л Л Л Л И Л Л p r И И Л Л Л И И Л Л И И И Л И И Л И И Л Л И И И И Данные формулы не являются эквивалентными. |