Bul algebrasi

Bul algebrasi nima?

Bul algebrasi Boolean qiymatlar (true yoki false) ustida mantiqiy amallar (AND, OR, NOT) qo‘llanganda nima sodir bo‘lishini o‘rganadi.

Bul algebrasi kompyuterlar va raqamli elektronika qanday ishlashini hamda mantiqiy ifodalarni qanday soddalashtirishni tushunishga yordam beradi.

AND, OR va NOT mantiqiy amallari dasturlashda qanday ishlatilishini ko‘rish uchun mantiqiy operatorlar haqidagi sahifamizni ko‘ring.

Bul algebrasining turli ko‘rinishlari

Bul algebrasini kontekstga qarab turli usullarda ifodalash mumkin.

Quyida AND, OR va NOT mantiqiy amallari matematikada va dasturlashda qanday ifodalanishi ko‘rsatilgan:

Bu sahifaning katta qismi matematika sifatidagi Bul algebrasiga bag‘ishlangan, lekin orada dasturlash misollari ham bor, pastroqda esa mantiqiy elementlar (logic gates) tushuntirilgan.

Bu operatorlar dasturlashda qanday ishlatilishi haqida ko‘proq bilish uchun mantiqiy operatorlar haqidagi sahifamizni ko‘ring.

AND, OR va NOT

Bul algebrasini ko‘rib chiqishni boshlashdan oldin AND, OR va NOT amallari qanday ishlashini aniq bilib olishimiz kerak.

AND ikkita Boolean qiymatni oladi. Natija faqat ikkala qiymat ham true bo‘lsagina true bo‘ladi, aks holda false bo‘ladi.

OR ikkita Boolean qiymatni oladi va qiymatlardan kamida bittasi true bo‘lsa, natija true bo‘ladi, aks holda false bo‘ladi.

NOT bitta Boolean qiymatni oladi va uni teskarisiga aylantiradi. Agar qiymat false bo‘lsa, bu qiymatga qo‘llangan NOT amali true qaytaradi, agar qiymat true bo‘lsa, NOT amali false qaytaradi.

