Введение в дискретную математику. Множества и операции над ними

6. Введение в дискретную математику 6.1. Множества и операции над ними Понятие множества относится к основным понятиям математики, наряду с натуральными числами, точкой, прямой и т. д. Для множества можно ввести синонимы: совокупность предметов, объединенных по какому-либо признаку, или группа предметов. Создатель теории множеств – немецкий математик Г. Кантор (1845–1918). Он сформулировал принцип объемности: два множества А и B равны тогда и только тогда, если они состоят из одних и тех же элементов. Если х – элемент из множества А, то записывают: x  А . Принцип объемности: А = В   х: ( x  A  x  B ). Например: A  1,1, 2, 2 , B   1, 2  А = В. Повторения не учитываются! Как же можно определить множество? Если множество конечное, то записывают все его элементы: A   a1 , a2 , a3 , ..., an . Если множество бесконечно, то указывают то общее свойство, которым обладают его элементы. Например: А   х Р (х) = все элементы х, обладающие свойством Р и только они. Из школьной программы известны, например, следующие множества: 1) N = 1, 2, 3, 4, 5, 6, … – множество натуральных чисел; 2) Z = 0, 1, 2, 3, 4, 5, … – множество целых чисел; m 3) Q  x x  , m Z , n Z , n  0 – множество рациональных чиn сел; 4)   х х  х – пустое множество, не содержащее ни одного эле-   мента. 218 Подмножества Пусть А и В – некоторые множества. Говорят, что А есть подмножество множества В, если  x : x A  xB . А обозначается это так: A  B . Замечание. По определению пустое множество принадлежит любому множеству В:  B . Обозначим через U – множество всех рассматриваемых множеств (и назовем его универсальным множеством). Операции над множествами 1. Объединением двух множеств А и В назовем такое множество А  В, которое состоит либо из элементов множества А, либо из элементов множества В, либо из их общих элементов (рис. 6.1). Или короче: А В =  х, х А или хВ . 2. Пересечением двух множеств А и В назовем такое множество А  В, которое состоит только из их общих элементов (рис. 6.2). Или короче: А  В  х х А и хВ . 3. Разностью двух множеств А и В назовем такое множество А – В, которое состоит только из тех элементов множества А, которые не содержатся в множестве В (рис. 6.3). Или короче: А – В =  х х А и х  В  . Замечание. Разность двух множеств А – В иногда обозначают и по-другому: А \ В. 4. Дополнением множества А (относительно уни- А В Рис. 6.1 А В Рис. 6.2 А В Рис. 6.3 U версального множества U) назовем такое множество А , которое состоит из таких элементов множества U, которые не содержатся в множестве А (рис. 6.4). А Или короче: А  U \ A . Рис. 6.4 219 5. Прямым декартовым произведением двух множеств А и В назовем такое множество АВ, которое состоит из всевозможных упорядоченных пар (х; у), где левый элемент х  А, а правый элемент упорядоченной пары у  В. Или короче: А В   ( х; у) х А , у В  . Основные тождества теории множеств 1. А  В  В  А – коммутативность операции объединения. 2. А  В  В  А – коммутативность пересечения. 3. ( А  В)  С  А  (В  С ) – ассоциативность объединения. 4. ( А  В)  С  А  (В  С ) – ассоциативность пересечения. 5. А  ( В  С )  ( А  В )  ( В  С ) – дистрибутивность объединения, относительность пересечения. 6. А  ( В  С )  ( А  В )  ( В  С ) – дистрибутивность пересечения, относительность объединения. 7. А Ø = А. 8. А Ø = Ø. 9. А  А  U . 10. А  А = Ø. 11. А  A  A . 12. А  A  A . 13. A  U  U . 14. A  U  A . 15. А  В  А  В   законы Де Моргана. 16. А  В  А  В  17. A  ( A  B)  A  законы поглощения. 18. A  ( A  B )  A  Пример 6.1. Заданы множества: А   х х  2 k  3, k  0, 1, 2, 3, 4, 5  , В   х х  2 m 1, m  1, 3, 5, 7  , С   х х  3 p  3, p  0, 1, 2, 3, 4  и уни- версальное множество U = Z (множество целых чисел). Требуется найти следующие множества: А В , АВ, А – С, дополнение А относительно универсального множества U = Z, АВ. 220 Решение Запишем подробно все элементы множеств А, В, С. Имеем: А    3;  1; 1;3; 5; 7 ; В  3; 7; 11; 15 ; С    3; 0; 3; 6; 9 . Находим объединение А  В    3;  1; 1;3; 5; 7; 11; 15 . Далее находим пересечение А  В  3; 7 – оно составлено только из общих элементов этих множеств. Чтобы найти разность А – С, необходимо из множества А удалить те элементы, которые одновременно принадлежат и множеству С (это будут числа: –3 и 3). Следовательно, А  С    1; 1; 5; 7 . Для того, чтобы найти дополнение А , необходимо из множества U = Z удалить все элементы множества А: А   xZ x  3; x  1; x  1; x  3; x  5; x  7 . Прямое декартовое произведение АВ будет составлено из всевозможных упорядоченных пар (х; у), где левый элемент х  А, а правый элемент упорядоченной пары у  В. Поэтому: А В  (  3; 3),(  3; 7),(  3; 11),(  3; 15),(  1; 3),(  1; 7),(  1; 11),(  1; 15), (1; 3),(1; 7),(1; 11),(1; 15),(3; 3),(3; 7),(3; 11),(3; 15), (5; 3),(5; 7),(5; 11),(5; 15),(7; 3),(7; 7),(7; 11),(7; 15). 6.2. Элементы математической логики Рассмотрим наиболее элементарный раздел математической логики, который носит название алгебра логики. Если у нас имеется несколько высказываний, то при помощи логических связок и отрицаний из них можно образовать различные новые высказывания. При этом исходные высказывания принято называть простыми, а вновь образованные высказывания – сложными. Рассмотрим примеры. 221 Пусть имеются высказывания: «На улице светит солнце», «В классе идут занятия». Из этих простых высказываний можно различными способами построить сложные высказывания: 1. На улице светит солнце, и в классе идут занятия. 2. На улице не светит солнце. 3. На улице светит солнце, однако в классе идут занятия. 4. В классе идут занятия, а на улице светит солнце. 5. На улице светит солнце, или в классе идут занятия. 6. Или на улице светит солнце, или в классе идут занятия. 7. Если на улице светит солнце, то в классе идут занятия. 8. Если в классе идут занятия, то на улице светит солнце. 9. На улице не светит солнце, или в классе идут занятия. 10. На улице светит солнце тогда и только тогда, когда в классе идут занятия. В алгебре высказываний допускаются любые грамматически правильные способы образования сложных высказываний, и совершенно игнорируется смысловая характеристика получившегося предложения. Любое из приведенных десяти сложных предложений допустимо с точки зрения алгебры высказываний. В алгебре высказываний интересуются лишь истинностью или ложностью (истинностным значением) высказываний. Более точно: в ней исследуется вопрос об истинности сложного высказывания в зависимости от истинности входящих в него простых высказываний и с этой точки зрения исследуются различные логические связки. Примеры логических связок (операций) Таблица 6.1 А В АВ И И И И Л Л Л И Л Л Л Л 1. Логическая связка, соответствующая союзу «и», называется конъюнкцией и обозначается знаком &. Высказывание А & В, называемое конъюнкцией А и В, истинно тогда и только тогда, когда истинны оба высказывания А и В. Это обстоятельство можно выразить с помощью так называемой таблицы истинности для конъюнкции (табл. 6.1). 222 В этой таблице символом И обозначается истинное высказывание, символом Л – ложное. В ней перечислены всевозможные истинностные значения (И и Л) высказываний А и B и соответствующие им истинностные значения высказывания A & B. С точки зрения алгебры высказываний логическая связка (операция) конъюнкция полностью определяется приведенной табл. 6.1. Высказывание А & В абсолютно истинно тогда и только тогда, когда абсолютно истинны оба высказывания А и В. 2. Отрицание ( А ) высказывания А задается табл. 6.2 истинности. Эта операция одноместна – в том смысле, что из одТаблица 6.2 ного данного простого высказывания А строится новое высказывание А . В то же время конъюнкция A & B – двуА А местная операция: сложное высказывание строится из двух И Л простых. Отрицание абсолютно истинного высказывания абсолютно ложно и наоборот. Л И 3. Двуместная логическая операция, соответствующая союзу «или» называется дизъюнкцией (она обозначается знаком ). Надо иметь в виду, что в обычной речи союз «или» упоТаблица 6.3 требляется по крайней мере в двух различных смыслах: неальтернативное (неисключающее) «или» и альА В АВ тернативное (исключающее) «или». И И И Дизъюнкция соответствует неальтернативному И Л И «или»; она задается следующей табл. 6.3 истинности. Л И И Абсолютная истинность АВ означает, что в Л Л Л каждой ситуации хотя бы одно из высказываний А, В истинно. Замечание. Часто, вместо & употребляется знак ^. Отметим также, что конъюнкцию иногда называют логическим умножением. Дизъюнкцию иногда называют логическим сложением. 4. Двуместная логическая операция, соответствующая обороту «если…, то…», посредством которого образуются условные предложения, называется импликацией. При этом сложное высказывание «если А, то В» записывается в виде A→В. Простое высказывание А называется посылкой импликации, В – ее заключением. Приводим табл. 6.4 истинности для импликации. 223 5. В качестве последнего примера логической операции рассмотрим связку, которую называют экА В А→В вивалентностью (обозначение: ~). Она соответствует И И И оборотам типа «тогда и только тогда, когда», «для тоИ Л Л го чтобы, необходимо и достаточно» и др. Приводим Л И И табл. 6.5 истинности для эквивалентности. Теперь у нас имеется некоторое количество «осЛ Л И новных» логических операций (отрицание, дизъюнкТаблица 6.5 ция, конъюнкция, импликация, эквивалентность), позволяющих получать из простых высказываний А В А~В сложные высказывания. При этом вместо простых И И И высказываний можно брать уже построенные сложИ Л Л ные высказывания. В результате появляется возможЛ И Л ность применять при построении сложных высказыЛ Л И ваний многоступенчатые конструкции, многократно использующие введенные логические операции. Назовем формулами логические операции, которые получаются комбинированием конечного числа указанных выше основных логических операций. Для всякой формулы можно построить истинностную таблицу, последовательно используя истинностные таблицы для основных операций. Для всякой формулы можно построить таблицу истинности для основных операций. Естественно считать равносильными формулы, которым соответствуют одинаковые таблицы истинности. Дадим точное определение. Таблица 6.4 Определение 6.1. Пусть U и W – две формулы алгебры высказываний, а А1, …, Аn – набор простых высказываний, входящих по крайней мере в одну из формул U, W. Формулы U и W называются равносильными, если при всех значениях истинности А1, …, Аn значения истинности U и W совпадают. Равносильность U и W обозначается посредством обычного знака равенства: U = W. Далее рассмотрим примеры, в которых будут даны образцы решения типовых задач по теме «Элементы математической логики». 224 Пример 6.2. Дана формула алгебры логики:     А  С   В    А ~В  &C  . Требуется записать для нее таблицу истинности. Решение Данная формула алгебры логики основана на трех простых высказываниях: А, В и С (они будут занимать первые три столбца таблицы истинности (табл. 6.6), эти первые три столбца лучше всегда заполнять так, как в этом образце  для быстроты проверки вашего решения). Таблица 6.6 № 1 2 3 4 5 6 7 8 № А И И И Л И Л Л Л 1 В И И Л И Л И Л Л 2 С И Л И И Л Л И Л 3 А Л Л Л И Л И И И 4 В Л Л И Л И Л И И 5 С Л И Л Л И И Л И 6 1 Л И Л И И И И И 7 2 Л И И И И И И И 8 3 Л Л И И И И Л Л 9 4 Л Л И И Л Л Л Л 10  Л И И И И И И И 11 Пояснения. Для заполнения столбца № 7 для 1  А  С используем столбец № 1 для А, столбец № 6 для С и табл. 6.4 для импликации. Например, на пересечении столбца № 7 и строки № 1 (табл. 6.6) поставлено Л потому, что у высказывания А в строке № 1 стоит И, у высказывания С в строке № 1 стоит Л, а по табл. 6.4 для импликации имеем И  Л  Л . Аналогично заполняются все остальные строки столбца № 7 и столбцов № 811. В записи формулы участвуют А , В , С (они будут занимать столбцы № 4, 5 и 6  эти столбцы заполняем истинностными значениями с помощью табл. 6.2 для отрицания). Далее внимательно изучаем формулу  слева направо. Следующие ее составляющие таковы: 1  А  С, 2 1  В, 3  А ~В, 4 3 &C, 225   2 4 . Они будут занимать столбцы № 711. При заполнении столбцов № 711 истинностными значениями мы будем использовать табл. 6.16.5 для основных логических операций. Пример 6.3. Дана табл. 6.7 для формулы  алгебры логики. Требуется восстановить равносильную  формулу, составить для восстановленной формулы таблицу истинности (табл. 6.8) и сравнить ее с исходной табл. 6.7. Решение Таблица 6.7 № 1 2 3 4 5 6 7 8 № А И И И Л И Л Л Л 1 В И И Л И Л И Л Л 2 С И Л И И Л Л И Л 3  Л И Л Л Л Л И Л 4 Сначала в последнем столбце (в этой задаче это столбец № 4 табл. 6.7) находим буквы И (у нас это строки № 2 и 7, поэтому восстановленная формула будет состоять из двух вариантов, соединенных дизъюнкцией (союзом «или»). Каждый из этих двух вариантов формируется с помощью соответствующей строки (№ 2 и 7) следующим образом: а) берем строку № 2  в ней у высказываний А, В и С истинностные значения тако- вы: И, И, Л, поэтому первый вариант 1  А&В&С ; б) берем строку № 7  в ней у высказываний А, В и С истинностные значения таковы: Л, Л, И, поэтому второй вариант 2  А&В&С . Восстановленная формула имеет вид:   1  2   А&В&С    А&В&С  . Для проверки правильности восстановления этой формулы составим для нее таблицу истинности (табл. 6.8). Рассмотрим восстановленную формулу более подробно: 1  А&В, 1 1 &С, 2  А&В, 2 2 &С,  1 2 . Затем заполняем табл. 6.8 так же, как и в примере 6.2. 226 Таблица 6.8 № 1 2 3 4 5 6 7 8 № А И И И Л И Л Л Л 1 В И И Л И Л И Л Л 2 С И Л И И Л Л И Л 3 А Л Л Л И Л И И И 4 В Л Л И Л И Л И И 5 С Л И Л Л И И Л И 6 1 И И Л Л Л Л Л Л 7 1 Л И Л Л Л Л Л Л 8 2 Л Л Л Л Л Л И И 9 2 Л Л Л Л Л Л И Л 10  Л И Л Л Л Л И Л 11 Замечание. Если сравнить последний столбец табл. 6.8 (здесь это столбец № 11) с последним столбцом табл. 6.7 из условия примера 6.3, то можно увидеть их полное совпадение. Следовательно, мы восстановили формулу правильно. 6.3. Элементы теории графов Определение 6.2. Графом назовем геометрическую структуру, составленную из вершин графа и дуг графа. Вершины графа будем обозначать точками с надписями в виде цифр, или букв, или, даже, слов. Вершины графа, как бы, обозначают станции назначения нашего сложного маршрута движения. Дуги графа будем обозначать линиями, соединяющими две вершины графа. Эти линии могут быть со стрелками или без них. Стрелка показывает направление разрешенного движения по данной дуге графа (как улица с односторонним движением). Если же на дуге графа нет стрелки, то это означает, что движение по этой дуге графа разрешено в обе стороны. Графы будем обозначать буквами G1, G2, …. Пример графа дан на рис. 6.5. У этого графа, в частности, на вершине 3 указана так называемая петля, которая соответствует кольцевой дороге через 3 вершину. Определение 6.3. Пусть задан граф, у которого количество всех вершин равно n. Назовем матрицей смежности этого графа матрицу АG раз227 мера n  n , которая составлена только из чисел 0 и 1. Причем элемент aij этой матрицы АG равен 0, если нет разрешенного движения по дуге графа из вер1 3 • • шины № i в вершину № j. И элемент aij этой матрицы АG равен 1, если есть разрешенное движение по G1: дуге графа из вершины № i в вершину № j. Например, для графа G1 на рис. 6.5 матрица • • 4 5 0 1 0 0 0 0 0 0 0 1   Рис. 6.5 смежности выглядит так: A G1   0 1 1 1 0  ,   1 1   0 1 0 1 0   при этом а33  1 потому, что петля есть только на 3 вершине графа. 2 • Замечание. Матрица смежности полностью определяет свой граф. Определение 6.4. Пусть задан граф G, у которого количество всех вершин равно n. Составим для него матрицу смежности AG, размер которой – n  n . Назовем дополнением к графу G такой граф G , у которого вершины – точно такие же, что и у графа G, а дуги построены в соответствии с матрицей смежности A G , у которой 1 стоят на тех местах, где в исходной матрице AG стоят 0, и наоборот. Пример 6.4. Матрица смежности для дополнения к графу G1 (см. 1 0 1 1 1 1 1 1 1 0   рис. 6.5) имеет вид: A G1   1 0 0 0 1  .   0 1 0 1 1 1 0 1 0 1   Построение дополнения к заданному графу (см. рис. 6.5) проводится так: берем те же самые вершины, затем рисуем петли только возле тех вершин, у которых их не было на исходном графе (на рис. 6.5 – это вершины 1, 2, 4 и 5). Разные вершины графа соединяем дугами, которых не было в исходном графе. В итоге получаем рис. 6.6. 228 Определение 6.5. Пусть заданы графы G1 и G2. Пересечением этих графов назовем новый граф G1  G 2 , который имеет только общие вершины этих двух графов и только общие дуги этих двух графов. Пример 6.5. Построить пересечение графов G1 (см. рис. 6.5) и G2 (рис. 6.7). 2 • 1 • 3 • G1 : • 4 • 5 двух Решение Рис. 6.6 Общие вершины этих двух графов: 1, 2, 3 и 4. Далее берем вершину 1. Сначала проверяем путь 1→2 на общность в двух графах: у графа G1 есть путь 1→2, а у графа G2 есть путь 2→1. Поэтому в пересечении вершины 1 и 2 не будут соединяться. Далее проверяем пути: 1→3, 1→4, 2→3, 2→4, 3→4. В частности, у графа G2 есть путь 1––4 в обе стороны, а у графа G1 есть путь 4→1. Поэтому в пересечении вершины 1 и 4 будут соединяться так 4→1. Общих петель у этих графов тоже нет. В результате получаем рис. 6.8. 2 • 1 • 3 • G2: • 4 Рис. 6.7 Определение 6.6. Пусть заданы графы G1 и G2. Объединением этих графов назовем новый граф G1  G 2 , который имеет вершины, принадлежащие хотя бы одному из этих двух графов, и имеет дуги, которые принадлежат хотя бы одному из этих двух графов. Пример 6.6. Построить объединение двух графов G1 (см. рис. 6.5) и G2 (см. рис. 6.9). Решение В «большой куче», куда можно «свалить» вершины этих двух графов разных вершин будет пять: 1, 2, 3, 4 и 5. Это и будут вершины графа G1  G 2 . 229 Точно также можно «свалить в общую кучу» и дуги обоих графов. В результате у графа G1  G 2 дуги будут такие: 1––2, 1––3, 1––4, 2←3, 2––4, 2––5, 3––4, 4←5, плюс петли возле вершин 1 и 3. Результат на рис. 6.9. 2 • 2 • 1 • 3 • 1 • 3 • G1  G 2 : G1  G 2 : • 4 • 5 Рис. 6.8 • 4 Рис. 6.9 6.4. Контрольные задания по теме «Введение в дискретную математику» Задача 6.1. Заданы множества: А   х х  2 k  5, k   3,  2,  1, 0, 1  , В   х х  3 m  4, m   1, 0, 1, 2, 3 , С   х х  4 p 1, p   1, 0, 1, 2, 3  , D   х х  2 n  7, n  1, 2, 3, 4, 5  , Е   х х  3t  5, t   2,  1, 0, 1, 2  . Требуется найти объединение, пересечение, разность и прямое декартовое произведение следующих множеств (по вариантам): 1. А и В. 2. А и С. 3. А и D. 4. А и Е. 5. В и С. 6. В и D. 7. В и Е. 8. С и D. 9. С и Е. 0. D и Е. Задача 6.2. Для данной формулы  алгебры логики записать таблицу истинности. Формула  задана по вариантам: 1.    А ~ С   В   А  В  &C  . 2.    А ~ С  &В   А  В   C  . 3.    В~ С   В &  А  В  &C  . 4.    А  С  &В   А  В  ~ C . 5.    А&С   В   А  В  ~ C . 6.    А&С  ~ В   А  В   С  . 230 7.    В~С   В &  А  В  &C . 8.    А  С  &В   А  В  ~ С . 9.    А&С   В   А ~ В  C . 0.    А&С  ~ В   А  В   С . Задача 6.3. Дана табл. 6.9 (по вариантам) для формулы  алгебры логики. Требуется восстановить равносильную  формулу, составить для восстановленной формулы таблицу истинности и сравнить ее с исходной табл. 6.9 (по своему варианту). Таблица 6.9 А И И И Л И Л Л Л Вариант В С И И И Л Л И И И Л Л И Л Л И Л Л 1  И Л И Л Л Л Л И 2  Л Л Л И Л И Л И 3  Л И Л Л И И Л Л 4  Л И Л Л И Л Л И 5  И Л Л И Л И Л Л 6  Л И И Л Л Л Л И 7  Л Л Л Л Л И И И 8  И И И Л Л Л Л Л 9  Л Л И И И Л Л Л  Л И Л И Л И Л Л Задача 6.4. Даны графы (рис. 6.7 и 6.10). Требуется построить пересечение следующих графов (по вариантам): 1. G 2  G5 . 2. G3  G 4 . 3. G3  G5 . 4. G 4  G5 . 5. G3  G 4 . 6. G3  G 4 . 7. G3  G5 . 8. G5  G3 . 9. G 4  G5 . 0. G5  G 4 . 2 • 2 • 1 • 3 • G3: 2 • 6 • 3 • G4: • 4 1 • 3 • G5: • 5 • 4 Рис. 6.10 231 • 5 • 4 Задача 6.5. Даны графы (рис. 6.7 и 6.10). Требуется построить объединение следующих графов (по вариантам): 1. G 2  G5 . 2. G3  G 4 . 3. G3  G5 . 4. G 4  G5 . 5. G3  G 4 . 6. G3  G 4 . 7. G3  G5 . 8. G5  G3 . 9. G 4  G5 . 0. G5  G 4 . Задача 6.6. Даны графы (рис. 6.7 и 6.10). Требуется построить дополнение к следующим графам и записать матрицу смежности для исходного графа и его дополнения (по вариантам): 1. G5  ? 2. G 4  ? 3. G3  ? 4. G 2  ? 5. G6  ?, если G6  G 4  G3 . 6. G7  ?, если G7  G3  G5 . 7. G8  ?, если G8  G5  G3 . 8. G9  ?, если G9  G 4  G5 . 9. G10  ?, если G10  G5  G 4 . 0. G11  ?, если G11  G 2  G5 . 232