Pagsusuri at synthesis ng mga lohikal na aparato. Mga pamamaraan para sa pagliit ng mga lohikal na function at circuit. Pagmomodelo ng matematika ng plastic deformation ng mga kristal

Kapag nagdidisenyo ng digital na automata, ang mga pamamaraan para sa pagliit ng mga function ng Boolean ay malawakang ginagamit upang makakuha ng mga circuit na matipid sa gastos. Pangkalahatang gawain Ang pag-minimize ng mga function ng Boolean ay maaaring mabuo tulad ng sumusunod: maghanap ng analytical expression para sa isang ibinigay na function ng Boolean sa isang form na naglalaman ng pinakamababang posibleng bilang ng mga titik.

Ang mga pamamaraan ng pag-minimize ay batay sa operasyon ng gluing (algorithm para sa pagsasama-sama ng kalapit binary na mga numero):

kung saan ang A ay isang pang-elementarya na pang-ugnay.

Sa expression, ang mga termino ay magkatabing binary na mga numero na naiiba sa bawat isa sa pamamagitan lamang ng isang digit. Kapag nagsasagawa ng isang gluing operation sa dalawang katabing numero, ang isang variable ay hindi kasama mula sa set, na nakikilala ang isang numero mula sa isa pa, sa apat na pares na magkatabi na mga numero - dalawang variable, sa walong - tatlong variable, atbp.

Ang minimum na disjunctive normal form (MDNF) ng isang Boolean function ay ang DNF na naglalaman ng pinakamaliit na bilang ng mga letra (na may kaugnayan sa lahat ng iba pang DNF na kumakatawan sa isang partikular na Boolean function).

I-minimize ang mga function, ibig sabihin, hanapin ang pinakasimpleng expression para sa orihinal na function Pwede iba't ibang pamamaraan. Ang lahat ng mga ito ay halos naiiba lamang sa unang yugto - ang yugto ng pagkuha ng pinaikling DNF. Dapat tandaan na, sa kasamaang-palad, ang paghahanap para sa MDNF ay palaging nauugnay sa ilang paghahanap para sa mga solusyon. Tingnan natin ang ilan sa kanila.

Pag-minimize ng Mga Kumplikadong Boolean Expression Gamit ang Carnot Matrix

Upang ipatupad ang pagsasama-sama ng algorithm, kinakailangan na maghanap ng mga kalapit mula sa buong hanay ng mga mandatoryong nasasakupan sa perpektong disjunctive normal na anyo ng isang lohikal na algebra function. Upang makahanap ng mga kalapit na nasasakupan, ginagamit ang mga Carnot matrice, isang sala-sala ng mga kalapit na numero, at mga talahanayan ng mga kalapit na nasasakupan.

Maipapayo na gumamit ng Carnot matrices upang mabawasan ang FAL sa mga set ng 2,3,4,5 at 6 na variable. Ang mga numero ng column sa Carnot matrice ay bumubuo ng hindi bababa sa makabuluhang mga digit, at ang mga row na numero ay bumubuo ng pinakamahalagang digit ng mga set. Binubuo ang mga cell number ng mga numero ng row at column at tumutugma sa mga hanay ng mga variable.

Isaalang-alang natin ang Carnot matrix para sa isang logical algebra function sa set ng 4 na variable (Talahanayan 1).

Talahanayan 1. Carnot matrix

Ang mga column at row sa matrix na ito ay itinalaga ng binary na katabing numero: 00-0I-II-I0. Samakatuwid, ang mga bilang ng pahalang at patayong katabi na mga cell, pati na rin ang mga pinakalabas na mga cell sa mga hilera at column, ay mga magkatabing numero, halimbawa:

mga cell na may mga numero at;

mga cell na may mga numero;

mga cell na may mga numero.

Upang mabawasan ang isang logical algebra function na tinukoy sa perpektong disjunctive normal form gamit ang Carnot matrix, kinakailangan na: ihanda ang Carnot matrix sa pamamagitan ng pagsusulat ng mga unit sa mga cell na naaayon sa mga mandatoryong constituent, pagsamahin ang mga cell na may mga unit sa "subcubes", isulat ang minimized logical algebra function sa disjunctive normal form.

Ang mga "subcubes" ay pinagsama:

- dalawang cell na may mga numero na magkatabing mga numero, habang ang isang variable ay hindi kasama;
- apat na mga cell (hilera, haligi, parisukat, sulok na mga cell), habang ang dalawang variable ay hindi kasama;
- walong cell (dalawang katabi o matinding row (column)), habang ang tatlong variable ay hindi kasama.

Upang magbigay ng isang pagbubukod posible higit pa variable, ang mga sukat ng "subcubes" ay dapat na kasing laki hangga't maaari, at ang kanilang bilang kaunti hangga't maaari. Para sa layuning ito, maaari mong gamitin ang parehong cell na may isang yunit ng ilang beses, kasama ito sa iba't ibang "subcubes". Ang bilang ng mga termino sa isang pinaliit na logical algebra function ay katumbas ng bilang ng mga subcube at mga cell na may mga yunit na hindi pinagsama sa mga subcube.

Hayaang i-minimize ang sumusunod na logical algebra function:

Ang Carnot matrix, na napunan alinsunod sa formula na ito, ay maaaring ipakita sa anyo ng Talahanayan 2:

Talahanayan 2. Carnot matrix

Sa matrix na ito, maaaring makilala ang dalawang dalawang-cell na subcubes. Bilang resulta ng minimization ay makukuha natin susunod na function lohika ng algebra:

Pamamaraan ni Quine

Upang makuha ang pinakamaliit na anyo ng isang lohikal na pag-andar, kinakailangan na gawin ang lahat ng posibleng gluing at pagsipsip sa perpektong disjunctive normal na anyo ng function (PDNF) upang ang resulta ay isang pinababang disjunctive normal na anyo ng function. (DNF).Sa pangkalahatang kaso, ang pinababang DNF ay maaaring maglaman ng mga karagdagang pangunahing implikasyon, na dapat matukoy sa ikalawang yugto ng pag-minimize.

Sa unang yugto, ang isang paglipat ay ginawa mula sa isang function na tinukoy sa DNF form sa isang pinababang DNF. Ang kakanyahan ng pamamaraan ay ang sunud-sunod na pagsasagawa ng lahat ng posibleng gluings at pagkatapos ay ang lahat ng pagsipsip, na humahantong sa isang pinababang DNF. Ang pamamaraan ay naaangkop sa perpektong DNF. Mula sa kaugnayan ng pagsipsip ay sumusunod na ang isang di-makatwirang elementong produkto ay hinihigop ng alinmang bahagi nito. Upang patunayan ito, ito ay sapat na upang ipakita na ang isang arbitrary prime implicant p = x i1 x i2... x sa maaaring matanggap. Sa katunayan, inilalapat ang paglalahad ng operasyon sa p (ang kabaligtaran ng operasyon ng gluing):

para sa lahat ng nawawalang variable x ik , ..., x im ang orihinal na function f, nakukuha natin ang set S ng mga constituent ng pagkakaisa. Sa pamamagitan ng gluing magkasama ang lahat ng mga constituents mula sa S makuha namin ang implicant p. Ang huli ay halata, dahil ang gluing operation ay ang kabaligtaran ng paglalahad ng operasyon. Ang hanay ng S ng mga nasasakupan ay kinakailangang naroroon sa isang perpektong DNF ng isang function f dahil ang p ang implicant nito.

