Непрерывная математика Дискретная математика - polpoz.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
Литература по математике (алгебра, геометрия, математический анализ... 1 224.35kb.
Бакалавр прикладной математики и информатики подготовлен преимущественно... 1 25.06kb.
Перечень вопросов для подготовки к зачету по дисциплине «Дискретная... 1 13.02kb.
Программа дисциплины «Дискретная математика» 1 283.06kb.
Математизация науки. “Чистая” и “прикладная” математика. Основные... 3 911.51kb.
По дисциплине: Дискретная математика 1 105.49kb.
Математика. Комплект 2 5 493.04kb.
Экзаменационные вопросы по дисциплине «Дискретная математика» для... 1 34.55kb.
«Математический анализ I», «Алгебра и геометрия», «Дискретная математика»... 1 18.09kb.
Математика, системного программиста по специальности 010200 Прикладная... 1 528.16kb.
Анализ результатов школьного тура олимпиады предметна область «Математика»... 1 63.95kb.
К. А. Михайлов. От античной философии к современной логике: аргумент... 1 130.93kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

Непрерывная математика Дискретная математика - страница №3/3


Классификация бинарных соответствий

Приведем классификацию соответствий по его компонентам: области определения Dom S, закону сопоставления элементов множеств M1 и M2, области значений Im S.

1) Говорят, что соответствие всюду определенно, если Dom S = M1. В этом случае такое соответствие называют отображением Г и записывают q = < M1, M2, Г> или Г: M1  M2.

Очевидно, что если Dom S  M1 (область определения есть собственное подмножество области отправления), то говорят о частично определенном соответствии (или о не всюду определенном S).

2) Соответствие q называют многозначным, если хотя бы один элемент xi  M1 имеет число образов больше единицы, т. е. когда |imsxi| >1

3) Соответствие называют функциональным (однозначным), если для любого xM1 |imsx|  1.В этом случае запись соответствий имеет вид 1, M2 , Sf > (для отображения 1, M2 , Гf >, для отношения f>, для функции ).

4) Соответствие называют инъективным, если его обратное соответствие < M2, M1 ,S-1> -однозначно, т. е., когда |coimsyj|  1.

5) Соответствие называют сюръективным, если Im S = M2, т. е., когда ПрM2 S = M2.

6) Соответствие называют биективным, если оно одновременно инъективно и сюръективно.

7) Соответствие называют взаимно однозначным (функциональной биекцией), если M1 = Dom S,

M2 = Im S, | M1| = | M2|, а S и S-1 - функциональны.

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



Замечание:

1) Соответствие вне n,M,Sf> называется n-арной частичной алгебраической операцией. В частности, бинарная алгебраическая операция 2,M,Гf>, всюду определенная на множестве М, записывается как кортеж 2>, где f2: M2→M. В случае же одноместной (одноарной) всюду определенной алгебраической операции запись f: M→M аналогична записи f(x), где хM, f(x) M;

2) В записи всюду определенной алгебраической операции f: Mn→M фиксируется ее функциональность (однозначность, детерминированность) и замкнутость (т.е. результат операции над элементами из М является также элементом М). Очевидно, что операция декартового произведения не является алгебраической.
Примеры интерпретации соответствий.

а) Интерпретацией частично определенного многозначного инъективного соответствия может быть англо-русский словарь. В этом случае M1 и M2 -слова указанных языков; Dom S -подмножество слов английского языка, представленного в словаре; Im S -подмножество слов русского языка. S многозначно, потому что некоторым английским словам из Dom S соответствует несколько слов из Im S. Закон сопоставления S-1 также является многозначным.

б) Интерпретацией инъективного несюрьективного функционального отображения может быть сопоставление элементов множества десятичных цифр М1 и множества булевых векторов длины 4М2:

М1 М2


Гf

в) Интерпретацией сюрьективного неинъективного функционального отображения может быть дизъюнкция (алгебраическая операция на булевом множестве В={0,1}):
В2 = ВЧВ

0V0=0


0V1=1

1V0=1


1V1=1
B2 V B

Очевидно, что отображение Г: В→В2 является биекцией (т.е. одновременно это отображение инъективно и сюрьективно), т.е.:


B Г B2

Примечание:

Из этого примера видно, что биекция не является взаимно-однозначным соответствием. Интерпретацией функциональной биекции (взаимно-однозначного соответствия) может быть сопоставление элементов множества М1={0,1,2,3,4,5,6,7} и булевых кортежей М2={<0,0,0>,<0,0,1>,<0,1,0>,<0,1,1>,<1,0,0>,<1,0,1>,<1,1,0>,<1,1,1>}.

