Покрытие и разбиение множеств - раздел Философия, Курс лекций По дисциплине ДИСКРЕТНАЯ МАТЕМАТИКА Разбиением Множества А Называется Се...
Разбиением множества А называется семейство Аiнепустых и различных подмножеств А, таких, что и для всех (i ≠ j). Множества Ai называютсяклассами разбиения.
Пример. Разбиения множества А = {1, 2, 3. 4}. {1, 2}, {3, 4} и {1}, {2, 4}, {3}. Все объединения разбиений дают множество А, а все их пересечения пусты.
Если множество А представляет собой объединение подмножеств А1, А2, ..., Аn ..., то совокупность подмножеств {А1, А2, ..., Ап, ...} называется покрытием множества А.
Пусть - некоторое семейство подмножеств множества M и . Семейство называется покрытием множества M, если каждый элемент его принадлежит хотя бы одному из :
Семейство называется дизъюнктным если элементы этого семейства попарно не пересекаются, т.е. каждый элемент множества M принадлежит не более чем одному из множеств :
Дизъюнктное покрытие называется разбиением множества M.
Если же совокупность подмножеств покрытия множества А такова, что при i ≠ j, то совокупность {А1, А2, ..., Ап, ...} называется разбиением множества А, а подмножества Аi— классами этого разбиения, (i = 1, 2, ... ,n, ...).
Пример
Пусть А — множество всех студентов МГСУ, которые его закончили, а Аi — подмножество тех студентов МГСУ, которые закончили i-й факультет этого вуза.
Поскольку не исключена возможность, что некто из множества студентов А закончил несколько факультетов данного вуза, и такой человек попадает в несколько соответствующих подмножеств совокупности, то ясно, что совокупность подмножеств А1, А2, …,Ak, является покрытием множества А.
Если же взять совокупностьвсех студентов МГСУ, которые учатся в данное время, то совокупность студентов А1, А2, …,Ak` является, очевидно, разбиением множества всех студентов данного вуза, которые учатся в данное время.
Если все рассматриваемые множества являются подмножествами некоторого множества U, то это множество называютуниверсальным множеством.
Пример. Для арифметики универсальным множеством служит множество действительных чисел, так как натуральные, целые и рациональнее числа являются его подмножествами.
Рассмотрим два конечных множества А и В с числом элементов т и п. Между этими числами возможно одно из трех соотношений: т = п; т < п; т > п. Вопрос о том, какое из них имеет место, решается просто: подсчетом количества элементов А и В. Однако можно поступить иначе, не считая эти элементы. Для этого между элементами множеств А, В необходимо попытаться установить взаимно однозначное соответствие, при котором каждому элементу множества А отвечает один и только один элемент множества В и, наоборот, каждому элементу множества В соответствует один и только один элемент множества А.
Иными словами, каждому элементу множества А необходимо «поставить в пару» элемент множества В. Такое соответствие можно установить тогда и только тогда, когда число элементов в этих множествах одинаковое, т.е. т = п. Когда же после «постановки в пару» остались элементы множества В, то т < п. Если же полностью исчерпаны элементы В и остались лишние элементы множества А, то т > п.
Пример. Проверить, одинаково ли число студентов в группе и стульев в аудитории, можно не пересчитывая тех и других, посадить каждого студента на определенный стул. Если мест хватит всем и не останется ни одного лишнего стула, то тем самым будет установлено взаимно однозначное соответствие и, следовательно, равенство элементов в множествах студентов и стульев.
Если между элементами двух различных множеств А и В можно установить взаимно однозначное соответствие по любому закону, то эти множества называютсяэквивалентными, или равномощными. Это записывается так: А = В.
Характерно, что установление взаимно однозначного соответствия между элементами множеств пригодно для сравнениянетолько конечных множеств, но и бесконечных.
Приведем примеры эквивалентных бесконечных множеств. Множество всех натуральных чисел эквивалентно множеству всех четных чисел, так как каждому натуральному числу п соответствует одно и только одно четное число 2n, и каждому числу 2n соответствует его половина, являющаяся натуральным числом. Множество всех целых чисел эквивалентно множеству натуральных чисел. Соответствие между целыми и натуральными числами устанавливается по следующей схеме:
0,-1, 1.-2.2...
1, 2, 3, 4, 5,..., т.е. неотрицательному числу п > 0 ставится в соответствие нечетное число 2n + 1, а отрицательному п < 0- четное число 2 ׀n׀ .
Счетным множеством называется всякое множество, элементы которого можно поставить во взаимно однозначное соответствие со всеми числами натурального ряда. Иначе говоря, счетное множество — это такое множество, элементы которого можно последовательно пронумеровать числами натурального ряда. Приведенные выше примеры множеств четных и целых чисел являются счетными множествами,
Множество называется счетным, если оно эквивалентно множеству натуральных чисел.
Если эквивалентны между собой два конечных множества, то, как указывалось выше, они состоят из одинакового числа элементов.
Эквивалентные между собой бесконечные множества называются множествамиравной мощности.
Частично упорядоченные множества
Алгебраическое понятие решетки тесно связано с отношением порядка, заданным на конечном множестве, и может быть определено следующим образом.
Определение: Множество S называется частично упорядоченным (ЧУМ), если на нем задано рефлексивное, транзитивной и антисимметричное бинарное отношение частичного порядка с.
Определение: ЧУМ называется линейно упорядоченным (цепью), если для любых x,y ∈ S или x ≤ y, или y ≤ x, либо выполняются оба эти отношения (x = y).
Любое конечное, линейно упорядоченное множество (A, ≤) можно представить следующим образом: a1 ≤ a2 ≤ a3 ≤. . .≤ an. Мы можем также записать A как (a1, a2, . . ., an). Линейно упорядоченное множество можно изобразить графически диаграммой, в которой элементам множества соответствуют вершины. Из вершины а ведет дуга в вершину b, если a ≤ b и нет такого с, что a ≤ c ≤ b. Конечному линейно упорядоченному множеству (A, ≤) соответствует диаграмма вида (рис. 3.1)
Рис. 3.1.
На таких диаграммах не принято изображать петли, отображающие рефлексивность отношения ≤, и дуги, отображающие транзитивность этого отношения.
Утверждение: Частичное упорядочение на конечном множестве может быть представлено как объединение отношений линейного порядка на некоторых подмножествах данного множества
Любой частичный порядок можно представить изображением объединения множества диаграмм соответствующих линейно упорядоченных подмножеств. Полученная таким образом диаграмма называется диаграммой Хасса.
Рис. 3.2.
Пример 6.1.
Пусть на множестве S={1,2,3,4,6,10,12,20} задано отношение с={(x, y):х делитель y}. Выделим все линейно упорядоченные подмножества S: (1, 3, 6, 12), (1, 2, 6, 12), (1, 2, 4, 12), (1, 2, 4, 20), (1, 2, 10, 20). Объединение диаграмм, построенных для этих подмножеств, дает диаграмму Хассе, показанную на рис. 3.2. Если задано (S, ≤)и B – подмножество S: B ⊆ S, можно определить верхнюю и нижнюю грани подмножества В.
Определение: Верхней гранью двухэлементного подмножества B={a,b}, a,b ∈ S, называется элемент h ∈ S, такой, что a ≤ h, b ≤ h. Соответственно,
нижней гранью двухэлементного подмножества B={a, b}, a, b ∈ S, называется элемент l ∈ S, такой, что l ≤ a, l ≤ b.
Определение: Если некоторая из верхних граней H подмножества B={a,b} удовлетворяет неравенству H ≤ h, где h - произвольная верхняя грань подмножества B={a,b}, то ее называют наименьшей верхней гранью (supremum) подмножества B и обозначают H = sup ({a,b}). Соответственно, если некоторая из нижних граней L подмножества B = {a, b} удовлетворяет неравенству l ≤ L, где l - произвольная нижняя грань, то ее называют наибольшей нижней гранью (infimum) подмножества B и обозначают L = inf ({a,b}).
Введенные понятия хорошо иллюстрируются на языке диаграмм Хассе:
x ≤ y , если и только если на диаграмме существует путь из вершины x в вершину y; верхняя грань подмножества B={a,b} на диаграмме соответствует вершине, в которую есть путь как из a, так и из b; нижняя грань подмножества B={a,b} соответствует вершине, из которой есть путь как в a, так и в b.
Пример 6.2.
Рассмотрим ЧУМ, представленное диаграммой Хассе на рис. 6.2. Подмножество B={3,6} имеет две верхние грани: h1=6 и h2=12, одна из которых является наименьшей: H=sup({3,6})=h1=6. Это же подмножество имеет две нижние грани:l1=1 и l2=3, одна из которых является наибольшей: L=inf({3,6})=l2=3. Подмножество B={6,4} имеет одну верхнюю грань h1=12, которая, естественно, будет наименьшей верхней гранью H=sup ({6,4})=12, и две нижние грани l1=2, l2=1, одна из которых будет наибольшей: L=inf ({6,4})=l1= 2. Подмножество B={6,10} имеет те же две нижние грани l1=2, l2=1 и ту же наибольшую нижнюю грань L=inf ({6,10})=l1= 2, однако не имеет ни одной верхней грани
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ... ИНСТИТУТ ЭКОНОМИКИ УПРАВЛЕНИЯ И ИНФОРМАЦИОННЫХ СИСТЕМ В СТРОИТЕЛЬСТВЕ... ИЭУИС...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Покрытие и разбиение множеств
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Предмет дискретной математики
Предмет дискретная (финитная, конечная) математика – направление математики, изучающее свойства дискретных структур, в то время как классическая (непрерывная) математика изучает свойства объ
Изоморфизм
Наука, изучающая алгебраические операции называется алгеброй. Это понятие по мере изучения курса будет конкретизироваться и углубляться. Алгебру интересует только вопрос, КАК действуе
Упражнения
1. Докажите, что изоморфное отображение всегда изотонно, а обратное утверждение неверно.
2. Запишите на языке множеств свою группу.
3. Запишите на языке множеств предметы, которые
Множество и элементы множества
В настоящее время существующие теории множеств различаются парадигматикой (системой взглядов) концептуального базиса и логических средств. Так, в качестве примера, можем привести две противоположны
Конечные и бесконечные множества
То, из чего состоит множество, т.е. объекты, образующие множество, называется его элементами. Элементы множества различны и отличаются друг от друга.
Как видно из приведенных пример
Мощность множества
Мощность для конечного множества равна числу его элементов. Например, мощность универсума В(A) множества A мощностью n
Подмножество, собственное подмножество
После того как введено понятие множества, возникает задача конструирования новых множеств из уже имеющихся, то есть определить операции над множествами.
Множество М',
Символический язык содержательных теорий множеств
В процессе изучения курса будем различать объектный язык теории множеств и метаязык, средствами которого изучается объектный язык.
Под языком теории множеств будем понимать реляцион
Ограниченные множества. Границы множеств
Пусть на некотором множестве X задана числовая функция f(х).
Верхней гранью (границей) функции f(х) называется такое число
Точная верхняя (нижняя) граница
Совокупность всех верхних границ Е обозначается через Еs, всех нижних границ - через Еi. В случа
Множество с атрибутивной точки зрения
Агрегатная точка зрения, в отличие от атрибутивной, является логически несостоятельной в том плане, что она приводит к парадоксам типа Рассела и Кантора (см. ниже).
В рамках атрибутивной т
Структура
Частично упорядоченное множество X называется структурой, если в нем любое двухэлементное множество
Бинарные отношения
Последовательность длины п, члены которой суть а1, .... аn, будем обозначать через {а1, .... а
Свойства бинарных отношений
Бинарное отношение R на множестве Хобладает следующими свойствами:
(а) рефлексивно, если хRх
Частично упорядоченные множества
Множество S называется частично упорядоченным (ЧУМ), если на нем задано рефлексивное, транзитивной и антисимметричное бинарное отношение частичного порядка
Перестановки
Дано множество A. Пусть A – конечное множество, состоящее из n элементов A = {a1, a2, …, a
Перестановки с повторениями
Пусть в множестве A имеются одинаковые (повторяющиеся) элементы. Перестановкой с повторениями состава (n1, n2, … ,nk
Размещения
Кортежи длины k (1≤k≤n), состоящие из различных элементов n-элементного множества A (кортежи отличаются од
Размещения с повторениями
Пусть во множестве A имеются одинаковые (повторяющиеся) элементы. Размещениями с повторениями из n элементов по k назы
Упорядоченное размещение
Разместим п объектов по m ящикам так, чтобы каждый ящик содержал бы последовательность, а не множество, как прежде, помещенных в нем объектов. Два
Сочетания
Из m-элементного множества A построим упорядоченное множество длины n, элементы которого являются размещениями с одними и тем
Сочетания с повторениями
Полученные формулы справедливы только, когда в множестве A нет одинаковых элементов. Пусть имеются элементы n видов и из них составляется кортеж из
Метод производящий функций
Этот метод используется для перечисления комбинаторных чисел и установления комбинаторных тождеств.
Исходным пунктом являются последовательность {ai} комбинатор
Алгебраическая система
Алгебраической системой A называется совокупность ‹M,O,R›, первая составляющая которой M есть непустое множество, вторая компонента O – множество
Алгебры с одной бинарной операцией
Пусть на множестве М задана одна бинарная операция. Рассмотрим порождаемые ею алгебры, но предварительно рассмотрим некоторые свойства бинарных операций.
Бинарная о
Группоид
Алгебра вида <М, f2>называется группоидом.
Если f2 — операция типа умножения (
Фактор-множества и фактор-алгебра
Если отношение R обладает свойствами: рефлексивное симметричное транзитивное, т.е. является отношением эквивалентности (~ или ≡ или Е) на множестве M
Конгруэнции
Конгруэнцией на алгебре A = <A; Σ> (Σ – сигнатура алгебры состоит только из функциональных символов) называется такое отношение эквивалентности
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Графы - математические объекты.
Теория графов применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электротехника, машиностроение, архитектура, исследование о
Граф, вершина, ребро
Под неориентированным графом (или короче графом) будем понимать такую произвольную пару G = <V, E>, что
Соответствие
Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, ко
Неориентированный граф
Если ребра не имеют ориентации, то граф называется неориентированным (неориентированный дубликат или неориен
Инцидентность, смешанный граф
Если ребро е имеет вид {и, v } или <и, v>, то будем говорить, что ребро е инцидентно вер
Связность
Две вершины в графе называются связным, если существует соединяющая их простая цепь. Граф называется связным, если все его вершины связны.
Теорема.
Граф со взвешенными дугами
Граф G = (N, A) называется взвешенным, если на множестве дуг A определена некоторая функция l: A → R, которую на
Матрица сильной связности.
Матрица сильной связности: по диагонали ставим 1; заполняем строку X1 - если вершина достижима из X1 и X1 д
ДЕРЕВЬЯ
Деревья важны не только потому, что они находят приложения в различных областях знаний, но и Вилу особого положения их в самой теории графов. Последнее вызвано предельной простотой строения деревье
Теорема
Центр свободного дерева состоит из одной вершины или из двух смежных вершин:
Z(G) = 0&k(G) = 1 → С(G) = К1
Ориентированные, упорядоченные и бинарные деревья
Ориентированные (упорядоченные) деревья являются абстракцией иерархических отношений, которые очень часто встречаются как в практической жизни, так и в математике и программировании. Дерево (ориент
Доказательство
1. Каждая дуга входит в какой-то узел. Из п. 2 определения 9.2.1 имеем:
v
Упорядоченные деревья
Множества Т1,.. ., Тk в эквивалентном определении ордерева являются поддеревьями. Если относительный порядок поддеревьев Т1,.. .,
Бинарные деревья
Бинарное (или двоичное) дерево - это конечное множество узлов, которое либо пусто, либо состоит из корня и двух непересекающихся бинарных деревьев - левого и правого.
Бинарное дерево не яв
Представление свободных деревьев
Для представления деревьев можно использовать те же приёмы, что и для представления графов общего вида — матрицы смежности и инциденций, списки смежности и другие. Но используя особенные свойства д
End for
Обоснование
Код Прюфера действительно является представлением свободного дерева. Чтобы убедиться в этом, покажем, что если Т' — дерево
Представление бинарных деревьев
Всякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить. Для потомков одного узла (братьев) упорядоченного ордерева определено отно
Основные логические функции
Обозначим через E2 = {0, 1} – множество, состоящее из двух чисел. Числа 0 и 1 являются основными в дискретной мате
Булева функция.
Булевой функцией от n аргументов x1, x2, … ,xn, называется функция f из n-ой степени множества
Таблицы булевых функций
Булева функция от n переменных может быть задана таблицей, состоящей из двух столбцов и 2n строк. В первом столбце перечисляются все наборы из B
Порядок выполнения операций
Если в сложном выражении скобок нет, то операции надо выполнять в следующем порядке: конъюнкция, дизъюнкция, импликация, эквивалентность, отрицание.
Соглашения относительно расстановки ско
Эквивалентность формул
Различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие эквивалентности формул.
Формулы φ(x1,..., xn) и
Замечание
1. Формула φ тождественно ложна тогда и только тогда, когда неφ тождественно истинна (|=неφ );
2. Формула φ
Фактор-алгебра алгебры формул
Обозначим через Фn множество всех формул алгебры логики с переменными из множества {х1, х2, ... , хn}.
Определение
Если х — логическая переменная, , то выражение
Алгоритм приведения формулы к ДНФ.
1. Выразить все логические операции, участвующие в построении формулы, через дизъюнкции, конъюнкции и отрицания, используя эквивалентности
Первая теорема Шеннона
Для решения задачи нахождения СДНФ и СКНФ, эквивалентных исходной формуле φ, предварительно рассмотрим разложения булевой функции f(x1, х2
Вторая теорема Шеннона
В силу принципа двойственности для булевых алгебр справедлива
Теорема 6.4.3 (вторая теорема Шеннона). Любая булева функция f(x1, х2,...
Функциональная полнота
Теорема(о функциональной полноте). Для любой булевой функции f найдется формула φ, представляющая функцию f
Алгоритм нахождения СДНФ.
Для нахождения СДНФ данную формулу нужно привести сначала к ДНФ, а затем преобразовать ее конъюнкты в конституенты единицы с помощью следующих действий:
а) если в конъюнкт входит некоторая
Метод Квайна
Рассмотрим метод Квайна для нахождения МДНФ, представляющей данную булеву функцию. Определим следующие триоперации:
- операция полного склеивания -
Каноническое представление логических функций
Каноническими формами логических (формул) функций называются выражения, имеющие стандартную форму булевой формулы такой, которая однозначно представляет логическую функцию.
В алгебр
Системы булевых функций
Пусть даны булевы функции f(g1, g2, …, gm) и g1(x1, x2, …, xn), g2(x1
Базис Жегалкина.
Примерю Рассмотрим систему . Она является полной, так как любая функция из стандартного базиса выражается чере
Теорема Поста
Теорема Поста устанавливает необходимые и достаточные условия полноты системы булевых функций.
(Post E.L. The two-valued interactive systems of mathematical logic. – Annals of Math. Stu
Алгебра Жегалкина
Сумма по модулю 2, конъюнкция и константы 0 и 1 образуют функционально полную систему, т.е. образуют алгебру - алгебру Жегалкина.
A = <FB,
ЛОГИКА ВЫСКАЗЫВАНИЙ
Математическая логика изучает базовые понятия синтаксиса (формы) и семантики (содержания) естественного языка. Рассмотрим три крупных направления исследований в математической логике — логику
Определение предиката
Пусть Х1, Х2, ..., Хп произвольные переменные. Эти переменные будем называть предметными. Пусть наборы переменных вы
Применение предикатов в алгебре
Рассмотрим предикаты, в которых свободной является лишь одна переменная, которую обозначим через х, и обсудим применение предикатов в алгебре.
Типичным приме
Булева алгебра предикатов
Так как к предикатам можно применять логические операции, то для них справедливы основные законы булевой алгебры.
Теорема. (Свойства логических операций для предикатов).
Мн
Исчисление предикатов
Исчисление предикатов называют еще теорий первого порядка.
В исчислении предикатов, так же как и в исчислении высказываний, на первом по важности месте стоит проблема разрешимост
Следование и эквиваленция
Высказывательная форма Q2 следует из высказывательной формы Q1, если импликация Q1→Q2 обращается в истинное выс
Принятые обозначения
Символы «порядка не более». При сравнении скорости роста двух функций f(n) и g(n) (с неотрицательными значениями) очень удобны следующи
непустых и различных подмножеств А, таких, что 
и 
для всех 
(i ≠ j). Множества Ai называютсяклассами разбиения.
- некоторое семейство подмножеств множества M и 
. Семейство 
называется покрытием множества M, если каждый элемент его принадлежит хотя бы одному из 
:
:
Новости и инфо для студентов