Третья нормальная форма

Определение 4. Атрибут A_k транзитивно зависит от множества атрибутов ,если существует множество, состоящее из атрибутов ,каждый из которых функционально зависит от ,такое, что A_k функционально зависит от .

Определение 5. (3NF) Файл с первичным ключом находится в третьей нормальной форме, если он находится в первой нормальной форме, и для любого функциональная зависимость атрибута A_k от атрибутов не является транзитивной.

Произвольный ключ отношения можно выделить как первичный. Если с помощью выделения любого ключа как первичного мы получаем отношение, находящееся в третьей нормальной форме, то заданное отношение называется находящимся в нормальной форме Бойса-Кодда. В частности, отношение будет находиться в нормальной форме Бойса-Кодда, если оно допускает единственный ключ.

1.8. Упражнения

1. Задано подмножество AÍU. Найти все подмножестваXÍU, для которых

AÇX=.

2. Решить систему уравнений

3. Решить уравнения

(1) .

(2) .

(3) .

(4) .

4. Пусть - множество всех функций B®A. Установить биекции между множествами

(1) A ´ B и B ´ A;

(2) (A ´ B)^С и A^C ´ B^C;

(3) (A^B)^Cи A^B´C;

(4) A^BÈCи A^B´A^C, если BÇC =Æ.

5. Построить бинарное отношение

(1) рефлексивное, симметричное, не транзитивное,

(2) рефлексивное, антисимметричное, не транзитивное,

(3) рефлексивное, транзитивное, не симметричное,

(4) антисимметричное, транзитивное, не рефлексивное.

6. Доказать, что пересечение семейства отношений эквивалентности на заданном множестве является отношением эквивалентности.

7. Построить пример частично упорядоченного множества, имеющего ровно один минимальный элемент, но не имеющего наименьшего элемента.

8. Доказать, что если R– отношение порядка, тоR^-1– отношение порядка.

9. Доказать, что пересечение отношений порядка является отношением порядка. Всегда ли объединение отношений порядка является отношением порядка?

10. Найти число рефлексивных отношений на множестве из nэлементов.

11. Найти число симметричных отношений на множестве из nэлементов.

12. Будет ли множество функций X  Rрешеткой относительно отношения порядка

fg f(a) g(a)?

13. Сколько подмножеств множества A={1,2,∙∙∙,300} содержат по крайней мере одно число кратное 5, и ни одного – кратного 10.

14. Сколько подмножеств множества A={1,2,∙∙∙,300} не содержат ни чисел кратных 4, ни чисел кратных 6?

15. Сколько подмножеств множества A={1,2,∙∙∙,300} состоят из чисел кратных 4, но не содержат чисел кратных 6?

16. Сколько подмножеств множества A={1,2,∙∙∙,300} состоят из чисел кратных 4 и, сверх того, содержат по крайней мере одно число кратное 6 ?

2. Комбинаторика

Комбинаторикойназывается раздел дискретной математики, который занимается следующими вопросами:

1. Задача перечисления: найти количество элементов заданной математической модели.

1. Задача перебора: построить алгоритм перебора этих элементов.

Основное внимание мы будем уделять задаче перечисления.

Конечная математическая модель в комбинаторике называется конфигурацией. Мы изучим следующие конфигурации: размещения, сочетания, разбиения и их обобщения. Для дальнейшего изучения рекомендуем [14], [15], [21].