Вивчення поняття відносин залежності (86278)

Посмотреть архив целиком














Курсова робота

Вивчення поняття відносин залежності



Зміст


Введення


1. Визначення й приклади

2. Простір залежності

3. Транзитивність

4. Зв'язок транзитивних відносин залежності з операторами замикання

5. Матроїди

Висновок

Список літератури



Введення


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

Поставлена мета припускає рішення наступних задач:

Вивчити й дати визначення поняттю відношення залежності.

Розглянути деякі приклади відносини залежності.

Сформулювати й довести властивості й теореми як для довільних, так і для транзитивних просторів залежності.

Розглянути теорему про зв'язок транзитивного відношення залежності й алгебраїчного оператора замикання.

Вивчити поняття матроїда, привести приклади матроїдів.

Розглянути жадібний алгоритм і його зв'язок з матроїдами.

На підставі поставлених цілей і задач кваліфікаційна робота розбивається на 5 параграфів.

У першому параграфі наведені основні визначення й розглянуті деякі приклади відносини залежності.

У другому - розглядаються довільні простори залежності, їхньої властивості й деяких теорем.

Третій – присвячений транзитивним і кінцеве мірним просторам залежності. Тут розглянуті властивості транзитивних просторів залежності й доведені теореми, які підтверджують існування базису й інваріантність розмірності в будь-якому кінцеве мірному транзитивному просторі залежності.

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

П'ятий параграф присвячений матроїдам, прикладам матроїдів і їхньому застосуванню при вивченні теоретичною основою аналізу «жадібних» алгоритмів.

Основною літературою при написанні кваліфікаційної роботи стали монографії: Кона П. «Універсальна алгебра» [2] і Куроша О. Г. «Курс вищої алгебри» [3].



1. Визначення й приклади


Визначення 1.

Множина Z підмножин множини A назвемо відношенням залежності на A, якщо виконуються наступні аксіоми:


Z1: Z ;

Z2: Z Z ;

Z3: Z ( Z - звичайно).


Підмножина множини A називається залежною, якщо вона належить Z, і незалежною у противному випадку.

Легко переконатися в незалежності аксіом Z1 - Z3..

Модель 1: . Думаємо Z = B (А) для будь-якої множини .

Модель 2: . Нехай Z = при .

Модель 3: . Нехай Z = для нескінченної множини .

Визначення 2.

Простором залежності назвемо пари Z , де Z – відношення залежності на A.

Визначення 3.

Елемент називається залежним від множини , якщо а  X або існує така незалежна підмножина Y множини X, що залежно, тобто Z Z ).

З визначення 1 випливає, що якщо елемент залежить від множини , то він залежить від деякої кінцевої підмножини .



Визначення 4.

Множина всіх елементів, що залежать від X, називається оболонкою множини X і позначається через .

Ясно, що й включення тягне включення їхніх оболонок: .

Визначення 5.

Якщо = A, то X називається множиною, що породжує, множини A.

Визначення 6.

Незалежна підмножина, що породжує, множини A називається базисом множини A.

Визначення 7.

Множина залежить від , якщо будь-який елемент із залежить від , тобто .

Визначення 8.

Відношення залежності Z на A будемо називати транзитивним відношенням залежності, якщо .

Визначення 9.

Транзитивним простором залежності назвемо простір залежності, у якому відношення залежності має властивість транзитивності.

Як теоретико-множинний постулат будемо використовувати наступний принцип, еквівалентний відомій аксіомі вибору.

Лема Цорна.

Непуста впорядкована множина, у якому кожне лінійно впорядкована підмножина має верхню грань, має максимальний елемент.

Далі доцільно розглянути деякі приклади відносини залежності:



Приклад 1.

Поняття лінійної залежності у векторному просторі V над полем . Система векторів векторного простору V називається лінійно залежної, якщо існує кінцева лінійно залежна її підсистема, у противному випадку – лінійно незалежної.

Поняття лінійної залежності в кінцеве мірних векторних просторах дається в курсі алгебри. Кінцева система векторів V називається лінійно залежної, якщо існують елементи поля одночасно не рівні нулю й такі, що лінійна комбінація . Множина лінійних комбінацій множини векторів векторного простору V з коефіцієнтами з поля P називається лінійною оболонкою цих векторів і позначається . При цьому - є підпростором у просторі V, породженим . Одержуємо транзитивне відношення залежності.

Приклад 2.

