Жиындар теориясының негізгі ұғымдары

Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 83 бет
Таңдаулыға:

1 Жиындар теориясының негізгі ұғымдары
1.1 Жиындар
Жиын математикадағы негізгі ұғымдарының бірі болғандықтан, оған анықтама берілмейді. Жиын деп белгілі математикалық объектілердің жиынтығын түсінеміз. Ол объектілер жиынның элементтері деп аталып, кіші әріптермен, ал жиынның өзі бас әріппен белгіленеді.
а элементі А жиынына тиістілігін аА, "" - тиістілік кванторымен белгілейді.
b A - b элементі А жиынына тиісті емес.
Бізге белгілі жиындарды атап өтейік:
N - натурал сандар жиыны;
Z - бүтін сандар жиыны;
Q - рационал сандар жиыны;
R - нақты сандар жиыны;
C - комплекс сандар жиыны;
Ø - бос жиын.
Жиі қолданылатын кванторлар:
- кез келген, х А (кез келген х А жиынында жатады);
- табылады, у В (В жиынынан у элементі табылады);
׃ ( ) - мынадай, қасиетін сипаттау үшін;
- бұдан шығатын салдар;
- тепе-теңдік кванторы, тек сол жағдайда;
- қатаң енгізу кванторы.
Жиынға енетін элементтер саны шенеулі немесе шексіз көп болуы мүмкін.
1-мысал: а) қазақ алфавитінің әріптер жиыны (42 элемент бар);
ә) натурал сандар жиыны ( элементі бар);
б) теңдеуінің нақты түбірлерінің жиыны ешқандай да элементтен тұрмайды, бос жиын.
Ақырлы жиын деп осы жиынның элементтерінің санына тең болатын натурал сан табылатын жиынды айтады. Ақырлы емес жиын ақырсыз жиын деп аталады.
Ақырлы А және В жиындары тек қана бірдей элементтерден құралса, тең жиындар деп аталып, А=В деп белгіленеді.
Егер ақырлы А жиынында ақырлы В жиынына тиісті емес элемент бар болса, және керісінше, онда олар тең емес жиындар деп аталады.
2-мысал. {0, 1, 2}={1, 2, 0}, {0, 1}{1, 2, 0, 3}.
Жиындардың берілу тәсілдері.
1. Мүшелерін (элементтерін) тізіп жазу арқылы. Ақырлы жиын
, ақырсыз жиын В={1, 3, 5, 7, ..., } - тақ сандар жиыны.
2. Сипаттау арқылы. Мысалы жиынның кез келген х мүшесі р(х)
қасиетіне ие болсын, онда осы элементтерден тұратын С жиыны былай беріледі: С={х(х)}.
Осы сияқты анықталған жиындар
Q={}, В={х: х=}.
А және В жиындары берілсін. Егер А жиынының кез келген х элементі В жиынында да жатса, онда А жиыны В жиынының ішкі жиыны деп аталады.
А В немесе В А деп белгіленеді. Кванторлар тілінде
(А В) (х А х В).
Егер В жиынының А ішкі жиыны В жиынынан және Ø-ден өзгеше болса,
онда ол меншікті ішкі жиыны деп аталады. Кванторлар тілінде, А В
А В және А В.
Ø кез келген жиынның ішкі жиыны болады: Ø А.
Қасиеттері:
а) А А;
ә) А В, В А А = В;
б) А В, В С А С.
В жиынының В және Ø ішкі жиындары оның меншіксіз ішкі жиындары деп аталады. Егер жиын ең болмағанда екі элементтен тұрса, онда оның меншікті ішкі жиындары болады.
Мысалы: А = {а, в} жиынының ішкі жиындары: {а}, {в}, {Ø}, {а, в}. Бұл ішкі жиындардың ішінде {а}, {в}- меншікті, ал {а, в}, {Ø}- меншіксіз болып табылады.

Ішкі жиындарға қолданылатын амалдар
U (универсум) деп кең жиынды белгілейік, яғни элементтер осы жиыннан алынып отыратын болсын.
Эйлер - Венн диаграммасы. Тік төртбұрыштың нүктесі U жиынынан алынған деп есептейік. Мысалға А={1,2,3,4}, В={1,3,5}, С={5,6} жиындарын алайық.
1. Ең болмағанда А жиынына немесе В жиынына тиісті элементтер
жиынын А және В жиындарының бірігуі (қосындысы) (А В) деп айтады.
А В = {х: х А немесе х В}

А В={1,2,3,4,5}, А С={1,2,3,4,5,6}.

1.1 Сурет
___________________________________ ______
Леонард Эйлер (1707-1783)- швейцарлық математик.
Джон Венн (1834-1923) - ағылшын математигі.
Бірігу амалын жалпыласақ,
2. А жиынына да, В жиынына да тиісті элементтер жиынын А және В жиындарының қиылысуы (көбейтіндісі) (АВ) деп айтады.
АВ ={х:хА және хВ}.

А В={1,3}, В С={5}, АС= Ø.

1.2 Сурет
Қиылысу амалын жалпыласақ, .
3. А жиынына тиісті, бірақ В жиынына тиісті емес элементтер жиынын А және В жиынының айырымы (А\В) деп айтады.
А\В = {х:хА және хВ}

А \ В={2,4}, В \ С={1,3}, А\С=А.

1.3 Сурет
4. А және В жиындарының симметриялық айырмасы (АВ) деп келесі
жиынды айтады:
АВ=(А\В) (В\А)= {х:(хА және хВ) немесе (хВ және хА) }.

1.4 Сурет
АВ= {2,4}{5}={2,4,5}, АC= {1,2,3,4}{5,6}={1,2,3,4,5,6}.
5. U\A жиыны А жиынының толықтауышы деп аталып, деп белгіленеді.
= U\A

