Шпора 8 страниц

1

Множество – это "мысленная" надстройка над некоторой группой объектов любой природы, объединяющая эту группу объектов в некоторое мысленное целое. Из любого набора объектов можно составить множество, элементами которого будут эти и только эти объекты. Множество, элементом которого являются другие множества, называют множеством множеств или семейством множеств.

Знак множества – это некий объект, главным свойством которого является обозначать, быть представителем некоторого конкретного множества. Облик и внутреннее устройство знака множества может быть самым различным. Необходимо четко отличать знак какого-либо множества как абстракцию и конкретное представление знака в некотором тексте. Каждому знаку множества можно поставить в соответствие множество, обозначаемое этим знаком и множество всевозможных изображений этого знака.

Для каждого множества можно построить знак, обозначающий это множество. Множество, каждый элемент которого является знаком множества, будем называть нормализованным множеством.

Пара принадлежности - множество частного вида, состоящее либо из двух элементов, один из которых - знак некоторого множества, а второй – один из элементов указанного множества, либо из двух вхождений одного и того же элемента, который трактуется как знак некоторого множества, включающего в качестве одного из своих элементов знак самого себя. Пару принадлежности второго вида будем называть петлей принадлежности.

Узловое множество – это множество, не являющееся парой принадлежности.

Объект, который не является ни множеством, ни знаком множества, будем называть предметом. Каждому предмету можно поставить в соответствие некоторый знак. Такие знаки будем называть предметными знаками.

Мощность множества – это суммарное количество вхождений в это множество всех его элементов.

По признакам нормализованности множества можно разбить на два следующих класса нормализованные и ненормализованные множества.

По признаку наличия многократного вхождения элементов множества делятся на множества без кратных элементов и множества с кратными элементами.

По признаку вхождения в число элементов множества, как самого себя, множества делятся на рефлексивные множества (множества, которые включают в число своих элементов собственные знаки) и нерефлексивные множества.

По этому признаку мощности множества делятся на 1-мощные, 2-мощные, 3-мощные множества и т.д.

Семейства множеств одинаковой мощности разбиваются на следующие подклассы семейство 1-мощных, семейство 2-мощных, семейство 3-мощных множеств и т.д.

На основании свойства "мощность множества" и свойства "количество элементов множества" можно выделить также следующие классы множеств конечно-арные (множества, мощность которых является конечным числом); бесконечно-арные; конечно-элементные множества; бесконечно-элементные множества.

Объединение множеств. В это множество входят все те и только те элементы, которые являются либо элементами множества s₂, либо элементами множества s₁. Если некий элемент x входит в состав одного из указанных множеств n-кратно, а в состав другого m-кратно (причем m  n) , то в состав множества ( s₁ s₂ ) указанный элемент будет входить m - кратно. Кратность, равная нулю означает отсутствие вхождений элемента во множество.

Пересечение множеств. В это множество входят все те и только те элементы, которые являются как элементами множества s₁ , так и элементами множества s₂. Если некий элемент x входит в состав одного из указанных множеств n – кратно, а в состав другого m - кратно (причем m  n) , то в состав множества ( s₁ s₂ ) указанный элемент будет входить n - кратно.

Разность множеств. В это множество входят все те и только те элементы множества s1, которые

не являются элементами множества s2.

Симметрическая разность множеств. В это множество входят все те и только те элементы множества

( s1 s2 ), которые не (!) являются элементами множества ( s1 s2 ).

2

Множества всевозможных перестановок - классическое отношение, у которого отсутствуют связки с кратными вхождениями элементов, все его связки являются встречными друг другу, т.е. являются кортежами, имеющими одинаковые элементы, но входящими в кортежи под различными атрибутами. У такого отношения все элементы его области определения входят в состав каждого его кортежа. Очевидно также, что для заданной области определения существует несколько отношений, обладающих указанными выше свойствами. Но существует одно, которое будет называться множеством всех перестановок из заданного набора элементов. Очевидно, что отношение, принадлежащее к классу множеств всевозможных перестановок однозначно определяется: своей областью определения и своей схемой.

