DiM 2203 дискретті математика



Pdf көрінісі
бет3/16
Дата25.11.2019
өлшемі3,62 Mb.
#52396
1   2   3   4   5   6   7   8   9   ...   16
Байланысты:
umkd (1)


Анықтама.  Элементтердің  ақырлы  санынан  тұратын  жиын,  ақырлы 
жиын деп аталады, керісінше болса ақырсыз жиын деп аталады. Мысалы N
R жиындары ақырсыз.  
Анықтама.  Ақырлы  жиындардағы  элементтердің  саны  жиынның 
қуаты деп аталады және |  | белгілерімен қоршалып жазылады. Мысалы, М – 
ақырлы жиын болса, оның қуаты | M |. Қуаты 0-ге тең жиын, яғни элементтері 
жоқ жиын бос жиын деп аталады және   белгіленеді |   | = 0. (|{ }| = 1емес)  
Бос  жиын  кез-келген  жиынның  ішкі  жиыны  болады  деп  есептеледі.Егер  А 
және  В  жиындары  тең  болса,  олар  тең  қуатты  жиындар  деп  аталады. 
Мысалдар: 
1. А = {1, 2, 3}, B = {3, 4, 5}, A   B. 
2. A = {1 ,2 ,3, 4}; B = {4, 3, 1, 2}; A = B, себебі A   BB   A
3. A = {1, 2, 3}; B = {2, 4, 6}; C = {1, 2, 3, 4, 5}, A   CB   A
Анықтама.  А  жиынының  барлық  ішкі  жиындарының  жиынтығы 
булеан  немесе дәрежелі жиын деп аталады және Р(А) деп белгілінеді (2
А
 деп 
те белгіленеді). Сонымен, 2
А
 = P(A) ⇆ {B | B   A} немесе 2
А
. Мысалдар: Егер 
А = {1, 2 ,3} болса, P(A) = { , {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}}. 
Анықтама.  Қарастыруға  болатын  барлық  мүмкін  элементтерден 
тұратын  жиын  универсал  немесе  универсум  деп  аталады  және  U  деп 
белгіленеді. 
 
1.3. Жиындармен операциялар (амалдар). 
 
P(U)  булеанындағы  операцияларды  және  олардың  геометриялық 
кескінделулерін қарастырамыз. 
1. Қиылысу операциясы. Егер A,B   P(U) онда, осы А, 
В  жиындарының  екеуіне  де  тиісті  элементтерден  тұратын 
жиынды  А,  В  жиындарының  қиылысуы  деп  атайды  және  ол 
төмендегідей өрнектеледі: 
A B⇆{x | x A & x B};  Мысалы, A{1,2,3}, B{3,4,5}  болса A B={3}; 
2.  Бірігу  операциясы.  А,В  жиындарының  ең  болмаса  біреуіне  тиісті 
элемент  терден  тұратын  жиынды  А,В  жиындарының  бірігуі 
деп атайды және ол төмендегідей өрнектеледі:
 
 
A   B ⇆ {x | x   A ∨  x B}     Мысалы,   A={1, 2, 3, 4}; 

B={4, 3, 6, 7} болса, A B = {1, 2, 3, 4, 6, 7} 
А,В жиындарының қиылысуын олардың көбейтіндісі (А*В), ал бірігуін 
олардың қосындсы (А + В) деп те атайды 
Жиындардың  айырымы.  А  жиынының  
В-ға  кірмейтін  элементтерінен  тұратын  жиынды 
А,В жиындарының айырымы деп  атаймыз және 
ол төмендегідей өрнектеледі:  
А\В⇆A-B⇆{x|x A және х В}. 
A{1,2,3},   B{3,4,5}  болса, A\B={1,2};    B\A ={4,5}; 
3.  Сақиналы  қосынды.    А,В  жиындарының  өзара 
айырымдарының  бірігуін  сақиналы  қосынды  немесе 
симметриялық  айырым  деп  атайды  A B⇆(A\B) (B\A) 
болып  белгіленеді.  (А\В) (В\А).Жоғарыда  қарастырылған 
А,В үшін: A={1,2,3,4};   B={4,3,6,7} ;  А \ B ={1,2,3,4} \  {3,4,6,7}={1,2}B\А= 
{3, 4, 6, 7}\{1, 2, 3, 4} = {6, 7}; А   В = {1, 2, 6, 7}; 
Симметриялық айырымның тағы бір формуласы:  
A B=A B=A B ⇌(A B)\(A B); 
A B={1, 2, 3, 4, 6, 7} \ {3, 4}={1, 2, 6, 7}. 
4.  Жиынының  толықтауышы.  U  универсумындағы  А-ға  тиісті  емес 
элементтер U универсумындағы А жиынының толықтауышы деп аталады (А-
ны U-ға дейін толықтыратын) Ā⇆U\A болып белгіленеді. 
 
