dm_tema_1

Свойства характеристических функций:

1)fU (x) = 1, f;(x) = 0

2)fA[B (x) = fA(x) + fB (x) fA(x)fB (x)

3)fA\B (x) = fA(x)fB (x)

4)fA(x) = 1 fA(x)

5)fAnB (x) = fA(x) fA(x)fB (x)

6)fA4B (x) = fA(x) + fB (x) 2fA(x)fB (x)

Докажем свойство 4

x 2 A ) x 2= A ) fA(x) = 0 ) 1 fA(x) = 1;

x 2= A ) x 2 A ) fA(x) = 1 ) 1 fA(x) = 0:

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

A fx1; : : : ; xng

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

hA = [fA(x1); : : : ; fA(xn)]:

Элементы характеристических векторов принимают только два значения: 0 и 1. Под суммой, произведением и отрицанием характеристических векторов будем понимать поэлементное выполнение этих операций в булевой алгебре с операциями дизъюнкции, конъюнкции и отрицания:

Операции над конечными множествами можно выразить через операции над характеристическими векторами этих множеств:

1)hA[B = hA + hB

2)hA\B = hAhB

3) hA = hA

4) hAnB = hAhB

5) hA4B = hAhB + hAhB

1. Теория множеств 1.2 Операции над множествами

Справедливы следующие теоретико-множественные тождества:

Доказать теоретико-множественные тождества можно методом диаграмм Эйлера-Венна, методом включения, методом характеристических функций.

Метод включения заключается в следующем. Множества A è B равны, если A B è B A. Следовательно, A = B, åñëè

8x : x 2 A ) x 2 B è x 2 B ) x 2 A;

или в виде одного утверждения

8x : x 2 A , x 2 B:

Докажем закон де Моргана

A [ B = A \ B

методом включения. В соответствии с определением операций над множествами

x 2 A [ B ) x 2= A [ B ) x 2= A è x 2= B )

x2 A è x 2 B ) x 2 A \ B ) A [ B A \ B:

Ñдругой стороны,

x 2 A \ B ) x 2 A è x 2 B ) x 2= A è x 2= B ) x 2= A [ B ) x 2 A [ B ) A \ B A [ B:

Объединим две эти записи в одну

x 2 A [ B , x 2= A [ B , x 2= A è x 2= B ,

x 2 A è x 2 B , x 2 A \ B ) A [ B = A \ B:

Докажем методом характеристических функций

fA[B (x) = 1 fA[B (x) = 1 fA(x) fB (x) + fA(x)fB (x); fA\B (x) = fA(x)fB (x) = (1 fA(x))(1 fB (x)) =

= 1 fA(x) fB (x) + fA(x)fB (x):

Следовательно,

fA[B (x) = fA\B (x)

è

A [ B = A \ B:

Законы де Моргана можно обобщить на несколько множеств

nn

[\

Ai = Ai ;

i=1 i=1

nn

\[

Определение

Прямым (декартовым) произведением множеств Ai , i = 1; : : : ; n,

B = A1 A2 An

называется множество всех упорядоченных наборов

(x1; x2; : : : ; xn);

ãäå xi 2 Ai , i = 1; : : : ; n.

Определение

Пусть все множества Ai , i = 1; : : : ; n равны между собой. Множество

An = A A

называется n-ой степенью множества A.

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

y

BC

A x

Здесь множества A è B отрезки числовой оси, C = A B.