Теоретический материал к заданию № 3.

Бинарные дела

1. Бинарные дела и операции над ними

ОПРЕДЕЛЕНИЕ. Пусть А1, А2, . . . , Аn - некие огромного количества. Их прямым либо декартовым произведением именуется огромное количество упорядоченных наборов из n частей, т.е.

А1´А2´ . . . ´Аn= aiÎAi .

Если все огромного количества Ai совпадают A=А1=А2= . . . =Аn, то прямое произведение А Теоретический материал к заданию № 3.1´А2´ . . . ´Аn=An именуют прямой n-ой степенью огромного количества А.

Бинарным отношением меж элементами множеств А и В именуется хоть какое подмножество RÍA´B. Если огромного количества A и B совпадают А=В, то R именуют бинарным отношением на огромном количестве А Теоретический материал к заданию № 3..

Если (x, y)ÎR, то это обозначают еще xRy и молвят, что меж элементами x и y установлено бинарное отношение R.

Приведем примеры бинарных отношений.

Пусть A=B=R, пара (x, y) является точкой вещественной плоскости. Тогда бинарное отношение

R1 = x2 + y2 £1

определяет замкнутый круг единичного радиуса с центром Теоретический материал к заданию № 3. в точке (0,0) на плоскости, отношение

R2 = x ³ y

полуплоскость, а отношение

R3= x-y

полосу.

Диагональ огромного количества A´A, т.е. огромное количество D=(x,x) , именуется единичным бинарным отношением либо отношением равенства в A.

Областью определения бинарного дела R именуется огромное количество

dR= xÎA .

Областью значений бинарного дела Теоретический материал к заданию № 3. R именуется огромное количество

rR= xÎA, (x, y)ÎR .

Образом огромного количества X относительно дела R именуется огромное количество

R(X) = xÎX, (x, y)ÎR ;

прототипом X относительно R именуется R -1(X).

В теории выбора и принятия решений огромную роль играют бинарные дела предпочтения, другими словами такие дела, согласно которым в Теоретический материал к заданию № 3. паре (x, y)ÎR элемент x в каком-то смысле лучше чем y. К примеру:

- в смысле дела R2 "лучше" значит "больше либо равно";

- в смысле дела R3 понятие "лучше" может означать "отстоит не больше чем на единицу".

Операции над бинарными отношениями определяются подобно операциям над надлежащими огромными количествами Теоретический материал к заданию № 3.. Пусть А – случайное огромное количество на котором введены бинарные дела R, R1, R2,...

1) Объединение 2-ух бинарных отношений R1 и R2 - это отношение

R1ÈR2 = (x, y)ÎR1 либо (x, y)ÎR2 .

2) Скрещение 2-ух бинарных отношений R1 и R2 - это отношение

R1ÇR2 = (x, y)ÎR1 и (x, y)ÎR Теоретический материал к заданию № 3.2 .

3) Оборотное отношение R –1 = (y, x)ÎR.

4) Дополнение к отношению = (x, y)Î(A´A)\R.

5) Двоякое отношение Rd = .

6) Композиция (суперпозиция) отношений R=R1oR2 содержит пару (x, y) и тогда только тогда, когда существует такое zÎA, что (x, y)ÎR1 и (z, y)ÎR2.

7) R1 содержится в R2 (R1 Í R Теоретический материал к заданию № 3.2), если неважно какая пара (x, y), которая принадлежит отношению R1 также принадлежит и отношению R2.

2. Характеристики операций над отношениями.

Приведем тут перечень главных параметров операций над отношениями и докажем некие из их.

1) Ç Rk -1=(Ç Rk) -1.

2) È Rk -1=(È Rk ) -1.

3) (R1 o R2) -1 = R1 -1o R2 -1.

4) (R1 o R2 )oR3 = R Теоретический материал к заданию № 3.1o(R2 o R3).

5) (R1 È R2 )oR3 = (R1 oR3 )È( R2o R3 ).

6) (R1 Ç R2 )oR3 Í (R1 oR3 )Ç( R2o R3 ).

7) а) если R1Í R2 то R1o R3 ÍR2o R3;

б) если R1 Í R2 то R1-1Í R2-1;

