Cтраница 4
Первая же рассматриваемая ветвь относится к дереву и представляет двухэлементный класс, объединяющий пару вершин, инцидентных этой дуге. В дальнейшем каждое включение ветви в дерево сопровождается объединением двух классов эквивалентности, так что при наличии в дереве q ветвей разбиение состоит из v - q классов. Процесс формирования дерева заканчивают после того, как совокупность ветвей графа образует дерево - связный подграф, не содержащий контуров. Ему соответствует полное отношение эквивалентности, при котором множество всех вершин графа образует единственный класс. [46]
Объединение порядков в общем случае не является порядком. Это хорошо видно на таком примере. Пусть А - совершенный нестрогий порядок, тогда А-1 - есть отношение того же типа. Однако объединение A U А-1 есть полное отношение, и, следовательно, не является порядком. [47]
Хотя отношение в предыдущем примере может быть заполнено двумя способами для данного множества F-зависимостей, оба этих способа приводят к сильному нарушению. Достаточно ясно, что любое отношение с сильным нарушением не имеет допустимых пополнений. Чтобы результат применения правила заполнения был всегда определен, будем предполагать, что в случае отношения с сильным нарушением это правило заменяет его на некоторое специальное значение, которое обозначается HV. Через nchaseF ( г) обозначим результат применения правила заполнения с F-зависи-мостями из F к отношению г до тех пор, пока будут возможны какие-либо изменения. Полученное значение nchasef ( r) есть либо отношение, либо специальное значение HV. I Мы хотим показать, что г допустимо относительно F в тех и только в тех случаях, когда nchaseF ( r) не равно HV. Отношение nchaseF ( r) может иметь несколько вхождений некоторого помеченного неопределенного значения. Следует расширить определения терминов являться частичным пополнением и пополнять для случая нескольких вхождений. По-прежнему отношение с помеченными неопределенными значениями рассматривается как множество аксиом ( или как одна аксиома) относительно полного отношения, которое представлено с помощью этого частичного отношения. Однако теперь аксиомы, порожденные разными строками, могут содержать общие кванторы по одинаковым переменным. [48]
Хотя отношение в предыдущем примере может быть заполнено двумя способами для данного множества F-зависимостей, оба этих способа приводят к сильному нарушению. Достаточно ясно, что любое отношение с сильным нарушением не имеет допустимых пополнений. Чтобы результат применения правила заполнения был всегда определен, будем предполагать, что в случае отношения с сильным нарушением это правило заменяет его на некоторое специальное значение, которое обозначается HV. Через nchaseF ( r) обозначим результат применения правила заполнения с F-зависи-мостями из F к отношению г до тех пор, пока будут возможны какие-либо изменения. Полученное значение nchaseF ( r) есть либо отношение, либо специальное значение HV. Мы хотим показать, что г допустимо относительно F в тех и только в тех случаях, когда nchaseF ( r) не равно HV. Отношение nchaseF ( r) может иметь несколько вхождений некоторого помеченного неопределенного значения. Следует расширить определения терминов являться частичным пополнением и пополнять для случая нескольких вхождений. По-прежнему отношение с помеченными неопределенными значениями рассматривается как множество аксиом ( или как одна аксиома) относительно полного отношения, которое представлено с помощью этого частичного отношения. Однако теперь аксиомы, порожденные разными строками, могут содержать общие кванторы по одинаковым переменным. [49]