Лекции Русакова, страница 2

2759.04. Установка необходимого программного обеспечения. ........... 2809.05. Замечания. ..................................................................................... 2819.06. Методический пример. ................................................................ 2839.07. Контрольная распечатка. ............................................................. 2849.08. Отчет по практической работе. .................................................. 2859.09. Контрольные вопросы. ................................................................ 2859.10. Варианты заданий.

....................................................................... 285Глава 10. Дополнительные материалы. .................................................. 28710.01. Биография Георга Кантора (основатель теории множеств). . 28710.02. Город Калининград (Кёнигсберг). ........................................... 288Глава 11. Список литературы.

................................................................. 2905Введение.Дискретная математика — часть математики, которая зародилась вглубокой древности. В широком смысле этого слова к дискретнойматематике относятся как классические разделы математики: алгебра, теориячисел, теория множеств, математическая логика и т.д., так и новые разделы,которые возникли в середине прошлого столетия в связи с внедрением ЭВМв практическую жизнь. В настоящее время понятие «дискретная математика»употребляется в узком смысле только для тех разделов современнойматематики, которые связаны с областью компьютерной науки.

К нимотносятся:1. Теория множеств.2. Теория графов.3. Теория автоматов.4. Теория формальных грамматик.5. Теория булевых функций (переключательные функции).6. Комбинаторика и другие разделы современной «компьютерной»математики.Сегоднядискретнаяматематикаявляетсяважнымзвеномматематического образования. Умение пользоваться «математическимиаппаратами»дискретнойматематикиявляетсяобязательнымквалификационным требованием к специалистам в области информационныхтехнологий.Глава 1. Теория множеств.1.01. Понятие множества. Операции над множествами.В математике встречаются самые разнообразные множества.

Можноговорить о множествах граней многогранника, точек, чисел и т.д.Теория множеств, возникшая в конце XIX века, оказала и продолжаетоказывать большое влияние на всю математику в целом.По определению Георга Кантора (биография приведена в разделедополнительные сведения), основоположника теории множеств, множествоесть любое собрание определенных и различимых между собой объектовнашей интуиции или интеллекта, мыслимое нами как единое целое.

Междуотдельнымиобъектамиимножествамисуществуетотношениепринадлежности. Как правило, множества обозначают прописными буквами,а их элементы — малыми, которые перечисляются внутри фигурных скобокчерез запятую {}.Определение.Утверждение "элемент a принадлежит множеству A " символическизаписывается так: a ∈ A илиA ∈ a , a "элемент b не принадлежитмножеству A " записывается так: b ∉ A или A ∉ b .Определение.Если все элементы, из которых состоит A , входят и в B , причемслучай A = B не исключается, то A называется подмножеством B .Записывается это так: A ⊂ B .Например, целые числа образуют подмножество в множестведействительных чисел.7Иногда не известно заранее, содержит ли некое множество, например,множество действительных корней данного уравнения, хотя бы одинэлемент.

Поэтому целесообразно ввести понятие пустого множества.Определение.Множество, не содержащее ни одного элемента, называется пустыммножеством. Его обозначают символом ∅.Следствие из определения.Любое множество содержит в качестве подмножества множество ∅.Определение.Подмножества множества, отличные от него самого и от ∅,называются собственными.Определение.Пусть A и B — множества.

Тогда их суммой или объединениемC = A  B называетсямножество,состоящееизвсехэлементов,принадлежащих хотя бы одному из множеств A или B .BAРис. 1.1. C = A  B .Аналогично определяется сумма любого (конечного или бесконечного)числа множеств, а именно:если Aα — произвольное множество, то их сумма  Aα — естьαсовокупность элементов, каждый из которых принадлежит хотя бы одномуиз множеств Aα .Определение.8Пересечением C = A  B множеств A и B называется множество,состоящее из всех элементов, принадлежащих как A , так и B .Пересечением любого (конечного или бесконечного) числа множествAα называется совокупность  Aα элементов, принадлежащих каждому изαмножеств Aα .BAРис. 1.2. C = A ∩ B .Пример.Пересечение множества всех четных чисел и множества чисел,делящихся на три, состоит из всех целых чисел, делящихся без остатка нашесть.1.02.

Свойства операций сложения и пересечениямножеств.A  B = B  A.– коммутативностьA  B = B  A.( A  B)  C = A  ( B  C ) .– ассоциативность( A  B)  C = A  ( B  C ) .( A  B)  C = ( A  C )  ( B  C ) .– взаимная( A  B)  C = ( A  C )  ( B  C ) .дистрибутивностьСвойства 1. – 4. выполняются по определению.Докажем свойство 5, то есть что ( A  B)  C = ( A  C )  ( B  C ) .9Пусть х ∈ ( A  B)  C .

Это означает, что х ∈ С и принадлежит покрайней мере одному из множеств А или В. Но тогда х ∈ A  C или B  C ,то есть х ∈ множеству, записанному в правой части равенства 5.Докажем обратное,то есть пусть х ∈ ( A  C )  ( B  C ) . Тогдах ∈ A  C или х ∈ B  C ⇒ х ∈ С, а также х ∈ А или х ∈ В, то есть х ∈ A  B⇒ х ∈ ( A  B)  C ,то есть х ∈ множеству, записанному в левой частиравенства 5. Таким образом, равенство 5 доказано.Определение.Разность множеств А и В, обозначаемая как С = А \ В, – этосовокупность тех элементов из А, которые не содержатся в В.ABРис.

1.3. С = А \ В.Замечание.1. При определении разности А \ В, вообще говоря, не предполагается, чтоА ⊃ В.2. Иногда вместо А \ В пишут А – В.Определение.Симметрическая разность двух множеств А и В – это сумма разностейА \ В и В \ А, то естьA∆B = ( A \ B )  ( B \ A) .10Рис. 1.4. С = А ∆ В.Замечание.Название “симметрическая разность” для операции A∆B не совсемудачна. Операция A∆B во многом аналогична операции взятия суммыA  B .

Действительно, A  B означает, что связываются неисключающимили два утверждения: “элемент ∈ А” и “элемент ∈ В”, а А∆В означает, чтоэти же два утверждения связываются исключающим или,то есть х ∈А∆В ⇔ х ∈ либо только А, либо только В.Множество А∆В можно было бы назвать “суммой по модулю два”множеств А и В,то есть берётся объединение этих двух множеств, ноэлементы, которые при этом встречаются дважды, выбрасываются.Определение.Пусть S и А – множества, при этом A ⊂ S.

Запас подмножеств S \ Аназывается дополнением множества А и обозначается СА или A ′ ( A ).1.03. Принцип двойственности в теории множеств.1. Дополнение суммы равно пересечению дополнений:S \  Aα =  ( S \ Aα ) .α(1)α2. Дополнение пересечений равно сумме дополнений:S \  Aα =  ( S \ Aα ) .α(2)αДокажем, например, соотношение 1.11Пусть x ∈ S \  Aα . Это означает, что x ∉  Aα , то есть х ∉ Aα для ∀ ααα⇒ х ∈ S \ Aα для ∀α ⇒ x ∈  ( S \ Aα ) .αОбратно, пусть х ∈ ( S \ Aα ) ,αто есть х ∈ S \ Aα, ∀α ⇒ х ∉ Aα для ∀α⇒ x ∉  Aα ⇒ x ∈ S \  Aα .ααТаким образом, равенство 1 доказано.1.04. Отображения множеств.Определение.Пусть M и N – два произвольных множества. Если каждому элементух ∈ M поставлен в соответствие один и только один элемент y ∈ N, тоговорят, что на M определена функция ƒ, принимающая значения из N, тоесть ƒ: M → N.ƒMxNyРис.

ƒ: M → N.Замечания.Для множеств произвольной природы часто вместо термина “функция”используется термин “отображение”.При специализации природы множеств M и N возникают специальныетипы функций, которые носят особые названия: “вектор-функция”, “мера”,“функционал”, “оператор” и т.д.Определение.12Пусть а ∈ M, ƒ: M → N. Тогда элемент b = ƒ(а) ∈ N называется образомэлемента а при отображении ƒ.Определение.Совокупность всех тех элементов а из M, образом которых приотображении ƒ является данный элемент b ∈ N, называется прообразом(полным прообразом) элемента b и обозначается ƒ–1(b).Определение.Пусть А, M, N – множества; ƒ: M → N; А ⊂ M.

Тогда совокупность{ƒ(a) | a ∈ A} всех элементов вида ƒ(а), где а ∈ А, называется образом А иобозначается ƒ(А).Определение.ПустьM, N, B – множества,B ⊂ N,ƒ: M → N.Тогда совокупность {ƒ–1(b) | b ∈ B} всех тех элементов из М, образыкоторых принадлежат В называется (полным) прообразом ƒ–1(В) множестваВ при отображении ƒ.Замечание.Может оказаться, что ни один элемент b ∈ B не имеет непустогопрообраза, тогда и прообраз ƒ–1(В) будет пустым множеством ∅.Определение.Отображение ƒ: М → N есть отображение “на” множество N илисюръекция, если ƒ(М) = N.Определение.Отображение ƒ: М → N есть отображение множества М “в” множествоN, если ƒ(М) ⊂ N.13Определение.Пусть ƒ: М → N – отображение множества М “в” множество N, то естьƒ(М) ⊂ N.Если при х1 ≠ х2, где х1 ∈ М, х2 ∈ М, образы y1 = ƒ(х1) и y2 = ƒ(х2)различны, то есть y1 ≠ y2, то ƒ называется инъекцией.Определение.Отображение ƒ: М → N, которое одновременно является и сюръекциейи инъекцией, называется биекцией или взаимно однозначным соответствиеммежду M и N.Теорема.Прообраз суммы двух множеств равен сумме их прообразов, то естьf −1 ( A  B) = ƒ–1(А)  ƒ–1(В).Доказательство:Пусть х ∈ ƒ–1( A  B ).

