Калкулатор за опростяване на булеви изрази

Опростяване на булеви изрази чрез алгоритъма на Quine–McCluskey

Проектирането на цифрови схеми и оптимизацията на софтуерни условия изискват представянето на логическите функции в техния най-компактен вид. Процесът на ръчно опростяване чрез законите на булевата алгебра или карти на Карно (K-maps) е податлив на грешки и става изключително труден при нарастване на броя на променливите. При повече от 4 променливи броят на комбинациите в таблицата за истинност достига 32 или 64, което прави ръчната проверка неефективна.

Този онлайн инструмент автоматизира процеса, като преобразува всеки булев израз до неговите две минимални математически форми: минимална сума от произведения (SOP) и минимално произведение от суми (POS). Оптимизацията се извършва чрез метода на Quine–McCluskey (метод на табличните съкращения), който гарантира намирането на точното минимално покритие, за разлика от евристичните подходи.

Поддържани формати и синтаксис на входните данни

Инструментът приема променливи, изписани като единични букви, и поддържа широк спектър от оператори, използвани в инженерните науки, програмирането и формалната логика. Потребителят може свободно да смесва следните означения:

• AND (Конюнкция): Може да се записва като подразбиращо се долепяне (например AB), с точка A·B, със звездичка A*B, с логически думи A AND B, с програмен оператор A && 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.

Входните параметри са ограничени до максимум 6 различни променливи и обща дължина на израза до 2,000 знака. За улеснение интерфейсът предлага бързи връзки за примерни изрази: „Сливане на членове“ (консенсусен пример), „Отрицание на произведение“ (пример за законите на Де Морган) и „Тройно XOR“. Бутонът „Изчистване“ нулира въведеното съдържание.

Анализ на изходните резултати и диагностика

След въвеждане на израза, инструментът извършва незабавно изчисление в браузъра на потребителя. Резултатите се представят в няколко специализирани секции:

1. Разчетено като: Показва нормализираната интерпретация на въведения от потребителя израз, за да се потвърди правилното разчитане на операторите.
2. Минимална сума от произведения (SOP): Крайната оптимизирана дизюнктивна нормална форма, състояща се от AND-членове, свързани с OR.
3. Минимално произведение от суми (POS): Крайната оптимизирана конюнктивна нормална форма, състояща се от OR-членове, свързани с AND.
4. Накратко: Диагностичен панел, който обобщава ключовите параметри на функцията:
   • Променливи: Списък на откритите уникални променливи.
   • Редове, равни на 1: Списък или брой на минтермите.
   • Прости импликанти: Общият брой на намерените прости импликанти.
   • Съществени прости импликанти: Броят на импликантите, които задължително трябва да участват в покритието.
   • Литерали, преди → след: Сравнение на броя на литералите в първоначалния и в оптимизирания израз.
   • Метод: Използваният алгоритъм, изписан като „Quine–McCluskey, точно минимално покритие“.

Всеки резултат може да бъде лесно запазен чрез бутона „Копиране на резултата“.

Детайлно описание на стъпките по минимизация

В секцията „Как беше опростен“ се извежда пълният математически ход на решението:

