Непейвода Н.Н. Прикладная логика

Подождите немного. Документ загружается.

5.3. ОТНОШЕНИЯ

Рис. 5.5: x − y — целое число

Третий взгляд на множество пар полезен при построении диаграмм,

подобных диаграммам Эйлера и Венна. Здесь каждый из сомножителей

изображается отрезком, их прямое произведение — прямоугольником,

а отношение — подмножеством квадрата. Такое изображение часто на-

зывают графиком отношения.

Пример 5.3.1.

Картинка на рис. 5.5 показывает график отношения ‘

x −

— целое число’ на множестве

[0, 5]

Определение 5.3.2. Образ

элемента

при соответствии

—множество

всех таких

, что

(x, y) ∈ R

Прообраз

элемента

при соответствии

— множество всех таких

, что

(x, y) ∈ R

. Образ

при соответствии

обычно обозначается

через

R hxi

Образ (прообраз) множества

⊂ X (Y

⊂ Y )

— объединение

образов (прообразов) его элементов. Образ

при соответствии

так-

же обычно обозначается через

R hXi

. Как говорят, конкретный смысл

операции здесь устанавливается по контексту

Ситуация, когда один и тот же знак операции применяется к выражениям разных ти-

пов и по существу означает разные вещи, на самом деле обычна в математике. Напри-

мер, знак

+ применяется для сложения и натуральных, и целых, и рациональных чисел,

и действительных, и комплексных, и матриц, и еще математик знает чего. В програм-

мировании дела обстоят точно так же.Такое “сверхиспользование” символа называется

перегрузкой. С примером, как корректно решать проблемы перегрузки, мы познакомим-

ся далее. Но не надейтесь, что все, использующие перегрузку, заботятся о ее корректно-

сти. Чаще всего дело ограничивается благими пожеланиями, даже если об этой пробле-

ме задумываются (например, в языке Ada, созданном по заказу Министерства обороны

США, по поводу перегрузки было высказано требование, чтобы алгебраические свой-

ства операций, обозначающихся одним и тем же значком, совпадали и на одинаковых

аргументах эти операции давали одинаковые результаты, но никаких средств проверки

этого условия дано не было).

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

определено на

, если образ

непуст.

не определено на

, если образ

пуст.

Рассмотрим операции над отношениями. Конечно же, поскольку от-

ношения являются множествами, над ними можно производить обыч-

ные булевы операции, поскольку они — подмножества прямого произ-

ведения, можно находить их проекции. Но есть и специфические для

бинарных отношений операции.

Первая из них — нахождение обратного отношения. Она сопоста-

вляет отношению

R между A и B отношение R

−1

(часто обозначаемое

также

) между B и A, определяемое следующим образом:

−1

= {(y, x)|x ∈ A & y ∈ B & (x, y) ∈ R}. (5.7)

Например,для изображенного на рис. 5.5отношения обратным является

оно само, для отношения

< — отношение > и т. п.

Интересны два подкласса отношений между

X и X (обычно назы-

ваемых отношениями на X).

Определение 5.3.3. Симметричным

называется такое

, что

−1

= R

Антисимметричным

— такое

, что

−1

∩ R = ∅

Понятия симметричности и антисимметричности выражаются на язы-

ке логики:

∀x ∀y((x, y) ∈ R ⇒ (y, x) ∈ R),

∀x ∀y((x, y) ∈ R ⇒ (y, x) /∈ R).

Важным частными отношением на X является диагональ, или единич-

ное соответствие, или тождественное отображение

= {(x, x)|x ∈ X} = {(x, y)|x = y}.

Эта диагональ является графиком функции λx.x,перерабатывающей ка-

ждое x само в себя.

Определение 5.3.4. Рефлексивным

называется отношение, содержащее

диагональ.

Антирефлексивным

называется отношение, не пересекаю-

щееся с диагональю.

Обилие имен у математического объекта, как правило, означает, что он полезен для

самых разных целей.

5.3. ОТНОШЕНИЯ

Понятия рефлексивности и антирефлексивности также выразимы на

логическом языке:

∀x(x, x) ∈ R,

∀x(x, x) /∈ R.

Определение 5.3.5. Композиция

отношений

R ⊂ X ×Y

S ⊂ Y ×Z

—

отношение

R ◦ S ⊂ X × Z

, такое, что

R◦S = {(x, z)|x ∈ X & z ∈ Z & ∃y(y ∈ Y & (x, y) ∈ R & (y, z) ∈ S)}.

Итак, при композиции мы связываем x и z посредством такого y, что

y соответствует x согласно R и z соответствует y согласно S. Очевидно,

что если отношения имеют вид

R = {(x, y)|x ∈ X & y ∈ Y & y = f (x)},

S = {(x, y)|x ∈ Y & y ∈ Z & y = g(x)},

(5.8)

то их композиция представляется как

R ◦ S = {(x, y) | x ∈ X & y ∈ Z & y = g(f(x))}. (5.9)

Приведем некоторые важные алгебраические свойства композиции

отношений.

R ◦ (S ◦ T ) = (R ◦ S) ◦ T (ассоциативность) (5.10)

R ◦ id

= R id

◦ R = R id — единица (5.11)

(R ◦ S)

−1

= (S

−1

◦ R

−1

) обратный к композиции (5.12)

Но вот

R ◦ R

−1

= id

выполнено отнюдь не всегда.

И последние из “джентльменского набора” классов отношений —

транзитивные и антитранзитивные отношения. Чисто формально легко

написать определяющие их логические условия, но и в данном случае

лучше связать эти понятия с операцией композиции над отношениями

на

Определение 5.3.6.

Квадрат отношения

R ⊂ X ×X

— отношение

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

R ◦ R

. Соответственно определяется

= R ◦ ∙∙∙ ◦ R

| {z }

раз

Отношение называется транзитивным, если R

⊂ R. Отношение

антитранзитивно, если R

∩ R = ∅. Понятия транзитивности и анти-

транзитивности имеют выражение на логическом языке. Мы приведем

его для транзитивности, а для антитранзитивности выразите сами.

∀x ∀y ∀z((x, y) ∈ R & (y, z) ∈ R ⇒ (x, z) ∈ R). (5.13)

С транзитивностью связано важное понятие — транзитивное замыка-

ние отношения

. Дадим два определения транзитивного замыкания и

докажем их эквивалентность.

Определение 5.3.7.

— наименьшее множество, обладающее свойством

, если вы-

полнено

A(X)

∀Y (A(Y ) ⇒ Y ⊂ X).

2. Транзитивное замыкание отношения

R ⊂ X × X

— наименьшее

отношение

∞

⊂ X × X

, такое, что

∞

содержит все элементы

из

∞

транзитивно.

Не путайте данную степень с декартовой! Забавнее всего, что поскольку отноше-

ния также множества, можно рассматривать и декартову степень

R, но в связи с тем,

что в чистой математике она практически никогда не нужна, математики допускают

т. н. “вольность речи,” а вот безумные программисты иногда вынуждены использовать

структуры данных, соответствующие декартову произведению отношений.

Схема, примененная при определении транзитивного замыкания, — на самом деле

общая схема, используемая при превращении структур, не обладающих замкнутостью

относительно некоторой операции, в структуры, замкнутые относительно нее. Так, на-

пример, двоично-рациональные числа (числа вида

) получаются замыканием целых

чисел относительно операции деления на 2; комплексные числа — замыканием дей-

ствительных чисел относительно операции нахождения корней любого алгебраическо-

го уравнения вида

+ a

n−1

∙ ∙ ∙ + a

= 0.

5.3. ОТНОШЕНИЯ

3. Транзитивное замыкание отношения

R ⊂ X × X

—

∞

