Është një kompleks i operacioneve të përgjithësimit të njëpasnjëshëm. Përmbledhje statistikore dhe grupim
Punoni në temë
METODAT E MINIMIZIMIT
FUNKSIONET LOGJIKE
Konceptet kryesore: shprehjet logjike, funksionet logjike, metodat e minimizimit, përmbysja, lidhja, disjunksioni, nënkuptimi, ekuivalenca.
përmbajtja
Hyrje
Njerëzit që janë larg teknologjisë shpesh shikojnë kompjuterë dhe dixhitalë të tjerë pajisje elektronike si diçka misterioze dhe e pakuptueshme. Sidoqoftë, të gjitha këto pajisje funksionojnë në përputhje të rreptë me ligje të qarta logjike. Njohja dhe kuptimi i këtyre ligjeve ndihmon në komunikimin me një kompjuter dhe pajisje të tjera dixhitale.
Parimet e ndërtimit të një qarku të pajisjes dixhitale përcaktohen nga funksionet logjike. Kompleksiteti i një funksioni logjik, dhe si rrjedhim, kompleksiteti dhe kostoja e qarkut (qarkut) që e zbaton atë, është në proporcion me numrin operacionet logjike dhe numrin e shfaqjes së variablave ose mohimet e tyre. Në parim, çdo funksion logjik mund të thjeshtohet drejtpërdrejt duke përdorur aksiomat dhe teoremat e logjikës, por, si rregull, transformime të tilla kërkojnë llogaritje të rënda.
Përveç kësaj, procesi i thjeshtimit të shprehjeve Boolean nuk është algoritmik. Prandaj, është më e këshillueshme që të përdoren metoda speciale të minimizimit algoritmik që bëjnë të mundur thjeshtimin e funksionit më thjesht, shpejt dhe pa gabime.
Funksioni i thjeshtuar do të përmbajë më pak operacione dhe kombinime të argumenteve, dhe për këtë arsye qarku që zbaton funksionin do të përmbajë më pak elementë, d.m.th. do të jetë më e lirë dhe më e besueshme.
Në këtë drejtim, minimizimi i funksioneve logjike është veçanërisht i rëndësishëm.
Qëllimi puna është studimi i metodave për minimizimin e funksioneve logjike të algjebrës.
Objekti Puna përfshinte procesin e minimizimit të funksioneve logjike.
Artikulli hulumtim - metoda për minimizimin e funksioneve logjike dhe metodat për mësimin e kësaj teme në klasa të specializuara.
Detyrat hulumtim:
të studiojë elementet bazë të logjikës matematikore;
eksplorojnë metoda për minimizimin e funksioneve logjike;
zgjidhni detyrat për punë të pavarur;
zgjidhni problemet e zgjedhura duke përdorur metodat e përshkruara.
Puna përbëhet nga një hyrje, dy seksione, një përfundim dhe një listë referencash.
Hyrja vërteton rëndësinë e temës dhe përcakton qëllimin dhe objektivat e studimit.
Seksioni i parë diskuton bazat logjike të funksionimit të një kompjuteri.
Seksioni i dytë zbulon metodat për minimizimin e funksioneve logjike dhe jep shembuj të zgjidhjes së problemeve duke përdorur metodat e përshkruara.
Në përfundim, janë përmbledhur rezultatet e përgjithshme të studimit.
Bazat logjike funksionimin e kompjuterit
Elemente të logjikës matematikore
Kompjuterët janë pajisje automatike, parimet e funksionimit të të cilave bazohen ligjet elementare logjika binare.
Kompjuterët i të gjitha gjeneratave përbëhej dhe përbëhet nga elementë logjikë dhe elementë memorie që marrin dy vlera (bit) 0 dhe 1. I gjithë përpunimi i informacionit në një kompjuter të të gjitha blloqeve logjike të tij, qarqet logjike dhe pajisjet ishin dhe do të bazohen në ligjet dhe parimet e logjikës matematikore.
Logjika (nga greqishtja e lashtë logos, që do të thotë "fjalë, mendim, koncept, arsyetim, ligj") është shkenca e lashtë, duke studiuar korrektësinë e gjykimeve, arsyetimit dhe provave.
Logjika matematikoreështë një disiplinë matematikore që studion teknikën e provave.
Themeluesi i logjikës matematikore është matematikani i madh gjerman Gottfried Wilhelm Leibniz (1646 – 1716). Ai hodhi idenë për ta përdorur atë në logjikë simbolika matematikore dhe ndërtimi i llogaritjes logjike, shtroi problemin e justifikimit logjik të matematikës, luajtur rol të rëndësishëm në historinë e krijimit të kompjuterëve elektronikë: propozuar për t'u përdorur për qëllime të matematikës llogaritëse sistemi binar Duke llogaritur. Mbi themelin e hedhur nga Leibniz, matematikani irlandez George Boole ndërtoi një ndërtesë shkencë e re– logjika matematikore, – e cila, ndryshe nga algjebra e zakonshme, nuk vepron me numra, por me pohime. Për nder të D. Boole, variablat logjikë në gjuhën e programimit Pascal u quajtën më pas Boolean.
Logjika matematikore studion pyetjet e zbatimit metodat matematikore për të zgjidhur probleme logjike dhe ndërtimi i qarqeve logjike që qëndrojnë në themel të funksionimit të çdo kompjuteri. Gjykimet në logjikën matematikore quhen deklarata ose shprehje logjike.
Pohim është çdo deklaratë për të cilën mund të thuhet nëse është e vërtetë apo e gabuar, d.m.th. nëse i përgjigjet realitetit apo jo; Ky është një shënim simbolik i përbërë nga sasi logjike (konstante ose ndryshore) të bashkuara nga operacione logjike (lidhëse).
Shprehje (deklarata) të ndryshme logjike mund të marrin vetëm dy kuptime: "e vërtetë" ose "e rreme". Çdo variabël boolean mund të marrë vetëm një vlerë. Ka opsione të ndryshme denotimet e së vërtetës dhe të pavërtetës:
E vërtetë
DHE
E vërtetë
T
1
Gënjeshtra
L
E rreme
F
0
Deklaratat mund të jenë të thjeshta ose komplekse. Ato të thjeshta korrespondojnë me variablat algjebrike, dhe ato komplekse janë një analog funksionet algjebrike. Funksionet mund të merren duke kombinuar variabla duke përdorur veprimet logjike(operacionet).
Le të shqyrtojmë operacionet logjike me të cilat mund të shkruani ndonjë shprehje logjike.
Operacioni më i thjeshtë logjik është operacioni NOT (me fjalë të tjera, ai shpesh quhet mohim, shtim ose përmbysje dhe shënohet ). Rezultati i një mohimi është gjithmonë e kundërta e kuptimit të argumentit. Të tjerët fjalë të thjeshta, ky veprim do të thotë që grimca "jo" ose fjalët "nuk është e vërtetë që" i shtohen shprehjes logjike origjinale.
Kështu, me mohim ndonjë deklaratë është një pohim që është i vërtetë kur false, dhe false kur e vërtetë.
Operacioni logjik NUK është i njëanshëm, d.m.th. ka vetëm një operand. Përkufizimi i një mohimi mund të shkruhet duke përdorur një të ashtuquajtur tabelë të së vërtetës, e cila specifikon se cilat vlera të së vërtetës (1, 0) merr mohimi në varësi të vlerave të së vërtetës së deklaratës origjinale :
1
0
0
1
Logjike AND (shumëzimi ose lidhja logjike) është një shprehje logjike komplekse që konsiderohet e vërtetë nëse dhe vetëm nëse të dyja shprehje të thjeshta janë të vërteta, në të gjitha rastet e tjera kjo shprehje komplekse e rreme. Lidhja e deklaratave dhe shënoni: , dhe ndonjëherë ata thjesht shkruajnë . Deklaratat në një lidhëz lidhen me lidhëzën "dhe". Përkufizimi i një lidhjeje mund të shkruhet si një tabelë e së vërtetës, në të cilën për secilën nga katër grupet e mundshme të vlerave të pohimeve origjinale Dhe vendoset kuptimi përkatës i lidhëzës :
1
1
1
1
0
0
0
1
0
0
0
0
Përkufizimi i një lidhjeje të dy pohimeve shtrihet natyrshëm në cilindo numri përfundimtar komponentët: lidhëza A 1 &A 2 &A 3 &...&A N e vërtetë nëse dhe vetëm nëse të gjitha pohimet janë të vërteta A 1 , A 2 , A 3 , ...A N(dhe, për rrjedhojë, e rreme kur të paktën një nga këto pohime është e rreme).
OSE logjike (shtimi ose shkëputja logjike) është një shprehje logjike komplekse që është e vërtetë nëse të paktën një nga shprehjet e thjeshta logjike është e vërtetë dhe e gabuar nëse dhe vetëm nëse të dyja shprehjet e thjeshta logjike janë të rreme. Ndarja e deklaratave Dhe do të shënojmë me simbolin dhe ne do të lexojmë: ose . Përkufizimi i një ndarjeje mund të shkruhet si një tabelë e së vërtetës:
1
1
1
1
0
1
0
1
1
0
0
0
Përkufizimi i një shkëputjeje të dy pohimeve shtrihet natyrshëm në çdo numër të kufizuar përbërësish: disjunksionA 1 A 2 A 3 ... A N e vërtetë nëse dhe vetëm nëse të paktën një nga pohimet është e vërtetëA 1 , A 2 , A 3 , ..., A N (dhe për këtë arsye e rreme kur të gjitha këto deklarata janë të rreme).
Formohen operacionet AND, OR, dhe NOT sistem të plotë operacionet logjike, nga të cilat mund të ndërtoni një shprehje logjike arbitrarisht komplekse. Por përveç tyre, ka edhe operacione të tjera logjike.
Implikimi logjik (nënkuptimi) është një shprehje logjike komplekse që është e vërtetë në të gjitha rastet, përveç kur një gënjeshtër rrjedh nga e vërteta. Kjo do të thotë, ky operacion logjik lidh dy shprehje të thjeshta logjike, nga të cilat e para është një kusht (), dhe e dyta ( ) është pasojë. Le ta shënojmë nënkuptimin me simbolin dhe hyrja " “ do të lexojmë: “Nga vijon."
Le ta shkruajmë këtë përkufizim në formën e një tabele të së vërtetës:
1
1
1
1
0
0
0
1
1
0
0
1
Deklarata "Nëse, atëherë" nga pikëpamja logjike ka të njëjtin kuptim si thënia "nuk është e vërtetë se ajo që është e vërtetë dhe e rreme". Kjo do të thotë që funksioni i nënkuptimit mund të zëvendësohet nga një kombinim i dy funksioneve (negimi dhe lidhja).
Një identitet logjik (ekuivalencë) është një shprehje logjike komplekse që është e vërtetë nëse dhe vetëm nëse të dyja shprehjet e thjeshta logjike kanë të njëjtën të vërtetë. Ekuivalenca tregohet nga simboli dhe hyrja "" lexohet "ekuivalente", ose "ekuivalente", ose " , nëse dhe vetëm nëse », « atëherë dhe vetëm nëse " Përkufizimi i ekuivalencës mund të shkruhet si një tabelë e së vërtetës:
1
1
1
1
0
0
0
1
0
0
0
1
Funksionet logjike dhe transformimi i tyre
Një funksion logjik është një funksion i ndryshoreve logjike që mund të marrë vetëm dy vlera: 0 ose 1. Nga ana tjetër, vetë ndryshorja logjike (argumenti i një funksioni logjik) mund të marrë gjithashtu vetëm dy vlera: 0 ose 1.
Çdo funksion logjik mund të specifikohet një numër i madh funksione të llojeve të ndryshme. Por edhe çdo funksion logjik mjaft kompleks mund të zbatohet me një grup relativisht të thjeshtë të operacioneve bazë logjike. Baza më e njohur është një grup funksionesh "dhe", "ose", "jo".
Për operacionet e lidhjes, ndarjes dhe përmbysjes, janë përcaktuar ligje që lejojnë transformime identike (ekuivalente) të shprehjeve logjike:
;
.
Bazuar në ligjet, është e mundur të thjeshtohen shprehjet logjike komplekse.
Për arsye të lehtësisë së transformimeve të mëvonshme, dy format e mëposhtme kanonike të përfaqësimit të funksioneve pranohen si fillestare: forma normale e përsosur disjunctive (PDNF) dhe forma normale e përsosur lidhore (PCNF).
Përpara se të kalojmë te SDNF dhe SKNF, le të prezantojmë disa koncepte.
Lidhëza elementare është një lidhje e disa ndryshoreve, të marra me ose pa mohim, dhe midis variablave mund të ketë të njëjtat.
Dijunksioni elementar është dijunksioni i disa ndryshoreve, të marra me ose pa mohim, dhe midis variablave mund të ketë edhe të njëjtë.
Çdo ndarje e lidhëzave elementare quhet një formë normale disjunktive, domethënë DNF.
Për shembull, shprehjaështë DNF.
Çdo lidhëz e disjuksioneve elementare quhet formë normale lidhore, domethënë CNF.
Për shembull, shprehjaështë KNF.
Një DNF e përsosur (PDNF) është një DNF në të cilën nuk ka lidhje elementare të barabarta dhe të gjitha përmbajnë të njëjtat ndryshore, me secilën ndryshore vetëm një herë (ndoshta me mohim).
Për shembull, shprehja është DNF, por jo SDNF; shprehjeështë SDNF.
Një CNF e përsosur (SCNF) është një CNF në të cilën nuk ka ndarje elementare të barabarta dhe të gjitha përmbajnë të njëjtat ndryshore, me secilën ndryshore vetëm një herë (ndoshta me mohim).
Për shembull, shprehja .
Unë do të jap algoritme për kalimet nga një formë në tjetrën. Natyrisht, në raste specifike(në njëfarë qasje krijuese) përdorimi i algoritmeve mund të jetë më i mundimshëm sesa transformimet e thjeshta duke përdorur një lloj specifik të një forme të caktuar:
kalimi nga caktimi arbitrar i funksionit në DNF
Ky tranzicion vjen në mospërmbushjen e përmbysjeve të zakonshme për disa ndryshore, duke hapur kllapa dhe duke kombinuar, nëse ato lindin, terma identikë duke përdorur ligjet:
Për shembull:
kalimi nga DNF në KNF
Algoritmi për këtë tranzicion është si vijon: ne vendosim dy mohime mbi DNF dhe, duke përdorur rregullat e De Morgan (pa prekur mohimin e sipërm), ne reduktojmë mohimin e DNF përsëri në DNF. Në këtë rast, duhet të hapni kllapat duke përdorur rregullin e thithjes. Negacioni (i sipërm) i DNF-së që rezulton (përsëri sipas rregullit të de Morgan) na jep menjëherë CNF-në:
Mënyra e dytë për të kaluar nga DNF në CNF është përdorimi i ligjit shpërndarës:
kalimi nga KNF në DNF
Ky tranzicion realizohet thjesht duke hapur kllapat (duke përdorur përsëri rregullin e përthithjes):
kalimi nga KNF në SKNF
Ky tranzicion kryhet në një mënyrë të ngjashme me atë të mëparshme: nëse një ndarje të thjeshtë i mungon një variabël, për shembull,z , pastaj shtoni shprehjen në të (kjo nuk e ndryshon vetë ndarjen), pas së cilës hapim kllapat duke përdorur ligjin e shpërndarjes:
kalimi nga DNF në SDNF
Nëse ndonjë lidhjeje të thjeshtë i mungon një ndryshore, për shembull,z , atëherë shumëzojmë lidhëzën jo të plotë me një shprehje të formës , pas së cilës hapim kllapat (nuk shkruajmë terma të ndarë përsëritës). Për shembull:
Për të marrë SDNF dhe SCNF nga tabelat e së vërtetës, duhet të kryeni 4 pikat e mëposhtme të algoritmit:
SDNF
SKNF
Ndërtimi i SDNF dhe SKNF fillon me një tabelë të së vërtetës.
Le të shënojmë ato rreshta të tabelës, rezultatet e të cilave janë të barabarta
1
0
Për çdo rresht të shënuar, ne shkruajmë një kombinim variablash duke përdorur shenjën
lidhëza (&)
ndarje (V)
Vendosim shenjat e operacionit të mohimit si më poshtë:
nëse një ndryshore është e barabartë me 1, atëherë e shkruajmë vetë këtë ndryshore nëse është e barabartë me 0, atëherë shkruajmë mohimin e saj.
nëse një ndryshore është e barabartë me 0, atëherë e shkruajmë vetë këtë ndryshore nëse është e barabartë me 1, atëherë shkruajmë mohimin e saj.
Ne i lidhim të gjitha shprehjet që rezultojnë me operacionin
ndarjet
lidhëzat
Pasi të keni marrë SDNF ose SKNF, mund të përpiloni qark elektronik, duke zbatuar këtë funksion logjik. Duhen 3 për ta ndërtuar atë porta logjike :
inverter
lidhës
ndarës
Por më shpesh SDNF përmban shumë terma dhe detyra është të zvogëlojë numrin e tyre dhe të thjeshtojë shprehjen logjike. Për të thjeshtuar funksionet logjike, mund të përdorni ligjet e logjikës të dhëna më sipër. Për të njëjtin qëllim, ato u zhvilluan metoda të veçanta, e cila do të diskutohet në seksionin vijues.
Minimizimi i funksioneve logjike
Siç vërehet në kapitulli i mëparshëm, një funksion logjik mund të përfaqësohet në formën e një tabele të vërtetësisë ose në formën e SDNF (formë normale e përsosur disjunctive) ose SCNF (formë normale e përsosur konjuktive) dhe mund të përdoret për të marrë qarkun logjik të pajisjes. Megjithatë, qarku logjik që rezulton në përgjithësi nuk do të jetë optimal. Kjo është arsyeja pse fazë e rëndësishme Sinteza e qarqeve logjike është minimizimi i funksioneve logjike.
Minimizimi është transformimi i funksioneve logjike me qëllim të thjeshtimit të paraqitjes analitike të tyre.
Ekzistojnë dy drejtime për minimizimin:
Forma më e shkurtër e shënimit (kjo prodhon format më të shkurtra KDNF, KKNF, KPNF);
Marrja e formularit minimal të regjistrimit (marrja e numrit minimal të karaktereve për të shkruar të gjithë funksionin menjëherë).
Por duhet theksuar se asnjë nga metodat e minimizimit nuk është universale.
Janë zhvilluar një sërë metodash për të minimizuar funksionet e algjebrës logjike:
metoda e shndërrimeve të drejtpërdrejta të funksioneve logjike;
metoda për minimizimin e funksioneve logjike duke përdorur hartat Karnaugh;
Metoda Quine-McCluskey;
Metoda Blake-Poretsky;
Metoda e Petrikut dhe të tjerët.
Le të ndalemi më në detaje në dy metodat e para.
Metoda e shndërrimeve të drejtpërdrejta të funksioneve logjike
Një nga metoda të thjeshta minimizimi është një metodë e transformimeve të drejtpërdrejta, e cila kryhet duke përdorur teoremat bazë të algjebrës së logjikës.
Kur përdorni këtë metodë:
Funksionet logjike SDNF janë shkruar,
Forma është transformuar dhe thjeshtuar duke përdorur aksiomat e algjebrës së logjikës, dhe, në veçanti, identifikohen termat fqinjë (anëtarët) në SDNF origjinale, në të cilat ka një ndryshore që nuk përkon.
Ligji i ngjitjes vlen për termat fqinjë.
Termat e formuar nga ngjitja quhen implikante.
Implikantët e fituar pas ngjitjes ngjiten së bashku, nëse është e mundur, derisa ngjitja të bëhet e pamundur.
Funksioni i përftuar si rezultat i minimizimit quhet funksion i rrugës pa krye.
Le të jepet funksioni
Ne e minimizojmë atë duke përdorur metodën e përshkruar më sipër. Për ta bërë këtë, ne shtojmë një term tjetër dhe përdorni ligjet e ngjitjes.
Ne morëm funksionin minimal
Metoda e konsideruar e minimizimit me transformime direkte është mjaft e thjeshtë, veçanërisht me një numër të vogël variablash. Disavantazhi i metodës është se nuk tregon një rrugë minimizimi të formalizuar rreptësisht. Me një numër të madh variablash, mintermat mund të grupohen ndryshe, duke rezultuar në forma të ndryshme të thjeshtuara funksioni i dhënë. Megjithatë, nuk mund të jetë i sigurt se ndonjë nga këto forma është minimale. Ka mundësi që të jetë marrë një nga format qorre, e cila nuk është më e thjeshtuar, pa qenë minimale.
Metoda për minimizimin e funksioneve logjike duke përdorur hartat Karnaugh
Harta Carnaugh ose harta Veitch (diagrami) - metodë grafike minimizimi i funksioneve të algjebrës logjike.
Hartat e Karnaugh janë të dobishme kur ka një numër të vogël variablash.
Hartat Carnaugh përfaqësojnë tabelë specifike Vlerat e së vërtetës zakonisht janë për dy, tre dhe katër variabla dhe ndryshojnë nga njëra-tjetra në mënyrën se si caktohen rreshtat dhe kolonat e tabelave të së vërtetës.
Në Fig. 1 tregon hartat Veitch për dy, tre dhe katër variabla, respektivisht.
oriz. 1
Vendndodhja e grupeve të ndryshueshme x nuk ka rëndësi, është e nevojshme vetëm që çdo qelizë të ndryshojë nga çdo qelizë fqinje vetëm me një ndryshore. Sipas formë e pranuar Gjatë ndërtimit të hartave, qelizat e rreshtit të parë dhe të fundit dhe qelizat e kolonës së parë dhe të fundit konsiderohen gjithashtu ngjitur. Numri i qelizave të hartës është i barabartë me numrin kombinime të mundshme vlerat e variablave (termet) dhe vlera e funksionit logjik që i korrespondon këtë grup variablave. Nëse ndonjë nga kombinimet e mundshme është i pranishëm në formën normale të përsosur ndarëse (PDNF) të shkrimit të funksionit, atëherë "1" vendoset në qelizën përkatëse të hartës Carnot. Nëse nuk ka asnjë term në funksionin që rezulton, atëherë "0" vendoset në qelizën përkatëse të hartës Carnaugh.
Për shembull, funksioni i konsideruar në shembullin e mëparshëm
e specifikuar nga tabela e së vërtetës (Fig. 2 a) gjithashtu mund të minimizohet duke përdorur hartat Carnaugh. Harta e Karnaugh për të do të ketë formën e treguar në Fig. 2 b.
oriz. 2
Në hartën e Carnaugh ka logjike 1 , të shkruara në qelizat ngjitur, tregojnë se korrespondon me këto 1 lidhëzat (produktet) ndryshojnë vetëm në një ndryshore, të cilat plotësojnë njëra-tjetrën dhe mund të hiqen.
Pra, në rreshtin e parë të hartës Karnaugh (shih Fig. 2 b) ndryshorja X , ndodh në kombinim me X 1 Dhe X 2 , të cilat plotësojnë njëra-tjetrën:
Kështu, duke grupuar dy qeliza ngjitur në rreshtin e sipërm (kontura në Fig. 2 b), një variabël mund të eliminohet - X 1 .
Në mënyrë të ngjashme, duke grupuar dy qeliza ngjitur në kolonën e majtë (kontura në Fig. 2 b) dhe duke përjashtuar variabla të ndryshëm, marrim një shprehje të thjeshtuar - X 2 .
Shprehjet e thjeshtuara që rezultojnë kombinohen duke përdorur operacionin OR.
Në këtë mënyrë, qelizat ngjitur në një hartë Karnaugh mund të grupohen për të eliminuar një ndryshore. Numri i qelizave të grupuara mund të jetë më shumë se dy, por numri i tyre duhet të jetë çift dhe duhet të jenë në kontakt (fqinj) me njëra-tjetrën.
Është gjithashtu e mundur që të ketë disa grupe qelizash të mbivendosura, si në shembullin e sapo diskutuar.
Qelizat e rreshtit të parë dhe të fundit, kolona e parë dhe e fundit gjithashtu mund të grupohen, d.m.th., harta mund të rrotullohet në një cilindër si përgjatë boshtit vertikal ashtu edhe horizontal.
Për të përjashtuar n variablat numri total qelizat e grupuara duhet të jenë të barabarta 2 n. Kështu, për të përjashtuar një variabël, është e nevojshme të kombinohen dy qeliza fqinje, dhe për të përjashtuar tre ndryshore, tashmë është e nevojshme të kombinohen tetë qeliza fqinje.
Kështu, për të marrë një funksion logjik të minimizuar, është e nevojshme të grupohen të gjitha qelizat fqinje të hartës Carnaugh që përmbajnë 1, dhe më pas të kombinohen grupet që rezultojnë duke përdorur operacionin OR. Qelizat që përmbajnë 1, të cilat nuk mund të kombinohen me qeliza të tjera, formojnë terma të pavarur në funksionin logjik të minimizuar, secila prej të cilave përmban të gjitha variablat.
Le të shohim disa shembuj të hartave Veitch dhe si të ndërtojmë konturet e grupimeve të qelizave fqinje për të marrë një funksion logjik të thjeshtuar.
Kështu, harta Veitch për funksionin logjik
është paraqitur në figurën 3.
oriz. 3
Kjo foto tregon mënyrën e duhur duke kombinuar qelizat fqinje, d.m.th., harta Veitch është, si të thuash, e palosur në një cilindër të vendosur vertikalisht.
Një shprehje e thjeshtuar për një funksion logjik është
Kështu, duke grupuar qelizat fqinje në një katror të vetëm, ishte e mundur të eliminoheshin dy variabla ( X 1 Dhe X 2 ) dhe merrni një shprehje të thjeshtë për funksionin logjik.
Le të shqyrtojmë një shembull të minimizimit të një funksioni logjik
Harta e Karnaugh për këtë funksion është paraqitur në Figurën 4:
oriz. 4
Qelizat që do të grupohen janë të rrethuara nga dy skica. Kontura e poshtme bën të mundur eliminimin e një ndryshorejeX 3 dhe pas kësaj një anëtar mbetet në të.
Në ciklin e sipërm, dy variabla mund të eliminohen (X 2 Dhe X 4 ) dhe pas kësaj anëtari mbetet në të. Një shprehje e thjeshtuar Boolean për një funksion logjik është
Le të shqyrtojmë minimizimin e një funksioni logjik, harta Veitch e të cilit është paraqitur në Fig. 5.
oriz. 5
Shprehja Boolean për këtë funksion është
Katër qelizat qoshe mund të kombinohen në një grup. Ky bashkim eliminon dy variabla (X 1 Dhe X 2 ) dhe merrni një anëtar.
Dy njësi nga rreshti i parë mund të kombinohen me dy njësi nga fundi, merrni një grup prej katër qelizave që ju lejon të përjashtoni dy variabla (X 1 Dhe X 3 ) dhe merrni një anëtar.
Së fundi, e vetmja 1 e mbetur (nga rreshti i dytë dhe kolona e fundit) mund të kombinohet me qelizën mbi të, duke eliminuar një ndryshore (X 4 ) dhe merrni një anëtar.
Kështu, marrim funksionin logjik të minimizuar
Metoda e hartave Karnaugh (diagramet Veitch), në thelb, thjeshton gjetjen e lidhjeve të ngjitura në SDNF të funksionit logjik origjinal.
Minimizimi i funksioneve të algjebrës logjike duke përdorur metodat e përshkruara
Ky kapitull paraqet funksionet që kemi zgjedhur dhe shembuj të minimizimit të tyre duke përdorur metodat e diskutuara më sipër.
Thjeshtoni përdorimin e hartave Carnaugh për një funksion prej 2 variablash:
Harta e Karnaugh (diagrami Vaitch) për këtë funksion do të duket si kjo:
Në rreshtin e parë mund të përjashtoni variablin X 2 dhe merrni një shprehje të thjeshtuar X 1 .
Në kolonën e dytë mund të përjashtoni variablinX 1
Kështu, do të duket një shprehje e thjeshtuar e funksionit logjik
Në kolonën e parë mund të përjashtoni variablin X 1 dhe merrni një shprehje të thjeshtuar X 2 .
Në rreshtin e dytë, mund të eliminoni variablin dhe të merrni një shprehje të thjeshtuar.
Ne lidhim shprehjet e thjeshtuara që rezultojnë duke përdorur operacionin OR.
Kështu, do të duket një shprehje e thjeshtuar e funksionit logjik
Thjeshtoni përdorimin e hartave Carnaugh për një funksion prej 3 variablash:
Diagrami Veitch për këtë funksion do të duket kështu:
X 3 dhe merrni një shprehje të thjeshtuar.
X 3 dhe merrni një shprehje të thjeshtuar.
Në kolonën e fundit mund të përjashtoni variablinX 1 dhe merrni një shprehje të thjeshtuar.
Ne lidhim shprehjet e thjeshtuara që rezultojnë duke përdorur operacionin OR.
Kështu, do të duket një shprehje e thjeshtuar e funksionit logjik
Diagrami Veitch për këtë funksion do të duket kështu:
Në rreshtin e parë mund të përjashtoni variablinX 3 dhe merrni një shprehje të thjeshtuar dhe një ndryshoreX 2 dhe merrni një shprehje të thjeshtuar.
Ne lidhim shprehjet e thjeshtuara që rezultojnë duke përdorur operacionin OR.
Kështu, do të duket një shprehje e thjeshtuar e funksionit logjik
Ne gjetëm gjithashtu një mënyrë të dytë për të minimizuar këtë funksion.
Atëherë diagrami Veitch për këtë funksion do të duket si ky:
Në rreshtin e parë mund të përjashtoni variablinX 3 dhe merrni një shprehje të thjeshtuar.
Rreshti i parë përmban shprehjen .
Ne lidhim shprehjet që rezultojnë duke përdorur operacionin OR.
Kështu, do të duket një shprehje e thjeshtuar e funksionit logjik
Natyrisht, funksioni që rezulton nuk është minimal, kështu që ne do të përdorim metodën e transformimeve të drejtpërdrejta të funksioneve logjike. Le ta heqim ndryshoren nga kllapatX 1 dhe për shprehjen në kllapa zbatojmë rregullin e konvolucionit. Marrë të njëjtin rezultat si në rastin e parë.
Kjo do të thotë që qelizat fqinje mund të grupohen në mënyra të ndryshme, gjëja kryesore është të mos harrohet rregulli bazë: për përjashtim n variablave, numri i përgjithshëm i qelizave të grupuara duhet të jetë i barabartë me 2 n .
Diagrami Veitch për këtë funksion do të duket kështu:
rreshti i parë mund të përjashtojë variablin X 3 dhe merrni një shprehje të thjeshtuar.0 1 0 0
Rreth kolonës së dytë mund të përjashtoni variablin X 1 .
Ne lidhim shprehjet e thjeshtuara që rezultojnë duke përdorur operacionin OR.
Kështu, do të duket një shprehje e thjeshtuar e funksionit logjik
Diagrami Veitch për këtë funksion do të duket kështu:
Në rreshtin e parë mund të përjashtoni variablinX 3 dhe merrni një shprehje të thjeshtuar.
Në rreshtin e dytë mund të përjashtoni variablinX 3 dhe merrni një shprehje të thjeshtuar.
Ne lidhim shprehjet e thjeshtuara që rezultojnë duke përdorur operacionin OR.
Kështu, do të duket një shprehje e thjeshtuar e funksionit logjik
Diagrami Veitch për këtë funksion do të duket kështu:
Mund të përjashtoni variablat në kolonën e parë dhe të funditX 1 Dhe X 2 dhe merrni një shprehje të thjeshtuar.
Në rreshtin e dytë mund të përjashtoni variablinX 2 dhe merrni një shprehje të thjeshtuar. RRETH .
Ne lidhim shprehjet e thjeshtuara që rezultojnë duke përdorur operacionin OR.
Kështu, do të duket një shprehje e thjeshtuar e funksionit logjik
Ky kapitull prezantoi funksionet e dy, tre dhe katër variablave që u minimizuan duke përdorur diagramet Veitch. Kam demonstruar dhe përshkruar qartë tiparet e përdorimit të kësaj metode të minimizimit në funksione të ndryshme, duke përfshirë në kombinim me metodën e transformimit të drejtpërdrejtë të funksioneve të algjebrës logjike.
konkluzioni
Puna e paraqitur i kushtohet metodave për minimizimin e funksioneve të algjebrës logjike. Gjatë punës ishin:
janë studiuar elementet bazë të logjikës matematikore;
janë studiuar metodat për minimizimin e funksioneve logjike;
detyra të zgjedhura për punë të pavarur;
problemet e përzgjedhura u zgjidhën duke përdorur metodat e përshkruara.
Shqyrtova në detaje 2 metoda për minimizimin e funksioneve logjike:
metoda e shndërrimeve të drejtpërdrejta të funksioneve logjike, e kryer duke përdorur teorema të algjebrës logjike;
metoda e minimizimit duke përdorur diagramet Veitch (hartat Karnaugh).
Metoda e parë mori e përhapur edhe në tekstet shkollore shkenca kompjuterike (për shembull, tekste shkollore për klasat 10-11 nga N. Ugrinovich, L. Shchautsukova), pasi është një nga metodat e thjeshta të thjeshtimit të funksioneve të algjebrës logjike. Detyrat e paraqitura në tekstet shkollore të këtyre autorëve janë mjaft të ndryshme:
thjeshton një formulë logjike duke përdorur ligjet e algjebrës logjike;
të ndërtojë një qark logjik bazuar në një funksion të caktuar;
thjeshtoni qarkun e kalimit;
të provojë një shprehje logjike duke përdorur një tabelë të së vërtetës;
Ndërtoni një tabelë të vërtetësisë për këtë funksion.
Metoda e dytë ju lejon të eliminoni shpejt dhe me lehtësi variabla të ndryshëm dhe të merrni një shprehje të thjeshtuar që mund të mos jetë gjithmonë minimale. Prandaj, kjo metodë duhet të konsiderohet në lidhje me metodën e transformimeve të drejtpërdrejta të funksioneve logjike.
Kjo temë ka rëndësi praktike në mikroelektronikë. Përveç kësaj, Provimi i Unifikuar i Shtetit në shkencat kompjuterike dhe TIK përmban një sërë detyrash që lidhen me algjebrën logjike, të cilat i kemi ndarë në 4 grupe.
Grupi i parë janë detyra që kërkojnë nga ju të tregoni një shprehje logjike të barabartë me atë të dhënë.
Grupi i dytë është detyra për gjetjen e fragmenteve të tabelave të së vërtetës që korrespondojnë me një shprehje të caktuar.
Grupi i tretë përfshin detyra për të gjetur vërtetësinë e deklaratave për çdo vlerë të ndryshoreve X Dhe në .
Dhe grupi i katërt është detyra për të përcaktuar formula strukturore, që korrespondon me këtë qark logjik.
Nuk kam hasur në asnjë detyrë që lidhet posaçërisht me minimizimin e funksioneve logjike, por detyrat e disponueshme në teste kërkojnë mjaft njohuri të thella në fushën e logjikës algjebër.
Për shkak të kompleksitetit në rritje të testeve pranuese në arsimin e lartë institucionet arsimore mund të supozohet se së shpejti në teste, dhe për këtë arsye në programet arsimore, detyrat mund të duket se thjeshtojnë dhe minimizojnë funksionet logjike.
Referencat
Gavryukova G. A. Logjika në shkencën kompjuterike [ Burim elektronik]. – Mënyra e hyrjes: tetor. 2010).
Ivin A. A. Logic: Tutorial. - botimi i 2-të. – M.: Dituria, 1998. – 233 f.
Igoshin V.I. Logjika matematikore dhe teoria e algoritmeve: Libër mësuesi për nxënës. më të larta teksti shkollor ndërmarrjet. – Botimi i 2-të, i fshirë. – M.: Akademia, 2008. – 448 f.
Shkenca Kompjuterike dhe TIK. Përgatitja për Provimin e Unifikuar të Shtetit 2009. Testet e hyrjes. / Ed. F. F. Lysenko. – Rostov n/d: Legion-M, 2009. – 208 f.
Shkenca Kompjuterike: Teksti mësimor / B.V. Sobol [etj.]. – Botimi i 3-të, shto. dhe të përpunuara – Rostov n/d: Phoenix, 2007. – 446 f.
Shkenca Kompjuterike: Libër shkollor / A. V. Mogilev, N. I. Pak, E. K. Henner. - botimi i 3-të. – M.: Akademia, 2004. – 848 f.
Kalabekov B. A. Pajisjet dixhitale dhe sistemet mikroprocesorike: Libër mësuesi për shkollat teknike të komunikimit. – M.: Linja telefonike – Telekom, 2000. – 336 f.
Kaimin V. A. Shkenca Kompjuterike: Libër mësuesi. – Botimi i 2-të, i rishikuar. dhe shtesë – M.: INFRA-M, 2001. – 272 f.
Kovalenko A. A, Petropavlovsky M. D. Bazat e mikroelektronikës: Libër mësuesi. – M.: Akademia, 2006. – 240 f.
Lvovsky M. B. Manual metodik në shkenca kompjuterike për studentët e klasave 9-11 që studiojnë IBM PC [Burimi elektronik]. – Mënyra e hyrjes: Shtator. 2010).
Bazat matematikore të shkencës kompjuterike. Lëndë me zgjedhje: Libër mësuesi / E. V. Andreeva, L. L. Bosova, I. N. Falina. – M.: BINOM. Laboratori i Dijes, 2005. – 328 f.
Minimizimi i funksioneve logjike [Burimi elektronik]. – Mënyra e hyrjes: Gusht. 2010).
Bazat e mikroelektronikës: Libër shkollor për universitetet / N. A. Avaev, Yu E. Naumov, V. T. Frolkin. – M.: Radio dhe komunikime, 1991. – 288 f.: ill.
Punëtori për shkencën kompjuterike dhe teknologjitë e informacionit / N. D. Ugrinovich, L. L. Bosova, N. I. Mikhailova. – Botimi i 2-të, rev. – M.: BINOM. Laboratori i Dijes, 2004. – 394 f.
Matematikë e aplikuar: Manual / I. N. Revchuk, V. K. Pchelnik. – Grodno: Universiteti Shtetëror Grodno me emrin. Ya. Kupala, 2007. – 128 f.
Rabkin E. L., Farforovskaya Yu B. Matematikë diskrete: Funksionet Boolean dhe elementet e teorisë së grafikut: Udhëzimet Dhe detyrat e kontrollit[Burimi elektronik]. – Mënyra e hyrjes: 7 gusht 2010).
Savelyev A. Ya. Bazat e shkencës kompjuterike: Libër shkollor për universitetet. – M.: MSTU im. N. E. Bauman, 2001. – 328 f., ill.
Stepanenko I.P. Bazat e mikroelektronikës: Libër shkollor për universitetet. – Botimi i 2-të, i rishikuar. dhe shtesë – M.: Laborator Njohuri Bazë, 2001. – 488 f.
Teoria dhe metodologjia e mësimdhënies së shkencave kompjuterike: Libër mësuesi / [M. P. Lapchik, I. G. Semakin, E. K. Henner, M. I. Ragulina etj.]; redaktuar nga M. P. Lapchik. – M.: Akademia, 2008. – 592 f.
Ugrinovich N.V. Informatikë dhe TIK. klasa e 10-të. Niveli i profilit. – Botimi i 3-të, rev. – M.: Binom. Laboratori i Dijes, 2008. – 387 f.
Ugrinovich N.V. Informatikë dhe Teknologjia e informacionit: Libër mësuesi për klasat 10-11. - M.: BINOMIAL. Laboratori i Dijes, 2003. – 512 f.
Shautsukova L.Z Informatikë 10 – 11. – M.: Arsimi, 2004. – 420 f.
Kohëzgjatja: 2 orë (90 min.)
14.1 Çështjet kryesore
14 Leksioni nr 13. Minimizimi i funksioneve logjike 1
14.1 Çështjet kryesore 1
14.2 Teksti i leksionit 1
14.2.1 Minimizimi i funksioneve logjike 1
14.2.1.1 Metoda e llogaritjes 1
14.2.1.2 Hartat e Carnot 4
14.2.2 Minimizimi i sistemeve ekuacionet logjike 7
14.2.3 Minimizimi i funksioneve logjike të përcaktuara pjesërisht 8
14.2.4 Pyetje për kontroll 10
14.2 Teksti i ligjëratës
14.2.1 Minimizimi i funksioneve logjike
Ka mjaft metoda për minimizimin e funksioneve logjike këtu janë vetëm dy metoda që përdoren më shpesh në praktikën inxhinierike:
vendbanimi;
Harta e Carnot.
14.2.1.1 Mënyra e llogaritjes
Këtu ata aplikojnë:
- ngjitje,
- përthithja,
– vendosja.
Lidhja
a) Nëse shprehja përmban shumën e dy lidhëzave, në njërën prej të cilave njëri prej variablave është në kuptimi i drejtpërdrejtë, dhe në tjetrën në një vlerë të anasjelltë, dhe ndryshoret e mbetura janë të njëjta, atëherë kjo shumë e lidhjeve mund të zëvendësohet nga një lidhëz që nuk përmban një ndryshore që ka vlera të ndryshme:
Lidhëzat që ndryshojnë vetëm në vlerat e njërës ndryshore (ndryshorja hyn në njërën prej tyre pa mohim, dhe tjetra me mohim) quhen ngjitur.
Koment:
dhe ligji shpërndarës i lidhjes në lidhje me disjunksionin (shih Leksionin nr. 10)
.
b) Nëse në një shprehje ka një prodhim të dy disjuksioneve, në njërën prej të cilave njëri prej ndryshoreve është në vlerën e drejtpërdrejtë, dhe në tjetrin në vlerën e anasjelltë, dhe ndryshoret e mbetura janë të njëjta, atëherë ky produkt i disjuksioneve. mund të zëvendësohet nga një ndarje që nuk përmban një ndryshore që ka vlera të ndryshme:
Ndarjet që ndryshojnë vetëm në vlerat e njërës ndryshore (ndryshorja hyn në njërën prej tyre pa mohim, dhe tjetra me mohim) quhen ngjitur.
Koment: Ky rregull bazohet në ligjin e komplementaritetit 
dhe ligji shpërndarës i disjuksionit në lidhje me lidhëzën (shih Leksionin nr. 10)
c) Rregulla të përgjithësuara të ngjitjes.
Në rastin e parë, puna u zhduk p.e.s, në të dytën shuma zhduket b 
c, në të tretën sërish puna p.e.s(rasti i tretë pas hapjes së kllapave zvogëlohet në të parën). Këto rregulla vërtetohen, si zakonisht, duke përpiluar dhe krahasuar tabelat e së vërtetës për anën e majtë dhe të djathtë ose duke përdorur zgjerimin (shih më poshtë).
Absorbimi
a) Nëse shprehja përmban shumën e dy produkteve, njëri prej të cilëve është pjesë e tjetrit, atëherë kjo shumë mund të zëvendësohet me një produkt më të vogël:
b) Nëse shprehja përmban një produkt të dy shumave, njëra prej të cilave është pjesë e tjetrës, atëherë ky produkt i shumave mund të zëvendësohet me një shumë më të vogël:
a(a 
b)= a;a(a 
b)(a 
c)…=a;
(a 
b)(a 
b 
c)= a 
b.
Vendosja
Zgjerimi ju lejon të rivendosni variablat "të humbur" (për shembull, si rezultat i minimizimit) në formula ose të lëvizni nga DNF dhe CNF në forma perfekte– SDNF dhe SKNF. Rindërtimi i variablave për DNF dhe CNF kryhet ndryshe. Le të shohim shembuj.
Le të kemi DNF
në të cilën ndryshorja është dukshëm e humbur y. Për të rivendosur një ndryshore y produkt i variablave xz shumëzohet me 1, atëherë 1 zëvendësohet nga shuma e përcaktimeve të drejtpërdrejta dhe të anasjellta të ndryshores që mungon, dhe bëhet një transformim bazuar në ligjin shpërndarës
Le të kemi CNF 
, ku humbet edhe ndryshorja y. Për ta rikthyer atë në sasi 
0 shtohet, pastaj 0 zëvendësohet nga prodhimi i ndryshores që mungon dhe anasjelltas i saj dhe zbatohet ligji shpërndarës
Duke përdorur zgjerimin, mund të zbulohet kuptimi i koncepteve të "përbërësi i një" dhe "përbërësi i zeros".
Le n= 2 (ndryshore a Dhe b).
Le të zgjerojmë njësinë 1.
1= 1
=
=.
Ne morëm funksionet SDNF të dy variablave f= 1, ku çdo lidhëz është një përbërës (përbërës) i njësisë.
Le të zgjerojmë 0.
Ne morëm funksionet SCNF të dy variablave f= 0, ku çdo disjunksion është një komponent (përbërës) i zeros.
Dobia e zgjerimit tregohet nga një shembull i vërtetimit të rregullave të ngjitjes së përgjithësuar (shih seksionin 4.1.1):
Le të shqyrtojmë rregullin e parë
Le të zgjerojmë anën e majtë të identitetit, në produktin e parë të të cilit mungon ndryshorja c, mungon vepra e dytë b, por jo në të tretën a.
Pas sjelljes anëtarë të ngjashëm duke përdorur ngjitje të thjeshtë
marrim krahun e djathtë, prandaj vërtetohet identiteti.
Le të shqyrtojmë rregullin e dytë
Le të zgjerojmë anën e majtë të identitetit.
Duke përdorur ligjin shpërndarës të disjuksionit në lidhje me lidhëzën, marrim
Pas sjelljes së termave të ngjashëm, duke përdorur ngjitjen e thjeshtë, kemi
Ne morëm anën e duhur, prandaj rregulli është i provuar.
Procedura e përgjithshme për minimizimin e funksionit të specifikuar nga SDNF është si më poshtë.
Së pari, operacioni i ngjitjes zbatohet tek anëtarët e SDNF (çdo lidhje mund të përdoret shumë herë, duke u bashkuar me anëtarë të ndryshëm). Në këtë rast, një variabël përjashtohet prej tyre. Më pas futen pjesë të ngjashme dhe përsëri bëhet ngjitja. Ky proces vazhdon derisa shprehja që rezulton nuk përmban lidhëza që ndryshojnë nga njëra-tjetra në vlerat e një ndryshoreje. Shprehja që rezulton quhet formë e shkurtuar normale
. Çdo funksion logjik korrespondon vetëm me një formë të tillë. Operacioni i përgjithësuar i ngjitjes zbatohet në formën normale të reduktuar. Si rezultat, lidhëzat e panevojshme përjashtohen prej saj. Procesi vazhdon derisa ngjitja të mos jetë më e mundur. Forma që rezulton quhet
formë qorre funksioni logjik. Një funksion logjik mund të ketë disa forma pa rrugëdalje. Forma e bllokuar që rezulton aksidentalisht mund të rezultojë minimale. NË
rast i përgjithshëm
Për të gjetur formën minimale, është e nevojshme të numërohen format e bllokuara. Funksionet e paraqitura në SKNF trajtohen në mënyrë të ngjashme, duke marrë parasysh veçoritë e tyre. Ndonjëherë rezulton të jetë e përshtatshme në një fazë të ndërmjetme të shkosh në formën normale disjunctive dhe të vazhdosh minimizimin siç përshkruhet më sipër.
Shembulli 1:
Ngjitja e përgjithësuar këtu mund të kryhet duke përdorur disa opsione, të cilat japin rezultatet e mëposhtme:
.
Të përjashtuar 
,
,
:
(
),
(
),
(
).
Termat e përfshirë në ngjitjen e përgjithësuar tregohen në kllapa.
Të përjashtuar 
,
,
:
(
),
(
),
(
).
Siç mund ta shohim, këtu ka dy forma minimale normale. Ata janë të njëjtë në vështirësi.
Shembulli 2: Vazhdimi i zgjidhjes së problemit të krijimit të një pajisjeje në Fig. 3, ne do të kryejmë minimizimin e funksionit të shumicës (shih tabelën 12), për të cilin SDNF dhe SCNF janë marrë më sipër.
Këtu kemi marrë në konsideratë shumën e parë në çift me shumën e dytë, të tretë dhe të katërt dhe pasi i kemi ngjitur këto çifte kemi marrë rezultatin.
8.3. Metodat analitike minimizimi i funksioneve të ndërrimit
Metoda e Quine.
Metoda bazohet në krahasimin në çift dhe ngjitjen së bashku, nëse është e mundur, të gjithë përbërësve (anëtarë të SDNF). Për ta bërë këtë, çdo përbërës krahasohet me ato të mëvonshme, gjë që çon në marrjen e një implikuesi. Implikantët që rezultojnë krahasohen përsëri dhe, nëse është e mundur, ngjiten së bashku - etj. derisa implikantët e mbetur nuk mund të ngjiten më së bashku. Këta janë implikantë të thjeshtë;
Për renditje, këshillohet që përbërësit të ndahen në grupe sipas numrit të variablave jo të përmbysur. Në këtë rast, çdo përbërës i njëpasnjëshëm, duke filluar nga lart, krahasohet vetëm me përbërësit e grupit ngjitur me fundin, ku numri i variablave jo të përmbysur është një më shumë.
Le të ketë një funksion komutues të përcaktuar nga SDNF:
Le t'i ndajmë përbërësit në grupe sipas numrit të ndryshoreve jo të përmbysura.
Numri romak i numrit të grupit korrespondon me numrin e ndryshoreve jo të kundërta. Le të vizatojmë vija që tregojnë përbërësit që do të ngjiten së bashku. Rezultati i ngjitjes është gjithmonë një lidhje elementare, e cila është pjesë e përbashkët lidhëzat origjinale (në veçanti, përbërëse).
Implikantët që rezultojnë gjithashtu lejojnë ngjitjen, dhe rezultati është i njëjti implikant 
.
Ngjitja e mëtejshme është e pamundur, prandaj implikantët që rezultojnë janë të thjeshtë, dhe DNF e shkurtuar ka formën:
Faza e parë ka përfunduar. Në fazën e dytë, është e nevojshme të eliminohen implikantët kryesorë të panevojshëm. Kjo bëhet duke përdorur një tabelë të veçantë implikuese Quine (tabelë mbuluese). Rreshtat e tabelës janë shënuar me implikantë të thjeshtë të funksionit komutues, d.m.th. anëtarët e DNF-së së shkurtuar, dhe kolonat janë përbërës të njësisë, d.m.th. anëtarët e funksionit komutues SDNF.
Siç u përmend tashmë, një implikant i thjeshtë thith disa përbërës të një njësie nëse është pjesë e tij. Qeliza përkatëse e tabelës implikuese në kryqëzimin e rreshtit të një implikuesi të thjeshtë të dhënë dhe kolonave me përbërësit e njësisë shënohet, për shembull, me një shenjë "+". DNF-të minimale janë ndërtuar duke përdorur tabelën implikuese si më poshtë:
1) kërkohen kolonat e tabelës implikuese që kanë vetëm një kryq, implikantët e thjeshtë që u korrespondojnë këtyre kryqëzimeve quhen bazë dhe formojnë të ashtuquajturën bërthamë të funksionit komutues. Bërthama përfshihet domosdoshmërisht në DNF minimale;
2) konsiderohen opsione të ndryshme për zgjedhjen e një grupi implikantësh të thjeshtë që do të mbulojnë kolonat e mbetura të matricës implikuese me kryqe, dhe zgjidhen opsionet me numrin total minimal të shkronjave.
Thelbi i funksionit tonë (Tabela 35) janë implikantët 
dhe x 1 x 2 x 3, d.m.th. funksioni ka një bllokim unik dhe DNF minimale:
Tabela 35
Tabela implikuese e Quine
|
Përbërësit 1 (anëtarë të SDNF) |
|||||||
|
implikantët |
|
|
|
|
|
|
|
|
| |||||||
Mund të shihet se implikuesi x 2 x 3 x 4 është i tepërt, pasi mbulon përbërës tashmë të mbuluar nga implikantët 
, x 1 x 2 x 3 .
Numri i kryqeve në një rresht është një fuqi prej 2; Për më tepër, mund të siguroheni që është e barabartë me N=2 n - k, ku k është numri i shkronjave në një implikant të thjeshtë, n është numri i ndryshoreve nga të cilat varet funksioni.
Nëse SDNF nuk është specifikuar në fillim, atëherë duhet të merret duke përdorur, për shembull, metoda të njohura tashmë për ne.
Është e qartë se për tabelat e mëdha implikuese është e vështirë të identifikohen vizualisht opsionet me një numër minimal shkronjash. Prandaj, përdoret metoda e Petrik-ut, e cila bën të mundur marrjen e të gjitha DNF-ve pa rrugëdalje nga një tabelë implikuese duke ndërtuar të ashtuquajturën paraqitje konjuktive të saj. Për ta bërë këtë, të gjithë implikantët e thjeshtë shënohen me shkronja të ndryshme (A, B, C në tabelën 35), dhe më pas për secilën kolonë ndërtohet një ndarje e të gjitha shkronjave që tregojnë rreshtat e tabelës, kryqëzimi i të cilave me një kolonë të caktuar është shënuar me kryq. Paraqitja konjuktive e matricës implikuese është formuar si një lidhje e ndarjeve të ndërtuara për të gjitha kolonat. Të gjitha marrëdhëniet e algjebrës së Bulit të funksioneve komutuese mund të aplikohen në paraqitjen konjuktive të tabelës implikuese për ta thjeshtuar atë. Pas hapjes së kllapave dhe kryerjes së të gjitha përthithjeve të mundshme, marrim një ndarje lidhëzash, secila prej të cilave përmban të gjithë implikantët e DNF-së pa rrugëdalje.
Kjo do të thotë që një DNF pa rrugëdalje përmban dy implikantë kryesorë ( 
dhe në të njëjtën kohë C=x 1 x 2 x 3) dhe ka formën:
Metoda Quine-McCluskey.
Metoda është një zyrtarizim i metodës së Quine, i orientuar drejt përdorimit të kompjuterëve. Formalizimi konsiston në regjistrimin e përbërësve të njësisë (anëtarët e SDNF) me numrat e tyre binar. Të gjithë numrat ndahen në grupe të shkëputura sipas numrit të njësheve në numrin binar. Lidhjet bëhen vetëm midis grupeve ngjitur. Kategoria që do të eliminohet tregohet me shenjën “–” (“dash”). Grupe të mëtejshme nga implikantët që rezultojnë formohen duke marrë parasysh vendndodhjen identike të vizës. Ky emërtim i implikantëve quhet kode të përgjithësuara. Le të jepet një funksion logjik
111101001000110.
Le t'i grupojmë këta përbërës të një njësie sipas numrit të njësive:
Asnjë ngjitje e mëtejshme nuk është e mundur. DNF-të minimale gjenden më pas duke përdorur tabelën implikuese (Tabela 36):
Kjo do të thotë që DNF-të e bllokuara përmbajnë tre implikantë kryesorë dhe kanë formën:
(dy përmbysje);
(tre përmbysje).
Tabela 36
Tabela implikuese Quine-McCluskey
|
implikantët |
Përbërësit e njësive |
|||||||
Vini re se ngjitja e dy implikantëve me një vizë është e mundur vetëm nëse ato janë të pozicionuara siç duhet, për shembull:
|
|
|
|
|
Ju mund të zgjidhni cilindo nga TDNF-të e marra dhe, duke marrë parasysh numrin më të vogël të përmbysjeve, të parën.
Metoda Blake-Poretsky.
Metoda lejon që dikush të marrë një DNF të reduktuar të një funksioni Boolean nga DNF e tij arbitrare, dhe jo nga SDNF, si në metodat Quine dhe Quine-McCluskey, duke përdorur ligjin e ngjitjes së përgjithësuar. Metoda bazohet në deklaratën e mëposhtme: nëse në një DNF arbitrare të një funksioni Boolean kryhen të gjitha operacionet e mundshme të kundërta me ngjitjen e përgjithësuar dhe më pas kryhen të gjitha thithjet, atëherë rezultati është një DNF e reduktuar e funksionit.
Le të jepet funksioni DNF:
Mund të shihet se ligji i ngjitjes së përgjithësuar në lidhje me ndryshoren x 1 mund të zbatohet në lidhjet e para dhe të dyta; marrim:
Në mënyrë të ngjashme për lidhëzat e para dhe të treta:
ato. gjithçka mbetet ashtu siç është!
Lidhjet e dyta dhe të treta pranojnë ngjitjen e përgjithësuar përgjatë x2:
Le të kalojmë te DNF:
Pas zbatimit të ligjit të idempotencës (përsëritjes) dhe përthithjes marrim:
Përpjekjet për të përdorur më tej lidhjen dhe thithjen e përgjithësuar nuk japin rezultate. Rrjedhimisht, merret një funksion i reduktuar DNF.
Tabela 37
Tabela implikante për të ilustruar metodën Blake-Poretsky
|
implikantët |
Kompletet e veçorive dhe kuptimet e saj |
|||||||||
Kështu, grupet e punës (njësisë) mund të mbulohen nga tre implikantë kryesorë, p.sh. 
,
,
. Bërthama përfshin implikantët 
,
. Atëherë DNF-të e bllokuara kanë formën:
(më mirë për sa i përket numrit të përmbysjeve).
për të parën – X 3 X 4;
për të dytën – X 1 X 3;
për të tretën – X 2 X 3;
për të katërtin – X 1 X 2 X 4;
për të pestën – X 1 X 2 X 4;
Një DNF minimale do të duket kështu:
Duke krahasuar metodën e hartës Karnaugh me metodat e tjera të minimizimit të funksioneve, mund të konkludojmë se e para është më e përshtatshme për ekzekutim manual. Koha i bërë vetëështë reduktuar ndjeshëm (për shkak të paraqitje vizuale implikantë ngjitës). Zbatimi i softuerit të kësaj metode ka vështirësitë e veta. Po, do të jetë shumë e vështirë për t'u zbatuar zgjedhje optimale drejtkëndësha të rregullt, veçanërisht për një numër të madh argumentesh.
1.3.5 Metoda e koeficientëve të pasigurt
Kjo metodë mund të përdoret për çdo numër argumentesh. Por meqenëse kjo metodë është mjaft e rëndë, ajo përdoret vetëm në rastet kur numri i argumenteve nuk është më shumë se 5-6.
Metoda e koeficientëve të pacaktuar përdor ligjet e bashkësive universale dhe nule dhe ligjet e përsëritjes. Në fillim, të gjithë koeficientët janë të pasigurt (prandaj edhe emri i metodës).
Le të ndërtojmë një matricë koeficientësh të pasigurt për katër argumente. Në këtë rast, do të kemi një sistem prej 16 ekuacionesh.
Sistemi shfaqet në faqen tjetër.
Le të barazojmë të gjithë koeficientët me 0 në ato rreshta që korrespondojnë me 0 në kolonën vektoriale. Pastaj barazojmë koeficientët përkatës në rreshtat e tjerë me 0. Pas këtyre transformimeve, sistemi do të marrë formën e mëposhtme:
V = 1 VVVVVVV = 1 VVV V VV = 1 V = 1 VVV = 1 VVVVVVV = 1 VVV = 1 VVVVVV = 1 VVV = 1Tani në çdo rresht duhet të zgjidhni koeficientin minimal të renditjes dhe ta vendosni atë të barabartë me një, dhe koeficientët e mbetur me 0. Pas kësaj, kaloni linja identike, duke lënë njërën prej tyre (ato rreshta me të gjithë koeficientët e barabartë me 0 janë gjithashtu të kryqëzuara jashtë).
= 1 = 1 = 1 = 1 = 1Le të shkruajmë tani lidhëzat që korrespondojnë me koeficientët, e barabartë me njësitë. Ne do të marrim minimumin 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 .
Pra, ne kemi marrë DNF minimale në disa mënyra në të gjitha rastet doli të jetë e njëjtë, domethënë, ndonjë nga metodat e përshkruara mund të përdoret për të minimizuar funksionin. Sidoqoftë, këto metoda ndryshojnë ndjeshëm nga njëra-tjetra si në parimin e gjetjes së MDNF-së ashtu edhe në kohën e ekzekutimit. Metoda e hartës Karnaugh është shumë e përshtatshme për llogaritjet manuale. Është vizual, nuk kërkon operacione rutinë dhe zgjedhja e vendndodhjes optimale të drejtkëndëshave të duhur nuk është e vështirë. Ndërsa zbatimi i kësaj metode me makinë është i ndërlikuar nga nevoja për të gjetur rregullimin optimal të drejtkëndëshave. Natyrisht, përdorimi i metodave të tjera (metoda Quine, metoda Quine-McCluskey, metoda e koeficientëve të pacaktuar) për llogaritjet manuale është i papërshtatshëm. Ato janë më të përshtatshme për zbatimin e makinës, pasi përmbajnë një numër të madh operacionesh të thjeshta të përsëritura.
Detyra 2.
2.1 Diagrami i algoritmit për metodën e Quine
1. Fillimi.
2. Futni matricën DSNF funksion origjinal.
3. Kontrolloni vijat i-të (i=1,m-1: ku m është numri i vijave në DSNF) dhe j-të (j=i+1, m) për ngjitje. Nëse linjat ngjiten së bashku, atëherë shkoni në hapin 6, in ndryshe shkoni në pikën 5.
4. Formoni një grup implikantësh të thjeshtë, pasi të keni shënuar më parë me simbolin ‘*’ variablin me të cilin këto vargje janë ngjitur së bashku.
5. Shkoni në hapin 2.
6. Shkruani një rresht që nuk është i bashkuar me asnjë rresht tjetër në grupin përfundimtar.
7. Shkoni në hapin 2.
8. Prodhimi i matricës që rezulton.
Diagrami logjik i algoritmit në shënimin Lyapunov
V H V 1 Z 1 V 2 ¯ V 3 V 4 V K
V H – fillimi.
V 1 – futni matricën DSNF të funksionit origjinal.
V 2 - formoni një grup implikantësh të thjeshtë, pasi të keni shënuar më parë me simbolin '*' variablin me të cilin janë ngjitur këto vargje.
V 3 - një varg që nuk është i bashkuar me asnjë varg tjetër shkruhet në grupin përfundimtar.
V 4 – prodhimi i matricës që rezulton.
Z 1 - nëse linjat janë ngjitur së bashku, atëherë shkoni në hapin 3, përndryshe shkoni në hapin 5.
V K – fund.
Diagrami grafik i algoritmit.
 |
