рефераты бесплатно
Рефераты бесплатно, курсовые, дипломы, научные работы, курсовые работы, реферат, доклады, рефераты, рефераты скачать, рефераты на тему, сочинения,рефераты литература, рефераты биология, рефераты медицина, рефераты право, большая бибилиотека рефератов, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент и многое другое.
ENG
РУС
 
рефераты бесплатно
ВХОДрефераты бесплатно             Регистрация

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

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














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

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


Зміст


Введення

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 можна сформулювати умова транзитивності відповідного простору залежності.


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

 

Теорема 1.

Нехай  Z - довільний простір залежності. Розглянемо наступні три твердження:

X базис в A;

X максимальна незалежна підмножина в A;

 X мінімальна множина, що породжує, в A.

Тоді  й .

Доказ:

(i)  (ii)     Якщо X – базис, то по визначенню 6 X – незалежна підмножина, що породжує. Доведемо від противного, що воно максимальне. Нехай існують незалежні множини . Візьмемо , тоді  незалежно, тому що будь-яка підмножина незалежної множини незалежно. Тому по визначеннях 3 і 5 , звідки , одержали протиріччя з умовою. Тому X є максимальною незалежною підмножиною в A.

(ii)  (i)     Доведемо від противного, нехай  не базис в , тобто . Тоді  таке, що незалежно й лежить в , одержали протиріччя з максимальністю .

(ii)  (iii) Якщо X — максимальна незалежна множина в A, те всякий елемент в A або належить X, або такий, що залежно, а тому  в тім і іншому випадку, тобто  Оскільки , те X - множина, що породжує. Виходить,  - базис простору .

Доведемо тепер, що воно мінімально. Нехай множина . Доведемо, що воно не є породжує для A. Візьмемо , але . Тоді  незалежно, як підмножина множини X. Тому по визначеннях 3 і 5  і , а це значить, що Y не є множиною, що породжує. Висновок: X – мінімальна множина, що породжує, в A.

(i)  (iii) Справедливо, по доведеним вище твердженнях (i) (ii) і (ii) (iii). :

Визначення - позначення 10.

Для довільної множини  простору залежності  Z позначимо  множину всіх максимальних незалежних підмножин, а через  - множину всіх мінімальних підмножин, що породжують, цієї множини.

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

Наступний приклад показує, що зворотне включення  вірно не завжди.

Приклад 10.

Розглянемо дев'яти елементну множину , що записана у вигляді матриці . Залежними будемо вважати підмножини множини , що містять «прямі лінії»: стовпці, рядки або діагоналі матриці .

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

Розглянемо ще одну множину , вона є мінімальним що породжує, тому що якщо виключити з нього хоча б один елемент, то воно вже не буде множиною, що породжує. Легко помітити, що  залежно, тому не є базисом. Даний приклад ілюструє, що (iii) (i) не вірно в загальному випадку, тобто для довільних просторів залежності.

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

Заміщення. Якщо

Доказ:

Нехай , . Тому що  залежить від , те  залежить від незалежної підмножини  множини , тобто  залежно. Тепер, якби , те  було б підмножиною множини  й тому , що суперечило б нашому припущенню. Тому . Візьмемо . Тоді  незалежно, тому що . Але  залежно. Звідки .

Страницы: 1, 2


© 2010.