11. Графики

График — это множество пар, т. е. множество, каждый элемент которого является парой или кортежем длины 2. Множество Р называется графиком, если каждый элемент его пара.

Пример. Множество Р = {<а, B>, <а, 1>, <с, D>}Является графиком.

Если М — произвольное множество, то М2, а также любое множество СМ2 является графиком. В частности графиком является множество D2 действительных чисел. Пусть заданы множества А и В, тогда А×В, СА×В являются графиками.

Понятие графика является обобщенным. В принципе оно происходит от понятия графика функции.

Областью определения графика Р называется множество Пр1P(проекция на первую ось (ось абсцисс) данного графика).

Областью значения графика называется множество проекций на вторую ось (ось ординат) (Пр2Р).

Легко видеть, что если Р — график, тогда если Р =Ø, то Пр1P = Ø & пр2P=Ø.

Рассмотрим основные операции над графиками:

1. Инверсия (определяется через инверсию кортежа)

Инверсией графика Р называют множество инверсий пар из Р.

Пример. Р = {<с, D>, <а, B>}, Р-1 = {<D, С>, <B, а>}.

График Q называется инверсией графика Р, если αQ тогда и только тогда, когда α-1Р,где α - Произвольный кортеж.

В теоретико-множественном виде запишем:

α-1Р → αР-1

αР → α-1Р-1

График Р называется Симметричным, если он наряду с любой своей парой содержит ее инверсию. Например, Р = {<а, B>, <B, а>}

Пусть М — произвольное множество. Тогда считают ΔM — множество всех пар вида <х, Х>, где Х присутствует во всем множестве М. Таким образом, если М = {а, B},то ΔM = {<а, а>, <B, B>}— является симметричным графиком и называется Диагональю.

2. Композиция

График R называется композицией двух графиков Р и Q, а также <X, Y>R, Тогда и только тогда, когда ZТакое, что <х, Z>Р &<Z, у>Q.

Переход от графиков Р и Q к их композиции (Р·Q) называется Компонированием графиков Р и Q.

Пример. Пусть Р = {<а, а>, <а, C>}, a Q = {<а, B>, <B, C>}, тогда P · Q = {<а,B>}.

Композиция графика Р и Ø равна Ø, то есть Р·Ø = Ø·Р = Ø.

Если М — произвольное множество и РМ2, тогдаP·ΔM= ΔM· P=P.

Если операцию композиции графиков сопоставить с умножением чисел, то роль нуля будет играть пустое множество, а роль единицы диагональ (Δ).

Пусть <х, z>- произвольная пара из А·В. Тогда для нее справедливо высказывание:

<х, Z>А · В (Y(YW))(<X, Y>A&<Y, Z>B).

Если некоторая пара <х, z>не принадлежит А· B, то истинно высказывание:

<х, Z>А · В (Y(YW))(<X, Y>A&<Y, Z>B).

В операции композиции элемент у называется Компонирующим элементом для пар <х, у>А и <y, z>В. Если множество компонирующих элементов пусто, то и результат композиции является пустым множеством:

А · В = Ø Пр2АПр1В = Ø А·Ø = Ø·А = Ø.

Свойства операции композиции:

· A · B ≠ B · A – некоммутативность

· A · (B · С) = (A · B) ·C – ассоциативность

· A · (BC) = (A · B) (A · C) – дистрибутивность по объединению

· A · (BC) = (A · B) (A · C) – дистрибутивность по пересечению

· (A · B)-1 = В-1 · А-1

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

Пример. Пусть P, Q, R – графики. Необходимо доказать следующее тождество: (P · Q) · R = P · (Q· R)

Доказательство.

1. Необходимость: <A, B>(P · Q) · R<A, Z>(P · Q) &<Z, B>R<A, X>P&<X, Z>Q&<Z, B>R<A, X>P&<X, B>(Q· R) <A, B>(P · (Q · R)) Перваячастьдоказана

2. Достаточность:<A, B>(P · (Q · R)) <A, X>P&<X, B>(Q· R) <A, X>P& (<X, D>Q&<D, B>R) <A, X>P&<X, D>Q&<D, B>R<A, D>(P · Q) &<D, B>R<A, B>((P · Q) · R) Втораячастьдоказана.

3. Значит, исходное тождество справедливо.

Основные свойства графиков:

· График Р называется Функциональным, если в нем нет пар с одинаковыми первыми и разными вторыми компонентами. Например, Р ={<b, а>, <с, а>, <d, a>}.

· График Р называется Инъективным, если в нем нет пар с различными первыми и одинаковыми вторыми компонентами. Например, Р ={<а, b>, < а, c>, <a, d>}.

Композиция функциональных графиков есть функциональный график, т. е. композиция сохраняет функциональность. Композиция инъективных графиков инъективна.

Итак, говорят, что график Р функционален тогда и только тогда, когда Р-1 инъективен. График Р инъективен тогда и только тогда, когда Р-1 функционален.

< Предыдущая		Следующая >