Përshkrimi makinë procedurat
Procedura e mbërthyer (S1, S2: Diz; IndexS1, IndexS2: byte);
Kjo procedurë bashkon së bashku dy ndarjet që i kalojnë asaj. Klauzolat janë të specifikuara në parametrat S1, S2. Indekset IndexS1, IndexS2 përcaktojnë indekset e këtyre klauzolave në grupin kryesor të punës. Algoritmi i procedurës është si më poshtë: së pari, kërkohet numri i karaktereve që janë ngjitur së bashku. Nëse ka 0 prej tyre, atëherë ato janë të njëjta dhe vetëm njëri prej tyre shkruhet në grupin përfundimtar. Nëse 1, atëherë përcaktohet vendndodhja e simbolit me anë të së cilës këto dy ndarje janë ngjitur së bashku, dhe ne e zëvendësojmë këtë simbol me "*". Të gjitha rezultatet e fituara futen në grupin REZ.
Të gjitha funksionet dhe procedurat e tjera të programit janë të lidhura me veprimet në vargje, domethënë ato nuk janë të lidhura drejtpërdrejt me këtë metodë gjetja e MDNF. Prandaj nuk ka kuptim t'i përshkruajmë ato.
2.2 Diagrami i algoritmit për metodën e Petrikut
1. Fillimi.
2. Futni matricën DSNF të funksionit origjinal dhe implikantëve të thjeshtë të marrë në metodën e Quine.
3. Krijoni një tabelë etiketash.
4. Duke përdorur tabelën e etiketave, ndërtoni një lidhje ndarjesh, secila prej të cilave është një grup i atyre implikantëve që kanë etiketa në një kolonë të caktuar.
Artikulli i mëparshëm: Sa është shpejtësia e dritës Artikulli vijues: Lëkundjet harmonike Formula e fizikës së frekuencës së lëkundjeve