Bilang resulta ng gluing, ang isang conjunction ng n-1 ranggo ay nakuha, at ang mga conjunctions ay nananatili sa orihinal na expression at lumahok sa paghahambing sa iba pang mga miyembro ng SDNF. Kaya, posibleng bawasan ang ranggo ng mga termino.

Ginagawa ang gluing at absorption hangga't may mga miyembro na hindi nakilahok sa pairwise comparison. Ang mga termino na sumailalim sa gluing operation ay minarkahan. Ang mga hindi namarkahang termino ay mga pangunahing implikasyon at kasama sa pinaikling DNF. Ang lahat ng mga minarkahang conjunction ng ranggo n-1 ay muling sumasailalim sa gluing operation hanggang sa makuha ang mga termino ng ranggo n-2, at iba pa hanggang sa ang bilang ng mga unmarked conjunctions ay mas malaki sa 2. Bilang resulta ng unang yugto, isang pinababang DNF ay nakuha.

Ang resultang lohikal na pagpapahayag ay hindi palaging minimal. Sa ikalawang yugto, lumipat sila mula sa pinababang DNF patungo sa mga dead-end na DNF at pinipili ang MDNF sa kanila.

Upang bumuo ng mga dead-end na DNF, isang implicant na talahanayan (matrix) ang itinayo, ang mga hilera nito ay minarkahan ng mga simpleng implicants ng pinaikling DNF, at ang mga column na may mga constituent ng unit ng orihinal na SDNF. Sa linya sa tapat ng bawat simpleng implicant, isang marka ang inilalagay sa ilalim ng mga set na iyon (constituents ng unit) kung saan kumukuha ito ng value na 1. Ang mga kaukulang constituent ay hinihigop (covered) ng simpleng implicant na ito.

Mula sa kabuuang bilang ng mga pangunahing implikasyon, kinakailangang piliin ang kanilang pinakamababang bilang, na inaalis ang mga hindi kailangan. Ang pagbuo ng mga dead-end na form at ang pagpili ng minimal na saklaw ay nagsisimula sa pagtukoy ng mga obligatoryong pangunahing implikasyon, iyon ay, yaong (at sila lamang) ang sumasaklaw sa ilang paunang hanay. Tingnan natin ang halimbawa ng pagliit ng isang lohikal na function:

f SDNF = V (1,2,5,6,7)=x 1 x 2 x 3 +x 1 x 2 x 3 +x 1 x 2 x 3 +x 1 x 2 x 3 +x 1 x 2 x 3

1 2 3 4 5

Gawin natin ang gluing operation:

1 - 3 (x 1 ) x 2 x 3 1
2 - 4 (x 1 ) x 2 x 3 2
3 - 5 (x 2 ) x 1 x 3 3
4 - 5 (x 3 ) x 1 x 2 4

Bilang resulta ng unang hakbang sa pagdikit, nakakuha tayo ng apat na bagong pangatnig; Ang mga resultang conjunctions ay hindi na magkakadikit at bumubuo ng pinaikling DNF.

f abbr SDNF =x 2 x 3 +x 2 x 3 +x 1 x 3 +x 1 x 2

Upang matukoy ang mga ipinag-uutos na simpleng implikasyon at bumalangkas ng pinakamababang saklaw batay sa mga ito, isang implicant na talahanayan ang itinayo (Talahanayan 3). Ang mga simpleng implicant ay nakasulat sa mga hilera ng implicant table, at ang mga constituent ng pagkakaisa ay nakasulat sa mga column. Ang asterisk ay ibinibigay kung ang prime implicant ay sumasaklaw sa constituent.

Talahanayan 3. Implicant na talahanayan

x 1 x 2 x3	X 1 x 2 x3	x 1 x 2 x3	x 1 x 2 x3	x 1 x 2 x3

Ang mga pangunahing implikasyon ay obligado dahil sila lamang ang sumasakop sa mga nasasakupan at kasama sa pinakamababang saklaw. May nananatiling isang walang takip na constituent x 1 x 2 x 3 na maaaring saklawin ng isa sa dalawang natitirang pangunahing implikasyon. Nagreresulta ito sa dalawang dead-end na anyo.

Paraan ni Blake-Poretsky

Ang pamamaraan ay nagpapahintulot sa isa na makakuha ng pinababang DNF ng isang Boolean function f mula sa arbitrary na DNF nito. Batay sa aplikasyon ng pangkalahatang gluing formula:

ang bisa nito ay madaling patunayan. talaga,

Kaya naman,

Ang pamamaraan ay batay sa sumusunod na pahayag: kung sa isang di-makatwirang DNF ng isang Boolean function f ay ginagawa namin ang lahat ng posibleng generalized gluings at pagkatapos ay isagawa ang lahat ng absorption, ang resulta ay isang pinababang DNF ng function f.

Tingnan natin ang isang halimbawa. Hayaang ang Boolean function f ay ibigay ng isang di-makatwirang DNF.

Kinakailangang gamitin ang paraan ng Blake-Poretsky upang makakuha ng pinaikling DNF ng function f. Nagsasagawa kami ng pangkalahatang gluing. Madaling makita na ang una at pangalawang elemento ng orihinal na DNF ay umamin ng pangkalahatang gluing na may paggalang sa variable x 1 . Bilang resulta ng gluing nakukuha namin:

Ang una at pangatlong elemento ng orihinal na DNF ay umamin ng pangkalahatang gluing na may paggalang sa parehong variable na x 1 at x 2 . Matapos idikit ang x 1 mayroon kaming:

Pagkatapos magdikit sa x 2 mayroon kaming:

Ang ikalawa at pangatlong elemento ng DNF ay umamin ng pangkalahatang gluing na may paggalang sa variable x 2 . Pagkatapos ng gluing makuha namin:

Nang maisagawa ang huling pangkalahatang gluing, nakarating kami sa DNF:

Matapos isagawa ang mga pagsipsip nakukuha namin:

Ang mga pagtatangka na higit pang ilapat ang operasyon ng pangkalahatang gluing at pagsipsip ay hindi nagbubunga ng mga resulta. Dahil dito, ang isang pinababang DNF ng function f ay nakuha. Susunod, ang problema sa paghahanap ng isang minimal na DNF ay malulutas gamit ang isang implicant matrix sa eksaktong parehong paraan tulad ng sa pamamaraan ni Quine.

Pag-minimize ng mga hindi kumpletong tinukoy na FAL

Kung, kapag nag-synthesize ng logical circuit na nagpapatupad ng ilang FAL ng n variable, lumalabas na ilang set ng kabuuang bilang 2 n hindi kailanman maaaring lumitaw sa mga input ng circuit, kung gayon ang lohikal na function na ito ay hindi tinukoy sa mga set na ito. Tapos 2 n Ang mga hanay ng mga variable ay maaaring nahahati sa tatlong pangkat: mga hanay kung saan ang function ay tumatagal ng isang halaga ng yunit L, isang zero na halaga D at isang pangkat ng mga hanay kung saan ang function ay hindi tinukoy N (mga hindi natukoy na hanay). Ang isang FAL na naglalaman ng mga hindi natukoy na hanay ay tinatawag na hindi kumpleto o bahagyang tinukoy. Maaaring gamitin ang mga hindi natukoy na hanay upang mapabuti ang kalidad ng pag-minimize. Sa kasong ito, ang mga hindi tiyak na hanay (kapag pinaliit, halimbawa, ng Veitch, mga mapa ng Carnaugh) ay maaaring lumahok sa pagbuo ng mga contour na may parehong unit at zero set. Nagreresulta ito sa pagbuo ng isang mas simpleng pinaliit na function ng lohika.

