Mavzu: Mantiqiy funksiyalar va Bul algebrasini asoslari

Bul algebrasidan foydalanib Bul ifodalarini soddalashtirish. Mantiqiy qurilmani sintez qilish bir nechta bosqichlarga bo‘linadi. Birinchi bosqichda so‘z bilan, jadval ko‘rinishida yoki boshqa shakllarda berilgan funksiyalarni qandaydir bazisdan foydalanib, mantiqiy ifoda ko‘rinishida tasvirlash kerak. Keyingi bosqichlar, sintez jarayonida eng kam miqdordagi elektron asbob va qurilmaning funksio‘nal sxemasini ratsio‘nal qurishni ta’minlaydigan funksiyalarning eng kichik shakllarini hosil qilishga mo‘ljallanadi. Birinchi bosqich uchun mantiqiy qurilmani qurish uchun qanday bazis ishlatilganligidan qat’iy nazar, odatda “VA”, “YOKI”,“YO‘Q" bazisi qo‘llaniladi.
Keyingi almashtirishlarni osonlashtirish uchun, funksiyani tasvirlashning quyidagi ikki boshlang‘ich kanonik shakli qabul qilingan: mukammal diz’yunktiv normal shakl (MDNSh) va mukammal kon’yuktiv normal shakl (MKNSh).
Mukammal diz’yunktiv normal shakl (MDNSh). Diz’yunktiv normal shakl (MDNSh) deb, funklsiyaning shunday tasvirlash shakliga aytiladiki, bunda funksiyaning mantiqiy ifodasi har biri argumentlarning sodda konyunksiyasi yoki ularning inversiyasi bo‘lgan hadlar qatorining diz’yunksiyasi ko‘rinishida quriladi. DNSHga misol sifatida qo‘yidagi misolni keltiramiz:
f (x₁x₂ x₃ x₄ )  X₁  X₂ * X₃  X₁ * X₂ * X₃  X₂ * X₃ (3.1)
DNSh bo‘lmaydigan funksiyani tasvirlash shaklini keltiramiz. Masalan, quyidagi funksiya



f (x₁x₂ x₃ x₄ )  X₁  X₂ * X₃  X₁ * X₂ * X₃  X₂ * X₃
DNShda tasvirlanmagan, chunki oxirgi hadi argumentlarning sodda konyunksiyasi bo‘lmaydi.
Huddi shunday, funksiyani tasvirlashning qo‘yidagi shakli ham DNSH bo‘lmaydi:
f (x₁x₂ x₃ x₄ )  X₁ *( X₂ * X₃  X₂ * X₃ )  X₂ * X₃
Agar DNSh ning har bir hadida funksiyaning barcha argumentlari (yoki ularning inversiylari) tasvirlangan bo‘lsa, unda bunday shakl MDNSh deb ataladi. (3.1) ifoda MDNSh bo‘la olmaydi, chunki uning uchinchi hadigina funksiyaning barcha argumentlarini o‘z ichiga oladi.
DNShdan MDNShga o‘tishda barcha argumentlar tasvirlanmagan har bir hadiga ko‘rinishdagi ifodani kiritish kerak, bu yerda x_i-argumentdagi mavjud bo‘lmagan argument, bo‘lgani uchun bunday amal funksiyaning qiymatini o‘zgartira olmaydi. DNShdan MDNShga o‘tishni quyidagi ifoda ko‘rinishida ko‘rsatamiz.

f (x₁x₂ x₃ x₄ )  X₁ * (X ₂ * X ₂ ) * (X₃ * X₃ )  X ₂ * X₃ * (X₁  X₁)  X₁ * X ₂ *



* X₃  X₁ * X ₂ * X₃  X₁ * X ₂ * X₃  X₁ * X ₂ * X₃  X₁ * X ₂ * X₃  X₁ * X ₂ * X₃
(3.2)

Hadlarga