Нехай поле є розширенням основного поля Р, а мінімальне підкольце утримуючі елементи й поле Р. Підкольце складається із всіх елементів поля, які виражаються через елементи й елементи поля Р за допомогою додавання, вирахування й множення: це будуть усілякі багаточлени від з коефіцієнтами з поля Р. Тоді, якщо для всякого елемента існує єдиний запис у вигляді багаточлена від як невідомих з коефіцієнтами з поля Р, тобто якщо різні багаточлени від будуть різними елементами підкольца , те система елементів , буде називатися алгебраїчно незалежної над полем Р, у противному випадку алгебраїчно залежної. Довільна множина елементів поля Р називається залежним, якщо воно містить кінцеву залежну підмножину. У першому випадку кільце ізоморфно кільцю багаточленів . Відношення алгебраїчної залежності над полем Р є транзитивним відношенням залежності.

Приклад 3.

Нехай на множині A задане рефлексивне й симетричне бінарне відношення (називане відношенням подібності). Підмножина X множини A будемо вважати залежним, якщо воно містить два різних елементи, що перебувають у відношенні .

Оболонкою множини служить множина



У цьому випадку можна підсилити аксіому відносини залежності в такий спосіб:


Z Z.


Тоді оболонкою множини буде множина всіх елементів, що перебувають відносно подібності хоча б з одним елементом із множини .

Уведене відношення залежності буде транзитивним тоді й тільки тоді, коли відповідне бінарне відношення буде транзитивне, тобто є відношенням еквівалентності на .

У випадку, коли - відношення еквівалентності буде незалежним тоді й тільки тоді, коли множина містить не більше одного елемента. Будь-яка максимальна незалежна підмножина буде містити рівно по одному елементі з кожного класу еквівалентності .

Приклад 4.

Розглянемо чотирьох елементну множину .

Назвемо підмножину множини залежним тоді й тільки тоді, коли або .


Z .


Розглянемо підмножину множини , по уведеному визначенню воно буде незалежно. Розглянемо оболонку множини й знайдемо оболонку оболонки нашої множини . Таким чином, ми одержали, тобто розглянуте нами відношення залежності не є транзитивним.

Приклад 5.

Розглянемо довільну множину й . Множина будемо вважати залежним, якщо B (А)\ B (В), тобто , але . Таким чином, одержали наступний транзитивний простір залежності: B (А)\ B (В. Оболонкою буде множина .

Зокрема можна розглянути 2 випадки:

, тобто всі множини незалежні, тоді .

B (А) , тобто всі множини, крім порожнього, будуть залежними, у цьому випадку .

Приклад 6.

Розглянемо довільну множину і його непусту кінцеву підмножину . Уведемо на множині А наступне відношення залежності


Z B (А) .


Таким чином, залежними будуть всі надмножини множини .


Якщо , то .

Якщо , то .

Якщо , то .


Одержуємо транзитивний простір залежності.

Приклад 7.

Підпростір простору залежності Z . Розглянемо , де діє те ж відношення залежності Z. Тоді одержимо індукований простір залежності Z B . У цьому випадку залежними будуть тільки ті підмножини множини, які були залежні в просторі Z . І якщо простір Z транзитивне, те транзитивним буде й підпростір .

Приклад 8.

Нехай і Z = . Такий простір залежності Z не транзитивне, тому що й . Простір А має два базиси й, які є і єдиними мінімальними множинами, що породжують в.

Цей приклад показує, що існують не транзитивні простори залежності, у яких мінімальні множини, що породжують, незалежні, тобто є базисами.

Приклад 9.

Задамо на множині N натуральних чисел наступне відношення залежності:


Z .


Одержуємо нескінченну строго зростаючий ланцюжок оболонок в Z . При одержуємо

.

Таким чином, маємо .

Зауваження.

Поняття простору залежності можна й зручно визначати через базу залежності. Саме, множина B всіх мінімальних залежних множин простору залежності Z назвемо його базою. Ясно, що множини з B не порожні, кінцеві й не втримуються друг у другу. Крім того, будь-яка незалежна множина містить деяка множина бази B. Простір Z має єдину базу й однозначно визначається їй. Тому простору залежності можна задавати базами.

Легко бачити, що вірно наступне твердження:

Непуста множина B підмножин множини задає на відношення залежності тоді й тільки тоді, коли множини з B не порожні, кінцеві й не включений друг у друга.

У термінах бази B можна сформулювати умова транзитивності відповідного простору залежності.






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