Файл: Учебника по курсу Основы дискретной математики и логики.pdf

Текст для учебника по курсу
«Основы дискретной математики и логики»
Слайд 2
Тема 1.1. Множества и операции над ними
Теория множеств – раздел математики, в котором изучаются общие свойства множеств – совокупностей элементов произвольной природы, обладающих каким-либо общим свойством. Создана теория множеств во второй половине XIX века Георгом Ка́нтором при значительном участии
Ри́харда Дедеки́нда, она привнесла в математику новое понимание природы бесконечности. Была обнаружена глубокая связь теории с формальной логикой, однако уже в конце XIX – начале XX века теория столкнулась со значительными сложностями в виде возникающих парадоксов. Поэтому изначальная форма теории известна как наивная теория множеств. В XX веке теория получила существенное методологическое развитие. Были созданы несколько вариантов аксиоматической теории множеств, обеспечивающие универсальный математический инструментарий. В связи с вопросами измеримости множеств тщательно разработана дескриптивная теория множеств.
Теория множеств стала основой многих разделов математики – общей топологии, общей алгебры, функционального анализа и оказала существенное влияние на современное понимание предмета математики. В первой половине XX века теоретико-множественный подход был привнесен и во многие традиционные разделы математики, в связи с чем стал широко использоваться в преподавании математики, в том числе в школах. Однако использование теории множеств для логически безупречного построения математических теорий осложняется тем, что она сама нуждается в обосновании своих методов рассуждения. Более того, все логические трудности, связанные с обоснованием математического учения о бесконечности, при переходе на точку зрения общей теории множеств приобретают лишь бо́льшую остроту.

Начиная со второй половины XX века представление о значении теории и ее влияние на развитие математики заметно снизились.
Это произошло за счет осознания возможности получения достаточно общих результатов во многих областях математики и без явного использования ее аппарата, в частности, с использованием теоретико-категорного.
Тем не менее нотация теории множеств стала общепринятой во всех разделах математики вне зависимости от использования теоретико-множественного подхода. На идейной основе теории множеств в конце XX века создано несколько обобщений, в том числе теория нечетких множеств, теория мультимножеств, используемые в основном в приложениях, теория полумножеств.
Слайд 3
Основными понятиями теории являются элементы и множество. Эти понятия считаются общеизвестными и не определяются, так как, если попытаться определить их, например, так: множество элементов есть их совокупность, – то нужно дать понятие совокупности. Например, совокупность элементов есть некоторый их набор, что потребует дать определение набора элементов. Такие вложенные определения будут повторяться до бесконечности. Поэтому, говоря о некотором множестве, лучше всего пояснить это на примерах. Таким же неопределяемым понятием является элемент. Например, множество студентов конкретной группы можно обозначить через М. Каждый студент этой группы является элементом множества М.
Множества обычно обозначаются большими буквами латинского алфавита, возможно с индексами, а элементы множества – малыми буквами.
Примеры обозначений множеств и их элементов приведены в формулах (1.1) и (1.2). Для указания принадлежности или непринадлежности элемента множеству используют обозначения, приведенные в формуле (1.3).

Множества A[а] и B[бэ] равны, если они состоят из одних и тех же элементов. Если все элементы, из которых состоит множество A[а], входят и во множество B[бэ], то A[а] называют подмножеством множества B[бэ]. На основании этого также можно сказать, что два множества A[а] и B[бэ] равны, если A[а] является подмножеством B[бэ], а B[бэ] является подмножеством
A[а]. Множество, не содержащее ни одного элемента, называется пустым множеством. Подмножества некоторого множества, отличные от него самого и от пустого множества, называются собственными. Например, множество целых чисел является собственным подмножеством множества действительных чисел; множество остроугольных треугольников является собственным подмножеством множества всех треугольников. Если А[а] является подмножеством B[бэ], но не совпадает с ним, то говорят, что А[а] является строгим подмножеством множества B[бэ]. Всякое собственное подмножество рассматриваемого множества будет его строгим подмножеством. Обратное утверждение неверно. Пустое множество является строгим подмножеством любого непустого множества, но не является его собственным подмножеством. В формуле (1.4) приведено обозначение, используемое для подмножества, в формуле (1.5) – обозначение пустого множества, в формуле (1.6) – обозначение строгого подмножества.
Слайд 4
Существуют различные способы задания множеств. Один из возможных способов – перечисление всех элементов множества, которые записываются в фигурных скобках. Таким образом, фигурные скобки обозначают множество.
Данный способ обычно применяется в том случае, когда множество содержит конечное небольшое количество элементов.
Если же множество содержит большое количество элементов или бесконечное число элементов, то для задания множества лучше использовать другой способ – характеристическое свойство. При этом способе задания

