Лабораторная работа Лабораторная работа Основы теории множеств - umotnas.ru o_O
Лабораторная работа Лабораторная работа Основы теории множеств - umotnas.ru o_O
|
Похожие работы
|
Лабораторная работа Лабораторная работа Основы теории множеств - страница №6/7
Лабораторная работа 7. Индивидуальное задание 2.
Лабораторная работа 7. Элементы комбинаторики. Дополнительные методы и приемы. Краткие теоретические положения.
Пусть дано множество . Построим из него кортеж состава в котором элемент встречается , элемент - раз и т.д. элемент используется раз. Порядок элементов в составном кортеже существенен, но перестановка местами разных копий одного и того же элемента на кортеж не влияет, т.е. копии одного и того же элемента считаются неотличимыми. Общее количество использованных элементов равно . Такие кортежи называются перестановками с повторениями. Их количество вычисляется по формуле . Пример. Сколькими способами можно расставить белые фигуры: 2 ладьи, 2 слона, 2 коня, ферзь и король на первой линии шахматной доски? Решение. Рассматриваемые кортежи имеют длину 8 и состоят из элементов пяти видов. Состав кортежей имеет вид (2, 2, 2, 1, 1). Следовательно, число способов, которыми можно расставить 8 фигур на первой линии шахматной доски, равно . Данную задачу удобно понять в рамках стандартной урновой схемы: Имеется 8 различных шаров (позиций горизонтали) и 5 урн(классов фигур). Сколько способов распределить 8 различных шаров по 5 урнам так, что в первую урну(ладьи) попадает 2 шара, вторую(слоны) – также 2 и т.д. формируя распределение шаров по урнам вида (2,2,2,1,1). Наиболее точно данная комбинаторная задача специфицируется путем использования понятия функции. Искомое число это количество отображений следующего вида: Пример. Число различных слов, которое получим, переставляя буквы слова «математика», равно , так как мы распределяем 10 различных позиций слова между классами букв :‘м’, ’а, ’т’ и т.д.
Если порядок различных элементов в составном кортеже не важен, а имеет место только состав кортежа , то получаем неупорядоченные кортежи с повторениями или сочетания с повторениями. Таких сочетаний имеется Пример. В цветочном магазине продаются цветы шести сортов. Сколько можно составить различных букетов из десяти цветов в каждом? (Букеты, отличающиеся лишь расположением цветов, считаются одинаковыми.) Решение. Рассматриваемое множество состоит из шести различных элементов, а кортежи имеют длину 10. Поскольку порядок расположения цветов в букете не играет роли, то число букетов равно числу сочетаний с повторениями из шести элементов по десяти в каждом. Следовательно, можно составить = 3003 различных букетов. ПРИМЕР 8.71. Сколько решений имеет уравнение где каждое — неотрицательное целое число? Решить уравнение равносильно задаче сформировать букет из 25 цветков используя цветки 5 типов 1-5 в некоторых неотрицательных количествах . Поэтому иско-мое количество решений данного уравнения - это количество раз-личных сочетаний из 5 элементов по 25 с повторениями. Итак, существуют Пусть и - множество, упорядоченное своими индексами , т.е. считаем, что , если . Выборкой объема из множества называется отображение , т.е. - некоторый набор из элементов из множества . Выборки различаются по критерию упорядоченности и наличия повторений. Множество всех отображений обозначается через или и называется множеством упорядоченных выборок с повторениями. Отображение называется инъективным, если при выполняется неравенство . Множество всех инъективных отображений обозначается как и называется множеством выборок без повторений. Выборка с повторениями получается в результате случайного эксперимента, когда выбираемый элемент снова возвращается в генеральную совокупность и может повторно встречаться в выборке сколь угодно раз. Выборка с повторениями называется также выборкой с возращением. В выборке без повторений, т.е. если эта выборка является элементом множества каждый элемент может встречаться только один раз и такая выборка формируется в результате случайного эксперимента без возвращения выбранных объектов. Отображение называется монотонным, если из условия следует неравенство . Множество монотонных отображений обозначается . Множество монотонных отображений называется множеством неупорядоченных выборок (с повторениями), т.к. монотонность выборки означает что мы расположили объекты, полученные в случайном эксперименте в стандартном порядке возрастания, т.е. их порядок не важен и объекты могут быть взаимно переставлены, так, что получится монотонная последовательность. Отображение называется строго монотонным, если из условия следует неравенство . Множество строго монотонных отображений обозначается . Ясно, что имеет место формула . Множество называется также множеством неупорядоченных выборок без повторений. Введем следующие обозначения : - число упорядоченных выборок без повторений или число размещений из по без повторений; - число упорядоченных выборок с повторениями или число размещений из по с повторениями; - число неупорядоченных выборок без повторений или число сочетаний из по без повторений; - число неупорядоченных выборок с повторениями или число сочетаний из по с повторениями; Теорема. Имеют место равенства: ; ; ; . Различные типы выборок имеют наглядную интерпретацию как схемы размещения шаров по урнам. Упорядоченным выборкам соответствует случай, когда все шары различимы (например, пронумерованы), а неупорядоченные выборки случай, когда все шары одинаковы. Выборкам с повторениями соответствуют размещения без запрета, когда в любой ячейке может быть любое количество шаров. В случае выборок без повторений используются размещения с запретом, когда в каждом ящике может находиться не более одного шара. При этом все размещения с повторениями двух различных шаров выглядят так: А размещения с повторениями одинаковых шаров следующим образом: Для соответствующих размещений с запретом имеем следующие диаграммы: Индивидуальное задание. Решить две задачи из заданий 1,2 согласно своему номеру варианта.
Задание 1. Решить задачу на комбинаторику жизненных ситуаций.
Задание 2. Решить задачу на подсчет стандартных комбинаторных конфигураций.
Лабораторная работа 8. Бинарные отношения и действия над ними. Краткие теоретические положения. В современно науке, технике практике важнейшую роль играет понятие отношения между людьми, предметами, объектами любой природы. Известно множество подобного рода отношений: отношения родства, старшинства по службе между людьми, отношение “проживать в доме” между людьми и домами и т.д. Поэтому большой научный и практический интерес представляет математическая теория свойства “отношение” между элементами множества любо природы. Всякое отношение определяется совокупностью тех пар объектов, которые в этом отношении находятся. Поэтому, в математике используется следующее определение: Пусть X и Y- заданные множества. Отношением А между элементами X и Y называется любое подмножество AXY в декартовом произведении множеств X и Y. Множество X называется начальным множеством отношения, а Y- конечным. Пусть, например, X = {1, 2, 3}, Y={1, 2, 3, 4} и A={(1, 1), (1 2), (2,1), (3, 4), (2,3)}. Тогда множество A задает отношение между элементами множеств X и Y. Данное отношение можно выразить в виде биграфа: Отношение можно задавать также его характерным свойством. Пусть, например, X = {1, 2, 3}, Y={1, 2, 3, 4} и A1={(x,y): xX, yY, и x является делителем у}. Отношение A1- отношение делимости в множествах X и Y, можно задать и перечислением. Для этого нужно найти все пары, входящие в данное отношение. Имеем: A1={(1,1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3)}. Тот факт, что элементы x и y находятся в отношении A записывается одним из следующих способов: xAy, yA(x), (x, y) A. Если же данные элементы не находятся в отношении A, это также записывается одним из трех способов: , yA(x), (x,y) A. Например, для отношения делимости A1 имеем: 2 A14, но и . В последнем случае учитывается тот факт, что 8Y. Множество первых координат x пар (x, y), входящих в отношение A, образует область определения D(A) данного отношения, а множество вторых координат y этих пар- область значений R(A). Таким образом, D(A)={x: существует у такой, что (x, y) A}, а R(A)={y: существует x такой, что (x, y) A}. Пусть, например, X={1,2 }, Y={2, 4, 5} и xAy((xX) и (yY) и (xy)). В этом случае A={(2,2)} и D(A)={2}, R(A)={2}. Если для отношения R начальное и конечное множество совпадают : X=Y, то говорят, что отношение задано в множестве X, причем, если D(A)=X, то используется терминология “отношение определено на X”. Используются следующие типичные отношения в произвольном множестве X: 1) полное(универсальное) отношение P=XX, которое имеет место для каждой пары (x1, x2) элементов из X (например, отношение ”работать в одном отделе” на множестве сотрудников данного отдела); 2) тождественное(диагональное) отношение E, равносильное x=y(например, равенство на множестве натуральных чисел); 3) пустое отношение , которому не удовлетворяет ни одна пара элементов из X(например, отношение ”быть братом” на множестве женщин. При этом для любого отношения A в X имеет место включение AP. Рассмотрим далее некоторое отношение отношение AXY. Пусть xX. Сечением по x отношения A, обозначаемое A(x), называется множество yY таких, что (x,y) A. Всякое отношение может быть описано как множество всех сечений отношения A, которое называется фактор-множеством множества X по отношению A и обозначается X/A. Пример. Пусть, например, X={x1,x2,x3,x4,x5}, Y={y1,y2,y3,y4} и A={(x1,y1), (x1,y3), (x2,y1), (x2,y3), (x2,y4), (x3,y1), (x3,y1), (x3,y2), (x3,y4), (x4,y3), (x5,y2), (x5,y4)}. Если записать под каждым элементом из X соответствующее сечение отношения A, то элементы второй строки образуют фактор- множество Y\A: . Отношение можно задать также его матрицей (т.е. прямоугольной таблицей, составленной из чисел). На пересечении i-го столбца и j-ой строки этой матрицы ставится 1, если выполнено отношение для соответствующей пары элементов и 0, если это отношение не выполняется. Например, для отношения, рассмотренного в предыдущем пункте, матрица имеет вид: . Пусть даны три множества X, Y, Z и два отношения AXY и BYZ. Композицией отношений A и B называется отношение C, состоящее из всех тех пар (x,z)XZ, для которых существует такой элемент yY, что (x, y) A и (y, z)B. При этом сечение отношения С по элементу x вычисляется по формуле: C(x)=B(A(x)). Пример. Пусть, например, A={(x1, y2), (x1, y3), (x2, y2), (x3, y1)}- отношение в XY и B=={(y1, z1), (y2, z1), (y2, z2), (y3, z1)}- в YZ, где X = {x1,x2,x3}, Y={y1,y2,y3}, Z={z1,z2}. Вычислить композицию C данных отношений. Имеем A(x1)={y2, y3}, A(x2)={y2}, A(x3)={y1} и B(y1)={z1}, B(y2)={z1, z2}, B(y3)= {z1}. Тогда B(A(x1))= B({y2, y3})=B(y2)B(y3) = = { z1, z2}{z1}={ z1, z2}; B(A(x2))=B({y2}) ={z1, z2}; B({y1})={z1}. Таким образом, отношение характеризуется своим фактор-множеством: и матрицей . Данный результат особенно легко получить с помощью биграфого представления отношения, как показано на рисунке: Пусть AXY- некоторое отношение. По определению, обратное отношение A-1 это подмножество в Y X, состоящее из всех таких пар (y,x), что пара с переставленными элементами (x,y) принадлежит отношению A: (x,y)A. Пример. Пусть, например, X={x1,x2}, Y={y1,y2,y3} и A= {( x1,y2), ( x1,y3), ( x2,y1), ( x2,y3)}. Тогда A-1 = { ( y1,x2), ( y2,x1),( y3,x1), ( y3,x2)}. Граф отношения A-1 получается из графа отношения A обращением направлений дуг: Матрица отношения A-1 получается из матрицы отношения A c помощью операции транспонирования: Задание. Бинарные отношения на универсуме даны следующим образом: Отношение дано своей матрицей, например, , а бинарные отношения заданы перечислением своих кортежей например, следующим образом., . Найти бинарные отношения – результаты следующих операций 1) ; 2) ; 3) ; 4) ; 5) ; Сначала сформируем матрицы отношений . Имеем: , 1) Имеем: Для выполнения второй операции имеем: Таким образом, получен ответ относительно результата во втором задании: Аналогично выполняем расчет состава отношения третьего пункта. Имеем: Таким образом, нашли, что . Отсюда, далее, получаем:. Выполним задание 4). Воспользуемся свойством матрицы транспонированного отношения:, т.е. для получения матрицы обратного отношения, к матрице данного отношения нужно применить операцию транспонирования. Имеем: . При этом мы использовали определение операции транспонирования: , которое на практике означает, что для получения транспонированной матрицы строки исходной матрицы записываются столбцами. Таким образом, мы получаем состав обратного отношения и его граф:. Для выполнения пятого задания используем свойство , т.е. для получения матрицы композиции отношений нужно перемножить матрицы данных отношений. Умножение матриц выполняем по формуле Рассматривая составной переход, сначала по стрелкам отношения , а затем по стрелкам отношения Индивидуальное задание.
Они имеют следущие названия: - коньюнкция - дезъюнкция - импликация х1 в х2 - импликация х2 в х1 - равнозначность (эквивалентность) - неравнозначность (сложение по mod2) - функция Шеффера - функция Вебба (стрелка Вебба) - функция запрета х1 - функция запрета х2 - повтор х1 - инверсия х1 - повтор х2 - инверсия х2 - константа 1 - константа 0 1. Дано множество в универсуме . Найти дополнение множества . 2. Даны множества и . Найти объединение данных множеств. 3. Даны множества, , . 4.Даны множества , . 5. Даны множества , Найти симметрическую разность 6.Даны множества . Найти состав множества 7.Даны множества , , 8.Даны множества , Множество удовлетворяет уравнению Какое из следующих множеств удовлетворяет данному уравнению 9.Даны множества , Множество удовлетворяет уравнению 10 Даны множества , . Найти их декартово произведение 11.Найти мощность множества 12.Множество описано своим характерным свойством Найти мощность множества . 13.Множество описано своим характерным свойством. Найти мощность множества . 14.Даны два множества и Сколько элементов первого множества являются элементами второго. 15Дано множество . Сколько из следующих утверждений являются верными. 1) 2) 3) 4) 17 Найти состав следующего множества 18 Найти количество элементов в множестве , если 19 Дано множество Указать количество верных утверждений в следующем списке 20 Найти декартово произведение 3-х множеств Операции над множествами удовлетворяют ряду важнейших законов: 1а) AB=BA 1б) AB=BA 2a) A(BC)=(AB) C 2б) A(BC)=(AB) C 3a) A(BC)=(AB) (AC) 3б) A (BC)=(AB) (AC) 4a) A=A 4б) AE=A 5a) AAd=E 5б) AAd= 6а) A E=E 6б) A= 7a) d=E 7б) Ed= 8a) AA=A 8б) AA=A 9a) A(AB)=A 9б) A(AB)=A 10a) (AB)d=AdBd 10б) (AB)d=AdBd 11) если AB=E и AB= то A=Bd 12) Ad=E\A 13) (Ad)d=A 14) A\B=ABd 15) AB=(ABd) ( AdB) 16) AB=BA 17) (AB)C=A(BC) 18) A=A 19)AB(AB=A)(AB=B) (ABd=) 20) A=B( ABd) ( BAd). Самые важные из выписанных свойств имеют специальные названия. Так свойства 1а) и 1б) называются законами коммутативности операций объединения и пересечения множеств, свойства 2а) и 2б)- законами ассоциативности этих операций, 3а) и 3б) – их свойствами дистрибутивности одной относительно другой, 10а) и 10б)- законами де Моргана, 9а) и 9б)- теоремами поглощения. Опираясь на свойства 1)-20) можно устанавливать другие тождества и решать различные задачи по теории множеств. << предыдущая страница следующая страница >> |
|
|