Jebkurai loģiskai formulai, izmantojot identitātes transformācijas, var izveidot bezgalīgi daudz tai līdzvērtīgu formulu. Loģikas algebrā viens no galvenajiem uzdevumiem ir kanonisko formu (t.i., formulu, kas konstruētas pēc viena noteikuma, kanona) meklēšana.

Ja loģiskā funkcija tiek izteikta ar mainīgo lielumu disjunkciju, konjunkciju un noliegumu, tad šo attēlojuma veidu sauc par normālu.

Starp normālām formām izšķir perfektās normālās formas (tās formas, kurās funkcijas ir ierakstītas unikālā veidā).

Perfekta disjunktīva normālā forma (PDNF)

Definīcija. Formulu sauc par elementāru savienojumu, ja to veido noteikta skaita mainīgo konjunkcija vai to noliegumi.

Piemēri: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

Definīcija. Formulu sauc par disjunktīvo normālo formu (DNF), ja tā ir neatkārtotu elementāru savienojumu disjunkcija.

DNF ir uzrakstīts šādā formā: F 1 ∨ F 2 ∨ ... ∨ F n , kur F i ir elementārais savienojums

Piemēri: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3, ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Definīcija. Loģisko formulu k mainīgajos sauc par perfektu disjunktīvo normālo formu (PDNF), ja:
1) formula ir DNF, kurā katrs elementārais savienojums ir k mainīgo x 1, x 2, ..., x k konjunkcija, un šī savienojuma i-tajā vietā ir vai nu mainīgais x i, vai tā noliegums. ;
2) visi elementārie savienojumi šādā DNF ir pa pāriem atšķirīgi.

Piemērs: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)

Perfekta konjunktīva normālā forma (PCNF)

Definīcija. Formulu sauc par elementāro disjunkciju, ja to veido noteikta skaita mainīgo vai to noliegumu disjunkcija.

Piemēri: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

Definīcija. Formulu sauc par konjunktīvo normālo formu (CNF), ja tā ir neatkārtotu elementāru disjunkciju konjunkcija.

CNF raksta šādā formā: F 1 ∧ F 2 ∧ ... ∧ F n , kur F i ir elementāra disjunkcija

Piemēri: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

Definīcija. Loģisko formulu k mainīgajos sauc par perfektu konjunktīvo normālo formu (CPNF), ja:
1) formula ir CNF, kurā katra elementārā disjunkcija ir k mainīgo x 1, x 2, ..., x k disjunkcija, un šīs disjunkcijas i-tajā vietā ir vai nu mainīgais x i, vai tā noliegums;
2) visas elementārās disjunkcijas šādā CNF ir pa pāriem atšķirīgas.

Piemērs: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)

ievērojiet, tas jebkuru loģisko funkciju, kas nav identiski vienāda ar 0 vai 1, var attēlot kā SDNF vai SKNF.

Algoritms SDNF konstruēšanai, izmantojot patiesības tabulu

  1. Atlasiet visas tabulas rindas, kurās funkcijas vērtība ir vienāda ar vienu.
  2. Katrai šādai rindai visu mainīgo konjunkciju ierakstiet šādi: ja kāda mainīgā vērtība šajā kopā ir vienāda ar 1, tad konjunkcijā iekļaujam pašu mainīgo, pretējā gadījumā tā noliegumu.
  3. Visas iegūtās konjunkcijas savienojam ar disjunkcijas operācijām.

Algoritms SCNF konstruēšanai, izmantojot patiesības tabulu

  1. Atlasiet visas tabulas rindas, kurās funkcijas vērtība ir nulle.
  2. Katrai šādai rindai visu mainīgo disjunkciju ierakstiet šādi: ja kāda mainīgā vērtība šajā kopā ir vienāda ar 0, tad konjunkcijā iekļaujam pašu mainīgo, pretējā gadījumā tā noliegumu.
  3. Visas iegūtās disjunkcijas savienojam ar konjunkcijas operācijām.

Algoritmu analīze parāda, ka, ja lielākajā daļā patiesības tabulas rindu funkcijas vērtība ir 0, tad tās loģiskās formulas iegūšanai labāk konstruēt SDNF, pretējā gadījumā - SCNF.

Piemērs: Dota trīs mainīgo loģiskās funkcijas patiesības tabula. Izveidojiet loģisku formulu, kas īsteno šo funkciju.

