Минимизација на кола за Булови функции

Во Буловата алгебра, минимизацијата на кола е проблем на добивање на најмалото логичко коло (Булова формула) кое претставува дадена Булова функција или таблица на вистинитост. Долго време се претпоставувало дека проблемот на неограничена минимализација на коло е $\Sigma _{2}^{P}$ -комплетно,резултат кој конечно бил докажан во 2008 година, но постојат ефективни методи, како што се Карноовите мапи и Квин-Меккласки алгоритмот кои го олеснуваат процесот.

Цел

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

Пример

Иако постојат многу начини да се минимализира (намали) колото, овој е пример кој ја минимализира (или поедноставува) Буловата функција. Треба да се забележи дека Буловата функција, извршена со помош на колото е директно поврзана со алгебарскиот израз од кој се имплементира . функцијата. Да го разгледаме колото кое се користи за да се претстави $(A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)$ .Очигледно е дека тука се употребени две негации, две конјункции и дисјункција. Тоа значи дека за да се изгради колото потребни се два инвертора, две И порти и ИЛИ порта.

Колото може да се поедностави со примена на логички идентитети или со помош на интуиција. Поради тоа што примерот укажува дека А е точно кога Б е неточно или обратно, може да заклучиме дека тоа едноставно значи дека $A\neq B$ . Во однос на логичките врати, нееднаквоста едноставно значи ИКСИЛИ порта(исклучиво ИЛИ). Според тоа, $(A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B$ .Двете кола дадени подолу се еквивалентни:

Дополнително може да ја проверите точноста на резултатот со користење на таблица на вистинитост.

Литература

De Micheli, Giovanni. Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994, Part III, Logic-Level Synthesis and Optimization
Zvi Kohavi, Niraj K. Jha. Switching and Finite Automata Theory. 3rd ed. Cambridge University Press. 2009. ISBN 978-0-521-85748-2, chapters 4–6
Knuth, Donald E. (2010). The Art of Computer Programming. chapter 7.1.2: Boolean Evaluation. 4A. Addison-Wesley. стр. 96–133. ISBN 0-201-03804-8.
Multi-level minimization part I, partII: CMU lectures slides by Rob A. Rutenbar