Мысалы, A = {1,2,3,4} жиынының толықтауышы. Ā ={6,7}; B={4,3,6,7} 
жиынының  толықтауышы 
В
  ={1,2}  ;  { , , }  операциялары  буль 
операциялары деп аталады .  
5.  Анықтама.  Жиындардың  геометриялық  кескіндері  Эйлер-Венн 
диаграммалары  деп  аталады.  Біріктіру,  қиылысу  операцияларын  кез-келген 
жиындар  дың  жиыны  болатын  А
i
  (мұндағы  і 
  І  жиынының  элементтерін 
қабылдайды) жиынына да анықтауға болады: 
Айталық  І  –  элементтері  индекс  ретінде  қолданылатын  қандай  да  бір 
жиын болсын және   і   І үшін А
і
 белгілі болсын. Олай болса, қиылысу  
i
A
{
 

I
i
}  мен  бірігуді   
i
A
{
|  і   I}  төмендегідей  анықтауға  болады.         
i
A
{
  | 
I
i
}={x | x   A
 і  ,   
  (кез-келген,барлық)   і I үшін }; 
i
A
{
| і  I} ={x | x   
A
і 
 ,  (ең болмағанда бір  і   I үшін } теңдіктерімен беріледі.   Көбінесе, 
i
A
{
 

I
i
},   
i
A
{
|  і   I}    орнына     
i
I
i
A

i
I
i
A
  немесе  текстің  мәтінінен      І  
жиынының  қандай  екенді гі белгілі болса   жай ғана 
і
А
  , 
і
А
    белгілерін 
қолданады. 
i
I
i
A
={x|x A 


 
і I};
i
I
i
A
={x|x A

,
і I};  Егер 

I={1,2,…,n}болса  A
1
A
2
A
3
… A
n   
;  A
1
A
2
A

… A


i
n
i
A
1
  және 
i
n
i
A
1
белгілеулері қолданылады.  
1.4. Жиындарға қолданылатын операциялардың қасиеттері 
 
Айталық  U  универсумы  берілсін.  Олай  болса 
  А,В,С 
  U 
төмендегідей қасиеттер орындалады: ,  операцияларының ассоциативтігі  
A (B C)=(A B) C 
A (B C)=(A B) C  
2.  , операцияларының коммутативтігі  
A B=B A;  
A B=B A 
3. Дистрибутивті заң (үлестіру заңы) 
A (B C)=(A B) (A C)    
A (B C)=(A B) (A C) 
4. Идемпотенттік заң 
A A=A;    A A=A     
5. Жұтылу заңы 
A (A B)=A; A (A B)=A 
6. Де Морган заңы 
B
A
=
A
B
  
B
A
=
A
B
 
7. Нөл мен бір заңы, айталық 0⇆ , 1⇆U онда 
А
=A;  A
= ; 
A 1=1;    A 1=A; 
A
A
=1;  A
A
=  
8. Қос терістеу заңы (инволютивность) 
А
A
 
9. Толықтыру заңы. 
A
A
U

A
A
 
 
Жиындарға 
қолданылатын 
операциялардың 
қасиеттерінің 
дұрыстығына бірнеше тәсілдермен көз жеткізуге болады: 
Нақтылы  жиындар  мен  амалдарды  орындау  арқылы  (екі  жағынан 
бірдей нәтиже шығады) ; 
Венн диаграммасын сызу арқылы; 
Амалдардың анықтамасын пайдалану арқылы. 
 операциясының ассоциативтігін дәлелдейік: 
Дәлелдеуі:  Ассоциативті  заңды  дәлелдеу  A (B C)=(A B) C  (Теру 
заңы)
};
,
b
a
A
 
};
,
,
{
d
c
a
B
 
}
,
,
,
{
e
d
c
b
C
 болсын. 
1-тәсіл. Амалдарды орындайық.
C
B
A
C
B
A
)
(
)
(

Сол жағы :
};
,
,
,
,
{
}
,
,
,
,
{
}
,
{
e
d
c
b
a
e
d
c
b
a
b
a
 

Оң 
жағы: 
};
,
,
,
,
{
}
,
,
,
{
}
,
,
,
{
}
,
,
,
{
})
,
,
{
}
,
({
e
d
c
b
a
e
d
c
b
d
c
b
a
e
d
c
b
d
c
a
b
a
 
Демек жиындар тең. 
2-тәсіл. Диаграммасын салайық: 
 
Диаграммаларының  бірдейлігінен  жиындар  тең  деген  қорытындыға 
келеміз. 
3-тәсіл. 
а) 
C
x
B
x
A
x
C
B
x
A
x
C
B
A
x
)
(
 
C
B
A
x
C
x
B
A
x
)
(
;  Бұдан 
.
)
(
)
(
C
B
A
C
B
A
  Енді  екінші 
жағынан, 
б) 
C
x
B
x
A
x
C
x
B
A
x
C
B
A
x
)
(
)
(
 
)
(
)
(
C
B
A
x
C
B
x
A
x
 
демек, 
)
(
)
(
C
B
A
C
B
A

Яғни, 
A (B C)=(A B) C  
 
1.5. Жабу және бөліктеу 
 
Айталық, {A

|  i I}  А  жиынының  бос  емес  ішкі  жиындары  болсын.  A


Анықтама.  Егер  A  =
i
I
i
A
  болса,  яғни  А  жиынының  әр  элементі  А
і
 
жиындарының ең болмаса біреуіне кірсе, онда бос емес {A

|  i I}  жиыны  А 
жиынының  жабуы  деп,  ал  егер    i j    болғанда    A

A


    болса,  жабу 
бөліктеу деп аталады (  I , j I  i j =  A

A


). Басқа сөзбен айтқанда А 
жиынының    бос  емес  {A

|  i I}  ішкі  жиындары  қиылыспаса  яғни  А-ның  әр 
элементі бос емес А
і
 жиындарының тек біреуіне ғана кіретін болса, онда {A


i I} жиыны  А жиынының бөліктеуі деп  аталады. Мысалы, А={1,2,3} болса, 
онда  {{1,2},{2,3},{3,1}}  –  А  жиынын  жабады,  ал  {{1},{2},{3}}  –  А 
жиынының бөліктеуі болады. 
 
 
Негізгі әдебиет: 1[5-9];  2[10-16]  
Қосымша әдебиет: 7[9-34]  
Бақылау сұрақтары: 
1.  Қандай жиынды ішкі жиын деп атайды? 
2.  Қандай жиындар тең болады? 
3.  Жиындармен орындалатын негізгі операцияларды қандай? 
4.  Бірігу,қиылысу,толықтыру  операцияларының  негізгі  қасиеттерін 
атаңыз. 
5.  Жиындарды өрнектеудің қандай әдістері бар? 
 
 

2-Дәріс. Жиындардың декарттық көбейтіндісі.  
 
2.1. Жиындардың декарттық көбейтіндісі. 
 
 х
1
...х
n
      n  элементтен  тұратын  реттелген  тізбекті  (x
1
,x
2
,…,x
n
)  немесе 
1
,x
2
,…,x
n
> деп белгілеуге болады. Мұндағы дөңгелек, бұрышты жақшалар 
элементтердің  жазылу  ретін  көрсету  үшін  ғана  қолданылады.  Мұндай 
нөмірлерінің  ретіне  қарай  орналасқан  тізбек  ұзындығы  реттелген  тізбек 
немесе  ұзындығы  n  болатын  кортеж  деп  аталады. 
i
х
-элемент  1
,x
2
,…,x
n

кортежінің  і- координатасы деп аталады. 
Мысалдар  
{a,b,c}  және  {1,2}  жиындарынан  ұзындығы  2-ге  тең  6  кортеж  құруға 
болады: 
(a,1), (a,2), (b,1), (b,2), (c,1), (c,2) 
2.  Кез-келген  әріптерден  құралған  сөз  кортеж,  натурал  сандардың 
ондық жүйедегі жазылуы цифрлардан   тұратын кортеж т. б. 
Кез-келген  координаттары  әртүрлі  реттелген  ақырлы  жиын 
кортеж.Ұзындығы 2-ге тең кортеждер реттелген жұптар, ұзындығы 3-ке тең 
кортеждер  реттелген  үштіктер,  ұзындығы  n-ге  реттелген  n-діктер  деп 
аталады.  Жиындар  екі  элементпен  алу  амалының  көмегімен  төмендегі 
ережеге сәйкес кодталады. 
< >⇋ , 1
> ⇋x
1
1
, x
2
>⇌{{x
1
},{x
1
,x
2
}}, 1
,…,x
n
>⇌< 1
,x
2
,…,x
n
>, 
x
n+1  

Анықтама.Екі  кортеж  ұзындықтары  бірдей,  әрі  бірдей  нөмірлі 
координаттары  тең  болса  ғана  тең  болады.      Яғни        x=(x
1
,x
2
,…,x
n
)  ,  
y=(y
1
,y
2
,…,y
n
)   кортеждері  x
1
=y
1
;  x
2
=y
2
,…x
n
=y
n
  болғанда ғана тең болады  
( x=y ). Мысалы  (1
2
, 2

, 3

) және (
1
 
16
,
81
,
) кортеждері тең. (1,2,3) және 
(3,1,2)  әртүрлі ; (1,2,3) және (1,2,3,4) әртүрлі; (1,2) (2,1) ал {1,2} және {2,1} 
жиындары  тең.  Кортеждердің  координаттары  жиын,  кортеж  т.  б.  болуы 
мүмкін. Мысалы, ({a,b},c)=({b,a},c)  себебі {a,b}={b,a}, ал ( (a,b ), c ) және ( 
(b,a),  c  )  кортеждері  тең  емес,  себебі  (a,b) (b,a).  Бір  де  бір  координаты  жоқ 
кортеж (ұзындығы 0) бос кортеж деп аталады.  
Сонымен жиын мен кортеж ұғымдарының айырмашылығы: 
а)  жиындардың  элементтерінің  орны,  реті  бәрі  бір,  ал  кортеждерде 
элементтерінің  ұзындығы  бірдей  болып  элементтерінің  реті  басқаша  болса 
тең емес (құрамы бірдей болса да); 
б) жиында элементтер әртүрлі, кортежде бірдей бола береді. 
Анықтама. А және В жиындарының тура  (декартық) көбейтіндісі деп 
элементтері  реттелген  (х  ,у)  жұбынан  тұратын  жиынды  айтамыз.Мұндағы, 
х А, ал  у В. Декарт көбейтіндісі   әр түрлі жиын элементтерінен құралады, 
А   В болып белгіленеді: А   В = {(х ,у) | х А және у В}.  
n
A
A
A
,...,
,
2
1
  
