Реферат: Конспект по дискретной математики

--PAGE_BREAK--<img width=«79» height=«78» src=«ref-1_290074163-1652.coolpic» v:shapes="_x0000_s1027">  Объединение системы множеств можно записать

<img width=«53» height=«53» src=«ref-1_290075815-297.coolpic» v:shapes="_x0000_i1027">   — объединение системы nмножеств.
Пример:   объединение    множеств,   когда   они

заданы списком.
A= {a,b,d}  B= {b,d,e,h} AUB= {a,b,c,d,e,h}
    <img width=«271» height=«233» src=«ref-1_290076112-737.coolpic» v:shapes="_x0000_s1040"> <img width=«271» height=«232» src=«ref-1_290076849-739.coolpic» v:shapes="_x0000_s1045">
     

<img width=«148» height=«81» src=«ref-1_290077588-3018.coolpic» v:shapes="_x0000_s1032 _x0000_s1033 _x0000_s1034 _x0000_s1035 _x0000_s1036 _x0000_s1037 _x0000_s1038 _x0000_s1039"> <img width=«98» height=«99» src=«ref-1_290080606-2105.coolpic» v:shapes="_x0000_s1041 _x0000_s1043"> <img width=«99» height=«99» src=«ref-1_290082711-2133.coolpic» v:shapes="_x0000_s1042 _x0000_s1044">
2) Пересечением множеств А и В  называется множество, состоящие из элементов принадлежащих   одновременно множествам А и В.


<img width=«454» height=«174» src=«ref-1_290084844-720.coolpic» v:shapes="_x0000_s1074">AÇB
<img width=«127» height=«118» src=«ref-1_290085564-2839.coolpic» v:shapes="_x0000_s1059 _x0000_s1060 _x0000_s1061 _x0000_s1062 _x0000_s1063 _x0000_s1066 _x0000_s1067 _x0000_s1069 _x0000_s1070 _x0000_s1071 _x0000_s1072 _x0000_s1073"> <img width=«69» height=«118» src=«ref-1_290088403-1774.coolpic» v:shapes="_x0000_s1048 _x0000_s1049 _x0000_s1051 _x0000_s1052 _x0000_s1053 _x0000_s1054 _x0000_s1055 _x0000_s1057 _x0000_s1058">


Пересечение прямой и плоскости
1)      <img width=«13» height=«16» src=«ref-1_290090177-233.coolpic» v:shapes="_x0000_s1076">если прямые  ||  пл., то множество пересечений – единственная точка;

2)      если прямые IIпл., то M¹Æ;

3)      если прямые совпадают, то множество пересечений = множество прямой.
Пересечение системы множеств: <img width=«51» height=«51» src=«ref-1_290090410-280.coolpic» v:shapes="_x0000_i1028">

4)      Разностью 2-х множеств А и В называется множество, состоящее из всех элементов А, не входящих в В.
С = А \ В
<img width=«194» height=«165» src=«ref-1_290090690-497.coolpic» v:shapes="_x0000_s1081"> <img width=«194» height=«165» src=«ref-1_290091187-495.coolpic» v:shapes="_x0000_s1087"> <img width=«194» height=«165» src=«ref-1_290090690-497.coolpic» v:shapes="_x0000_s1093">


  <img width=«79» height=«79» src=«ref-1_290092179-1615.coolpic» v:shapes="_x0000_s1083"><img width=«79» height=«79» src=«ref-1_290093794-1104.coolpic» v:shapes="_x0000_s1084">            
A
\
B
  

  <img width=«108» height=«108» src=«ref-1_290094898-2122.coolpic» v:shapes="_x0000_s1077">         А \ В

      продолжение
--PAGE_BREAK--  <img width=«60» height=«59» src=«ref-1_290097020-1312.coolpic» v:shapes="_x0000_s1089"><img width=«60» height=«59» src=«ref-1_290098332-1310.coolpic» v:shapes="_x0000_s1088"><img width=«98» height=«98» src=«ref-1_290099642-1704.coolpic» v:shapes="_x0000_s1082">      <img width=«60» height=«60» src=«ref-1_290101346-1280.coolpic» v:shapes="_x0000_s1078"> 
A= {a,b,d}; B= {b,c,d,h} C= A\ B={a}.
В отличии от предыдущих операций разность: 1) строго двухместна;

                                                                                2) не коммутативна, т.е. A\B¹B\A.
4) дополнение <img width=«77» height=«28» src=«ref-1_290102626-284.coolpic» v:shapes="_x0000_i1029"> 

E– универсальное множество.