Ang isang unibersal na paraan ng pagliit ay ang paggamit ng mga batas at relasyon ng lohikal na algebra, na nagpapahintulot sa pagliit ng FAL para sa anumang bilang ng mga variable.

Ang mag-aaral ay dapat:

alamin:

· Mga pamamaraan para sa pagliit ng mga lohikal na function.

Magagawang:

· Magsagawa ng pag-minimize ng function gamit ang direktang paraan ng pagbabago; Magsagawa ng function minimization gamit ang direct transformation method;

· Magsagawa ng pag-minimize ng function gamit ang mga mapa ng Karnaugh.

Direktang paraan ng pagbabago

Logical function na tumutukoy sa prinsipyo ng pagbuo ng isang circuit digital na aparato, ay maaaring, tulad ng ipinapakita sa itaas, ay maipakita sa anyo ng isang talahanayan ng katotohanan o sa anyo ng SDNF o SKNF at maaaring magamit upang makuha ang lohikal na circuit ng aparato. Gayunpaman, ang resultang logic circuit ay karaniwang hindi magiging pinakamainam. kaya lang mahalagang yugto synthesis mga logic circuit ay ang pagliit ng mga lohikal na pag-andar.

Minimization(pagpapasimple ng anyo ng notasyon) ng function ay mahalagang operasyon kapag nag-synthesize ng isang lohikal na circuit, dahil salamat sa paunang pag-minimize, ang circuit ay ipinatupad na may pinakamaliit na bilang ng mga elemento.

Ang isang bilang ng mga pamamaraan ay binuo para sa minimization. Isa sa mga simpleng pamamaraan Ang minimization ay isang paraan ng direktang pagbabago, na isinasagawa gamit ang mga pangunahing theorems ng algebra ng logic.

Halimbawa, isang lohikal na pag-andar

sa anyo ng SDNF, maaaring i-minimize tulad ng sumusunod:

1. Idagdag sa function na ito ang term na nasa function na ito, gamit ang panuntunang x+x=x

2. Ilapat natin ang paraan ng pagdikit-dikit ng mga pang-elementarya na may pantay na salungguhit

3. Ilapat natin ang paraan ng gluing para sa huling dalawang elementarya na pang-ugnay

Ang lohikal na function na nakuha bilang resulta ng minimization ay tinatawag na dead-end function. Ang isang lohikal na function ay maaaring magkaroon ng ilang mga dead-end na form.

Ang pagtukoy at pag-aalis ng mga redundancies sa pagtatala ng isang function sa pamamagitan ng pagbabago nito gamit ang mga axiom, batas, pagkakakilanlan at theorems ng algebra ng logic ay nangangailangan ng masalimuot na kalkulasyon at nauugnay sa maraming oras.

Mga mapa ng Carnot

Ang direktang paraan ng pagbabago ay pinakaangkop para sa mga simpleng formula, kapag ang pagkakasunud-sunod ng mga pagbabagong-anyo ay halata sa gumaganap. Kadalasan, ang pamamaraang ito ay ginagamit para sa panghuling pag-minimize ng mga expression na nakuha pagkatapos ng pagliit ng mga ito sa pamamagitan ng iba pang mga pamamaraan.

Ang pagnanais na i-algoritma ang paghahanap para sa mga kalapit na produkto ng elementarya ay humantong sa pag-unlad mga pamamaraan ng tabular pagliit ng mga lohikal na function. Ang isa sa mga ito ay isang paraan batay sa paggamit ng mga mapa ng Karnaugh.

Ang mga mapa ng Carnot ay naimbento noong 1952 ni Edward W. Veitch at pinahusay noong 1953 ni Maurice Carnot, isang physicist sa Bell Labs, at nilayon upang makatulong na gawing simple ang mga digital electronic circuit.

Ang mapa ng Karnaugh ay isang graphical na representasyon ng talahanayan ng katotohanan ng mga lohikal na function. Ito ay isang talahanayan na naglalaman ng 2 n rectangular na mga cell, kung saan ang n ay ang bilang ng mga lohikal na variable.

Halimbawa, ang isang Karnaugh na mapa para sa isang function ng apat na variable ay may 2 4 = 16 na mga cell.

Ang istraktura ng isang Karnaugh map para sa mga function ng dalawang variable ay ipinapakita sa Figure 2.2. 2

Larawan 2.2

Ipinapakita ng Figure 2.3 ang istruktura ng isang Karnaugh map para sa isang function ng tatlong variable.

a) talahanayan ng katotohanan; b) istraktura ng mapa ng Karnaugh

Larawan 2.3

Ang mapa ay minarkahan ng isang coordinate system na naaayon sa mga halaga ng mga variable ng input. Halimbawa, nangungunang linya ang mga mapa para sa isang function ng tatlong variable (Figure 2.3) ay tumutugma sa zero na halaga variable x1, at ang mas mababang isa - ang halaga ng yunit nito.

Ang bawat haligi ng mapa na ito ay nailalarawan sa pamamagitan ng mga halaga ng dalawang variable: x2 at x3. Ang kumbinasyon ng mga numero na nagmamarka sa bawat haligi ay nagpapakita para sa kung anong mga halaga ng mga variable na x2 at x3 ang function na inilagay sa mga cell ng column na ito ay kinakalkula.

Kung nasa tinukoy na set variable function ay katumbas ng isa, kung gayon ang SDNF nito ay kinakailangang naglalaman ng elementarya na produkto na kumukuha ng unit value sa set na ito. Kaya, ang mga cell ng mapa ng Carnot na kumakatawan sa isang function ay naglalaman ng kasing dami ng mga yunit ng elementarya na nakapaloob sa SDNF nito, at ang bawat yunit ay tumutugma sa isa sa mga elementarya na produkto.

Tandaan natin na ang mga coordinate ng mga hilera at column sa mapa ng Carnaugh ay hindi sumusunod sa natural na pagkakasunud-sunod ng pagtaas ng mga binary code, ngunit sa pagkakasunud-sunod na 00, 01, 11, 10. Ang pagbabago sa pagkakasunud-sunod ng mga set ay ginagawa upang magkatabi ang mga kalapit na hanay, ibig sabihin. nagkakaiba sa halaga ng isang variable lamang.

Ang mga cell kung saan ang function ay kumukuha ng mga halaga na katumbas ng isa ay puno ng mga halaga. Ang natitirang mga cell ay puno ng mga zero.

Isaalang-alang natin ang proseso ng minimization gamit ang halimbawang ipinakita sa Figure 2.4.

a) talahanayan ng katotohanan; b) Mapa ng Carnaugh

Larawan 2.4

Una, bumubuo kami ng mga parihaba na naglalaman ng 2k na mga cell, kung saan ang k ay isang integer.

Ang mga kalapit na cell na tumutugma sa mga katabing elementary na produkto ay pinagsama sa mga parihaba.

Halimbawa, sa Figure 2.4b, pinagsama ang mga cell na may mga coordinate 001 at 101 Kapag pinagsama ang mga cell na ito, nabuo ang isang parihaba kung saan binabago ng variable na x1 ang halaga nito. Dahil dito, mawawala ito kapag pinagsama-sama ang kaukulang mga elementarya at ang x2 at x3 lamang ang mananatili, at kinukuha namin ang variable na x2 sa inverse form, dahil ito ay katumbas ng 0.