в) если R1 Í R2 то R3oR1 Í R3oR Теоретический материал к заданию № 3.2.

8) a) (R1È R2)d = R1d ÇR2d;

б) (R1Ç R2)d = R1d ÈR2d;

в) (R d)d = R.

Подтверждение.

Свойство 2.

Пусть пара (x, y)Î(È Rk ) -1. Тогда (y, x)ÎÈ Rk. Это значит, что найдется отношение Rj, что (y, x)Î Rj. Отсюда, по определению оборотного дела Теоретический материал к заданию № 3., (x, y)ÎRj-1, а означает, (x, y)ÎÈRk-1и (ÈRk)-1 Í È Rk-1.

Докажем оборотное включение.Пусть (x,y)Î Rk-1 Это значит, что найдется такое огромное количество Rj, что (x,y)ÎRj-1. Как следует, (y, x)ÎRj и (y, x)Î ÈRk ,потому (x, y)Î(È Rk )-1. Означает, È Rk-1 Í (ÈRk)-1.

Одновременное выполнение обоих Теоретический материал к заданию № 3. включений значит равенство множеств, что и требовалось обосновать.

Свойство 6.

Пусть (x, y)Î(R1 ÇR2)oR3. По определению композиции это значит, что найдется такое zÎA, что (x, z)Î(R1ÇR2) и (z, y)ÎR3.

1-ое включение может быть только тогда, когда сразу выполнено (x, z)ÎR1 и (x, z Теоретический материал к заданию № 3.)ÎR2. Это, в свою очередь значит, с учетом (z, y)ÎR3, что сразу (x, y)ÎR1oR3 и (x, y)ÎR2oR3, а, как следует, (x, y)Î(R1oR3)Ç(R2oR3), что и обосновывает требуемое соотношение.

ЗАМЕЧАНИЕ. Покажем, почему ошибочно оборотное включение. Пусть (x, y)Î(R1oR3)Ç Теоретический материал к заданию № 3.(R2oR3), тогда (x, y) Î(R1oR3) и (x, y) Î(R2oR3). 1-ое включение значит существование такового элемента z1 из A, что (x, z1)ÎR1 и (z1, y)ÎR3, 2-ое - существование такового z2ÎA, что (x, z2)ÎR2 и (z2, y)ÎR3, при этом необязательно z1=z2. Означает, не всегда существует Теоретический материал к заданию № 3. таковой элемент z, что (x, z)ÎR1 и (x, z)ÎR2, а, как следует, не будет принадлежности скрещению R1 и R2.

Свойство 7б.

Возьмём всякую пару (x, y)ÎR1, что эквивалентно (y, х)Î ÎR1-1. Пусть сейчас R1ÍR2, т.е. из (x, y)ÎR1 следует (x Теоретический материал к заданию № 3., y)ÎR2. Перейдя к оборотным отношениям, получим, что из (y, х)ÎR1-1 вытекает (y, х)ÎR2-1, что и значит требуемое свойство.

Свойство 8а.

Докажем за ранее равенство (`R )-1=`R-1

Пусть (x, y)Î(`R )-1. Как следует, (y, x) Î`R либо другими словами (y, x)ÏR. Отсюда, ( x, y)Ï R-1, что значит и (x Теоретический материал к заданию № 3., y)Î`R-1 . Если же (x, y) Î`R-1 , то (x, y)ÏR-1 и (y, x)ÏR. Тогда (y, x)Î`R либо, что то же самое, (x,y)Î(`R )-1.

Для подтверждения характеристики 8а воспользуемся доказанным равенством и известными качествами операций над огромными количествами и отношениями.

________­­_ _______

(R1ÈR2)d = ( R1ÈR2)-1 = ( R Теоретический материал к заданию № 3.1ÈR2)-1 =

=(`R1Ç`R2) =`R1-1 Ç `R2-1 = R1d Ç R2d.

3. Методы задания бинарных отношений

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

1. Матричное задание. Оно употребляется когда А – конечное огромное количество Теоретический материал к заданию № 3. А={xi}. Тогда отношение R можно задавать при помощи матрицы R={xij}, элементы которой определяются соотношением:

2. Задание при помощи графа.

Для конечного огромного количества А отношение можно задавать при помощи графа Г(R), который является геометрическим образом бинарного дела. Граф - фигура состоящая из точек (вершин) соединенных линиями (дугами). Верхушки Теоретический материал к заданию № 3. графа соответствуют элементам огромного количества А, другими словами xi, а наличие дуги, соединяющей верхушки xi и xj, значит, что (xi,xj)ÎR. Чтоб выделить упорядоченность пары на дуге ставится стрелка.

Главные характеристики графа.

1) Г(R-1) выходит из Г(R) конфигурацией направления стрелок на обратные.