• Определяне на пространството: В зависимост от броя на променливите се изписва съобщение за размера на таблицата за истинност. Например: „Изразът използва ‹count› променливи (‹variables›), така че таблицата за истинност има ‹rows› реда.“ (или съответните съобщения за една променлива или за константен израз без променливи).
• Идентифициране на редовете: Посочват се минтермите и макстермите във формат: „Той е равен на 1 за редовете Σm(‹minterms›) и на 0 за редовете ΠM(‹maxterms›).“.
• Намиране на простите импликанти: Описва се първият етап на алгоритъма на Quine–McCluskey: „Сливането на съседни редове с 1 доколкото е възможно оставя ‹count› прости импликанти: ‹list›.“.
• Определяне на съществените импликанти: Посочват се тези импликанти, които покриват уникален минтерм: „Съществени прости импликанти — единственото останало покритие за поне один ред: ‹list›.“ При липса на такива се извежда: „Нито една проста импликанта не е съществена: всеки ред с 1 може да бъде покрит по повече от един начин.“.
• Покриване на останалите редове: Ако съществените импликанти не покриват всички минтерми, се прилага оптимизационна процедура: „Останалите непокрити редове се затварят с възможно най-малко допълнителни членове: ‹list›.“ В противен случай се изписва: „Съществените прости импликанти вече покриват всеки ред с 1, така че сумата е пълна.“.
• Генериране на POS: Описва се дуалната процедура: „Изпълнението на същото сливане върху редовете с 0 дава минималното произведение от суми ‹pos›.“.
• Верификация: Процесът завършва с потвърждението: „Двете минимални форми съвпадат с оригиналния израз на всички ‹rows› реда от таблицата за истинност.“.

За визуално потвърждение се генерира пълна „Таблица за истинност“, съдържаща колони за всяка променлива, оригиналния израз (колона „Израз“) и опростения вариант (колона „Минимална SOP“).

Правила за обработка, ограничения и грешки

Инструментът стриктно следи за коректността на въведения синтаксис и налага следните ограничения:

• Лимит на променливите: Поддържат се до 6 уникални променливи. При превишаване се задейства съобщението: „Този израз използва ‹count› различни променливи; опростителят поддържа до 6.“.
• Дължина на низа: При изрази над 2,000 знака се показва грешката: „Дължината на израза трябва да бъде под 2,000 знака.“.
• Константни функции: Ако изразът е тавтология, се извежда съобщението: „Този израз винаги е 1: всяка комбинация от стойности го прави истина.“. За противоречия се извежда: „Този израз винаги е 0: нито една комбинация от стойности не го прави истина.“. В общия статус се изписва: „Този израз е константа: той винаги е равен на ‹value›.“.
• Вече минимален израз: Ако входният израз не подлежи на допълнително опростяване, се изписва: „Вашият израз вече е минимална сума от произведения.“.

При синтактични грешки се визуализират следните съобщения:

• При празно поле: „Въведете булев израз.“.
• При неподдържан символ: „"‹char›" (позиция ‹position›) не е булев оператор, променлива или константа.“.
• При липсващ операнд: „Липсва операнд до оператор близо до позиция ‹position› — проверете за незавършен + · или ⊕.“.
• При некоректни скоби: „Скобите не са балансирани — добавете или премахнете скоба.“.

Поверителност на данните

Всички изчисления и логически трансформации се извършват локално в уеб браузъра на потребителя. Въведените булеви изрази и междинните таблици за истинност се обработват изцяло на вашето устройство и никога не се изпращат или съхраняват на външни сървъри.

Често задавани въпроси (FAQ)

Защо се поддържат най-много 6 променливи?
Шест променливи вече генерират таблица за истинност с 64 реда, което е приблизително лимитът за лесно четене и ръчна проверка. Отвъд това минимизирането на теория продължава да работи, но извеждането и таблицата, около които е изградена тази страница, престават да бъдат полезни за онагледяване. Софтуерът за проектиране на логически схеми с изход във файл е по-подходящ за по-широки функции.

Как се намира минималната форма?
Инструментът изгражда пълната таблица за истинност, слива съседните редове с единица в прости импликанти (метод на Quine–McCluskey), запазва съществените от тях и покрива останалите редове с точно минимално покритие. Резултатът е гарантирано минимален за формата сума от произведения (SOP) — това не е евристика — а същата процедура върху редовете с нула дава произведението от суми (POS).

Кои начини на изписване на израза се разпознават?
Всички често срещани конвенции могат да се смесват свободно: инженерен стил (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. В зависимост от функцията едната форма може да изисква по-малко логически елементи от другата, затова инструментът винаги показва и двете.