3.4 Графики

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

Пример.

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

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

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

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

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

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

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

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

Пример. Р = {, }, Р-1 = {, }.

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

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

α-1Р → αР-1

αР → α-1Р-1

График Р называется симметричным, если он наряду с любой своей парой содержит ее инверсию.

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

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

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

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

Пример. Пусть Р = {, }, aQ = {, }, тогда P · Q = {}.

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

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

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

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

А · В (y(YW))(A&B).

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

А · В (y(YW))(A&B).

В операции композиции элемент у называется компонирующим элементом для пар А и В.

А · В = O пр2Апр1В = O А·O = O·А = O.

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

· 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. Необходимость: (P · Q) · R(P · Q) &RP&Q&RP&(Q· R) (P · (Q · R)) перваячастьдоказана

2.

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

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

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

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

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

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