1.5 Сурет
Унивесум U={1,2,3,4,5,6,7,8,9} болса, онда ={5,6,7,8,9} болады.

1.2 Жиындар алгебрасы
Жиындарға амалдар қолданып, жаңа жиындар алуға болады. Осы амалдардың негізгі қасиеттері мен олардың арасындағы байланыс жиындар алгебрасы деп аталады.
1.1 К е с т е - Қасиеттер

1
(идемпотенттік)
АА=А

АА=А
2
Ауыстырымдылық (коммутативтік)
АВ=ВА

АВ=ВА
3
Үлестірімділік
А(ВС) =(АВ) С

А (ВС) =(АВ) С
4
Терімділік (дистрибутивтік)
А(ВС) =(АВ) (АС)

А (ВС) =(АВ) (АС)
5
Сіңіру
А(ВА)=А

А (ВА)=А
6
Нөлдің қасиеті А Ø=А
А Ø= Ø
7
Бірдің қасиеті А U= U
А U= А
8
Қосалқы принципі (де Морган заңы)

9
Екі рет теріске шығару

10
Толықтауыштың қасиеті

Ø
Жиындар арасындағы қасиеттер (заңдар) жоғарыдағы келтірілген қасиеттермен шектеліп қоймайды. Қалған қасиеттерді логика алгебрасының ережелері бойынша аталған касиеттерді қолданып алуға болады.

Жиындардың декарттық (тура) көбейтіндісі
Математикада жиындардың жай элементтері ғана емес, сонымен бірге олардың реттелген жұп элементтері де кездеседі. (а1,а2,...,аn) элементтері реттелген жиын берілсін, оны жиынтық, вектор, кортеж деп те атайды, аі -
___________________________________ ______________
Огастес де Морган (1806-1871) - шотландық математик

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

1.6 Сурет
1-есеп. де Морган заңын (қосалқы принципі) дәлелдеу керек.
Шешуі: І әдіс Эйлер-Венн диаграммасы арқылы. Ол үшін теңдіктің сол жағындағы жиынды кескіндеп аламыз:
а)

1.7 Сурет
Ал оң жақтағы жиынды бейнелеу үшін алдымен жиынын көлденең жолақпен, жиынын тік жолақпен белгілеп аламыз. Сонда бізге керекті жиын осы екі жолақтың қиылысуында, яғни тормен кескінделген жиын болады;
ә)

1.8 Сурет
Байқасақ, жоғарыдағы диаграммада штрихпен белгіленген жиын мен төмендегі тормен белгіленген жиын бір жиынды береді, бұл екі жиынның теңдігін білдіреді.
ІІ әдіс қасиеттерге сүйеніп, өрнектерді түрлендіру арқылы.
Алдымен U =VUV, VU қасиеті бойынша:
1) ;
2) енгізулері орындалатынын көрсетейік.
1) және және ;
2) керісінше, және және .

Жиынның бүркеуі мен бөлікшесі
Жиындарға қолданылатын операциялардың тағы бір түрі - жиынды ішкі жиындар жүйесіне бөліктеу операциясы болып табылады. А жиыны мен оның ішкі жиындар жүйесін A қарастырайық.
Анықтама. Егер 1) A Ø], 2)
шарттары орындалса, онда A жиын жүйесін А жиынының бүркеуі деп атайды.
Анықтама. Егер 1) A Ø, ]; 2) ;
3) A Ø] немесе Ø
шарттары орындалса, онда A жиын жүйесі А жиынының бөлікшесі деп аталады.
Егер бүркеу анықтамасындағы екі шартқа 3) шартты қоссақ, онда бүркеу бөлікше бола алады. Басқаша айтқанда, егер әрбір элементі тек қана бір Аі ішкі жиынына тиісті болса, онда А жиынының бос емес ішкі жиындардың A жүйесі оның бөлікшесі бола алады.
1 - мысал. жиыны берілсін:
а) - А жиынының бүркеуі;
ә) - А жиынының бөлікшесі болады;
б) - қандай-да бір ішкі жиындардың жүйесі, ол бүркеуі де емес, бөлікшесі де емес, себебі .
2 - мысал. N - натурал сандар жиынын қарастырайық. N 0 - жұп, N 1 - тақ сандар жиыны болсын. Онда {N 0 , N 1 } - N бөлікшесі бола алады.
1.3 Қатынастар. Унарлы, бинарлы, n-орынды қатынастар
А1, А2, ..., Аn жиындарындағы n - орынды қатынас немесе n - орынды предикат деп А1А2...Аn тура көбейтіндісінің кез келген жиыншасын айтамыз. Басқаша айтқанда, егер (х1,х2,...,xn)Р болса, х1, х2, ..., xn элементтері (мұндағы х1, х2, xn ) Р қатынасымен байланыстырылған деп аталып, Р(х1,х2,...,xn) деп белгіленеді.
n=1 болса, онда Р қатынасы А жиынының жиыншасы болады, РА және унарлы қатынас немесе қасиет деп аталады.
n=2 болса, онда жиі кездесетін екі орынды қатынас. Бұл жағдайда олар бинарлы қатынас немесе сәйкестік деп аталады. Сонымен А және В жиындарының арасындағы Р сәйкестігі АВ жиынының жиыншалары болып табылады, және (х,у) , оны жиі хРу деп жазады.
- А жиынындағы n-орынды қатынас. Кейбір оқулықта бинарлық қатынасы немесе деп белгіленеді, А1 - қатынасты жіберу облысы, А2 - қатынасты қабылдау жиыны деп аталады.
1 - мысал:
а) егер ал бинарлық қатынас P={(x;y) x,y, y элементі х-ке бөлінеді, х}, онда P={(2,2),(2,4),(2,6),(2,8),(3,3),(3 ,6)};
ә) P={(х,у) x, y} қатынасын R жиынында қарастырайық. Онда xPy жазуын деп түсінуге болады, яғни Р қатынасы "" символымен берілген;
б) А - нақты сандар жиыны, онда {(x,y)} A жиынындағы бинарлы қатынас болады;
в) А - адамдар жиыны , онда {(x,y)-тің туысқаны} А-дағы бинарлық қатынас.
Бинарлы қатынастардың берілу жолдары:
1) тізіп жазу арқылы, мысалы (2,2), (2,4), (2,6), (2,8), (3,3), (3,6);
2) бинарлық қатынасын график көмегімен кескіндеу қолайлы.
Өзара перпендикуляр өстер (Ox - көлденең өс, Oy - тік өс) сызайық. А және В жиындарының элементтерін сәйкес өстерде белгілейік. XOY жазықтығында координаталары болатын нүктелерді белгілейік. Алынған нүктелер жиыны Р қатынасына сәйкес келеді;