2) Граф Г(А´ Теоретический материал к заданию № 3.;А) содержит дуги, соединяющие всякую пару (xi, xj). Таковой граф назывыется полным.

3. Задание верхними и нижними срезами.

Этот метод может быть применен для всех множеств и отношений. Пусть на огромном количестве А задано отношение R. Верхний срез GR (x) дела R в точке x ÎА - это огромное количество частей Теоретический материал к заданию № 3. yÎА таких, что (y, x)ÎR, т.е.

GR(x) = yÎA .

Если рассматривать R как отношение предпочтения, то GR (x) – это огромное количество частей, наилучших чем х.

Нижний срез HR(x) дела R в точке xÎА - это огромное количество частей yÎА, таких, что (x, y Теоретический материал к заданию № 3.)ÎR, т.е.

HR(x) = yÎA .

Характеристики нижних и верхних срезов.

Для хоть какого хÎA и хоть какого дела Ri ÍA´A производятся соотношения.

1. а) GRÇR(x)=GR(x)ÇGR(x); б) HRÇR(x)=HR(x)ÇHR(x)

2. a) G`R(x) = A\GR(x); б)H`R(x Теоретический материал к заданию № 3.) = A\HR(x).

3. a) GR-1(x) = HR(x); б) HR-1(x) = HR(x).

4. GA´A(x) = HA´A(x) = A.

4. Характеристики бинарных отношений.

1) Рефлексивность.

Отношение R именуется рефлексивным, если (х, х)ÎR для хоть какого хÎA.

Примеры рефлексивных отношений: дела "³", "£" на огромном Теоретический материал к заданию № 3. количестве R.

2) Антирефлексивность.

Отношение R именуется антирефлексивным, если (х, х)ÏR для хоть какого хÎA.

Примеры антирефлексивных отношений: дела "" на огромном количестве R.

Если R - антирефлексивное отношение, то xÏGR(x) и хÏHR(x)

для хоть какого хÎA .

3) Симметричность.

Отношение R именуется симметричным, если для всех Теоретический материал к заданию № 3. x,yÎA из того, что (x, y)ÎR следует (y, x)ÎR и назад.

Примеры симметричных отношений: дела "=" и "¹".

Если отношение R симметрично, то для хоть какого хÎA

а) GR(x) = HR(x); б) R = R-1.

4) Антисимметричность.

Отношение R именуется антисимметричным, если для всех x и y из A Теоретический материал к заданию № 3. из одновременного выполнения критерий (x, y)ÎR и (y, x)ÎR следует, что x = y.

Пример антисимметричного дела. Пусть А - огромное количество людей в данной очереди. Отношение R "не стоять за кем-то в очереди" будет антисимметричным.

Пусть х=ВАСЯ, а y=ИВАНОВ. Тот факт, что (x, y Теоретический материал к заданию № 3.)ÎR значит, что "ВАСЯ не стоит в очереди за ИВАНОВЫМ", (y, x)ÎR - "ИВАНОВ не стоит за ВАСЕЙ". Разумеется, что одновременное выполнение обоихвключений может быть, только если ВАСЯ и есть ИВАНОВ, т.е. x = y.

Отношение "³" также антисимметрично: если x³y и y³x, то Теоретический материал к заданию № 3. x=y.

5) Асимметричность.

Отношение R асимметрично, если RÇ R-1= Æ, т.е. скрещение

дела R с оборотным отношением пусто.

Эквивалентное определение асимметричности: из 2-ух отношений (x, y)ÎR и (y, x)ÎR одно не производится.

Примеры асимметричных отношений: ">", "<", "быть начальником". Если R - асимметричное отношение, то из xRy следует yRx.