<img width=«16» height=«21» src=«ref-1_290102910-199.coolpic» v:shapes="_x0000_i1030"> — дополнение
Операции объединения, пересечения и дополнения называются Булевыми.
Основные законы операций над множествами.
Некоторые свойства È, Ç похожи на алгебраические операции, однако многие свойства операций над множествами все же отличаются.


Основные свойства


1)      AUB
=
BUA
;
A
Ç
B
=
B
Ç
A
– переместительный закон объединения и пересечения.

2)     
(
А
UB)UC = AU(BUC); (A
Ç
B)
Ç
C=A
Ç
(B
Ç
C) – сочетательныйзакон.

3)     
А
U
Æ
=A, AÇÆ
=
Æ
, A \
Æ
=A, A \ A=
Æ


1,2,3 – есть аналог в алгебре.

3.а)  
Æ
\
A
=
Æ
— нет аналога.

4)      <img width=«200» height=«30» src=«ref-1_290103109-392.coolpic» v:shapes="_x0000_i1031">Æ; E \ A =<img width=«16» height=«21» src=«ref-1_290102910-199.coolpic» v:shapes="_x0000_i1032">; A \ E=Æ; AUA=A; AÇA=A; AUE=E; AÇE=A;

5.а) свойства 1-4 очевидны и не нуждаются в доказательствах.

5)     
A
Ç
(
BUC
)=(
A
Ç
B
)(
A
Ç
C
)– есть аналогичный распределительный закон Çотносительно U.


    продолжение
--PAGE_BREAK--Прямые произведения и функции


Прямым декартовым “х” множеством А и В называется множество всех пар (a;b), таких, что аÎА, bÎB.
С=AхВ, если А=В то С=А2.
Прямыми «х» nмножеств A1x,…,xAnназывается множество векторов (a1,…an)  таких, что a1ÎA1,…, AnÎAn.
Через теорию множеств введем понятие функции.
Подмножество FÎMxxMyназывается функцией, если для каждого элемента хÎMxнайдется yÎМу не более одного.

(x;y)ÎF,    y=F(x).
Соответствие между аргументом и функцией можно изобразить с помощью диаграммы Венна:

<img width=«263» height=«154» src=«ref-1_290103700-3157.coolpic» v:shapes="_x0000_s1094 _x0000_s1096 _x0000_s1097 _x0000_s1098 _x0000_s1099 _x0000_s1100 _x0000_s1101 _x0000_s1109 _x0000_s1110"> <img width=«262» height=«153» src=«ref-1_290106857-3168.coolpic» v:shapes="_x0000_s1102 _x0000_s1103 _x0000_s1104 _x0000_s1105 _x0000_s1106 _x0000_s1107 _x0000_s1108 _x0000_s1112 _x0000_s1113">



   Определение: Между множествами MXи MYустановлено взаимноодназночное соответствие, если каждому хÎMX соответствует 1 элемент yÎMYи обратное справедливо.

Пример:   1)  (х, у) в круге

<img width=«290» height=«184» src=«ref-1_290110025-726.coolpic» v:shapes="_x0000_s1115">


<img width=«577» height=«162» src=«ref-1_290110751-2944.coolpic» v:shapes="_x0000_s1114 _x0000_s1117 _x0000_s1118 _x0000_s1121 _x0000_s1122 _x0000_s1123 _x0000_s1124 _x0000_s1125 _x0000_s1126 _x0000_s1127">
             2) x= sinx

<img width=«338» height=«237» src=«ref-1_290113695-2546.coolpic» v:shapes="_x0000_s1141 _x0000_s1142 _x0000_s1143 _x0000_s1144 _x0000_s1146 _x0000_s1147 _x0000_s1148 _x0000_s1149 _x0000_s1150">
                 RàR                                                <img width=«151» height=«52» src=«ref-1_290116241-379.coolpic» v:shapes="_x0000_i1033">

<img width=«76» height=«2» src=«ref-1_290116620-171.coolpic» v:shapes="_x0000_s1145">


Пусть даны две функции  f: AàBи g: BàC, то функция y:AàCназывается композицией функций  fи g.
Y=fog        o– композиция.
Способы задания функций:
1)      таблицы, определены для конечных множеств;

2)      формула;

3)      графики;
Способы 1-3 частные случаи выч. процедуры.
Пример процедуры, не относящейся к 3 способам задания функций n!
Взаимнооднозначное соответствие и мощности множеств.
Определение: Множества равномощны |A|=|B| если между ними взаимнооднозначное соответствие.
Теорема: Если для конечного множества А мощность равна |A| то количество всех подмножеств 2|A|=2n.

Множества равномощные Nназываются счетными, т.е. в них можно выполнить нумерацию элементов. N– множество натуральных чисел.       
Множество N2– счетно.
    продолжение
--PAGE_BREAK--