Бульдік функциялардың канондық түрлері

Кіріспе

Бульдік функциялардың стандартты формалары

Буль алгебрасында кез келген Бульдік функцияны канондық дизъюнктивті қалыпты формада (CDNF) немесе минотермикалық канондық формада, сондай-ақ оның қос формасы – канондық конъюнктивті қалыпты формада (CCNF) немесе макситермикалық канондық формада көрсетуге болады. Басқа канондық формаларға жай импликанттардың толық қосындысы немесе Блейк канондық формасы (және оның қосы) және алгебралық қалыпты форма (Жегалькин немесе Рид-Мюллер формасы деп те аталады) жатады. Минотермдер айнымалылардың логикалық АНД (ЖӘНЕ) комбинациясы болғандықтан "көбейтінділер" деп аталады, ал максимумдар айнымалылардың логикалық ИЛИ (ЖӘНЕ) комбинациясы болғандықтан "қосындылар" деп аталады. Бұл ұғымдар Де Морган заңдарында көрсетілгендей, олардың толықтырғыш симметриялық қатынастарына байланысты қос болып табылады. Кез келген Бульдік функцияның екі қос канондық формасы – "минотермдердің қосындысы" және "макситермдердің көбейтіндісі". "Көбейтінділердің қосындысы" (SoP немесе SOP) термині минотермдердің дизъюнкциясы (ИЛИ) болатын канондық форманы белгілеу үшін кеңінен қолданылады. Оның Де Морган қосы – максимумдардың конъюнкциясы (АНД) болатын канондық форманың "Қосындылардың көбейтіндісі" (PoS немесе POS). Бұл формалар аталған функцияларды жеңілдетуге көмектеседі, бұл Бульдік формулаларды және әсіресе цифрлық тізбектерді оңтайландыруда маңызды рөл атқарады.

Ақшалай мерзімдер

Өзгергіштердің бульдік функциясы үшін, әрбір өзгергіш бір рет кездесетін (толықтырылған немесе толықтырылмаған түрінде) өнім термині – minterm деп аталады. Демек, minterm – тек толықтыру операторы мен конъюнкция операторын қолданатын n өзгергіштің логикалық өрнегі. Мысалы, , және – үш өзгергіштің (a, b, c) Бульдік функциясы үшін 8 minterm-нің 3 мысалы. Соңғысы әдетте "a ЖӘНЕ b ЖӘНЕ c-нің жоғы" деп оқылады.

n өзгергіш үшін 2n minterm болады, себебі minterm өрнегіндегі әрбір өзгергіш тікелей немесе толықтырылған түрінде болуы мүмкін – әрбір өзгергіш үшін екі таңдау.

Минотермдерді индекстеу

Минотермдер әдетте өзгермелілердің толықтыру схемасының екілік кодтамасы арқылы нөмірленеді, мұнда өзгермелілер стандартты ретпен, әдетте әліпбилік ретпен жазылады. Бұл конвенция тікелей түріне 1 және толықтырылған түріне 0 мәнін тағайындайды; содан кейін минотерм мысалы, минотерм 1102 = 610 ретімен нөмірленеді және деп белгіленеді.

Макстермдерді индекстеу

Әрбір maxterm-ге minterms үшін қолданылатын дәстүрлі екілік кодтаманың керісіне негізделген индекс тағайындалады. Maxterm конвенциясы тікелей түріне 0, ал толықтырылған түріне 1 мәнін береді. Мысалы, (110) maxterm-іне 6 индексін тағайындаймыз және осы maxterm-ді M6 деп белгілейміз. Сол сияқты, осы үш айнымалы үшін M0 (000) болады, ал M7 (111) болады.

Дуализация

Минимумның толықтығы - тиісті максимум. Бұл де Морган заңы арқылы оңай тексеріледі. Мысалы:

Қолданба үлгісі

Жоғарыда келтірілген минтермдер мен макстермдердің шындық кестелерінің үлгілері екілік сандарды қосуда бір бит позициясының канондық түрін анықтауға жеткілікті, бірақ AND және OR қақпалары инвентаризациясыңызда болмаса, цифрлық логиканы жобалау үшін жеткіліксіз. Егер өнімділік маңызды болса (мысалы, «Аполлон» басқару компьютерінде), транзисторлық логиканың ішкі толықтыру қасиетіне байланысты қолда бар бөліктердің NAND және NOR болуы ықтимал. Мәндер кернеу күйлері ретінде анықталады, біреуі жерге жақын, екіншісі – тұрақты ток көзінің кернеуіне (Vcc) жақын, мысалы +5 В. Егер жоғары кернеу 1-дің «нағыз» мәні ретінде анықталса, NOR қақпасы – ең қарапайым және пайдалы логикалық элемент болып табылады. Нақтырақ айтқанда, 3 кіріс NOR қақпасы 3 биполярлық тоқ өткізгіш транзисторлардан тұруы мүмкін, олардың барлық эмиттерлері жерге қосылған, коллекторлары біріктірілген және жүктеме кедергісі арқылы Vcc-ге қосылған. Әрбір база кіріс сигналына қосылады, ал ортақ коллектор нүктесі шығыс сигналын ұсынады. Базасына 1 (жоғары кернеу) келген кез келген кіріс транзистордың эмиттерін коллекторымен қысқа тұйықталады, бұл жүктеме кедергісі арқылы ток ағынына себеп болады, осының нәтижесінде коллектор кернеуі (шығысы) жерге өте жақын болады. Бұл нәтиже басқа кірістерге тәуелсіз. Тек барлық 3 кіріс сигналы 0 (төмен кернеу) болған жағдайда ғана барлық 3 транзистордың эмиттер-коллектор кедерімі өте жоғары болады. Содан кейін өте аз ток ағып, жүктеме кедергісімен кернеуді бөлу әсері коллектор нүктесіне Vcc-ге өте жақын жоғары кернеуді қосады. Бұл қақпа схемаларының толықтыру қасиеттері канондық түрде функцияны жүзеге асыруға тырысқанда кемшілік сияқты көрінуі мүмкін, бірақ оны өтеуге болатын артықшылығы бар: тек бір кірісі бар мұндай қақпа толықтыру функциясын жүзеге асырады, ол цифрлық логикада жиі қажет болады. Бұл мысал «Аполлон» бөліктерінің инвентаризациясын қарастырады: тек 3 кіріс NOR қақпалары, бірақ талқылауды жеңілдету үшін 4 кіріс NOR қақпалары да қолда бар деп есептеуге болады («Аполлон» жүйесінде олар 3 кіріс NOR қақпаларының жұптарынан құралған).

The sample truth tables for minterms and maxterms above are sufficient to establish the canonical form for a single bit position in the addition of binary numbers, but are not sufficient to design the digital logic unless your inventory of gates includes AND and OR. Where performance is an issue (as in the Apollo Guidance Computer), the available parts are more likely to be NAND and NOR because of the complementing action inherent in transistor logic. The values are defined as voltage states, one near ground and one near the DC supply voltage Vcc, e. g. +5 VDC. If the higher voltage is defined as the 1 "true" value, a NOR gate is the simplest possible useful logical element. Specifically, a 3 input NOR gate may consist of 3 bipolar junction transistors with their emitters all grounded, their collectors tied together and linked to Vcc through a load impedance. Each base is connected to an input signal, and the common collector point presents the output signal. Any input that is a 1 (high voltage) to its base shorts its transistor's emitter to its collector, causing current to flow through the load impedance, which brings the collector voltage (the output) very near to ground. That result is independent of the other inputs. Only when all 3 input signals are 0 (low voltage) do the emitter collector impedances of all 3 transistors remain very high. Then very little current flows, and the voltage divider effect with the load impedance imposes on the collector point a high voltage very near to Vcc. The complementing property of these gate circuits may seem like a drawback when trying to implement a function in canonical form, but there is a compensating bonus: such a gate with only one input implements the complementing function, which is required frequently in digital logic. This example assumes the Apollo parts inventory: 3 input NOR gates only, but the discussion is simplified by supposing that 4 input NOR gates are also available (in Apollo, those were compounded out of pairs of 3 input NORs).

Цифрлық схемаларды жобалауда қолдану

Буль алгебрасының бір қолданылуы – цифрлық схемаларды жобалау, мұндағы мақсаттардың бірі – қақпалардың санын барынша азайту, ал екіншісі – тұрақтандыру уақытын қысқарту. Екі өзгерушінің он алты мүмкін функциясы бар, бірақ цифрлық логикалық құрылғыларда ең қарапайым қақпа схемалары олардың төртеуін ғана іске асырады: конъюнкция (AND), дизъюнкция (қосымша OR) және олардың тиісті инверсиялары (NAND және NOR). Көптеген қақпа схемалары екіден астам кіріс айнымалысын қабылдайды; мысалы, ғарышқа ұшқан «Аполлон» басқару компьютері, 1960 жылдары интегралды схемаларды қолдануды алғаш рет енгізген, тек бір типті қақпа – 3 кіріс NOR қақпасымен құрастырылған, оның шығысы тек барлық 3 кіріс те жалған болғанда ғана дұрыс мән береді.