Для хоть какого дела Теоретический материал к заданию № 3. R вводятся понятия симметричной части дела Rs =R ÇR-1 и асимметричной части дела Ra = R \ Rs. Если отношение R симметрично, то R= Rs, если отношение R асимметрично, то R= Ra.

Примеры. Если R - "³", то R-1 - "<", Rs - "=", Ra - ">".

6) Транзитивность.

Отношение R транзитивно, если для любыx x, y, zÎA Теоретический материал к заданию № 3. из того, что (x, y)ÎR и (y, z)ÎR следует (x, z)ÎR.

Характеристики транзитивного дела:

а) RoRÍR;

б) для хоть какого хÎA из yÎGR(x) следует, что GR(y)ÍGR(x).

Нетранзитивным является отношение "¹". Пусть x=2, y=3, z=2, тогда справедливо x¹y Теоретический материал к заданию № 3. и y¹z, но x=z, т.е. (x, z)ÏR.

Отношение R1 именуется транзитивным относительно дела R2, если:

а) из (x, y)Î R1 и (y, x)Î R2 следует, что (x, z)Î R1;

б) из (x, y)Î R2 и (y, x)Î R1 следует, что (x, z)Î R1.

7) Негатранзитивность Теоретический материал к заданию № 3..

Отношение R именуется негатранзитивным, если`R транзитивно.

Примеры.

Дела R1 - ">" и R2 - " ¹" негатранзитивны, потому что отношения`R1 - "£",`R2 - "=" транзитивны. Может быть одновременное выполнение параметров транзитивности и негатранзитивности. К примеру, отношение R1 сразу транзитивно и негатранзитивно, а R2 , как понятно, транзитивным не является.

8) Полнота.

Отношение R много, если для Теоретический материал к заданию № 3. всех x,yÎА или (x, y)ÎR, или (y, x)ÎR, или оба дела производятся сразу.

Характеристики полных отношений:

а) GR(x)ÈHR(x) = А для хоть какого хÎA;

б) полное отношение рефлексивно.

9) Слабенькая полнота.

Отношение R именуется слабо полным, если для всех х¹y из А либо Теоретический материал к заданию № 3. (x, y)ÎR, либо (y, x)ÎR.

Пример слабо полного дела. Пусть А - огромное количество компаний, "неблагополучных" в смысле собственного бюджета. Отношение R "быть подабающим" является слабо полным, потому что каждое из этих компаний либо кому-либо должно, либо ему кто-то должен, но быть подабающим себе нельэя Теоретический материал к заданию № 3. и (x, x)ÏR.

10) Ацикличность.

Бинарное отношение R ациклично, если Rn ÇR-1= Æ для хоть какого nÎN . Другими словами, если из хоть какой конечной цепочки отношений хRу, уRt,..., vRz следует, что z¹х, то отношение R ациклично.

9. Пусть дела R1, R2 - симметричны. Обосновать, что для того чтоб R Теоретический материал к заданию № 3.1oR2 было симметрично нужно и довольно, чтоб производилось равенство R1oR2 = R2oR1.

5. Связи меж бинарными отношениями.

1. Отношение R симметрично и тогда только тогда, когда R = R-1.

2. Если R рефлексивно, то Rd антирефлексивно, если R антирефлексивно, то Rd рефлексивно.

3. Отношение R слабо много и тогда только тогда, когда Rd Теоретический материал к заданию № 3. антисимметрично.

Подтверждение. Пусть R слабо много и x¹y. Разглядим три варианта.

1) (x, y)ÎR.Тогда, по определению оборотного дела

(y,x)ÎR-1, а по определению двоякого дела - (y,x)ÏRd.

2) (y,x)ÎR, тогда (x, y)ÎR-1 и, как следует, (x,y)Ï`R-1 = Rd.

3) (x, y)ÎR Теоретический материал к заданию № 3. и сразу (y, x)ÎR. Отсюда, (y, х)ÏRd и

(x, y)Ï Rd.

Потому что R - слабо полное отношение, то для всех x¹y производится или случай а), или б), или в). Ни в каком из этих случаев включения (x, y)ÎRd и (y, x)ÎRd не могут производиться Теоретический материал к заданию № 3. сразу. Как следует, отношение Rd антисимметрично.