1.9 Сурет
1 мысалдағы Р қатынасы.
3) Р қатынасымен байланысқан және элементтері стрелкамен қосылған түрінде.
2 - мысал. мен жиындарының арасындағы қатына-сын, ал А жиынындағы қатынасын бейнелеу керек:
а) ;
ә) ;

1.10 Сурет
4) ақырлы жиындардың арасындағы бинарлы қатынас жұптардың тізімімен немесе матрица арқылы беріледі. , және бинарлы қатынасы берілген болсын. Бұл қатынастың матрицасы: , өлшемді, мұндағы
.
Сонымен нөл мен бірден тұратын кез келген матрица - қандай да бір бинарлы қатынастың матрицасы болып табылады.
3 - мысал. а) , жиындары мен осы жиындар арасындағы , қатынастары берілген. Бұл қатыныстарды матрица арқылы беруге болады
, ;
ә) жиынында қатынасы берілген: . Бұл қатынасқа сәйкес матрица
.
Анықтама. Р қатынасының анықталу облысы (Dp деп белгіленеді) Dpкейбір у үшін . Ал мәндерінің жиыны Еркейбір х үшін жиындары айтылады.
Dp - бірінші элементтерден құралған жиын,
Ер - екінші элементтерден құралған жиын.
А және В жиындарының арасында Р қатынасы берілсін. .
Келесі анықтамаларды енгізейік:
а) кері қатынас:
;
ә) толықтауыш қатынас:
;
б) тепе-тең қатынас:
. Кейде деп белгіленеді, -дағы диагональ деп те атайды;
в) универсалды қатынас:
және кейде толық қатынас деп те атайды.
4 - мысал. жиынында x элементі y - тің бөлгіші} қатынасы берілген. Олай болса . Бұл қатынас үшін Dp={2,3} - анықталу облысы, Ep={2,3,4,6,8} - мәндерінің жиыны, P-1={(2,2),(4,2),(6,2),(8,2),(3,3), (6,3)} - кері қатынас.
1. P қатынасына (предикатына) қатысты Х жиынының бейнесі деп, келесі жиын айтылады: P(x)={y(x,y), кейбір үшін}
2. P предикатына қатысты кері бейнесі деп, Р-1(х) немесе Р-1 предикатына қатысты Х жиынының бейнесін айтады.
Анықтама. және бинарлық қатынастарының композициясы немесе көбейтіндісі деп қатынасы немесе жиыны айтылады, ол былай анықталады
және .
5-мысал және - оң бүтін сандар жиынында берілген бинарлық қатынастар болсын: -оң бүтін сан}, - оң бүтін сан}. Онда - оң бүтін сан} және - оң бүтін сан}.
Теорема. Кез келген P, Q, R бинарлық қатынастар үшін келесі қасиеттер орындалады:
а) ;
ә) ;
б) .
Дәлелдеуі [1, 19 бет].
Бинарлық қатынас матрицасының негізгі қасиеттері
Егер және , онда
1.
(матрицалардың элементтерін қосу 0+0=0; 1+1=0+1=1+0=1 ережесі бойынша жүргізіледі);
2.
матрицалардың элементтерін көбейту кәдімгідей іске асырылады, яғни 00=01=10=0; 11=1).
1-мысал. бинарлық қатынастардың матрицалары берілген. Олар үшін
,
.
3. Егер -кері қатынас болса, онда .
4. Егер және .
5. -тепе-тең қатынас болса, онда - бірлік матрица.
6. -ның толықтауышы, онда - бұл -дағы 0-ді 1-ге, ал 1-ді 0-ге ауыстырған матрица.
7. Егер , онда композиция және матрицалар кәдімгі матрицаларды көбейту ережесі бойынша іске асырылады, бірақ матрицаларды көбейту кезінде элементтерді қосып, көбейту бірінші пункттегідей жүргізіледі
.
Анықтама. P қатынасы анықталған болсын.
1. Егер үшін болса, онда P рефлексивті қатынас деп аталады (P-бір қалада тұру).
2. Егер үшін -дан шығатын болса, онда P симметриялы қатынас деп аталады (P-бір фирмада жұмыс істеу).
3. Егер -дан шығатын болса, онда P антирефлексивті деп аталады (P-ұлы болу).
4. Егер және -дан шығатын болса, онда P антисимметриялы қатынас деп аталады (P-бастық болу).
5. Егер және -да шығатын болса, онда Р транзитивті қатынас деп аталады (P-ағасы болу немесе ).
2-мысал. А- нақты оң сандар жиыны болсын. Р қатынасы ретінде"", "", "=" қарастыруға болады.
Ескерте кетелік, Р бинарлы қатынасы жиынында анықталған болсын. Бұл қатынастың қасиеттерін матрицасы арқылы тексеруге болады:
1. P- рефлексивті болсын ,мұнда орнына бір немесе нөлдер белгіленген.
2. P- симметриялы болсын .
3. P- антисимметриялы немесе . Бұл қасиет матрицасындағы бас диагональдан басқа жердегі элементтері нөлге тең болады, бас диагональда да нөлдер болуы мүмкін екендігін көрсетеді.
4. P- транзитивті , яғни егер , , онда .
3-мысал. матрицасымен берілген Р қатынасының қасиеттерін қарастырайық. матрицасының бас диагоналінде бірлер тұрғандықтан, Р рефлексивті, яғни . матрицасы симметриялы емес, олай болса Р қатынасы да симметриялы емес.
.
Бұл матрица антисимметриялылықты тексеруге қажет. Бас диагональдан басқа жердегі элементтер нөлге тең емес болғандықтан, Р антисимметриялы емес. Келтірілген мысалдан антисимметриялық қасиет пен симметриялы емес қасиеттері әртүрлі екендігі көрінеді. Енді транзитивті қасиетіне тексерейік.

яғни , олай болса транзитивті емес [4, 93 бет], [6, 13 бет].
Егер P қатынасы рефлексивті, симметриялы және транзитивті болса, онда ол эквивалентті қатынас деп аталады. Эквиваленттілікті Е немесе ~ (тильда) символымен белгілейді: , .
4-мысал. теңдік қатынасы кез келген А жиынында эквивалентті қатынас болады, себебі:
а) рефлексивті ;
ә) симметриялы , ;
б) транзитивті , .
5-мысал. Үшбұрыштар жиынын алсақ, ұқсастық қатынасы эквивалентті болады.
А жиынындағы Е эквиваленттілік қатынасы осы А жиынын элементтері өзара эквивалентті ішкі жиындарға бөледі. Мұндай ішкі жиындар эквиваленттілік класы деп аталады.
Е - А жиынындағы эквиваленттілік қатынасы және болсын. А жиынының х-ке эквивалентті элементтердің ішкі жиыны х элементінің эквиваленттілік класы деп аталады. Е(х) немесе деп белгіленеді
Эквивалент кластар жиыны А жиынының Е эквивалентке қатысты
фактор жиыны деп аталады, деп белгіленеді: . Фактор жиын булеанның ішкі жиыны болып табылады.
6-мысал. А - АЭжБИ студенттер жиыны, Е - студенттік группаға тиесілік қатынасы. Эквиваленттілік класы - бір группадағы студенттер жиыны. Е - ге қатысты АЭжБИ студенттер жиынындағы фактор жиын АЭжБИ студенттік топтар жиыны болады.
Анықтама бойынша:
а) эквиваленттілік класының кез келген элементі эквиваленттілік класын туындайды, яғни егер , онда ;
ә) әрбір эквиваленттілік класта кем дегенде бір элемент бар, яғни
;
б) ешқандай элемент екі әртүрлі класқа бірден тиесілі бола алмайды
, онда
Бөлікше анықтамасын еске түсірсек, онда
Теорема. фактор-жиын А жиынының бөлікшесі болып табылады. Керісінше, егер A - А жиынының қандай-да бір бөлікшесі, онда оған сәйкес Е эквиваленттілік қатынасын орнатуға болады.
Сонымен, А жиынындағы барлық эквиваленттік қатынасы мен А-дағы барлық бөлікшелер арасында өзара бірмәнді сәйкестік орнатуға болады.
7-мысал. жиыны берілсін.
A - бөлікшесі, ал -
осы бөлікшеге сәйкес эквиваленттік қатынас болады.
8-мысал. жиыны берілсін. және
болсын:
а) қатынасының эквивалентті қатынас болатындығын көрсетейік, яғни бұл қасиет рефлексивті, симметриялы және транзитивті қасиеттерге ие болатын-дығын тексереміз. Ол үшін
қатынасының матрицасын құрамыз
.
1) - рефлексивті, себебі матрицадағы бас диагональда бірлер тұр;
2) - симметриялы, себебі ;
3)
.
Сондықтан - транзитивті. Олай болса, - эквивалентті қатынас;
ә) эквиваленттілік класы мен барлық эквиваленттілік кластарының жиынын (яғни фактор-жиынын құрайық).

Сонымен үш эквиваленттілік класы бар

Сондықтан фактор-жиын . Сонымен берілген эквивалентті қатынасқа сәйкес А жиынының бөлікшесін алдық.
Бұл мысалдан:
а) эквиваленттілік класының кез келген элементінен эквиваленттілік класс туындайды (яғни );
ә) әрбір эквиваленттілік класында ең болмағанда бір элемент болу керек (яғни );
б) әр элемент тек бір ғана класқа тиесілі болу керек ().

1.4 Реттік қатынастар
Егер А жиынында Р қатынасы антисимметриялы және транзитивті болса, ол реттік қатынас деп аталады. Реттік қатынас рефлексивті болса, онда ол дербес реттілік (қатаң емес, мысалы ), ал антирефлексивтік қосылса, онда қатаң реттілік (қатаң, мысалы, ) деп аталады.
А жиынында реттік қатынас берілген болсын. Егер осы жиынның екі , элементтері үшін немесе орындалса, онда бұл элементтер салыстырмалы деп аталады, қарсы жағдайда салыстырылмайтын деп аталады.
Егер А жиынының кез келген екі элементі салыстырылмалы болса, онда осы жиындағы дербес реттілік сызықты (толық, тізбектей) деп аталады.
Дербес (сызықты) реттілік анықталған жиын дербес реттелген жиын (сызықты реттелген жиын) деп аталып, д.р.ж. (с.р.ж) деп белгіленеді.
1-мысал. жиыны берілсін:
а) - дербес реттілік қатынас.
Ол сызықты болмайды, себебі және , және арасында қатынас жоқ, салыстыруға келмейді.

1.11 Сурет

