3 Тақырып. Бульдік алгебра

3.1 Бульдік алгебра және компьютердің логикалық схемасы. Графтар және ағаштар.

ЭЕМ немесе есептеу ортасын тұтасымен алғанда кез келген дискретті есептеу құрылғыларының негізін құрайтын логикалық схемалардың құрылымды – функционалды сипатталуы үшін машина логикасын математикалық әдіспен зерттеу ретінде 1854 жылы Дж.Буль құрған бульдік алгебра аппараты қолданылады. Бульдік алгебраны қолдану схемалармен немесе логикалық диаграммалармен амалдар қолданғаннан көрі, бульдік өрнектермен ыңғайлы

жұмыс жасауға мүмкіндік беріп қана қоймай, сонымен қатар формальді деңгейде эквивалентті түрлендіру және негізгі теоремалар жолымен кез келген

мақсаттағы экономикалық және техникалық түрде өте дамыған электрондық құрылғыларды құруға мүмкіндік бере отырып, оларды жеңілдетеді. Осыған байланысты, микропроцессорларды қолданылуының біріне аппараттық логиканы программалыққа ауыстыру жатады, сондықтан бульдік алгебра амалдары сонымен қатар, микро-ЭВМ программалық қамсыздандыруында да

жиі кездеседі. Бульдік алгебра аппараттарының және онымен сипатталатын логикалық схемалардың утилитарлық мәні сонымен қатар, көрсетілген аппаратқа негізделетін ақырлы – автономдытүсінуге негізделгенпрограммалық қамсызданудың құрылымдық қателерін автоматты түрде табу әдістемелерінің болуына да қатысты. Қазіргі заманғы ЕТ құрылымдық-функционалдық архитектурасын талдау, өңдеу және сипаттаудың негізгі құралы бола отырып,бульдік алгебра “компьютерлік информатика” курсының, сонымен қатар есептеуіш ғылымдардың бірқатар тарауларының негізгі құрылымдық бөлігі болып табылады.

Жалпы, кез келген формальды математикалық жүйе мына жиындардан:элементтерден,оларға қолданылатын амаладардан жәнеаксиомалардан тұрады. Есептеуіш құрылғылар схемаларын шартты түрде үш топқа бөлуге болады: орындаушы, ақпараттық және басқарушы. Біріншісі бинарлы түрде

берілген ақпаратты өңдеуді жүргізеді; екіншсі бинарлы түрдегі ақпаратты беру үшін қолданылады; үшіншісі басқарушы функцияларды орындайды. Барлық жағдайларда да, негізінен, логикалық схеманың қандай да бір нүктесінде әртүрлі деңгейлі екі сигнал пайда болады. Демек, сигналдар бинарлы символдармен {0,1} немесе логикалық мәндермен {Ақиқат (True), Жалған (False)} берілуі үмкін. Сондықтан, бульдік алгебраның B={0,1} элементтер жиыны бинарлы таңдалады; мұндай алгебра бинарлы немесе ажыратқышты

деп аталады. Оның элементтерін константа немесе логикалық 0 және 1 деп атайды; кей жағдайларда логикалық 0 және 1 бинарлы цифрлар сәйкес келеді, басқа жағдайларда оларға Жалған (False) және Ақиқат (True) логикалық мәндері сәйкес келеді. Логикалық схемаларды құрылымды-функционалды сипаттау үшін оның түйіндеріне сәйкесінше 0 және 1 мәндерін қабылдайтын, бульдік айнымалылар қойылады; бульдік айнымалыларды сипаттауүшін латын

алфавитін қолданамыз. Бульдік алгебраның элементтер жиынын анықтап алған соң, оған амалдар менпостулаттар (аксиомалар) жиынын беру қажет.

_{1 кесте}

Айнымалылар Негізгі логикалық амалдар

X Y {X· Y|X

_{және Y}}

{X+Y|X

_{немесе Y}}

