Неизбыточные покрытия. Теорема о структуре неизбыточного покрытия

Определение. Множество F-зависимостей F неизбыточно, если у него нет такого собственного подмножества F’, что F’ F. Если такое множество F’ существует, то F избыточно. F является неизбыточным покрытием G, если F есть покрытие G и F неизбыточно.

Для любого множества F-зависимостей G существует некоторое подмножество F, такое, что F является неизбыточным покрытием G. Если G неизбыточно, то F=G. Если G избыточно, то в G существует F-зависимость , которая является избыточной в G.

Определение Множества называются эквивалентными относительно , если и (обозначение ).

Теорема Если -неизбыточные покрытия, то относительно .

. Строим и для построения рассмотрим формулы . Если тогда . .

Пусть . Рассмотрим вывод над . Существует формула :в её выводе используется . Действительно, если бы её не существовало, то каждую формулу из можно бы было получить из , т.к. , то , то есть - избыточно. Приходим к противоречию.

Пусть в выводе используется . Тогда . Имеем , откуда по правилу проекции .

Обратно - аксиома.

, т.к. .