Это означает, что ƒ(х) ∈ A  B , то есть ƒ(х) ∈ Аили ƒ(х) ∈ В ⇒ х принадлежит по крайней мере одному из множеств ƒ–1(А)илиƒ–1(В), то есть х ∈ ƒ–1(А)  ƒ–1(В).Обратно, пусть х ∈ ƒ–1(А)  ƒ–1(В), тогда х принадлежит по крайнеймере одному из множеств ƒ–1(А) или ƒ–1(В), то есть ƒ(х) принадлежит хотя быодному из множеств А или В ⇒ ƒ(х) ∈ A  B⇒ х ∈ ƒ–1( A  B ), что итребовалось доказать.Теорема.Прообразпересечениядвухмножествпрообразов, то есть ƒ–1 ( A  B) = ƒ–1(А)  ƒ–1(В).Доказательство:14равенпересечениюихПусть х ∈ ƒ–1( A  B )⇒ ƒ(х) ∈ А  В,то есть ƒ(х) ∈ А и ƒ(х) ∈ В.Следовательно, х ∈ ƒ–1(А) и х ∈ ƒ–1(В) ⇒ х ∈ ƒ–1(А)  ƒ–1(В).Обратно, пусть х ∈ ƒ–1(А)  ƒ–1(В), то есть х ∈ ƒ–1(А) и х ∈ ƒ–1(В) ⇒ƒ(х) ∈ А и ƒ(х) ∈ В, то есть ƒ(х) ∈ А  В ⇒ х ∈ ƒ–1(А  В), что и требовалосьдоказать.Теорема.Образ суммы двух множеств равен сумме их образов, то естьƒ ( A  B) = ƒ(А)  ƒ(В).Доказательство:Пусть y ∈ ƒ(А  В). Это означает, что y = ƒ(х), где х принадлежит покрайнеймереодномуизмножествАилиВ.Следовательно,y = ƒ(х) ∈ ƒ(А)  ƒ(В).Обратно, пусть y ∈ ƒ(А)  ƒ(В) ⇒ y = ƒ(х), где х принадлежит покрайнеймереодномуизмножествАилиВ,тоестьх ∈ А  В ⇒ y = ƒ(х) ∈ ƒ(А  В), что и требовалось доказать.Замечания.1.

Последние три теоремы остаются в силе для сумм и пересеченийлюбого (конечного или бесконечного) числа множеств.2. Образ пересечения двух множеств, вообще говоря, не совпадает спересечением их образов.Например, пусть задано отображение, проектирующее плоскость наось х. Тогда отрезки0 ≤ x ≤ 1, y = 0;0 ≤ x ≤ 1, y = 1.не пересекаются, а в то же время их образы совпадают.151.05. Разбиение на классы. Отношения эквивалентности.На практике часто встречаются разбиения тех или иных множеств напопарно непересекающиеся подмножества.Например,1. плоскость, рассматриваемую как множество точек, можно разбить напрямые, параллельные оси х;2. трехмерноепространствоможнопредставитькакобъединениеконцентрических сфер различных радиусов, начиная с r = 0;3. жителей данного города можно разбить на группы по их году рожденияи т.п.Определение.Каждый раз, когда некоторое множество М представлено тем или инымспособом как сумма попарно непересекающихся подмножеств, говорят оразбиении множества М на классы.Обычно разбиения связаны с признаком, по которому элементымножества объединяются в классы.Ещё примеры:множество всех треугольников можно разбить наа) классы равных между собой треугольников;б) классы равновеликих треугольников и т.д.все функции от х можно разбить на классы, собирая в один классфункции, принимающие в данной точке одинаковые значения.Признаки могут быть самыми разнообразными, но их выбор непроизволен.Определение.Бинарное отношение над множеством М – это подмножество ℜмножества М × М всех упорядоченных пар из М.16Определение.Бинарнымотношениеммеждудвумямножестваминазываетсясоответствие элементов одного из них элементам другого.Замечание.Вместо принадлежности пары (х, y) бинарному отношению ℜ, то естьвместо (х, y) ∈ ℜ часто используют инфиксную запись, то есть х ρ y.Определение.Бинарное отношение ℜ над М называется рефлексивным, если для всехх ∈ М имеем: (х, х) ∈ ℜ или, другими словами,хρх для ∀х ∈ М.