8-ma'ruza Ventillar va Bul algebrasi Reja

8.2. Bul algebrasi

Turli xil vetillarni birlashtirish orqali olingan aylanishlarni tavsiflash uchun algebraning maxsus turi kerak, unda barcha o'zgaruvchilar va funktsiyalar faqat ikkita qiymatni olishi mumkin: 0 va 1. Bunday algebra Bul deb nomlanadi. U ingliz matematiki Jorj Bulning sharafiga qo'yilgan (1815–1864). Aslida, bu holda biz Bul algebrasining maxsus turi, xususan, o'rni elektron algebrasi haqida gapirayapmiz, ammo "Bul algebra" atamasi "o'rni elektron algebrasi" ma'nosida juda ko'p ishlatiladi, shuning uchun biz ularni ajratmaymiz.

Oddiy algebrada bo'lgani kabi (ya'ni maktabda o'rganiladigan bo'lsa), buing algebrasi ham o'z funktsiyalariga ega. Bul funktsiyasi bir yoki bir nechta o'zgaruvchini kirish sifatida qabul qiladi va faqat ushbu o'zgaruvchilarning qiymatlariga bog'liq bo'lgan natijani beradi. Siz oddiy funktsiyani f (A) = 1, agar A = 0 va f (A) = 0, agar A = 1 deb aytsangiz, bunday funktsiya NOT funktsiyasi bo'ladi (3.2, a-rasmlarga qarang).
N o'zgaruvchisining Bul funktsiyasi o'zgaruvchan qiymatlarning atigi 2 n mumkin bo'lgan kombinatsiyasiga ega bo'lganligi sababli, bunday funktsiyani 2 n qatorli jadvalda to'liq tavsiflash mumkin. Har bir satr o'zgaruvchan qiymatlarning turli xil kombinatsiyalari uchun funktsiya qiymatini beradi. Bunday jadval haqiqat jadvali deb ataladi. Barcha jadvallar sek. 3.2 - haqiqat jadvallari. Agar biz haqiqat jadvalining satrlarini har doim raqamlar tartibida, ya'ni 00, 01, 10, 11 tartibidagi ikkita o'zgaruvchiga tartiblashtirishga rozi bo'lsak, unda funktsiyani jadvaldagi natijalar ustunini vertikal ravishda o'qish orqali olingan 2 n-bitli ikkilik raqam bilan to'liq tavsiflash mumkin. haqiqat. Shunday qilib, NOT-AND 1110, NOT-OR 1000, and 0001 va OR 0111 bo'ladi. Shubhasiz, ikkita o'zgaruvchining 16 ta mantiqiy funktsiyalari mavjud bo'lib, ular 16 ta mumkin bo'lgan 4 bitli satrlarga mos keladi. Oddiy algebrada, aksincha, ikkita o'zgaruvchida cheksiz sonli funktsiyalar mavjud va ularning hech biri kirish funktsiyasining barcha ruxsat etilgan qiymatlari uchun ushbu funktsiyaning qiymatlari jadvali bilan tavsiflanishi mumkin emas, chunki har bir o'zgaruvchi cheksiz ko'p qiymatlarni olishi mumkin.
3.3, a rasmda uchta o'zgaruvchining Bul funktsiyasi uchun haqiqat jadvali ko'rsatilgan: M = f (A, B, C). Agar ko'p o'zgaruvchilar 0 bo'lsa, aksariyat o'zgaruvchilar bo'lsa 1 qiymatini oladi

8.3-rasm. Uchta o'zgaruvchilar (a) funktsiyasi uchun haqiqat jadvali; ushbu funktsiyani amalga oshirish sxemasi (в)

Yozuvning boshqa turini ko'rish uchun, shuni esda tutingki, har qanday Bul funktsiyasi funktsiyani bitta bo'lishiga olib keladigan kirish o'zgaruvchan qiymatlarining kombinatsiyasini ko'rsatib aniqlanishi mumkin. 3.3, a-rasmdagi funktsiya uchun o'zgaruvchilarning 4 kombinatsiyasi mavjud bo'lib, ular funktsiya uchun birlik qiymatini beradi. O'zgaruvchining ustiga uning qiymatini o'zgartirilishini bildirish uchun bar chizamiz. Barning yo'qligi o'zgaruvchining qiymati teskari o'zgartirilmasligini anglatadi. Bundan tashqari, biz Bul AND funktsiyasini (bu belgini qoldirib yuborish mumkin) va qo'shimcha belgini (+) Bul OR funktsiyasini belgilash uchun ko'paytirish belgisini (nuqta) ishlatamiz. Masalan, ABC 1 ga teng, faqat A = 1, B = 0 va C = 1. Bundan tashqari, AB + BC faqat (A = 1 va B = 0) yoki (B = 1 va C = bo'lsa) bo'ladi. 0). Rasmdagi jadval. 3.3 va funktsiya to'rtta satrda 1 qiymatini oladi: ABC, ABC, ABC va ABC. Agar ushbu to'rtta shartdan bittasi to'g'ri bo'lsa, M funktsiyasi (ya'ni 1) to'g'ri. Shunday qilib, biz yoza olamiz

M = ABC + ABC + ABC + ABC.
Bu ixcham haqiqat jadvalining kirishidir. Shunday qilib, n o'zgaruvchilar funktsiyasini ko'pi bilan 2 n "mahsulot" ning "yig'indisi" bilan tavsiflash mumkin, bunda har bir "mahsulot" n omillarni o'z ichiga oladi. Yaqinda ko'rib chiqamiz, bu shakllantirish ayniqsa muhimdir, chunki u ushbu funktsiyani standart ventillar yordamida amalga oshirishga imkon beradi.
Mavhum bulyon funktsiyasi va uning elektron bajarilishi o'rtasidagi farqni tushunish muhimdir. Bul funktsiyasi A, B va C kabi parametrlarga, shuningdek, AND, OR va NOT operatorlariga ega. Bul funktsiyasi haqiqat jadvali yoki maxsus belgi yordamida tasvirlangan, masalan:
F = ABC + ABC.
Bul funktsiyasi kirish, chiqish parametrlari va AND, OR va NOT kabi ventillarni bildiruvchi signallardan foydalangan holda elektron usulda (ko'pincha har xil usullar bilan) amalga oshirilishi mumkin.

8.3 Bul funktsiyalarini bajarish

Yuqorida ta'kidlab o'tilganidek, Bul funktsiyasini ko'pi bilan 2 n mahsulot yig'indisi sifatida ifodalash bizni to'g'ridan-to'g'ri ushbu funktsiyani amalga oshirishga olib keladi. Shaklda 3.3, b, A, B va C kirish signallari chap tomonda ko'rsatilgan va chiqish paytida olingan M funktsiyasi o'ng tomonda ko'rsatilgan. Kirish parametrlari teskari aylantirilishi kerakligi sababli, signal 1, 2 va 3 invertorlari orqali o'tadi. Shaklni yanada aniqroq qilish uchun biz 6 ta vertikal chiziq chizdik, ulardan 3 tasi kirish o'zgaruvchilari bilan, 3 tasi o'zlarining inversiyalari bilan. Ushbu chiziqlar kirish signalini ventillarga o'tkazadi. Masalan, 5, 6 va 7 shlyuzlar A signalini qabul qiladilar. Haqiqiy zanjirda, bu ventillar hech qanday oraliq vertikal simlarsiz to'g'ridan-to'g'ri A ga ulanishi mumkin.

O'chirish sxemasida to'rtta VA ventillar mavjud bo'lib, M uchun tenglamada har bir davr uchun bitta (ya'ni 1 natijasi bilan haqiqat jadvalidagi har bir satr uchun bittadan). Har bir AND ventilsi haqiqat jadvalining ko'rsatilgan satrlaridan birini baholaydi. Oxir-oqibat, ushbu mahsulotlarning barchasi yakuniy natijani olish uchun yig'iladi (OR operatsiyasini anglatadi).
3.3, b rasmga qarang. Biz quyidagi konventsiyadan foydalanamiz: agar rasmdagi ikkita chiziq kesishsa, munosabatlar faqat chorrahada qalin nuqta bo'lsa, nazarda tutiladi. Masalan, 3-ventilning chiqishi barcha 6 vertikal chiziqlarni kesib o'tadi, lekin u faqat S chizig'i bilan bog'liq bo'lib, boshqa kitoblar turli xil konventsiyalardan foydalanishlari mumkinligini unutmang. Shakldan. 3.3 har qanday mantiqiy funksiya uchun kontaktlarning zanglashiga olib borish kerakligi aniq bo'lishi kerak:
1. Ushbu funktsiya uchun haqiqat jadvalini tuzing.
2. Har bir kirish signalini o'zgartirishi uchun kontaktlarning zanglashiga olib keladigan invertorlarni qo'shing.
3. 1 natijasi bilan haqiqat jadvalining har bir qatori uchun AND ventilsini chizing.
4. AND ventillarini mos keladigan kirishga ulang.
5. Barcha va ventillarning chiqishlarini chiqaring va ularni OR ventilsining kirishiga yo'naltiring.
NOT, AND va OR ventillari yordamida har qanday Bul funktsiyasini qanday amalga oshirishni ko'rsatdik. Biroq, bitta turdagi shlyuzdan foydalanib, aylanishlarni qurish ancha qulaydir. Yaxshiyamki, oldingi algoritmdan foydalanib qurilgan aylanishlar osonlikcha NOT-AND yoki NOT-OR shaklida aylantiriladi. Bunday konversiyani amalga oshirish uchun kerak bo'lgan narsa - bitta, bitta ventildan foydalangan holda NOT, AND va OR ventillarini amalga oshirish. 3.4-rasmda EMAS yoki YO'Q yoki EMAS ventillari asosida buni qanday qilish kerakligi ko'rsatilgan. (Ushbu konversiya arzimas, ammo boshqa variantlar ham mavjud).



8.4-rasm. INKOR, YOKI va VA ventillarini faqat VF-EMAS yoki YOKI-EMAS ventillari yordamida yaratish