Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Неизбыточные покрытия. Теорема о структуре неизбыточного покрытия
Определение. Множество F-зависимостей F неизбыточно, если у него нет такого собственного подмножества F’, что F’ F. Если такое множество F’ существует, то F избыточно. F является неизбыточным покрытием G, если F есть покрытие G и F неизбыточно.
Для любого множества F-зависимостей G существует некоторое подмножество F, такое, что F является неизбыточным покрытием G. Если G неизбыточно, то F=G. Если G избыточно, то в G существует F-зависимость , которая является избыточной в G. Определение Множества называются эквивалентными относительно , если и (обозначение ).
Теорема Если -неизбыточные покрытия, то относительно . . Строим и для построения рассмотрим формулы . Если тогда . . Пусть . Рассмотрим вывод над . Существует формула :в её выводе используется . Действительно, если бы её не существовало, то каждую формулу из можно бы было получить из , т.к. , то , то есть - избыточно. Приходим к противоречию. Пусть в выводе используется . Тогда . Имеем , откуда по правилу проекции . Обратно - аксиома. , т.к. .
|