xyzF(x, y, z)
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1

Jo lielākajā daļā patiesības tabulas rindu funkcijas vērtība ir 1, tad mēs izveidosim SCNF. Rezultātā mēs iegūstam šādu loģisko formulu:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Pārbaudīsim iegūto formulu. Lai to izdarītu, mēs izveidosim funkcijas patiesības tabulu.

xyz¬x¬ x ∨ y ∨ z¬z¬ x ∨ y ∨ ¬ zF(x, y, z)
0 0 0 1 1 1 1 1
0 0 1 1 1 0 1 1
0 1 0 1 1 1 1 1
0 1 1 1 1 0 1 1
1 0 0 0 0 1 1 0
1 0 1 0 1 0 0 0
1 1 0 0 1 1 1 1
1 1 1 0 1 0 1 1

Salīdzinot sākotnējo patiesības tabulu un loģiskajai formulai konstruēto, mēs atzīmējam, ka funkciju vērtību kolonnas sakrīt. Tas nozīmē, ka loģiskā funkcija ir izveidota pareizi.

Propozīcijas algebras disjunktīvās un konjunktīvās normālās formas. Katrai priekšlikuma loģikas funkcijai var izveidot patiesības tabulu. Arī apgrieztā problēma vienmēr ir atrisināma. Ieviesīsim vairākas definīcijas.

Elementārie savienojumi (savienojumi) sauc par mainīgo konjunkcijām vai to noliegumiem, kuros katrs mainīgais sastopams ne vairāk kā

vienreiz.

Disjunktīva normālā forma(DNF) ir formula, kurai ir elementāru savienojumu disjunkcija.

Elementāras disjunkcijas (disjunkcijas) sauc par mainīgo lielumu disjunkcijām ar vai bez negācijām.

Konjunktīva parastā forma(CNF) ir formula, kurai ir elementāru disjunkciju konjunkcijas forma.

Katrai propozicionālās algebras funkcijai var atrast disjunktīvu un konjunktīvu normālformu kopu.

DNF izveides algoritms:

1. Pārejiet uz Būla operācijām, izmantojot līdzvērtīgas transformācijas formulas.

2. Pārejiet uz formulām ar tuvu noliegumiem, tas ir, uz formulu, kurā noliegumi atrodas ne augstāk kā virs mainīgajiem - piemērojiet De Morgana likumus.

3. Atveriet iekavas - piemērojiet sadales likumus.

4. Pieņem vienu reizi atkārtotus terminus – idempotences likumu.

5. Pielietojiet absorbcijas un pusabsorbcijas likumus.

6. piemērs. Atrodiet DNF formulas: .

Būla algebrā tā ir taisnība dualitātes princips. Tas ir šādi.

Funkcija tiek izsaukta dubultā uz funkciju if . Tie. Lai atrastu funkciju, kas ir duāla ar doto funkciju, ir jākonstruē funkcijas noliegums no argumentu noliegumiem.

7. piemērs. Atrodiet funkciju dubultā ar .

Starp loģikas algebras elementārajām funkcijām 1 ir duāls pret 0 un otrādi, x ir duāls ar x, duāls pret , duāls un otrādi.

Ja formulā F 1, kas attēlo funkciju, mēs aizstājam visus savienojumus

par disjunkciju, disjunkciju uz konjunkciju, 1 uz 0, 0 uz 1, tad iegūstam formulu F *, kas attēlo funkciju * ​​dual uz .

Konjunktīvā normālā forma (CNF) ir duāls DNF jēdziens, tāpēc to var viegli konstruēt saskaņā ar šādu shēmu:

8. piemērs. Atrodiet CNF formulu: .

Izmantojot 6. piemēra rezultātu, mums ir

Perfektas disjunktīvās un perfektās konjunktīvās normālās formas. Katrā no normālo formu veidiem (disjunktīvā un konjunktīvā) var izdalīt perfektu formu klasi SDNF un SCNF.

Perfekts elementārs savienojums ir visu mainīgo ar noliegumu vai bez tā loģisks produkts, un katrs mainīgais produktā parādās tikai vienu reizi.

Jebkuru DNF var reducēt par SDNF, sadalot savienojumus, kas nesatur visus mainīgos, t.i. saskaitot trūkstošajam mainīgajam x i tiek reizināts, izmantojot sadales likumu

9. piemērs. Atrodiet SDNF 6. piemēra DNF

Perfekta elementāra disjunkcija ir visu mainīgo ar vai bez noliegumiem loģiskā summa, un katrs mainīgais ir iekļauts summā tikai vienu reizi.

Jebkuru CNF var reducēt uz SCNF, pievienojot saikļa vārdu, kas nesatur nevienu mainīgo X i ar konjunkciju un piemērojot sadales likumu

10. piemērs. Nogādājiet KNF uz SKNF:

Lai izveidotu SCNF, varat izmantot diagrammu

11. piemērs. Atrodiet SCNF 6. piemēra formulai.

Katrai funkcijai ir SDNF un turklāt unikāls. Katrai funkcijai ir SCNF un turklāt unikāls.

Jo SDNF un SKNF ir unikāli definēti ar formulām; tos var konstruēt, izmantojot formulas patiesības tabulu.

Lai izveidotu SDNF, ir jāatlasa rindas, kurās F ņem vērtību 1, un jāpieraksta tām perfektas elementārās saites. Ja mainīgā vērtība vēlamajā patiesības tabulas rindā ir vienāda ar vienu, tad perfektā savienojumā to ņem bez noliegšanas, ja nulle, tad ar noliegumu. Tad perfektos savienojumus (to skaits ir vienāds ar vienību skaitu tabulā) savieno ar disjunkcijas zīmēm.

Lai izveidotu SCNF, izmantojot patiesības tabulu, tajā ir jāatlasa rindas, kur F = 0, un jāpieraksta perfektās elementārās disjunkcijas un pēc tam jāsavieno tās ar konjunkcijas zīmēm. Ja patiesības tabulas vajadzīgajā rindā (F=0) mainīgā vērtība atbilst nullei, tad perfektajā teikumā to ņem bez noliegšanas, ja ir viens, tad ar noliegumu.

12. piemērs. Atrodiet SDNF un SCNF, izmantojot patiesības tabulu 6. piemēra formulai.

14. tabulā parādīta tikai galīgā vērtība F=10101101. Jums pašam jāpārbauda šī apgalvojuma derīgums, izveidojot detalizētu patiesības tabulu.

14. tabula

x y z

Loģisko funkciju normālās formas Būla funkcijas attēlojumu vienības Ki 2.7 sastāvdaļu konjunktīvo vārdu disjunkcijas veidā sauc par šīs funkcijas DNF disjunktīvo normālo formu. satur tieši vienu no visiem loģiskajiem mainīgajiem ar vai bez noliegumiem, tad šo funkcijas attēlojuma formu sauc par šīs funkcijas perfekto disjunktīvo normālo formu SDNF. Kā redzat, veidojot SDNF funkciju, ir jāizveido visu mintermu, kuriem funkcijai ir vērtība 1, disjunkcija.


Kopīgojiet savus darbus sociālajos tīklos

Ja šis darbs jums neder, lapas apakšā ir līdzīgu darbu saraksts. Varat arī izmantot meklēšanas pogu


Lekcija 1.xx

Loģisko funkciju normālās formas

Būla funkcijas attēlojums konjunktīvu terminu disjunkcijas veidā (vienības sastāvdaļa) K i

, (2.7)

sauca disjunktīva normālā forma(DNF) šīs funkcijas.

Ja visi DNF konjunktīvie termini ir minterms , t.i., satur tieši vienu no visiem loģiskajiem mainīgajiem, ņemti ar vai bez noliegumiem, tad šo funkcijas attēlojuma formu saucperfekta disjunktīva normālā forma(SDNF ) šo funkciju. To sauc par SDNF ideāls , jo katrs disjunkcijas termins ietver visus mainīgos; disjunktīvs , jo galvenā darbība formulā ir disjunkcija. Jēdziens "normāla forma” nozīmē nepārprotamu formulas rakstīšanas veidu, kas īsteno noteiktu funkciju.

Ņemot vērā iepriekš minēto, no 2.1. teorēmas izriet šāda teorēma.

2. teorēma. Jebkura Būla funkcija(nav identiski 0) var uzrādīt SDNF, .

3. piemērs. Ļaujiet mums izveidot tabulas funkciju f (x 1 , x 2 , x 3 ) (10. tabula).

10. tabula

f (x 1 , x 2 , x 3 )

Pamatojoties uz formulu (2.6), iegūstam:

Kā redzat, veidojot SDNF funkciju, ir jāizveido visu mintermu, kuriem funkcijai ir vērtība 1, disjunkcija.

Būla funkcijas attēlojums disjunktīvu terminu savienojuma veidā (nulles sastāvdaļa) D i

, (2.8)

sauca konjunktīva normālā forma(CNF) šīs funkcijas.

Ja visi disjunktīvie CNF termini ir maxterms , t.i., satur tieši vienu no visiem funkcijas loģiskajiem mainīgajiem ar vai bez noliegumiem, tad šādu CNF saucideāla konjunktīva normālā forma(SKNF) šīs funkcijas.

3. teorēma. Jebkura Būla funkcija(nav identisks 1) var iesniegt SKNF, un tāds attēlojums ir vienīgais.

Teorēmas pierādīšanu var veikt līdzīgi kā 2.1. teorēmas pierādīšanu, pamatojoties uz šādu Šenona lemmu par konjunktīvo sadalīšanos.

Šenonas Lemma . Jebkura Būla funkcija f (x 1, x 2, …, x m) no m mainīgos var attēlot šādi:

. (2.9)

Jāpiebilst, ka abas loģiskās funkcijas attēlojuma formas (DNF un CNF) teorētiski ir vienādas pēc savām iespējām: jebkura loģiskā formula var tikt attēlota gan DNF (izņemot identisku nulli), gan CNF (izņemot identisko). ). Atkarībā no situācijas funkcijas attēlojums vienā vai citā formā var būt īsāks.

Praksē visbiežāk tiek izmantots DNF, jo šī forma cilvēkam ir vairāk pazīstama: kopš bērnības viņš ir vairāk pieradis pievienot produktus, nevis reizināt summas (pēdējā gadījumā viņam intuitīvi ir vēlme atvērt iekavas un tādējādi pāriet uz DNF).

4. piemērs. Funkcijai f (x 1 , x 2 , x 3 ), kas norādīts tabulā. 10, rakstiet to SKNF.

Atšķirībā no SDNF, kompilējot SCNF loģiskās funkcijas patiesības tabulā, ir jāaplūko mainīgo kombinācijas, kurās funkcijai ir vērtība 0, un jāizveido atbilstošo maxterms konjunkcija,bet mainīgie ir jāņem ar reverso inversiju:

Jāatzīmē, ka nav iespējams tieši pāriet no funkcijas SDNF uz tās SCNF vai otrādi. Mēģinot veikt šādas transformācijas, tiek iegūtas funkcijas, kas ir pretējas vēlamajām. Funkciju SDNF un SCNF izteiksmes var tieši iegūt tikai no tās patiesības tabulas.

5. piemērs. Funkcijai f (x 1 , x 2 , x 3 ), kas norādīts tabulā. 10, mēģiniet pārslēgties no SDNF uz SKNF.

Izmantojot 2.3 piemēra rezultātu, mēs iegūstam:

Kā redzat, vispārējā inversijā mēs ieguvām loģiskās funkcijas SCNF, kas ir 2.4. piemērā iegūtās funkcijas apgrieztā vērtība:

jo tajā ir visi maxterms, kas nav aplūkojamās funkcijas SCNF izteiksmē.

1. Izmantojot operāciju īpašības (skat. 9. tabulu) identitāte (), summa modulo 2 (), implikācija (), mēs pārejam pie operācijām AND, OR, NOT (Būla bāzē).

2. Izmantojot nolieguma īpašības un De Morgana likumus (sk. 9. tabulu), mēs nodrošinām, ka noliegšanas darbības attiecas tikai uz atsevišķiem mainīgajiem, nevis uz veselām izteiksmēm.

3. Izmantojot loģisko operāciju UN un VAI īpašības (skat. 9. tabulu), iegūstam normālo formu (DNF vai CNF).

4. Ja nepieciešams, pārejiet uz perfektām formām (SDNF vai SKNF). Piemēram, lai iegūtu SCNF, jums bieži ir jāizmanto rekvizīts: .

6. piemērs. Konvertējiet loģisko funkciju uz SKNF

Veicot iepriekš minētā algoritma darbības secībā, mēs iegūstam:

Izmantojot absorbcijas īpašību, mēs iegūstam:

