При доказательстве тождеств в теории множеств могут быть использованы не
сами множества, а их так называемые характеристические функции.
Характеристическая функция множества А представляет собой п-мерный вектор, если множество конечно
A [ A (x1),..., A (xn )], |
n |U |, |
||
1, x A, |
x U. |
|
|
A (x) |
x A, |
|
|
0, |
|
|
|
Характеристическая функция пустого множества состоит из нулей характеристическая функция универсального множества состоит из единиц:
[0 0 ... 0], |
U [1 1 ... 1]. |
1.1.2. Операции над множествами
1. Объединением множеств А и В называется множество А В, все элементы которого являются элементами множества А или В:
A B {x | x A или |
x B}. |
В терминах характеристических функций эта операция описывается следующим образом:
A B (x) max( A (x), B (x)).
2.Пересечением множеств А и В называется множество А В, элементы которого являются элементами обоих множеств А и В:
A B {x | x A и |
x B}. |
В терминах характеристических функций эта операция описывается следующим образом:
A B (x) min( A (x), B (x)).
3. Дополнением множества А называется множество A, состоящее из всех
элементов универсального множества U, которые не принадлежат множеству A:
|
{x | x U |
и x A}. |
A |
В терминах характеристических функций эта операция описывается следующим образом:
A (x) U (x) A (x) 1 A (x).
4.Разностью множеств А и В называется множество А\В, которое состоит из тех элементов множества А, которые не принадлежат множеству В:
А \ В {x | x А и x В}. Относительное дополнение выражается через другие операции:
А \ В А В .
В терминах характеристических функций эта операция описывается следующим
образом:
А\ В (x) max( А (x) В (x), 0),
А\ В (x) A B (х) min A (х),1 B (х) .
5.Симметрической разностью множеств А и В называется множество А+В:
A B (A \ B) (B \ A).
В терминах характеристических функций эта операция описывается следующим образом:
A B (x) max A (x) B (x), B (x) A (x) .
Приоритет выполнения операций: сначала выполняется операция дополнения, затем пересечения и только потом объединения и разности. Последовательность выполнения операций может быть изменена скобками.
Пример. Сравнить:
2 |
3 |
1 |
4 |
4 |
2 |
1 |
3 |
A B |
C |
\ |
D и A ((B |
C |
) \ D) |
||
B
A\B
Рис. 1.1. Диаграммы Эйлера-Венна
Пример. |
|
|
Даны множества: A {b, d, k,l, s}, |
B {a,b, k, o, v}, |
C {a, m, s,t, v}. Составить |
универсальное множество, характеристические функции. Выполнить следующие действия: A B, C B, C , B \ A, A C.
Решение.
Универсальное множество
U {a,b, d, k,l, m,o, s,t, v}.
Характеристические функции |
|
|
|
|
|
|
|
|
|
U [1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 1 |
1], |
|
A [0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0], |
B [1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1], |
C [1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1]. |
Операции: |
|
|
|
|
|
|
|
|
|
|||||
1. |
Объединение |
|
|
|
|
|
|
|
|
|
||||
|
A B {a,b,d,k,l,o,s,v}, |
|
|
|
|
|||||||||
|
A B [1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1]. |
||||
2. |
Пересечение |
|
|
|
|
|
|
|
|
|
||||
|
C B {a,v}, |
|
|
|
|
|
|
|
|
|||||
3. |
C B [1 0 0 0 0 0 0 0 0 1]. |
|||||||||||||
Дополнение |
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
{b,d,k,l,o}, |
|
|
|
|
|
|
|
|||
|
C |
|
|
|
|
|
|
|
||||||
|
|
|
[0 1 1 1 1 0 1 0 |
|
0 |
0]. |
||||||||
|
C |
|
||||||||||||
4. |
Разность |
|
|
|
|
|
|
|
|
|
||||
|
B \ A {a,o,v}, |
|
|
|
|
|
|
|
||||||
5. |
B\ A [1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1]. |
||||
Симметрическая разность |
|
|
|
|
|
|
|
|
|
|||||
AC (A \ C) (C \ A) {b,d,k,l} {a,m,t,v} {a,b,d,k,l,m,t,v},
A C [1 1 1 1 1 1 0 0 1 1].
1. Законы коммутативности
а) A B B A,
б) A B B A.
2. Законы ассоциативности
а) A (B C) (A B) C, б) A (B C) (A B) C.
3. Законы дистрибутивности
а) A (B C) (A B) (A C), б) A (B C) (A B) (A C).
4. Законы де Моргана
а) (A B) A B,
б) (A B) A B.
5. Законы идемпотентности
а) A A A, б) A A A.
6.Законы поглощения
а) A (A B) A, б) A (A B) A.
7.Законы тождества
а) A A,б) A U A.
8.Законы констант
а) A U U,
б) A .
9. Законы дополнения
а) A A U, б) A A ,
в) U , г) U.
10. Закон инволюции (снятие двойного отрицания)
A A.