Докажем, что из антисимметричности Rd следует слабенькая полнота дела R. Разглядим эквивалентное определение антисимметричности. Если x¹y, то или (x,y)ÎRd и (y,x)Ï Rd, или (x,y)ÏRd и (y,x)ÎRd, или (x,y)ÏRdи (y,x)ÏRd. В первом Теоретический материал к заданию № 3. случае получим, что (x,y)ÎR, во 2-м - (y,x)ÎR, в 3-ем - (x,y)ÎR и (y,x)ÎR. Это утверждение значит, что отношение R слабо много.

4. Отношение R асимметрично и тогда только тогда, когда Rd много.

Подтверждение. Пусть R - асимметрично. Тогда по определению, RÇR-1 = Æ. Разглядим два варианта Теоретический материал к заданию № 3..

1) (x, y)ÎR. Тогда (х, y)ÏR-1, означает, (x, y)ÎRd.

2) (x, y)ÏR. Тогда (x, y)Î`R и (y, x) Î`R-1 = Rd.

В любом случае или (x, y)ÎRd, или (y, x)ÎRd, а это значит, что Rd - много.

Докажем оборотное следствие. Пусть Rd много. Опять разглядим Теоретический материал к заданию № 3. два варианта:

а) (x, y)ÎRd, тогда (y, x)ÏR;

б) (y, x)ÎRd, тогда (x, y)ÏR.

Потому что Rd много, то или случай а), или случай б) всегда будет иметь место, а отсюда следует невозможность одновременного выполнения yRx и xRy. Это значит, что R асимметрично.

Примеры решений Теоретический материал к заданию № 3. задания № 3.

Пример 1.

Обосновать, что если дела R1, R2 рефлексивны, то справедливо включение R1ÈR2 Í R1oR2 .

Подтверждение.

Пусть (x, y)ÎR1ÈR2, тогда (x, y)ÎR1 либо (x, y)ÎR2. В первом случае из рефлексивности R2 следует (y, y)ÎR2 и, как следует, (x, y)Î R1oR2. Аналогично для второго варианта Теоретический материал к заданию № 3. получим (x, x)ÎR1 и (x, y)ÎR1oR2, что и требовалось обосновать.

Пример 2.

Обосновать, что дела RÈ(`RÇRd )=RÈ(`R )s полны.

Докажем равенство множеств, воспользовавшись качествами операций над огромными количествами и отношениями.