Tādējādi mēs esam ieguvuši CNF funkciju f (x 1 , x 2 , x 3 ). Lai iegūtu tā SCNF, jums ir jāatkārto katra disjunkcija, kurā trūkst kāda mainīgā, divreiz ar šo mainīgo un ar tā noliegumu:

2.2.6. Loģisko funkciju samazināšana

Tā kā to pašu loģisko funkciju var attēlot kā h personiskās formulas, pēc tam atrodot vienkāršāko formu R mule, kas definē Būla funkciju, vienkāršo loģisko shēmu, kas ievieš Būla funkciju uz ciju. Minimālā forma l O loģiskā funkcijakaut kādā veidā mēs varam uzskatīt tādu, kurā ir minimālais jautrības superpozīciju skaits Uz pamata, pieļaujot iekavas. Tomēr ir grūti izveidot efektīvu l algoritmu šādai minimizēšanai, lai iegūtu minimālo iekava r mēs.

Apskatīsim vienkāršāku minimizēšanas problēmu kombinēto ķēžu sintēzē, kurā mēs meklējam nevis funkcijas minimālo iekavas formu, bet gan tās minimālo DNF. Šim uzdevumam ir vienkārši, efektīvi algoritmi.

Kvina metode

Minimizējamā funkcija ir attēlota SDNF, un tai tiek piemērotas visas iespējamās nepilnīgās līmēšanas darbības

, (2.10)

un pēc tam uzsūkšanos

, (2.11)

un šie soļi tiek piemēroti atkārtoti. Tādējādi ir iespējams samazināt terminu rangu. Šo procedūru atkārto, līdz vairs nav palicis neviens termins, ko varētu saistīt ar kādu citu terminu.

Ņemiet vērā, ka vienādojuma (2.10) kreiso pusi var nekavējoties samazināt vienkāršāk un skaidrāk:

Šī metode ir slikta, jo ar šādu tiešu minimizēšanu konjunktīvie termini vai nu pazūd, lai gan joprojām ir iespējami gadījumi, kad tie tiek izmantoti līmēšanai un absorbcijai ar atlikušajiem terminiem.

Jāatzīmē, ka Kvina metode ir diezgan darbietilpīga, tāpēc kļūdu iespējamība transformāciju laikā ir diezgan augsta. Bet tā priekšrocība ir tāda, ka teorētiski to var izmantot jebkuram argumentu skaitam un, palielinoties mainīgo skaitam, transformācijas kļūst mazāk sarežģītas.

Karnaugh kartes metode

Carnot karšu (tabulu) metode ir vizuālāks, mazāk darbietilpīgs un uzticamāks veids, kā minimizēt loģiskās funkcijas, taču tās izmantošana praktiski aprobežojas ar 3-4 mainīgo, maksimums 5-6 mainīgo funkcijām.

Carnot karte šī ir divdimensiju tabulas forma Būla funkcijas patiesības tabulas attēlošanai, kas ļauj viegli atrast loģisko funkciju minimālos DNF grafiskā vizuālā formā. Katra tabulas šūna ir saistīta ar funkcijas SDNF minterm, kas tiek minimizēta, un tādā veidā, ka jebkuras tabulas simetrijas asis atbilst zonām, kas ir savstarpēji apgrieztas attiecībā uz kādu mainīgo. Šāds šūnu izvietojums tabulā ļauj viegli noteikt SDNF pielipšanas nosacījumus (atšķiras tikai viena mainīgā inversijas zīme): tie tabulā atrodas simetriski.

Patiesības tabulas un Carnaugh kartes divu joslu UN un VAI funkcijām e Mainīgie lielumi ir parādīti attēlā. 8. Katrā kartes šūnā tiek ierakstīta vērtība A Funkcijas vērtība argumentu vērtību kopā, kas atbilst šai šūnai N Biedrs

A) UN b) VAI

Rīsi. 8. Karnaugh karšu piemērs divu mainīgo funkcijām

Karnaugh kartē funkcijai Un ir tikai viens 1, tāpēc to nevar pielīmēt nekam. Minimālās funkcijas izteiksmē būs tikai termins, kas atbilst šim 1:

f = x y .

Carnot kartē funkcijai VAI jau ir trīs 1 un jūs varat izveidot divus līmēšanas pārus, kur 1 atbilst vārdam xy , tiek izmantots divas reizes. Minimālās funkcijas izteiksmē jums ir jāpieraksta termini pāriem, kas tiek salīmēti kopā, atstājot tajos visus mainīgos, kas šim pārim nemainās, un noņemot mainīgos, kas maina to vērtību. Horizontālajai līmēšanai mēs iegūstam x , un vertikālai y , kā rezultātā mēs iegūstam izteiksmi

f = x + y.

Attēlā 9 parāda divu trīs mainīgo funkciju patiesuma tabulas ( A ) un to Carnot kartes ( b un c). Funkcija f 2 atšķiras no pirmās ar to, ka tas nav definēts uz trim mainīgo kopām (tabulā tas ir norādīts ar domuzīmi).

Nosakot minimālo DNF funkciju, tiek izmantoti šādi noteikumi. Visas šūnas, kas satur 1, tiek apvienotas slēgtās taisnstūrveida zonās, ko sauc k-kubi, kur k = log 2 K, K daudzums 1 taisnstūra laukumā. Šajā gadījumā katram laukumam jābūt taisnstūrim ar šūnu skaitu 2 k, kur k = 0, 1, 2, 3, …. Ja k = Tiek izsaukts 1 taisnstūris viens ir kubs un satur 2 1 = 2 vienības; par k = 2 taisnstūris satur 2 2 = 4 vienības un sauc divu kubu; ja k = 3 apgabals no 2 3 = tiek izsauktas 8 vienības trīs kubu ; utt. Var izsaukt vienības, kuras nevar apvienot taisnstūros nulles kubi , kas satur tikai vienu vienību (2 0 = 1). Kā redzams, pat k apgabaliem var būt kvadrāta forma (bet ne obligāti) un, ja tie ir nepāra k tikai taisnstūri.

b c

Rīsi. 9. Karnaugh karšu piemērs trīs mainīgo funkcijām

Šie reģioni var pārklāties, tas ir, vienas un tās pašas šūnas var iekļūt dažādos reģionos. Tad minimālā DNF funkcija tiek uzrakstīta kā visu konjunktīvo terminu disjunkcija, kas atbilst k - kubi.

Katrs no norādītajiem apgabaliem Karnaugh kartē ir attēlots minimālā DNF ar savienojumu, kurā argumentu skaits ir k mazāks par kopējo funkcijas argumentu skaitu m , t.i., šis skaitlis ir vienāds mk . Katrs minimālā DNF savienojums sastāv tikai no tiem argumentiem, kuriem atbilstošajam kartes apgabalam ir vērtības vai nu bez inversijām, vai tikai ar inversijām, t.i., nemaina to nozīmi.

Tādējādi, pārklājot kartes šūnas ar slēgtiem laukumiem, jācenšas nodrošināt, lai apgabalu skaits būtu minimāls un katrā apgabalā būtu pēc iespējas vairāk šūnu, jo šajā gadījumā terminu skaits minimālajā DNF būs minimāls un argumentu skaits attiecīgajā savienojumā būs minimāls.

Funkcijai saskaņā ar Karnaugh karti attēlā. 9, b mēs atrodam

jo augšējam slēgtajam reģionam mainīgie x 1 un x 2 ir vērtības bez inversijām zemākajam x 1 jautājumiem ar inversiju, un x 3 bez inversijas.

Nedefinētas vērtības kartē attēlā. 9, V var sīkāk definēt, aizstājot to ar nulli vai vienu. Šai funkcijai ir skaidrs, ka abas nenoteiktās vērtības ir izdevīgāk aizstāt ar 1. Šajā gadījumā tiek veidotas divas zonas, kas ir dažāda veida 2-kubi. Tad minimālās DNF funkcijas izteiksme būs šāda:

Būvējot slēgtās zonas, ir atļauts Carnot karti salocīt cilindrā gan horizontāli, gan vertikāli. R tikal cirvji ar pretēju seju savienību R jūs, t.i., vienības, kas atrodas gar Carnot simetrijas kartes malām h bet var arī kombinēt.

Carnaugh kartes var zīmēt dažādos veidos (10. att.).

x 2 x 3

a b

Rīsi. 10. Dažādi veidi, kā attēlot Carnaugh kartes
3 mainīgo funkcijai

Bet ērtākās iespējas Karnaugh kartēm 2–4 mainīgo funkcijām ir tās, kas parādītas attēlā. 11 tabulas, jo tās parāda katrai šūnai A Mums ir visi mainīgie tiešā vai apgrieztā formā.

