Дискретная математика


СРЕДНЕЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАНИЕ
Серия основана в 2001 году




С.А. КАНЦЕДАЛ


ДИСКРЕТНАЯ МАТЕМАТИКА
УЧЕБНОЕ ПОСОБИЕ




                        Допущено Министерством образования и науки Российской Федерации в качестве учебного пособия для студентов учреждений среднего профессионального образования


znanium.com

Москва
ИД «ФОРУМ» — ИНФРА-М
2022

УДК 519.1(075.32)
ББК 22.176я723
     К19



      Рецензенты:
         Сенатов В.В., доктор физико-математических наук, профессор кафедры теории вероятности Московского государственного университета имени М.В. Ломоносова;
         Панишев А.В., доктор технических наук, профессор, заведующий кафедрой информатики и компьютерного моделирования Житомирского государственного технологического университета

      Канцедал С.А.
К19 Дискретная математика : учебное пособие / С.А. Канцедал. — Москва : ИД «ФОРУМ» : ИНФРА-М, 2022. — 222 с. — (Среднее профессиональное образование).
         ISBN 978-5-8199-0719-1 (ИД «ФОРУМ»)
         ISBN 978-5-16-013446-8 (ИНФРА-М, print)
         ISBN 978-5-16-104039-3 (ИНФРА-М, online)
         В учебном пособии на элементарном уровне изложены традиционные разделы дискретной математики. В главе «Экстремальные задачи» на примерах показано применение ее основ.
         Предназначено для студентов средних профессиональных учебных заведений, а также может быть рекомендовано студентам вузов.
УДК 519.1(075.32)
ББК 22.176я723

















ISBN 978-5-8199-0719-1 (ИД «ФОРУМ»)
ISBN 978-5-16-013446-8 (ИНФРА-М, print)
ISBN 978-5-16-104039-3 (ИНФРА-М, online)


© Канцедал С.А., 2006
© ИД «ФОРУМ», 2006

                Введение






   Математика — это наука о количественных отношениях и пространственных формах действительного мира. Наука эта древняя, хотя и не так стара, как старо все человечество.
   Когда-то очень давно, когда люди стали нуждаться в подсчете количеств некоторых предметов, они придумали числа 1, 2, 3, ... . При помощи этих чисел они и отражали то или иное количество предметов, непосредственно абстрагируясь от самих предметов. Позже указанные числа были названы числами натурального ряда.
   Арифметические операции над числами натурального ряда, и в первую очередь вычитание, привели к необходимости ввести в обиход числа отрицательные -1, -2, -3, ... ,а также число нуль, отображающее отсутствие количества, т.е., просто говоря, означающее «ничего». Полученная совокупность чисел натурального ряда, нуля и чисел отрицательных была названа множеством целых чисел.
   Практическая необходимость измерять величины, например, длины, веса, площади, объемы и т.п. привела к выработке понятия меры и единицы измерения. При помощи единицы измерения та или иная величина указывалась числом соответствующих единиц. Однако на практике это число часто оказывалось не целым. Тогда решили ввести понятие правильной дроби, как части целой единицы измерения. В результате оказалось возможным указывать измеряемую величину целым количеством единиц измерения и количеством частей этих единиц. Совокупность правильных дробей и целых чисел получила название множества рациональных чисел.
   Введенный набор рациональных чисел был весьма широк, однако практически оказался недостаточным для выражения всех величин. Например, никакое рациональное число не подходило для выражения длины диагонали квадрата через его единичную сторону. Таким образом, понадобилось ввести понятие множества иррациональных чисел, как множества правильних и бесконечных дробей.

