Bul algebrasi - 3. Bul funktsiyalarini amalga oshirish

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.
|