Реферат

Реферат Решітки

Работа добавлена на сайт bukvasha.net: 2015-10-28

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 11.11.2024


Реферат на тему:

Решітки

Серед частково впорядкованих множин винятково важливу роль відіграють так звані решітки або структури.

Точною верхньою гранню підмножини A частково впорядкованої множини M (позначається supA) називають найменшу з верхніх граней підмножини A. Відповідно, точною нижньою гранню підмножини A частково впорядкованої множини M (позначається infA) називають найбільшу з нижніх граней підмножини A.

Частково впорядкована множина M називається решіткою (структурою), якщо для будь-якої пари елементів a,bM (тобто для будь-якої двоелементної підмножини множини M ) існують sup{a,b} і inf{a,b}.

Приклад 1. 1. Будь-яка лінійно впорядкована множина M (наприклад, числові множини N, Z, Q і R з традиційними відношеннями порядку) є решіткою. Якщо a,bM, то sup{a,b} = max(a,b) і inf{a,b} = min(a,b).

2. Розглянемо множину N натуральних чисел з відношенням часткового порядку "ділить". Для a,bN означимо sup{a,b} = НСК(a,b) і inf{a,b) = НСД(a,b) (НСК - найменше спільне кратне, НСД - найбільший спільний дільник). Тоді sup{12,32 }=96, inf{12,32}= 4, inf{16,27}=1.

3. Частково впорядкована за відношенням включення множина (M) всіх підмножин множини M є решіткою: sup{A,B}=AB і inf{A,B}= AB, A,BM.

4. Розглянемо множину R кортежів дійсних чисел довжини n з відношенням часткового порядку, означеним у прикладі 1.17(4), тобто (a1,a2,...,an)(b1,b2,...,bn) тоді і тільки тоді, коли aibi, i=1,2,...n. Частково впорядкована у такий спосіб множина R є решіткою: sup{(a1,a2,...,an),(b1,b2,...,bn)}=(c1,c2,...,cn), де ci = max(ai,bi), i=1,2,...n, а inf{(a1,a2,...,an),( b1,b2,...,bn)} = (d1,d2,...,dn), де di = min(ai,bi), i=1,2,...,n.

Аналогічно можуть бути перетворені на решітки множини кортежів Nn, Zn, Qn і Bn, де B = {0,1 } - множина двійкових цифр.