Ang mga cell na matatagpuan sa unang hilera (Figure 2.4 b) ay naglalaman ng mga yunit at magkatabi. Samakatuwid, lahat sila ay pinagsama sa isang parihaba na naglalaman ng 2 2 = 4 na mga cell.

Ang mga variable na x2 at x3 sa loob ng parihaba ay nagbabago ng kanilang halaga; samakatuwid, mawawala ang mga ito mula sa nagreresultang produktong elementarya. Ang variable na x1 ay nananatiling hindi nagbabago at katumbas ng zero. Kaya, ang elementarya na produkto na nakuha sa pamamagitan ng pagsasama-sama ng mga cell ng unang hilera ng Figure 2.4 b ay naglalaman lamang ng isang x1, na kinukuha natin sa kabaligtaran na anyo, dahil ito ay katumbas ng 0.

Ito, sa partikular, ay sumusunod sa katotohanan na ang apat na mga cell ng unang hilera ay tumutugma sa kabuuan ng apat na elementarya na produkto:

Ang dalawang cell ng pangalawang column ay tumutugma sa kabuuan ng dalawang produkto

Ang function na naaayon sa Figure 2.4 ay may anyo:

Ang koleksyon ng mga parihaba na sumasaklaw sa lahat ng mga yunit ay tinatawag na pantakip. Tandaan na ang parehong cell (halimbawa, cell na may mga coordinate 001) ay maaaring sakupin ng dalawa o higit pang beses.

Kaya, magagawa mo ang mga sumusunod na konklusyon:

1. Ang formula na nagreresulta mula sa pag-minimize ng isang lohikal na function gamit ang mga mapa ng Carnaugh ay naglalaman ng kabuuan ng kasing dami ng mga elementarya na produkto na mayroong mga parihaba sa saklaw.

2. Kung mas maraming mga cell ang nasa isang parihaba, mas kaunting mga variable ang nasa kaukulang elementarya na produkto.

Halimbawa, para sa mapa ng Carnot na ipinapakita sa Figure 2.5 a, ang isang parihaba na naglalaman ng apat na mga cell ay tumutugma sa elementarya na produkto ng dalawang variable, at isang parisukat na binubuo lamang ng isang cell ay tumutugma sa elementarya na produkto. kabilang ang lahat ng apat na variable.

a) b) c)

Larawan 2.5

Ang function na naaayon sa saklaw na ipinapakita sa Figure 2.5 a ay may anyo:

Sa kabila ng katotohanan na ang mga mapa ng Carnot ay inilalarawan sa isang eroplano, ang kapitbahayan ng mga parisukat ay itinatag sa ibabaw ng torus. Itaas at mababang limitasyon Ang mga mapa ng Carnot ay tila "magkadikit", na bumubuo sa ibabaw ng isang silindro. Kapag nakadikit ang mga hangganan sa gilid, ang isang toroidal na ibabaw ay nakuha. Kasunod ng pangangatwiran sa itaas, itinatag namin na ang mga cell na may mga coordinate 1011 at 0011, na ipinapakita sa Figure 2.5 b, ay magkatabi at pinagsama sa isang parihaba. Sa katunayan, ang mga ipinahiwatig na mga cell ay tumutugma sa kabuuan ng mga elementarya na produkto

Ang natitirang apat na unit cell ay pinagsama sa parehong paraan. Bilang resulta ng kanilang kumbinasyon, nakakakuha kami ng isang elementarya na produkto.

Sa wakas, ang function na naaayon sa saklaw na ipinapakita sa Figure 2.5 b ay may form

Ang mapa ng Carnaugh na ipinapakita sa Figure 2.5c ay naglalaman ng mga solong cell na matatagpuan sa mga sulok. Ang lahat ng apat na mga cell ay katabi, at pagkatapos ng pagsasama-sama ay ibibigay nila ang elementarya na produkto

Ang mga halimbawang tinalakay sa itaas ay nagpapahintulot sa amin na bumalangkas ng pagkakasunud-sunod ng pagliit ng mga lohikal na function gamit ang mga mapa ng Karnaugh:

1. Ang isang talahanayan para sa n variable ay ipinapakita at ang mga gilid nito ay minarkahan.

2. Ang mga cell ng talahanayan na tumutugma sa mga hanay ng mga variable na nagpapaandar sa isa ay puno ng mga isa, ang natitirang mga cell ay puno ng mga zero.

3. Ang pinakamahusay na saklaw ng talahanayan ay pinili gamit ang mga regular na parihaba, na aming binabalangkas. Ang bawat parihaba ay dapat may 2n na mga cell.

4. Ang parehong mga cell na may mga yunit ay maaaring isama sa iba't ibang mga contour.

5. Ang bilang ng mga parihaba ay dapat na minimal, at ang lugar ng mga parihaba ay dapat na maximum.

6. Para sa bawat parihaba, isinusulat namin ang produkto ng mga variable lamang na hindi nagbabago ng kanilang halaga. Kung ang variable na ito ay katumbas ng zero, ito ay nakasulat sa inverse form.

7. Ikinonekta namin ang mga nagresultang produkto na may lohikal na pagdaragdag na tanda.

Mga tanong sa seguridad:

1. Ano ang tinatawag na minterms at minterms?

2. Isulat ang mga function na tinukoy ng mga talahanayan 2.9 at 2.10 sa SDNF at SKNF.

Talahanayan 2.9

3. Pasimplehin ang mga logical function gamit ang identity axioms at mga batas ng logical algebra:

Mga elemento ng lohika

Ang mag-aaral ay dapat

alamin:

· Logic state table para sa basic functional logic circuits;

· Mga pangunahing prinsipyo ng pagbuo ng mga lohikal na circuit.

Magagawang:

· Tukuyin ang mga lohikal na estado sa mga output mga digital circuit sa pamamagitan ng mga kilalang estado sa mga input;

· Tuparin lohikal na disenyo sa mga base ng microcircuit;

· Pumili ng microcircuit mula sa reference book, batay sa ibinigay na mga parameter at mga tuntunin ng paggamit.

Ang prinsipyo ng logic device ay nakabatay sa IC sa trabaho bipolar transistor sa key mode (sarado man o bukas).

Ang lohikal na aksyon ay isinasagawa tulad ng sa isa (single-input elemento ng lohika) at may isang set (multi-input logic element) ng mga variable ng input.

Kapag nagtatrabaho mga lohikal na aparato Tatlong pangunahing operasyon ang ginagamit ayon sa Boolean algebra - "AT", "O", "HINDI".

Ang isang lohikal na function ay maaaring ipahayag sa salita, sa algebraic form, sa pamamagitan ng isang talahanayan ng katotohanan na tinatawag na isang switch table, gamit ang timing diagram. Isaalang-alang natin ang lahat ng mga pagpipilian para sa kumakatawan sa mga lohikal na function.

para sa una – X 3 X 4;

para sa pangalawa – X 1 X 3;

para sa pangatlo – X 2 X 3;

para sa ikaapat – X 1 X 2 X 4;

para sa ikalimang – X 1 X 2 X 4;

Ang isang minimal na DNF ay magiging ganito:

Ang paghahambing ng paraan ng mapa ng Karnaugh sa iba pang mga pamamaraan ng pag-minimize ng function, maaari nating tapusin na ang una ay pinakaangkop para sa manu-manong pagpapatupad. Oras gawa ng sarili ay makabuluhang nabawasan (dahil sa visual na representasyon malagkit na implikasyon). Pagpapatupad ng software Ang pamamaraang ito ay may sariling kahirapan. Oo, ito ay magiging napakahirap ipatupad pinakamainam na pagpipilian regular na mga parihaba, lalo na para sa malaking bilang mga argumento.

1.3.5 Paraan ng hindi tiyak na coefficient

Maaaring gamitin ang paraang ito para sa anumang bilang ng mga argumento. Ngunit dahil ang pamamaraang ito ay medyo mahirap, ginagamit lamang ito sa mga kaso kung saan ang bilang ng mga argumento ay hindi hihigit sa 5-6.

Ang paraan ng mga hindi tiyak na koepisyent ay gumagamit ng mga batas ng unibersal at null set at ang mga batas ng pag-uulit. Sa simula, ang lahat ng mga coefficient ay hindi tiyak (kaya ang pangalan ng pamamaraan).

Bumuo tayo ng isang matrix ng hindi tiyak na mga coefficient para sa apat na argumento. Sa kasong ito, magkakaroon tayo ng sistema ng 16 na equation.

Ang sistema ay ipinapakita sa susunod na pahina.

Itumbas natin ang lahat ng coefficient sa 0 sa mga row na iyon na tumutugma sa 0 sa column ng vector. Pagkatapos ay tinutumbas namin ang kaukulang mga coefficient sa ibang mga hilera sa 0. Pagkatapos ng mga pagbabagong ito, ang sistema ay kukuha ng sumusunod na anyo:

V = 1 VVVVVV = 1 VVV V VV = 1 V = 1 VVV = 1 VVVVVV = 1 VVV = 1 VVVVV = 1 VVV = 1

Ngayon sa bawat linya kailangan mong piliin ang minimum na koepisyent ng ranggo at itakda ito na katumbas ng isa, at ang natitirang mga koepisyent sa 0. Pagkatapos nito, i-cross out ang magkaparehong mga linya, na iniiwan ang isa sa mga ito (ang mga linya na may lahat ng mga coefficient na katumbas ng 0 ay tumawid din palabas).

= 1 = 1 = 1 = 1 = 1

Isulat natin ngayon ang mga pang-ugnay na katumbas ng mga coefficient na katumbas ng pagkakaisa. Makukuha namin ang pinakamababang DNF.

F(X 1 X 2 X 3 X 4) = X 1 X 3 V X 2 X 3 V X 3 X 4 V X 1 X 2 X 4 V X 1 X 2 X 4 .

