Halimbawa. Maghanap ng mga formula ng CNF

~ ~

Ang perpektong disjunctive normal na anyo ng SDNF ay maaaring itayo gamit ang sumusunod na algorithm:

1. = 1. DNF algorithm

2. = 2. DNF algorithm

3. = 3. DNF algorithm

4. = 4. DNF algorithm

5. Alisin ang magkaparehong maling termino, ibig sabihin, mga tuntunin ng form

6. Kumpletuhin ang mga natitirang termino gamit ang mga nawawalang variable

7. Ulitin ang punto 4.

Halimbawa. Maghanap ng mga formula ng SDNF.

~

Upang bumuo ng SCNF, maaari mong gamitin ang sumusunod na scheme:

Halimbawa. Maghanap ng mga formula ng SDNF.

~

Ito ay kilala (Theorems 2.11, 2.12) na ang SDNF at SCNF ay katangi-tanging tinukoy ng formula at, samakatuwid, maaari silang mabuo gamit ang talahanayan ng katotohanan ng formula.

Ang pamamaraan para sa pagbuo ng SDNF at SCNF ayon sa talahanayan ng katotohanan ay ibinigay sa ibaba, para sa formula ~ :

			~
			1 0 1 0 1 1 0 1	SDNF; SKNF.

2.2. Mag-ehersisyo.

2.2.1 Nasa ibaba ang mga Boolean na expression. Pasimplehin ang mga expression ng iyong variant hangga't maaari gamit ang mga batas ng lohika ng Boole. Pagkatapos ay gumamit ng mga talahanayan ng katotohanan upang ihambing ang iyong pinasimple na expression sa orihinal.

2.2.2. Linawin ang tanong ng equivalence ng f 1 at f 2 sa pamamagitan ng pagbabawas ng mga ito sa SDNF (Talahanayan 1).

2.2.3. Hanapin ang dual function para sa f 3 gamit ang pangkalahatan at Boolean na prinsipyo (Talahanayan 1). Ihambing ang mga resulta.

№	f 1	f 2	f 3

2.3. Kontrolin ang mga tanong.

2.3.1. Tukuyin ang isang pahayag.

2.3.2. Ilista ang mga pangunahing operasyon sa isang pahayag.

2.3.3. Ano ang talahanayan ng katotohanan?

2.3.4. Lumikha ng mga talahanayan ng katotohanan para sa mga sumusunod na formula:

~ ~ ~ ;

2.3.5. Isinasaalang-alang ang mga kombensyon sa pagkakasunud-sunod ng mga operasyon, alisin ang "dagdag" na mga panaklong at ang "" na tanda sa mga formula:

;

2.3.6. Gamit ang mga katumbas na pagbabago, patunayan ang magkatulad na katotohanan ng mga formula:

2.3.7. Maghanap ng dalawahang formula:

)

2.3.8. Bawasan ang mga sumusunod na formula sa perpektong DNF (SDNF) form:

~

2.3.9. Bawasan ang mga sumusunod na formula sa perpektong CNF (SCNF) form:

~

Laboratory work No. 3

Paksa:“Pagbabawas ng mga function ng Boolean. lohika"

Target: Pagkuha ng mga praktikal na kasanayan sa pagtatrabaho sa mga pamamaraan para sa pagliit ng mga function ng Boolean.

3.1. Teoretikal na impormasyon.

Minimal na mga anyo

Tulad ng ipinakita sa, anumang Boolean function ay maaaring katawanin sa perpektong normal na anyo (disjunctive o conjunctive). Bukod dito, ang gayong representasyon ay ang unang hakbang sa paglipat mula sa isang tabular na detalye ng isang function patungo sa analytical expression nito. Sa mga sumusunod, magpapatuloy tayo mula sa disjunctive form, at ang mga kaukulang resulta para sa conjunctive form ay nakuha batay sa prinsipyo ng duality.

Ang canonical na problema ng synthesizing logical circuits sa isang Boolean na batayan ay bumababa sa pagliit ng mga function ng Boolean, i.e. upang kumatawan sa kanila sa disjunctive normal na anyo, na naglalaman ng pinakamaliit na bilang ng mga titik (mga variable at ang kanilang mga negasyon). Ang ganitong mga anyo ay tinatawag na minimal. Sa canonical synthesis, ipinapalagay na ang parehong mga signal at ang kanilang mga inversion ay ibinibigay sa mga input ng circuit.

Ang formula na ipinakita sa disjunctive normal form ay pinasimple sa pamamagitan ng paulit-ulit na paggamit ng gluing operation at ang absorption operation at (ang dalawahang pagkakakilanlan para sa conjunctive normal na anyo ay may anyo: at ). Dito, at maaaring maunawaan bilang anumang Boolean algebra formula. Bilang resulta, nakarating tayo sa isang analytical expression kung saan hindi na posible ang mga karagdagang pagbabago, i.e. nakakakuha tayo ng dead-end na form.

Kabilang sa mga dead-end na anyo ay mayroon ding minimal na disjunctive form, at maaaring hindi ito kakaiba. Upang matiyak na ang isang ibinigay na dead-end na form ay minimal, kailangan mong hanapin ang lahat ng dead-end na form at ihambing ang mga ito ayon sa bilang ng mga titik na nilalaman ng mga ito.

Hayaan, halimbawa, ang function ay ibigay sa perpektong normal na disjunctive form:

Pagpapangkat ng mga tuntunin at paglalapat ng gluing operation, mayroon kaming .

Sa isa pang paraan ng pagpapangkat nakukuha namin:

Ang parehong dead-end na mga form ay hindi minimal. Upang makuha ang minimal na anyo, kailangan mong hulaan upang ulitin ang isang termino sa orihinal na formula (maaari itong palaging gawin, dahil ). Sa unang kaso, ang naturang miyembro ay maaaring . Tapos . Sa pamamagitan ng pagdaragdag ng termino , makakakuha tayo ng: . Ang pagkakaroon ng napagdaanan ang lahat ng posibleng mga opsyon, maaari mong tiyakin na ang huling dalawang form ay minimal.

Ang pagtatrabaho sa mga formula sa antas na ito ay parang pagala-gala sa dilim. Ang proseso ng paghahanap ng kaunting mga form ay nagiging mas nakikita at may layunin kung gagamit ka ng ilang graphic at analytical na representasyon at mga simbolo na espesyal na binuo para sa layuning ito.

Multidimensional na kubo

Ang bawat vertex ng isang -dimensional cube ay maaaring iugnay sa isang constituent ng isang unit. Dahil dito, ang subset ng may markang vertices ay isang pagmamapa sa -dimensional na kubo ng isang Boolean na function ng mga variable sa perpektong disjunctive normal na anyo. Sa Fig. Ang 3.1 ay nagpapakita ng gayong pagmamapa para sa function mula sa sugnay 3.7.

Fig. 3.1 Pagpapakita ng isang function na ipinakita sa SDNF sa isang three-dimensional na kubo

Upang ipakita ang isang function ng mga variable na ipinakita sa anumang disjunctive normal na anyo, ito ay kinakailangan upang magtatag ng isang sulat sa pagitan ng mga miniterms nito at ang mga elemento ng -dimensional cube.

Ang isang miniterm na (-1) na ranggo ay maaaring ituring bilang resulta ng pagsasama-sama ng dalawang miniterms ng ranggo (constituent ng pagkakaisa), i.e. , Sa isang -dimensional na kubo, ito ay tumutugma sa pagpapalit ng dalawang vertice na naiiba lamang sa mga halaga ng coordinate na nagkokonekta sa mga vertex na ito sa isang gilid (ang gilid ay sinasabing sumasakop sa mga vertices na insidente dito). Kaya, ang (-1) na mga miniterm na order ay tumutugma sa mga gilid ng -dimensional na kubo. Katulad nito, ang mga pagsusulatan ng mga miniterm ng (-2) na pagkakasunud-sunod ay itinatag na may mga mukha ng isang -dimensional na kubo, na ang bawat isa ay sumasaklaw sa apat na vertices (at apat na gilid).