Оның матрицасы - бірлік матрица, рефлексивті (тепе-тең);
ә) P(A)Ø,.
Осы P(A) жиынында келесі қатынасты анықтайық:
=
P(A) - дербес реттелген жиын болады, бірақ сызықты реттілік емес, себебі салыстырмалы, ал және салыстырылмайтын элементтер;
б) сызықты реттелген жиын - бұл N, Z, Q, R жиындары (кәдімгі рет бойынша алынған "", "", "="...). Бұл сызықты реттелген жиынды N,, (Z, ) жұбы ретінде белгілейді.
Сызықты реттелген жиынды бірінші элементіне қарай бөлуге болады. Мысалы, егер сызықты реттелген жиын ретінде натурал және бүтін сандар жиынын алатын болсақ, онда натурал сандарда кіші элемент бар, ал бүтін сандарда жоқ.
Егер реттелген А жиынында орындалатын х элементі болмаса, элементі минималды (максималды) деп аталады.
Егер сызықты реттелген жиынның бос емес ішкі жиынында минимальды элемент бар болса, онда ол әбден реттелген деп аталады.
2-мысал. әбден реттелген жиын.
3-мысал. әбден реттелген жиын, себебі , бірақ -де ең кіші элемент жоқ.

Лексикографиктік реттілік
Лексикографиктік реттілікте сөздіктегі сөздердің реттелуі негізге алынған. Мысалы арман сөзі болат сөзінен бұрын, себебі алфавитте а әріпі б әріпінен бұрын орналасқан.
бос емес символдар жиыны берілген, ол алфавит деп аталады. Х-тен алынған бірінен соң бірі жазылған символдардың ақырлы жиынтығы сөздер деп аталады, мысалы, . сөзінің элементі оның ші координатасы, ал оның ұзындығы деп аталады. W(x) - Х алфавитіндегі сөздер жиыны.
X-тегі реттік қатынас болсын, яғни - реттелген жиыны берілген. W(x) жиынындағы лексикографиктік рет деп деп белгіленеді) келесі ережеге сүйенетін қатынас айтылады
және немесе ) және
үшін шарты орындалады.
.5 Функция. Функционалдық қатынас
Анықтама. Егер
а) ;
ә)
шарттары орындалса, онда А жиынынан В жиынына бинарлы қатынасы функционалдық (функция) деп аталады.
(яғни бұл бинарлық қатынаста бірінші элементі бірдей, ал екінші элементі әртүрлі екі жұп болмайды немесе функция).
Егер орнына орындалса, онда дербес функция деп аталады. А-дан В-ға бейнеленетін функциясы былай белгіленеді: немесе .
Егер болса, онда функциясының мәні, ал аргументі деп аталады) немесе ( функциясы элементіне элементін сәйкес қояды).
Мысалы:
а) функция;
ә) функция емес, себебі элементіне элементтері сәйкес келеді;
б) функция, мұндағы ;
в) функция емес.
Анықтама. болсын.
а) егер қатынасы дербес функция болса, яғни кез-келген элементтері үшін -ден екені шығатын болса (немесе және , онда функциясы инъективті (инъекция немесе әртүрлі мәнді) деп аталады;

Инъекция (сюръекция емес)
1.12 Сурет
ә) егер болса, онда функциясы сюръективті (сюръекция) деп аталады. сюръекция;

Сюръекция (инъекция емес)
1.13 Сурет
б) егер функциясы әрі инъективті, әрі суръективті болса, яғни А жиынының әрбір элементіне В жиынының тек бір элементі және В жиынының әр элементіне А жиынының кейбір элементі сәйкес келетін болса, онда ол биективті (биекция немесе өзара бірмәнді) деп аталады.
Биекция деп белгіленеді.
1-мысал.

қатынас емес инъекция (сюръекция емес)

сюръекция (инъекция емес) биекция

1.14 Сурет

2-мысал.
функцияларын қарастырайық.
1.15 Сурет
биективті;
инъективті, сюръекция емес;
сюръекция, инъекция емес;
инъекция емес, сюръекция емес.
Жиындар қуаты
Жиындар қуаты түсінігі элементтер санына байланысты жиындарды салыстыру барысында пайда болады.
Анықтама. Егер биъекциясы бар болса, онда А және В жиындары эквивалентті деп аталады (А~B - деп белгіленеді).
Сонымен ақырлы элементтер саны бар екі жиынның элементтер саны тең болса, олар эквивалентті болады. Ал егер элементтер саны шексіз көп болса, онда жиынның қуаты деген түсінік пайда болады.
Анықтама. А жиынының қуаты деп А жиынына эквивалентті жиындар класы айтылады, - деп белгіленеді:
а) егер А жиыны ақырлы элементтен тұратын жиын болса, болады. А және В эквивалентті жиындар қуаттары бірдей болып есептеледі;
ә) егер А элементтер саны ақырсыз жиын және N- натурал сандар жиынына эквивалентті болса, онда А - санамалы (санаулы) жиын деп аталады (санамалы жиынның элементтерін нөмірлеуге болады). А жиыны мен N натурал сандар жиынымен өзара бірмәнді байланыс орнатуға болса, онда А санамалы жиын деп аталады;
б) натурал сандар жиынымен өзара бірмәнді сәйкестік орнатылмайтын ақырсыз жиындар санамалы емес жиындар деп аталады.
Мысалы, Кантор теоремасы бойынша [0,1] кесіндісінде нақты сандар жиыны санамалы емес. Мұндай жиындар қуатын континуум деп аталады (С деп белгіленеді). Ал жиынның өзін континуалды немесе континуум деп атайды. Сонымен континуалды жиын қуаты , яғни санамалы жиынның барлық ішкі жиындарының жиынының қуатына тең.
Жалпы кез келген жиыны үшін, оның қуаты . (U) - жиынның ішкі жиындарынан тұратын жиын немесе булеан.
1-мысал. Санамалы жиындар:
а) бүтін сандар жиыны (оң және теріс);
ә) рационал сандар жиыны (Q);
б) натурал сандар жиынының (N) кез келген ішкі жиындары;
в) санамалы.
2-мысал. Континуалды жиындар:
а) нақты сандар жиыны N (сан өсіндегі нүктелер жиыны);
ә) кеңістіктегі (жазықтықтағы) бүкіл нүктелер жиыны;
б) санамалы жиынның ішкі жиындарының жиыны санамалы жиын).
Жиындар теориясында кез келген қуатты жиын үшін оның ішкі жиындарынан тұратын жиынның қуаты әлдеқайда жоғары. Сондықтан ең жоғары (ең көп, максималды) қуатты жиын болмайды. Жиынның қуатына жаңа көзқараспен қарауға болады, оны қандай да бір жаңа объект ретінде қарастырсақ болады, оны кардинал немесе кардиналды сан деп атайды.

