4. Свойства операций над множествами (с доказательством).

   коммутативность	А В=В А	А В=В А
   ассоциативность	А (В С)= (А В) С	А (В С)= (А В) С
   дистрибутивность	А (В С)= (А В) (А С)	А (В С)= (А В) (А С)
   идемпотентность	А А=А	А А=А
   закон поглощения	А (А В)=А	А (А В)=А
   закон Де-Моргана	А В=А В	А В=А В
   свойства 0	А =А	А =
   свойства 1	А U=U	А U=A
   свойство дополнения	А А=U	A A=

5. Прямое произведение множеств. Бинарные отношения. Способы задания бинарных отношений.

Прямым (декартовым) произведением множеств А и В называется множество всех пар (а, в) таких, что а А и в В. Обозначение: А В.

Если А = В, то А В =А² и называется декартовым квадратом.

Прямое произведение множеств А₁ , А₂ , …, А_n есть множество всех векторов (а₁ , а₂ , а₃ ,…, а_n) длины n таких , что а₁ А₁ , а₂ А₂ , …, а_n А_n .

Если А₁ = А₂ = … = А_n , то А₁ А₂ … А_n = А_n и называется декартовой степенью.

N-местным отношением или n-местным предикатом Р на множествах А₁ , А₂ , …, А_n называется

любое подмножество прямого произведения А₁ А₂ … А_n. Другими словами, элементы

х₁,х₂,…,х_n (где х₁ А_1,…, х_n А_n) связаны соотношением Р(обозначается Р(х₁,х₂,…,х_n)) тогда и только

тогда, когда (х₁,х₂,…,х_n) Р.

Наиболее часто встречаются двухместные отношения (n=2). В этом случае они называются

бинарными отношениями или соответствиями.

Отношения на конечных множествах обычно задаются:

1. Перечислением пар, для которых выполняется это отношение.

2. Матрицей бинарного отношения.

3. Словесным описанием (больше, меньше и т.д.)

4. Графически (на плоскости)

6. Операции над бинарными отношениями: композиция отношений, степень отношения, обратное отношение, дополнение отношения, объединение, пересечение, разность отношений.

Пусть задано бинарное отношение Р. Областью определения бинарного отношения Р называется множество D_p={x: существует такое у, что (х, у) }. Областью значений бинарного отношения Р называется множество Е_p={у: существует такое х, что (х, у) }.

Тождественным называется отношение I={(x,x):x }. Универсальным отношением U={(x,y):x }.

Обратным отношением для р называется отношением р^-1={(х,у):(у,х) р}.

Композицией отношений р₁ и р₂ называется отношение р₁ р₂={(x,y):существует такое z, что (x,z) p₁ и (z,y) p₂}.

Степенью отношения р называется его композиция с самим собой. pⁿ=p … p (n раз).

Дополнение отношения р между элементами A и B есть множество -R = (AxB)\R .

Объединение отношений p₁ и р₂ называется отношение p₁ р₂={(x,y): (x,y) p₁ или (х,у) p₂}.

Пересечение отношений p₁ и р₂ называется отношение p₁ р₂={(x,y): (x,y) p₁ и (х,у) p₂}.

Разность отношений p₁ и р₂ называется отношение p₁ р₂={(x,y): (x,y) p₁ и (х,у) p₂}.