описывается признак, по которому мы однозначно можем определить, принадлежит рассматриваемый элемент данному множеству или не принадлежит.
Множество А[а] на слайде задано перечислением его элементов.
Множества В[бэ] и С[cэ] – с помощью характеристического свойства.
Двоеточие в записи множеств В[бэ] и С[cэ] читается «такие, что».
Множество B[бэ] состоит из целых чисел x[икс] таких, что x[икс] кратно трем. Множество С[cэ] состоит из таких действительных чисел х
[икс], что х[икс] меньше десяти.
Универсальное множество U[у] есть множество, обладающее таким свойством, что все рассматриваемые множества являются его подмножествами.
В теории чисел универсальное множество обычно совпадает со множеством всех целых чисел или натуральных чисел. В математическом анализе универсальное множество может быть множеством всех действительных чисел или множеством всех точек эн-мерного пространства.
Следует отметить, что хотя универсальное множество и названо универсальным, однозначно не определено, если точно не указана область рассмотрения. Конечно, любое множество, содержащее U[у] может быть использовано как универсальное.
В некоторых случаях оказывается удобным графический способ задания множества.
Он применяется, например, тогда, когда рассматриваемое множество представляет собой часть плоскости. Это может быть круг, треугольник, квадрат, полуплоскость, координатная четверть и тому подобное. В таких ситуациях интересующее нас множество изображается на плоскости и заштриховывается или закрашивается.
Слайд 5
Объединением множеств А[а] и В[бэ] называется множество С[цэ], состоящее из всех элементов, принадлежащих хотя бы одному из множеств

А[а] и В[бэ]. Аналогично определяется объединение любого, возможно бесконечного, числа множеств. Например, объединением множества положительных целых чисел и множества отрицательных целых чисел является множество целых чисел, отличных от нуля. Если одно из рассматриваемых множеств является частью другого, то их объединением будет более широкое множество. Так, объединением множества равнобедренных треугольников и множества равносторонних треугольников является множество равнобедренных треугольников.
Пересечением множеств А[а] и В[бэ] называется множество С[цэ], состоящее из всех элементов, принадлежащих как А[а], так и В[бэ].
Аналогично определяется пересечение любого числа множеств. Например, пересечением множества натуральных чисел, делящихся на 5, и множества натуральных чисел, делящихся на 3, является множество натуральных чисел, делящихся на 15. Если одно из рассматриваемых множеств является частью другого, то их пересечением будет более узкое множество. Так, пересечением множества квадратов и множества прямоугольников является множество квадратов.
Формулы (1.7) и (1.8) определяют введенные выше операции с помощью математических символов.
Слайд 6
Говорят, что множества А[а] и В[бэ] находятся в общем положении, если они пересекаются, но ни одно из них не является подмножеством другого. Например, рассмотрим множество натуральных чисел, делящихся на 6, и множество натуральных чисел, делящихся на 9. Они имеют непустое пересечение – множество натуральных чисел, делящихся на 18. При этом ни одно из двух данных множеств не является частью другого. Следовательно, рассматриваемые множества находятся в общем положении.
Разностью множеств А[а] и В[бэ] называется множество C[цэ], состоящее из всех элементов А[а], не принадлежащих B[бэ]. Например,

разностью множества натуральных чисел и множества нечетных чисел является множество четных чисел.
Симметрической разностью множеств A[а] и B[бэ] называется множество C[цэ], получающееся при объединении разности A[а] и B[бэ] с разностью B[бэ] и A[а]. Отметим, что если множество B[бэ] является частью множества A[а], то симметрическая разность A[а] и B[бэ] совпадает с обычной разностью.
Предположим, что мы рассматриваем совокупность множеств, являющихся подмножествами некоторого основного, или универсального, множества U[у]. Тогда для всякого множества A[а]разность U[у] и A[а] называют дополнением множества A[а]. Например, дополнением множества всех остроугольных треугольников до множества всевозможных треугольников является множество всех тупоугольных и прямоугольных треугольников.
Определения операций разности, симметрической разности и дополнения с помощью математических символов представлены соответственно в формулах (1.9), (1.10) и (1.11).
Слайд 7
Операции объединения и пересечения множеств обладают свойством коммутативности. Указанное свойство представлено формулами (1.12), (1.13) соответственно. Свойство коммутативности выполняется и для операции сложения чисел и в этом случае означает, что от перестановки мест слагаемых сумма не меняется.
Операции объединения и пересечения множеств обладают свойством ассоциативности. Указанное свойство представлено формулами (1.14), (1.15) соответственно. Это свойство означает, что одна и та же операция для трех и более множеств может производиться в любом удобном порядке.

Кроме того, для данных операций справедливы свойства дистрибутивности, которые выражаются формулами (1.16) и (1.17). С помощью этих свойств можно выносить общее множество за скобки.
В теории множеств часто используются правила де Мо́ргана, или теоремы двойственности. Первая из них утверждает, что дополнение до объединения множеств равно пересечению их дополнений. Вторая говорит о том, что дополнение до пересечения множеств совпадает с объединением их дополнений.
Формулировки данных утверждений с помощью математических символов представлены в формуле (1.18).
Слайд 8
Для геометрической иллюстрации операций над множествами довольно часто используют диаграммы Эйлера – Венна. На этих диаграммах исходные множества изображаются в виде кругов. В случаях, когда рассматриваются операции пересечения, объединения, разности и симметрической разности, круги, изображающие множества A[а] и B[бэ], накладываются друг на друга. Для изображения операции дополнения универсальное множество U[у] изображается в виде круга или прямоугольника, внутри которого содержится круг, изображающий дополняемое множество A[а]. На рис. 1.1 множества, получающиеся в результате применения указанных операций к множествам A[а] и B[бэ], закрашены синим цветом.
Подобные диаграммы могут быть использованы для геометрической иллюстрации объединения и пересечения трех и более множеств. В этом случае на рисунке изображается столько налегающих друг на друга кругов, сколько множеств участвует в объединении или пересечении.
Слайд 9
Рассмотрим примеры выполнения операций над множествами. В первом случае даны два конечных множества A[а] и B[бэ] и универсальное множество U[у].

Для нахождения объединения множеств A[а] и B[бэ] записываем все числа, входящие в эти множества. Их общие элементы записываются один раз.
В пересечение множеств входят их общие элементы.
Разность множеств А[а] и В[бэ] состоит из элементов, которые принадлежат первому множеству и не принадлежат второму. Аналогично в разность множеств В[бэ] и А[а] входят те элементы из В[бэ], которых нет в
А[а].
Симметрическая разность представляет собой объединение двух разностей, поэтому в симметрическую разность собраны вместе элементы двух предыдущих множеств.
Дополнение множества А[а] состоит из всех элементов универсального множества, которые не принадлежат множеству А[а]. Соответственно, дополнение множества В[бэ] образовано теми элементами множества U[у], которые не вошли в В[бэ].
Слайд 10
В качестве второго примера рассмотрим бесконечные множества A[а] и
B[бэ] на плоскости, которая в данном случае будет играть роль универсального множества. Пусть A[а] −
множество всех точек плоскости с неотрицательными абсциссами, а B[бэ] − множество всех точек плоскости с неотрицательными ординатами. Формулы (1.19), (1.20) задают множества
A[а] и B[бэ] с помощью математических символов.
Объединение множеств A[а] и B[бэ] представляет собой совокупность всех точек плоскости, лежащих в первой, второй и четвертой координатных четвертях, вместе с ограничивающими данное множество полупрямыми.
Пересечение множеств A[а] и B[бэ] состоит из всех точек первого квадранта вместе с ограничивающими его полупрямыми. Описания указанных множеств с помощью математических символов представлены формулами
(1.21) и (1.22).