Введение

   Все вместе перечисленные классы получили название множества действительных чисел, которое тем не менее не является достаточным для отображения количественных связей между всеми объектами, которыми оперирует математика. Есть еще числа недействительные — комплексные.
   Беглый взгляд на возникновение чисел, изложенный выше, свидетельствует о том, что математика не принадлежит к естественным наукам, таким, например, как физика, биология, астрономия, геология и др. Это наука, основанная на абстракции и воображении, и она, вводя в естественные науки количественные связи, обслуживает их. Такова роль математики и в пространственных, т.е. геометрических, формах действительного мира.
   Современная математика объединяет много разделов. В средней школе изучают арифметику, алгебру, геометрию и тригонометрию. Программы высших учебных заведений в зависимости от специализации их выпускников предлагают различную глубину изучения аналитической геометрии, высшей алгебры, дифференциального и интегрального исчисления, теории чисел, функционального анализа, численных методов анализа, топологии и др. Однако по современным воззрениям в основе всех математических дисциплин лежит понятие множества и основные положения теории множеств, впервые изложенные немецким математиком Г. Кантором (1845—1918).
   Дискретная математика — это раздел математики, который опирается на понятие дискретного множества. К этому разделу мы относим элементы теории конечных множеств как фундамента дискретной математики, теорию графов как наглядное представление дискретных множеств, имеющую широкое практическое применение комбинаторику, элементы математической логики, включающие булеву алгебру и алгебру высказываний, теорию алгоритмов и экстремальные задачи дискретной математики, результаты решения которых имеют важные практические приложения.
   С определенной степенью полноты указанные разделы дискретной математики изложены в данном учебном пособии. Оно предназначено для учащихся средних специальных заведений, обучающихся по специальностям: 2202 — автоматизированные системы обработки информации и управления, 2203 — программное обеспечение вычислительной техники и автоматизированных систем.

                Глава 1
                Множества, отношения, функции






            1.1. Множества


   Понятие множества является базисом современной математики, теория множеств — ее фундамент.
   Определение 1.1. Множество — это совокупность вполне оп-ределе нныхи различимых между собой объектов любой природы, мыслимых как единое целое.
   Главное в этом определении то, что некоторая совокупность (собрание) объектов рассматривается как единое целое. В эту совокупность могут входить как реально существующие объекты, так и воображаемые. Например, можно определить множество студентов данного университета, множество его преподавателей, множество аудиторий, множество учебников, которыми пользуются студенты, множество автомобилей данного города, множество звезд Солнечной галактики, множество песчинок на берегу моря и т.д.
   Все это — реально существующие множества. Воображаемые множества, с которыми мы будем иметь дело, — это объекты математики. Можно привести такие примеры этих множеств: множества натуральных, целых, рациональных, действительных и комплексных чисел, множество точек плоскости площадью 1 см х 1 см, множество кривых, проходящих через данную точку прямой, множество окружностей диаметром меньше 1 мм с центром в одной точке плоскости. И этот перечень легко продолжить.
   Любое множество состоит из его элементов. Оно считается заданным, если известны эти элементы. Поэтому термин «вполне определенных и различимых между собой», фигурирующий в определении множества, следует понимать как то, что для любых двух элементов множества можно сказать, различимы они или одинаковы и является ли конкретный предмет элементом множества.

Глава 1. Множества, отношения, функции

   Множество принято задавать двояко: либо перечислением его элементов, которые записываются в фигурных скобках, либо специальным правилом, по которому можно отнести элемент к множеству. Само множество при этом обозначается прописной (большой) буквой русского или латинского алфавита.
   Вот примеры записи множеств первым способом:
   A = {а, б, в} — три начальные буквы русского алфавита;
   C ={0,1,2,3,... ,9} — цифры десятичной системы счисления;
   В = {0, 1} — цифры двоичной системы счисления;
   D = {0, 1} — значения корней уравнения x² - x = 0;
   N = {1, 2, 3, ... } — натуральные числа;
   M = {2, 4, 6, ... } — четные натуральные числа;
   L = {0, 1, -1, 2, -2, ... } — целые числа;
   K = {a, b, c, d, t, f, ... ,x, y, z} — буквы латинского алфавита.
   При втором способе множество задается так: X = {xp(x)}. Это означает, что X — множество всех элементов х таких, что высказывание Р(х) истинно. Например, Y = {у 1 < у < 10} — множество значений у из интервала [1,10]; I = {i\i}, i — цифра десятичной системы счисления — множество десятичных цифр 0, 1, 2, ... ,9; X = {x|x}, х — действительный корень уравнения x² + x + 2 = 0 — множество действительных корней указанного уравнения.
   Запись множества перечислением его элементов характерна для множеств с небольшим количеством элементов. Второй способ задания более общий и может быть использован всегда.
   Тот факт, что некоторый элемент х принадлежит множеству X, записывают так: x е X, где е — так называемый квантор принадлежности, заменяющий слово «входить». Если же элемент х не принадлежит множеству X, то применяется запись x е X.
   Пусть задано числовое множество X = {x|x < 1 и x > 2}. Это множество не содержит никаких элементов, так как нет чисел, которые бы одновременно были больше 2 и меньше 1. Такое множество называется пустым и обозначается знаком 0.
   Таким образом, X = {x|x < 1 и x > 2} = 0, X = {x|x = x} = x. Однако множество X = {0} ^ 0, поскольку это множество содержит один элемент, а именно число 0. Пустое множество {0} ^ 0, так как 0 — множество, а 0 множеством не является по обозначению. Далее {0} ^ 0, поскольку множество {0} содержит один элемент, а именно пустое множество 0. При этом любое множество А всегда содержит пустое множество 0.

