Глава 2. Отношения

§ 7. Составные отношения

Подобно тому как мы устанавливали внутренние связи в файлах, для выделения некоторых данных из информации (например, ПОСТАВЩИК и МЕСТО РАСПОЛОЖЕНИЯ 3 посредством файлов DEL и SUP4 в примере 6.3) часто приходится связывать бинарные от-"^ношения друг с другом. Руководствуясь предыдущими рассуждениями, можно определить это понятие следующим образом.

Определение. Пусть заданы множества А, В и С и отношения а между А и В и р между В а С. Определим отношение между А и С следующим образом: оно действует из А в В посредством о, а затем из В в Ссоставным и обозначают р ° о, т. е. посредством р. Такое отношение называют

(роо)(д)=р(о(а)). /

Следовательно, (х, y)e(p^•a), если существует zeB такое, что (х, z)ea и (г, у)<=р. Отсюда следует, что Q^ffla °= о"'^. Чтобы проиллюстрировать ситуацию, рассмотрим рис. 2.11.

Глава 2. Отношения

6.Отношения на базах данных и структурах данных

Определение. При обработке данных наборы, из п элементов называют записями; элементы этих наборов называют полями. Записи, определяющие отношение, обычно содержатся в файле. Если потребовать, чтобы несколько файлов содержали совокупность записей, удовлетворяющих некоторым отношениям, то мы получим (относительную) базу данных.

Замечание. Для случая обработки данных мы сейчас употребили термин “поле”. В гл. 5 мы будем употреблять этот термин в математическом смысле, однако в данном случае это не приводит к недоразумению.

Глава 2. Отношения

§ 5. Отношения порядка

Поскольку из понятия равенства (скажем, между числами) возникает математическое понятие эквивалентности, некоторые неравенства могут также использоваться как модели для более широкого класса отношений.

Частичным порядком на множестве А назовем отношение, которое рефлексивно, антисимметрично и транзи-тивно. Порядок (называемый также отношением порядка) — это обобщение отношения ^ на N. Поэтому можно легко проверить требуемые три свойства. Заметим, что мы могли бы в качестве определения взять отношение <. Тогда отношение порядка было бы только тран-зитивно. Поэтому свойство транзитивности является наиболее важным для отношения порядка.

Определив отношение =S, можно определить отношение < следующим образом:

a<b^>a<b и aҐ-b. Аналогично, если задано <, то

а ^ Ь -“=*- о=Ь или о < Ь.

Глава 2. Отношения

§ 4. Разбиения и отношения эквивалентности

Во многих вычислительных задачах берутся большие множества и разбиваются таким образом, чтобы все интересующие нас ситуации можио было исследовать на нескольких правильно выбранных примерах. Например, один из путей получения качественной оценки характеристик языка программирования—это посмотреть конкретные программы, написанные на этом языке. Однако каждый интересный язык, включая такие языки высокого уровня, как Паскаль и Фортран, порождает бесконечно много программ, и, следовательно, мы должны выбирать программы так, чтобы они правильно отражали достоинства и недостатки языка. Чтобы быть более конкретными, давайте в дальнейшем предполагать, что язык имеет три основные управляющие структуры и четыре метода доступа и более у него нет никаких особых свойств. Мы могли бы в качестве примера взять семь программ, каждая из которых включает только одпу характеристику языка (хотя, вообще говоря, каждая программа может использовать более чем одну характеристику языка). Исследование этих программ тогда могло бы покрыть большую часть свинств языка

Глава 2. Отношения

§ 3. Свойства отношений

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

Определение. Пусть р — отношение на множестве А- Тогда:

а) р рефлексивно, если хрх для любого х е А;

б) р симметрично, если -тру влечет урх;

в) р транзитивно, если хру и ypz влечет хрг;

г) р антисимметрично, если хру и урх влекут х =y.

Терминология, вподоппая здесь, вероятно, является повой для читателя, однако он, по-видимому, знаком с этими понятиями. Иоясшш их на следующих примерах.

Глава 2. Отношения

§ 2. Графические представления

При решении задачи па первом этапе часто полезно начертить “рисунок” для того, чтобы более ясно увидеть компоненты задачи. Особенно это полезно для описания отношений, так как записанные в виде множества упорядоченных пар отношения нелегко расшифровываются.

Отношения — это множества, обладающие определенной структурой; их элементы имеют несколько компонент, и поэтому, в принципе; мы можем использовать диаграммы Венна для их изображения. Хотя этим методом и можно воспользоваться, особенно при описании некоторых больших множеств чисел, существуют методы, которые более эффективны в общих ситуациях (включающих, в частности, бинарные отношения на небольших множествах). В этом параграфе мы кратко рассмотрим некоторые из них. Для описания этих методов используем множество

 Х = {о, Ь, с, Л

и отношения Ix, Us и Д, где

Л-{(д,Ь), (а, с), (b,d), (с,е), (е,Ъ)).

Глава 1. Множества

§ 4. Подмножества и доказательства

Операции пересечения, объединения, разности и дополнения позволяют нам формировать новые множества. Однако, как правило, мы не можем сказать, как одно множество соотносится с другими. Например, пусть даны два множества Х и Y; пересечение Х П Y в некотором смысле “меньше” (или по крайней мере не больше), чем X. Действительно, все элементы множества Х Л Y принадлежат также множеству X, Из этого наблюдения можно формально определить равенство множеств п различных выражений для того же самого множества, С по

мощью этих определений мы также в состоянии написать подходящие логические доказательства важных фактов, относящихся к множествам. Эти результаты, хотя и очевидны, обеспечивают подходящие ситуации, в которых можно ввести некоторые из основных способов доказательств, используемых в дальнейшем.