{X`| емес

_X}

0	0	0	0	1
0	1	0	1	1
1	0	0	1	0
1	1	1	1	0
		(a)	(b)	(c)

Бірнеше бульдік амалдар бар, олардың ішінен тек үшеуі: ЖӘНЕ (AND),

НЕМЕСЕ (OR) және ЕМЕС (NOT) негізгі болып табылады, қалғандарын

осылардың негізінде алуға болады. ЖӘНЕ амалын логикалық көбейту немесеконъюнкция деп аталады, {· | және } көбейту таңбасымен белгіленеді және 1 (а) кестесімен анықталады. НЕМЕСЕ амалылын логикалық қосу немеседизъюнкция деп атайды, {+| немесе } таңбасымен және 1 (b) кестесімен анықталады. Және, ЕМЕС амалы логикалық терістеу немесе инверсия, деп аталады, {`| емес } таңбасымен және 1 (с) кестесімен анықталады; 1 кестесі бульдік алгебра аксомаларын (постулаттарын) береді. Сонымен, бульдік алгебра B={0,1} элементтер жиынынмен,1-кестеде берілген {ЖӘНЕ, НЕМЕСЕ,ЕМЕС} амалдарымен және аксиомалармен анықталады.

Бульдік алгебра логикалық өрнектермен немесе ақиқаттық кестесімен логикалық схемалар анализін жасап қана қоймай, сонымен қатар олардың синтезін де жасайды, яғни логикалық схеманың құрылымды-аналитикалық есептерін де шешеді. ЕТ құралдарын құру кезінде қолданылатынэлементар ЛС

вентилдер (gates) деп аталады; қазіргі уақытта негізіне қазіргі заманғы ЭЕМ жататын бірқатар базалық вентилдер бар; олардың кейбіреулері төменде қарастырылған. Логикалық амалдардың {ЖӘНЕ,НЕМЕСЕ,ЕМЕС} жиыныәмбебап (функционалды толық) болып табылатындықтан, яғни оның негізінде кез келген логикалық функцияны ұсынуға болатындықтан, оған сәйкес келетін вентильдер жиыны да әмбебап болып табылады. Базалық вентильдер негізінде (19) кез келген ЛС құрыла алады. Математикалық логикадан белгілі,

{ЖӘНЕ,НЕМЕСЕ,ЕМЕС} мен қатар функционалды толық болып негізгі амалдардың басқа да қарапайым жиындары табылады:

{ЖӘНЕ,ЕМЕС},{НЕМЕСЕ,ЕМЕС},{ЖӘНЕ-НЕМЕСЕ}(Шеффер штрихі),

{НЕМЕСЕ-ЕМЕС} (Пирс бағдаршасы) және т.б. Шынымен де, мысалыға

{ЖӘНЕ,ЕМЕС} редуцияланған жүйесі {X· Y,X+Y,X`} є {X· Y,(X`· Y`)`,X`}

болғандықтан, функционалды толық қасиетін жоғалтпайды. Элементар немесе базалық ЛС кескіндейтін схемаларды және олардың байланысын логикалық

диаграмма (ЛД) деп атайды; егер ЛД вентилдерден тұрса және онда кері

байланыс болмаса, онда оған сәйкес келетін ЛС комбинациондық деп атайды. Комбинацияланған ЛД және бульдік өрнектер арасындағы өзара бірыңғай сәйкестікке байланысты, соңғысы ЛД/ЛС анализа және/немесе синтезінде де қолданылады; соған орай, бульдік алгебра құрамындағы бульдік өрнектер қазіргі заманғы техникалық ғылымдардың көптеген салаларында кеңінен

қолданылады. Элементар вентильдің екеуі де әмбебап болып табылады, яғни олардың әрқайсысының негізінде {ЖӘНЕ,НЕМЕСЕ,ЕМЕС} кез келген базалық амалдар үшін ЛС ретінде де, сонымен қатар кез келген комбинациялық ЛС ретінде де жүзеге асыруға болады. Мұнда бірқатар күрделі құрылымдық есептерді шешуге болады: күрделілігі минимальді ЛС алу, элементар вентилдер жиыны берілген ЛС, вентильдердің тиімді топологиясы және т.б. Мұндай

есептерді шешу үшін миллиондаған элементар вентильдерден тұратын және күрделі топологиялы өте күрделі ЛС тиімді жасауға мүмкіндік беретін арнайы автоматтандырылған жобалау жүйесі (САПРлар). Логикалық вентильдер олар жүзеге асыратын амаладардан тәуелсіз бірдей элементтер, ең бастысы тоқ өтуінің транзистор-ажыратқышы негізінде құрылады.

Жоғарыда айтылып кеткендей, тізбектелген схема коммуникациялықтан жадының болуымен ерекшеленеді; оның негізгі элементіне триггерді – арнайы электрондық схеманы жатқызуға болады. Триггерлі схема деп екі шығыс сигналдардан {Q,Q`} тұратын арнайы ЛС (жоғарыда айтылған логикалық вентилдерде жүзеге асырылған) айтамыз. Сонымен қатар, шығыс Q-сигналақиқат болып табылады, ал Q`-сигнал - жалған немесе қосымша болады. Осы сигналдарға триггердің екі берік күйі сәйкес келеді: 1 (қондыру) және 0 (шығару). Кіріс сигналы әскрінен триггер дискретті түрде бір берік күйден екіншісіне өтеді және бұл кезде дискретті түрде оның шығыс сигналының дәрежесі өзгереді: жоғары (1) және төмен (0), оң логика кезінде. Триггерлер схемасы бірнеше типтерге бөлінеді: RS-, T-, D-, JK-триггер және т.б. Триггер күйі шығыс Q(Q`)-сигналмен анықталады, ал оның қызмет көрсету ережесі өту кестесімен беріледі. RS-триггер схемасы триггерлердің басқа түрін құруға негіз болып табылады.

Маңызды тізбектелінген схемалар ретінде санағыштарды, жылжыту регистрлерін, жады элементтерін және т.б. айтуға болады. Ақпаратты ЭЕМ-де өңдеу ЛС екі түрде: комбинацияланған және тізбектелген немесе автоматтардың қолданбалы теория терминдерінде - ЛС және шығу мен өту толық жүйелі элементар автоматтармен жүргізіледі.

Цифрлы есептеуіш құрылғыларын құруға арналған элемменттер жиыны

көп жағдайда функцияоналды артық болады, ол ЛС – ды қолданылатын элементтері бойынша үнемді болатындай етіп құруға мүмкіндік береді. Жиын базалық және қосымша логикалық амалдарды орындауға арналаған элементтерден тұрады. Физикалық түрде элементтер жартылайөткізгішті кристаллда сәйкес технологиямен құрылғанмикросхемаларды білдіреді. Элементтердің бірқатары күрделілігі бойынша әртүрлі: кіші дәрежелі интеграциялы (ИС), орташа (ОИС), үлкен (ҮИС) және өте үлкен (ӨҮИС) дәрежелі интеграциялы микросхемалардан тұрады. ИС түріндегі логикалық элементтер қолданылатын логикалық вентилдер жиынын құрады: AND,OR,NOT,AND-OD,OR-ELSE және т.б., сонымен қатар триггерлер. ОИС, ҮИС және ӨҮИС логикалық схемалар түйіндерді, тіпті тұтас ЭЕМ-дерді құрады.

Қазіргі заманғы ЭЕМ-дың техникалы-экономикалық көрсеткіштерінің артуы

ҮИС мен ӨҮИС қолданылуына байланысты. Микропроцессорлардың әмбебап қолданылуын құру ҮИС мен ӨҮИС қолданылуы мәселесін шешкенімен, ҮИС- ды электрондық схемалар құру мәселесін қалдырады.

Логика (бульдік) алгебрасының негізгі заңдары

1.Орнын ауыстыру заңы. Коммутативтік (лат. – айырбастау, қайта

^{айырбастау). X}₁ ^{ X}₂ ^{= X}₂ ^{ X}₁ ^X₁ ^{ X}₂ ^{= X}₂ ^{ X}₁

2. Үйлестіру заңы. Ассоциативтік (лат. – біріктіру).

^X₁ ^{ (X}₂ ^{ X}₃^{) = (X}₁ ^{ X}₂^{)  X}₃

^X₁ ^{ (X}₂ ^{ X}₃^{) = (X}₁ ^{ X}₂^{)  X}₃

3. Тарату заңы. Дистрибутивтік.

^X₁ ^{ (X}₂ ^{ X}₃^{) = (X}₁ ^{ X}₂^{)  (X}₁ ^{ X}₃⁾

X₁  (X₂ X₃) = (X₁ X₃) (X₁ X₃)

^{4. Жұту заңы. X}₁ ^{ (X}₁ ^X₂^{) = X}₁ ^X₁ ^(X₁ ^{ X}₂^{) = X}₁

^{5. Желімдеу заңы. X}₁^X₂ ^{ X}₁^X₂ ^{= X}₁ ^(X₁ ^{ X}₂^)(X₁ ^{ X}₂^{) = X}₁

6. Де Морган ережесі.

X₁ X₂ X₃ =X₁ X₂ X₃;X₁X₂X₃ =X₁ X₂ X₃

3.2-тақырып. Графтар және ағаштар. Логикалық схемалар және логикалық машиналар.

Графтар электр желілерінің және молекулалық құрылымдардың схемаларын салуда қолданылады. Қазіргі уақытта графтар теориясы бір жағынан таза математиканың бөлімдерінің бірі болса, екінші жағынан әр түрлі практикалық мақсаттарда сәйкестіктерді орнатуда, транспорттық есептерді шығаруда, мұнай құбырларын тиімді пайдалануда, тізбектік желілер туралы есептерде, программалауда қолданылады. Графтар теориясы енді ғылымның барлық салаларында қолданылатын болды: физикада, биологияда, химияда, лингвистикада, қоғамдық ғылымдарда, техникада және т.б. Сондай-ақ, теориялық-графтық моделдер коммуникациялық желілерді, ақпараттық жүйелерді, химиялық және генетикалық құрылымдарды зерттеулерде кең танымал.

Көптеген қолданбалы есептерде әр түрлі объектілер арасындағы байланыстар жиыны қарастырылады. Объектілер төбелер деп аталып нүктемен белгіленеді, ал төбелер арасындағы байланыс доға деп аталады және сәйкес нүктелер арасындағы стрелкамен белгіленеді. Осындай жүйелер графты құрайды.

Ағаштар, бағытталмаған және бағытталған графтар. Граф нүктелер мен

сызықтардың жиынтығы. Нұктелер графтың шыңы (төбесі), сызық қабырғасы (қыры) болады. Егер қыр екі төбені байланыстырса, онда оларды инцидентті, ал шың қабырғамен байланысса аралас деп аттайды.

Граф G = (V, Е) V және Е жиындары жұбымен беріледі. Бірінші жиын элементтері v1, v2,..., vM графтың шыңы деп аталады ал (графикалық көріністе оларға нүктелер сәйкес). Екінші жиын элементтеріel, e2, ..., eN қабырғалар деп

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

Сурет 3 - Бағытталған графмысалы

Егер екі шың екі немесе одан да көп қабырғалармен қосылса, онда мұндай қабырғалар параллельді деп аталады (мысалы, қабырғалар е4 және е5).

Егер қабырғаның басы мен аяғы бір жерден шықса, онда мұндай қабырға ілмек (петля) деп аталады (мысалы, қабырға e7). Ілмексіз және параллельді қабырғаларсыз графтар қарапайым депаталады.

Граф деп G = (V, Е) алгебралық жүйесін айтамыз, мұнда R-екі орынды предикаттық символ. Х тасымалдаушының элементтері G графының төбесідеп, алV⊆Х бинарлық қатынасының элементтері доғасы деп аталады. Сонымен (a,b)∈V төбелер жұбы доға болып табылады. Мұнда сонымен қатар (а,b) доғасы

а төбесінен шығушы және в төбесіне енуші деп аталады. 4- суретте, Х={1,2,3,4} төбелер жиыны мен V={(1,1),(1,2), (2,3), (3,4), (4,3), (4,1)} доғалар жиынымен берілген G графы бейнеленген.

Сурет 4

V жиынындағы жұптар қайталануы мүмкін және сол сияқты жұптағы элементтер де қайталануы мүмкін.

Егер V жиынындағы жұптар қайталанса, онда G псевдограф немесе еселі қабырғалы граф деп аталады.

Егер V жиынындағы жұптар реттелмеген болса, онда G графы бағдарланбаған граф деп аталады. Егер олар реттелген болса, онда G графы бағдарланған граф немесе орграф деп, ал V жиынының элементтері доға деп аталады.

Төбелер сыбайлас немесе көршілес деп аталады, егер оларды қосатын қабырға бар болса.

Егер төбе қабырғаның басы немесе соңғы ұшы болса, онда төбе мен қабырға

инцедентті деп аталады.

Төбе дәрежесі деп оған инцедентті қабырғалар саны аталады, х төбесінің дәрежесі d(х) деп белгіленеді. Дәрежесі 0-ге тең төбе оқшауланған (изолированная) деп аталады. Дәрежесі 1-ге тең төбе ілінулі (висячая) немесе дағдарысты (тупиковая) деп аталады.

5 суретте G = (V, Е) графы төбелер жиыны Х={a₁, a₂, …, a_n} n элементтен тұратын граф болсын. G графыныңА_G=(А_ij) сыбайлас матрицасы деп

А_ij=түрінде анықталатын n-ші ретті матрица аталады. Егер А_ij=1 болса, онда а_i төбесі а_j төбесінен шығушы деп, ал а_i төбесі а_j –дің алдындағы деп аталады. Егер А_ij=1 немесе А_ji= 1 болса, онда а_i және а_j төбелері сыбайлас деп аталады. Қабырғалары (доғалары) еселі графтарда 1–дің орнына i және j төбелері арасындағы қабырғалар (доғалар) саны жазылады. х₇ төбесі оқшауланған. Суретте бағдарланбаған граф үшін сыбайластық матрицасы 7х7 өлшемді болады және келесі түрде жазылады.

^х₄

^х₁

^х₂

^х₅

^х₃ А=

^х_{6 ·} ^х₇

Сурет 5. Бағдарланбаған граф

Бағдарланған граф үшін 6х6 өлшемді сыбайластық матрицасын келесі түрде

жазылады.

х₂ 0 1 0 0 0 0

^х₄ ^{0 0 1 0 0 0}

^х₃ ^{0 0 0 1 0 0}

^х₁ ^{А= 0 0 0 0 1 0}

^х₅ ^{0 0 1 0 0 0}

0 0 1 0 0 0

х₆

Сурет 6. Бағдарланған граф

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

N төбелі және m қабырғалы бағдарланған графтың инцидентік матрицасы деп n жол мен m бағаннан тұратын b_ij элементтері келесі түрде анықталатын матрицаны айтамыз.

1,егер i төбесі j қабырғасының басыболса

^b_ij^{= -1, егер і төбесі j қабырғасының ұшы болса}

2, егер і төбесі j қабырғасының басы мен ұшы болса

0, егер і төбесі мен j қабырғасыны инцидентті болса

^х₂ ^{1 0 0 0 0 0}

	2			х4	-1 1 0	0	0 0
1		х3	3	4	0 -1	1	0 -1 -1

^х₁ ^{В= 0 0 -1 0 1 0}

х₅ 0 0 1 -1 0 0

⁵ _{0 0 1 0 0 0}

6

^х₆

Сурет 7. Графтың инцидентті матрицасы

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

Графтардың әртүрлі мүмкін әдістерін қарастыра отырып, сәйкес ақпаратты компьютерге енгізу мұқтаждығын есте сақтау қажет. Осы жағдайда ақпаратты сандық түрде енгізу ең қолайлысы, дегенмен қазіргі техникалық құралдар графикалық ақпаратты да (кестелер, мәтіндер, графиктер, суреттер) енгізеді және өңдей алады.