Теориялық мәлімет

Логика алгебрасының негізгі жағдайларын XIX ғ. ағылшын математигі Джордж Буль жасаған. Логика алгебрасын булевтік алгебра деп те атайды.

Булевтік алгебрада екілік айнымалыларды және айырып-қосқыш функцияларды ажыратады.

Екілік айнымалылар екі мән қабылдай алады: 0 және 1. Оларда логикалық немесе булевтік айнымалылар деп аталады және х₁,x₂,х₃,... таңбаларымен белгіленеді.

Айырып-қосқыш функциялар (АФ) екілік айнымалылардан тәуелді. Олар, аргументтері сияқты, тек екі мән қабылдай алады: 0 немесе 1. АФ логикалық немесе булевтік функциялар депте айтады. АФ f(х₁,x₂,х₃,...) түрінде, жақша ішінде аргументтерін көрсете отырып, немесе y₁,y₂,y₃,... түрінде белгілейтін боламыз. АФ өз кезегінде оданда күрделі логикалық функциялардың аргументтері болып қызмет ете алады. Сондықтан, логикалық байланыстардың шектеулі санын қолдана отырып, кезкелген күрделілігі алдынала берілген АФ құруға болады.

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

Айнымалылар жиыны — бұл екілік айнымалылар мәндерінің жиынтығы, олардың әрқайсысы 0 немесе 1 тең болуы мүмкін. Егер АФ аргументтер саны (тәуелсіз айнымалылар) n тең болса (яғни х₁,x₂,х₃,...x_n), онда осы айнымалылардың 2 әртүрлі үйлесімі бар, яғни жиындардың.

2.1 кестесі х₁,x₂,х₃ екілік айнымалылардан тәуелді f₁ және f₂ кейбір АФ үшін ақиқат кестесін көрсетеді. n = 3 (үш айнымалы) болғандықтан, 2.1 кестесі х₁,x₂,х₃ айнымалыларының 2³ = 8 жиынына сәйкес, 8 жолдан тұрады. 2.1 кестесіндегі әрбір жиын үшін, 0 немесе 1 тең, f₁ және f₂ АФ мәндері жазылған. Ақиқат кестесі бойынша АФ үшін аналитикалық өрнектер жазылады.

Кесте 2.1

х₁	х₂	х₃	f₁	f₂

Кезкелген АФ элементарлық логикалық функциялардың шектеулі саны көмегімен екілік айнымалылардан функциялар түрінде өрнектелуі мүмкін. Осы функцияларды қарастырайық.

Логикалық теріс (ЕМЕС (НЕ) функциясы). х айнымалысының логикалық терісі деп мынадай АФ f₁(x) айтады, x = 0 болғанда ол 1 мәнін, ал х= 1 болғанда 0 мәнін қабылдайды. АФ ЕМЕС түрінде белгіленеді және: «f₁ (эквивалентті) х емес» оқылады.

2.2 кестесі ЕМЕС логикалық функциясының ақиқат кестесін көрсетеді.

Кесте 2.2

х	f₁

ЕМЕС функциясын физикалық элемент (электрондық схема) орындайды, ол ЕМЕС элементі немесе инвертор деп аталады. Функционалдық схемада инверторды белгілеу 2.1 суретінде көрсетілген.

2.1. сурет

Логикалық көбейту (конъюнкция). Екі (немесе кезкелген басқа сан) х₁ және х₂ айнымалыларының конъюнкциясы тек барлық айнымалыларының мәні 1 тең жиында ғана 1 мәнін қабылдайды. Қалған жиындарда бұл функция 0 мәніне тең.

Кесте 2.3

x₁	x₂	f₂

2.3 кестесі екі х₁ және х₂ айнымалылары конъюнкциясының ақиқат кестесін көрсетеді. АФ конъюнкциясы түрінде белгіленеді және: «f₂ х₁ және x₂ (эквивалентті)» деп оқылады.

2.2.сурет