Kaya, nakuha namin ang kaunting DNF sa ilang mga paraan Sa lahat ng mga kaso ito ay naging pareho, iyon ay, alinman sa mga inilarawan na pamamaraan ay maaaring gamitin upang mabawasan ang pag-andar. Gayunpaman, ang mga pamamaraang ito ay makabuluhang naiiba sa bawat isa kapwa sa prinsipyo ng paghahanap ng MDNF at sa oras ng pagpapatupad. Ang paraan ng mapa ng Karnaugh ay napaka-maginhawa para sa mga manu-manong kalkulasyon. Ito ay visual at hindi nangangailangan mga nakagawiang operasyon, at ang pagpili ng pinakamainam na lokasyon ng mga tamang parihaba ay hindi mahirap. Habang ang pagpapatupad ng makina ng pamamaraang ito ay kumplikado sa pamamagitan ng pangangailangan upang mahanap ang pinakamainam na pag-aayos ng mga parihaba. Naturally, ang paggamit ng iba pang mga pamamaraan (Quine's method, Quine-McCluskey method, method of indefinite coefficients) para sa mga manu-manong kalkulasyon ay hindi naaangkop. Ang mga ito ay mas angkop para sa pagpapatupad ng makina, dahil naglalaman ang mga ito ng isang malaking bilang ng mga paulit-ulit na simpleng operasyon.

Gawain 2.

2.1 Algorithm diagram para sa pamamaraan ni Quine

1. Simula.

2. Ipasok ang DSNF matrix ng orihinal na function.

3. Suriin ang i-th (i=1,m-1: kung saan ang m ay ang bilang ng mga linya sa DSNF) at j-th (j=i+1, m) na mga linya para sa gluing. Kung magkadikit ang mga linya, pagkatapos ay pumunta sa hakbang 6, kung hindi ay pumunta sa hakbang 5.

4. Bumuo ng hanay ng mga simpleng implikasyon, na minarkahan dati ng simbolong '*' ang variable kung saan pinagdikit ang mga string na ito.

5. Pumunta sa hakbang 2.

6. Sumulat ng isang linya na hindi pinagsama sa anumang iba pang linya sa huling hanay.

7. Pumunta sa hakbang 2.

8. Output ng resultang matrix.

Lohikal na diagram ng algorithm sa Lyapunov notation

V H V 1 Z 1 V 2 ¯ V 3 V 4 V K

V H – simula.

V 1 – ipasok ang DSNF matrix ng orihinal na function.

V 2 - bumuo ng isang hanay ng mga simpleng implikasyon, na dati ay minarkahan ng simbolong '*' ang variable kung saan ang mga string na ito ay pinagdikit.

V 3 - isang string na hindi pinagsama sa anumang iba pang string ay nakasulat sa huling array.

V 4 - output ng resultang matrix.

Z 1 – kung ang mga linya ay pinagdikit, pagkatapos ay pumunta sa hakbang 3, kung hindi, pumunta sa hakbang 5.

V K – wakas.

Graph diagram ng algorithm.

Paglalarawan makina mga pamamaraan

Procedure Stuck(S1, S2: Diz; IndexS1, IndexS2: byte);

Pinagsasama ng pamamaraang ito ang dalawang disjunct na ipinasa dito. Ang mga sugnay ay tinukoy sa mga parameter S1, S2. Tinutukoy ng Indexes IndexS1, IndexS2 ang mga indeks ng mga clause na ito sa pangunahing working array. Ang algorithm ng pamamaraan ay ang mga sumusunod: una, ang bilang ng mga character na nakadikit ay hinanap. Kung mayroong 0 sa kanila, magkapareho ang mga ito, at isa lamang sa kanila ang nakasulat sa huling hanay. Kung 1, ang lokasyon ng simbolo ay tinutukoy kung saan ang dalawang disjunction na ito ay pinagdikit, at pinapalitan namin ang simbolo na ito ng '*'. Ang lahat ng nakuhang resulta ay ipinasok sa hanay ng REZ.

Ang lahat ng iba pang mga pag-andar at pamamaraan ng programa ay nauugnay sa mga aksyon sa mga array, iyon ay, hindi sila direktang nauugnay sa ang pamamaraang ito paghahanap ng MDNF. Samakatuwid, walang saysay na ilarawan ang mga ito.

2.2 Algorithm diagram para sa pamamaraan ni Petrik

1. Simula.

2. Ipasok ang DSNF matrix ng orihinal na function at mga simpleng implikat na nakuha sa pamamaraan ni Quine.

3. Gumawa ng talahanayan ng mga label.

4. Gamit ang talahanayan ng mga label, bumuo ng isang conjunction ng mga disjunctions, na ang bawat isa ay isang set ng mga implicants na nasa kolum na ito may marka.

Algebras ng lohika

3.3.1. Pag-minimize ng FAL gamit ang Carnot matrix

Ang Carnot matrix ay isang uri ng FAL truth table, na nahahati sa mga cell. Ang bilang ng mga matrix cell ay 2 n, Saan n– bilang ng mga argumento ng FAL. Ang mga column at row ng isang matrix ay itinalaga ng mga hanay ng mga argumento. Ang bawat cell ng matrix ay tumutugma sa isang constituent ng FAL unit (binary number). Binubuo ang binary number ng cell ng isang set ng row at column arguments. Ang Carnot matrix para sa FAL, depende sa dalawang argumento, ay ipinakita sa anyo ng talahanayan 3.3., mula sa tatlong argumento sa talahanayan 3.4. at mula sa apat na argumento talahanayan 3.5.

Talahanayan 3.3.

Talahanayan 3.5.

X 3 X 4 X 1 X 2
	0 0 0 0	0 0 0 1	0 0 1 1	0 0 1 0
	0 1 0 0	0 1 0 1	0 1 1 1	0 1 1 0
	1 1 0 0	1 1 0 1	1 1 1 1	1 1 1 0
	1 0 0 0	1 0 0 1	1 0 1 1	1 0 1 0

Ang mga cell ng matrice (Tables 3.3., 3.4. at 3.5.) ay binibilang na may mga decimal na katumbas ng mga binary na numero ng mga cell. Ang mga katabing matrix cell, parehong pahalang at patayo, ay naglalaman ng mga katabing binary na numero. Bilang karagdagan, ang mga katabing binary na numero ay matatagpuan sa lahat ng mga column sa itaas at ilalim na mga row, gayundin sa lahat ng mga row ng mga pinakalabas na column.

Ang proseso ng pagliit ng FAL gamit ang Carnot matrix ay batay sa batas ng pagdikit ng mga katabing binary na numero. Maaari mong pagsamahin ang mga binary na numero ng magkatabing mga cell, ngunit inirerekomenda na pagsamahin ang mga hanay ng mga argumento na nagpapahiwatig ng mga row at column ng mga matrice. Isaalang-alang natin ang pagdikit ng mga binary na numero ng mga cell ng unang hanay ng matrix (Talahanayan 3.5.).

Ang mga cell 0 at 4, mga binary na numero 0000 at 0100, ayon sa pagkakabanggit, ang resulta ng gluing ay 0-00.

Mga cell 8 at 12, mga binary na numero 1000 at 1100, resulta 1-00. Ang mga nagresultang implicants ay pinagsama-sama, dahil Ang gitling ay nasa parehong lugar at ang mga implicant na binary na numero ay katabi, ang huling resulta ay - 00.

Mga cell 8 at 12

Kaya, kung ang lahat ng mga binary na numero ng isang hanay ay pinagsama-sama, pagkatapos ay ang mga bit na nagpapahiwatig ng mga hilera ay mawawala. Katulad nito, kung ang lahat ng mga binary na numero ng isang hilera ay nakadikit, halimbawa 4, 5, 7, 6, kung gayon ang lahat ng mga digit na nagpapahiwatig ng mga haligi ay mawawala, i.e. ang resulta ay ang mga sumusunod na 01- -.

Kung ang mga binary na numero ng alinmang dalawang cell ay pinagdikit, pagkatapos ay maglalagay ng gitling sa halip na ang digit na iyon ng mga binary na numero ng isang row o column na magbabago kapag lumipat ang mga cell mula sa isang linya patungo sa isa pa (o mula sa isang column patungo sa isa pa) . Halimbawa, ang mga bilang ng mga cell 5 at 13 ay pinagsama-sama, nakuha namin ang resulta -101, o mga cell 7 at 6 ang resulta ay 011-.

Kapag naglalagay ng mga binary na numero ng walong katabing mga cell, nawawala ang tatlong variable, halimbawa, para sa mga cell 3, 7, 15, 11, 2, 6, 14, 10, nawawala ang mga variable X 1 , X 2 , X 3. Mga variable X 1 , X 2 mawala dahil ang lahat ng mga cell ng mga haligi ay nakadikit magkasama, at X 3 dahil ang huling dalawang column ay pinagdikit.

Bago isaalang-alang ang mga halimbawa ng pagliit ng FAL gamit ang Carnot matrix, kinakailangan na uriin ang mga hanay ng mga argumento sa tulong kung saan natutukoy ang mga function ng algebra ng lohika.

Ito ay kilala na para sa bawat FAL mayroong 2 set ng mga argumento n, Saan n– ang bilang ng mga argumento kung saan nakasalalay ang isang function o lohikal na expression.

Ang mga hanay ng argumento ay nahahati sa tatlong uri

1. Ang mga hanay ng mga argumento kung saan ang function ay katumbas ng isa ay tinatawag na working.

2. Ang mga hanay ng mga argumento kung saan ang function ay katumbas ng zero ay tinatawag na bawal.

3. Ang mga hanay ng mga argumento kung saan ang isang function ay maaaring katumbas ng alinman sa isa o zero ay tinatawag na walang malasakit.

Kung ang isang ibinigay na FAL ay walang mga set na walang malasakit, maaari itong i-representa sa literal na pagpapahayag sa anyo ng SDNF. Kung may mga walang malasakit na hanay sa isang ibinigay na FAL, ang representasyon nito ay maaaring magkaroon ng sumusunod na anyo.

kung saan ang mga katumbas ng decimal mga hanay ng trabaho,

– decimal na katumbas ng mga ipinagbabawal na set.

Ang mga hanay ng mga argumento na wala sa mga nagtatrabaho at ipinagbabawal ay magiging walang malasakit.

Halimbawa 3.3. I-minimize ang ibinigay na FAL sa anyo ng SDNF gamit ang Carnot matrix.

Samakatuwid, ang function ay tinukoy sa pamamagitan lamang ng mga working set. Ang iba ay ipagbabawal. Ang function ay nakasalalay lamang sa tatlong argumento. Bumubuo kami ng Carnot matrix at inilalagay ang mga iyon sa mga cell nito na tumutugma sa mga gumaganang set, at naglalagay ng mga zero sa natitirang mga cell.

Talahanayan 3.5.

X 2 X 3 X 1
	0

Upang mabawasan, ang mga matrix cell na naglalaman ng mga ito ay pinagsama sa mga contour. Ang circuit ay maaaring magsama ng dalawang cell, apat o lahat ng walo. SA sa halimbawang ito kasama sa outline ang apat na magkatabing cell ng parehong row. Ang implicant ng ibinigay na contour ay magiging 1 - -. Ang resulta ng minimization ay ang mga sumusunod, i.e. nagkaroon ng pagbawas ibinigay na function sa SDNF na may 11 letra.

Halimbawa 3.4. I-minimize ang Boolean expression na ibinigay ng gumagana at ipinagbabawal na mga set gamit ang Carnot matrix.

Bumubuo kami ng Carnot matrix para sa apat na variable at punan ang mga cell ng mga isa at mga zero, ayon sa pagkakabanggit, para sa mga nagtatrabaho at ipinagbabawal na set.

Talahanayan 3.6.

X 3 X 4 X 1 X 2	00
		(1)

	(1)	(1)

Kapag pinagsama ang mga cell na may mga yunit sa mga contour, ito ay kanais-nais na ang bawat tabas ay kasama ang pinakamalaking posibleng bilang ng mga cell. Upang gawin ito, ginagamit namin ang mga cell ng ilang walang malasakit na hanay bilang mga cell ng gumaganang set, na pinapalitan ang mga nasa panaklong sa mga ito. Bilang resulta, nakakakuha kami ng tatlong contour na naglalaman ng 4 na cell bawat isa. Sa pangkalahatang code ng circuit, na kinabibilangan ng lahat ng mga cell ng isang linya, nawawala ang mga variable X 2 X 3 (10 - -). Sa pangkalahatang code ng circuit, na kinabibilangan ng lahat ng mga cell ng isang column, nawawala ang mga variable X 1 X 2 (- - 11) at para sa isang contour na naglalaman ng dalawang cell ng dalawang linya, nawawala ang mga variable X 2 (kapag gumagalaw sa isang contour mula sa isang linya patungo sa isa pa) at X 3 (kapag lumipat mula sa isang hanay patungo sa isa pa). Bilang resulta, nakukuha namin ang pinakamababang DNF sa ang sumusunod na anyo

Mga posibleng opsyon ang kumbinasyon ng mga cell ng Carnot matrix sa mga contour ay ipinapakita sa Figure 3.4.

X 3 X 4 X 1 X 2

A = 0 - 0 -

Z = - 0 - 0

B = 1 - 1 -

K = - - - 1

B = - - 0 0

L = - 1 - -

Г = 1 0 - -

M = - - - 0

D = - 0 0 1

H = - 0 - -

E = - 0 1 -

F = - 1 - 1

kanin. 3.1. Mga posibleng opsyon para sa pagsasama-sama ng mga cell ng Carnot matrix sa mga contour

3.3.2. Pag-minimize ng mga logical algebra function gamit ang isang matrix ng limang variable

Ang minimization matrix para sa limang variable ay itinayo katulad ng Carnot matrix, i.e. sa matrix na ito, ang mga katabing column at row ay dapat italaga ng mga katabing binary na numero ng mga hanay ng mga variable

Sa isang limang-variable na matrix (Talahanayan 3.7.), ang mga hilera ay tumutugma sa mga hanay ng mga variable X 1 X 2 X 3, at ang mga column ay mga hanay ng mga variable X 4 X 5. Ang bawat cell ng matrix ay tumutugma sa isang limang-bit na binary na numero. Ang mga cell ng matrix (Talahanayan 3.7.) ay naglalaman ng mga decimal na katumbas ng mga katumbas na binary na numero.

Talahanayan 3.7.

X 4 X 5 X 1 X 2 X 3

Ang pag-minimize ng FAL gamit ang isang matrix ng limang variable ay binubuo ng pagsasama-sama ng mga cell na may mga gumaganang set (kabilang, kung kinakailangan, ang mga cell na may mga set na walang malasakit) sa mga contour at pagkuha ng mga pangkalahatang code na tumutugma sa mga contour na ito.

Ang kakaiba dito ay na sa mga column ng isang matrix ng limang variable, maaari mong pagsamahin ang apat na cell sa mga contour lamang, o apat na cell sa itaas, o apat na cell sa ibaba, o apat na cell sa gitna. Halimbawa, para sa huling column ng matrix, ang mga contour ay maaaring binubuo ng mga cell 2, 6, 14, 10, o 26, 30, 22, 18 o 14, 10, 26, 30.

Halimbawa 3.6. Gumamit ng limang-variable na matrix upang mabawasan ang sumusunod na lohikal na expression

Bumubuo kami ng isang matrix ng limang mga variable at punan ang mga cell ng mga nagtatrabaho na hanay ng mga isa, at ang mga cell ng mga ipinagbabawal na hanay ay may mga zero.

Pinagsasama namin ang mga cell na may gumaganang set sa mga contour, kabilang ang mga kinakailangang cell ng mga walang malasakit na set. Para sa bawat circuit ay tinukoy namin ang isang pangkalahatang code.

Talahanayan 3.8.

X 4 X 5 X 1 X 2 X 3
	(1)	(1)	(1)
	(1)
	(1)	(1)
		(1)	(1)
	(1)		(1)
			(1)
	(1)		(1)

Nakukuha namin ang pinakamababang DNF

Mga tanong sa seguridad

1. Tukuyin ang pinaikling DNF.

2. Ano ang isang dead-end na DNF?

3. Paano pinipili ang kaunting DNF mula sa mga dead-end na DNF?

4. Para saan ginagamit ang implicant table at paano ito binuo?

5. Ipaliwanag ang analytical na pamamaraan para sa pagliit ng Quine-McClassky FAL.

6. Paano binuo ang Carnot matrix para sa tatlo at apat na variable?

7. I-minimize ng analytical ang mga sumusunod mga lohikal na pagpapahayag, tinukoy lamang ng mga gumaganang set

8. Gamit ang Carnaugh matrix, i-minimize ang mga lohikal na expression na tinukoy ng gumagana at ipinagbabawal na set

Kaugnay na impormasyon.

Ang pag-minimize ng mga logical function ay isa sa karaniwang mga gawain sa proseso ng pag-aaral ng disenyo ng circuit. Samakatuwid, sa palagay ko ay may lugar ang naturang artikulo, sana ay magustuhan mo ito.

Bakit kailangan ito?

Ang pagiging kumplikado ng isang lohikal na function, at samakatuwid ang pagiging kumplikado at gastos ng circuit (circuit) na nagpapatupad nito, ay proporsyonal sa bilang lohikal na operasyon at ang bilang ng mga paglitaw ng mga variable o ang kanilang mga negasyon. Sa prinsipyo, ang anumang lohikal na pag-andar ay maaaring gawing simple nang direkta gamit ang mga axiom at theorems ng lohika, ngunit, bilang panuntunan, ang mga naturang pagbabago ay nangangailangan ng masalimuot na mga kalkulasyon.

Bilang karagdagan, ang proseso ng pagpapasimple ng mga expression ng Boolean ay hindi algorithmic. Samakatuwid, mas ipinapayong gumamit ng espesyal algorithmic na pamamaraan mga minimization na nagpapahintulot sa pagpapasimple ng isang function na maisagawa nang mas simple, mabilis at walang error. Kasama sa mga naturang pamamaraan, halimbawa, ang Quine method, ang Karnaugh map method, ang implicant test method, ang implicant matrix method, ang Quine-McCluskey method, atbp. Ang mga paraang ito ay pinakaangkop para sa regular na pagsasanay, lalo na ang minimization ng isang logical function. gamit ang mga mapa ng Karnaugh. Ang paraan ng mapa ng Karnaugh ay nagpapanatili ng kalinawan kapag ang bilang ng mga variable ay hindi hihigit sa anim. Sa mga kaso kung saan ang bilang ng mga argumento ay higit sa anim, karaniwang ginagamit ang pamamaraang Quine-McCluskey.

Sa proseso ng pagliit ng isang partikular na lohikal na pag-andar, kadalasang isinasaalang-alang kung anong batayan ang magiging mas mahusay na ipatupad ang minimal na anyo nito gamit ang mga electronic circuit.

Pag-minimize ng Logical Function Gamit ang Karnaugh Maps

Carnot Map - graphic na pamamaraan minimization ng switching (Boolean) function, na nagbibigay ng relatibong kadalian ng pagtatrabaho sa malalaking expression at pag-aalis ng mga potensyal na karera. Kinakatawan ang mga operasyon ng pairwise incomplete gluing at elementary absorption. Ang mga mapa ng Karnaugh ay itinuturing na talahanayan ng katotohanan ng isang function na muling inayos nang naaayon. Ang mga mapa ng Carnaugh ay maaaring isipin bilang isang partikular na flat development ng isang n-dimensional na Boolean cube.

Sa isang mapa ng Carnaugh, inililipat ang mga variable ng Boolean mula sa talahanayan ng katotohanan at inayos gamit ang Grey code, kung saan ang bawat susunod na numero ay naiiba mula sa nauna nang isang digit lamang.

Ang pangunahing paraan para sa pagliit ng mga lohikal na function na ipinakita sa anyo ng SDNF o SCNF ay ang pagpapatakbo ng pairwise na hindi kumpletong gluing at elementarya na pagsipsip. Ang pagpapatakbo ng pairwise gluing ay isinasagawa sa pagitan ng dalawang termino (mga miyembro) na naglalaman ng magkaparehong mga variable, ang mga paglitaw kung saan (direkta at kabaligtaran) ay nag-tutugma para sa lahat ng mga variable maliban sa isa. Sa kasong ito, ang lahat ng mga variable maliban sa isa ay maaaring alisin sa mga bracket, at ang direkta at kabaligtaran na mga paglitaw ng isang variable na natitira sa mga bracket ay maaaring idikit. Halimbawa:

Ang posibilidad ng pagsipsip ay sumusunod mula sa halatang pagkakapantay-pantay

kaya, pangunahing gawain Kapag pinaliit ang SDNF at SCNF, kinakailangan na maghanap ng mga termino na angkop para sa gluing na may kasunod na pagsipsip, na para sa malalaking anyo ay maaaring maging isang mahirap na gawain. Nagbibigay ang mga mapa ng Carnaugh ng visual na paraan upang mahanap ang mga ganoong termino.

Gaya ng nalalaman, ang mga function ng Boolean ng N variable, na ipinakita sa anyo ng SDNF o SCNF, ay maaaring maglaman ng 2N iba't ibang termino. Ang lahat ng mga terminong ito ay bumubuo ng isang tiyak na istraktura, topologically katumbas ng isang N-dimensional cube, at anumang dalawang termino na konektado sa pamamagitan ng isang gilid ay angkop para sa gluing at pagsipsip.

Ipinapakita ng larawan simpleng mesa halaga ng katotohanan para sa isang function ng dalawang variable, isang 2-dimensional na kubo (parisukat) na tumutugma sa talahanayang ito, pati na rin isang 2-dimensional na kubo na may pagtatalaga ng mga termino ng SDNF at isang katumbas na talahanayan para sa pagpapangkat ng mga termino:

Sa kaso ng isang function ng tatlong variable, kailangan mong harapin ang isang three-dimensional na kubo. Ito ay mas kumplikado at hindi gaanong nakikita, ngunit posible sa teknikal. Ang figure ay nagpapakita, bilang isang halimbawa, isang talahanayan ng katotohanan para sa isang Boolean function ng tatlong mga variable at ang kaukulang kubo nito.

Tulad ng makikita mula sa figure, para sa tatlong-dimensional na kaso ay posible ang mas kumplikadong mga pagsasaayos ng mga termino. Halimbawa, apat na termino na kabilang sa isang mukha ng isang kubo ay pinagsama sa isang termino na may dalawang variable na hinihigop:

Sa pangkalahatan, masasabi nating ang 2K na termino na kabilang sa isang K-dimensional na mukha ng isang hypercube ay pinagsama-sama sa isang termino, at ang mga K variable ay hinihigop.

Upang gawing simple ang pagtatrabaho sa mga function ng Boolean ng isang malaking bilang ng mga variable, iminungkahi ang sumusunod maginhawang pagtanggap. Ang kubo, na isang istraktura ng mga termino, ay nakabukas sa isang eroplano tulad ng ipinapakita sa figure. Ginagawa nitong posible na kumatawan sa mga function ng Boolean na may higit sa dalawang variable sa anyo ng isang flat table. Dapat alalahanin na ang pagkakasunud-sunod ng mga term code sa talahanayan (00 01 11 10) ay hindi tumutugma sa pagkakasunud-sunod ng mga binary na numero, at ang mga cell na matatagpuan sa matinding mga haligi ng talahanayan ay katabi ng bawat isa.

Sa katulad na paraan, maaari kang gumana sa mga function ng apat, lima o higit pang mga variable. Ang mga halimbawa ng mga talahanayan para sa N=4 at N=5 ay ipinapakita sa figure. Para sa mga talahanayang ito, dapat tandaan na ang mga kalapit na mga cell ay ang mga matatagpuan sa kaukulang mga cell ng mga pinakalabas na hanay at ang kaukulang mga cell ng tuktok at ilalim na linya. Para sa mga talahanayan ng 5 o higit pang mga variable, dapat mo ring isaalang-alang na ang 4x4 na mga parisukat ay halos matatagpuan sa ibabaw ng bawat isa sa ikatlong dimensyon, samakatuwid ang mga katumbas na mga cell ng dalawang katabing 4x4 na mga parisukat ay magkatabi, at ang mga kaukulang termino ay maaaring idikit nang magkasama .

Ang isang Karnaugh na mapa ay maaaring i-compile para sa anumang bilang ng mga variable, ngunit ito ay maginhawa upang gumana nang hindi hihigit sa limang mga variable. Sa pangkalahatan, ang isang Karnaugh Map ay isang talahanayan ng katotohanan na pinagsama-sama sa 2-dimensional na anyo. Salamat sa paggamit ng Grey code, ang tuktok na hilera ay katabi sa ibaba, at ang kanang hanay ay katabi sa kaliwa, i.e. ang buong Carnot Map ay gumuho sa isang torus (donut) figure. Sa intersection ng isang row at isang column, ang katumbas na value mula sa truth table ay ipinapasok. Kapag napuno na ang Card, maaari mong simulan ang pagliit.

Kung kinakailangan upang makuha ang pinakamababang DNF, sa Map ay isasaalang-alang lamang namin ang mga cell na naglalaman ng mga iyon; Ang pag-minimize mismo ay isinasagawa ayon sa mga sumusunod na patakaran (gamit ang halimbawa ng DNF):

Susunod, kukunin namin ang unang lugar at tingnan kung aling mga variable ang hindi nagbabago sa loob ng lugar na ito, isulat ang pinagsama ng mga variable na ito, kung ang hindi nagbabagong variable ay zero, inilalagay namin ang isang inversion sa ibabaw nito. Kunin ang susunod na lugar, gawin ang parehong bilang para sa una, at iba pa para sa lahat ng mga lugar. Pinagsasama namin ang mga conjunction ng mga rehiyon sa pamamagitan ng disjunction.
Halimbawa (para sa Maps na may 2 variable):

Para sa CNF, ang lahat ay pareho, tanging ang mga cell na may mga zero ang isinasaalang-alang namin, ang mga hindi nagbabagong variable sa loob ng isang rehiyon ay pinagsama sa mga disjunction (naglalagay kami ng mga inversion sa mga unit variable), at ang mga disjunction ng mga rehiyon ay pinagsama sa isang conjunction. Sa puntong ito, ang minimization ay itinuturing na kumpleto. Kaya para sa Karnaugh Map sa Fig. 1, ang expression sa format na DNF ay magiging ganito:

Sa format na CNF: