• 3 – ТАҚЫРЫП. Бульдік алгебра

• 3.1 Бульдік алгебра функциялары, қатынас және жиындар.

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

• 3.3 Графтар мен ағаштар.

• Буль алгебрасы, буль торы — ішінара реттелген жиынның арнаулы түрі. Егер жиынның ең үлкен элементі 1 (Буль алгебрасының бірлігі), ең кіші элементі 0 (Буль алгебрасының нөлі) болса және әрбір х элементі мен оның толықтыру элементі Сх: sup {x, Cx}=1, іnf {x, Cx}=0 қатынастарын қанағаттандырса, онда Буль алгебрасы дистрибутивтік  және тор деп аталады. Sup және іnf операциялары әдетте таңбаларымен, кейде және таңбаларымен белгіленеді. Мұнан олардың жиын теориясындағы бірігу және қиылысу операцияларымен ұқсастығы көрінеді. Сх кейде –х болып жазылады. Буль алгебрасында кез келген элементтің толықтыруы біреу-ақ болады. Буль алгебрасының аксиомаларында “жиын”, “оқиға” және “пікір” ,  ұғымдарының арасындағы ұқсастық бейнеленген. Буль алгебрасында С, сияқты негізгі операциялардан басқа операциялар да анықталған болуы мүмкін. Солардың ішінде төмендегідей симметриялық айырма операциясы у, |x-у| деп те жазылады. КезСх). Бұл х(уСу) ерекше маңызды: х+2у=(х келген Буль алгебрасы +2 (“қосу (“”) және көбейту”) операциялары орындалатын бірлігі бар буль сақинасы болып табылады. Буль алгебрасы ағылшын математигі Дж. Бульдің (1815 — 1864) еңбектерінде (1847, 1854) символикалық логиканың аппараты ретінде пайда болды. Кейіннен ол математиканың әр түрлі саласында (ықтималдық теориясы, топология, функционалдық талдау, т.б.) кеңінен қолданылды.

• Информатиканың логикалық негіздері.

• ЭЕМ қатысуымен шешілетін есептердің арасында дәстүр бойынша логикалық деп аталатын мұндай есептер аз емес.

• Логика дегеніміз - адамның ойлау нысандары мен заңдары туралы, нақты айтқанда, дәлелді пікір заңдары туралы ғылым.

• Логикалық алгебраның негіздері түсініктері.

• Ғылыми пән ретінде логиканың бірнеше нұсқалары дараланады: формалды логика, математикалық логика, ықтималды логика, диалектикалық логика және т.б.

• Әр түрлі кестелерді жасау, қарама-кайшы түйіндерді шешу және баска да көптеген жағдайларда адамдар логиканың көмегіне жүгінеді.

• Формалды логика сөйлеу тілімен білдіретін біздің кәдімгі мазмұнды пікірімізге талдау жасаумен байланысты.

• Математикалық логика формалды логиканың бір бөлігі болып табылады және ол кесіп-пішіп, айқындалған объектілер мен пікірлердің ақиқаттығын немесе жалғандығын біржақты шешуге болатын дәйектемелерді ғана үйретеді.

• Математикалық логика саласы, алгебралық қисын сияқты, информатикада да жақсы меңгерілген. Казіргі уақытта алгебралық қисынның негізгі операцияларына қосылмаған бір де бір программалау тілі жоқ.

• Логикалық есептерде тек сандар ғана емес, тосын, тым шатасқан пікірлер де бастапқы деректер болып табылады.

• Компьютерде бұл есепті шешу кезінде программада шартты қолдану жолымен логикалық операциялар пайдаланылуы қажет.

• Логикалық өрнектер.

• Ақпараттармен алмасу кезінде адамдармен қатынасудың формаларының бірі - бұл сұрақтар мен жауаптарды кезектестіру. Әрбір сұрақ бізді қоршайтын заттық әлем туралы білімнің қажеттігін көрсетеді. Бұл білімдерді біз пікір түрінде айтамыз. Пікір қағида бойынша бақыланатын фактілерді тікелей көрсете алады: "Күн жарқырап тұр", "Бұл тіктөртбұрыш - квадрат" және т.с.с. Бірақ пікірлер ойдан шығарылған объектілер немесе әлі болмаған жағдайлар туралы пайымдап, оларды көрсете алады: "Су перісі бұтақтарда отыр", "Бүгін жаңбыр болады" және т.с.с.

• Пікірлер дегеніміз - жалған немесе ақиқат болатын кейбір пайымдаулар.

• Мысалы, "ақ қар", "2*2=4" пікірлері ақиқат, ал "жер тегіс", "2*2=5" пікірлері жалған. Әдетге, біз бақылайтың фактілер ақиқатқа қабылданылады. Жалған пайымдаулар көбіне жиі талқылаулардағы немесе сөйлемдердегі қателерден немесе қалауды шыңдықтың орнына беруге ұмтылудан пайда болады.

• Пікірлер жалпы және жеке болып бөлінеді. Жеке пікірлер нақты фактілерді көрсетеді, мысалы, "3+3<7", "Бүгін бұлтсыз шуақты күн болады".

• Жалпы пікірлер объектілер тобының немесе оқиғаның қасиетін сипаттайды, мысалы, "Егер жаңбыр жауып өткен болса, онда көше ылғалды болады", "Кез келген квадрат параллелограмм болып табылады" және т.с.с.

• Жалпы пікірлер объектілердің қандай да бөліктері үшін ақиқат және басқа объектілер үшін жалған болуы мүмкін. Мысалы, "Иттер мысықтарды жақсы көрмейді" пікірі иттердің көп саны үшін әділетті, бірақ барлықтары үшін емес. "х*у>0" пікірі х=1 және у=1 үшін ақиқат және сол кезде у ерікті кезінде х=0 үшін жалған.

• Егер пікірде айтылған ой объектілердің кез келгені үшін әділетті болса, онда жалпы пікір бекем ақиқат деп аталады. Мысалы, "Итте төрт аяқ" пікірі кез келген ит үшін әділ. Бекем ақиқат пікір заттардың заңдылықтарын байланыстыруда ерекше құнды. Мысалы, "а+в=в+а" пайымдауы кез келген айғақ сан үшін әділетті және -"Қосылғыштардың орнын ауыстырғаннан қосынды өзгермейді" деген арифметиканың заңын көрсетеді.

• Қиын жағдайларда сұрақтардың жауабы ЖӘНЕ, НЕМЕСЕ, ЕМЕС жалғаулары арқылы құрамды пікірлермен көрсетіледі.

• Құрамды пікірлердегі ЖӘНЕ жалғаушысы әрқашан бір мезгілдік ақиқатты болжайтын пікірлерді құрайды.

• Құрамды пікірлердегі НЕМЕСЕ жалғаушысы екі рөлді ойнауы мүмкін. Мысалы, "Бүгін біз баққа демалуға барамыз немесе бақшада жұмыс істейміз". НЕМЕСЕ жалғаушысын "Не" бөлушісімен айырбастауға болады, "Бүгін біз не бақка демалуға барамыз, не бақшада жұмыс істейтін боламыз", өйткені бір мезгілде бақта демалуға және бақшада жұмыс істеуге мүмкін емес. Ал "Жаңбыр күндіз немесе кешке болады" деген сөйлемде үш түрлі жағдай мүмкін: "Жаңбыр күндіз болады", не "Жаңбыр кешке болады", не "Жаңбыр күндіз де, кешкеде болады". Бірінші мысалда НЕМЕСЕ жалғаушысы бөлуші рөл, ал екіншісінде біріктіруші рөл атқарады.

• Барлық компьютерлік программаларда және математикалық талқылауларда НЕМЕСЕ жалғаушысы тек біріктіруші рөл атқарады. Мысалы, "х=0 немесе у=0" пайымдауыңдағы НЕМЕСЕ жалғаушысы не "у=0", не "х=0", не "х=0 және у=0" білдіреді.

• Ереже. Математикада НЕМЕСЕ жалғаушысы бар құрамды пікір: егер оны құрайтындардың тіпті біреуі ғана ақиқат болса, ол ақиқат болып; егер оны құрайтындардың бәрі жалған болса, ол жалған пікір болады.

• ЕМЕС жалғаушысы теріске шығаруды пішімдеу үшін қолданылады. Мысалы, "х=0" пайымдауының теріске шығаруы "х=0" пайымдауына тең "х=0 теріс" пайымдауы болады. "Бұл адам әдемі" пайымдауының теріске шығарылуы "Бұл адам әдемі емес" пайымдауына тең.

• Ереже. Егер бастапқы пайымдау жалған болса, онда теріске шығару ақиқат және, керісінше, егер бастапқы пайымдау әділ болса, онда теріске шығару жалған.

• Логикалық амалдар.

• Логикалық жалғаушылар математикалық логикада күрделі пайымдауларды сипаттайтын логикалық операциялар болып табылады. Математикалық логикада ЖӘНЕ, НЕМЕСЕ, ЕМЕС логикалық операциялары ақиқаттық мәндер кестесімен анықталады.

  "және" "немесе" "емес"

  конъюнкция (логикалық көбейту) дизъюнкция (логикалық қосу) теріске шығару

  А және В А немесе В А емес

•  

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

• ЖӘНЕ жалғаулығының көмегімен бір құрамдасқа екі қарапайым А және В пайымдауларының бірігуі логикалық көбейту немесе конъюнкция деп аталады, ал операцияның нәтижесі - логикалық көбейтінді.

• ЖӘНЕ (конъюнкция) логикалық операциясы үшін ақиқаттық кесте мынадай:

  А	В	А және В
  иә	иә	иә
  иә	жоқ	жоқ
  жоқ	иә	жоқ
  жоқ	жоқ	жоқ

• Мұндағы А және В - иә немесе жоқ мәнін қабылдай алатын екі пайым.

• Мысалы, деректері қарапайым айтылымдар болсын: А - "Астана - Қазақстанн астанасы", В - "Астанада 300 мыңнан астам адам тұрады".

• Онда осы айтылғандардың логикалық көбейтіндісі, немесе конъюнкциясы, күраіу пайымдау болады: Астана - Қазақстанның астанасы және Астанада 300 мыңі астам адам тұрады пайымдауларьшың ақиқат мәніне байланысты иә немесе жоқ мә қабылдайды. А мен В пайымдауы иә мәнін қабылдағанда "А мен В" кұрам пайымдауы да иә мәнін қабылдайтьшын кестеден көреміз.

• Ақиқат кестесінен:

• Пікірдің екеуі де ақиқат болғанда, А және В конъюнкциясы ақиқат;

• А немесе В пікірлерінің біреуі немесе екеуі де жалған болғанда, А және В конъюнкциясы жалған болатындығын көреміз.

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

• Біріктіруші мағынада қолданылатын НЕМЕСЕжалғаулығының көмегімен бір құрамдасқа екі қарапайым А және В айтылымдарының бірігуі логикалық қосу немесе дизъюнкция деп аталады, ал операцияның нәтижесі - логикалық қосынды.

• НЕМЕСЕ логикалық операциясы үшін ақиқаттық кесте мынадай түрде болады:

  А	В	А немесе В
  иә	иә	иә
  иә	жоқ	иә
  жоқ	иә	иә
  жоқ	жоқ	жоқ

• Мысалы, "Күзде ағаштарда жапырақтар жасыл және сары" құрамды пікірі үш жағдайда иә логикалық мағынасын қабылдайды: "Күзде ағаштарда жапырақтар жасыл" не "Күзде ағаштарда жапырақтар сары", не "Күзде ағаштарда жапырақтар жасыл әне сары" болғанда.

• Бұл операцияның ақиқаттық кестесінен, егер А да, В да иә мәніне ие болса; не тек қана А, не тек қана В иә мәніне ие болса, онда "А немесе В" айтылымы иә мәніне ие болатындығы көрінеді. Және керісінше, егер А да, В да жоқ мәніне ие болса, онда "А немесе В" айтылымы жоқ мәніне ие болады.

• Егер А немесе В пікірлерінің тек біреуі ғана ақиқат болғанда, А және В дизъюнкциясы ақиқат.

• А және В пікірлерінің екеуі де жалған болғанда, А және В дизъюнкциясы жалған.

• Логикалық теріске шығару

• Қарапайым А айтылымына ЕМЕС демеулік шылауын қосу логикалық теріске шығару операциясы деп аталады, операцияны орындағаннан кейінгі нәтиже жаңа айтылымды береді.

• ЕМЕС (теріске шығару) логикалық операциясы үшін ақиқаттық кесте мына түрде болады:

  А	А емес
  иә	жоқ
  жоқ	иә

• Мұндағы А кейбір еркін айтылымдар.

• Мысалы, "Бүгін далада ыстық" айтылымы үшін "Бүгін далада ыстық емес" айтылымы теріске шығару болады.

• Кей жағдайларда барлық айтылымдарға "... жалған" сөзін қолдануға болады. Сонда "Сен жақсы баға алдың" айтылымын "Сенің жақсы баға алғаның жалған" айтылымы теріске шығару болады.

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

• Бастапқы пікір жалған болғанда, теріске шығару ақиқат.

• Бастапқы пікір ақиқат болғанда, теріске шығару жалған.

• Логикалық элементтер — логика алгебрасы ережелеріне сәйкес кіріс сигналдарымен қарапайым логикалық операцияларды (функцияларды) жүзеге асыратын электрондық құрылғылар. Осындай операцияларға логикалық қосу — '''дизъюнкция''' (“немесе”), көбейту — '''конъюнкция''' (“және”), терістеу — '''инвертирлеу''' (“емес”) жатады. Қарапайым Логикалық элементтердің шартты белгілері суретте көрсетілген. Ақпараттық сигналдар ретінде электр кернеуі немесе тогының дискреттік мәндері (деңгейлері) қолданылады. Мысалы:

• 0 — төмен деңгейге, 1 — жоғары деңгейге сәйкес келеді.

• Логикалық элементтер функционалдық белгіленуі, ақпарат беру әдісі, сұлбатех. шешімі және пайдаланылатын электрондық құралдары бойынша ажыратылады. Күрделі Логикалық элементтер қарапайым операциялар орындайтын элементтерді біріктіру арқылы жасалады. Мысалы:

• “немесе” — “емес”, “және — емес”, “немесе — және — емес”, т.б.