Математика. Раздел 1. Дискретная математика. Тетрадь 1. Казанцев Э.Ф. - 28 стр.

UptoLike

ВУЗ: 

МУМ | Москва

Составители: 

Рубрика: 

б) Во мно же ст ве под мно жеств уни вер саль но го мно же ст ва U от но -
ше ние A Í B есть от но ше ние час тич но го по ряд ка;
в) Схе ма ор га ни за ции под чи не ния в уч ре ж де нии есть отноше ние
час тич но го по ряд ка на мно же ст ве долж но стей.
2) От но ше ние час тич но го по ряд ка на мно же ст ве X , для ко то ро го
лю бые два эле мен та срав ни мы, то есть для лю бых x, y Î X x y или
y x, назы вается от но ше ни ем ли ней но го по ряд ка.
Пре ды ду щий при мер: а) — это от но ше ние ли ней но го по ряд ка;
а при мер б) — та ко вым не яв ля ет ся.
3) Мы оп ре де ли ли тип от но ше ний, ис поль зуя ин туи тив ное по ня -
тие по ряд ка (кто глав нее). Пусть на мно же ст ве X за да но от но ше ние час -
тич но го по ряд ка r . Как те перь срав нить па ры эле мен тов из мно же ст ва
X, то есть как за дать от но ше ние час тич но го по ряд ка на мно же ст ве X´X
(как срав нить под чи нён ных раз лич ных от де лов)? Один из воз мож ных
спо со бов со сто ит в сле дую щем: на мно же ст ве X´X оп ре де лим от но ше -
ние P ус ло ви ем:
<a,b> P <c,d>Û arc и brd.
От но ше ние P есть от но ше ние час тич но го по ряд ка. Оно на зы ва -
ет ся от но ше ни ем Па ре то.
4) Мно же ст во X с за дан ным на нём час тич ным (ли ней ным) по -
ряд ком на зывается час тич но (ли ней но) упо ря до чен ным. Обо зна чим
x p y, ес ли x y и x ¹ y. Го во рят, что эле мент y по кры ва ет эле мент x.
5) Час тич но упо ря до чен ное мно же ст во мож но пред ста вить в ви де
схе мы, в ко то рой ка ж дый эле мент изо бра жа ет ся точ кой на плос ко сти, и
ес ли y по кры ва ет x, то точ ки x и y со еди ня ют от рез ком, при чём точ ку x
рас по ла га ют ни же точ ки y. Та кие схе мы на зы ва ют ся диа грам ма ми
Хассе.
При мер: а) Пусть A = {1, 2, 3}. На мно же ст ве P(A) рас смот рим от -
но ше ние «быть под мно же ст вом». Мно же ст во P(A) со дер жит во семь эле -
мен тов: {Æ,{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}. Ему со от вет ст ву ет диа -
грам ма Хас се (ри су нок 1.1.5);
28
     б) Во множестве подмножеств универсального множества U отно-
шение A Í B есть отношение частичного порядка;
     в) Схема организации подчинения в учреждении есть отношение
частичного порядка на множестве должностей.

      2) Отношение частичного порядка на множестве X, для которого
любые два элемента сравнимы, то есть для любых x, y Î X x ¶ y или
y ¶ x, называется отношением линейного порядка.
       Предыдущий пример: а) — это отношение линейного порядка;
а пример б) — таковым не является.

       3) Мы определили тип отношений, используя интуитивное поня-
тие порядка (кто главнее). Пусть на множестве X задано отношение час-
тичного порядка r. Как теперь сравнить пары элементов из множества
X, то есть как задать отношение частичного порядка на множестве X´X
(как сравнить подчинённых различных отделов)? Один из возможных
способов состоит в следующем: на множестве X´X определим отноше-
ние P условием:

                         P Û arc и brd.

      Отношение P есть отношение частичного порядка. Оно называ-
ется отношением Парето.

     4) Множество X с заданным на нём частичным (линейным) по-
рядком называется частично (линейно) упорядоченным. Обозначим
x p y, если x ¶ y и x ¹ y. Говорят, что элемент y покрывает элемент x.

      5) Частично упорядоченное множество можно представить в виде
схемы, в которой каждый элемент изображается точкой на плоскости, и
если y покрывает x, то точки x и y соединяют отрезком, причём точку x
располагают ниже точки y. Такие схемы называются диаграммами
Хассе.
      Пример: а) Пусть A = {1, 2, 3}. На множестве P(A) рассмотрим от-
ношение «быть подмножеством». Множество P(A) содержит восемь эле-
ментов: {Æ,{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}. Ему соответствует диа-
грамма Хассе (рисунок 1.1.5);
28

Страницы