Ang mga elemento ng isang -dimensional cube na nailalarawan sa pamamagitan ng mga sukat ay tinatawag na -cube. Kaya, ang mga vertices ay 0-cube, ang mga gilid ay 1-cube, ang mga mukha ay 2-cube, atbp. Sa pangkalahatan sa pangangatwiran sa itaas, maaari nating ipagpalagay na ang isang miniterm na () ika-ranggo sa disjunctive normal na anyo para sa isang function ng mga variable ay kinakatawan ng isang -cube, at ang bawat -cube ay sumasaklaw sa lahat ng mga -cube ng mas mababang dimensyon na nauugnay sa mga vertices nito. . Bilang isang halimbawa sa Fig. Ang 3.2 ay nagpapakita ng isang function ng tatlong variable. Dito ang mga miniterm ay tumutugma sa 1-cube (), at ang miniterm ay kinakatawan ng isang 2-cube ().

Fig.3.2 Saklaw ng function

Kaya, ang anumang disjunctive normal na anyo ay nakamapa sa isang -dimensional na cube ng isang set ng -cube na sumasaklaw sa lahat ng vertices na tumutugma sa mga constituent ng pagkakaisa (0-cubes). Ang kabaligtaran na pahayag ay totoo rin: kung ang isang tiyak na hanay ng mga -cube ay sumasaklaw sa hanay ng lahat ng mga vertices na tumutugma sa mga halaga ng yunit ng isang function, kung gayon ang disjunction ng mga miniterm na tumutugma sa mga -cube ay isang pagpapahayag ng function na ito sa disjunctive normal anyo. Ang nasabing koleksyon ng mga -cube (o ang kanilang mga kaukulang miniterms) ay sinasabing bumubuo ng isang takip ng isang function.

Ang pagnanais para sa isang minimal na anyo ay intuitively nauunawaan bilang isang paghahanap para sa naturang takip, ang bilang ng mga cube na kung saan ay magiging mas maliit, at ang kanilang dimensyon ay magiging mas malaki. Ang saklaw na naaayon sa pinakamababang anyo ay tinatawag na pinakamababang saklaw. Halimbawa, para sa covering function sa Fig. 3.3 ay nakakatugon sa mga minimum na form At .

kanin. 3.3 Mga saklaw ng function.

umalis – ; sa kanan –

Ang pagpapakita ng isang function sa isang -dimensional cube ay malinaw at simple kapag . Ang isang four-dimensional na kubo ay maaaring ilarawan tulad ng ipinapakita sa Fig. 3.4, na nagpapakita ng function ng apat na variable at ang pinakamababang saklaw nito na naaayon sa expression . Ang paggamit ng pamamaraang ito ay nangangailangan ng gayong kumplikadong mga konstruksyon na ang lahat ng mga pakinabang nito ay nawala.

kanin. 3.4 Pagpapakita ng function sa isang four-dimensional na kubo

Mga mapa ng Carnot

Isa pang paraan para sa graphic na pagpapakita ng mga gamit ng Boolean Mga mapa ng Carnot, na mga espesyal na inayos na mga talahanayan ng sulat. Ang mga haligi at hilera ng talahanayan ay tumutugma sa lahat ng posibleng hanay ng mga halaga na hindi hihigit sa dalawang variable, at ang mga hanay na ito ay nakaayos sa isang pagkakasunud-sunod na ang bawat kasunod na isa ay naiiba mula sa nauna sa halaga ng isa lamang sa mga variable. . Salamat sa ito, ang mga kalapit na mga cell ng talahanayan nang pahalang at patayo ay naiiba sa halaga ng isang variable lamang. Ang mga cell na matatagpuan sa mga gilid ng talahanayan ay isinasaalang-alang din na katabi at may ganitong katangian. Sa Fig. Ipinapakita ng Figure 3.5 ang mga mapa ng Karnaugh para sa dalawa, tatlo, apat na variable.

kanin. 3.5 Mga mapa ng Carnaugh para sa dalawa, tatlo at apat na variable

Tulad ng sa mga ordinaryong talahanayan ng katotohanan, ang mga cell ng mga hanay kung saan ang function ay kumukuha ng halaga 1 ay puno ng mga (karaniwang hindi magkasya ang mga zero, tumutugma sila sa mga walang laman na cell). Halimbawa, sa Fig. 3.6, A ay nagpapakita ng isang Karnaugh na mapa para sa isang function, ang pagpapakita kung saan sa isang four-dimensional cube ay ibinibigay sa Fig. 3.4. Upang pasimplehin ang mga bagay, ang mga row at column na tumutugma sa mga value ng 1 para sa isang variable ay naka-highlight na may curly brace na nagsasaad ng variable na iyon.

kanin. 3.6 Pagpapakita ng function ng apat na variable sa isang mapa ng Carnaugh

(a) at ang pinakamababang saklaw nito (b)

Sa pagitan ng mga function mappings sa n-dimensional cube at ang Carnot map ay mayroong one-to-one na sulat. Sa mapa ng Carnot s-ang isang cube ay tumutugma sa isang set ng 2 kalapit na mga cell na inilagay sa isang row, column, square o rectangle (isinasaalang-alang ang kalapitan ng magkabilang gilid ng mapa). Samakatuwid, ang lahat ng mga probisyon na itinakda sa itaas (tingnan ang talata. multidimensional na kubo), ay may bisa para sa mga mapa ng Karnaugh. Kaya, sa Fig. 3.6, b nagpapakita ng saklaw ng mga yunit ng mapa na tumutugma sa minimal na disjunctive form ang function na pinag-uusapan.

Ang pagbabasa ng mga miniterms mula sa isang mapa ng Karnaugh ay sumusunod sa isang simpleng panuntunan. Nabubuo ang mga cell s-cube, bigyan ng miniter (n–s)-ika ranggo, na kinabibilangan ng mga (n–s) mga variable na nagpapanatili ng parehong mga halaga dito s-cube, kung saan ang value 1 ay tumutugma sa mga variable mismo, at ang value 0 ay tumutugma sa kanilang mga negasyon. Mga variable na hindi nagpapanatili ng kanilang mga halaga para sa s-cube, ay wala sa miniterm. Ang iba't ibang paraan ng pagbasa ay nagreresulta sa iba't ibang representasyon ng function sa disjunctive normal form (ang nasa dulong kanan ay minimal) (Figure 3.7).

Ang paggamit ng mga mapa ng Karnaugh ay nangangailangan ng mas simpleng mga konstruksyon kumpara sa pagmamapa sa n-dimensional na kubo, lalo na sa kaso ng apat na variable. Upang ipakita ang mga function ng limang variable, dalawang Karnaugh na mapa para sa apat na variable ang ginagamit, at para sa isang function ng anim na variable, apat na ganoong mga mapa ang ginagamit. Sa karagdagang pagtaas sa bilang ng mga variable, ang mga mapa ng Karnaugh ay halos hindi na magagamit.

Sikat sa panitikan Veitch card Naiiba lamang sila sa magkakaibang pagkakasunud-sunod ng mga hanay ng mga variable na halaga at may parehong mga katangian tulad ng mga mapa ng Karnaugh.

Kumplikado ng mga cube

Ang hindi pagkakapare-pareho ng mga graphical na pamamaraan na may malaking bilang ng mga variable ay binabayaran ng iba't ibang mga analytical na pamamaraan para sa kumakatawan sa mga function ng Boolean. Ang isa sa gayong representasyon ay complex ng mga cube, gamit ang terminolohiya ng isang multidimensional na lohikal na espasyo kasama ng espesyal na binuo na simbolismo.

). Ang 0-cube na naaayon sa mga nasasakupan ng pagkakaisa ay kinakatawan ng mga hanay ng mga variable na halaga kung saan ang function ay katumbas ng pagkakaisa. Obvious naman sa recording

kanin. 3.8 Kumplikadong mga cube ng isang function ng tatlong variable ( A) at ang simbolikong representasyon nito ( b)

Nabubuo ang complex ng mga cube maximum na saklaw ng pag-andar. Hindi kasama ang lahat ng iyon s-mga cube na natatakpan ng mga cube na may mas mataas na dimensyon, nakakakuha kami ng mga pantakip na tumutugma sa mga dead-end na form. Kaya, para sa halimbawang isinasaalang-alang (Larawan 3.8) mayroon kaming dead-end na takip

,

na tumutugma sa function . Sa kasong ito, ang saklaw na ito ay minimal.

Para sa dalawang Boolean function, ang disjunction operation ay tumutugma sa unyon ng kanilang cube complexes, at ang conjunction operation ay tumutugma sa intersection ng kanilang cube complexes. Ang negation ng isang function ay tumutugma sa complement ng isang complex ng mga cube, ibig sabihin, at tinutukoy ng lahat ng vertices kung saan ang function ay tumatagal ng value na 0. Kaya, mayroong one-to-one correspondence (isomorphism) sa pagitan ng algebra ng Boolean function at Boolean set na kumakatawan sa mga complex ng mga cube.

Ang kumakatawan sa isang function sa anyo ng mga complex ng mga cube ay hindi gaanong nakikita, ngunit ang pinakamahalagang bentahe nito ay ang mga paghihigpit sa bilang ng mga variable ay tinanggal at ang pag-encode ng impormasyon ay pinadali kapag gumagamit ng mga computer.

Pag-minimize ng Boolean Function

Pagbubuo ng problema. Ang pag-minimize ng isang circuit sa isang Boolean na batayan ay bumababa sa paghahanap ng minimum na disjunctive form na tumutugma sa minimum na saklaw. Ang kabuuang bilang ng mga titik na kasama sa normal na anyo ay ipinahayag ng halaga ng pagsakop , kung saan ang bilang ng mga cube na bumubuo sa takip ng isang naibigay na function ng n variable. Ang pinakamababang saklaw ay nailalarawan sa pinakamababang halaga ng presyo nito.

Karaniwan, ang problema sa pag-minimize ay nalulutas sa dalawang hakbang. Una, naghahanap kami ng pinababang takip na kinabibilangan ng lahat ng -cube ng maximum na dimensyon, ngunit hindi naglalaman ng isang cube na sakop ng anumang cube ng takip na ito. Ang kaukulang disjunctive normal form ay tinatawag na reduced, at ang mga miniterms nito ay tinatawag na simple impliants. Para sa isang partikular na function, ang pinababang saklaw ay natatangi, ngunit maaaring ito ay kalabisan dahil sa katotohanan na ang ilan sa mga cube ay sakop ng mga koleksyon ng iba pang mga cube.

Sa ikalawang hakbang, ang isang paglipat ay ginawa mula sa pinababa sa dead-end na disjunctive normal na mga form, kung saan ang mga minimal na form ay pinili. Ang mga dead-end na form ay nabuo sa pamamagitan ng pagbubukod mula sa pinababang sumasaklaw sa lahat ng mga redundant na cube, kung wala ang natitirang hanay ng mga cube ay bumubuo pa rin ng isang takip ng isang partikular na function, ngunit sa karagdagang pagbubukod ng alinman sa mga cube, hindi na nito saklaw ang hanay ng lahat. vertices na tumutugma sa mga solong halaga ng function, ibig sabihin, ito ay tumigil na maging isang takip .

Ang isang pinababang coverage cube na sumasaklaw sa mga vertex ng isang partikular na function na hindi sakop ng anumang iba pang mga cube ay hindi maaaring maging kalabisan at palaging isasama sa pinakamababang saklaw. Ang naturang cube, tulad ng katumbas nitong implicant, ay tinatawag na extremal (mahahalagang implicant), at ang mga vertices na sakop nito ay tinatawag na cancelled vertices. Ang hanay ng mga extremals ay bumubuo sa core ng takip; ito ay malinaw na kapag lumipat mula sa isang pinababang takip sa isang minimal na isa, una sa lahat, ang lahat ng extremals ay dapat na ihiwalay. Kung ang hanay ng mga extremals ay hindi bumubuo ng isang takip, pagkatapos ito ay pupunan upang takpan ng mga cube mula sa pinababang takip.

Ang ibinigay na mga kahulugan ay inilalarawan sa Fig. 3.9, kung saan ang pinababang saklaw (tingnan ang Fig. 3.9a, ) at ang pinakamababang saklaw (Larawan 3.9b) at (tingnan ang Larawan 3.9, b) ay ipinahayag bilang mga sumusunod.

Kahulugan 1.Conjunctive monomial (elementaryong conjunction) of variables ay ang conjunction ng mga variable na ito o ang kanilang mga negasyon.

Halimbawa, ay isang pang-elementarya na pang-ugnay.

Kahulugan 2.Disjunctive monomial (elementarya disjunction) mula sa mga variable ay ang disjunction ng mga variable na ito o ang kanilang mga negations.

Halimbawa, ay isang elementarya na disjunction.

Kahulugan 3. Ang isang formula na katumbas ng isang ibinigay na propositional algebra formula at isang disjunction ng elementary conjunctive monomials ay tinatawag disjunctive normal na anyo(DNF) ng formula na ito.

Halimbawa,– DNF.

Kahulugan 4. Ang isang formula na katumbas ng isang ibinigay na propositional algebra formula at isang conjunction ng elementarya disjunctive monomials ay tinatawag conjunctive normal na anyo(CNF) ng formula na ito.

Halimbawa, – KNF.

Para sa bawat propositional algebra formula maaari kang makahanap ng isang set ng disjunctive at conjunctive normal forms.

Algorithm para sa pagbuo ng mga normal na form

Gamit ang mga katumbas ng logical algebra, palitan ang lahat ng mga pangunahing operasyon sa formula: conjunction, disjunction, negation:

Alisin ang dobleng negatibo.

Ilapat, kung kinakailangan, ang mga katangian ng distributivity at absorption formula sa mga operasyon ng conjunction at disjunction.

2.6. Perpektong disjunctive at perpektong conjunctive na normal na anyo

Anumang Boolean function ay maaaring magkaroon ng maraming representasyon sa anyo ng DNF at CNF. Ang isang espesyal na lugar sa mga representasyong ito ay inookupahan ng perpektong DNF (SDNF) at perpektong CNF (SCNF).

Kahulugan 1. Perpektong disjunctive normal na anyo(SDNF) ay isang DNF kung saan ang bawat conjunctive monomial ay naglalaman ng bawat variable mula sa set nang eksaktong isang beses, alinman mismo o ang negation nito.

Sa istruktura, ang SDNF para sa bawat propositional algebra formula na binawasan sa isang DNF ay maaaring tukuyin bilang mga sumusunod:

Kahulugan 2. Perpektong disjunctive normal na anyo(SDNF) ng isang propositional algebra formula ay tinatawag na DNF nito, na may mga sumusunod na katangian:

Kahulugan 3. Perpektong conjunctive normal na anyo(SCNF) ay isang CNF kung saan ang bawat disjunctive monomial ay naglalaman ng bawat variable mula sa set nang eksaktong isang beses, at alinman mismo o ang negasyon nito ay lilitaw.

Sa istruktura, ang SCNF para sa bawat propositional algebra formula na binawasan sa CNF ay maaaring tukuyin bilang mga sumusunod.