1.1. Множества

7

   Элементы множества могут быть записаны в любом порядке. Например, {1,2,3}и{3,2, 1} — одно и тоже множество, содержащее три элемента.
   Определение 2.1. Два множества равны, когда они состоят из одних и тех же элементов.
   Множества A = {1, 2, 3}, B = {3, 1, 2}, C = {1, 2, 3, 3} — равны. Множество С есть, в сущности, множество А, только в нем элемент 3 записан дважды, т.е. две тройки в нем неразличимы. Множества A = {1, 2}, B = {1, 2, 3} — не равны.
   Определение 3.1. Семейством множеств называется множество, элементы которого сами являются множествами.
   Например, A = {{0}, {1, 2}, {3, 4, 5}} — с мейство,состоящее из трех множеств. Очевидно, что 2 е X = {1, 2, 3} и в то же время {1, 2} g X = {{1, 2, 3}, {1, 3}, 1, 2}, так как среди элементов семейства X нет множества {1, 2}.
   Определение 4.1. Если А и В — множества, то говорят, что множество А содержится в В или включено в множество В и пишут A с B в том и только в том случае, если каждый элемент множества А является элементом множества В.
   Множество А в этом случае называется подмножеством В. Когда же множество А содержит только часть элементов множества В, оно называется собственным подмножеством множества В и записывается так: A с B.
   Пусть заданы множества A = {a, b, c}, B = {a, b, c}, C = {a, b, c, d, e}, тогда A с B, A с C, B с C. Пусть X = {x 1 < x < 2}, Y = {y 1 < y < 2}, Z = {z0 < z < 3}, тогда X с Y, X с Z, Y с Z. И если N = {{1, 2}}, M = {{1, 2}}, P = {{1, 2}, {1, 2, 3}}, тогда N с M, N с P, M с P.
   Основные свойства включения следующие: X с X; если X с Y, а Y с Z, то X с Z; если X с Y и Y с X, то X = Y.
   Определение 5.1. Каждое непустое подмножество A ±0 имеет по крайней мере два различных подмножества: само множество А и пустое множество 0. Кроме того, каждый элемент множества А определяет некоторое его подмножество. Например, если а е A, то {а} с A.
   Определение 6.1. Семейство всех подмножеств данного А называется множеством-степенью множества А и обозначается Р(А).
   Например, если A = {1, 2, 3}, то P(A) = {A, 0, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}}.

Глава 1. Множества, отношения, функции

   То, что 0 с A доказывается просто. Предположим, что 0 не включено в А, т.е. 0 £ A. Это может быть только в том случае, когда существует некоторый элемент A е0, не являющийся элементом множества А. Но это невозможно, так как множество 0 не имеет элементов, оно пустое. Значит A g0 и, следовательно, 0 £ A ложно. Таким образом, 0 с A.
   На практике весьма часто используются индексированные множества. Например, запись X = {xz|z = 1, 2, ..., n} означает, что X — множество, состоящее из элементов x 1, x₂, ... ,xₜ ,..., xₙ. При этом I = {z|z = 1, 2, ..., n} — индексное множество.
   Различают множества конечные и бесконечные.
   Определение 7.1. Множество называется конечным, если количество его элементов может быть выражено некоторым положительным числом.
   При этом совершенно неважно, известно это число или нет. Важен лишь факт существования такого числа. В качестве примеров конечных множеств можно привести такие: множество букв русского алфавита, множество страниц данной книги, множество домов некоторого поселка, множество пчел в данном улье, множество студентов и стульев данной аудитории. Этот список, безусловно, можно продолжать. Для конечного множества А, содержащего n элементов, его множество-степень P(A) равна 2ⁿ.
   Бесконечные множества — это тоже объекты математики. Бесконечны множества натуральных, целых, рациональных, действительных и комплексных чисел. Бесконечно множество всех точек плоскости, множество всех точек прямой, длиной, например, 1 мм, множество всех непрерывных функций, множество прямых, пересекающихся в одной точке и т.д.
   Дискретная или, как часто говорят, конечная математика оперирует с конечными множествами, т.е. с множествами, элементы которых можно сосчитать.
   Безусловно, дискретность (прерывность) более свойственна окружающему нас миру, а понятия бесконечности, непрерывности, предела, которыми оперирует континуальная математика, введены специально для упрощения изучения явлений, которые лишь кажутся нам непрерывными.
   Множества натуральных, целых, рациональных и действительных чисел, а также производные от них упорядоченные наборы чисел (множества векторов), которые используются как в непрерывной, так и частично в дискретной математике, получили