[

n=1

4. Транзитивное замыкание отношения

R ⊂ X × X

— пересечение

всех транзитивных отношений, включающих

R ⊆ X,

транзитивно

X (5.14)

Докажем, что три определения

∞

эквивалентны. В самом деле,

∞

n=1

содержит R и транзитивно,поскольку если (x, y) ∈ R

,(y, z) ∈

, то (x, z) ∈ R

n+m

. Любое транзитивное отношение, содержащее R,

должно содержать и все R

(это легко доказывается по индукции). Зна-

чит,

∞

n=1

— наименьшее транзитивное отношение, содержащее R,

что и требовалось доказать. И, наконец, пересечение семейства транзи-

тивных отношений само транзитивно, а семейство из (5.14) включает, в

частности, и минимальное из транзитивных расширений R

Если отношение транзитивно и антирефлексивно, оно называется

отношением (частичного) порядка и обозначается символом < либо

похожими на него (например, ). Если отношение транзитивно и ре-

флексивно, то оно называется отношением предпорядка и обозначается

символом, похожим на 6 (например, <). Частичный порядок называет-

ся линейным, если выполнено условие

∀x ∀y(x  y ∨ x = y ∨ y  x).

Обратите внимание!! В третьем пункте мы определили транзитивное замыкание R

через класс, содержащий само это транзитивное замыкание. Более того, если из этого

класса транзитивное замыкание выбросить, порою пересечение оставшихся множеств

уже будет побольше. Так что в последнем случае

∞

определялось само через себя!

Такая ситуация издревле рассматривалась как логическая ошибка “Порочный круг в

определении”. Тем не менее в математике подобные определения широко используют-

ся; мы, правда, их стараемся избегать. Практически всегда их можно заменить более

конструктивными определениями типа использованных во втором пункте, но здесь по-

рою натуральных чисел не хватает для нумерации шагов построения.

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

Множество с заданным на нем отношением частичного порядка на-

зывается частично упорядоченным множеством (чум)

. Множество с

отношением предпорядка — пум. Множество с отношением линейного

порядка — линейно упорядоченное множество (лум).

Предпорядок называется строгим предпорядком (или нестрогим по-

рядком), если выполнено

∀x ∀y(x < y & y < x ⇒ x = y).

Пример 5.3.2.

Отношение «Быть начальником» является отношением

частичного порядка на множестве чиновников

.Отношение «Быть стар-

ше по званию» — отношение частичного порядка на множестве воен-

ных. Отношение «Не быть старше по званию» — отношение предпо-

рядка на этом же множестве

Для изображения частично-упорядоченных множеств имеется гра-

фический аппарат, известный под названием диаграммы Гессе. Пример

диаграммы Гессе см. на рис. 5.6. На этой диаграмме, как видите, изо-

бражаются не все пары из отношения порядка. Элемент y больше эле-

мента x, если есть путь, составленный из идущих вверх дуг диаграммы,

ведущий из x в y. Поэтому, в частности, нет нужды проводить дугу, на-

пример, от 0 к 1.

Введем несколько важных понятий,касающихся упорядоченных мно-

жеств.

Определение 5.3.8.

Элемент

чума

называется

наибольшим

, если

∀y(y ∈ X & y 6= x

⇒ x

 y).

Таким образом, он больше всех остальных.

Максимальный

элемент не

меньше никакого другого.

∀y(y ∈ X ⇒ ¬y  x

Симпатичное русское сокращение чум введено новосибирской школой. Московская

математическая школа его не признает, видимо, потому, что в Европе ни чумов,ни чумы

нет.

Хотя фактически частенько чиновники занимают позицию “Начальник моего началь-

ника — не мой начальник” и, соответственно, приказания Президента не исполняются

чаще, чем повеления непосредственного шефа, но формально такое поведение проти-

воречит законам и инструкциям.

То, что здесь старшинство “перепутано” — младшие по званию считаются больше

старших, — частный случай того математического факта, что

R — отношение порядка

ттт R

−1

— отношение порядка. Этот порядок называется обратным к R.

5.3. ОТНОШЕНИЯ

∙

∙ ∙ ∙

∙

Рис. 5.6: Диаграммы Гессе двух важных пятиэлементных множеств

Соответственно определяются

минимальный

наименьший

элементы.

Элемент

называется

верхней гранью

множества

Y ⊆ X

(обозначается

sup Y

либо

), если

∀x(x ∈ Y ⇒ x ≺ a ∨ x = a) &

∀x(x ∈ X & x ≺ a ⇒ ∃y(y ∈ Y & x ≺ y & (y ≺ a ∨ y = a))).

Соответственно определяется нижняя грань

(inf Y

Y )

.Верхняя (ниж-

няя) грань двух элементов обозначается

a ∪ b

(

a ∩ b

). Чум, в котором у

каждых двух элементов имеется верхняя и нижняя грань, существуют

наибольший и наименьший элементы, называется

структура

. Структу-

ра называется

полной

, если верхние и нижние грани существуют у лю-

бого подмножества элементов.

Определение 5.3.9.

Пусть

— чум. Тогда на множестве

∞

кортежей

элементов из

можно ввести отношение частичного порядка, называ-

емое

лексикографическим упорядочением

, . . . , x

]  [y

, . . . , y

]

= ∃i(∀j(j < i ⇒ x

= y

) & x

 y

Например,лексикографическое упорядочение кортежей букв исполь-

зуется при построении словарей.

Упражнения к § 5.3

5.3.1. В книге Н. Бурбаки “Теория множеств”, в которой понятие пары

наряду с понятием множества и принадлежности рассматривается

как исходное, для пар задана следующая аксиома (переписанная в

наших обозначениях):

∀x ∀y ∀u ∀v((x, y) = (u, v) ⇒ x = u & y = v).

Почему не задана как аксиома и обратная импликация?

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

Покажите, что для выполнения аксиомы Н. Бурбаки достаточно

определить пару (x, y) как двухэлементное множество {x, {x, y}}.

Объясните, можно ли определять пару, скажем, так:

(x, y)

= {{x, 0}, {y, 1}}.

5.3.2. Почему в формулах (5.8), (5.9) повсюду используются одни и те

же переменные x, y, хотя множеств целых три: X, Y , Z?

5.3.3. Проверьте следующие тождества:

(A ∪ B) × C = (A × C) ∪ (B × C)

2. (A ∩ B) × C = (A × C) ∩ (B × C)

Если некоторые из них не всегда выполнены, в какую из сторон

имеет место вложение?

5.3.4. Верно ли, что

∪ R

) ◦ S = (R

◦ S) ∪ (R

◦ S)

2. (R

∩ R

) ◦ S = (R

◦ S) ∩ (R

◦ S)

5.3.5. Когда (x, x) ∈ R◦R

−1

?Выведите из Вашего условия,когда id

⊆

R ◦ R

−1

5.3.6. Каковы обратные отношения к следующим отношениям:

1. Быть отцом.

2. Быть мужем.

3. Быть начальником.

4. y = a ∙ x.

5. Быть братом.

6. Быть братом или сестрой.

7. Любить.

8. Ненавидеть.

9. Воевать.

5.3. ОТНОШЕНИЯ

5.3.7. Построить композиции следующих отношений (‘Быть

’ означа-

ет ‘x является

для y’. Математические формулы рассматрива-

ются на множестве действительных чисел):

a) Быть родителем Быть отцом