Одноместный предикат Р(х): М→В есть логическая форма простого высказывания субъектно-предикатной структуры (записывают в вид выражения х<=Р, где хМ={a,b,c…,k}, <= - отношение предикации, Р – свойство, которым обладает элемент универсума рассмотрения М), Р(а), Р(b),…,Р(k)- простые высказывания логики предикатов.


  1. Пусть М={1/3,2,7,9/4}, Р – натуральное число. Очевидно, что Р(1/3)=л и Р(9/4)=л (ложные высказывания), а Р(2)=и и Р(7)=и (истинные высказывания). Одноместный предикат Р(х): {1/3,2,7,9/4}{и, л} в этом случае является выполнимым (т.е. сюрьективным функциональным отображением), а диаграмма имеет вид:

М Р В


Область выполняемости предиката

2) Пусть М={1,2,7,9}, Р – натуральное число. В этом случае предикат Р(х): {1,2,7,9}→{и, л} является тождественно истинным (т.е. М есть область выполнимости предиката), т.е.


М Р В

Область выполняемости предиката

3) Пусть М={1/3,1/2,1/5,1/9), Р – целое число. В этом случае (т.е. когда область выполнимости предиката пуста) говорят о тождественно ложном предикате, т.е.
М Р В

Примечание. Говорят, что Гf: AB  C есть внешний закон композиции, если ABC (если A=B=C, то говорят о внутреннем законе композиции или алгебраической операции).
Способы задания соответствий.

Наиболее часто соответствия задают:



  • множеством картежей;

  • матрицей;

  • сечением (фактор-множеством);

  • диаграммой.

а) Задание соответствия множеством кортежей.

Поскольку S является подмножеством декартового произведения, то его можно задать как перечислением (в частности списком) конечного числа картежей, так и описанием.



Пример:

Пусть M1 ={a0, a1, a2}, M2 ={b1, b2, b3, b4},

S={< a0, b1>, < a0, b2>, < a0, b3>, < a0, b4>, < a1, b2>, < a1, b3 >, < a1, b4 >, < a2, b3>, < a2, b4>} (M1M2).

Заданное перечисление картежей S можно задать описанием: S={< ai , bj> M1  M2: j>i, i=0,1,2; j=1,…,4}



б) Задание соответствий матрицей.

Используя понятие индикатора для подмножества S  M1M2, перепишем соответствие как отображение декартова произведения в двоичное множество {0,1}, т.е. Гf: M1M2 {0,1}

Этому отображению сопоставим булеву матрицу размера M1M2, строки и столбцы которой помечены элементами множеств M1 и M2, а позиции – нулем или единицей.

Пример:

Пусть М = {x1, x2, x3}, M={y1, y2} и S = M1M2={<x1,y1>,< x1,y2>,< x3,y1> } = {<< x1,y1>,1>,



<< x1,y2>,1>, << x2,y1>,0>, <2,y2>,0>, << x3,y1>,1>, << x3,y2>,0> }.


y1y2



x111

x200

x310
S

Г

B



Имеем булеву матрицу:

Замечание:

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



Пример:

Для А= {a1, a2}, B = { b1, b2, b3}, C = { c11, c12, c13, c21, c22, c23}

Внешний закон композиции Гf: AB C может быть задан следующей таблицей Кэли

Гfb1b2b3a1c11c12c13a2c21c22c23


V01

001

111
Пример:

Таблица Кэли для дизъюнкции V: B2 B имеет вид


в) Задание соответствия сечением.

Сечением (окрестностью единичного радиуса) элемента xi  M1 называется подмножество YM2 таких, что: i, yi>S  M1M2.

Множество всех сечений элементов множества M1 называется фактор множеством. М1= {xi} i=1,...5.

Пример:

M1 ={yj}j=1,...4. S = {1,y1>, < x2,y3>, < x3,y2>, < x5,y2>, < x5,y4>}


X 1 X2 X3 X4 X5

Имеем:

{Y1} {Y3} {Y2} Ш {Y2, Y4}


г) Задание соответствий диаграммой.

Обычно для соответствий диаграммным представлением является двудольный граф (доли -множества вершин, помеченных символами элементов множеств М1 и М2), рассмотренный ранее как графическое представление S, а для отношений – псевдограф, в котором кортеж i,xj>


представляется петлей xi , а кортеж i,xj> - дугой X1 X 2

Пример:

Пусть М1 = М2 ={x1, x2, x3 , x4}, R = {1,x2>, < x2,x3>, < x4,x1>, < x4,x4>} x2

Имеем псевдограф, как представление этого соответствия : x3

x1

x4

Пример:

Информационный обмен между устройствами фон-Неймановской структуры ЭВМ можно задать ориентированным графом (здесь дуга указывает связь источника информации с её потребителем):

Поскольку управлением информацией процессом осуществляется контроллером, то его, как вершину графа V5 , поместим в центре, а процессор и периферийные устройства V1,V2, V3, V4 - - вкруг.

V1 – устройство обработки информации ( процессор);

V2 - устройство ввода;

V3 - запоминающее устройство

V4 - устройство вывода

V5 - устройство управления (контроллер)

Очевидно, что это бинарное отношение R, заданное графом, можно представить и другими способами, в частности, перечислением дуг и матрицей смежности и перечислением множества дуг:




R= U = {5,V1>, 1,V5>,< V5,V2>, 2,V5>, 3,V5>, < V5,V3>, < V2,V1>, 1,V4>,< V2,V3>,


V1V2V3V4V5

V100111

V210101

V310011

V400001

V511110
< V3,V4>,< V1,V3>,< V3,V1>}


Пример

Пусть q~ = 1,M2, R~>, где M= {x1, x2, x3}, R~= {<< x1, x1>;0,5>, << x1, x2>;1>, << x2, x3>;0,5>,



<< x3, x1>;1>, << x3, x2>;1>}


X1X2X3



X10,510

X2000,5

X3110
Это соответствие, заданное матрицей и графиком, имеет вид:

x1

x3 x2

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

В инженерной практике наиболее часто применяют следующие операции над соответствиями:



  • теоретико-множественные

  • инволюции (обращения)

  • композиции (произведения, суперпозиции).

1) Теоретико-множественные операции над соответствиями S.

Поскольку S являются подмножествами множества, то можно говорить об объединении однотипных соответствий, их пересечении, разности и дополнении:

S1 S2  M1M2, где S1 M1M2,, S2 M1M2

S1 S2  M1M2,

S1 \ S2  M1 M2,

S=(M1M2)\S



Замечание. Соответствия и булевы операции над ними {,,}образуют булеву алгебру 1M2),,,>, несущим множеством которого является булеан декартова произведения.
2) Инволюция соответствия.

Инволюцией q-1 = 2 , M1 ,S-1 > соответствия q=1,M2,S > называется множество:

S-1={ M2M1:  S}

Из этого определения следует, что S-1 является обратным к S.



Пример. (графический для инволюции)
M1 M1

M2 M2

3) Композиция соответствий.

Композиция соответствий q1 = 1 , M 2,S1 >, q2 = 2 , M 3, S2> - бинарная операция q1q2 = q3 < M1 , M3 , S1S2 >, определяемая равенством:

S3 = S1S2 ={ M1M3: y ( S1 u  S2)}, т.е. если S1 M1M2 и S2  M2M3, то произведение S1S2= S3 состоит из таких наборов (M1M3), для которых найдется элемент

y M2 такой, что  S1 , S2. При этом Jm S1=Dom S2 (т.е. равны проекции Прy S1 = Прy S2)




Пример

Пусть M1 ={ x1, x2, x3, x4, x5}, M 2={ y1, y2, y3, y4}, M3 ={ z1, z2, z3},

q1= 1 , M 2,S1>, q2 = 2 , M 3, S2> ,

S1={ 1, y1>, 2, y2>, 3, y1>, 4, y3>}, S2={ 1, z1>, 2, z2>, 3, z1>}.

Композиция q3 = q1q2 = < M1 , M 2,S1S2>, где S1S2= { 1, z1>, 2, z2>, 3,z1>, 4, z1>}

Очевидно Dom S1S2 ={ x1, x2, x3, x4} M1 , Jm S1S2 ={ z1, z2} M3 , DomS2 = JmS1 = {y1, y2, y3}.

Полученный результат иллюстрируется графически:
M1 M2 M3

Примечание.

1) Композицию можно распространить на большее, чем два, число соответствий.

2) Свойства операций композиции над соответствиями:

а) (S1S2)S3 = S1 (S2S3) – ассоциативность

б) Дистрибутивность к операциям  и 

