ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
Теоретико-множественные тождества Цель занятия изучить методы доказательства теоретико-множествен- ных тождеств. Задания 1. На рис изображены круги Эйлера, соответствующие множествам А, В и С, с пронумерованными элементарными областями (не содержащими внутри себя других областей. Заштриховать элементарные области в соответствии с вариантом задания (см. табл. А 1 3 2 В 5 7 6 4 С Рис. Круги Эйлера, соответствующие множествам А, В и С с пронумерованными элементарными областями 2. Написать выражение 1 надмножествами А, В и С, определяющее заштрихованную область, используя операции пересечения, объединения и дополнения. 3. Используя свойства операций надмножествами, преобразовать выражение 1 в выражение 2, не содержащее операции дополнения множества. Используя свойства операций надмножествами, преобразовать выражение 2 в выражение 3, не содержащее операции объединения множеств. 52 5. Используя свойства операций надмножествами, преобразовать выражение 3 в выражение 4, не содержащее операции пересечения множеств. 6. Доказать тождественность выражений 2 и 3 методом характеристических функций. 7. Доказать тождественность выражений 2 и 4 методом логических функций. Для автоматизации доказательства написать программу, которая получает и сравнивает таблицы истинности логических функций. 8. Доказать тождественность выражений 3 и 4 теоретико-множест- венным методом. Для автоматизации доказательства написать программу, в которой вычисляются и сравниваются значения выражений 3 и 4 при Аи. Таблица 1.5 Варианты заданий Вариант Номера областей 1 1, 2, 3 2 1, 2, 4 3 1, 2, 7 4 1, 3, 4 5 1, 3, 7 6 1, 4, 6 7 1, 5, 6 8 1, 5, 7 9 1, 6, 7 10 2, 3, 4 11 2, 3, 7 12 2, 4, 6 13 2, 5, 7 14 2, 6, 7 15 3, 4, 5 16 3, 4, 6 17 3, 5, 6 18 4, 5, 6 19 4, 5, 7 20 4, 6, 7 53 Практическое занятие 1.4 Теоретико-множественные уравнения Цель занятия научиться решать теоретико-множественные уравнения с применением ЭВМ. Задания 1. Преобразовать исходное уравнение (см. Варианты заданий) в уравнение с пустой правой частью. 2. Преобразовать левую часть уравнения к виду используя разложение Шеннона по неизвестному множеству X. 3. Написать программу, вычисляющую значения множеств и при заданных исходных множествах. 4. Вычислить значения множеств и и сделать вывод о существовании решения уравнения. Если решения уравнения не существует, то выполнить п.п. 1 — 4 для следующего (предыдущего) варианта. 5. Определить мощность общего решения, найти некоторые (или все) частные решения, в том числе частные решения наименьшей и наибольшей мощности. 6. Написать программу для проверки найденных решений. Варианты заданий Вариант 1. X B X A C X B A U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {3, 4, 5, 6, 8, 10} B = {1, 2, 7, 8, 9, 10} C = {1, 2, 3, 4, 5, 10} X — ? Вариант 2. ) ( ) ( X C X A X B X A U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {3, 7, 9, 10} B = {1, 3, 8, 9, 10} C = {2, 4, 5, 6, 7} X — ? 54 Вариант 3. )) ( ( )) ( ( X C B A X C B A U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 5, 7} B = {2, 4, 6, 10} C = {1, 3, 5, 6, 8, 10} X — ? Вариант 4. )) ( ( )) ( ( X A C B X C B A U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 5, 7} B = {2, 4, 6, 10} C = {1, 3, 5, 6, 8, 10} X — ? Вариант 5. C B X B X X A ) ( U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {2, 3, 4, 7, 10} B = {1, 2, 6, 9} C = {3, 5, 7, 9} X — ? Вариант 6. C B X A X X C B X A ) ( ) ( ) ( ) ( U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {4, 8, 9} B = {1, 2, 4, 6, 8, 9} C = {4, 5, 7, 9} X — ? Вариант 7. ) ( ) ( ) ( X C X A C B X A X U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {2, 9, 10} B = {1, 2, 8, 9, 10} C = {1, 3, 6, 7} X — ? 55 Вариант 8. B A X C B X A X U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {3, 4, 5, 6, 10} B = {1, 2, 3, 7, 9} C = {3, 4, 5, 8, 10} X — ? Вариант 9. ) ( ) ( ) ( X C X A C X B X A U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 3, 5, 6, 8} B = {2, 4, 6, 9} C = {2, 6, 7, 10} X — ? Вариант 10. X C X B A C X B A ) ( ) ( U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {4, 5, 7, 8, 9, 10} B = {2, 3, 4, 5, 6, 10} C = {4, 5, 7, 8, 10} X — ? Вариант 11. X B X A A C X B ) ( ) ( U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 3, 6, 7, 8, 10} B = {1, 3, 4, 5, 9} C = {1, 3, 6, 7, 10} X — ? Вариант 12. ) ( X C B A X C B A U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 4, 10} B = {3, 5, 6, 7} C = {3, 6, 7, 10} X — ? 56 Вариант 13. ) ( X C B A C X X B A U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {2, 3, 9, 10} B = {1, 5, 8} C = {4, 5, 7} X — ? Вариант 14. ) ( ) ( X A X C C X B X A U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 4, 8} B = {1, 5, 7, 10} C = {3, 6, 7, 10} X — ? Вариант 15. C X A X X C B X A ) ( ) ( ) ( U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 2, 5, 8, 9} B = {1, 2, 6, 7, 9, 10} C = {2, 4, 6, 9, 10} X — ? Вариант 16. ) ( X A X B A C X B U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 3, 6, 7, 8, 10} B = {1, 3, 4, 5, 9} C = {1, 3, 6, 7, 10} X — ? Вариант 17. X B X A X A X C ) ( ) ( U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {3, 7, 9, 10} B = {1, 3, 8, 9, 10} C = {2, 4, 5, 6, 7} X — ? 57 Контрольные вопросы и задания 1. Дать определение понятиям — множество, элемент множества — конечное множество, мощность множества — бесконечное, счетное и несчетное множество — пустое множество, универсум — подмножество, собственное подмножество — булеан, операции надмножествами. Привести примеры задания множества различными способами. 3. Проиллюстрировать операции надмножествами и свойства операций диаграммами Эйлера. 4. Вычислить значение теоретико-множественного выражения. 5. Определить количество подмножеств заданного множества. 6. Дать определение понятиям — первичный терм — элементарное пересечение — нормальная форма кантора — конституента; — совершенная НФК; — простая импликанта; — сокращенная НФК; — тупиковая НФК; — минимальная НФК. 7. Как получить сокращенную НФК? 8. Что такое импликантная матрица Квайна? Для чего она используется. Доказать теоретико-множественное тождество различными методами. Дать определение теоретико-множественному уравнению. 11. Что такое частное и общее решение теоретико-множественного уравнения 12. Что является условием существования решения теоретико- множественного уравнения 13. Как определить мощность общего решения теоретико-множест- венного уравнения 14. Сравнить способы представления множества в памяти ЭВМ объем памяти, время выполнения операций. 15. Программно реализовать заданную операцию надмножествами при заданном способе представления множества в памяти ЭВМ. 16. Изменить алгоритмы 1.19 и 1.20, используя логические операции вместо операций сравнения. 58 2. КОМБИНАТОРНЫЕ ОБЪЕКТЫ 2.1. Введение Под комбинаторным объектом будем понимать набор, составленный из элементов множества и обладающий свойством, определяющим заданный комбинаторный объект. Основными простейшими комбинаторными объектами являются подмножество, перестановка, размещение, сочетание, разбиение. При изучении комбинаторного объекта необходимо — подсчитать количество всех различных комбинаторных объектов заданного типа (обладающих заданным свойством, которые можно составить из элементов заданного множества — определить способ (алгоритм) получения всех различных комбинаторных объектов заданного типа, которые можно составить из элементов заданного множества. При подсчете количества всех различных комбинаторных объектов заданного типа часто применяется правило произведения, которое заключается в следующем. Пусть требуется выполнить одно за другим K действий. Если первое действие можно выполнить N 1 способами, второе действие — способами, третье действие — N 3 способами итак до го действия, которое можно выполнить N k способами, то все K действий могут быть выполнены N 1 N 2 N 3 … N k способами 2.2. Метод поиска с возвращением Пусть задача имеет множество решений, каждое из которых можно представить последовательностью R конечной, нов общем случае, неопределенной длины, состоящей из элементов, принадлежащих некоторому множеству Аи требуется найти все решения задачи. Их можно найти, используя метод поиска с возвращением, который заключается в следующем. Для получения одного решения будем последовательно, элемент за элементом, формировать последовательность R. Сначала определим подмножество элементов множества А, которые можно поставить на е место и один из них поставим на е место. Затем, по аналогии, будем определять и ставить элементы на ее итак далее место, продвигаясь по последовательности R вперед, те. делать шаги вперед. Так, двигаясь вперед, на некотором м шаге мы либо получим одно из решений (случай 1), либо обнаружим, что во множестве А нет ни одного элемента, который можно поставить на очередное место, не нарушая условие задачи (случай 2). Случай 2 означает, что ни одно решение задачи не содержит в качестве первых i – 1 элементов элементы, поставленные в последовательность R. В этой ситуации нужно сделать шаг назад, к i – 1-му месту и попытаться поставить другой допустимый элемент на i – е место. В случае 1, когда решение получено, для продолжения поиска других решений необходимо попытаться поставить другой допустимый элемент на е место, а если такого элемента нетто нужно сделать шаг назад. Если нужно выполнить шаг назад тогда, когда находимся нам месте в последовательности R, то поиск решений прекращается, все решения найдены. Метод поиска с возвращением можно реализовать на ЭВМ, используя рекурсивный или итеративный алгоритмы, структуры которых представлены на рис и 2.2 соответственно. + Рис. Рекурсивный алгоритм поиска с возвращением Поиск с возвращением (i) М R i := x Решение получено Выход (шаг назад к i–1) Шаг вперед к i+1 Поиск с возвращением (i+1) R М := множество элементов, которые можно поставить на е место 60 + + Рис. Итеративный алгоритм поиска с возвращением Решение получено Начало Инициализация стека Множество элементов, которые можно поставить на е место, положить в стек. i := 1 i > 0 М := взять из стека M ≠ R i := x | x M M–{x} в стек Шаг вперед i := i+1 Множество элементов, которые можно поставить на е место, положить в стек. Шаг назад i := i–1 Конец 61 Рекурсивная подпрограмма формирует й элемент последовательности, поэтому при первом обращении к ней нужно передать параметр, равный 1. Метод поиска с возвращением можно также использовать, если требуется определить, существует ли решение задачи, подсчитать количество возможных решений или найти одно из возможных решений. 2.3. Подмножества Множество А называется подмножеством множества В, если истинно включение А в В (А В = истина. Теорема 2.1. Количество всех различных подмножеств элементного множества равно Доказательство. Поставим в соответствие каждому подмножеству А множества В разрядный двоичный вектор, й разряд которого равен единице только тогда, когда й элемент множества В принадлежит подмножеству А. Для того, чтобы сформировать разрядный двоичный вектор, нужно выполнить одно за другим n действий заполнить й разряд вектора, й разряди так до го разряда. Каждое действие можно выполнить двумя способами (разряд двоичного вектора можно заполнить только нулем или единицей. По правилу произведения все n действий могут быть выполнены 2 2 … 2=2 n способами, те. может быть получено 2 n различных разрядных двоичных векторов, следовательно, количество всех различных подмножеств элементного множества равно Для получения (порождения) всех подмножеств заданного множества В достаточно сформировать все двоичные вектора, разрядность которых равна n=|B|. Можно сформировать все двоичные разрядные вектора, используя метод поиска с возвращением, выполняя действия, описанные в доказательстве теоремы 2.1. Формирование го разряда опишем рекурсивным алгоритмом 2.1, блок-схема которого представлена на рис. В цикле выполняем один из способов заполнения го разряда. Если заполнен последний разряд, то вектор сформирован и выводим его, иначе заполняем следующий разряд по алгоритму 2.1. Алгоритм 2.1 порождения разрядных двоичных векторов. Вход i — формируемый разряд вектора D. Выход последовательность всех разрядных двоичных векторов. Глобальные параметры D — формируемый вектор n — разрядность вектора. 62 + Рис. Рекурсивный алгоритм порождения разрядных двоичных векторов Пусть задано множество {1,2,3} и требуется получить все его подмножества. Схема получения всех двоичных трехразрядных векторов по алгоритму 2.1 и соответствующих им подмножеств заданного множества представлена на рис. Самый правый (первый) разряд вектора соответствует элементу 1, средний (второй) — элементу 2, самый левый третий) — элементу 3. В исходной ситуации все разряды двоичного вектора неопределенны. В схеме к стрелкам приписаны номера действий. После последовательного выполнения действий 1, 2 и 3 заполняются нулями третий, второй и первый разряды и вектор (0,0,0), соответствующий пустому подмножеству, сформирован. После выполнения действия заполняется единицей первый разряди вектор (0,0,1), соответствующий подмножеству {1}, сформирован. Затем выполняются два шага назад и действие 5, заполняющее единицей второй разряд вектора. Далее, после выполнения действия 6, заполняется нулем первый разряди вектор (0,1,0), соответствующий подмножеству {2}, сформирован. Аналогичным образом формируются все остальные двоичные вектора. Действия и 8 заполняют третий разряд вектора, действия 2, 5, 9, 12 — второй разряд, действия 3, 4, 6, 7, 10, 11, 13, 14 — первый разряд. Двоичные вектора (i) x := 0,1 D i := x Конец Двоичные вектора (i+1) D 63 вектор (0,0,0) 3 подмножество вектор (0,0,?) 4 вектор 2 (0,0,1) подмножество вектор {1} (0,?,?) вектор 5 (0,1,0) 6 подмножество 1 {2} вектор (0,1,?) 7 вектор (0,1,1) подмножество {2,1} вектор (?,?,?) вектор (1,0,0) 8 10 подмножество {3} вектор (1,0,?) 11 вектор 9 (1,0,1) подмножество вектор {3 , 1} (1,?,?) 12 вектор (1,1,0) 13 подмножество {3,2} вектор (1,1,?) 14 вектор (1,1,1) подмножество {3,2,1} Рис. Схема порождения двоичных векторов по алгоритму 2.1 64 2.4. Перестановки Перестановкой называется расположенные в определенном порядке элементы множества М. Теорема 2.2. Количество всех различных перестановок элементного множества М (количество способов упорядочивания множества) определяется формулой Р = n!. Доказательство Перестановку можно представить последовательностью из n мест. Для того чтобы получить одну перестановку, нужно выполнить одно за другим n действий заполнить е место в последовательности, е место итак до го места. Для выполнения го действия заполнения го места) можно взять любой элемент из множества Ми поставить его на е место, те. его можно выполнить способами, и после этого в множестве М останется n – 1 элемент. Для выполнения го действия (заполнения го места) можно взять любой элемент из оставшихся в множестве Ми поставить его на е место, те. его можно выполнить n – способами, и после этого в множестве М останется n - 2 элемента и т.д. По правилу произведения все n действий могут быть выполнены n (n – 1) (n – 2) ... 2 1 = n! способами,следовательно, количество всех различных перестановок элементного множества равно n!. Получить все перестановки элементного множества М можно, используя метод поиска с возвращением, выполняя действия, описанные в доказательстве теоремы 2.2. Формирование го элемента перестановки опишем рекурсивным алгоритмом 2.2, блок-схема которого представлена на рис. В цикле перебираются элементы множества М, которые можно поставить на е место. Если заполнено последнее место, топе- рестановка сформирована и выводим ее, иначе заполняем следующее i + е место по алгоритму 2.2 элементами множества М, за исключением элемента, поставленного на е место. Алгоритм 2.2 порождения перестановок элементного множества. Вход М — множество, элементы которого можно поставить на е место заполняемое место в последовательности Р. Выход последовательность всех перестановок элементного множества. Глобальные параметры Р — формируемая перестановка n — мощность множества. 65 + Рис. Рекурсивный алгоритм порождения перестановок элементного множества Пусть задано множество {1,2,3} и требуется получить все его перестановки. Схема получения всех перестановок по алгоритму 2.2 представлена на рис. В этой схеме представлены формируемые перестановки и множества, элементы которых можно поставить на очередное место в перестановке. В исходной ситуации все места перестановки неопределенны и любой элемент множества {1,2,3} можно поставить на первое место. В схеме к стрелкам приписаны номера действий. В результате выполнения действия 1 на первое место перестановки устанавливается элемента на второе место после этого можно поставить любой элемент множества {2,3}. После выполнения действия 2 на второе место перестановки устанавливается элемента на третье место после этого можно поставить только элемент множества {3} (действие 3) и первая перестановка (1,2,3) сформирована. Затем выполняются два шага назад и действие 4, ставящее элемент 3 из множества {2,3} на второе место. Далее действие 5 ставит оставшийся элемент 2 на третье место и вторая перестановка (1,3,2) сформирована. Аналогичным образом формируются все остальные перестановки. Действия 1, 6 и 11 заполняют первое место перестановки, действия 2, 4, 7, 9, 12 и 14 — второе место, действия 3, 5, 8, 10, 13 и 15 — третье место. Перестановка (ММ Р := x Конец Перестановка(М – {x},i+1) Р 66 множество множество {3} 3 перестановка перестановка (1,2,?) (1,2,3) 2 множество {2,3} перестановка (1,?,?) 4 множество множество {2} 5 перестановка перестановка (1,3,?) (1,3,2) 1 множество множество {3} 8 перестановка перестановка (2,1,?) (2,1,3) 7 множество множество {1,2,3} 6 {1,3} перестановка перестановка (?,?,?) (2,?,?) 9 множество множество {1} 10 перестановка перестановка (2,3,?) (2,3,1) 11 множество множество {2} 13 перестановка перестановка (3,1,?) (3,1,2) 12 множество {1,2} перестановка (3,?,?) 14 множество множество {1} 15 перестановка перестановка (3,2,?) (3,2,1) Рис. Схема получения всех перестановок по алгоритму 2.2 |