Есть семейство неориентированных отношений, не имеющих кратных связок и не имеющих связок с кратными вхождениями элементов. Для такого семейства отношений можно построить минимальное отношение, являющиеся подмножеством для всех отношений, удовлетворяющих указанным выше свойствам. Для этого достаточно построить множество, являющееся результатом объединения областей определения всех отношений, входящих в состав заданного семейства неориентированных отношений, для построенного множества построить семейство всевозможных его подмножеств. Указанное отношение называется булеаном.

Множества всевозможных сочетаний с повторениями. Есть семейство m-арных неориентированных отношений, не имеющих кратных связок и не имеющих связок с кратными вхождениями элементов. Для такого семейства отношений можно построить минимальное отношение, являющееся надмножеством для всех отношений, удовлетворяющих указанным выше свойствам. Для этого необходимо построить множество, являющееся объединением областей определения всех отношений, входящих в состав заданного семейства неориентированных отношений, для построенного множества построить семейство всевозможных его подмножеств, имеющих мощность, равную m. Указанное отношение называется множеством сочетаний из заданного множества по m элементов.

3

Кортеж – это множество, у которого каждому вхождению каждого его элемента явно или неявно ставится в соответствие некоторый атрибут, указывающий роль этого вхождения элемента в рамках рассматриваемого кортежа. Кортеж – это множество, для которого существенным является не только набор вхождений элементов в это множество, но и дополнительное явное указание атрибута в рамках этого множества хотя бы одного вхождения какого-либо его элемента. Кортежи также называют упорядоченными множествами, ориентированными множествами. Атрибут задает определенную роль вхождений элементов в рамках кортежей. Числовой атрибут – это условный порядковый номер вхождения элемента в кортеж. Количество всех вхождений в состав кортежа всех его элементов, т.е. мощность кортежа называется арностью кортежа. Последним символом идентификатора знака атрибута в языке SCBs должен быть символ подчеркивания.

Существуют кортежи, которые состоят из одинаковых элементов с одинаковыми атрибутами (кратные кортежи). Существуют вырожденные кортежи, в которых все вхождения элементов имеют одинаковые атрибуты и встречные кортежи, которые являются равными множествами, но с разными атрибутами.

Схемой отношения будем называть множество знаков всех атрибутов, которые используются в кортежах отношения. Если в кортежах отношения используется атрибут, задаваемый по умолчанию, то в схеме этого отношения знак этого атрибута должен быть явно указан. Атрибут, знак которого входит в схему отношения, может использоваться не в каждом кортеже, который входит в состав отношения.

4

Отношение представляет собой некоторое семейство однотипных множеств. Нормализованное отношение - это множество знаков нормализованных множеств, каковыми могут быть кортежи. Нормализованное отношение можно трактовать как конструкцию, состоящую из следующих уровней: знак самого отношения, знаки нормализованных множеств, являющиеся элементами отношения, знаки атрибутов, используемых для указания роли элементов в кортежах, знаки множеств, являющиеся элементами множеств, знаки которых являются элементами отношения.

Связка – это множество, знак которого принадлежит какому-либо нормализованному отношению. В языке SCB для изображения связок, являющихся кортежами используется графический примитив

Анализ принадлежности связок отношений к числу кортежей позволяет выделить следующие классы отношений: ориентированные (все связки которых являются кортежами, неориентированные (все связки являются неориентированными множествами), частично ориентированные отношения (среди связок встречаются как кортежи, так и неориентированные множества). По признаку рефлексивности отношения делятся на рефлексивные и нерефлексивные. По признаку мощности отношения делятся на конечные отношения и бесконечные. Отношениям со связками одинаковой мощности можно поставить в соответствие числовую характеристику - “арность отношения”. Важной особенностью классического отношения является то, что его можно представить в виде таблицы, столбцы которой соответствуют используемым атрибутом, а строки – кортежам, входящим в состав отношения. Элементы кортежей в этой таблице представляются именами (идентификаторами) соответствующих объектов.

Область определения отношения – это множество всех объектов, которые являются элементами связок отношения.

Проекция отношения r по атрибутам a1, a2,…, am, - это множество знаков всех кортежей, которые строятся из кортежей отношения r путём удаления всех вхождений элементов, которые имеют атрибуты, не совпадающие с указанными выше атрибутами a1, a2,…, am, а также путем последующего устранения кратности кортежей.

Отношение d является декартовым произведением в том случае, если отношение d является классическим и в состав отношения d входит каждый кортеж вида  a1 : x1i , a2 : x2i , … , an : xni  где: xni есть элемент множества, являющегося унарной проекцией отношения d по атрибуту an

5

Бинарное отношение – множество, каждым элементом которого является знак пары (кортеж из двух элементов).

Отношение r является рефлексивным бинарным отношением в том и только в том случае, если для каждого х из области определения отношения r кортеж <x, x> принадлежит этому отношению.Если не существует ни одного такого кортежа, то отношение иррефлексивно (арефлексивно).

Отношение называется симметричным, если для любых 2 элементов f и t из области определения бинарного отношения, если существует пара <f,t>, то пара <t,f> тоже должна принадлежать бинарному отношению. Если не выполняется, отношение антисимметричное, причем f может равняться t.

Отношение называется асимметричным, если для любых 2 элементов f и t из области определения бин. отношения, если существует пара <f,t>, то пара <t,f> тоже не должна принадлежать бинарному отношению, причем f не должен равняться t (антисимметричное и арефлексивное).

Отношение называется транзитивным, если для любых 3 элементов f, е и t из области определения бин. отношения, если существуют пары <f,е> и <е,t>, то пара <f ,t> тоже должна принадлежать бинарному отношению. Если не выполняется, отношение антитранзитивное.

Отношения эквивалентности (рефлексивные, симметричные, транзитивные).

Отношения нестрогого порядка (рефлексивные, антисимметричные, транзитивные).

Отношения строгого порядка (арефлексивные, антисимметричные, транзитивные).

Знаки пар бинарных отношений представляются в виде SCB-дуг.

6

Соответствие между двумя множествами - тернарный кортеж, связывающий знак некоторого бинарного отношения – этому знаку присваивается атрибут отношение_, знак пары, связывающий знак одного из заданных множеств со знаков соответствующего ему атрибута, используемого в указанном выше бинарном отношении – в этой паре используется атрибут атрибут_ , а второй атрибут задается по умолчанию, знак аналогичной пары связывающей знак второго из заданных множеств со знаком соответствующего ему атрибута.

Кортеж k задает соответствие между множеством x и множеством y, т.е. имеет место

в том и только том случае, если

r - бинарно ориентированное отношение с атрибутами a_x и a_y;

k – знак конкретного соответствия между множеством s_x и s_y,

s_x – множество прообразов

s_y – множество образов

r – отношение соответствия

r _⊆ x(a_x) y(a_y)

7

Отношение r относится к классу отношений над отношениями (к классу метаотношений) в том случае, если в область определения отношения r входят либо знаки всевозможных отношений, либо знаки отношений некоторого класса и в состав каждой связки отношения r входит знак некоторого отношения.

Можно выделить классы метаотношений: классические, ориентированные, неориентированные, бинарные и т.д. Примером метаотношения может быть бинарное отношение с явным введением знака схемы отношения.

схема отношения сложения

метаотношение «быть схемой отношения»

8

n-арной (n-местной) алгебраической операцией (или просто операцией), определенной на множестве A называется n-местная функция f: Aⁿ  A. Число n для n-арной операции f (n-арного отношения r) называется арностью операции f (отношения r) и обозначается n(f) (n(r)). Арности отношений – это числа большие нуля. Арности операций – это числа большие или равные нулю. Операции арности 0 представляют собой функции с областью определения, состоящей из одного элемента (n-ки длины 0) и отождествляются со значением функции.^*

Свойства операций

 Идемпотентность. Операция * идемпотентна, если x * x = x для любого x  A. ^*

 Коммутативность. Операция * коммутативна, если x * y = y * x для любых x,y  A. ^*

 Антикоммутативность. Операция * антикоммутативна, если x * y  y * x для любых x,y  A. ^*

 Ассоциативность. Операция * ассоциативна, если x * (y * z) = (x * y) * z для любых x,y,z  A. ^*

 Дистрибутивность. Операция * дистрибутивна относительно операции _°, если x _° (y * z) = (x _° y) * (x _° z) для любых x,y,z  A. ^*

 Взаимно обратные операции. Операции * и _° называют взаимно обратными, если x * y = z тогда и только тогда, когда z _° y = x для любых x,y,z  A. ^*

 Нейтральный элемент. При операцию * говорят, что она имеет нейтральный элемент, если во множестве A существует элемент (обозначим его e), такой что x * e = x для любого x  A. ^*

Если рассматриваемая операция обозначается знаком +, то нейтральный элемент обычно называют нулём, если знаком · (умножить), то – единицей.

 Обратный элемент. При операцию * с нейтральным элементом e говорят, что для неё элемент x  A имеет обратный элемент, если для него во множестве A можно найти элемент (обозначим его x'), такой что x * x' = e. ^*

Если для всех элементов существуют обратные, то операцию называют обратимой.

Если некоторое свойство не выполняется (то есть для некоторых элементов условие нарушается), то к названию свойства добавляют ``не''. Так, если говорят о нерефлексивном отношении, это означает, что есть элемент, для которого нарушается свойство рефлексивности.

9

Множество чисел, являющихся результатами измерения заданного параметра по заданной процедуре измерения, называется шкалой измерения указанного параметра по указанной процедуре. Каждое число может входить в несколько шкал измерения. Все множество чисел можно считать интегрированной шкалой измерения, представляющей собой объединение всевозможных шкал. Для этого достаточно трактовать каждое число как множество всевозможных объектов, для которых указанное число является результатом измерения какого-либо параметра. Множество пар принадлежности, выходящих из знаков чисел, разбивается на подмножества, каждое из которых соответствует тому или иному измеряемому параметру. Таким образом, каждый измеряемый параметр трактуется как множество знаков пар принадлежности, связывающих числа с объектами, которые обладают указанными параметром (свойством).

К числу измеряемых параметров, в частности, относятся порядковый номер элемента кортежа, множитель множества (количество пар принадлежности, выходящих из знака множества), количество элементов множества.

мощность множества равна n, количество элементов множество равно m.

10

Алгебраическая система задается: <M,S>, где M – носитель, S – сигнатура (отношения, алгебраические операции). Если S содержит только операции, то алгебраическая система называется алгеброй, если содержит только отношения, то – модель, если только бинарные отношения – графовая модель.

Алгебра <A; * > называется полугруппой, если операция * удовлетворяет свойству ассоциативности: для любых элементов a, b, c  A выполняется: a * (b * c) = (a * b) * c.

Алгебра <A; *, ^-1, 1 > называется группой, если операция * удовлетворяет свойству ассоциативности, 1 – единичный элемент относительно операции *, а ^-1 – унарная операция, дающая обратный элемент относительно операции *, т.е. для любого элемента a  A выполняется: a * a^-1 = a^-1 * a = 1.

Алгебра с двумя операциями <M, {¤,*}>называется кольцом, если <M, {¤}> - группа причем m1¤m2=m2¤m1, для любых m1, m2, m3 принадлежащих M: (m1¤m2)*m3=(m1*m3)¤(m2*m3).

11

Отношение гомоморфизма на алгебраических системах.

Алгебры A = <M, S > и B = <N, Q> гомоморфны тогда и только тогда, когда существует g функциональное соответствие и для любых φ_i принадлежащих M существует ψ _i принадлежащее N, такое что для любых m1, m2,…mkg_i((m₁,...,m_k)) =ψ (g(m₁) ,...,g(m_k)).

12

Алгебраические системы, для которых существует изоморфизм, называются изоморфными. Изоморфизм алгебраических систем A = <A;f₁,...,f_k; r₁,...,r_l> и B = <B;g₁,...,g_k;p₁,...,p_l> одного типа <m₁,...,m_k; n₁,...,n_l> – это взаимно-однозначное отображение  множества A на B, такое что выполняются условия:

1. (f_i(x₁,...,x_mi)) = g_i((x₁),...,(x_mi)),

2. (x₁,...,x_nj)  r_j  ((x₁),...,(x_nj)  p_j

для любых x₁, x₂, ...  A, для любых i : 1  i  k, для любых j : 1  j  l.

Изоморфизм алгебраической системы на себя называется автоморфизмом. Автоморфизм, являющийся тождественным отображением называется тривиальным.

13

Объединение переменных классов математических структур называется классической реляционной структурой. Каждая классическая реляционная структура (конструкция) включает в себя:

• некоторое семейство классических отношений, которое называются сигнатурными отношениями реляционной структуры (при этом некоторым отношениям из указанного семейства могут быть поставлены в соответствие функции или алгебраические операции);

• некоторое семейство специально выделенных множеств, которые называются сигнатурными множествами реляционной структуры (заметим, что сигнатурные множества в реляционной структуре могут отсутствовать, заметим также, что семейство сигнатурных множеств и отношений реляционной структуры будем называть сигнатурой реляционной структуры);

• некоторое множество, которое будем называть носителем реляционной структуры и которое представляет собой нестрогое надмножество объединения всех указанных выше сигнатурных множеств реляционной структуры, а также областей определения всех указанных выше сигнатурных отношений, входящих в состав классической реляционной структуры.

Каждая реляционная структура рассматривается как формальная (математическая) модель некоторой предметной области, а используемые в реляционной структуре знаки атрибутов – как "относительные" понятия соответствующей предметной области. При этом сигнатурные элементы реляционной структуры есть не что иное, как "абсолютные" понятия указанной предметной области. При этом будем отличать сигнатурные и атрибутные элементы, соответствующие неопределяемым (исходным, базовым) понятиям, а также сигнатурные и атрибутные элементы, которые соответствуют определяемым понятиям.

Реляционная структура – это такая система множеств, для которой каждому ее элементу дополнительно приписывается некоторая его роль в рамках этой системы множеств.

Термин “реляционная структура” можно трактовать как знак ориентированного отношения с кортежами разной мощности и со схемой, включающей в себя атрибуты: “первичный элемент_ ”, “атрибут_ ”, “сигнатурное отношение_ ”, “сигнатурное множество_ ” и “атрибут по умолчанию_”.

К числу классических реляционных структур относятся полугруппы, группы, коммутативные (абелевы) группы, кольца, алгебры, алгебраические системы, алгебраические модели.

14

К числу графовых структур относятся следующие виды структур неориентированные графы (такие структуры обычно называют просто графами), ориентированные графы (орграфы), гиперграфы, сети, мультиграфы, псевдографы.

Неориентированный граф – это классическая реляционная структура с одним бинарным неориентированным отношением. Орграф – это классическая реляционная структура с одним бинарным ориентированным отношением. Гиперграф – это классическая реляционная структура с одним неориентированным отношением, связки которого имеют различную мощность. Сеть – это граф или орграф, связкам которого ставятся в соответствие некоторые числовые "веса". Классический неориентированный граф – бинарное неориентированное отношение, ребра которго – связки, нет атрибутов. Планарный граф – граф, который можно нарисовать на плоскости, так чтобы линии, изображающие ребра не пересекались.

Графом называется двуосновная модель <V, E; i >, где i – бинарное отношение множеств V и E, такое, что каждый элемент e  E находится в отношении i либо ровно с одним, либо ровно с двумя элементами множества V. При этом элементы множества V называются вершинами графа, элементы множества E называются рёбрами графа, а отношение i – отношением инцидентности. Вершины, инцидентные одному и тому же ребру, называются смежными.

Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра – линиями, соединяющими те точки, соответствующим вершинам которых ребра инцидентны. Граф без кратных рёбер и петель называется простым графом.

15

Язык SCB – это фактографический язык, обеспечивающий представление всевозможных математических структур путем трактовки каждой такой структуры как полностью нормализованной системы множеств. Каждая полностью нормализованная система множеств однозначно задается множеством троек принадлежности, которые имеют следующий вид: < v, e, g> , где

v – некоторый непредметный узел;

e– знак некоторого множества, который представляется в виде некоторого SCB-элемента и который является одним из элементов множества, обозначаемого узлом v. SCB-элемент e может быть как узлом, так и дугой принадлежности;