"NOT A" NOT amalini bajarganda, ko‘pincha "A ning to‘ldiruvchisi" (complement), "A bar" (\(\overline{A}\) ko‘rinishida yoziladi), "A inkori", "A shtrix" (\(A'\) ko‘rinishida yoziladi) yoki shunchaki "NOT A" deymiz.

Bul algebrasini yozish

Bul algebrasini yozishda quyidagi komponentlar ishlatiladi:

• true \(1\) ko‘rinishida yoziladi
• false \(0\) ko‘rinishida yoziladi
• AND ko‘paytirish belgisi (\(\cdot\)) yordamida yoziladi
• OR qo‘shish belgisi (\(+\)) yordamida yoziladi
• NOT ustki chiziq (\(\overline{A}\)) yordamida yoziladi

AND, OR va NOT amallarini \(\wedge\), \(\vee\) va \(\neg\) belgilari yordamida ham yozish mumkin, lekin biz yuqoridagi ro‘yxatda ko‘rsatilgan belgilardan foydalanamiz.

Bul algebrasining oddiy misollari

true AND false ni Bul algebrasi yordamida hisoblash quyidagicha ko‘rinadi:

\[1 \cdot 0 = 0 \]

Hisob bizga shuni aytadi: "true ni false bilan AND qilish natijasi false".

Xuddi shu AND amalini dasturlashda bajarish quyidagicha ko‘rinadi:

print(True and False)

console.log(true && false);

System.out.println(true && false);

cout << (true && false);

Ustki chiziq yordamida "NOT true" hisobi quyidagicha ko‘rinadi:

\[ \overline{1} = 0 \]

Hisob bizga shuni aytadi: "NOT true natijasi false".

OR dan foydalanish quyidagicha ko‘rinadi:

\[ 1 + 0 = 1 \]

Hisob bizga shuni aytadi: "true ni false bilan OR qilish natijasi true".

Buning javobini topa olasizmi?

\[ 1 + 1 = \text{ ?} \]

Umid qilamizki, javob sizni xafa qilmaydi, chunki esda tuting: biz bu yerda oddiy matematika bilan shug‘ullanmayapmiz. Biz Bul algebrasi bilan ishlayapmiz.

Quyidagini olamiz:

\[ 1 + 1 = 1 \]

Bu shunchaki "true ni true bilan OR qilish natijasi true" degani.

Amallar tartibi

Oddiy matematikada qaysi amallarni birinchi bajarish qoidalari bo‘lgani kabi, Bul algebrasida ham amallar tartibi bor.

Murakkabroq Bul algebrasiga o‘tishdan oldin amallar tartibini bilishimiz kerak.

1. Qavslar
2. NOT
3. AND
4. OR

Masalan, ushbu ifodada:

\[ 1 + 0 \cdot 0 \]

To‘g‘ri tartib — avval AND ni, ya’ni \(0 \cdot 0\) ni bajarish; shunda dastlabki ifoda quyidagiga qisqaradi:

\[ 1 + 0 \]

Bu \(1\) (true) ga teng.

Demak, ifodani to‘g‘ri tartibda yechsak:

\[ \begin{aligned} 1 + 0 \cdot 0 &= 1 + 0 \\[8pt] &= 1 \end{aligned} \]

Bu ifodani noto‘g‘ri tartibda, ya’ni OR ni AND dan oldin bajarib yechsak, javob \(0\) (false) chiqadi, shuning uchun amallarning to‘g‘ri tartibiga rioya qilish muhim.

O‘zgaruvchilar bilan Bul algebrasi

Bul algebrasining asosiy tushunchalarini aniqlab olganimizdan so‘ng, nihoyat foydaliroq va qiziqarliroq natijalarni ko‘rishni boshlashimiz mumkin.

Boolean o‘zgaruvchilar odatda \(A\), \(B\), \(C\) va hokazo kabi katta harflar bilan yoziladi.

Boolean o‘zgaruvchini noma’lum deb tasavvur qilishimiz kerak, lekin u yo true, yo false bo‘ladi.

Quyida o‘zgaruvchilar yordamida olinadigan Bul algebrasining ba’zi asosiy natijalari keltirilgan:

\[ \begin{aligned} A + 0 &= A \\[8pt] A + 1 &= 1 \\[8pt] A + A &= A \\[8pt] A + \overline{A} &= 1 \\[8pt] A \cdot 0 &= 0 \\[8pt] A \cdot 1 &= A \\[8pt] A \cdot A &= A \\[8pt] A \cdot \overline{A} &= 0 \\[8pt] \overline{\overline{A}} &= A \\[8pt] \end{aligned} \]

Yuqoridagi natijalar oddiy, lekin muhim. Ularni birma-bir ko‘rib chiqib, tushunganingizga ishonch hosil qilishingiz kerak. (\(A\) o‘zgaruvchisini \(1\) bilan almashtirib, to‘g‘riligini tekshiring, so‘ngra \(A\) ni \(0\) bilan almashtirib, hali ham to‘g‘riligini tekshiring.)

Bul algebrasi yordamida kodni soddalashtirish

Yuqoridagi qoidalardan kodni soddalashtirish uchun foydalanish mumkin.

Keling, biror kishi universitet kutubxonasidan kitob olishi mumkinligini aniqlash uchun shart tekshiriladigan kod misolini ko‘rib chiqaylik.

if is_student and (age < 18 or age >= 18):
  print("You can borrow a book from the university library")

if (is_student && (age < 18 || age >= 18)) {
  console.log("You can borrow a book from the university library");
}

if (is_student && (age < 18 || age >= 18)) {
  System.out.println("You can borrow a book from the university library");
}

if (is_student && (age < 18 || age >= 18)) {
  cout << "You can borrow a book from the university library";
}

Yuqoridagi if operatoridagi shart

\[ is\_student \text{ AND } (age \lt 18 \text{ OR } age \geq 18) \]

Bul algebrasi yordamida quyidagicha yozilishi mumkin:

\[ is\_student \cdot (under18 + \overline{under18}) \]

Yoki:

\[ A \cdot (B + \overline{B}) \]

Yuqoridagi Bul algebrasi natijalari ro‘yxatidan ko‘ramizki,

\[B + \overline{B} = 1\]

(Bu qoidani oldingi bo‘limdagi Bul algebrasi natijalari ro‘yxatidan bilamiz.)

Demak, if operatoridagi shartni soddalashtirish mumkin:

\[ \begin{aligned} &is\_student \cdot (under18 + \overline{under18}) \\[8pt] &= is\_student \cdot (1) \\[8pt] &= is\_student \end{aligned} \]

Natijada, kishi universitet kutubxonasidan kitob olishi mumkinligini bilish uchun uning yoshini umuman tekshirishimiz shart emas, faqat talaba ekanini tekshirishimiz kifoya.

Shart soddalashtirildi:

if is_student:
  print("You can borrow a book from the university library")

if (is_student) {
  console.log("You can borrow a book from the university library");
}

if (is_student) {
  System.out.println("You can borrow a book from the university library");
}

if (is_student) {
  cout << "You can borrow a book from the university library";
}

Demak, talabalik guvohnomasini tekshirishning o‘zi yetarli, kitob olishga ruxsat berilganini bilish uchun yoshini tekshirish shart emas.

Balki shartni Bul algebrasisiz ham qanday soddalashtirish mumkinligini ko‘ra olarsiz, lekin murakkabroq ifodalarda Bul algebrasi juda foydali bo‘lishi mumkin.

Bul algebrasi qonunlari

Oldingi bo‘limda sanab o‘tilgan Bul algebrasining asosiy qonunlaridan tashqari, murakkabroq qonunlar ham bor.

O‘rin almashtirish qonuni (kommutativ qonun) o‘zgaruvchilarning tartibi ahamiyatga ega emasligini ko‘rsatadi.

\[ A \cdot B = B \cdot A \]

\[ A + B = B + A \]

Taqsimot qonuni (distributiv qonun) AND amalini OR amali bo‘yicha taqsimlash mumkinligini aytadi.

\[ A \cdot (B + C) = A \cdot B + A \cdot C \]

\[ A + B \cdot C = (A + B) \cdot (A + C) \]

Yuqoridagi birinchi qonun ancha sodda va oddiy algebradagi taqsimot qonuniga o‘xshaydi.

Lekin yuqoridagi ikkinchi qonun unchalik ravshan emas, shuning uchun o‘ng tomondan boshlab, xuddi shu natijaga qanday kelishimiz mumkinligini ko‘raylik:

\[ \begin{aligned} &(A + B) \cdot (A + C) \\[8pt] &= A \cdot A + A \cdot C + B \cdot A + B \cdot C \\[8pt] &= A + A \cdot C + A \cdot B + B \cdot C \\[8pt] &= A \cdot (1 + C + B) + B \cdot C \\[8pt] &= A \cdot 1 + B \cdot C \\[8pt] &= A + B \cdot C \end{aligned} \]

Guruhlash qonuni (assotsiativ qonun) natijani o‘zgartirmasdan o‘zgaruvchilarni turli usullarda guruhlash mumkinligini aytadi.

\[ (A \cdot B) \cdot C = A \cdot (B \cdot C) \]

\[ (A + B) + C = A + (B + C) \]

De Morgan qonunlari

De Morgan qonunlari — Bul algebrasida keng qo‘llaniladigan va e’tirof etilgan ikkita qonun.

complement (to‘ldiruvchi) so‘zi Bul algebrasida qarama-qarshi ma’noni, ya’ni biror narsani negate (inkor qilish) yoki NOT operatoridan foydalanishni anglatadi. \(A\) ning to‘ldiruvchisi \(\overline{A}\) ko‘rinishida yoziladi.

Quyida De Morganning birinchi qonuni yordamida shartni qanday qilib qayta yozish mumkinligi va u aynan avvalgidek ishlashiga misol keltirilgan.

Aytaylik, ishlab chiqarish jarayonidagi rezervuar undagi harorat ham, bosim ham ma’lum chegaralardan past bo‘lsa, xavfsiz hisoblanadi.

\[ tmp < 100 \text{ AND } press < 20 = \text{Xavfsiz} \]

Aks holda rezervuar xavfsiz emas va biz xavf signalini chalishimiz kerak.

\[ \overline{tmp < 100 \text{ AND } press < 20} = \text{Xavf signali} \]

De Morganning birinchi qonunidan foydalanib, ifodani qayta yozishimiz mumkin:

\[ \begin{aligned} &\overline{tmp < 100 \text{ AND } press < 20} \\[8pt] &= \overline{tmp < 100} \text{ OR } \overline{press < 20} \\[8pt] &= tmp ≥ 100 \text{ OR } press ≥ 20 \end{aligned} \]

Bu yerda kelgan natijamizni tushunish ham, dasturlash ham osonroq, De Morganning birinchi qonunidan to‘g‘ri foydalanganimiz uchun esa shart asl ko‘rinishdagidek ishlashiga amin bo‘lishimiz mumkin.

Masalan, agar siz "I do not have dogs or cats" ("Menda it yoki mushuk yo‘q") desangiz

\[ \overline{haveDogs + haveCats} \]

Buni "I do not have dogs and I do not have cats" ("Menda it yo‘q va menda mushuk yo‘q") deb aytishingiz ham mumkin

\[ \overline{haveDogs} \cdot \overline{haveCats} \]

Bu ikki gap bir xil ma’noni anglatadi va De Morganning ikkinchi qonuniga bo‘ysunadi.

Bul algebrasi yordamida murakkab ifodani soddalashtirish

Ochiq derazalar va eshiklarni aniqlaydigan sensorlar hamda harakatni aniqlaydigan sensorlarga ega xavfsizlik tizimini tasavvur qiling.

• ochiq deraza \(W\)
• ochiq eshik \(D\)
• oshxonada harakat aniqlandi \(M_K\)
• mehmonxonada harakat aniqlandi \(M_L\)

Xavf signalini ishga tushirishi kerak bo‘lgan barcha turli shartlar yoki vaziyatlar quyidagilar:

• Mehmonxonada harakat aniqlandi AND deraza ochiq (\(M_L \cdot W\))
• Mehmonxonada harakat aniqlandi AND eshik ochiq (\(M_L \cdot D\))
• Oshxonada harakat aniqlandi AND deraza ochiq (\(M_K \cdot W\))
• Oshxonada harakat aniqlandi AND eshik ochiq (\(M_K \cdot D\))

Bul algebrasidan foydalanganda, ushbu ifoda true bo‘lsa, xavf signali chalinadi:

Balki buni darhol qanday soddalashtirish mumkinligini ko‘rayotgandirsiz? Lekin ko‘rgan taqdiringizda ham, soddalashtirilgan ifoda asl ifoda bilan bir xil ishlashiga qanday amin bo‘lish mumkin?

Keling, ifodani soddalashtirish uchun Bul algebrasidan foydalanaylik:

Bul algebrasi yordamida ifodani soddalashtirdik.

Agar mehmonxonada yoki oshxonada harakat aniqlansa va shu bilan birga deraza yoki eshik ochiq bo‘lsa, xavf signali chalinadi.

Mantiqiy elementlar

Mantiqiy element (logic gate) — bu tranzistorlardan yasalgan va AND, OR yoki NOT mantiqiy amalini (Boolean funksiyasini) amalga oshiradigan elektron qurilma. Boshqa keng tarqalgan mantiqiy elementlar: NAND, NOR, XOR va XNOR.

Turli mantiqiy elementlar qanday ishlashini o‘zingiz ko‘rish uchun quyidagi simulyatsiyani sinab ko‘ring.

A va B kirishlarini 0 va 1 o‘rtasida almashtirish uchun ularni bosing, turli mantiqiy elementlarni navbatma-navbat ko‘rish uchun esa elementning o‘zini bosing.

Mantiqiy elementlar kompyuterlar va elektron qurilmalarning hamma joyida ishlatiladi: quloqchinlar, avtomobillar, mobil telefonlar, SSD, RAM, CPU va hokazo.

Quyida eng keng tarqalgan mantiqiy elementlarning umumiy ko‘rinishi keltirilgan.

AND, OR va NOT mantiqiy elementlari asosiy mantiqiy elementlar bo‘lib, oldingi bo‘limlarda tavsiflanganidek ishlaydi.

NAND va NOR mantiqiy elementlari AND va OR ning shunchaki teskarisi, shuning uchun bu yerda ular batafsil tavsiflanmaydi.

Lekin XOR va XNOR mantiqiy elementlari biroz o‘ziga xos.

XOR elementi kirishlar har xil ekanini (\(A \neq B\)) tekshiradi va agar shunday bo‘lsa, 1 chiqaradi. XOR dasturlashdagi A != B ifodasiga o‘xshaydi.

XNOR elementi kirishlar tengligini (\(A = B\)) tekshiradi va agar shunday bo‘lsa, 1 chiqaradi. XNOR dasturlashdagi A == B ifodasiga o‘xshaydi.

XOR va XNOR uchun rostlik jadvallari quyidagicha ko‘rinadi: