Логика заңы және базалық логикалық элементтер

Логиканың негізгі заңдары: А = А – тепе-теңдік заңы

А & = 0

A  = 1

= А – Екілік терістеу заңы

---------------------------------------------------------------------------------------------------

Тұрақты қасиеті: = 1 = 0

А  0 = А А  0 = 0

А  1 = 1 А  1 = 1

--------------------------------------------------------------------------------------------------

Идемпотент заңы: А  А = А

А  А = A

--------------------------------------------------------------------------------------------------

Орнын ауыстыру заңы. Коммутативтік: А  В = В  А

А  В = В  А

--------------------------------------------------------------------------------------------------

Үйлестіру заңы. Ассоциативтік (лат.-біріктіру): А  (В  С) = (А В)  С

А  (В  С) = (А  В)  С

--------------------------------------------------------------------------------------------------

Тарату заңы. Дистрибутивтік: А  (В  С) = (А В)  (А  С)

А  (В  С) = (А  В)  (А С)

-------------------------------------------------------------------------------------------------

Жұтыну заңы: А  (А  В) = А

А  (А  В) = А

-------------------------------------------------------------------------------------------------

де Морган заңы:

---------------------------------------------------------------------------------------------------

Компьютердің базалық логикалық элементы

Логикалық элемент ЖӘНЕ

конъюнктор

Логикалық элемент НЕМЕСЕ

дизъюнктор

Логикалық элемент ЕМЕС

инвертор

3 Графтар және ағаштар

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

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

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

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

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

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

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

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

Суретте 3.4, Х={1,2,3,4} төбелер жиыны мен V={(1,1),(1,2),

(2,3), (3,4), (4,3), (4,1)} доғалар жиынымен берілген G 1 графы бейнеленген.

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

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

3

4

Сурет 3.4

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

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

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

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

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

3.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 өлшемді болады және келесі түрде жазылады.

А=

х₄

х₁

х₂

х₅

х₃

х₆

Сурет 3.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

х₆

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

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

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

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

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

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

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

х₂ 1 0 0 0 0 0

₂ х₄ -1 1 0 0 0 0

₁ х_{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

⁶

х₆

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

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

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

Бақылау сұрақтары:

1. Жиын анықтамасын беріңіз?

2. Жиын қандай болады?

3. Жиындардың қандай түрлерін білесіз?

4. Логиканы негіздеуші кім?

5. Ақиқаттық кестесі деген не?

6. Логиканың негізгі заңдарын атаңыз?

7. Граф деген не?

8. Ағаш деген не ?

Қолданылған әдебиеттер:

[1], [3], [5], [6], [8], [10], [11]

Глоссарий

Ақпарат көзі – ақпаратты туындатып және оны мәліметтер түрінде көрсететіп беретін субъект немесе объект.

Ақпаратты қабылдаушы – мәліметті қабылдап және оны дұрыс пайымдау (интерпретациялау) мүмкіндігі бар субъект немесе объект.

Ақпаратты тасушы – мәліметтерді ақпарат көзінен қабылдаушыға жіберуге бір арнайы заттандырылған (материалданған) субстанция. Мәліметтер, тасушының көмегімен сигнал арқылы беріледі.

Сигнал – хабарды беруді қамтамасыз ететін қандай да бір физикалық шаманың уақыт барысында өзгеруі.

Алфавит – тәртібі анықталған цифрлардың немесе символдардың шектелген жиыны.

Символдарды кодтау (ағылш. encoding) — белгілердің шектелген жиынын нақтылы кодтау кестесі. Мұндай кестеде әр символды, ұзындығы бір немесе бірнеше байттар тізбегімен салыстырады. Қазіргі кезде негізінен үш типті кодтау қолданылады: ASCII1 кодымен үйлесімді, EBCDIC кодымен үйлесімді және 16-биттік Юникодқа негізделген кодтаулар.

EBCDIC (Extended Binary Coded Decimal Interchange Code ) — кеңейтілген екілік-ондық ақпарат алмасу коды, айтылуы «эб-си-дик». IBM корпорациясы құрастырған стандарты сегізбиттік EBCDIC коды латын алфавитінің әріптерін, араб цифрларын, кейбір тыныс белгілерін және басқару символдардын кодтайды.

Юникод немесе Уникод (англ. Unicode) — шын мәнінде барлық жазба тілдердің белгілерін ұсынуға мүмкіндік беретін, символдарды кодтау стандарты. Бұл стандартты 1991 жылы коммерциялық емес «Юникод консорциумы» (Unicode Consortium, Unicode Inc.) ұжымы ұсынған.