Лекция 1. Элементы дискретной математики. Кафедра высшей математики 31 августа 2020 г
 Скачать 367.67 Kb.
|
|
Элементы дискретной математики Множества 1 Теория множеств является одной из сравнительно молодых математических дисциплин. Основоположником еј считает- ся немецкий математик Георг Кантор (18451918). В основе этой теории лежит понятие множества. Согласно Г. Кантору, ѕмножество есть многое, мыслимое нами как единоеї. Другими словами, множество это совокупность предме- тов, рассматриваемая как один предмет. Это не является определением множества, а всего лишь поясняет его. Мно- жество самое широкое понятие математики, оно не может быть определено через другие, более простые понятия. 2 Обозначения Произвольные множества : A, B, C, D, . . .; пустое множество символом ?. Элементы множества: a, b, c, d, . . . или a 1 , a 2 , . . . , a n , a n+1 , . . . Отношение между элементами и множеством выражают сло- вами ѕявляется элементомї или ѕпринадлежитї. Предло- жение ѕЭлемент a принадлежит множеству Aї запишем с использованием символа: ? (a ? A). Если же a не является элементом множества A, то будем писать a /? A. 3 Обозначения наиболее часто используемых числовых множеств N множество натуральных чисел N 0 множество целых неотрицательных чисел (или Z + ) Z множество целых чисел Q множество рациональных чисел R множество действительных чисел R + множество неотрицательных действительных чисел R ? множество неположительных действительных чисел 4 Способы задания множеств Множество считается заданным, если о любом объекте мож- но сказать, принадлежит он этому множеству или не принад- лежит. Перечислением всех его элементов в произвольном порядке. Например, если множество A состоит из однозначных нечјт- ных чисел, то запишем: A = {1, 3, 5, 7, 9} . Это множество можно записать и так: A = {3, 5, 1, 9, 7} или A = {9, 7, 1, 3, 5}, или с перечислением элементов в каком-то другом порядке. Следует отличать символы a и {a} . Так, a обозначает эле- мент множества, {a} одноэлементное множество. 5 Задания множества через указание характеристического свой- ства его элементов. Определение 1 . Характеристическим свойством, определя- ющим множество, называется такое свойство, которым об- ладает каждый элемент, принадлежащий данному множеству, и не обладает ни один элемент, ему не принадлежащий. Множество B, определяемое некоторым характеристическим свойством P , будем обозначать: B = {x|P (x)} ; эта запись чи- тается так: ѕB есть множество всех x таких, что x обладает свойством P ї, или ѕB есть множество всех x , обладающих свойством P ї. 6 Например, запись B = {x|x ? Z, ?2 ? x < 3} означает, что множество B состоит из целых чисел, больших или равных ?2 и меньших 3, а множество корней уравнения 2z 2 ?z ?3 = 0 можно описать как: C = {z|2z 2 ? z ? 3 = 0} Часто одно и то же множество может задаваться обоими способами. Например, заданные выше с помощью характе- ристического свойства множества B и C могут быть заданы и перечислением: B = {?2, ?1, 0, 1, 2}, C = {?1, 3/2}. 7 Отношения между множествами Диаграммы ЭйлераВенна Пусть даны два произвольных множества A и B. Рассматри- вая вопрос об отношениях между ними, необходимо прежде всего отметить две возможности. I. Множества A и B не имеют общих элементов, то есть из того, что x ? A, следует, что x /? B , а из того, что y ? B, сле- дует, что y /? A. На диаграммах ЭйлераВенна нет элементов, которые принадлежали бы одновременно A и B II. Множества A и B имеют общие элементы, то есть суще- ствуют такие элементы x, для которых верно то, что x ? A и x ? B 8 1. Не все элементы множества A принадлежат множеству B, и не все элементы множества B принадлежат множеству A . В этом случае говорят, что множества A и B находятся в отношении пересечения. 9 Примеры множеств, находящихся в отношении пересечения: а) A = {п, и, о, н, е, р}; B = {у, ч, е, н, и, к}; б) A множество натуральных делителей числа 72; B множество натуральных делителей числа 85. 10 2. Все элементы множества A принадлежат множеству B , но множество B может содержать элементы, не принад- лежащие множеству A. В этом случае говорят, что мно- жества A и B находятся в отношении включения. На диа- грамме ЭйлераВенна каждая точка множества A нахо- дится внутри фигуры, изображающей множество B (рис. в) Например, A множество чисел, кратных четырјм, и B множество чисел, кратных двум, находятся в отношении вклю- чения. 11 Определение 2 . Множество A называется подмножеством (или частью) множества B, если каждый элемент множества A является элементом множества B. Обозначают включение символом ?: A ? B и читают ѕA включается в Bї или ѕA подмножество Bї. 12 Свойства отношения включения: 1) рефлексивность: A ? A , то есть всякое множество вклю- чается в себя, или всякое множество является подмно- жеством самого себя; 2) транзитивность: из того что A ? B и B ? C, следует, что A ? C ; 3) для всякого множества A справедливо включение ? ? A. Поскольку ? не имеет элементов, то естественно считать его подмножеством любого множества. 13 Само множество A и пустое множество ? называют несоб- ственными подмножествами множества A. Все остальные под- множества множества A называются собственными. 3. Все элементы множества B принадлежат множеству A, но множество A может содержать элементы, не принадлежа- щие множеству B. В этом случае множество B включает- ся во множество A . Диаграмма ЭйлераВенна для такого варианта включения представлена на рис. г. 14 4. Все элементы множества A принадлежат множеству B, и все элементы множества B принадлежат множеству A. В этом случае говорят, что множества A и B равны. Определение 3 . Два множества A и B называются равными или совпадающими, если A ? B и B ? A. Равенство множеств обозначают символом = (A = B), и чи- тают ѕA равно Bї. На диаграмме ЭйлераВенна контуры множеств A и B совпадают (рис. д). 15 Пусть, например, A множество гласных букв в слове ѕбе- локї, B множество гласных букв в слове ѕпрогрессї. Оче- видно, что множества A = {е, о} и B = {о, е} равны между собой. Можно дать и другое определение равенства множеств. Определение 4 . Два множества A и B называются равны- ми, если они состоят из одних и тех же элементов. 16 Отношение равенства множеств обладает следующими свой- ствами: 1) рефлексивностью: A = A, то есть всякое множество рав- но самому себе; 2) симметричностью: если A = B, то и B = A; 3) транзитивностью: если A = B и B = C, то A = C. 17 Определение 5 . Множество, относительно которого все мно- жества, рассматриваемые в данной задаче, являются под- множествами, называется универсальным. Например, множество действительных чисел R является уни- версальным для рассмотренных выше числовых множеств. Универсальное множество будем обозначать буквой U, а на диаграммах ЭйлераВенна в виде прямоугольника (рис. е). 18 Отношение между числовыми множествами N ? Z ? Q ? R ? C 19 Операции над множествами Объединение множеств Дано: A = {15, 30, 45, 60, 75, 90} множество двузначных чи- сел, кратных 15; B = {18, 36, 54, 72, 90} множество двузнач- ных чисел, кратных 18. Образуем новое множество, состоящее из элементов этих множеств. Полученное множество {15, 18, 30, 36, 45, 60, 72, 75, 90} называется объединением множеств A и B . Число 90 за- писали один раз, поскольку элементы множеств не должны повторяться. 20 Определение 6 . Объединением множеств A и B называется множество, состоящее из тех и только тех элементов, кото- рые принадлежат множеству A или множеству B. Союз ѕилиї здесь не выполняет разделительную функцию. Другими словами, если элемент принадлежит объединению множеств, то он принадлежит или A, или B, или обоим мно- жествам одновременно. 21 Обозначают объединение множеств A и B символом ?: A ? B . Аналогично определяется объединение трјх и более мно- жеств. Определение объединения можно записать в таком виде: A ? B := {x|x ? A или x ? B}. На рис. объединению со- ответствует заштрихованная часть. На рис. б B ? A; поэтому A ? B = A 22 Пересечение множеств Пусть имеем два множества: A = {1, 2, 3, 4, 6, 12} множе- ство натуральных делителей числа 12; B = {1, 3, 6, 9, 18} множество натуральных делителей числа 18. Образуем множество, состоящее из общих элементов мно- жеств A и B. Вновь полученное множество {1, 3, 6} называют пересечением множеств A и B. 23 Определение 7 . Пересечением множеств A и B называется множество, состоящее из тех и только тех элементов, кото- рые принадлежат множеству A и множеству B одновременно. Пересечение множеств A и B обозначают символом ?: A ? B . Аналогично определяется пересечение трјх и более мно- жеств. Определение пересечения можно записать в таком ви- де: A ? B := {x|x ? A и x ? B}. Как следует из определения пересечения, x ? A ? B тогда и только тогда, когда x ? A и x ? B. Соответственно, x /? A ? B тогда и только тогда, когда x /? A или x /? B. 24 Если множества A и B изобразить с использованием диа- грамм ЭйлераВенна, то пересечению будет соответствовать заштрихованная часть. На рис. б B ? A, поэтому A ? B = B. На рис. в A ? B = ?. 25 Свойства объединения и пересечения множеств 1. A ? B = B ? A коммутативность объединения. 2. A ? B = B ? A коммутативность пересечения. 3. A ? (B ? C) = (A ? B) ? C ассоциативность объединения. 4. A ? (B ? C) = (A ? B) ? C ассоциативность пересечения. 5. A ? (B ? C) = (A ? B) ? (A ? C) дистрибутивность пересе- чения относительно объединения. 6. A ? (B ? C) = (A ? B) ? (A ? C) дистрибутивность объеди- нения относительно пересечения. 26 7. A ? A = A. 8. A ? A = A. 9. A ? ? = A. 10. A ? ? = ?. 11. A ? U = U. 12 A ? U = A. Свойства 712 называются законами поглощения. 27 Разность двух множеств. Дополнение Пусть A множество равнобедренных треугольников, B множество треугольников, не имеющих прямого угла. То- гда множество равнобедренных прямоугольных треугольни- ков состоит из тех и только тех элементов множества A, которые не принадлежат множеству B. Это множество назы- вается разностью множеств A и B. 28 Определение 8 . Разностью множеств A и B называется множество, состоящее из тех и только тех элементов мно- жества A, которые не принадлежат множеству B. Разность множеств A и B обозначают символом \. A \ B : читается ѕA без Bї. Определение разности можно записать в таком виде: A \ B := {x|x ? A и x /? B}. Операция, при помощи которой находится разность множеств, называется вычитанием. 29 Если B ? A, то разность A \ B называется дополнением мно- жества B до множества A. Обозначают дополнение символом B A Если множество B является подмножеством универсального множества U, то дополнение B до U обозначается B. Итак, по определению, B = U \ B. Из этого определения следует, что x ? B тогда и только то- гда, когда x /? B, и x /? B тогда и только тогда, когда x ? B. 30 Замечания. В некоторых случаях удобно рассматривать сим- метричную разность двух множеств A и B, которая опреде- ляется как объединение разностей A \ B и B \ A. Симмет- ричную разность множеств A и B будем обозначать симво- лом ч; A ч B (или A4B). Таким образом, по определению, A ч B = (A \ B) ? (B \ A) Последовательность выполнения операций над множествами (операции даны по убыванию приоритетов): A, A \ B, A ? B, A ? B , A ч B. 31 Свойства разности и дополнения Разность не обладает свойствами коммутативности и ассо- циативности, то есть A \ B 6= B \ A; A \ (B \ C) 6= (A \ B) \ C. 1. ? = U. 2. U = ?. 3. A \ ? = A. 4. A = A. 5. A ? A = ?. 6. A ? A = U. 7. A ? B = A ? B. 8. A ? B = A ? B. 9. A \ (B ? C) = (A \ B) ? (A \ C). 10. A \ (B ? C) = (A \ B) ? (A \ C). 32 Декартово произведение множеств Пусть имеем число 46, записанное с помощью цифр 4 и 6. Цифры в числе расположены в определјнном порядке. Если их поменять местами, то получится другое число 64. Говорят, что 4, 6 упорядоченная пара цифр. В общем случае под упорядоченной парой будем понимать два элемента, расположенные в определјнном порядке. Упо- рядоченную пару с первым элементом a и вторым элементом b обозначим (a, b). Элементы a и b пары называют еј компо- нентами. Две пары (a 1 , b 1 ) и (a 2 , b 2 ) считаются равными тогда и только тогда, когда a 1 = a 2 и b 1 = b 2 . В общем случае, ес- ли a 6= b , то (a, b) 6= (b, a), то есть две пары, отличающиеся только порядком расположения элементов, будут различны. 33 Упорядоченные пары можно образовать и из элементов двух различных множеств. Пусть A = {t, p}; B = {a, o, e}. Составим всевозможные пары, первые элементы которых принадлежат множеству A, а вторые множеству B. Получим множество {(t, a), (t, o), (t, e), (p, a), (p, o), (p, e)}, кото- рое называют декартовым (или прямым) произведением мно- жеств A и B. 34 Определение 9 . Декартовым произведением двух непустых множеств A и B называется множество, состоящее из всех упорядоченных пар вида (a, b), где a ? A и b ? B. Декартово произведение множеств A и B обозначают сим- волом Ч, A Ч B. Приведјнное определение можно записать короче: A Ч B = {(a, b)|a ? A и b ? B}. Декартово произведение A Ч A называют декартовым квад- ратом множества A и обозначают A 2 Операция, с помощью которой находится декартово произ- ведение множеств, называется декартовым умножением. Декартово умножения не обладает свойствами коммутатив- ности и ассоциативности. 35 Свойства декартова произведения 1. Если A 6= B, то A Ч B 6= B Ч A. 2. Если ни одно из множеств A, B и C не является пустым, то A Ч (B Ч C) 6= (A Ч B) Ч C. 3. A Ч (B ? C) = (A Ч B) ? (A Ч C). 4. (A ? B) Ч C = (A Ч C) ? (B Ч C). 5. A Ч (B ? C) = (A Ч B) ? (A Ч C). 6. (A ? B) Ч C = (A Ч C) ? (B Ч C). 7. A Ч (B \ C) = (A Ч B) \ (A Ч C). 8. (A \ B) Ч C = (A Ч C) \ (B Ч C). 36 Понятие упорядоченной пары естественным образом распро- страняется на наборы из n элементов. Под упорядоченной n -кой (читается ѕэнкаї) будем понимать n элементов, рас- положенных в определјнном порядке. Обозначают n-ку сим- волом (a 1 , a 2 , . . . , a n ) и называют кортежем длины n. Определение 10 . Декартовым произведением непустых мно- жеств A 1 , A 2 , . . . , A n называется множество всевозможных кортежей длины n, первая компонента которых принадлежит множеству A 1 , вторая множеству A 2 , . . . , n-я множеству A n Декартово произведение множеств A 1 , A 2 , . . . , A n обозначают A 1 Ч A 2 Ч . . . Ч A n 37 R Ч R = R 2 множество точек плоскости. RЧRЧR = R 3 множество точек трјхмерного пространства. R Ч R Ч R . . . Ч R = R n множество точек n-мерного простран- ства. 38 Бинарные отношения Определение 11 . Бинарным отношением (соответствием) между множествами A и B называется любое подмножество F декартова произведения A на B. F бинарное отношение ?? F ? A Ч B Для бинарного соответствия P ? X Ч Y множество X на- зывают областью отправления, множество Y областью прибытия, а множество P графиком соответствия ?. Ес- ли (x, y) ? P , то говорят, что при соответствии ? элементу x соответствует элемент y, и записывают: x ? y. 39 Пусть даны два непустых множества X и Y . Определение 12 . Соответствие f, которое каждому элемен- ту x ? X сопоставляет один и только один элемент y ? Y на- зывается функцией и записывается y = f(x), x ? X : X ? Y. f отображает множество X на множество Y . X область определения функции f: D(f). Y множество значений функции f: E(f). Если X и Y числовые множества, то f числовая функ- ция. В этом случае x аргумент или независимая перемен- ная, а y функция или зависимая переменная. 40 Элементы математической логики Логика наука, изучающая понятия с формальной точки зрения: методы их определения и преобразования, суждения о них и структуры доказательных рассуждений. Исследования в логике тесно связаны с изучением ѕвыска- зыванийї. С помощью высказываний устанавливаются свой- ства, взаимосвязи между объектами. Высказывание истинно, если оно адекватно отображает эту связь, в противополож- ном случае оно ложно. Определение 13 . Высказывание повествовательное пред- ложение (утверждение об объектах), имеющее однозначный, точно определенный смысл, о котором можно говорить: оно истинно или ложно. 41 Это определение не математическое. С чисто математиче- ской точки зрения понятия высказывания и объекта явля- ются исходными. Определение 14 . Высказывание называется простым (эле- ментарным,атомарным), если никакая его часть не является высказыванием. Сложные высказывания образуют из простых применением трех видов операций. 42 1. Логические связки применяются к высказываниям, в ре- зультате образуют новое высказывание. Например: ѕнеї, ѕилиї, ѕне только . . . , но и . . . ї и др. 2. Модальности применяются к высказываниям и изменяют наше отношение к ним. Например: ѕпо сведениям Западно-Сибирского гидрометцен- тра . . . ї, ѕМаша сказала, что . . . ї и др. 3. Кванторные конструкции применяются к совокупности однородных (отличающихся лишь значениями некоторых па- раметров) высказываний либо выражений и дают единое вы- сказывание либо выражение, которые не зависят от упомя- нутых выше параметров. Например: ѕбольшинство. . . ї, ѕвсе. . . ї, ѕнайдется. . . ї и др. 43 Логические связки Для обозначения высказываний обычно используются про- писные или строчные буквы латинского алфавита: A, B, C, X , Y , p, q, r, s, t и др. Составные высказывания получаются из простых при помощи так называемых логических свя- зок (операций): НЕ (отрицание), И (конъюнкция), ИЛИ (дизъюнкция), СЛЕ- ДУЕТ (импликация), ТОГДА И ТОЛЬКО ТОГДА, КОГДА (эквивалентность). 44 A A 0 1 1 0 A B A ? B A ? B A ? B A ? B 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 1 1 1 45 Кванторные конструкции Квантор общее название для логических операций, ограни- чивающих область истинности какого-либо предиката и со- здающих высказывание. Символ ? для квантора всеобщности введјн Герхардом Ген- ценом ? в 1935 году по аналогии с символом квантора суще- ствования ?, введјнным Джузеппе Пеано † в 1897 году. ? Герхард Карл Эрих Генцен немецкий математик и логик, 24 ноября 1909 4 августа 1945 † Джузеппе Пеано 27 августа 1858 20 апреля 1932 итальянский математик 46 ДЛЯ ВСЕХ Утверждение ѕдля всех x верно A(x)ї символически записы- вается ?xA(x). Символ ? называется квантором всеобщно- сти. Эта же связка используется при переводе утверждений: ѕA верно при любом значении xї, ѕдля произвольного x име- ет место A(x)ї, ѕкаково бы ни было x, справедливо A(x)ї и т. п. Утверждение ?xA(x) истинно ттт A(x) истинно при любом фиксированном значении x. Утверждение ?xA(x) ложно ттт имеется хотя бы одно кон- кретное значение x, такое, что A(x) ложно. 47 Определение же истинностного значения формулы ?xA(x) не всегда сводится к простому вычислению. Например, при данных конкретных натуральных x, y, z, n утвер- ждение x n+2 + y n+2 6= z n+2 можно проверить простым вы- числением, а проблема, верно или неверно на множестве N утверждение ?x ?y ?z ?n(x n+2 + y n+2 6= z n+2 ) . Эта проблема известна под названием великой теоремы Ферма ? . На обыч- ном математическом языке она формулируется следующим образом: уравнение x n + y n = z n при n > 2 не имеет решений в положительных целых числах. ? В общем виде теорема была сформулирована Пьером Ферма в 1637 году на полях ѕАрифметикиї Диофанта. Доказана в 1994 году Эндрю Уайлсом с коллегами (доказательство опубликовано в 1995 году). 48 СУЩЕСТВУЕТ Утверждение ѕсуществует такое x, что A(x)ї записывается на языке математики как ?xA(x). Знак ? называется кван- тором существования. Эта же запись применяется при пе- реводе утверждений: ѕA(x) верно при некоторых xї, ѕA(x) иногда верної, ѕесть такое x, при котором A(x)ї, ѕможно найти такое x, при котором A(x)ї и т. п. Высказывание ?xA(x) истинно, если в нашем универсе най- дется хотя бы одно значение c, при котором A(c) истинно. ?xA(x) ложно, если при любом значении c ложно A(c). 49 Нахождение истинностного значения ?xA(x) также может со- ставлять проблему. Например, натуральное число n называ- ется совершенным, если сумма его делителей (исключая са- мо n) равна n. Например: 6 совершенное число, т. к. 6 = 1 + 2 + 3; 28 также совершенное число, т. к. 28 = 1 + 2 + 4 + 7 + 14. Яс- но, что при данном n проверка условия ѕn совершенное числої является чисто механическим процессом; ее можно поручить компьютеру. Но проблема ѕсуществует ли нечетное совершенное число?ї стоит уже более 2000 лет, и пока нет способа ее решения. 50 Пример определения, записанного с помощью кванторных конструкций Число A называется пределом последовательности {x n } , ес- ли для любого положительного числа ? найдјтся такое на- туральное числ n 0 = n 0 (?) , что при всех n > n 0 выполняется неравенство: |x n ? A| < ? , lim n?? x n = A (A : ?? > 0 ? n 0 ? N : ?n > n 0 ? |x n ? A| < ? ? lim n?? x n = A.) 51 |