3-мысал.
а) кез келген натурал сан n (n элементтен тұратын ақырлы жиынның қуаты);
ә) және т.б.
2 Математикалық логика элементтері
Математикалық логика екі негізгі бөлімнен тұрады: айтылымдар логикасы және предикаттар логикасы.
Анықтама. Айтылым деп дәл осы уақытта оның ақиқаттығы немесе жалғандығы белгілі хабарлы сөйлемді айтады.
Мысалы. Екі қосу екі тең төртке (хабарлы сөйлем, ақиқат). Манат - Қазақстанның валютасы (хабарлы сөйлем, жалған).
Анықтама. Қарапайым айтылым деп бөліктелмейтін, бүтін бір ұғымды айтады (жиынның элементтері сияқты). Айтылымдарды А, В, С, ... , Р, Q, ... бас әріптермен белгілейді.
Анықтама. Күрделі айтылымдар деп логикалық байланыс (операциялар, қисаптар) арқылы байланысқан қарапайым айтылымдардан тұратын сөйлемді айтады.
2.1 Негізгі логикалық операциялар (қисаптар)
2.1.1 Конъюкция (және операциясы, логикалық көбейту), белгіленуі ("Р және Q" деп оқылады).
P және Q айтылымдардың конъюкциясы деп тек екеуі де ақиқат болған жағдайда ақиқат болатын, қалған жағдайда жалған болатын айтылымды айтады.
2.1.2 Дизъюнкция (немесе операциясы, логикалық қосынды), белгіленуі ("Р немесе Q" деп оқылынады). Екеуі де жалған болған жағдайда жалған болып есептелетін, қалған жағдайда ақиқат айтылым.
2.1.3 Теріске шығару (инверсия, бірақ), белгіленуі (" емес", " теріс" деп оқылынады). Р айтылымның керісі деп Р жалған болғанда ақиқат болатын, ал Р ақиқат болғанда жалған болатын айтылымды айтады.
2.1.4 Импликация (логикалық салдар), белгіленуі ("егер Р болса, онда Q" немесе "Р-ның салдары Q", "Р-дан Q шығады" деп оқылады).
Р ақиқат, ал Q жалған болғанда жалған болатын айтылым. Р айтылымы импликацияның бастамасы, ал Q - қорытындысы деп аталады.
2.1.5 Эквиваленттілік (эквиваленция, бірдей мәнді), белгіленуі ("Р айтылымы Q айтылымына эквивалентті", "Р , тек егер Q" , "Р мен Q бірмәнді" деп оқылынады). Р мен Q ақиқат мәндері сәйкес келгенде ақиқат болатын, қарсы жағдайда жалған болатын айтылымдарды эквивалентті айтылымдар деп атайды.
2.2 Логика алгебрасы
Логика алгебрасын қолданып, айтылымдар логикасының мазмұнын қарастырайық. Айта кетелік, логика алгебрасында логикалық формулалар алгебралық өрнектер ретінде қарастырылады, оларды логикалық заңдарға бағынатын ережелер бойынша түрлендіруге болады. Логика алгебрасы математикалық логиканың бір бөлігі ретінде логикалық айтылымдардың (формулалардың) және алгебралық әдістер көмегімен олардың ақиқаттығын анықтайды.
Р айтылымына х логикалық айнымалысын сәйкес қоямыз. Егер Р ақиқат болса, онда х айнымалысы 1 мәнін, ал Р жалған болса, онда 0 мәнін қабылдайды.
Анықтама-1. Кез келген айнымалы формула болып табылады (ең кішкентай формула - атом, атомарлы формула деп те аталады).
Анықтама-2. Егер және формулалар болса, онда өрнектері де формула болады.
Анықтама. Анықтама-1 және анықтама-2 бойынша құрылған формулалардан өзге формула жоқ.
Егер формуласы жиынына тиісті логикалық айнымалылардан құралған болса, онда деп жазамыз. Логикалық операциялар нәтижесі ақиқат кестесі арқылы беріледі. Мысалы теріске шығару операциясы
2.1 К е с т е

0
1
1
0

Қалған логикалық операциялар анықтамасын төменгі кесте арқылы еске түсіруге болады.
2.2 К е с т е

0
0
0
0
1
1
0
1
0
1
1
0
1
0
0
1
0
0
1
1
1
1
1
1
Бұл кесте арқылы кез келген формуланың ақиқаттығын анықтай аламыз, яғни олар үшін ақиқат кестесін құруға болады.
1-мысал.
формуласының ақиқаттық кестесі
2.3 К е с т е

у

0
0
0
1
1
0
1
1
1
0
0
1
1
1
1
1
1
1
0
1
0
1
0
1
1
1
1
0
1
1
1
0
1
1
1
1
1
0
0
0
1
0
0
1
0
1
0
1
0
1
1
0
0
0
1
1
0
1
0
1
0
0
0
1
1
1
1
0
1
0
0
0