Конъюнкцияны белгілеу үшін немесе & таңбаларын қолдануға болады. Конъюнкция называется также функцией ЖӘНЕ (И) функциясы депте аталады, себебі, тек егерде бірінші және екінші аргументтер 1 мәніне ие болса ғана, ол 1 мәніне ие болады.

ЖӘНЕ функциясы электрондық схемамен орындалады, ол ЖӘНЕ элементі немесе коньюнктор деп аталады. ЖӘНЕ элементін функционалдық схемада белгілеу 2.2 суретте көрсетілген. ЖӘНЕ элементінің кіру саны, көбейту амалына қатысатын айнымалылар санына тең.

Логикалық қосу (дизъюнкция). Екі (немесе кезкелген басқа сан) х₁ және х₂ айнымалыларының дизъюнкциясы тек барлық айнымалыларының мәні 0 тең жиында ғана 0 мәнін қабылдайды. Егер айнымалылардың кем дегенде біреуі 1 тең болса, функция 1 мәніне ие болады.

2.4 кестесі екі х₁ және х₂ айнымалылары дизъюнкциясының ақиқат кестесін көрсетеді. АФ дизъюнкциясы түрінде жазылады және: «f₃ х₁ немесе x₂ (эквивалентті)» деп оқылады. + таңбасынан басқа, дизъюнкция үшін V таңбасы қолданылады.

Дизъюнкция функциясы 1 мәніне ие болғандықтан, егер бірінші немесе екінші аргументтер 1 мәніне ие болса, дизъюнкция амалы НЕМЕСЕ (ИЛИ) амалы деп те аталады.

Кесте 2.4

x₁	x₂	f₃

НЕМЕСЕ амалы электрондық схемамен жүзеге асырылады, ол НЕМЕСЕ элементі немесе дизъюнктор деп аталады. НЕМЕСЕ элементін функционалдық схемада белгілеу 2.3 суретте көрсетілген. НЕМЕСЕ элементінің кіру саны, дизъюнкция амалына қатысатын айнымалылар санына тең.

2.3. сурет

Элементарлық логикалық функциялар ЕМЕС, ЖӘНЕ, НЕМЕСЕ негізгі логикалық функциялар болып табылады. Негізгі функциялардан туынды тағыда бірнеше логикалық функциялар (яғни ЕМЕС, ЖӘНЕ, НЕМЕСЕ функциялары арқылы өрнектелетін) бар, олар сәйкес электрондық элементтермен жүзеге асырылады және ЭЕМ схемотехникасында жиі кездесетіндіктен, оларға меншік атаулар берілген. Осы функцияларды қарастырайық.

Конъюнкцияны теріске шығару (амал ЖӘНЕ — ЕМЕС). Бұл функция ЖӘНЕ амалы орындалу кезінде, алынған нәтижені теріске шығару жолымен алынады. 2.5 кестесі екі айнымалы үшін ЖӘНЕ — ЕМЕС амалының ақиқат кестесін көрсетеді. АФ ЖӘНЕ-ЕМЕС конъюнкцияны теріске шығару (амалы) болып табылатындығы, 2.3 және 2.5 кестелерін салыстырудан көрінеді. АФ ЖӘНЕ — ЕМЕС түрінде жазылады

Кесте 2.5.

x₁	x₂	f₄

ЖӘНЕ—ЕМЕС функциясын схема орындайды, ол ЖӘНЕ — ЕМЕС элементі деп аталады. Функционалдық схемада ЖӘНЕ — ЕМЕС элементін белгілеу 2.4. суретінде көрсетілген. ЖӘНЕ — ЕМЕС элементінің кіру саны ЖӘНЕ — ЕМЕС функциясының аргумент санымен анықталады.

2.4. сурет

