Каким термином называют представление единого объекта в виде множества отдельных элементов?

4 ответов на вопрос “Каким термином называют представление единого объекта в виде множества отдельных элементов?”

  1. Adoth Ответить

    Существенным пунктом канторовского понятия множества является то, что совокупность предметов рассматривается как один предмет («представляется как единое целое»). Основное внимание тут переносится с отдельных предметов на совокупности предметов, которые в свою очередь, можно рассматривать как предметы.
    Что касается «предметов нашей интуиции или интеллекта», то эта формулировка дает значительную свободу прежде всего тем, что никак не ограничивает природу предметов, составляющих множество. Множество может состоять, например, из людей, простых чисел, точек пространства, планет Вселенной и т.д. Заметим, что канторовская формулировка множества дает возможность рассматривать множества, элементы которых по определенной причине точно задать невозможно.
    Смысл выражений: «которые можно отличить один от другого» и «определенные предметы» заключается в следующем. В первом случае для любых двух предметов, которые рассматриваются как элементы данного множества, должна существовать возможность выяснить, различные эти предметы или одинаковые. Во втором случае, если задано некоторое множество и какой-нибудь предмет, то можно определить, является ли этот предмет элементом данного множества. Отсюда следует, что всякое множество полностью определяется своими элементами. Это канторовское требование формулируется как интуитивный принцип объемности или аксиома экстенсиональности, согласно которому два множества (А и В) равны тогда и только тогда, когда они состоят из одних и тех же элементов (обозначают А=В).
    Таким образом, два множества равны, если каждый элемент одного из них является элементом другого и наоборот.
    Общим обозначением множества служит пара фигурных скобок {…}, внутри которых перечисляются элементы множества. Для обозначения конкретных множеств используют различные прописные буквы (М, Х, А,…), или прописные с индексами (М1, М2, …). Для обозначения элементов множества в общем случае используют различные строчные буквы, или строчные буквы с индексами. Для указания того, что некоторый элемент a является элементом множества А, используется символ принадлежности множеству I[1]. Запись аIА означает, что элемент а принадлежит множеству А, а запись аIА означает, что элемент а не принадлежит множеству А. Записью а1, а2, … аn IА пользуются в качестве сокращения для записи а1IА, а2IА, а3IА, …аnIА.
    Множества бывают конечными и бесконечными. Множество называют конечным, если число его элементов конечно, т.е. если существует натуральное число N, являющееся числом элементов множества. Множество называют бесконечным, если оно содержит бесконечное число элементов.
    1.2 Способы задания множества
    Существует два основных способа задания множества: перечисление и описание.
    Например, множество отличников группы можно задать, перечислив студентов, которые учатся на “отлично”. Например: {Иванов, Сидоров, Петров,…}.
    Для сокращения записи А={a1, a2, … an } иногда пишут A= , или вводят множество индексов I={1,2,….n} и пишут А={ai}, iII. Такой способ удобен при рассмотрении конечных множеств, содержащих небольшое число элементов.
    Описательный способ задания множества состоит в том, что указывается характерное свойство, которым обладают все элементы множества. Под свойством предмета х будем понимать такое повествовательное предложение, в котором нечто утверждается относительно предмета х и которое можно характеризовать как истинное или ложное по отношению к х (характеристический предикат).
    Например, свойствами являются:
    – 5 делит х;
    – х2 > 0.
    Выражения:
    – существует такой х, что 5х < 0; - для всех х, y ху=ух не являются свойствами, потому что их нельзя характеризовать как истинные или ложные относительно х. Если обозначить Р(х) некоторое свойство, тогда Р(а) будет означать тоже самое свойство, но с заменой х на а. Задание множества в терминах свойств достигается с помощью интуитивного принципа абстракции или аксиомы свертки: всякое свойство Р(х) определяет некоторое множество А с помощью условия: элементами множества А являются те и только те предметы а, которые имеют свойства Р.
    В силу принципа абстракции всякое свойство Р(х) определяет единственное множество, которое обозначают {a|Р(а)} и читают так: «множество всех тех предметов а, что Р(а)»
    Так, если С – множество студентов группы, то множество О отличников этой группы запишется в виде:
    .
    “Множество О состоит из элементов s множества С, обладающих тем свойством, что s является отличником группы”.
    В тех случаях, когда не вызывает сомнений из какого множества берутся элементы s, указание о принадлежности s множеству С можно опустить. При этом множество О запишется в виде:
    .
    Примеры:
    А={x|x – четное} – множество целых четных чисел;
    В={x|x2-1=0} – множество {-1, 1}.
    Пусть N множество целых чисел. Тогда {nIN| } есть множество {1,2,3,4,5,6,7}.
    Важным понятием теории множеств является понятие пустого множества. Пусть А – некоторое множество, а Р(х) имеет вид х ¹ х, тогда множество {a|P(a)} = {a|a ¹ a}, очевидно, не имеет элементов. Из принципа объемности следует, что может существовать только одно множество, которое не имеет элементов. Это множество и называется пустым множеством.
    Или, Пустыммножеством называют множество, не содержащее ни одного элемента. Пустое множество обозначается символом ?.
    Например, {nIN| n2+2n+5=0}=?.
    Пустое множество условно относится к конечным множествам.
    Задание множества называют неизбыточным, если каждый элемент входит в данное множество в единственном экземпляре, и избыточным, если хотя бы один элемент входит в его состав более чем в одном экземпляре (мультимножества).
    1.3 Равенство множеств
    Как уже отмечалось, два множества называются равными, если они состоят из одних и тех же элементов, т.е. представляют собой одно и тоже множество. Символ равенства множеств обладает свойствами:
    · А=А – рефлексивность;
    · если А=В, то В=А – симметричность;
    · если А=В и В=С, то А=С – транзитивность.
    Из определения равенства множеств вытекает:
    1. порядок элементов в множестве несуществен. Например, множества {1,2,3,4} и {3,4,1,2} представляют собой одно и тоже множество;
    2. в множестве не должно быть неразличимых элементов. Поэтому в множестве не должно быть одинаковых элементов. Например, запись множества А={6,7,8,6,9} следует рассматривать как А={6,7,8,9}1.
    Но, множество, которое состоит из элементов некоторого множества А так, что эти элементы могут входить в состав этого множества в любом количестве экземпляров, называют мультимножеством множества А. С точки зрения теории множеств, множество и мультимножество – это один и тот же объект и они могут между собой не различаться. Однако часто, особенно когда речь идет о представлении множества в памяти ЭВМ, возникает потребность отличать множество от мультимножества.
    1.4 Подмножество
    Множество А является подмножеством множества В, если любой элемент множества А принадлежит и множеству В.
    Например, множество студентов группы является подмножеством студентов факультета; множество четных целых чисел может рассматриваться как подмножество множества натуральных чисел.
    Для определения подмножества в теории множеств используются символы:
    · “ – символ, называемый квантором всеобщности. Запись “xозначает: “ любой х”, “каков бы ни был х”, “для всех х”, “для всякого х”; и т.п.
    · $ – символ, называемый квантором существования. Запись $xозначает: “существует такой х, что”;
    · ® (или ?) символ следствия (импликации), означающий “влечет за собой”; “если… то”;
    · U – символ эквивалентности, означающий “тогда и только тогда”, “то же самое”.
    Тогда определение подмножества, которое может быть сформулировано в виде: для любого х утверждение “х принадлежит А“ влечет за собой утверждение “х принадлежит В” запишется так:
    1.1
    Более краткой записью выражение “A является подмножеством B” будет запись
    1.2
    (Читается “В содержит А”).
    Используемый здесь символ I означает включение.
    Если множество В содержит и другие элементы кроме элементов из А, то используют символ строгого включения I и обозначается это А I В. В этом случае А называется собственным подмножеством множества В
    Связь между символами дается выражениями:
    1.3
    Свойства подмножеств:
    · АIА – рефлексивность; (AEA – иррефлексивность) 1.4
    · [AIB и BIC] ® AIC – транзитивность. 1.5
    Следует отметить важное свойство, что для любого множества А пустое множество ? I A.
    Если АIВ и ВIА, то множества А и В эквивалентны: А=В, т.е. все эле-менты А являются элементами В, а все элементы В являются элементами А.
    Т.е. А=В U ( )
    Определение. Множество всех подмножеств данного множества А называют булеаном или степеньюмножества А и обозначают ?(А)1.
    Формально ?(А)={B| BIA}. В частности заметим, что поскольку ? I А и А I А, то ? I ?(А); А I ?(А).
    Пример. Пусть А={a,b,c}. Тогда ?(А)={ ?, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, A}.
    1.5 Операции над множествами
    1.5.1 Предварительные замечания
    Над множествами можно производить действия, которые во многом напоминают действия сложения и умножения в элементарной алгебре. Если а и b некоторые числа, то законы элементарной алгебры можно записать как:
    1. a+b = b+a; a?b=b?a – коммутативный (переместительный) закон;
    2. – ассоциативный (сочетательный) закон;
    3. (a+b)?c=a?c+b?c – дистрибутивный (распределительный) закон.
    Заметим, что в ассоциативном и коммутативном законах можно заменить действие сложения умножением, а действие умножения – сложением. При этом получим другой закон, который будет справедлив как и первый. Однако в дистрибутивном законе подобной симметрии нет. Если в этом законе заменить сложение умножением, а умножение сложением, то придем к абсурду
    .
    Всегда ли это так? Оказывается существуют алгебры, и именно алгебра множеств, в которой все три закона симметричны относительно действий “сложения” и “умножения”.
    1.5.2 Объединение множеств
    Объединением множеств А и В называют множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств А и В. Объединение множеств А и В обозначается символом , т.е. .
    Определение объединения множеств можно записать как
    1.6
    Объединение множеств иногда называют суммой множеств и обозначают А+В. Однако свойства объединения множеств несколько отличаются от свойств суммы при обычном арифметическом понимании. Поэтому термином сумма пользоваться не рекомендуется.

  2. porch kitte Ответить

    3 М9 = {n | for n from 1 to 9}.
    Перечислением можно задавать только конечные множества. Бесконечные множества задаются характеристическим предикатом или порождающей процедурой.
    Операции над множествами.
    Самого по себе понятия множества еще недостаточно – нужно определить способы конструирования новых множеств из уже имеющихся, то есть совершать операции над множествами. Обычно рассматриваются следующие операции:
    1 Объединением множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А, В. Символически это записывается так
    А
    ВА
    А E В = {C e C I АилиC I В }

    Аналогично определяется объединение произвольной совокупности множеств. В общем случае можно использовать обозначение E А , которое формулируется как объединение всех множеств А , принадлежащих совокупности М.
    Пример. Сборочная единица представляет собой объединение некоторого множества Т-систем « деталь»
    СЕ = E ТСД
    2 Пересечением множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые одновременно принадлежат и А и В. Символически это записывается так
    А
    В
    А C В = {C e C I АиC I В }
    Аналогично определяется пересечение произвольного числа множеств.
    В
    А
    3 Разностью множеств А и Вназывается множество всех тех и только тех элементов А,которые не содержатся в В. Обозначается это следующим образом
    А \ В = {C e C I АиC I В }
    В отличие от двух предыдущих операций разность строго двухместна, т.е. определена только для двух множеств и не коммутативна:
    А \ В ¹ В \ А
    Симметричная разность множеств А и В это множество. стоящее из элементов, которые принадлежат хотя бы одному из множеств А и В, но без элементов, которые одновременно принадлежат множествам А и В.
    А ? В= (А U B) \ (A ? B)= {X | (X Є A и Х IВ ) или (ХI А и е Є В)}
    А В
    А ? В
    Отношения
    Обычно широко используемое понятие «отношение» имеет вполне определенное математическое значение.
    Прямым произведением множеств А и Вназывается множество пар (а,в),таких что а I А , в I В.
    А*В:= {(а,в) | а Є А и в Є В}

  3. Briton Ответить

    В.П. Пинчук
    Анализ и построение алгоритмов. Краткий конспект лекций –
    Запорожье: ЗНТУ, 2010.
    Глава 5
    комбинаторные задачи и вычисления на множествах
    1. Понятие множества. Представление множества для вычислений
    2. Набор операций для множеств
    3. Алгоритмы выполнения основных операций над множествами и их эффективность
    4. Получение полных наборов комбинаторных объектов. Перестановки
    5. Подмножества
    6. Разбиения
    7. Поиск наибольшей монотонно возрастающей подпоследовательности
    Понятие множества. Представление множества для вычислений
    Множество
    Определение. Способы задания множества: перечисление элементов, предикатный метод. Универсальное множество (универсум).
    Представление множеств для вычислений
    Так как бесконечные множества не являются объектами дискретных вычислений, рассматриваются только конечные множества. Для представления множеств при компьютерных вычислениях используются три базовые структуры данных:
    – битовый вектор;
    – неупорядоченный массив целых чисел;
    – упорядоченный массив целых чисел.
    В любом представлении используется тот факт, что любой элемент любого множества всегда можно представить целым числом – его номером в универсуме. Поэтому в качестве элементов базовых структур, представляющих множества, достаточно использовать только целые числа.
    Под универсумом (универсальным множеством) понимают множество, включающее в себя элементы любого множества, используемого в данном рассмотрении. Таким образом, если U – универсальное множество, а A – некоторое множество в данном рассмотрении, то имеем: “A: AIU (и всегда необходимо добавлять: в данном рассмотрении).
    Битовый вектор
    Битовый вектор представляет собой бинарный код, размер которого соответствует мощности универсального множества. Пусть A – рассматриваемое множество. Значение i-того элемента битового вектора ai множества A определяется по следующему правилу: ai = 1, если i-тый элемент универсума принадлежит множеству A, и ai = 1, если нет.
    Достоинством битового вектора для представления множеств является малое время выполнения основных операций: объединения, пересечения, дополнения. Недостатком является то, что размер соответствующего объекта определяется не числом элементов рассматриваемого множества, а размером универсума. Это приводит в некоторых случаях к недопустимо большому размеру объектов, порождаемых программой и используемых для представления множеств.
    Неупорядоченный массив целых чисел
    Неупорядоченный массив целых чисел, представляющий множество, может быть простым или динамическим. Достоинством такого представления множества является простота программной реализации. Недостатком является большое время выполнения операций: проверка принадлежности, объединение, пересечение, дополнение. В том случае, когда используется простой (не динамический) массив, недостатком является также недостаточно эффективное использование ресурса памяти компьютера.

Добавить ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *