Дискретная математика_коллоквиум. Множество совокупность элементов объединенных некоторыми свойствами или признаками
 Скачать 14.86 Kb.
|
|
МНОЖЕСТВА и тд Множество совокупность элементов объединенных некоторыми свойствами или признаками Универсальное множество - множество всевозможных элементов Способы задания: перечисление, описание хар. свойств, задание множества с помощью порождающей процедуры(числа фибоначчи) Подмножество - множество A называется подмножество B если взять любой элемент из подмножества он должен принадлежать множеству. Для любого множества можно указать два подмножества - пустое и само N. Множества называются равными, если они состоят из одних и тех же элементов. Конечное/бесконечное множество. Счетные/континуальные 1..4/1,4...4,002. Мощность множества А - число элементов этого множества. Булиан - множество всех возможных подмножеств. 2^кол элементов Операции над множествами: пересечение(и), объединение(или) ,разность (x принадлежит A и не принадлежит В), дополнение (универсальное множество синус А), симметрическая разность (х принадлежит А и не принадлежит В или х принадлежит В и не принадлежит А) Декартово произведение множеств - множество пар, где 1-й элемент принадлежит А, а 2-й принадлежит В. В математике рассматриваются не только упорядоченные пары, а и наборы из 3-х 4-х и тд элементов. Такие упорядоченные наборы называются кортежами. ОТОБРАЖЕНИЕ Отображение - частный случай соответствия - для задания необходимо указать 1)Множество, которое отображается - область определения отображения 2)Множество в(на) которое отображается данная область определения - множество значений 3)Закон или соответствие между этими множествами, по которому для элементов первого множества выбираются элементы из второго множества. Образ - для некоторого элемента а из А поставим в соответствие элемент b из B, который называют образом элемента А. Пусть А и В это не пустые множества. Говорят, что на множестве А задано отображение F из А в В, если каждому элементу а из А соответствует элемент b из B. Способы задания: Аналитический, Табличный, Графический. Сюръективное - соответствие при котором каждому элементу множества А указан единственный элемент В, а каждому элементу множества В можно казать хотя бы один элемент множества А. Инъективное - каждому элементу множества А соответствует единственный элемент В, а каждому элементу В соответствует не более одного прообраза из А. Биективное - отображение множества А на В при котором каждому элементу В соответствует единственный элемент из А (Инъекция + Сюръекция). Если между элементам множеств А и В установлено взаимнооднозначное соответствие, то множества эквивалентные, равномощные. Композиция множеств - произведение, суперпозиция БИНАРНОЕ ОТНОШЕНИЕ Отношение - одна из форм всеобщей взаимосвязи всех предметов, явлений, процессов в природе, обществе и мышлении. БО между элементами множеств А и В - любое подмножество R декартового произведения AxB. Способы задания: перечисление элементов(список), с помощью како-то правила, графический способ, задание с помощью графов, матричный способ. ImR Областью значений БО R называется подмножество множества В для которого найдутся такие элементы из А, что х и у находятся в отношении R (xRy). Вторая координата. DomR Область определения называется подмножество множества А для которого найдутся такие элементы из В, что выполняется xRy. Первая координата. Операции: пересечение, объединение, разность, дополнение. Рефлексивность - если для любого x из А выполняется xRx. Главная диагональ (1). В графе у каждой вершины есть петля. Симметричность - если для любых х,у из А пара х,у принадлежит R тогда и только тогда, когда y,x принадлежит R. Симетрична относительно гл. диагонали. В графе все стрелки двухсторонние. Антирефлексивность - когда БО не обладает свойством рефлексивности для всех элементов. В матрице (0) на гл. диаг. Антисимметричность - не обладает свойством симметричности. Транзитивность - если для любых х,у,z из А выполняется xRy и yRz следовательно xRz. Виды БО: Эквивалентность - транзитивность+симметричность+рефлексивность. Толерантность - рефлексивно и симетрично. Отношение порядка - антисимметричность и транзитивность. Частным порядком - рефлексивно, антисимметрично и транзитивно. Рефлексивное отношение порядка называется отношением не строгого порядка. Антирефлексивным отношением порядка называется отношение строго порядка. Связанные отношении и порядки называются полными, в противном случае частными. ПОДСТАНОВКИ Взаимно однозначное соответствие (отображение) из Еn в En называется подстановкой степени n. Подстановки принято записывать в виде матриц из двух рядов. Первая стока - аргументы или прообразы. Вторая - образы. Если элементы первой строки расположены в порядке возрастания, то запись такой подстановки называется канонической. Представления: графический, композиция циклов. Тождественная подстановка отображает каждый элемент множества на саму себя. Порядком подставки называется наименьшее натуральное число n, такое что G^n = тождественной подстановке. Транспозиция - любая перемена двух элементов второй строки Инверсия - перемена двух соседних элементов во второй строке. МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ Утверждение - общее - частное Дедукция - переход от общего утверждения к частному Индукция - переход от частного утверждения к общему БАЗИС ИНДУКЦИИ - ИНДУКЦИОННЫЙ ШАГ |