Дизъюнкцияны теріске шығару (НЕМЕСЕ — ЕМЕС амалы). Бұл амал НЕМЕСЕ амалын орындаған кезде алынған, нәтижені теріске шығару жолымен пайда болады. 2.6 кестесі екі айнымалы үшін НЕМЕСЕ — ЕМЕС амалының ақиқат кестесін көрсетеді. АФ НЕМЕСЕ-ЕМЕС дизъюнкцияны теріске шығару (ЕМЕС амалы) болып табылатындығы, 2.4 және 2.6 кестелерін салыстырудан көрінеді. АФ НЕМЕСЕ — ЕМЕС түрінде жазылады.

Кесте 2.6.

x₁	x₂	f₅

НЕМЕСЕ — ЕМЕС амалын электрондық элемент орындайды, ол НЕМЕСЕ — ЕМЕС элементі деп аталады. Функционалдық схемада НЕМЕСЕ — ЕМЕС элементін белгілеу 2.5. суретінде көрсетілген. НЕМЕСЕ — ЕМЕС элементінің кіру саны НЕМЕСЕ — ЕМЕС функциясының аргумент санымен анықталады.

2.5. сурет

НЕМЕСЕні ЖОЮШЫ (ТЕҢМӘНСІЗДІК немесе ЕКІ МОДУЛІ БОЙЫНША ҚОСУ амалы). Берілген функция 1 мәніне, бірліктер саны тақ болатын, айнымалылар жиынында ие болады. Екі айнымалы үшін ТЕҢМӘНСІЗДІК амалы (кесте 2.7) ақиқат кестесінде көрсетілген. Бұл амал екі айнымалы үшін түрінде жазылады.

ТЕҢМӘНСІЗДІК функциясын орындаушы элементтің шартты белгісі, функционалдық схемада 2.6 суретте көрсетілген. Символ таңбасы элемент өрісінде «екі модулі бойынша қосуды» білдіреді.

2.6. сурет

ТЕҢМӘНСІЗДІК амалы ЕМЕС, ЖӘНЕ, НЕМЕСЕ амалдары арқылы түрінде өрнектеледі.

Кесте 2.7.

x₁	x₂	f₆

НЕМЕСЕні ЖОЮШЫ — ЕМЕС (ТЕҢМӘНДІЛІК) амалы. ТЕҢМӘНДІЛІК функциясы НЕМЕСЕні ЖОЮШЫ амалына кері амалды көрсетеді.

Берілген амал бірліктердің жұп мәндерінен тұратын, айнымалылар жиынында 1 мәніне ие болады. Екі айнымалы үшін НЕМЕСЕні ЖОЮШЫ — ЕМЕС амалы (кесте 2.8) ақиқат кестесінде көрсетілген. Бұл амал екі айнымалы үшін түрінде өрнектеледі.

Кесте 2.8.

x₁	x₂	f₆

НЕМЕСЕні ЖОЮШЫ — ЕМЕС амалы ЕМЕС, ЖӘНЕ, НЕМЕСЕ амалдары арқылы түрінде өрнектеледі.

ТЕҢМӘНДІЛІК функциясын, функционалдық схемадағы бейнесі 2.7 суретте көрсетілген, ұқсас атпен электрондық элемент орындайды.

2.7. сурет

Өз бетімен орындауға арналған тапсырмалар:

А және В екілік сандар берілген (кестедегі шамалар). Амалды орындаңыз:

- Теріске шығару

- Логикалық қосу

- НЕМЕСЕ теріске шығару

- Логикалық көбейту

- ЖӘНЕ теріске шығару

- НЕМЕСЕні жоюшы

- НЕМЕСЕні жоюшыны теріске шығару

Вариант	А	В
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.

Лабораториялық жұмыс №3 (1 сағат)

Тақырыбы: «Графтар мен ағаштар»

Жұмыстың мақсаты: Графтар мен ағаштарды оқып-үйрену

Тапсырма:

1. Графтар мен ағаштарды қарастыру

2. Бағдарланбаған және бағдарланған графтарды, графтардың айналып өту стратегиясын қарастыру

3. Графтар мен ағаштарға мысалдар келтіру

4. Есеп беруді құру