Kahulugan 4. Perpektong conjunctive normal na anyo(SCNF) ng isang ibinigay na propositional algebra formula ay tinatawag na CNF na nakakatugon sa mga sumusunod na katangian.

Teorama 1. Ang bawat Boolean function ng mga variable na hindi magkaparehong mali ay maaaring katawanin sa SDNF, at sa isang natatanging paraan.

Mga pamamaraan para sa paghahanap ng SDNF

1st method

ika-2 paraan

piliin ang mga linya kung saan kinukuha ng formula ang halaga 1;

bumubuo tayo ng disjunction ng mga conjunction sa ilalim ng kundisyon na kung ang isang variable ay kasama sa conjunction na may value na 1, pagkatapos ay isusulat namin ang variable na ito; kung may value na 0, pagkatapos ay ang negation nito. Nakukuha namin ang SDNF.

Teorama 2. Ang bawat Boolean function ng mga variable na hindi magkatulad na totoo ay maaaring katawanin sa SCNF, at sa isang natatanging paraan.

Mga pamamaraan para sa paghahanap ng SCNF

1st method– gamit ang mga katumbas na pagbabago:

ika-2 paraan– gamit ang mga talahanayan ng katotohanan:

piliin ang mga linya kung saan kinukuha ng formula ang halagang 0;

bumubuo kami ng isang kumbinasyon ng mga disjunction sa ilalim ng kondisyon na kung ang isang variable ay kasama sa disjunction na may halaga na 0, pagkatapos ay isulat namin ang variable na ito; kung may isang halaga ng 1, pagkatapos ay ang negasyon nito. Nakukuha namin ang SKNF.

Halimbawa 1. Bumuo ng mga function ng CNF.

Solusyon

Tanggalin natin ang nag-uugnay na "" gamit ang mga batas ng pagbabago ng mga variable:

= /de Morgan's laws and double negation/ =

/mga batas sa pamamahagi/ =

Halimbawa 2. Ibigay ang formula sa DNF.

Solusyon

Ipahayag natin ang mga lohikal na operasyon gamit ang at:

= /uriin natin ang negasyon bilang mga variable at bawasan ang dobleng negatibo/ =

= /batas ng pamamahagi/ .

Halimbawa 3. Isulat ang formula sa DNF at SDNF.

Solusyon

Gamit ang mga batas ng lohika, binabawasan namin ang pormula na ito sa isang anyo na naglalaman lamang ng mga disjunction ng elementarya na pang-ugnay. Ang resultang formula ay ang nais na DNF:

Upang bumuo ng SDNF, gumawa tayo ng talahanayan ng katotohanan para sa formula na ito:

Minarkahan namin ang mga row ng table kung saan ang formula (huling column) ay kumukuha ng value 1. Para sa bawat ganoong row, nagsusulat kami ng formula na totoo sa set ng mga variable ng row na ito:

linya 1: ;

linya 3: ;

linya 5: .

Ang disjunction ng tatlong formula na ito ay kukuha ng halaga 1 lamang sa mga hanay ng mga variable sa mga linya 1, 3, 5, at samakatuwid ay ang nais na perpektong disjunctive normal na anyo (PDNF):

Halimbawa 4. Dalhin ang formula sa SKNF sa dalawang paraan:

a) gamit ang mga katumbas na pagbabago;

b) gamit ang talahanayan ng katotohanan.

Solusyon:

Ibahin natin ang pangalawang elementarya na disjunction:

Ang formula ay mukhang:

b) gumuhit ng talahanayan ng katotohanan para sa formula na ito:

Minarkahan namin ang mga row ng table kung saan ang formula (huling column) ay kumukuha ng value na 0. Para sa bawat ganoong row, nagsusulat kami ng formula na totoo sa set ng mga variable ng row na ito:

linya 2: ;

linya 6: .

Ang pagsasama ng dalawang formula na ito ay kukuha ng halaga na 0 lamang sa mga hanay ng mga variable sa mga linya 2 at 6, at samakatuwid ay ang nais na perpektong conjunctive normal form (PCNF):

Mga tanong at gawain para sa independiyenteng solusyon

1. Gamit ang mga katumbas na pagbabago, bawasan ang mga formula sa DNF:

2. Gamit ang mga katumbas na pagbabago, dalhin ang mga formula sa CNF:

3. Gamit ang pangalawang distributive law, i-convert ang DNF sa CNF:

A) ;

4. I-convert ang mga ibinigay na DNF sa SDNFs:

5. I-convert ang ibinigay na CNF sa SCNF:

6. Para sa mga ibinigay na lohikal na formula, bumuo ng SDNF at SCNF sa dalawang paraan: gamit ang mga katumbas na pagbabago at paggamit ng talahanayan ng katotohanan.

b) ;

Conjunctive normal form ay maginhawa para sa awtomatikong pagpapatunay theorems. Ang anumang Boolean formula ay maaaring gawing CNF. Para dito maaari mong gamitin: ang batas ng double negation, batas ni Morgan, distributivity.

Encyclopedic YouTube