Множина P = {R1,R2,...,Rm} всіх можливих розбиттів деякої скінченної множини M може бути перетворена в решітку в такий спосіб. Вважаємо, що розбиття Ri={Ai1,Ai2,..., Aik} і Rj={Aj1,Aj2,...,Ajk} знаходиться у відношенні Ri < Rj, якщо кожен клас Ait, t=1,2,...,k розбиття Ri міститься в деякому класі Ajt розбиття Rj. Наприклад, для M ={1,2,3,4,5} розбиття R'={{1,2},{3},{4,5}} менше розбиття R''={{1,2,3},{4,5}} і менше розбиття R'''={{1,2},{3,4,5}}, а розбиття R'' і R''' непорівнювані.

Мінімальним елементом частково впорядкованої множини P є розбиття { {a} | aM}, а максимальним елементом - {M}. Тоді sup{Ri,Rj} = Rk, де Rk - розбиття, в якому елементи a,bM входять в один клас тоді і тільки тоді, коли існує такий cM, що кожна з пар елементів a і c та c і b належить одному класу або в Ri, або в R; inf{Ri,Rj} = Rl, де Rl - розбиття, в якому елементи a,bM належать одному класу тоді і тільки тоді, коли вони належать одному класу і в Ri, і в Rj.

Наприклад,

sup{R'',R'''} = {{1,2,3,4,5}}, sup{R',R''} = {{1,2,3},{4, 5}},

inf{R'',R'''} = {{1,2},{3},{4,5}}, inf{R',R''} = {{1,2},{3},{4,5}}.

Оскільки за теоремою 1.10 існує взаємно одозначна відповідність між усіма розбиттями даної множини M і всіма відношеннями еквівалентності на M, то множина всіх відношень еквівалентності на M може бути перетворена в решітку.

Скінченну частково впорядковану множину M зручно зображати у вигляді діаграми або структурного графа, вершини якого відповідають елементам множини M. З вершини a проводимо стрілку у вершину b, якщо a b і не існує такого c, що a c і c b. Стрілки (петлі), що відповідають діагональним парам (a,a) не проводимо.

Приклад 2. 1. На рис.1.6 зображено діаграми для чотирьох частково впорядкованих множин:

а) множини двійкових кортежів B3;

б) булеана (M) множини M = {a,b,c} з відношенням включення ;

в) множини натуральних чисел C={2,5,7,10,28,70} з відношенням "ділить";

г) множини D={a,b,c,d} з відношенням часткового порядку R={(a,a),(b,b),(c,c), (d,d),(a,c),(b,c),(a,d), (b,d)}.


а) б) в) г)

Рис.1.

  1. Діаграма будь-якої скінченної лінійно впорядкованої множини M={a1,a2,...,an}, ai ai+1, i=1,2,...,n-1 має вигляд


a1 a2 a3 an-1 an

Неважко переконатись, що ab, a,bM тоді і тільки тоді, коли в діаграмі частково впорядкованої множини M існує складений зі стрілок шлях, що веде з вершини a у вершину b. Верхня грань для {a,b} - це елемент, в який ведуть шляхи з a і з b. Нижня грань {a,b} - це елемент, з якого існують шляхи і в a, і в b.

Частково впорядкована множина не є решіткою тоді, коли

1) деяка пара елементів не має верхньої або нижньої грані;

2) для деякої пари елементів найменша верхня (або найбільша нижня) грань не існує.

Наприклад, перші дві множини B і (M) з прикладу 1. є решітками, тому що для їхніх діаграм не виконується жодна з наведених умов. Множина C не є решіткою, оскільки, наприклад, для пар {2,5}, {5,7}, {7,10} не існують нижні грані, а пари {10, 28} і { 28,70} не мають верхніх граней. Пара елементів {a,b} ({c,d}) множини D має дві верхні (дві нижні) грані c і d (відповідно a і b), однак не має найменшої верхньої (найбільшої нижньої) грані, оскільки елементи c і d (a і b) непорівнювані між собою.

Частково впорядкована множина M називається повною решіткою, якщо для будь-якої непорожньої підмножини AM в множині M існують найменша верхня грань sup A і найбільша нижня грань inf A. Очевидно, що довільна повна решітка є решіткою, але не будь-яка решітка є повною решіткою. Якщо M - повна решітка, то найменша верхня грань усієї множини M (sup M) називається одиницею даної решітки і позначається 1, а найбільша нижня грань множини M (inf M) називається нулем решітки і позначається 0. Вибір цих назв для sup M і inf M пояснюється такими властивостями елементів 1 і 0.

Для довільного елемента aM виконується

sup {1,a} = 1, sup {0,a} = a, a 1,

inf {1,a} = a, inf {0,a} = 0, a 0. (1.)

Очевидно, що елементи 0 і 1 є відповідно найменшим і найбільшим елементами повної решітки M.

Приклад 1.21. 1. Решітки B(M) і P з прикладу 1.19 є повними решітками. Одиницями цих решіток будуть відповідно (1,1,1), M і {M}, а нулями - (0,0,0), і { {a} | aM }.

2. Множина N натуральних чисел не є повною решіткою, оскільки будь-яка її нескінченна підмножина на має найменшої верхньої грані.

  1. Множина всіх дільників натурального числа n, частково впорядкована за відношенням "ділить", є повною решіткою. Одиницею в такій решітці є число n, а нулем - число 1.


1. Курсовая Венчурный капитал и его роль в финансировании инновационной деятельности
2. Реферат на тему Место и значение лыжного спорта в системе физического воспитания
3. Контрольная работа по Уголовно-исполнительному праву 2
4. Реферат Малый бизнес особенности и проблемы развития в современной России
5. Реферат Разработка проекта строительства дополнительного ствола из бездействующей скважины 8224 куста
6. Сочинение на тему Поэтический мир Иосифа Бродского
7. Реферат Назначение средств оргтехники
8. Контрольная работа Мочевыделительная система. Компоненты пищи, оказывающие влияние на функционирование пищеваритель
9. Реферат Модемы 2
10. Реферат Современное школьное математическое образование