RÈ(`R Ç Rd ) = RÈ(`R Ç`R-1) = RÈ(`RÇ(`R )-1) = =RÈ(`R Теоретический материал к заданию № 3. )s.

Покажем сейчас, что отношение RÈ(`R )s много. Для всех x, yÎA вероятен один из 3-х случаев:

1) (x, y)ÎR;

2) (y, x)ÎR;

3) (x, y)ÏR и (y, x)ÏR.

В первых 2-ух случаях принадлежность (x,y) к рассматриваемому отношению явна. Разглядим 3-ий случай. Потому что (x,y)Î`R и Теоретический материал к заданию № 3. (x,y)Î R-1, то (x,y)Î(`R )s. Как следует, рассматриваемое отношение много.

Варианты задания №1. Обосновать соотношение.

0. AÇ(BÇC) = (AÇB)ÇC.

1. AÈ(BÈ C) = (AÈB)È C.

2. .

3. .

4. .

5. .

6. .

7. .

8. (AÈB) \ C = (A \ C) È (B \ C).

9. A \ (B Ç C) = (A \ B) È (A \ C).

Варианты задания №2.

0.

a). Найти Теоретический материал к заданию № 3. проекции , если

б). Найти проекции огромного количества векторов : , если

.

Найти проекции упорядоченного огромного количества векторов : , если

.

г). Пусть Отыскать .

д). Сопоставить векторные оценки огромного количества

. Отыскать парето-оптимальные оценки.

1.

a). Найти проекции , если

б). Найти проекции огромного количества векторов : , если

.

Найти проекции упорядоченного огромного количества векторов : , если

.

г). Пусть Отыскать .

д). Сопоставить векторные оценки Теоретический материал к заданию № 3. огромного количества

. Отыскать парето-оптимальные оценки.

2.

a). Найти проекции , если

б). Найти проекции огромного количества векторов : , если

.

Найти проекции упорядоченного огромного количества векторов : , если

.

г). Пусть Отыскать .

д). Сопоставить векторные оценки огромного количества

. Отыскать парето-оптимальные оценки.

3.

a). Найти проекции , если

б). Найти проекции огромного количества векторов : , если

.

Найти проекции упорядоченного огромного количества векторов Теоретический материал к заданию № 3. : , если

.

г). Пусть Отыскать .

д). Сопоставить векторные оценки огромного количества

. Отыскать парето-оптимальные оценки.

4.

a). Найти проекции , если

б). Найти проекции огромного количества векторов : , если

.

Найти проекции упорядоченного огромного количества векторов : , если

.

г). Пусть Отыскать .

д). Сопоставить векторные оценки огромного количества

. Отыскать парето-оптимальные оценки.

5.

a). Найти проекции , если

б). Найти проекции огромного количества векторов : , если

.

Найти Теоретический материал к заданию № 3. проекции упорядоченного огромного количества векторов : , если

.

г). Пусть Отыскать .

д). Сопоставить векторные оценки огромного количества

. Отыскать парето-оптимальные оценки.

6.

a). Найти проекции , если

б). Найти проекции огромного количества векторов : , если

.

Найти проекции упорядоченного огромного количества векторов : , если

.

г). Пусть Отыскать .

д). Сопоставить векторные оценки огромного количества

. Отыскать парето-оптимальные оценки.

7.

a). Найти проекции , если Теоретический материал к заданию № 3.

б). Найти проекции огромного количества векторов : , если

.

Найти проекции упорядоченного огромного количества векторов : , если

.

г). Пусть Отыскать .

д). Сопоставить векторные оценки огромного количества

. Отыскать парето-оптимальные оценки.

8.

a). Найти проекции , если

б). Найти проекции огромного количества векторов : , если

.

Найти проекции упорядоченного огромного количества векторов : , если

.

г). Пусть Отыскать .

д). Сопоставить векторные оценки огромного количества

. Отыскать Теоретический материал к заданию № 3. парето-оптимальные оценки.

9.

a). Найти проекции , если

б). Найти проекции огромного количества векторов : , если

.

Найти проекции упорядоченного огромного количества векторов : , если

.

г). Пусть Отыскать .

д). Сопоставить векторные оценки огромного количества

. Отыскать парето-оптимальные оценки.

Варианты задания №3.

0. Обосновать, что если отношение R транзитивно, то R-1 также является транзитивным.

1. Обосновать, что из Теоретический материал к заданию № 3. асимметричности дела R следует асимметричность R-1.

2. Обосновать, что из антисимметричности дела R следует антисимметричность R-1.

3. Обосновать, что из рефлексивности дела R следует рефлексивность R -1.

4. Обосновать, что для симметричности дела R нужно и довольно, чтоб Rd было симметрично.

5. Обосновать, что если дела R1 и R2 рефлексивны, то рефлексивны дела R1ÈR2 , R Теоретический материал к заданию № 3.1ÇR2 , R1-1.

6. Обосновать, что если дела R1 и R2 антирефлексивны, то антирефлексивны и дела R1ÈR2, R1ÇR2, R1-1.

7. Обосновать, что если дела R1 и R2 симметричны, то симметричны дела R1ÈR2, R1ÇR2, R1-1.

8. Обосновать, что если дела R1 и R2 антисимметричны, то антисимметричны также R1ÇR Теоретический материал к заданию № 3.2 и R1-1.

9. Пусть дела R1, R2 - симметричны. Обосновать, что для того чтоб R1oR2 было симметрично нужно и довольно, чтоб производилось равенство R1oR2 = R2oR1.


teoreticheskie-aspekti-morfologii-kursovaya-rabota.html
teoreticheskie-aspekti-organizacii-reklamnoj-deyatelnosti-na-predpriyatiyah-industrii-gostepriimstva.html
teoreticheskie-aspekti-problemi-nevmenyaemosti.html