• 1 / 5

  Mga formula sa KNF:

  ¬ A ∧ (B ∨ C), (\displaystyle \neg A\wedge (B\vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E), (\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge ( D\vee\neg E),) A∧B. (\displaystyle A\wedge B.)

  Mga formula wala sa KNF:

  ¬ (B ∨ C), (\displaystyle \neg (B\vee C),) (A ∧ B) ∨ C , (\displaystyle (A\wedge B)\vee C,) A ∧ (B ∨ (D ∧ E)) . (\displaystyle A\wedge (B\vee (D\wedge E)).)

  Ngunit ang 3 formula na ito na wala sa CNF ay katumbas ng mga sumusunod na formula sa CNF:

  ¬ B ∧ ¬ C , (\displaystyle \neg B\wedge \neg C,) (A ∨ C) ∧ (B ∨ C) , (\displaystyle (A\vee C)\wedge (B\vee C),) A ∧ (B ∨ D) ∧ (B ∨ E) . (\displaystyle A\wedge (B\vee D)\wedge (B\vee E).)

  Konstruksyon ng CNF

  Algorithm para sa pagbuo ng CNF

  1) Alisin ang lahat ng mga lohikal na operasyon na nakapaloob sa formula, palitan ang mga ito ng mga pangunahing: conjunction, disjunction, negation. Magagawa ito gamit ang mga katumbas na formula:

  A → B = ¬ A ∨ B , (\displaystyle A\rightarrow B=\neg A\vee B,) A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B) . (\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \neg B).)

  2) Palitan ang negation sign na nauugnay sa buong expression ng negation sign na nauugnay sa mga indibidwal na variable statement batay sa mga formula:

  ¬ (A ∨ B) = ¬ A ∧ ¬ B , (\displaystyle \neg (A\vee B)=\neg A\wedge \neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B . (\displaystyle \neg (A\wedge B)=\neg A\vee \neg B.)

  3) Alisin ang dobleng negatibo.

  4) Ilapat, kung kinakailangan, ang mga katangian ng distributivity at absorption formula sa mga operasyon ng conjunction at disjunction.

  Halimbawa ng pagtatayo ng CNF

  Dalhin natin ang formula sa CNF

  F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) . (\displaystyle F=(X\rightarrow Y)\wedge ((\neg Y\rightarrow Z)\rightarrow \neg X).)

  Ibahin natin ang formula F (\displaystyle F) sa isang formula na hindi naglalaman → (\displaystyle \rightarrow ):

  F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ Y ∨ Z) ​​​​∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge (\neg (\neg Y\rightarrow Z)\vee \neg X)=(\neg X\vee Y)\wedge (\neg (\neg \ neg Y\vee Z)\vee \neg X).)

  Sa resultang formula, inililipat namin ang negasyon sa mga variable at binabawasan ang mga dobleng negatibo:

  F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X).)

  Halimbawa, ang sumusunod na formula ay nakasulat sa 2-CNF:

  (A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . (\displaystyle (A\lor B)\land (\neg B\lor C)\land (B\lor \neg C).)

  Simple pang-ugnay tinawag pang-ugnay isa o ilang mga variable, sa ito bawat isa variable nagkikita Hindi higit pa isa beses (o kanyang sarili, o kanya negasyon).

  Halimbawa, ay isang simpleng pang-ugnay,

  Disjunctive normal Hugis(DNF) tinawag disjunction simple lang mga pang-ugnay.

  Halimbawa, ang expression ay DNF.

  Perpekto disjunctive normal Hugis(SDNF) tinawag ganito disjunctive normal anyo, sa alin V bawat pang-ugnay kasama Lahat mga variable binigay listahan (o kanilang sarili, o kanilang pagtanggi), at V isa At dami parehook.

  Halimbawa, ang expression ay DNF, ngunit hindi SDNF. Pagpapahayag ay SDNF.

  Ang mga katulad na kahulugan (na may pagpapalit ng conjunction sa pamamagitan ng disjunction at vice versa) ay totoo para sa CNF at SKNF. Ibigay natin ang eksaktong salita.

  Simple disjunction tinawag disjunction isa o ilang mga variable, sa ito bawat isa variable kasama Hindi higit pa isa beses (o kanyang sarili, o kanya negasyon).Halimbawa, ang expression ay isang simpleng disjunction,

  Conjunctive normal Hugis(KNF) tinawag pang-ugnay simple lang disjunctions(halimbawa, ang expression ay CNF).

  Ang isang perpektong conjunctive normal form (PCNF) ay isang CNF kung saan ang bawat simpleng disjunction ay kinabibilangan ng lahat ng mga variable ng isang ibinigay na listahan (alinman sa kanilang sarili o sa kanilang mga negasyon), at sa parehong pagkakasunud-sunod.

  Halimbawa, ang expression ay SKNF.

  Ipakita natin ang mga algorithm para sa mga paglipat mula sa isang anyo patungo sa isa pa. Naturally, sa mga partikular na kaso (na may isang tiyak na malikhaing diskarte) ang paggamit ng mga algorithm ay maaaring maging mas labor-intensive kaysa sa mga simpleng pagbabago gamit ang isang partikular na uri ng isang naibigay na form:

  a) paglipat mula DNF hanggang CNF

  Ang algorithm para sa paglipat na ito ay ang mga sumusunod: inilalagay namin ang dalawang negasyon sa itaas ng DNF at, gamit ang mga panuntunan ni De Morgan (nang hindi hinahawakan ang itaas na negation), binabawasan namin ang negasyon ng DNF pabalik sa DNF. Sa kasong ito, kailangan mong buksan ang mga bracket gamit ang absorption rule (o Blake's rule). Ang negation (itaas) ng nagreresultang DNF (muli ayon sa tuntunin ni de Morgan) ay agad na nagbibigay sa atin ng CNF:

  Tandaan na ang CNF ay maaari ding makuha mula sa orihinal na expression kung kukuha tayo sa lampas sa mga bracket;

  b) paglipat mula sa CNF patungo sa DNF

  Isinasagawa ang paglipat na ito sa pamamagitan lamang ng pagbubukas ng mga bracket (muling ginagamit ang panuntunan sa pagsipsip)

  Kaya, nakatanggap kami ng DNF.

  Ang reverse transition (mula sa SDNF hanggang DNF) ay nauugnay sa problema ng pagliit ng DNF. Ito ay tatalakayin nang mas detalyado sa seksyon. 5, dito namin ipapakita kung paano gawing simple ang DNF (o SDNF) ayon sa panuntunan ni Blake. Ang ganitong uri ng DNF ay tinatawag pinaikling DNF;

  c) pagdadaglat ng DNF (o SDNF) ng tuntunin Blake

  Ang aplikasyon ng panuntunang ito ay binubuo ng dalawang bahagi:

  Kung kabilang sa magkahiwalay na termino sa DNF ay may mga termino , pagkatapos ay sa buong disjunction idagdag namin ang termino SA 1 SA 2. Ginagawa namin ang operasyong ito nang ilang beses (maaaring sunud-sunod, o sabay-sabay) para sa lahat ng posibleng pares ng mga termino, at pagkatapos ay ilapat ang normal na pagsipsip;

  Kung ang idinagdag na termino ay nakapaloob na sa DNF, maaari itong ganap na itapon, halimbawa,

  o

  Siyempre, ang pinaikling DNF ay hindi natatanging tinukoy, ngunit lahat sila ay naglalaman ng parehong bilang ng mga titik (halimbawa, mayroong DNF , pagkatapos ilapat ang panuntunan ni Blake dito, maaaring makarating ang isa sa katumbas na DNF dito):

  c) paglipat mula sa DNF patungo sa SDNF

  Kung ang ilang simpleng conjunction ay may nawawalang variable, halimbawa, z, ipasok ang expression dito, at pagkatapos ay buksan ang mga panaklong (hindi kami nagsusulat ng paulit-ulit na magkahiwalay na mga termino). Halimbawa:

  d) paglipat mula sa KNF patungo sa SKNF

  Isinasagawa ang paglipat na ito sa paraang katulad ng nauna: kung ang isang simpleng disjunction ay nawawala ang ilang variable (halimbawa, z, pagkatapos ay nagdaragdag kami ng isang expression dito (hindi nito binabago ang disjunction mismo), pagkatapos nito ay binuksan namin ang mga bracket gamit ang batas sa pamamahagi):

  Kaya, nakuha ang SKNF mula sa CNF.

  Tandaan na ang minimal o pinababang CNF ay karaniwang nakukuha mula sa kaukulang DNF.

  Normal na anyo ng mga lohikal na function Ang representasyon ng isang Boolean function sa anyo ng isang disjunction ng mga conjunctive terms ng mga constituent ng unit Ki 2.7 ay tinatawag na disjunctive normal form ng DNF ng function na ito. naglalaman ng eksaktong isa sa lahat ng mga lohikal na variable na kinuha nang may o walang mga negation, pagkatapos ang form na ito ng representasyon ng isang function ay tinatawag na isang perpektong disjunctive normal form SDNF ng function na ito. Tulad ng nakikita mo, kapag bumubuo ng isang SDNF function, kailangan mong lumikha ng isang disjunction ng lahat ng minterms kung saan ang function ay tumatagal ng halaga 1.

  
  Ibahagi ang iyong trabaho sa mga social network

  Kung ang gawaing ito ay hindi angkop sa iyo, sa ibaba ng pahina ay may isang listahan ng mga katulad na gawa. Maaari mo ring gamitin ang pindutan ng paghahanap

  
  

  Lektura 1.xx

  Mga normal na anyo ng mga lohikal na pag-andar

  Representasyon ng isang Boolean function sa anyo ng isang disjunction ng mga conjunctive terms (unit constituent) K i

  , (2.7)

  tinawag disjunctive normal na anyo(DNF) ng function na ito.

  Kung ang lahat ng magkakaugnay na termino sa DNF ay minterms , ibig sabihin ay naglalaman ng eksaktong isa sa lahat ng mga lohikal na variable, kinuha nang may o walang mga negasyon, pagkatapos ang form na ito ng representasyon ng function ay tinatawagperpektong disjunctive normal na anyo(SDNF ) ang function na ito. Ito ay tinatawag na SDNF perpekto , dahil ang bawat termino sa disjunction ay kinabibilangan ng lahat ng mga variable; disjunctive , dahil ang pangunahing operasyon sa formula ay disjunction. Konsepto "normal na hugis” ay nangangahulugang isang hindi malabo na paraan ng pagsulat ng isang pormula na nagpapatupad ng isang ibinigay na function.

  Isinasaalang-alang ang nasa itaas, ang sumusunod na theorem ay sumusunod mula sa Theorem 2.1.

  Teorama 2. Anumang Boolean function(hindi magkapareho 0) maaaring ipakita sa SDNF, .

  Halimbawa 3. Hayaan kaming magkaroon ng isang talahanayan na ibinigay function f (x 1 , x 2 , x 3 ) (Talahanayan 10).

  Talahanayan 10

  			f (x 1 , x 2 , x 3 )

  Batay sa formula (2.6) nakukuha natin:

  Tulad ng nakikita mo, kapag bumubuo ng isang SDNF function, kailangan mong lumikha ng isang disjunction ng lahat ng minterms kung saan ang function ay tumatagal ng halaga 1.

  Representasyon ng isang Boolean function sa anyo ng isang conjunction ng mga disjunctive terms (zero constituent) D i

  , (2.8)

  tinawag conjunctive normal na anyo(CNF) ng function na ito.

  Kung ang lahat ng disjunctive na termino ng CNF ay maxterms , ibig sabihin, naglalaman ng eksaktong isa sa lahat ng mga lohikal na variable ng function, na kinuha nang may o walang mga negasyon, pagkatapos ay tinatawag ang naturang CNFperpektong conjunctive normal na anyo(SKNF) ng function na ito.

  Teorama 3. Anumang Boolean function(hindi katulad ng 1) maaaring isumite sa SKNF, at ang gayong representasyon ay iisa lamang.

  Ang patunay ng theorem ay maaaring isagawa katulad ng patunay ng Theorem 2.1 batay sa sumusunod na Shannon lemma sa conjunctive decomposition.

  Ang Lemma ni Shannon . Anumang Boolean function f (x 1, x 2, …, x m) mula sa m ang mga variable ay maaaring ilarawan tulad nito:

  . (2.9)

  Dapat pansinin na ang parehong mga anyo ng representasyon ng isang lohikal na function (DNF at CNF) ay theoretically pantay sa kanilang mga kakayahan: anumang lohikal na formula ay maaaring kinakatawan pareho sa DNF (maliban sa magkaparehong zero) at sa CNF (maliban sa magkaparehong formula. ). Depende sa sitwasyon, maaaring mas maikli ang representasyon ng isang function sa isang anyo o iba pa.

  Sa pagsasagawa, ang DNF ay kadalasang ginagamit, dahil ang form na ito ay mas pamilyar sa isang tao: mula pagkabata, siya ay mas sanay sa pagdaragdag ng mga produkto kaysa sa pagpaparami ng mga kabuuan (sa huling kaso, siya ay intuitively ay may pagnanais na buksan ang mga bracket at sa gayon ay lumipat sa DNF).

  Halimbawa 4. Para sa function na f (x 1 , x 2 , x 3 ), na ibinigay ng talahanayan. 10, isulat ito sa SKNF.

  Hindi tulad ng SDNF, kapag kino-compile ang SCNF sa talahanayan ng katotohanan ng isang lohikal na function, kailangan mong tingnan ang mga kumbinasyon ng mga variable kung saan kinukuha ng function ang halaga 0, at lumikha ng isang conjunction ng kaukulang maxterms,ngunit ang mga variable ay dapat kunin na may reverse inversion:

  Dapat tandaan na imposibleng direktang lumipat mula sa SDNF ng isang function patungo sa SCNF nito o vice versa. Kapag sinusubukan ang gayong mga pagbabago, ang mga resulta ay mga pag-andar na kabaligtaran ng mga nais. Ang mga expression para sa SDNF at SCNF function ay maaaring direktang makuha lamang mula sa talahanayan ng katotohanan nito.

  Halimbawa 5. Para sa function na f (x 1 , x 2 , x 3 ), na ibinigay ng talahanayan. 10, subukang lumipat mula SDNF patungo sa SKNF.

  Gamit ang resulta ng halimbawa 2.3 nakukuha natin:

  Tulad ng nakikita mo, sa ilalim ng pangkalahatang inversion nakuha namin ang SCNF ng isang lohikal na function, na kung saan ay ang kabaligtaran ng function na nakuha sa halimbawa 2.4:

  dahil naglalaman ito ng lahat ng maxterms na wala sa expression para sa SCNF ng function na isinasaalang-alang.

  1. Gamit ang mga katangian ng mga operasyon (tingnan ang Talahanayan 9) pagkakakilanlan (), sum modulo 2 (), implikasyon (), nagpapatuloy tayo sa mga operasyong AT, O, HINDI (sa Boolean na batayan).

  2. Gamit ang mga katangian ng negation at mga batas ni De Morgan (tingnan ang Talahanayan 9), tinitiyak namin na ang mga pagpapatakbo ng negation ay nalalapat lamang sa mga indibidwal na variable, at hindi sa buong expression.

  3. Gamit ang mga katangian ng lohikal na operasyong AT at O ​​(tingnan ang Talahanayan 9), nakukuha natin ang normal na anyo (DNF o CNF).

  4. Kung kinakailangan, magpatuloy sa mga perpektong form (SDNF o SKNF). Halimbawa, upang makakuha ng SCNF madalas mong kailangang gamitin ang property: .

  Halimbawa 6. I-convert ang isang lohikal na function sa SKNF

  Isinasagawa ang mga hakbang ng algorithm sa itaas sa pagkakasunud-sunod, nakukuha namin:

  Gamit ang pag-aari ng pagsipsip, nakukuha namin ang:

  Kaya, nakuha namin ang CNF function f (x 1 , x 2 , x 3 ). Upang makuha ang SCNF nito, kailangan mong ulitin ang bawat disjunction kung saan nawawala ang anumang variable, dalawang beses kasama ang variable na ito at kasama ang negation nito:

  2.2.6. Pag-minimize ng Logic Function

  Dahil ang parehong lohikal na function ay maaaring kinakatawan bilang h personal na mga formula, pagkatapos ay paghahanap ng pinakasimpleng anyo R mule na tumutukoy sa isang Boolean function, pinapasimple ang logic circuit na nagpapatupad ng Boolean function sa tion. Pinakamababang anyo l O lohikal na pag-andarsa ilang batayan maaari nating isaalang-alang ang isa na naglalaman ng pinakamababang bilang ng mga superposisyon ng saya Upang tions ng batayan, na nagbibigay-daan para sa mga panaklong. Gayunpaman, mahirap bumuo ng isang epektibo l algorithm para sa naturang minimization upang makuha ang pinakamababang panaklong r kami.

  Isaalang-alang natin ang isang mas simpleng problema sa pag-minimize sa synthesis ng mga combinational circuit, kung saan hinahanap natin hindi ang minimal na parenthetical form ng isang function, ngunit para sa minimal na DNF nito. Mayroong simple at mahusay na mga algorithm para sa gawaing ito.

  Pamamaraan ni Quine

  Ang function na i-minimize ay kinakatawan sa SDNF, at lahat ng posibleng hindi kumpletong gluing operation ay inilalapat dito

  , (2.10)

  at pagkatapos ay pagsipsip

  , (2.11)

  at ang pares ng mga hakbang na ito ay paulit-ulit na inilalapat. Kaya, posibleng bawasan ang ranggo ng mga termino. Ang pamamaraang ito ay paulit-ulit hanggang sa wala nang isang termino na natitira na maaaring iugnay sa anumang iba pang termino.

  Tandaan na ang kaliwang bahagi ng equation (2.10) ay maaaring agad na mabawasan sa mas simple at mas malinaw na paraan:

  Ang pamamaraang ito ay masama dahil sa gayong direktang pag-minimize, maaaring mawala ang mga magkakaugnay na termino, bagama't may mga posibleng kaso pa rin ng paggamit ng mga ito para sa pagdikit at pagsipsip sa mga natitirang termino.

  Dapat tandaan na ang pamamaraan ni Quine ay medyo matrabaho, kaya ang posibilidad na magkamali sa panahon ng mga pagbabago ay medyo mataas. Ngunit ang kalamangan nito ay ang teoryang ito ay magagamit para sa anumang bilang ng mga argumento at habang ang bilang ng mga variable ay tumataas, ang mga pagbabagong-anyo ay nagiging mas kumplikado.

  Paraan ng mapa ng Karnaugh

  Ang paraan ng mga mapa ng Carnot (mga talahanayan) ay isang mas visual, hindi gaanong labor-intensive at maaasahang paraan upang mabawasan ang mga lohikal na pag-andar, ngunit ang paggamit nito ay halos limitado sa mga pag-andar ng 3-4 na mga variable, maximum na 5-6 na mga variable.

  Mapa ng Carnot ito ay isang two-dimensional na tabular form ng kumakatawan sa truth table ng isang Boolean function, na nagbibigay-daan sa iyong madaling mahanap ang pinakamababang DNF ng mga logical function sa isang graphical na visual na anyo. Ang bawat cell ng talahanayan ay nauugnay sa SDNF minterm ng function na pinaliit, at sa paraang ang anumang symmetry axes ng talahanayan ay tumutugma sa mga zone na magkabaligtaran na may kinalaman sa ilang variable. Ang pag-aayos na ito ng mga cell sa talahanayan ay ginagawang madali upang matukoy ang mga nakadikit na termino ng SDNF (naiiba sa inversion sign ng isang variable lamang): sila ay matatagpuan sa simetriko sa talahanayan.

  Mga talahanayan ng katotohanan at mga mapa ng Carnaugh para sa AND at OR function ng dalawang lane e Ang mga variable ay ipinakita sa Fig. 8. May nakasulat na value sa bawat cell ng card A Ang halaga ng isang function sa hanay ng mga halaga ng argumento na tumutugma sa cell na ito N Kasama

  A) AT b) O

  kanin. 8. Halimbawa ng mga mapa ng Karnaugh para sa mga function ng dalawang variable

  Sa Karnaugh map mayroon lamang isang 1 para sa And function, kaya hindi ito maaaring idikit sa kahit ano. Ang expression para sa minimal na function ay maglalaman lamang ng terminong naaayon sa 1 na ito:

  f = x y .

  Sa mapa ng Carnot para sa function na OR mayroon nang tatlong 1 at maaari kang gumawa ng dalawang pares na dumidikit, na ang 1 ay tumutugma sa termino xy , ay ginagamit ng dalawang beses. Sa expression para sa minimal na function, kailangan mong isulat ang mga termino para sa mga pares na pinagsama-sama, iniiwan sa kanila ang lahat ng mga variable na hindi nagbabago para sa pares na ito, at alisin ang mga variable na nagbabago ng kanilang halaga. Para sa pahalang na gluing nakukuha namin x , at para sa patayo y , bilang isang resulta nakukuha namin ang expression

  f = x + y.

  Sa Fig. 9 ay nagpapakita ng mga talahanayan ng katotohanan ng dalawang function ng tatlong variable ( A ) at ang kanilang mga mapa ng Carnot ( b at c). Function f 2 naiiba mula sa una dahil hindi ito tinukoy sa tatlong hanay ng mga variable (sa talahanayan ito ay ipinahiwatig ng isang gitling).

  Kapag tinutukoy ang minimum na function ng DNF, ginagamit ang mga sumusunod na patakaran. Ang lahat ng mga cell na naglalaman ng 1 ay pinagsama sa mga closed rectangular na lugar na tinatawag k-cube, kung saan k = log 2 K, K dami 1 sa isang hugis-parihaba na lugar. Sa kasong ito, ang bawat lugar ay dapat na isang parihaba na may bilang ng mga cell 2 k, kung saan ang k = 0, 1, 2, 3, …. Para sa k = 1 parihaba ang tinatawag ang isa ay isang kubo at naglalaman ng 2 1 = 2 yunit; para sa k = Ang 2 parihaba ay naglalaman ng 2 2 = 4 na yunit at tinatawag na dalawang-kubo; para sa k = 3 rehiyon ng 2 3 = 8 unit ang tawag tatlong-kubo ; atbp. Ang mga yunit na hindi maaaring pagsamahin sa mga parihaba ay maaaring tawagin zero-cube , na naglalaman lamang ng isang yunit (2 0 = 1). Tulad ng makikita, para sa kahit na k ang mga lugar ay maaaring magkaroon ng isang parisukat na hugis (ngunit hindi kinakailangan), at kung kakaiba k mga parihaba lamang.

  						b c

  kanin. 9. Halimbawa ng mga mapa ng Karnaugh para sa mga function ng tatlong variable

  Ang mga rehiyong ito ay maaaring mag-overlap, iyon ay, ang parehong mga cell ay maaaring pumasok sa iba't ibang mga rehiyon. Pagkatapos, ang minimal na function ng DNF ay isusulat bilang disjunction ng lahat ng magkakaugnay na termino na naaayon sa k - mga cube.

  Ang bawat isa sa mga ipinahiwatig na lugar sa Karnaugh map ay kinakatawan sa isang minimal na DNF sa pamamagitan ng isang conjunction, ang bilang ng mga argumento kung saan ay k mas mababa sa kabuuang bilang ng mga argumento ng function m , ibig sabihin, ang numerong ito ay pantay mk . Ang bawat conjunction ng isang minimal na DNF ay binubuo lamang ng mga argumento na para sa kaukulang lugar ng mapa ay may mga halaga alinman nang walang inversions o may lamang inversions, ibig sabihin, huwag baguhin ang kanilang kahulugan.

  Kaya, kapag sumasaklaw sa mga cell ng mapa na may mga saradong lugar, dapat magsikap na tiyakin na ang bilang ng mga lugar ay minimal, at ang bawat lugar ay naglalaman ng maraming mga cell hangga't maaari, dahil sa kasong ito ang bilang ng mga termino sa minimal na DNF ay magiging minimal at ang ang bilang ng mga argumento sa kaukulang conjunction ay magiging minimal.

  Para sa pag-andar ayon sa mapa ng Karnaugh sa Fig. 9, b nahanap natin

  dahil para sa itaas na saradong rehiyon ang mga variable x 1 at x 2 may mga halaga na walang inversion, para sa mas mababa x 1 bagay na may pagbabaligtad, at x 3 nang walang pagbabaligtad.

  Hindi natukoy na mga halaga sa mapa sa Fig. 9, V maaaring higit pang tukuyin sa pamamagitan ng pagpapalit nito ng zero o isa. Para sa pagpapaandar na ito, malinaw na mas kumikita na palitan ang parehong hindi natukoy na mga halaga ng 1. Sa kasong ito, dalawang lugar ang nabuo, na iba't ibang uri ng 2-cube. Kung gayon ang expression para sa minimum na function ng DNF ay ang mga sumusunod:

  Kapag gumagawa ng mga saradong lugar, pinapayagang tiklop ang mapa ng Carnot sa isang silindro nang pahalang at patayo. R tikal axes na may unyon ng magkasalungat na mukha R ikaw, ibig sabihin, mga unit na matatagpuan sa mga gilid ng Carnot symmetry map h ngunit maaari ding pagsamahin.

  Ang mga mapa ng Carnaugh ay maaaring iguhit sa iba't ibang paraan (Larawan 10).

  									x 2 x 3

  a b

  kanin. 10. Iba't ibang paraan upang ilarawan ang mga mapa ng Carnaugh
  para sa isang function ng 3 variable

  Ngunit ang pinaka-maginhawang opsyon para sa mga mapa ng Karnaugh para sa mga function ng 2-4 na variable ay ang mga ipinapakita sa Fig. 11 talahanayan, dahil ipinapakita ang mga ito para sa bawat cell A Mayroon kaming lahat ng mga variable sa direkta o kabaligtaran na anyo.

  a b

  kanin. labing-isa. Ang pinaka-maginhawang imahe ng mga mapa ng Carnaugh
  para sa mga function 3 ( a) at 4 (b) mga variable

  Para sa mga function ng 5 at 6 na variable, ang pamamaraan na ipinapakita sa Fig. 10, V .

  kanin. 12. Larawan ng isang Karnaugh map para sa isang function ng 5 variable

  kanin. 13. Larawan ng isang Karnaugh map para sa isang function ng 6 na variable

  Iba pang katulad na mga gawa na maaaring interesante sa iyo.vshm>
  9020.		ANG PRINSIPYO NG DUALIDAD. PAGPAPALAW NG BOOLEAN FUNCTION SA MGA VARIABLE. PERFECT DISJUNCTIVE AT CONJUNCTIVE NORMAL FORMS	96.34 KB
  	Ang theorem na ito ay nakabubuo sa kalikasan, dahil pinapayagan nito para sa bawat function na bumuo ng isang formula na nagpapatupad nito sa anyo ng isang perpektong d.n. f. Upang gawin ito, sa talahanayan ng katotohanan para sa bawat function, minarkahan namin ang lahat ng mga hilera kung saan
  6490.		Paglalarawan at pag-minimize ng mga lohikal na function	187.21 KB
  	Ang kaugnayan sa pagitan ng mga argumento ng isang function at mga halaga nito ay ipinahayag sa pandiwang anyo. Halimbawa: Ang isang tatlong-argument na function ay tumatagal ng isang halaga kapag ang alinman sa dalawa o higit pang mga argumento ng function ay pantay. Binubuo ng pagbuo ng talahanayan ng katotohanan na naglalaman ng mga halaga ng function para sa lahat ng hanay ng mga halaga ng argumento. Sa halimbawang ito, gamit ang talahanayan ng katotohanan, nakuha namin ang sumusunod na entry sa anyo ng DNF...
  6707.		Disenyo ng mga relational database. Mga problema sa disenyo sa klasikal na diskarte. Mga prinsipyo ng normalisasyon, mga normal na anyo	70.48 KB
  	Ano ang isang relational database project? Ito ay isang hanay ng mga magkakaugnay na relasyon kung saan ang lahat ng mga katangian ay tinukoy, ang mga pangunahing susi ng mga relasyon ay tinukoy, at ilang karagdagang mga katangian ng mga relasyon ay tinukoy na nauugnay sa mga prinsipyo ng pagpapanatili ng integridad. Samakatuwid, ang disenyo ng database ay dapat na tumpak at napatunayan. Sa katunayan, ang isang proyekto sa database ay ang pundasyon ng isang hinaharap na pakete ng software na gagamitin sa loob ng mahabang panahon at ng maraming mga gumagamit.
  4849.		Mga anyo at pamamaraan ng pagpapatupad ng mga tungkulin ng estado	197.3 KB
  	Ang terminong "function" ay malayo sa parehong kahulugan sa domestic at foreign scientific literature. Sa pilosopikal at pangkalahatang sosyolohikal na mga termino, ito ay itinuturing bilang "isang panlabas na pagpapakita ng mga katangian ng isang bagay sa isang ibinigay na sistema ng mga relasyon"; bilang isang hanay ng mga karaniwan o tiyak na mga aksyon ng mga indibidwal o katawan
  17873.		Pagbuo ng lohikal na UUD para sa mga mag-aaral sa ika-3 baitang	846.71 KB
  	Sikolohikal at pedagogical na aspeto ng problema ng pagbuo ng mga lohikal na unibersal na aksyon sa mga bata sa elementarya Mga pamamaraan para sa pagtatasa ng pagbuo ng mga lohikal na UUD. Ang pagbuo ng isang konsepto para sa pagbuo ng mga unibersal na aktibidad na pang-edukasyon sa pangkalahatang sistema ng edukasyon ay nakakatugon sa mga bagong pangangailangang panlipunan. Ang pinakamahalagang gawain ng modernong sistema ng edukasyon ay ang pagbuo ng mga unibersal na aktibidad na pang-edukasyon ng UUD. Ang pagbuo ng mga unibersal na aktibidad na pang-edukasyon ay ang susi sa pagpigil sa mga paghihirap sa paaralan.
  2638.		Teknikal na pagpapatupad ng mga lohikal na koneksyon sa mga awtomatikong sistema ng pagharang	1.04 MB
  	Teknikal na pagpapatupad ng mga lohikal na koneksyon sa mga awtomatikong blocking system Ang teknikal na pagpapatupad ng mga control algorithm para sa tatlong-digit at apat na-digit na baterya ay maaaring makamit gamit ang relay contact at contactless discrete at integral logic elements...
  10203.		APPLICATION OF THE CONCEPT OF RISK ORIENTED APPROACH TO BUILDING STRUCTURAL AND LOGICAL MODELS OF EMERGENCY OCCURENCE AND DEVELOPMENT	70.8 KB
  	Pangkalahatang pagsusuri sa panganib Ang kapaligiran ng produksyon ay nagiging puspos ng makapangyarihang mga teknolohikal na sistema at teknolohiya na ginagawang produktibo ang paggawa ng tao at hindi gaanong mahirap pisikal, ngunit mas mapanganib. Ang panganib ay nailalarawan sa pamamagitan ng hindi inaasahan at biglaang pagsisimula ng isang mapanganib na sitwasyon. Araw-araw ay nahaharap tayo sa maraming mga panganib, ngunit karamihan sa mga ito ay nananatiling potensyal. Ang teorya ng peligro ay nagbibigay ng isang quantitative assessment ng negatibong epekto sa isang tao, pati na rin ang pinsala sa kanyang kalusugan at buhay.
  11576.		Konsepto, uri at anyo ng mga transaksyon. Mga kahihinatnan ng hindi pagsunod sa kinakailangang anyo ng mga transaksyon	49.82 KB
  	Pagkilala sa isang transaksyon bilang di-wasto; mga uri ng mga di-wastong transaksyon. Ang inilapat na halaga ng gawaing kurso ay nakasalalay sa pagpapasimple ng konsepto ng isang transaksyon, iyon ay, ang pampublikong pagtatanghal nito sa isang mas madaling paraan.
  6213.		Pagtatantya ng function	3.08 MB
  	Ang una ay binubuo ng pagpapalit ng isang partikular na function na tinukoy sa analytical o tabularly ng isa pang function na malapit sa orihinal ngunit mas simple at mas maginhawa para sa mga kalkulasyon. Halimbawa, ang pagpapalit ng isang function na may polynomial ay nagbibigay-daan sa iyo upang makakuha ng mga simpleng formula para sa numerical integration at differentiation; Ang pagpapalit ng talahanayan ng isang approximating function ay nagbibigay-daan sa iyo upang makakuha ng mga halaga sa mga intermediate na punto nito. Ang pangalawang problema ay lumitaw din: pagpapanumbalik ng isang function sa isang tiyak na segment mula sa mga halaga ng function na ibinigay sa segment na ito sa isang discrete set ng mga puntos. Ang sagot sa tanong na ito...
  14058.		Ebolusyon ng mga tungkulin ng estado	29.99 KB
  	Ang estado ng Russia bilang isang ligal na kababalaghan ay dapat una sa lahat tiyakin ang pagpapatupad ng layunin ng estado pati na rin ang mga pangunahing katangian ng konstitusyon nito bilang isang demokratikong pederal na legal na panlipunang sekular na estado na may isang republikang anyo ng pamahalaan. Ang pangunahing layunin ng estado ay tinutukoy ng Art.