(S1S2)S3 = (S1S3)  (S2S3)

(S1S2)S3 = (S1S3) (S2S3)

(S1S2)-1 = S1-1 S2-1

3) В общем случае операция композиции некоммутативна: S1S2 S2S1

4) Запись h(x) = g(f(x)) означает композицию двух функциональных отображений вида:

Гf : M1  M2 и Гg : M2  M3 . В этом случае h(x): M1  M3 и говорят, что h(x) получено подстановкой f в g.
Бинарные отношения.

Бинарным отношением R во множестве M называется подмножество его квадрата M2, т.е.

R  M2 , R ={  M2: x, yM}.

Говорят, что х, у  M находятся в отношении R, если <х, у>  R (часто пишут и так хRу, т.е. <х, у>  R  х Rу).

Реляционная система называется бинарным графом, где M=V – множество вершин (носитель графа), R=U – множество дуг (сигнатура графа).

Рассмотрим основные свойства отношений.



  • Отношение R множестве M называется рефлексивным, если для каждого элемента хM справедливо, что R. (свойство рефлекcивности при задании отношения R матрицей характеризуется тем, что все элементы главной диагонали являются 1; если R задано графом, то все его вершины имеют петли).

  • Отношение R множества M называется симметричным, если из  R следует  R (хy). Симметричное отношение представляет неограф, а его матрица симметрична относительно главной диагонали. (неограф – сокращение от неориентированный граф).

  • Отношение R множества M называется транзитивным, если из R и <у,z>R следует  R; x, y, z  M, x  y, x  z, y  z.

В графе , задающем транзитивное отношение R  M2, для всякой пары дуг таких, что конец первой совпадает с началом второй, существует третья дуга, имеющая общее начало с первой и общий конец со второй (эту дугу называют транзитивно замыкающей дугой).

Пример. Пусть R = {  N2: x,y  N, х делитель у}.

Это отношение на множестве натуральных чисел:



  • Рефлексивно, т.к. х/х = 1,

  • Несимметрично, т.к. если ху, то х/у у/х (если 2 делитель 4, то 4 не является делителем 2).

  • Транзитивно, т.к. если у/х N и z/у  N, то z/x = у/х  z/у  N.




  • Антисимметрично, т.е. х у (хRу и уRx  х=у), поскольку если х/у  N и у/х  N, то х=у.

Пример: Отношение нестрого порядка  на множестве М рефлексивно, антисимметрично и транзитивно.

Пример: Отношение включения  есть отношение упорядоченности подмножеств заданного множества. Действительно, оно рефлексивно, т.к. Mi  Mi; антисимметрично, т.к. если Mi  Mj и Mj  Mi, то Mi = Mj; транзитивно, т.к. если Mi  Mj, Mj Mk, тo Mi Mk.

Пример: Отношение «на 5 меньше, чем …» на множестве N является интранзитивным, т.к. если х=10, у=15, z=20, то х меньше у на 5, но х меньше z на 10, а не на 5.
Виды бинарных отношений.

Формальное определение видов отношений задают через наличие у них тех или иных свойств.




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

Рефлексив-

ностьИрреф-

лексивностьСиммет-

ричностьАнтисиммет-ричностьТранзитив-ностьИнтранзи-тивность

Отношение

Эквивалентность+++

Толерантность++

Доминирование(предпочтение)++

Порядок+++

Строгий порядок+++

Квазипорядок(предпорядок)++

Предикация+++
Основные виды бинарных отношений сведём в таблицу:
Согласно этой таблице, формальным определением отношения эквивалентности на заданном множестве М будет следующее: «Отношение эквивалентности - бинарное отношение на множестве, т.е. R M2, обладающее свойствами рефлексивности, симметричности и транзитивности».

Согласно таблице, очевидно, что отношение эквивалентности является частным случаем отношения:

а) толерантности, обладающего только двумя свойствами – рефлексивностью и симметричностью;

б) квазипорядка, свойствами которого являются рефлексивность и транзитивность.



Аналогично могут быть формально определены и другие виды бинарных отношений.
Содержательная интерпретация основных видов отношений.

  1. Отношение эквивалентности является экспликацией интуитивных понятий «взаимозаменяемость», «одинаковость». Задание этого вида отношений на множестве означает идентификацию эго элементов блокам разбиения. Так, задав отношение на множестве резисторов отношение R, выражаемое неравенством (xi-x)≤x≤(xi+x), где xi
<< предыдущая страница  


izumzum.ru