Дискретная математика

48 fcA. (2.2) По определенгао функции y=f(x,, х^) образ каждого набора значений (х,, Х2 x,J единственен. Поэтому в соотношении (2.2) полагается, что / является одноэлементным множеством. Если / является многоэлементным множеством, то/можно рассматривать как многозначное отобра5кение. Из изложенного следует, что матроид можно рассматривать как конечное множество Е, на котором задано конечное множество нульместных многозначных операций (подмножеств множества Е), удовлетворяющие аксиомам М1-МЗ. Таким образом, матроид является некоторым расширением понятия алгебры. Сзтцествуют и другие определения матроидов, эквивалентные приведенному определению. Если ранее матроид вводился как конечное множество Е и семейство некоторых его подмножеств, называемых независимыми множествами, то в следующем определении элементы семейства подмножеств называются циклами. Матроидом называется конечное множество Е и семейство C=fC;,C?,Cj, непустых подмножеств множества Е, называемых циклами, которые удовлетворяют следующим аксиомам: Ml *; ни одно собственное подмножество цикла не есть цикл; М2*; если xefCinCz), то содержит цикл. Отметим ещё раз, что последнее определение матроида эквивалентно определению, приведённому в начале этого параграфа. § 13. Вопросы и темы для самопроверки 1. Операции и предикаты, 2. Алгебраические системы. Модель. Алгебра. Тип алгебры. 3. Подалгебра. Пересечение подалгебр. Образует ли подалгебру объединение подалгебр? 4. Гомоморфизм (однотипных) алгебр. Примеры. 5. Изоморфизм (однотипных) алгебр. Примеры. 6. Является ли изоморфизм гомоморфизмом? 7. Группоид, полугруппа, моноид. Единственна ли единица моноида? 8. Группа. Определение, примеры. Единственность обратного элемента. 9. Разрешимость уравнений в группе. 10. Образующие элементы группы. Циклическая группа. 11. Кольцо. Определение, примеры. Делители нуля, области целостности. 12. Кольцо с единицей. Доказательство, что 0?^1 и что О не имеет мультипликативного обратного. Примеры колец с единицей. 13. Поле. Определение. Примеры. 14. Решётки. Ограниченные решётки.