a b

Rīsi. vienpadsmit. Ērtākais Carnaugh karšu attēls
funkcijai 3 ( a) un 4 (b) mainīgie

5 un 6 mainīgo funkcijām tiek izmantota metode, kas parādīta attēlā. 10, V .

Rīsi. 12. Karnaugh kartes attēls 5 mainīgo funkcijai

Rīsi. 13. Karnaugh kartes attēls 6 mainīgo funkcijai

Citi līdzīgi darbi, kas jūs varētu interesēt.vshm>
9020. DUALITĀTES PRINCIPS. BULA FUNKCIJU PAPLAŠINĀŠANA MAINĪGOS. IDEĀLĀS DISJUNKTĪVAS UN SAVIENOJAS NORMĀLFORMAS 96,34 KB
Šai teorēmai ir konstruktīvs raksturs, jo tā ļauj katrai funkcijai izveidot formulu, kas to realizē ideālas d.n formā. f. Lai to izdarītu, katras funkcijas patiesības tabulā mēs atzīmējam visas rindas, kurās
6490. Loģisko funkciju apraksts un minimizēšana 187,21 KB
Attiecības starp funkcijas argumentiem un tās vērtībām tiek izteiktas verbālā formā. Piemērs: trīs argumentu funkcija iegūst vērtību, ja divi vai vairāki funkcijas argumenti ir vienādi. Sastāv no patiesības tabulas izveides, kas satur funkciju vērtības visām argumentu vērtību kopām. Šajā piemērā, izmantojot patiesības tabulu, mēs iegūstam šādu ierakstu formā DNF...
6707. Relāciju datu bāzu projektēšana. Dizaina problēmas klasiskajā pieejā. Normalizācijas principi, normālās formas 70,48 KB
Kas ir relāciju datu bāzes projekts Šis ir savstarpēji saistītu attiecību kopums, kurā ir definēti visi atribūti, norādītas relāciju primārās atslēgas un norādītas dažas papildu relāciju īpašības, kas attiecas uz integritātes saglabāšanas principiem. Tāpēc datu bāzes dizainam jābūt ļoti precīzam un pārbaudītam. Faktiski datu bāzes projekts ir nākotnes programmatūras pakotnes pamats, ko izmantos diezgan ilgu laiku un daudzi lietotāji.
4849. Valsts funkciju īstenošanas formas un metodes 197,3 KB
Jēdzienam “funkcija” vietējā un ārvalstu zinātniskajā literatūrā nebūt nav vienādas nozīmes. Filozofiskā un vispārīgā socioloģiskā ziņā to uzskata par “objekta īpašību ārēju izpausmi noteiktā attiecību sistēmā”; kā indivīdu vai struktūru parastu vai konkrētu darbību kopums
17873. Loģiskā UUD veidošana 3. klases skolēniem 846,71 KB
Loģisko universālo darbību veidošanas problēmas psiholoģiskie un pedagoģiskie aspekti sākumskolas vecuma bērniem Loģisko UUD veidošanās novērtēšanas metodes. Universālu izglītības pasākumu attīstības koncepcijas izstrāde vispārējās izglītības sistēmā atbilst jaunām sociālajām vajadzībām. Mūsdienu izglītības sistēmas svarīgākais uzdevums ir UUD universālu izglītības aktivitāšu veidošana. Universālu izglītības pasākumu veidošana ir galvenais, lai novērstu skolas grūtības.
2638. Loģisko savienojumu tehniskā realizācija automātiskās bloķēšanas sistēmās 1,04 MB
Loģisko savienojumu tehniskā realizācija automātiskās bloķēšanas sistēmās Trīsciparu un četrciparu akumulatoru vadības algoritmu tehnisko realizāciju var panākt, izmantojot releja kontaktu un bezkontakta diskrētos un integrālos loģikas elementus...
10203. RISKU ORIENTĒTAS PIEEJAS KONCEPCIJAS PIEMĒROŠANA ĀRKĀRTAS SITUĀCIJAS UN ATTĪSTĪBAS STRUKTURĀLO UN LOĢISKO MODEĻU VEIDOŠANAI 70,8 KB
Vispārējā riska analīze Ražošanas vide kļūst piesātināta ar jaudīgām tehnoloģiskām sistēmām un tehnoloģijām, kas padara cilvēka darbu produktīvu un fiziski mazāk grūtu, bet bīstamāku. Risku raksturo bīstamas situācijas negaidītība un pēkšņums. Ikdienā mēs saskaramies ar neskaitāmiem riskiem, taču lielākā daļa no tiem joprojām ir potenciāli.Riska teorija paredz kvantitatīvi novērtēt negatīvo ietekmi uz cilvēku, kā arī kaitējumu viņa veselībai un dzīvībai.
11576. Darījumu jēdziens, veidi un formas. Nepieciešamās darījumu formas neievērošanas sekas 49,82 KB
Darījuma atzīšana par spēkā neesošu, nederīgo darījumu veidi. Kursa darba lietišķā vērtība ir darījuma jēdziena vienkāršošana, tas ir, tā publiska prezentācija pieejamākā formā.
6213. Funkcijas aproksimācija 3,08 MB
Pirmais sastāv no noteiktas analītiski vai tabulas veidā norādītas funkcijas aizstāšanas ar citu funkciju, kas ir tuvu oriģinālajai, bet vienkāršāka un ērtāka aprēķiniem. Piemēram, funkcijas aizstāšana ar polinomu ļauj iegūt vienkāršas formulas skaitliskai integrācijai un diferenciācijai; Tabulas aizstāšana ar tuvināšanas funkciju ļauj iegūt vērtības tās starppunktos. Rodas arī otrā problēma: funkcijas atjaunošana noteiktā segmentā no funkcijas vērtībām, kas šim segmentam dotas diskrētā punktu kopā. Atbilde uz šo jautājumu...
14058. Valsts funkciju evolūcija 29,99 KB
Krievijas valstij kā juridiskai parādībai pirmām kārtām ir jānodrošina valsts mērķa īstenošana, kā arī tās galvenās konstitucionālās īpašības kā demokrātiskai federālai tiesiskai sociāli sekulārai valstij ar republikas pārvaldes formu. Valsts galveno mērķi nosaka Art.

Normāla forma loģiskā formula nesatur neelementāru formulu implikācijas, ekvivalences un nolieguma pazīmes.

Parastā forma ir divos veidos:

    konjunktīva normālā forma (CNF)-- vairāku disjunkciju savienojums, piemēram, $\left(A\vee \overline(B)\vee C\right)\wedge \left(A\vee C\right)$;

    disjunktīvā normālā forma (DNF)-- vairāku savienojumu disjunkcija, piemēram, $\left(A\wedge \overline(B)\wedge C\right)\vee \left(B\wedge C\right)$.

SKNF

Perfekta konjunktīva normālā forma (PCNF) ir CNF, kas atbilst trim nosacījumiem:

    nesatur identiskas elementāras disjunkcijas;

    neviena no disjunkcijām nesatur vienus un tos pašus mainīgos;

    katra elementārā disjunkcija satur katru mainīgo, kas iekļauts dotajā CNF.

Jebkura Būla formula, kas nav identiski patiesa, var tikt attēlota SKNF.

Noteikumi SKNF konstruēšanai, izmantojot patiesības tabulu

Katrai mainīgo kopai, kurai funkciju vienāds ar 0, summa tiek pierakstīta, un mainīgie, kuru vērtība ir 1, tiek ņemti ar noliegumu.

SDNF

Perfekta disjunktīva normālā forma (PDNF) ir DNF, kas atbilst trim nosacījumiem:

    nesatur identiskus elementārus savienojumus;

    neviens no savienojumiem nesatur tos pašus mainīgos;

    Katrs elementārais savienojums satur katru mainīgo, kas iekļauts dotajā DNF, un tādā pašā secībā.

Jebkura Būla formula, kas nav identiski nepatiesa, var tikt attēlota SDNF un unikālā veidā.

Noteikumi SDNF konstruēšanai, izmantojot patiesības tabulu

Katrai mainīgo kopai, kurai funkcija ir vienāda ar 1, tiek uzrakstīts reizinājums, un mainīgie, kuru vērtība ir 0, tiek ņemti ar noliegumu.

SCNF un SDNF atrašanas piemēri

1. piemērs

Uzrakstiet loģisku funkciju, izmantojot tās patiesības tabulu:

1. attēls.

Risinājums:

Izmantosim kārtulu SDNF konstruēšanai:

2. attēls.

Mēs saņemam SDNF:

Izmantosim noteikumu SCNF konstruēšanai.