1.1. Множества

9

название числовых (!) множеств. Оно происходит от того, что любое число из названных множеств или упорядоченный их набор можно изобразить точкой на геометрической оси или в n-координатном пространстве.
   Однако среди названных числовых множеств непрерывностью обладает лишь множество действительных чисел или соответствующий упорядоченный их набор. Это проявляется в том, что для множества действительных чисел между точками на геометрической прямой, отображающей некоторые числа, не существует просвета. Говоря строго, каждому числу соответствует точка на геометрической прямой, и любой точке на прямой соответствует свое действительное число. Все остальные числовые множества этим свойством взаимной однозначности точек и чисел не обладают. Даже для всюду плотного множества рациональных чисел, т.е. такого, что для двух его чисел r1 < r2 всегда найдет-r1 + r₂
ся третье число ¹ ², существует точка — длина диагонали квад-

рата с единичными сторонами, которая не отображается в рациональное число. Поэтому, определяя дискретное множество, часто говорят, что оно состоит из множества изолированных точек, отталкиваясь при этом именно от геометрической интерпретации элементов числовых множеств.
   Существует ряд так называемых теоретико-множественных операций над множествами. В результате этих операций получаются новые множества из уже существующих. Теоретико-множественные операции в некотором отношении аналогичны операциям сложения, вычитания и умножения целых чисел.
   Определение 8.1. Объединением (суммой) множеств А и В (обозначается A U B) называется множество тех элементов, каждый из которых принадлежит хотя бы одному из множеств А или В. Иными словами, A U B = {x|x е A или x е B}. При этом подразумевается неисключающий смысл слова «или».
   При выполнении операции объединения могут встретиться три случая: 1) A с B и B с A, т.е. A = B; 2) множества имеют общие элементы; 3) множества не имеют общих элементов.
   В первом случае объединение A U B — суть одни и те же элементы А и В. Например, A = {1,2,3}, B = {1,2,3}. Тогда A U B = {1,2, 3}.

Глава 1. Множества, отношения, функции

   Во втором случае только часть элементов общая. Например, A = {1,2,3}, B = {2, 3,4, 5, 6}. Тогда AUB = {1, 2, 3, 4, 5, 6}. При этом общий элемент 2 включается в объединение A U B один раз.
   Третий случай демонстрируется следующим примером A = {1, 2, 3}, B = {4, 6, 8}, AUB = {1, 2, 3, 4, 6, 8}.
   Рассмотренные случаи наглядно проиллюстрированы на рис. 1.1 при помощи диаграмм Венна-Эйлера.
   Заштрихованные окружности представляют собой объединения множеств.



  случай 1          случай 2                   случай 3

Рис. 1.1. Графическая иллюстрация операции объединения множеств

    Объединением (суммой) любой совокупности множеств A 1, A₂, ... Ai, ...An называется множество А таких элементов, каждый из которых принадлежит хотя бы одному из слагаемых множеств. Объединение многих множеств записывается так: A = A1 U A₂ U...UA U...UAₙ = UП=1 Ai. Например, A 1 = {a, b}, A₂ = {b, c, d}, A₃ = {c, d, e, f}. Тогда A = A 1 U A₂ U A₃ = {a, b, c, d, e, f}.
    Нетрудно видеть, что A U A = A. Это отличает свойства теоретико-множественного сложения от алгебраического. Кроме того, A U 0 = A.
    Определение 9.1. Пересечением (произведением) множеств А и В (обозначается A П B) называется множество тех элементов, которые одновременно принадлежат как множеству А, так и множеству В. Иными словами, A П B = {x\x е A и x е B}.
    При выполнении операции пересечения могут встретится также три случая: 1) A с B и B с A, т.е. A = B; 2) множества имеют часть общих элементов; 3) множества не имеют общих элементов.
    В первом случае пересечение A П B — это либо элементы А, либо элементы В, которые неразличимы. Например, A = {1,2}, B = {1,2}. Тогда A П B = {1,2}.
    Во втором случае пересечением являются общие элементы для А и В. Например, A = {1, 2, 3}, B = {2, 3, 4, 5}. Тогда A П B = {2, 3}.