жиындары үшін Декарт көбейтіндісі?  
n
A
A
A
...
2
1
 = 
т
m
i
A
1

}
,...,
,
)
,...,
,
{(
2
2
1
1
1
1
n
n
n
A
x
A
x
A
x
x
x
x
 болады. 

Егер A
1
=A
2
=…=A
n
=A болса, онда A
1
хA
2
х,…,хA
n
 жиыны А жиынының 
n-ші  Декарт  дәрежесі  деп  аталады  және  А
n
  болып  белгіленеді.  Анықтама 
бойынша A
0
⇌{ } 
Мысалдар: 
1.A={1,2}, B={3,4} берілсін. AхB={ (1,3),(1,4),(2,3),(2,4) }; 
BхA={ (3,1),(3,2),(4,1),(4,2) }; 
AхA={ (1,1),(1,2),(2,1),(2,2) }; Бұл мысалдардан AхB BхA. 
2. (Шахмат тақтасы). 
A={a,b,c,d,e,f,g,h};  B={1,2,3,4,5,6,7,8}  жиындары  берілсін.  Олай  болса 
әр (х,у) жұбына x,y AхB шахмат  тақтасының торлар жиыны сәйкес келеді. 
3. [0,1]
2
 жиыны { (a,b) | 0    a  1, 0   b    1 } ;Бұл жиынға жазықтықтың 
1-ден аспайтын теріс емес координаттары бар нүктелер жиыны сәйкес келеді. 
4. 
A={a,b,c}; 
B={1,2}; 
AхB={(a,1),(a,2),(b,1),(b,2),(c,1),(c,2)}; 
BхA={(1,a),(2,a),(1,b),(2,b),(1,c),(2,c)}; AхB   BхA 
5. А={1,2,3}; АхА={(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1 ), (3,2), (3,3) 
}; 
6.
}
,...,
,
{
2
1
m
x
x
x
X

}
,...,
,
{
2
1
n
y
y
y
Y

Y
,
  -    жиындарының  Декарт  көбей-
тіндісін  табайық.  Декарт  көбейтіндісінің  элементтері  әр  түрлі  жиын 
элементтерінен алынған жұптардан тұратындығы белгілі. 
Оларды  кестеге  орналастырайық:  Бұл  кестеде  m  жол,  n  бағаннан 
тұратын элементтер жұбын көреміз. 
)
,
(
y
x
  -  саны  х-элементтерінің    жиыны 
мен ү элементтерінің  жиындарының көбейтіндісіне тең. 
)
(
)
(
)
,
(
y
x
y
x
 (1) 
Бұл  жиындарды  көбейту  ережесі.  Егер  декарт  көбейткіштері  n 
жиыннан тұрса, онда (1) төмендегідей  жалпылауға болады: 
 
)
(
)...
(
)
(
)
*
...
*
*
(
2
1
2
1
n
n
x
x
x
x
x
x
 (2)A х B х C;   (A х B) х C; A х (B х C)  
жиындары да әр түрлі. A х B х C- (a,b,c);  (A х B) х C- 
((a,b),c ) a A, b B, c C; A х (B х C)=(a, (b,c) ); Егер А,В жиындарының 
бірі бос болса, олардың Декарт көбейтіндісі де бос деп есептеледі. A х   =   
х A =   х   =  ; 
Мысал, А={a
1
,a
2
,a
3
}, B={b
1
,b
2
,b
3
} ;  
АхВ
3
3
2
3
1
3
3
2
2
2
1
2
2
1
2
1
1
1
b
a
b
a
b
a
b
a
b
a
b
a
b
a
b
a
b
a

 
2.2. Сәйкестік және оның қасиеттері. 
 
Сәйкестіктер  –  жиын  элементтерінің  арасындағы  өзара  байланысты 
беру тәсілі. Оның дербес жағдайлары: функциялар, бейнелер, түрлендірулер, 
т.б. 

Анықтама.  А,  В  жиындарының  арасындағы  сәйкестік  деп  бұл 
жиындардың тура (декарт) көбейтіндісінің G ішкі жиынын айтады.  
G   AхB  Егер (a,b) G болса,G сәйкестігінде b  a-ға сәйкес деп айтады. 
G
={a|(a,b) G, G сәйкестігінің анықталу облысы, ал    
G
={b|(a,b) G}  мәндер 
жиыны деп аталады.  
Анықтама.  Егер 
G
=A  болса  толық  анықталған 
сәйкестік, 
A
A  болса  толық  емес  (жартылай)  сәйкестік 
болады. (толық анықталмаған). 
Анықтама.  Егер 
G
=B  –  сюръективті  сәйкестік  деп 
аталады.  (В-ның  әрбір  элементінің  А  прообразы  бар)  Анықтама  А 
жиынының  әрбір  a A    элементіне  B  жиынының    G  сәйкестігіндегі    а-ға 
сәйкес барлық b B элементтерінің жиыны   a элементі- нің образы, ал  әрбір 
b B    элементіне  А  жиынының    G  сәйкестігіндегі    в-ға  сәйкес  барлық  a A 
элементтерінің  жиыны  b  элементінің  А    жиынындағы  прообразы  деп 
аталады. 
Анықтама. Барлық а  С 
G
 элементтерінің образдарының жиыны С 
жиынының  образы  деп  аталады.  Барлық    в D
G
    элементтерінің 
прообраздарының жиыны  D
   
 жиынының прообразы деп аталады. 
Анықтама.  Егер  анықталу  облысынан  (
G
)  алынған  кез-келген  а 
элементінің  мәндер  жиынында  (
G
)    бір  ғана  образы  b
G
  болса,  G  – 
функционал (бір мәнді) сәйкестік деп аталады. 
Анықтама.  Егер  G  сәйкестігі  толық  анықталған,сюръективті, 
функционалды  және    b
G
  элемен  тінің  анықталу  облысында  бір  ғана 
прообразы a
G
 болса, онда G өзара бір мәнді сәйкестік  болады. 
Егер А мен В жиындарының арасында өзара бір мәнді сәйкестік болса, 
онда  олардың  қуаттары  тең  және  олар  тең  қуатты  жиындар  |A|=|B|  деп 
аталады.Бұл фактілер жиынды  санамай-ақ,олардың 
тең 
қуаттылығын 
анықтауға 
болатындығын 
көрсетеді.  Қуаты  белгілі  немесе  оңай  санауға 
болатын  басқа  жиынмен  өзара  бір  мәнділігін 
дәлелдеу  арқылы  жиын  элементтерін  санамай-ақ 
оның  қуатын  анықтауға  болады.  N  натурал  сандар 
жиыны мен тең қуатты жиындар саналымды жиын деп аталады. 
R  нақты  сандар  жиынымен  тең  қуатты  сандар  континуальды  деп 
аталады.  
1- мысал. Айталық , G  (x-3)
2
+(y-2)
2
≤1 қатынасын қанағат тандыратын 
барлық   (х,у)  нақты санды сандар жиыны болсын.    G={(x,y)|x,y  үшін (x-
3)
2
+(y-2)
2
≤1}    сәйкестігінің    графикалық  кескіні      центрі  (3,2)  нүктесінде 
болатын ,радиусы 1-ге тең дөңгелек. Бұл 3.2 суреттегідей G дөңгелегі  R мен 
R  арасындағы  сәйкестік    (  яғни  ОХ  өсі  мен  ОУ  өстерінің  арасындағы   
сәйкестік).  
а) 2, 3, 4 сандарының образы мен прообраздарын табу керек. 
Шешуі:  2
G
  G  сәйкестігіндегі  образы  жалғыз  ғана  2
G
,  3-ң  G 
сәйкестігіндегі образы [1,3] кесіндісіндегі  барлық нақты сандар  жиыны , 4-ң 

образы  2. G сәйкестігінің мәндер жиыны 
G   
алын ған  (2
G  
)    2 санының 
G  сәйкестігіндегі  прообразы  [2,4]
G
  ;  3
G
  G  сәйкестігіндегі  прообразы  
3
G
. 4
G
 – G сәйкестігінде прообраздары жоқ  
б)  1)  [2,3] 
G
    сандарының  образы  осы  [2,4]  кесіндідегі  барлық 
образдарының бірігуі, яғни   [1,3]
G

2) Осыған ұқсас [2,4]  кесіндісінің G сәйкестігіндегі образы [1,3];  
3) [2,3]   кесіндісінің  прообразы [2,4] ; [2,4]
G
   прообразы [2,4]; 
Егер  G  сәйкестігі  нақты  сандар  жиынында  анықталған  десек,  яғни 
G RхR онда 
1) G – толық анықталмаған себебі ,
G
R (
G
R) 
2) Сюръективті емес себебі 
G
R (
G
R) 
3)  Функционалды  (бір  мәнді)  емес,  себебі  [2,4]=
G
  үшін  (2  мен  4-тен 
басқа) образдар     жалғыз емес. 
4)  Өзара  бір  мәнді    болудың  қажетті  шарттары  (1,2,3  шарттар) 
орындалмағандықтан  сәйкестік өзара бір мәнді  емес. 
Егер  сәйкестік  G 
[2,4]х[1,3]  болса  G  толық  анықталған    және 
сюръективті ,бірақ функционал ды және өзара бір мәнді емес.  

Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   ...   16




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет