Графики

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

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

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

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

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

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

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

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

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> }.

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

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

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

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

< х, z> А · В ( y (Y W))(< x, y> A& < y, z> B).

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

< х, z> А · В ( y (Y W))(< x, y> A& < y, z> B).

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

А · В = Ø пр₂А пр₁В = Ø А·Ø = Ø ·А = Ø.

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

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

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

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

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

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

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

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