б) Быть родителем Быть сестрой

в) Быть соседом Быть другом

г) Быть другом Быть соседом

д) Быть мужем Быть отцом

е)

x > y y > x

ж) x

= y y

= x

з) x = e

x = sin y

5.3.8. Имеются ли отношения, которые одновременно и симметричны,

и антисимметричны?

5.3.9. На каком множестве любое отношение симметрично?

5.3.10. А есть ли множество, на котором любое отношение рефлексив-

но?

5.3.11. Отношение порядка,для которого выполнено

R◦R = R,называ-

ют плотным. Почему? Переведите данное условие на логический

язык.

5.3.12. Докажите, что для любого отношения предпорядка

R ◦ R = R.

5.3.13. Студентка Примерная нарисовала две красивых диаграммы

Гессе:

∙

∙ ∙

∙

∙ ∙

Какую ошибку содержат эти диаграммы и какую из них можно

упростить после исправления ошибки любым способом?

5.3.14. Студент Лыцаренко защитил студентку Примерную, заявив, что

это — диаграммы для предупорядоченных множеств. Насколько

обоснована его защита?

5.3.15. Определение 5.3.9 содержит неточность. Найдите и исправьте.

100

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

5.3.16. Не ошибся ли автор в определении максимального элемента, опу-

стив условие y 6= x

? А как для предупорядоченных множеств?

5.3.17. Переведите на формальный язык следующее определение:

Отношение называется согласованным, если два объекта, отно-

сящиеся к одному и тому же третьему объекту, относятся между

собой.

Не могли бы Вы переформулировать данное предложение на со-

держательном языке так, чтобы оно, не изменив математического

смысла, стало бы легче понимаемым?

§ 5.4. ФУНКЦИИ

Уже на картинке 5.5 хорошо видно, почему отношения называют соот-

ветствиями. Порою так и напрашивается интерпретация их как частич-

ных многозначных отображений

. Зато когда говорят о функциях, то

используют содержательное уточнение, которое всегда работает в мате-

матике.

Функция — правило, позволяющее по каждому элементу

области определения однозначно получить элемент области

значений.

Итак, каждая функция имеет область определения Dom f , над кото-

рой она работает, и область значений Val f, в которой должны содер-

жаться полученные результаты. Надо заметить, что отнюдь не всегда

функция может выдавать в качестве результата все элементы области

значений. Ниже мы разберем это подробнее.

Соответствие представляет график полноправной функции только в

том случае, если каждому

x из X соответствует единственное y из Y .

Например, таково соответствие

{(x, y) | x ∈ R & y ∈ R & x = y + 1}.

Не обольщайтесь этим. Неопределенность и многозначность — глубокие и ковар-

ные вещи. Отнюдь не всегда простейшее математическое уточнение понятия частичной

многозначной функции как отношения работает. Так что если кто-то говорит о частич-

ных многозначных функциях, уточняйте, что он имеет в виду.