Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану

1. 
   0 және 1 функциялары сәйкесінше нөлдік және бірлік функция деп аталады.
   

3. функциясын х – ті жоққа шығару немесе терістеу деп атайды, деп белгілейміз.

4. f₃ функциясын x₁ мен x₂-нің конъюнкциясы немесе логикалық көбейтіндісі деп атайды, оны x₁ ∩ x₂ деп белгілейміз.

5. f₄ функциясын x₁ мен x₂-нің дезъюнкциясы немесе логикалық қосындысы деп атайды, оны x₁ U x₂ деп белгілейміз.

6. f₅ функциясын x₁ мен x₂-нің модуль екі бойынша қосындысы деп атайды, оны x₁ x₂ деп белгілейміз.

7. f ₆ функциясын x₁ мен x₂-нің эквиваленциясы деп атайды, оны x₁ ↔ x₂ деп белгілейміз.

8. f ₇ функциясын x₁ мен x₂-нің импликациясы деп атайды, оны x_{1 →} x₂ деп белгілейміз.

9.f ₈ функциясын x₁ мен x₂-нің Шеффер штрихы деп атайды, оны x₁ | x₂ деп белгілейміз. Бұл функция антиконъюнкция деп те аталады.

10. f ₉ функциясын x₁ мен x₂-нің Пирс бағыттаушысы деп атайды, оны x₁ ↓ x₂ деп белгілейміз. Бұл функция антидизъюнкция деп те аталады.
Бақылау сұрақтары:

1. 
   Бульдік функция деген қандай функция?
   
2. 
   Құрама дегеніміз не?
   
3. 
   Логикалық функцияларға қолданылатын амалдарды атаңыз.
   
4. 
   Конъюнкция дегеніміз не?
   
5. 
   Дезъюнкция дегеніміз не?
   
6. 
   Шеффер штрихы дегеніміз не?
   

1. Графтың негізгі анықтамалары

2. Графтың инциденттік матрицасы

3. Графтың түрлері

1. Графтың негізгі анықтамалары

Анықтама. Граф деп – бейнеленген заттардың екі – екіден жұпталып келген заттардың бір – бірімен қатынасының жүйесін айтады. Графтармен коммуникация жолдарын қолайлы бейнелейді, үздіксіз емес көп қадамды процестерде («бинарлық қатынастардың жүйелерін, химиялық формулалардың құрылымында, тағы басқа әр түрлі схемалардың диаграммаларында») қолданылады.

Граф G - жүйе G(V, E, Г) ∙V ={V}жиынының элементі граф төбесінен тұрады да, E={e} қыры болып келген бейнелеуді көрсетеді. Г: Е→V² егер әрбір элементтің е Е реттелген санға сәйкес реттелген екі элементті

V₁, V₂ V– ның қырларының соңы сәйкес келеді.

V E (V және Eжиындарының бірігуі) - графтың көптеген элементтерінен тұрады да, ал V ∩E = ø (E мен V қиылысуы) құр жиынды көрсетеді. Г бейнесі әрбір соңғы қырының инцинденттігін анықтайды.

G=(V, E, Г) үшін ең қысқа G=(V, E). Мұнда инцинденттілігі көрсетілмеген. Олар контекстпен анықталады. Элементтерінің санына байланысты шекті және шексіз болып бөлінеді. Біз тек ғана шекті графпен танысамыз.

Егер r(e)=( V₁, V₂ – екі – екіден таралып реттелген.

(V₁, V₂) ≠ (V₂, V₁) V₁=V₂ болғанда, онда e бағытталған доғал болады да, шыққан V₁ - төбесі e доғасының басы, кіретін V₂ төбесі e доғасының соңы деп аталады.

Егер r(e)=( V₁, V₂ – жұбы ретсіз болса, онда e қыры бағытсыз деп аталады.

Кез – келген G графқа сәйкестендіріліп алынған бағытсыз граф G ,V және E жиындарынан және инцинденттіктерінен тұрады, бірақ барлық парлары ретсіз болады.

Төбелері бірде бір қырымен инциндентті болмаса, онда ондай қырды бөлектенген қыр деп атаймыз, ал төбесі бір қырымен инциндентті болса, онда оны аяқталған қыр, не ілінген қыр деп атаймыз. Қырдың басы мен соңы біріккен болса, оны ілмек деп атаймыз.

Егер екі төбе бір қырға инциндентті болса, ондай төбелерді көршілес, не

сыбайлас төбелер деп атайды. Егер екі қыр бір төбеге инциндентті болса, онда ондай қырды сыбайлас деп атаймыз. Қырға сәйкес қойылған екі төбені еселік, не параллель төбелер деп атаймыз.

Әртүрлі есептер үшін бір тек сол затқа графтың әртүрлі салыстыруы қажет. Мысалы: жолдар тармағының үзіндісі ретсіз қырмен көрсетіледі де, бір–бірімен қатынастарының аяқталуын бейнелейді (қоныстанған орындарымен, қала көшелерімен, көшенің түйіскен жерімен құралдарындағы бір жақты, не екі жақты қозғалыстар). Бірнеше доғаларымен бөлектеген әрбір бірнеше қозғалысты – қырға қосымша жазылған сандар, оның ұзындығын, енін, енкіштігін және сандар не басқа сипаттамасын көрсетеді. Қандай графтар ажыратылатын және ажыратылмайтын болып бөлінуін анықтау өте қажет болып табылады, оны тіпті графтардың изоморфизм ұғымымен байланыстырады. Өзара сақталып инцинденттік пайда болған бірімен – бірінің мәнді сәйкес бейнелеуін екі графтың G₁=(V₁, E₁, Г₁) және G₂=(V₂, E₂, Г₂) изоморфизмі деп атаймыз да, оны былай белгілейміз f :V₁ ↔ V₂ және g:E₁ ↔ E₂ кез келген е₁ Е₁ теңдікке r₁(е₁)=(V₁,V₂) → r₂(gе₂)=(fV₁,fV₂).

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

Графтарды бірнеше жолдармен беруге болады. Шекті графты оның қырларының тізімінің санын көрсетіп санау арқылы, оған қоса жеке тұрған төбенің тізімін көрсету.