2-мысал.
формуласының ақиқаттық кестесі
2.4 К е с т е

у

0
0
0
1
1
1
1
0
0
1
1
1
1
1
0
1
0
1
0
1
1
0
1
1
1
0
1
1
1
0
0
0
1
1
1
1
0
1
0
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
Бастапқы бес негізгі логикалық операциядан басқа тағы үш логикалық операция бар:
а) Шеффер штрихы (антиконъюнкция), белгіленуі .
немесе ;
ә) Пирс стрелкасы (антидизъюнкция), белгіленуі .
немесе ;
б) сақиналы қосынды (логикалық қосынды, екі модуль бойынша қосынды), белгіленуі .
немесе .
Анықтамаға сүйеніп, бұл операциялардың ақиқаттық кестесін құруға болады
2.5 К е с т е

0
0
1
1
0
0
1
1
0
1
1
0
1
0
1
1
1
0
0
0
Математикада өрнекті түрлендіргенде алдымен көбейту, содан соң қосу немесе азайту амалдарын орындаған сияқты, логика алгебрасында да, әр операцияның өз кезегі бар. Ол үшін төменгі келісімдерді келтірейік:
а) сыртқы жақшаларды жазбауға болады;
Мысалы. орнына жазуға болады;
ә) - логикалық операциялар жиынында күштірек немесе күштері басым және ~ күштері бірдей транзитивтік қатынастарын келесі сұлба бойынша енгізейік.

2.1 Сурет
Бұл келісімдерге сәйкес амалдарды орындау жақша жоқ жерде алдымен күштірек байланыстан басталып, әлсізден аяқталады, ал күші бірдей байланыстар үшін амалдарды солдан оңға қарай орындау керек.
Келесі формулаларда амалдар орындау ретіне сай жақша қою керек.
3-мысал. .
Жауабы: .
4-мысал. .
Жауабы: .
5-мысал. өрнегінде жақшаны алып тастауға болмайды, себебі біздің келісім бойынша өрнегіне формуласы сәйкес келер еді.
Логика алгебрасының функциялары
Әрбір формуланы логикалық айнымалылы логикалық функция деп түсінуге болады, ол функция тек екі мәнді 0 және 1-ді қабылдай алады.
Анықтама. n айнымалылы логика алгебрасының функциясы деп, кез келген нөлдер мен бірлердің жиынтығына мәнін сәйкес қоятын кез келген функцияны айтады, яғни .
Логика алгебрасының функциясы буль функциясы, екілік функция немесе ауыстырып-қосқыш функция деп аталып, деп белгіленеді. Себебі бұл функциялар белгілі бір қондырғының кіру сигналдарын шығу сигналдарына түрлендіруін сипаттайды. Қондырғының n кіру (ену) жолы бар, оларға ток берілуі де, берілмеуі де мүмкін және осы қондырғыда бір шығу жолы бар, оған да ток берілуі, берілмеуі кірер жолда токтың берілуіне байланысты.

2.2 Сурет
Бұл жағдайда i-нші кіру жолына ток берілгенде мәнін, ал берілмегенде мәнін қабылдайды. (мұнда ) мәнін, ток шығу жолынан өткенде, ал ток өтпеген жағдайда қабылдайды.
Мысалға, функциясы екі кіру жолы және бір шығу жолы бар қондырғыдағы конъюнкция операциясын көрсетеді.

2.3 Сурет
Бұл жағдайда егер екі кіру мәні де бірге тең болса, шығу мәні де бірге тең болады.
Логикалық функциялардың берілу жолдары
1. Ақиқаттық кестесі арқылы.
Кестенің сол жағында аргументтерінің қабылдайтын мәндері, ал оң жағында оған сәйкес мәні орналасады.
2. Функцияны 0 мәнін (нөлдік жиынтық) қабылдайтын барлық жиынтықтарды тізу және сол сияқты 1 мәнін (бірлік жиынтық) қабылдайтын жиынтықтарды тізу арқылы беруге болады.
3. Функцияның берілу тәсілі ретінде формуланы қарастыруға болады.
Дауыс беру мысалын қарастырайық. Үш мүшеден тұратын комитет қандай да бір резолюцияның қабылдау барысын қадағалайтын құрылғыны қарастырайық. Комитеттің әрбір мүшесі резолюцияны қолдайтын болса, өз кнопкасын басады, егер көпшілігі қолдаса, онда резолюция қабылданады. Бұны қондырғы өзіне белгілейді.
Сонымен қондырғыны функциясы іске асырады, ақиқаттық кестесі мына түрде беріледі.
2.4 К е с т е
x
y
z

0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
Көпшілік дауыс 2 немесе 3 болғанда, қабылданады. Бұл функцияны нөлдік жиынтықпен қабылдауға болады: немесе бірлік жиынтық:
Анықтама. функциясының мәндерінің векторы деп -тің барлық мәндерінің реттелген жиынтығы айтылады, ал мәндер аргумент жиынынан () лексикографиктік тәртіппен реттеледі.
Жоғарыдағы мысалда мәндерінің векторы (0,0,0,1,0,1,1,1) жиынтығы болады.
Е с к е р т у - Лексико-графиктік реттілік екі саннан тұратын жиынтықтың өсу ретіне сәйкес келеді. Графтар теориясындағы ағаш ұғымын қолданатын болсақ, 0 және 1 әртүрлі жиынтықтарын келесі жолмен алуға болады: бұл ағаштың әрбір қабатында ұзындығы n болатын () әртүрлі нөлдер мен бірлердің жиынтығы орналасады. І қабатында (жоғарыда) - n; ІІ қабатында - n; ІІІ қабатында - n, ..., т.б.

2.4 Сурет

