Прямое произведение множеств

Прямым (декартовым) произведением А₁ А₂ … А_n множеств А₁, А₂ … и А_n называется множество {<a₁, a₂, …, a_n> | a₁ A₁, a₂ A₂,, a_n A_n}, а Aⁿ обозначает А А … А (n раз) и называется прямой степенью множества А.

Отношения

Бинарным отношением между элементами множеств А и В называется любое подмножество R множества А В. Вместо <x, y> R часто пишут xRy.

Областью определения бинарного отношения R называется множество

d_R = {x | существует y такое, что <x, y> R}.

Областью значений бинарного отношения R называется множество

r_R = {x | существует y такое, что <y, x> R}.

Обратным отношением для бинарного отношения R называется множество

R^-1 = {<x, y> | <y, x> R}.

Образом множества Х относительно R называется множество

R(X) = {y | существует х Х такое, что <x, y> R},

прообразом Х относительно R называется R^-1(X).

Произведением подмножеств R₁ А В и R₂ B C называется отношение

R₁R₂ = {<x, y> | существует z такое, что <x, z> R₁, <z, y> R₂}.

Свойства отношений

Бинарное отношение R на множестве А называется

· рефлексивным, если <x, х> R для всех x А;

· симметричным, если <x, у> R <y, x> R;

· антисимметричным, если <x, у> R и <y, x> R х = у;

· транзитивным, если <x, у> R и <y, z> R <x, z> R.

Рефлексивное, симметричное и транзитивное отношение на множестве А называется эквивалентностью на А. Классом эквивалентности (смежным классом) элемента х по эквивалентности R называется множество

[x]_R = x / R = {y | <x, у> R}.

Множество классов эквивалентности элементов множества А по эквивалентности R называется фактор-множеством А по R и обозначается А / R.

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

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

Функции

Отношение f называется функцией из А в В (из А на В), если d_f = A, r_f В(r_f = В) и для всех x, y₁, y₂ из <x, y₁> f и <x, y₂> f следует y₁ = y₂. Обозначение f: A B. Пишем y = f(x) вместо <x, y> f и называем y значением функции f при значении аргумента х.

Функция f: A B осуществляет взаимно однозначное соответствие межу А и В, если d_f= A, r_f= В и из того, что y = f(x₁), y = f(x₂) следует х₁ = х₂.

Пусть А и В – частично упорядоченные множества и f – функция из А в В. f называется монотонным отображением, если из х₁ х₂ следует f(x₁) f(x₂) для всех x₁, x₂ А.

Функцию f: X Y называют n-местной функцией над множеством А, если Y = A и X = Aⁿ.

Предикатом называют функцию, областью значений которой является множество символов-цифр {0, 1}. При этом говорят, что предикат P: X {0, 1} истинен для x X, если P(x) = 1, и ложен, если P(x) = 0. Отношение на множестве Х – это двухместный предикат P: X² {0, 1}.

Алфавитом называют непустое конечное множество символов. Например, V₁ = {a, b}, V₂ = {0, 1}, V₃ = {a, +, 1, =} – алфавиты. Словом в алфавите V называется конечный объект, получаемый выписыванием одного за другим символов V, например, а + 1 = 1 + а – слово в алфавите V₃, 101011 – слово в алфавите V₂, abaab – слово в алфавите V₁. Длина слова – число символов в нем, пустое слово не содержит ни одного символа.

Множество всех слов в алфавите V обозначается V^*.

n-местной словарной функцией над алфавитом V называют n-местную функцию над V^*, т. е. функцию из V^* V^* … V^* (n раз) в V^*.

Понятие графа

Направленным графом называется тройка G = (V, E, Ф), где V - множество вершин, Е – множество дуг, а Ф – функция из Е в (V {w})², w V. Дуга е называется входом графа, если Ф(е) = (w, u), для u V {w}; внутренней, если Ф(е) = (u₁, u₂) для u₁,u₂ V; выходом, если Ф(е) = (u,w), для u V {w}. Дуга е, являющаяся одновременно и входом и выходом графа, называется висячей; для нее Ф(е) = (w,w). Дуги, не являющиеся внутренними, называются также свободными.

Говорят, что дуга е инцидентна вершине u, если е выходит из u или ведет в u. Две дуги смежны, если существует хотя бы одна инцидентная им обеим вершина. Вершина u называется наследником вершины u', если в графе имеется хотя бы одна такая дуга, что Ф(е) = (u', u).

Изображенный на рисунке 1.1. граф G₁ содержит 4 вершины, 8 дуг. Дуга е₁ – входная, дуга е₆ – выходная, дуга е₈ – висячая, остальные дуги внутренние; вершины u₁ и u₃ наследники вершины u₁.

Путем в графе G называется последовательность …u_ie_iu_i+1… дуг и вершин, такая, что для всех i Ф(е_i) = (u_i,u_i+1). Образом пути называется слово, составленное из пометок проходимых дуг и вершин.

Две вершины u₁,u₂ графа G называются связанными, если u₁ = u₂ или существует маршрут е₁, …, е_n графа G такой, что дуга е₁ инцидентна вершине u₁, а дуга е_n – вершине u₂.

Не нашли, что искали? Воспользуйтесь поиском по сайту: