5.Отношение эквивалентности и его свойства. Отношение порядка и его свойства. Матричное представление отношений.
5. Отношение эквивалентности и его свойства. Отношение порядка и его свойства. Матричное представление отношений.
Отношением эквивалентности или просто эквивалентностью на X называется отношение R, обладающее свойствами рефлексивности, симметричности и транзитивности. Вместо Подмножество T из X, содержащее в точности по одному элементу из каждого R-класса, называется трансверсалом множества X по модулю R. Антисимметричное транзитивное отношение R называется отношением порядка. Если выполняется свойство рефлексивности или антирефлексивности, то оно соответственно называется отношением нестрого или строго порядка. Если отношение порядка обладает свойством полноты (линейности), то оно называется отношением полного (линейного) порядка. В противном случае оно называется отношением частичного порядка. Обычно отношение строго порядка обозначается знаком <, а отношение нестрого порядка – знаком Отношение
6. Функции, их свойства. Представление функций в ЭВМ. Инъекция, сюръекция и биекция, их свойства.
Отношение называется (однозначной) функцией (отображением). Функция обозначается следующим образом:
Наиболее общим представлением функции Для представления функций в ЭВМ также используется особый вид процедур, возвращающих единственное значение для данного аргумента. Для функции
Функция инъективной, если сюръективной, если биективной, если она инъективна и сюръективна. Биективную функцию также называют взаимнооднозначной. Для конечных множеств X и Y классы инъективных, сюръективных и биетивных функций непусты, если соответственно выполнены соотношения: Представление функций в ЭВМ Наиболее общим представлением функции в ЭВМ является ее запись в виде двумерного массива. Пусть f: А → В, множество А конечно и не очень велико, |A| = n. Наиболее общим представлением такой функции является массив array [A] of В 7. Подстановки, перестановки, группы подстановок. Представление подстановок циклами.
Важным примером биективной функции является биективное отображение n-множества X на себя, которое называется подстановкой (на множестве X). Подстановкой называется множество равенств s={x1=t1, x2=t2, …, xn=tn}, где x1, x2, …, xn – различные переменные, t1, t2, …, tn – термы. Перестановкой из n элементов называются размещения, в которых участвуют все элементы множества Pn Pn=n! Множество G подстановок, замкнутое относительно выполнения операции композиции и содержащее тождественную (единичную) подстановку e и обратную подстановку Отображение задает канонический изоморфизм двух групп – группы подстановок s на множестве X и группы перестановок s на множестве X. Перестановку s можно рассматривать как n-набор
Группу всех подстановок (перестановок) называют симметрической группой и обозначают Другим общепринятым способом представления подстановок (перестановок) является их запись в виде объединения (произведения) циклов
Каждый элемент подстановки встречается в единственном цикле. Порядок записи циклов не имеет значения, а цикл может начинаться с любого своего элемента. Длина цикла Если подстановка Тот же самый смысл имеет обозначение Если обозначить Если в единичной перестановке поменять местами i-й и j-й элементы, то такая перестановка называется транспозицией. Каждую перестановку можно многими способами представить в виде произведения транспозиций. Четность перестановки совпадает с четностью ее разложения в произведение транспозиций, что легко доказывается по индукции. В группе Пара
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|