Сонымен, 0 және 1-ден тұратын барлық мүмкін жиынтықтар n айнымалылы функцияның саны тең, яғни бір айнымалылы функция үшін 2, екі айнымалылы функция үшін , т.б. Ал барлық мүмкін болатын әртүрлі n функциялардың саны болғанда, 0 мен 1-дің орналасу жағдайларының санына тең, яғни .
Егер деп функцияның аргументтерінің мәндерінің жиынын белгілесек, ал барлық аргументті функциялар болса, онда бұл жиындардың қуаты . Сонымен тез өседі.
, , , т.б.
Анықтама. Егер , онда функциясы және функцияларының суперпозициясы деп аталады,
Мысалы: функциясы және , , функцияларының суперпозициясы.
Анықтама. функциясы нөл мен бірлердің барлық жиынтығында 1 мәнін (0 мәнін) қабылдаса, яғни , онда ол 1 константасы (0 константасы) деп аталады.
Формулалар эквиваленттігі.
Логика алгебрасының негізгі эквиваленттік қатынастары
Жоғарыдағы 1-мысалдағы және формулаларының ақиқаттық кестелері бірдей болуы мүмкін. Бұл жағдайда эквивалентті формулалар ұғымы пайда болады.
Анықтама. Егер , формулаларының ақиқаттық кестелері бірдей болса, онда олар эквивалентті (күші бірдей) деп аталып, деп белгіленеді.
Мысалы. формулалары үшін ақиқаттық кестесін құрайық.

2.5 К е с т е
x
y

0
0
1
1
1
1
0
1
0
1
1
1
1
0
1
0
0
0
1
1
0
0
1
1
Ақиқаттық кестесі бірдей, сондықтан

Бұл мысалда формулалар эквиваленттілігін кәдімгі стандарт әдіспен тексердік:
а) әрбір формулаға ақиқаттық кестесін құрдық;
ә) айнымалының мәндерінің жиынтығы бойынша кестедегі нәтижелерді
салыстырдық.
Басқа әдіс - эквивалентті түрлендірулер. Мұнда эквивалент қатынастар (заңдар) мен ауыстыру ережелері қолданылады.
2.6 К е с т е - Негізгі эквиваленттік қатынастар (заңдар)
1
Орын ауыс-
тырымдылық
(коммутативтік)

2
Терімділік
(ассоциативтік)

3
Үлестірімділік
(дистрибутивтік)

4
Идемпотенттік

5
Сіңіру заңы

6
Де-Морган заңы

7
Екі рет теріске шығару
8
Константалардың қасиеті

9
- қарама-қайшылық заңы
- шығып қалған үшінші заңы

2.7 К е с т е - Тағы да басқа керекті эквиваленттік қатынастар
10
Жапсыру заңы

10 а
Тарқату

11
Жалпыланған жапсыру

12

13

14

15

16

Анықтама. Егер формуласы 1 мәнін (0 мәнін) қабылдайтындай айнымалы мәндерінің жиынтығы табылатын болса, онда формуласы орындалатын (теріске шығарылатын) деп аталады.
Мысалы. формуласы бір мезгілде орындалатын (1 және теріске шығарылатын болады.
Анықтама. Егер формуласы айнымалы мәндерінің барлық жиынтығында 1 мәнін (сәйкес 0 мәнін) қабылдаса (яғни 1 константа немесе 0 константа болса), онда формуласы тепе-тең ақиқат (жалпы мәнді) немесе тавтология (жалпы жалған, қарама-қайшылық) деп аталады.
Мысалы. формуласы - тепе-тең ақиқат,
формуласы - жалпы жалған болады, себебі
2.8 К е с т е
х

х
х
0
1
1
0
1
0
1
0
Егер тепе-тең ақиқат болса, онда деп белгілейміз.
Егер жалпы жалған болса, онда деп белгілейміз.
Е с к е р т у л е р
1 Егер формуласы тепе-тең ақиқат болса ғана, онда ол тепе-тең жалған болады .
2 Егер формуласы тепе-тең ақиқат болмаса ғана, оны теріске шығаруға болады .
3 Егер формуласы тепе-тең жалған болмаса ғана, ол орындалатын болады .
4 Егер тепе-тең ақиқат, тепе-тең жалған болса, онда кез-келген үшін келесі эквиваленттіктер орындалады

2.3 Буль алгебрасы
Алдыңғы тақырыпта көрсетілгендей, бір ғана логикалық функция әртүрлі логикалық операциялардың жиынтығы арқылы беріле алады. Мысалы .
Анықтама. Егер кез келген логикалық функция сигмадағы () функциялардың суперпозициясы болса, онда сигма () логикалық функциялардың жүйесі (жиынтығы) функционалды толық жүйе (немесе базис) деп аталады.
Мысалы логикалық функциялардың толық жүйесі:
т.б.
Осылардың ішінде жиі қолданылатын базис болып табылады.
Айнымалыдан, жақшадан басқа конъюнкция, дизъюнкция және теріске шығару таңбаларынан тұратын формулалар буль формулалары деп аталады.
Теорема. Кез келген логикалық функция буль формуласы бола алады.
Бұдан жүйесінің функционалды толықтығы шығады. Сондықтан қандай-да бір операциялардың жиынтығының толықтығын дәлелдеу үшін операциялар жиынтығы арқылы конъюнкция, дизъюнкция және теріске шығару операцияларын өрнектеуге болады. Бұл тұжырымды жалпыласақ,
Теорема. Егер функционалдық толық жүйесінің барлық функцияларын -дағы формулалармен өрнектеуге болса, онда -да функционалдық толық жүйе болады.
1-мысал. және жүйелері, базисі берілген. , функционалды толық болады, себебі олардың әрқайсысындағы -де жетпей тұрған операцияны қалған екеуі арқылы өрнектеуге болады (-де , -де жетпей тұр).
Де Морган заңыүшін
Де Морган заңыүшін
... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.