ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
1. МНОЖЕСТВА 1.1. Основные понятия Создатель теории множеств Г. Кантор определил понятие множества и элемента множества следующим образом Подмножеством мы понимаем собрание определенных отличных друг от друга объектов реальных или воображаемых, называемых элементами множества, в их общности. Обычно множества обозначают прописными буквами латинского алфавита, а их элементы — строчными буквами или числами. Количество элементов в множестве А называется мощностью множества Аи обозначается А. Если каждому элементу множества А можно поставить в соответствие единственный элемент множества В и каждому элементу множества В можно поставить в соответствие единственный элемент множества А, то множества Аи В называются равномощными и обозначаются А = В Множество, состоящее из конечного числа элементов, называется конечным. Множество, не являющееся конечным, называется бесконечным. Бесконечное множество называется счетным, если оно равномощно множеству N всех натуральных чисел. Говорят, что все элементы счетного множества можно пронумеровать. В противном случае бесконечное множество называется несчетным. Кантор доказал, что множество точек, расположенных на отрезке между 0 и 1, несчетно. Счетными являются, например, множества четных и нечетных чисел, множество целых решений неравенствах. Множество же действительных решений неравенствах является несчетным. Мощность любого счетного множества меньше мощности несчетного. (Счетными являются множества целых Z и натуральных N чисел, поэтому они равномощны Z = N ) Множество, не содержащее элементов, называется пустыми обозначается или { }. Обычно в конкретных рассуждениях элементы всех множеств берутся из некоторого одного, достаточно широкого множества U (своего для каждого случая, которое называется универсумом. Два множества Аи В называются равными, если они состоят из одних и тех же элементов (А = В. Если М — множество, а а — его элемент, то а принадлежит М а М. Если же а не есть элемент множества М, то а не принадлежит М (а М. 13 1.2. Способы задания множеств 1. Перечислением всех элементов. A = {a,b,c}, B = {b,a,c}, C = {a}, D = {1,2,3,5,9}. Из определения равенства множеств вытекает, что A = B. 2. Заданием характеристического свойства, выделяющего элементы данного множества среди элементов указанного или указанных других множеств. A = {x | x N и x < 10} (N – множество натуральных чисел, B = {1,2,3,4,5,6,7,8,9} , A = B. 3. Описанием порождающей процедуры с указанием множества (или множеств, которое пробегает параметр (или параметры) процедуры. A = {x 2 | x N} — множество всех квадратов натуральных чисел. Перечислением можно задать только конечное множество, ас помощью характеристического свойства или порождающей процедуры — конечное или бесконечное множество. 1.3. Операции надмножествами. Включение А в В (А Вили В А) истинно, если каждый элемент множества А принадлежит множеству В. В этом случае А называется подмножеством В, а В — надмножеством А. Множества Аи В равны А = В, если А В и В А. Пустое множество является подмножеством любого множества. Универсум является надмножеством любого множества. Множество всех подмножеств множества M называется булеаном и обозначается ММ Для конечного множества ММ. Каждому подмножеству А можно сопоставить разрядный двоичный вектор Св котором C i = 1, если i A и C i = 0, если i A, где i — элемент множества M, С — й разряд вектора С. Количество различных разрядных двоичных векторов равно 2 |M| , следовательно М = 2 |M| 2. Строгое включение А в В (А Вили В А) истинно, если А В и А В. Если Аи А В , то А есть собственное подмножество В. 14 3. Объединение Аи В (А Весть множество, состоящее из всех тех и только тех элементов, которые принадлежат А или В, те. А Вили. Пересечение Аи В А Весть множество, состоящее из всех тех и только тех элементов, которые принадлежат каждому из множеств Аи В, те. А В = {x | x A и x B}. 5. Разность Аи В А – Весть множество, состоящее из всех тех и только тех элементов множества А, которые не принадлежат множеству В, те. А – В = {x | x A и x B}. Для обозначения разности множеств в дискретной математике обычно используют символ ―\‖. 6. Симметрическая разность Аи В (А Весть множество, состоящее из всех тех и только тех элементов множества А, которые не принадлежат множеству В и только тех элементов множества В, которые не принадлежат множеству А, те. А В = {x | x A и x B или x В и x А. А В = А В – А В = А – В (В – А. 7. Дополнение А до универсума U ( A ) есть множество, состоящее из всех тех и только тех элементов универсума U, которые не принадлежат множеству А, те. A = {x | x А. A = U – A. Для любых двух множеств Аи В имеет место хотя бы один из следующих пяти случаев (возможностей 1) A = B, (|A| = |B|) А равно В 2) A B, (|A| |B|) А строго включено в В 3) B A, (|B| |A|) В строго включено в Аи) Аи Вне пересекаются 5) A B и A A B B, (|A B| < |A| + и < |A B| > |B|) Аи В в общем положении Если оба множества Аи Вне пусты, то имеет место только один случай На рис приведены диаграммы Эйлера Эйлер (1707—1783) предложил изображать множества в виде кругов еще до создания теории множеств Кантором (1845—1918) ), иллюстрирующие операции надмножествами. Множества изображаются фигурами (овалами, а результат выделяется графически. A B A B А = В А В A B A B А В А В А В А В А А – В А В A Рис. Операции надмножествами Выражение, составленное из некоторых, исходных, подмножеств универсума U и операций надмножествами, называется теоретико- множественным выражением. Исходные подмножества обозначаются либо именами, либо конкретными значениями. Значением теоретико- множественного выражения является подмножество универсума U. Теоретико-множественное выражение может содержать скобки, определяющие порядок выполнения операций. Если скобки не указаны, то порядок выполнения операций определяется их приоритетами (табл. Последовательность операций одного приоритета выполняется слева направо. 16 Таблица 1.1 Приоритеты операций надмножествами Название операции Обозначение Приоритет Дополнение А A 1 Пересечение Аи В А В 2 Объединение Аи В Разность Аи В Симметрическая разность Аи В А В А – В А В 3 3 3 Равенство Аи В Включение А в В Строгое включение А в В А = В А Вили В А А Вили В А 4 4 4 1.4. Свойства операций надмножествами. Идемпотентность: А А = А А А = А 2. Коммутативность А В = В А А В = В А А В = В А 3. Ассоциативность А (В С = А В С А (В С = А В С А (В С = А В С 4. Дистрибутивность для пересечения и объединения А (В С = А ВАС А (В С = А ВАС. Дистрибутивность для пересечения и разности A (B – C) = А ВАС АС. Дистрибутивность для пересечения и симметрической разности A (B C) = А ВАС. Дистрибутивность для разности (A – B) – C = (A – C) – (B – C) ( А – (В – Сне всегда равно (А – ВАС. Законы поглощения А В А = А А – В А = А А В А = А 17 9. Законы склеивания A B А B = А (A B ) (А B) = А 10. Свойства нуля А = А А = A – = A – A = A = A 11. Свойства единицы A U = U A U = A A – U = U – A = A A U = A 12. Инволютивность: A = A 13. Законы де Моргана B A = A B B A = A B 14. Законы де Моргана для разности, пересечения и объединения A – (B C) = (A – B) (A – C) A – (B C) = (A – B) (A – C) 15. Свойства дополнения A A = U A A = A A = U A – A = A 16. Определения разности A – B = A B = А B) A 17. Определения симметрической разности А В = А В – А В = А – В (В – А = А B ) (В A ) 18. Определения объединения А В=(А В (А В = А – B) B = (B – A) A 19. Определения пересечения A B = (A B) – (A B) = A – (A – B) = B – (B – A) 20. Разложение Шеннона: f (X, A 1 ,…, A n ) = X f ( , A 1 ,…, A n ) X f (U, A 1 ,…, A n ), где f (X, A 1 ,…, A n ) — теоретико-множественное выражение, содержащее множества X, A 1 ,…, A n ; f ( , A 1 ,…, A n ) — выражение, получаемое из (X, A 1 ,…, A n ) путем подстановки вместо множества X пустого множества выражение, получаемое из f (X, A 1 ,…, A n ) путем подстановки вместо множества X универсума U. 18 1.5. Нормальные формы Кантора Множество M может быть определено исходя из других, порождающих множеств M 1 , M 2 , …, M n с помощью теоретико- множественного выражения. Выражения M i и i M называют первичными термами. Пересечение попарно различных первичных термов называют элементарным. Выражение, задающее множество M в виде объединения различных элементарных пересечений, называется нормальной формой Кантора (НФК) множества M. Любое множество, которое может быть получено из порождающих множеств с помощью операций надмножествами, может быть представлено в НФК. Элементарное пересечение, содержащее все порождающие множества, называется конституентой. Любое множество, которое может быть получено из порождающих множеств с помощью операций надмножествами, может быть представлено объединением некоторого количества различных конституент. Такое представление множества называется совершенной НФК. Количество вхождений первичных термов в выражение, задающее множество, определяет сложность представления множества Минимальной НФК множества M называется НФК, имеющая минимальную сложность по отношению ко всем другим НФК этого же множества. Количество вхождений первичных термов в элементарное пересечение называется рангом пересечения. Элементарное пересечение, определяющее подмножество множества M, не являющееся надмножеством никакого другого подмножества множества M, которое может быть задано элементарным пересечением, называется простой импликантой. Можно получить все простые им- пликанты, используя совершенную НФК. Для этого необходимо выполнять всевозможные склеивания конституент, а затем элементарных пересечений меньшего ранга, пока это возможно. Элементарные пересечения, не участвовавшие в склеивании, являются простыми импликан- тами. Для сокращения количества проверок на склеивание можно использовать следующий способ. Каждую конституенту представим двоичным вектором, в котором й разряд равен 1, если конституента содержит множество M i , и равен 0, если конституента содержит дополнение множества M i , а совершенную НФК — в виде объединения двоичных векторов. Например, совершенная НФК С B A C B A C B A C B A C B A примет вид 100 011 000 110 111. Конституенты, представленные двоичными векторами, разобьем на группы. В ю группу включаем двоичные вектора, содержащие i единиц. Результат запишем в таблицу 19 Номер группы 0 1 2 3 000 100 011 111 110 Проверяем на возможность склеивания только конституенты из соседних групп. Конституенты склеиваются, если соответствующие им двоичные вектора различаются только одним м разрядом. Результат склеивания — вектор, в котором й разряд заменяется прочерком. Кон- ституенты, участвовавшие в склеивании, отмечаем крестиком справа, а результат склеивания дописываем в таблицу в соответствующую группу Номер группы 0 1 2 3 000+ 100+ 011+ 100+ 111+ –00 1–0 –11 11– Аналогично проверяем на возможность склеивания в полученной части таблицы. Склеиваются вектора, различающиеся только водном разряде (с учетом прочерка. В данном случае склеивания невозможны и все простые импликанты получены — они соответствуют неотмеченным крестиком векторам. Если в м разряде прочерк, то множество M i не записывается в простую импликанту. Объединение всех простых импли- кант образует сокращенную НФК: B A C B C A C B . Сокращенная НФК может содержать простые импликанты, исключение которых не изменяет определяемого множества. Такие простые им- пликанты называются лишними. Если из сокращенной НФК исключить все лишние простые импликанты, то получим тупиковую НФК. Тупиковых НФК может быть несколько. Для получения тупиковой НФК используют импликантную матрицу Квайна, в которой строки соответствуют простым импликантам, а столбцы — конституентам. Клетка им- пликантной матрицы на пересечении строки i и столбца j отмечается крестиком, если я импликанта покрывает ю конституенту, те. является ее составной частью. Импликантная матрица Квайна для рассматриваемого примера представлена в табл. 1.2. Тупиковой НФК соответствует минимальное покрытие столбцов строками в импликантной матрице Квайна — такое множество строк, при котором для каждого столбца найдется хотя бы одна строка из этого множества, на пересечении с которой этот столбец имеет крестик, причем при удалении хотя бы одной строки из этого множества указанное свойство не выполняется. 20 Таблица 1.2 Импликантная матрица Квайна Простые импликанты Конституенты 100 011 000 110 111 –00 + + 1–0 + + –11 + + 11– + + Для нахождения всех тупиковых НФК обозначим строки матрицы буквами a, d, c и d. Каждому столбцу поставим в соответствие объединение строк, которые его покрывают, а всей таблице — пересечение этих объединений (a b) c a (b d) (c d). Используя свойства дистрибутивности, идемпотентности и поглощения преобразуем это выражение в объединение элементарных пересечений. Каждое элементарное пересечение определяет минимальное покрытие импликантной матрицы, те. тупиковую НФК. Итак, получили две тупиковые НФК: C A C B C B и B A C B C B . Тупиковая НФК, имеющая минимальную сложность, является минимальной НФК. В данном случае тупиковые НФК имеют одинаковую сложность, поэтому обе они являются и минимальными НФК. (Если сложность оценивать количеством операций, то минимальной НФК будет только вторая из полученных тупиковых НФК ). 1.6. Преобразование теоретико-множественного выражения в нормальную форму Кантора Теоретико-множественное выражение может содержать скобки, операции разности и симметрической разности, групповые дополнения, что не соответствует НФК. Любое теоретико-множественное выражение можно преобразовать в НФК. Для этого можно выполнить следующие действия 1. Избавиться от разности и симметрической разности, используя соотношения A – B = A B А В = А B ) (В A ). 2. Последовательно избавиться от всех групповых дополнений, используя законы де Моргана B A = A B B A = A B 21 3. Используя свойство дистрибутивности, раскрыть скобки. 4. Упростить выражение, используя свойства коммутативности, идемпотентности, поглощения, дополнения, нуля и единицы. Преобразуем выражение C B A в НФК. C B A = C B A B A ) ( = C B A B A ) ( = = C B A B A ) ( = C B A B A = = C B A B A ) ( ) ( = C B B A B B A A A = = Произвольную НФК можно преобразовать в совершенную НФК. Пока в НФК есть элементарное пересечение, не являющееся конститу- ентой, заменить его двумя элементарными пересечениями большего ранга, применяя склеивание в обратном порядке А = A B А B. Затем упростить выражение, используя свойства коммутативности и идемпотентности. Преобразуем НФК C A B B A в совершенную НФК. C A B B A = A C A C C A B C A B C B A C B A = Для преобразования произвольного теоретико-множественного выражения в совершенную НФК можно использовать разложение Шенно- на по всем порождающим множествам ) ,..., , ( ) ,..., , ( 0 2 1 2 1 f M M M M M M f n n ) ,..., , ( 1 2 1 U f M M M n ::::::::::::::::::::::::::::::::::::::::: ) ,..., , ( 1 2 2 Результат будет представлять собой объединение пересечений кон- ституент с множеством f i , которое принимает значения либо U, либо Если f i = U, то конституента при f i принадлежит совершенной НФК, иначе — нет. Преобразуем выражение C B A в совершенную НФК. |