Преглед на кодот на Минимизација на кола за Булови функции

Во [[Булова алгебра|Буловата алгебра]], минимизацијата на кола е проблем на добивање на најмалото [[логичко коло]] (Булова формула) кое претставува дадена [[Булова функција]] или [[таблица на вистинитост]]. Долго време се претпоставувало дека проблемот на неограничена минимализација на коло е <math>\Sigma_2^P</math>-комплетно,резултат кој конечно бил докажан во 2008 година, но постојат ефективни методи, како што се [[Карноовите мапи]] и [[Квин-Меккласки алгоритмот]] кои го олеснуваат процесот.

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

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

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

[[Податотека:Circuit-minimization.svg]]

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

== Литература ==
* 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. [[:en:Special:BookSources/9780521857482|ISBN 978-0-521-85748-2]], chapters 4–6
* {{Наведена книга|title = [[The Art of Computer Programming]]|year = 2010|last = Knuth|first = Donald E.|authorlink = Donald Knuth|volume = 4A|department= chapter 7.1.2: Boolean Evaluation|publisher = Addison-Wesley|pages = 96–133|isbn = 0-201-03804-8}}
* Multi-level minimization [https://www.ece.cmu.edu/~ee760/760docs/lec07.pdf part I], [https://www.ece.cmu.edu/~ee760/760docs/lec08.pdf partII]: CMU lectures slides by Rob A. Rutenbar

[[Категорија:Булова алгебра]]