Разность множеств A[а] и B[бэ] представляет собой совокупность всех точек плоскости с неотрицательными абсциссами и отрицательными ординатами, то есть полуоткрытый четвертый квадрант. Симметрическая разность множеств A[а] и B[бэ] состоит из всех точек плоскости, у которых абсцисса и ордината имеют разные знаки, а также точек отрицательных полуосей оси абсцисс и оси ординат. Другими словами, данное множество представляет собой совокупность полуоткрытых второй и четвертой четвертей. Наконец, дополнение множества A[а] состоит из всех точек плоскости, имеющих отрицательную абсциссу. Описания разности и симметрической разности множеств A[а] и B[бэ], а также дополнения множества A[а] с помощью математических символов представлены формулами (1.23), (1.24) и (1.25) соответственно.
Слайд 11
Декартовым произведением множеств A[а] и B[бэ] называется множество всех упорядоченных пар, в которых первый элемент принадлежит множеству A[а], а второй – множеству B[бэ]. Определение декартова произведения с помощью математических символов представлено в формуле
(1.26). Формула (1.27) задает примеры конкретных множеств A[а] и B[бэ], а формула (1.28) представляет их декартово произведение.
Рассмотрим теперь множества A[а] и B[бэ], задаваемые формулой
(1.29). Их декартово произведение представлено формулой (1.30).
Декартово произведение множества A[а] на себя называют декартовым квадратом множества A[а]. Используемое в этом случае обозначение указано в формуле (1.31).
Наряду с декартовым произведением двух множеств можно рассматривать декартово произведение любого конечного числа множеств.
Соответствующее определение представлено формулой (1.32). Если все сомножители одинаковы и равны A[а], то получаем куб, четвертую, пятую и

более высокие степени множества A[а]. Соответствующие обозначения приведены в формуле (1.33).
Cлайд 12
Мощностью конечного множества A[а] называется число его элементов. Обозначение мощности множества приведено в формуле (1.34).
Для множества A[а], указанного в формуле (1.35), мощность равна 5.
Булеаном множества A[а] называют множество всех подмножеств множества A[а]. Обозначение булеана множества приведено в формуле
(1.36).
Каким бы ни было рассматриваемое множество, его булеан всегда содержит пустое множество, так как оно является подмножеством любого множества. Кроме того, в булеан множества входит само исходное множество. Остальные элементы булеана множества представляют собой собственные подмножества рассматриваемого множества. При записи булеана конечного множества A[а] обычно сначала указывают пустое множество, затем множества, состоящие из одного элемента, далее – множества, содержащие два элемента, потом – множества, содержащие три элемента, и так далее. В конце перечня записывают само множество A[а].
Формула (1.37) представляет булеан конкретного множества A[а].
В формуле (1.38) указана связь между мощностью конечного множества A[а], содержащего n[эн] элементов, и мощностью его булеана.
Слайд 13
Тема 1.2. Соответствия между множествами
Изучая окружающий нас мир, математика рассматривает не только его объекты, но связи между ними. Эти связи называют зависимостями, соответствиями, отношениями, функциями. Например, при вычислении длин предметов устанавливаются соответствия между предметами и числами, которые являются значениями их длин. При решении задач на движение устанавливается зависимость между пройденным расстоянием и временем