Xreferat.com » Рефераты по математике » Вивчення поняття відносин залежності

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

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

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

Приклад 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Вивчення поняття відносин залежності виконуються наступні властивості:

Заміщення. Якщо Вивчення поняття відносин залежності

Доказ:

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

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

Доказ:

Доведемо від противного. Припустимо, що Вивчення поняття відносин залежності залежно, тоді в ньому найдеться кінцева залежна підмножина Вивчення поняття відносин залежності:Вивчення поняття відносин залежності . Маємо Вивчення поняття відносин залежності, одержали протиріччя з незалежністю Вивчення поняття відносин залежності.

Максимальність. Будь-яка незалежна множина втримується в максимальній незалежній множині.

Доказ:

Нехай Вивчення поняття відносин залежності - довільна незалежна множина в. Вивчення поняття відносин залежності Утворимо множину Вивчення поняття відносин залежності Z :Вивчення поняття відносин залежності всіх незалежних множин, що містять Вивчення поняття відносин залежності. Відносно Вивчення поняття відносин залежності множина Вивчення поняття відносин залежності є впорядкованою множиною, що задовольняє по властивості вкладеності, умові леми Цорна. Тоді по лемі Цорна в Вивчення поняття відносин залежності існує максимальний елемент Вивчення поняття відносин залежності.

Теорема 2.

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

Доказ:

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


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


Особливий інтерес представляють транзитивні простори залежності. Важливим результатом є доказ інваріантності розмірності будь-якого транзитивного простору залежності.

Доведемо деякі властивості, справедливі для транзитивних просторів залежності Вивчення поняття відносин залежності ZВивчення поняття відносин залежності .

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

Доказ:

Вивчення поняття відносин залежностіВивчення поняття відносин залежності залежить від Вивчення поняття відносин залежності, тобто Вивчення поняття відносин залежності Вивчення поняття відносин залежності, і Вивчення поняття відносин залежності. Розглянемо Вивчення поняття відносин залежності, тоді Вивчення поняття відносин залежностіВивчення поняття відносин залежностіВивчення поняття відносин залежності - незалежно й Вивчення поняття відносин залежності - залежно, а Вивчення поняття відносин залежності, одержуємо, що Вивчення поняття відносин залежності, тому Вивчення поняття відносин залежності. Маємо Вивчення поняття відносин залежності.

Вивчення поняття відносин залежностіПо визначенню 8 будь-яка підмножина Вивчення поняття відносин залежності залежить від Вивчення поняття відносин залежності

Властивість 2: Якщо Вивчення поняття відносин залежності залежить від Вивчення поняття відносин залежності, а Вивчення поняття відносин залежності залежить від Вивчення поняття відносин залежності, те Вивчення поняття відносин залежності залежить від Вивчення поняття відносин залежності.

Доказ:

Запишемо умову, використовуючи властивість 1 Вивчення поняття відносин залежності, а Вивчення поняття відносин залежності, тоді очевидно, що Вивчення поняття відносин залежності.

Властивість 3: Якщо X — мінімальна множина, що породжує, в A, те X - базис в A.

Доказ:

Нехай X — мінімальна множина, що породжує, в A. Покажемо, що воно не може бути залежним, тому що в цьому випадку його можна було б замінити власною підмножиною, що усе ще породжує A. Дійсно, у силу транзитивності відносини залежності, будь-яка множина, що породжує множина

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

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

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: