Калкулатор Булове алгебре

Минимизација Булових израза у дигиталној логици

Поједностављивање Булових израза представља један од основних корака у пројектовању дигиталних кола и оптимизацији софтверских услова. Ручно поједностављивање сложених логичких функција често је подложно грешкама и захтева примену бројних теорема Булове алгебре. Калкулатор Булове алгебре омогућава брзо и тачно свођење било ког Буловог израза на његове минималне математичке облике.

Алат истовремено израчунава два стандардна минимална облика: минимални збир производа (SOP) и минимални производ збирова (POS). Поред самих решења, корисник добија детаљан приказ поступка минимизације корак по корак, комплетну истинитосну таблицу за верификацију резултата, као и преглед свих примарних и суштинских примарних импликаната.

Улазни формати и подржани оператори

Алат прихвата унос Булових израза дужине до 2,000 знакова, при чему се за променљиве користе појединачна слова, а максималан број различитих променљивих је 6. Флексибилност уноса огледа се у подршци за различите нотационе системе — од инжењерских и програмерских записа, преко формалних логичких симбола, па све до текстуалних оператора. Различити стилови се могу слободно комбиновати унутар истог израза.

Следећи оператори су подржани за унос:

• AND (конјункција): Може се записати имплицитно спајањем слова (нпр. AB), помоћу тачке A·B, звездице A*B, програмерског оператора A && B, текстуално као A AND B, или одговарајућим логичким симболом. Низови од више слова, попут ABC, аутоматски се тумаче као конјункција A AND B AND C.
• OR (дисјункција): Записује се као A + B, A OR B, A || B или помоћу логичког симбола за дисјункцију.
• NOT (негација): Може се означити примом иза променљиве A', узвичником испред променљиве !A, текстуално као NOT A, или симболом негације ¬A.
• XOR (ексклузивна дисјункција): Препознаје се кроз записе A ^ B, A XOR B и A ⊕ B.
• NAND: Записује се као A NAND B или помоћу симбола ⊼.
• NOR: Записује се као A NOR B или помоћу симбола ⊽.
• Константе: Дозвољена је употреба логичких константи 0 и 1.

Кориснички интерфејс садржи опцију „Уметни оператор” за брзо уношење специфичних симбола, као и дугме „Очисти” за ресетовање уноса. За брзо тестирање функционалности доступни су унапред дефинисани примери кроз опцију „Пробајте израз”:

• „Спајање чланова” (пример за теорему консензуса)
• „Негирани производ” (пример за Де Морганове законе)
• „Тространи XOR” (пример са три променљиве)

Квајн–Макласкијева метода и проналажење импликаната

За разлику од хеуристичких метода које не гарантују увек апсолутно минималан облик, овај алат користи Квајн–Макласкијеву методу (Quine–McCluskey) са тачним минималним покривањем. Овај алгоритам је табеларна метода која је математички еквивалентна Карноовим картама (K-мапама), али је погоднија за рачунарску имплементацију јер систематски разматра све могућности спајања суседних појмова.

Процес почиње генерисањем истинитосне таблице и идентификацијом свих минтерма (редова где је излаз једнак 1). Спајањем суседних редова који се разликују за само један литерал, алгоритам постепено елиминише променљиве и формира примарне импликанте. Примарни импликанти представљају највеће могуће групе суседних јединица које се не могу даље спајати.

Након тога се издвајају суштински примарни импликанти — они који једини покривају барем један специфичан минтерм у таблици. Ако суштински импликанти не покрију све минтерме, преостали редови се затварају проналажењем минималног покривања са најмањим могућим бројем додатних чланова. Исти поступак се паралелно спроводи над макстермима (редовима где је излаз једнак 0) како би се добио минимални производ збирова (POS).

Разлике између SOP и POS облика у пракси

Приликом пројектовања дигиталних система, избор између збира производа (SOP) и производа збирова (POS) директно утиче на физичку реализацију кола:

У зависности од распореда нула и јединица у истинитосној таблици, један од ова два облика може захтевати значајно мањи број логичких капија и улаза (литерала), што директно смањује цену и кашњење у реалном хардверу. Због тога алат увек приказује оба решења упоредо.

Ограничења ручне минимизације

Ручна оптимизација помоћу Карноових карата је практична и визуелно јасна за изразе са 2, 3 или 4 променљиве. Међутим, када број променљивих пређе 4, Карноове карте постају тродимензионалне или захтевају вишеструке табеле, што драстично повећава могућност грешке.

Са 6 променљивих, истинитосна таблица има 64 реда (2⁶ = 64), што представља крајњу границу коју човек може ручно да анализира и провери у разумном року. Из тог разлога је овај алат ограничен на максимално 6 променљивих, чиме се обезбеђује да корак-по-корак извођење и истинитосна таблица остану потпуно читљиви и корисни за едукацију и верификацију.

Сигурност података и локална обрада

Сва израчунавања и поједностављивања Булових израза обављају се директно у веб-прегледачу корисника. Подаци и унети изрази се не шаљу на спољне сервере нити се чувају у облаку. Обрада се врши локално на уређају корисника, чиме се обезбеђује приватност унетих података током рада.

Често постављана питања

Који начини писања израза се препознају?
Све уобичајене конвенције се могу слободно комбиновати: инжењерски стил (AB + A'C, са имплицитним AND и примом за NOT), програмерски стил (A &&!B || C, A ^ B), логички симболи (¬ ∧ ∨ ⊕ ⊼ ⊽) и обичне речи (A AND B OR NOT C, NAND, NOR). Низови од више слова као што је ABC значе A AND B AND C, а речи AND, OR, NOT, XOR, NAND, NOR се увек тумаче као оператори.

Која је разлика између SOP и POS резултата?
Оба описују исту функцију. Збир производа (SOP) повезује оператором OR чланове повезане оператором AND, као што је AB' + BC, и директно се пресликава у AND–OR кола; производ збирова (POS) повезује оператором AND факторе повезане оператором OR, као што је (A + B)(B' + C), и пресликава се у OR–AND кола. У зависности од функције, једном облику може бити потребно мање логичких капија него другом, па алат увек приказује оба.

Како се проналази минимални облик?
Алат гради комплетну истинитосну таблицу, спаја суседне редове са вредношћу 1 у примарне импликанте (Quine–McCluskey метода), задржава суштинске и затвара све преостале редове тачним минималним покривањем. Резултат је гарантовано минималан за облик збира производа — то није хеуристика — а исти поступак на редовима са вредношћу 0 даје производ збирова.

Зашто је подржано највише 6 променљивих?
Шест променљивих већ даје истинитосну таблицу од 64 реда, што је отприлике граница онога што се још увек може ручно читати и проверавати. Преко тога, минимизација у теорији и даље ради, али извођење и таблица око којих је ова страница изграђена престају да буду корисни као доказ. Софтвер за пројектовање логичких кола са излазом у датотеку је бољи избор за шире функције.