Esimerkki. Etsi CNF-kaavat

~ ~

SDNF:n täydellinen disjunktiivinen normaalimuoto voidaan rakentaa käyttämällä seuraavaa algoritmia:

1. = 1. DNF-algoritmi

2. = 2. DNF-algoritmi

3. = 3. DNF-algoritmi

4. = 4. DNF-algoritmi

5. Jätä pois identtiset väärät termit, eli lomakkeen termit

6. Täydennä loput termit puuttuvilla muuttujilla

7. Toista kohta 4.

Esimerkki. Etsi SDNF-kaavat.

~

SCNF:n rakentamiseen voit käyttää seuraavaa kaaviota:

Esimerkki. Etsi SDNF-kaavat.

~

Tiedetään (Lauseet 2.11, 2.12), että SDNF ja SCNF määritellään yksiselitteisesti kaavalla ja siksi ne voidaan konstruoida käyttämällä kaavan totuustaulukkoa.

Kaava SDNF:n ja SCNF:n rakentamiseksi totuustaulukon mukaan on annettu alla kaavalle ~ :

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

2.2. Harjoittele.

2.2.1 Alla on Boolen lausekkeet. Yksinkertaista muunnelmasi lausekkeet mahdollisimman paljon käyttämällä Boolen logiikan lakeja. Käytä sitten totuustaulukoita vertaillaksesi yksinkertaistettua lausekettasi alkuperäiseen.

2.2.2. Selvitä kysymys f 1:n ja f 2:n vastaavuudesta vähentämällä ne SDNF:ksi (taulukko 1).

2.2.3. Etsi f 3:n kaksoisfunktio käyttämällä yleistettyä ja Boolen periaatetta (taulukko 1). Vertaa tuloksia.

№	f 1	f 2	f 3

2.3. Kontrollikysymykset.

2.3.1. Määrittele lausunto.

2.3.2. Listaa lausunnon päätoiminnot.

2.3.3. Mikä on totuustaulukko?

2.3.4. Luo totuustaulukot seuraaville kaavoille:

~ ~ ~ ;

2.3.5. Kun otetaan huomioon operaatioiden järjestystä koskevat sopimukset, jätä kaavoista pois "ylimääräiset" sulkeet ja " "-merkki:

;

2.3.6. Todista kaavojen identtinen totuus käyttämällä ekvivalentteja muunnoksia:

2.3.7. Etsi kaksoiskaavat:

)

2.3.8. Pienennä seuraavat kaavat täydelliseen DNF (SDNF) muotoon:

~

2.3.9. Pienennä seuraavat kaavat täydelliseen CNF-muotoon (SCNF):

~

Laboratoriotyö nro 3

Aihe:"Boolen funktioiden minimointi. Logiikka"

Kohde: Hankitaan käytännön taitoja työskennellä Boolen funktioiden minimointimenetelmien kanssa.

3.1. Teoreettista tietoa.

Minimaaliset muodot

Kuten näytettiin, mikä tahansa Boolen funktio voidaan esittää täydellisessä normaalimuodossa (disjunktiivi tai konjunktiivi). Lisäksi tällainen esitys on ensimmäinen askel siirtymisessä funktion taulukkomäärittelystä sen analyyttiseen ilmaisuun. Seuraavassa edetään disjunktiivimuodosta, ja vastaavat tulokset konjunktiivimuodolle saadaan kaksinaisuuden periaatteen perusteella.

Kanoninen ongelma loogisten piirien syntetisoinnissa Boolen pohjalta tiivistyy Boolen funktioiden minimoimiseen, ts. edustamaan niitä disjunktiivisessa normaalimuodossa, joka sisältää pienimmän määrän kirjaimia (muuttujia ja niiden negaatioita). Tällaisia ​​muotoja kutsutaan minimaaliksi. Kanonisessa synteesissä oletetaan, että sekä signaalit että niiden inversiot syötetään piirin tuloihin.

Disjunktiivisessa normaalimuodossa esitettyä kaavaa yksinkertaistetaan käyttämällä toistuvasti liimausoperaatiota ja absorptiooperaatiota ja (konjunktiivisen normaalimuodon kaksoisidentiteetit ovat muotoa: ja ). Tässä ja voidaan ymmärtää minkä tahansa Boolen algebran kaavana. Tuloksena päästään analyyttiseen lausekkeeseen, jossa muut muunnokset eivät ole enää mahdollisia, ts. saamme umpikujamuodon.

Umpikujamuotojen joukossa on myös minimaalinen disjunktiivinen muoto, eikä se välttämättä ole ainutlaatuinen. Varmistaaksesi, että tietty umpikujalomake on minimaalinen, sinun on löydettävä kaikki umpikujalomakkeet ja verrattava niitä niiden sisältämien kirjainten lukumäärän mukaan.

Oletetaan esimerkiksi funktio täydellisessä normaalissa disjunktiivimuodossa:

Ryhmittelemällä termit ja soveltamalla liimausoperaatiota meillä on .

Toisella ryhmittelymenetelmällä saamme:

Molemmat umpikujamuodot eivät ole minimaalisia. Minimaalisen muodon saamiseksi sinun on arvattava toistaaksesi yksi termi alkuperäisessä kaavassa (tämän voi aina tehdä, koska ). Ensimmäisessä tapauksessa tällainen jäsen voi olla . Sitten . Lisäämällä termin , saamme: . Kun olet käynyt läpi kaikki mahdolliset vaihtoehdot, voit varmistaa, että kaksi viimeistä muotoa ovat minimaaliset.

Kaavojen kanssa työskentely tällä tasolla on kuin vaeltelua pimeässä. Minimaalisten muotojen etsintäprosessista tulee visuaalisempi ja tarkoituksenmukaisempi, jos käytät joitain graafisia ja analyyttisiä esityksiä ja symboleita, jotka on erityisesti kehitetty tähän tarkoitukseen.

Moniulotteinen kuutio

Jokainen -ulotteisen kuution kärki voidaan liittää yksikön ainesosaan. Näin ollen merkittyjen pisteiden osajoukko on täydellisessä disjunktiivisessa normaalimuodossa olevien muuttujien Boolen funktion -ulotteisen kuution kartoitus. Kuvassa 3.1 esittää tällaisen funktion kuvauksen lausekkeesta 3.7.

Kuva 3.1 SDNF:ssä esitetyn funktion näyttö kolmiulotteisessa kuutiossa

Missä tahansa disjunktiivisessa normaalimuodossa esitettyjen muuttujien funktion näyttämiseksi on tarpeen luoda vastaavuus sen minitermien ja -ulotteisen kuution elementtien välille.

(-1) arvosanan minitermiä voidaan pitää tuloksena, kun liimataan yhteen kaksi arvosanaa (yksinäisyyden ainesosa), ts. , -ulotteisessa kuutiossa tämä vastaa kahden sellaisen kärjen korvaamista, jotka eroavat vain koordinaatin arvoista, jotka yhdistävät nämä kärjet reunaan (reunan sanotaan peittävän siihen tulevat kärjet). Siten (-1):nnen kertaluvun minitermit vastaavat -ulotteisen kuution reunoja. Vastaavasti (-2) kertaluvun minitermien vastaavuus määritetään -ulotteisen kuution pintojen kanssa, joista jokainen peittää neljä kärkeä (ja neljä reunaa).

-ulotteisen kuution elementtejä, joille on tunnusomaista mitat, kutsutaan -kuutioiksi. Siten kärjet ovat 0-kuutiot, reunat 1-kuutiot, pinnat ovat 2-kuutiot jne. Yleistäen yllä olevaa päättelyä, voidaan olettaa, että ():nnen asteen minitermi disjunktiivisessa normaalimuodossa muuttujien funktiolle esitetään -kuutiolla, ja jokainen -kuutio kattaa kaikki ne pienemmän ulottuvuuden -kuutiot, jotka liittyvät sen kärkiin. . Esimerkkinä kuvassa. 3.2 esittää kolmen muuttujan funktiota. Tässä minitermit ja vastaavat 1-kuutiota (), ja minitermiä edustaa 2-kuutio ().

Kuva 3.2 Toiminnon kattavuus

Joten mikä tahansa disjunktiivinen normaalimuoto kartoitetaan -ulotteiseen kuutioon joukolla -kuutioita, jotka kattavat kaikki yksikön aineosia vastaavat kärjet (0-kuutiot). Myös käänteinen väite on totta: jos tietty joukko -kuutioita kattaa joukon kaikkia funktion yksikköarvoja vastaavia pisteitä, niin näitä -kuutioita vastaavien minitermien disjunktio on tämän funktion lauseke disjunktiivisessa normaalissa. muodossa. Tällaisen kokoelman -kuutioita (tai niitä vastaavia minitermejä) sanotaan muodostavan funktion peitteen.

Minimaalisen muodon halu ymmärretään intuitiivisesti sellaisen päällysteen etsimiseksi, jonka kuutioiden määrä olisi pienempi ja niiden mitat suurempi. Minimimuotoa vastaavaa kattavuutta kutsutaan minimikattavuudeksi. Esimerkiksi kuvan 1 peittotoiminnolle. 3.3 täyttää vähimmäislomakkeet Ja .

Riisi. 3.3 Toimintojen kattavuus.

vasemmalle – ; oikealla –

Toiminnon näyttäminen -ulotteisessa kuutiossa on selkeä ja yksinkertainen, kun . Neliulotteinen kuutio voidaan kuvata kuvan 1 mukaisesti. 3.4, joka näyttää neljän muuttujan funktion ja sen lauseketta vastaavan minimikattavuuden . Tämän menetelmän käyttö vaatii niin monimutkaisia ​​rakenteita, että kaikki sen edut menetetään.

Riisi. 3.4 Toimintojen näyttö neliulotteisessa kuutiossa

Carnot kartat

Toinen menetelmä Boolen funktioiden graafiseen esittämiseen käyttää Carnot kartat, jotka ovat erityisesti järjestettyjä vastaavuustaulukoita. Taulukon sarakkeet ja rivit vastaavat kaikkia mahdollisia enintään kahden muuttujan arvojoukkoja, ja nämä joukot on järjestetty sellaiseen järjestykseen, että jokainen seuraava eroaa edellisestä vain yhden muuttujan arvossa. . Tämän ansiosta taulukon viereiset solut vaakasuunnassa ja pystysuunnassa eroavat vain yhden muuttujan arvosta. Taulukon reunoilla sijaitsevat solut katsotaan myös vierekkäisiksi ja niillä on tämä ominaisuus. Kuvassa Kuva 3.5 näyttää Karnaugh-kartat kahdelle, kolmelle, neljälle muuttujalle.

Riisi. 3.5 Carnaugh-kartat kahdelle, kolmelle ja neljälle muuttujalle

Kuten tavallisissa totuustaulukoissa, niiden joukkojen solut, joissa funktio saa arvon 1, täytetään ykkösillä (nollat ​​eivät yleensä mahdu sisään, ne vastaavat tyhjiä soluja). Esimerkiksi kuvassa Fig. 3.6, A esittää Karnaugh-kartan funktiolle, jonka näyttö neliulotteisessa kuutiossa on esitetty kuvassa 1. 3.4. Asioiden yksinkertaistamiseksi rivit ja sarakkeet, jotka vastaavat muuttujan arvoa 1, on korostettu tätä muuttujaa osoittavalla aaltosululla.

Riisi. 3.6 Neljän muuttujan funktion näyttäminen Carnaugh-kartalla

(a) ja sen vähimmäissuoja (b)

Funktiokartoitusten välillä n-ulotteinen kuutio ja Carnot-kartta ovat yksi-yhteen vastaavuus. Carnotin kartalla s-kuutio vastaa 2 vierekkäisen solun joukkoa, jotka on sijoitettu riviin, sarakkeeseen, neliöön tai suorakulmioon (ottaen huomioon kartan vastakkaisten reunojen läheisyyden). Siksi kaikki edellä mainitut määräykset (katso kohta. moniulotteinen kuutio), ovat voimassa Karnaugh-kartoissa. Joten kuvassa 3.6, b näyttää minimidisjunktiivimuotoa vastaavien karttayksiköiden kattavuuden kyseessä oleva toiminto.

Minitermien lukeminen Karnaugh-kartalta noudattaa yksinkertaista sääntöä. Solujen muodostuminen s-kuutio, anna miniter (n–s)-th rank, joka sisältää ne (n–s) muuttujat, jotka säilyttävät samat arvot tässä s-kuutio, jossa arvo 1 vastaa itse muuttujia ja arvo 0 vastaa niiden negaatioita. Muuttujat, jotka eivät säilytä arvojaan s-kuutio, ovat poissa minitermissä. Erilaiset lukutavat johtavat funktion erilaisiin esityksiin disjunktiivisessa normaalimuodossa (äärioikealla oleva minimaalinen) (kuva 3.7).

Karnaugh-karttojen käyttö vaatii yksinkertaisempia rakenteita verrattuna kartoitukseen n-ulotteinen kuutio, erityisesti neljän muuttujan tapauksessa. Viiden muuttujan funktioiden näyttämiseksi käytetään kahta Karnaugh-karttaa neljälle muuttujalle ja kuuden muuttujan funktiolle neljää tällaista karttaa. Muuttujien määrän lisääntyessä Karnaugh-kartoista tulee käytännössä käyttökelvottomia.

Kuuluisa kirjallisuudessa Veitch-kortit Ne eroavat toisistaan ​​vain muuttujaarvojoukkojen eri järjestyksessä ja niillä on samat ominaisuudet kuin Karnaugh-kartoilla.

Kuutioiden kompleksi

Graafisten menetelmien epäjohdonmukaisuus suurella määrällä muuttujia kompensoidaan erilaisilla analyyttisilla menetelmillä Boolen funktioiden esittämiseksi. Yksi tällainen esitys on kuutioiden kompleksi, jossa käytetään moniulotteista loogista avaruusterminologiaa yhdessä erityisesti kehitetyn symbolismin kanssa.

). 0-kuutiot, jotka vastaavat yhtenäisyyden ainesosia, esitetään muuttuja-arvojoukoilla, joilla funktio on yhtä suuri kuin yksikkö. Ilmeisesti äänityksessä

Riisi. 3.8 Kolmen muuttujan funktion kuutioiden kompleksi ( A) ja sen symbolinen esitys ( b)

Kuutioiden kompleksi muodostuu maksimaalinen toimintopeitto. Sulkemalla pois kaikki nuo s-kuutiot, jotka on peitetty suuremmilla kuutioilla, saadaan umpikujamuotoja vastaavat päällysteet. Tarkasteltavalle esimerkille (kuva 3.8) on siis umpikuja

,

joka vastaa toimintoa . Tässä tapauksessa tämä kattavuus on minimaalinen.

Kahden Boolen funktion disjunktiooperaatio vastaa niiden kuutiokompleksien liittoa ja konjunktiooperaatio vastaa niiden kuutiokompleksien leikkauskohtaa. Funktion negaatio vastaa kuutiokompleksin komplementtia, eli sen määräävät kaikki kärjet, joissa funktio saa arvon 0. Siten funktion algebran välillä on yksi yhteen vastaavuus (isomorfismi). Boolen funktiot ja Boolen joukot, jotka edustavat kuutioiden komplekseja.

Funktion esittäminen kuutiokompleksien muodossa on vähemmän visuaalista, mutta sen tärkeimmät edut ovat muuttujien lukumäärän rajoitusten poistaminen ja tiedon koodaus helpottuu tietokoneita käytettäessä.

Minimoi Boolen funktiot

Ongelman muotoilu. Piirin minimointi Boolen perusteella laskee vähimmäispeittoa vastaavan vähimmäisdisjunktiivimuodon löytämisen. Normaalimuodossa olevien kirjeiden kokonaismäärä ilmaistaan ​​peittokuluina , missä on niiden kuutioiden lukumäärä, jotka muodostavat tietyn n muuttujan funktion peitteen. Minimikattavuudelle on ominaista sen hinnan alhaisin arvo.

Tyypillisesti minimointiongelma ratkaistaan ​​kahdessa vaiheessa. Ensin etsimme pienennettyä kantta, joka sisältää kaikki maksimimittaiset -kuutiot, mutta ei sisällä ainuttakaan kuutiota, jonka yksikään tämän kannen kuutio peittää. Vastaavaa disjunktiivista normaalimuotoa kutsutaan pelkistetyksi ja sen minitermejä yksinkertaisiksi implikantteiksi. Tietylle toiminnolle alennettu peitto on ainutlaatuinen, mutta se voi olla tarpeeton, koska jotkin kuutioista ovat muiden kuutioiden kokoelmien peittämiä.

Toisessa vaiheessa siirrytään pelkistetyistä disjunktiivisista normaalimuodoista umpikujaan, joista valitaan minimaaliset muodot. Umpikujamuodot muodostetaan jättämällä pois supistetusta kattavuudesta kaikki ylimääräiset kuutiot, joita ilman jäljellä oleva kuutiojoukko muodostaa edelleen tietyn funktion peitteen, mutta jos jokin kuutioista edelleen jätetään pois, se ei enää kata kuutioiden joukkoa. kaikki funktion yksittäisiä arvoja vastaavat kärjet, eli se lakkaa olemasta peitto.

Pienennetty peittokuutio, joka kattaa tietyn funktion kärjet, joita muut kuutiot eivät peitä, ei voi olla redundantti, ja se sisällytetään aina vähimmäispeittoon. Tällaista kuutiota, kuten sen vastaavaa implikanttia, kutsutaan äärimmäiseksi (olennainen implikantti), ja sen peittämiä kärkipisteitä kutsutaan peruutetuiksi pisteiksi. Extremaalien joukko muodostaa päällysteen ytimen, on selvää, että siirryttäessä pelkistetystä päällysteestä minimaaliseen tulee ensinnäkin eristää kaikki ääripäät. Jos ääripäiden sarja ei muodosta peitettä, sitä täydennetään peittämällä kuutioilla pelkistetystä päällysteestä.

Annetut määritelmät on havainnollistettu kuvassa. 3.9, jossa kattavuus on pienempi (katso kuva 3.9a, ) ja vähimmäispeitot (kuva 3.9b) ja (katso kuva 3.9, b) ilmaistaan ​​seuraavasti.

Määritelmä 1.Konjunktiivinen monomiaali (alkeiskonjunktio) muuttujien konjunktio on näiden muuttujien tai niiden negaatioiden konjunktio.

Esimerkiksi, on alkeiskonjunktio.

Määritelmä 2.Disjunktiivinen monomiaali (alkeisdisjunktio) muuttujista on näiden muuttujien disjunktio tai niiden negaatiot.

Esimerkiksi, on alkeisdisjunktio.

Määritelmä 3. Kaava, joka vastaa annettua lausealgebran kaavaa ja on alkeiskonjunktiivisten monomien disjunktio, kutsutaan disjunktiivinen normaalimuoto(DNF) tämän kaavan mukaisesti.

Esimerkiksi,– DNF.

Määritelmä 4. Kaava, joka vastaa tiettyä lausealgebran kaavaa ja on alkeisdisjunktiivisten monomien konjunktio, kutsutaan konjunktiivinen normaalimuoto(CNF) tämän kaavan mukaisesti.

Esimerkiksi, – KNF.

Jokaiselle lausealgebran kaavalle voidaan löytää joukko disjunktiivisia ja konjunktiivisia normaalimuotoja.

Algoritmi normaalimuotojen muodostamiseksi

Käytä loogisen algebran ekvivalensseja, korvaa kaikki kaavan perustoiminnot: konjunktio, disjunktio, negaatio:

Päästä eroon kaksoisnegatiivista.

Käytä tarvittaessa distributiivisuus- ja absorptiokaavojen ominaisuuksia konjunktio- ja disjunktiooperaatioihin.

2.6. Täydelliset disjunktiiviset ja täydelliset konjunktiiviset normaalimuodot

Jokaisella Boolen funktiolla voi olla useita esityksiä DNF- ja CNF-muodossa. Erityinen paikka näiden esitysten joukossa on täydellinen DNF (SDNF) ja täydellinen CNF (SCNF).

Määritelmä 1. Täydellinen disjunktiivinen normaalimuoto(SDNF) on DNF, jossa jokainen konjunktiivinen monomi sisältää jokaisen muuttujan joukosta täsmälleen kerran, joko itsensä tai sen negatiivisen.

Rakenteellisesti kunkin lausealgebrakaavan SDNF, joka on pelkistetty DNF:ksi, voidaan määritellä seuraavasti:

Määritelmä 2. Täydellinen disjunktiivinen normaalimuoto Propositioalgebrakaavan (SDNF) kutsutaan sen DNF:ksi, jolla on seuraavat ominaisuudet:

Määritelmä 3. Täydellinen konjunktiivinen normaalimuoto(SCNF) on CNF, jossa jokainen disjunktiivinen monomi sisältää jokaisen muuttujan joukosta täsmälleen kerran, ja joko itse tai sen negaatio ilmestyy.

Rakenteellisesti kunkin lausealgebrakaavan SCNF, joka on pelkistetty CNF:ksi, voidaan määritellä seuraavasti.

Määritelmä 4. Täydellinen konjunktiivinen normaalimuoto Tietyn lausealgebrakaavan (SCNF) kutsutaan CNF:ksi, joka täyttää seuraavat ominaisuudet.

Lause 1. Jokainen muuttujien Boolen funktio, joka ei ole identtisesti epätosi, voidaan esittää SDNF:ssä ja ainutlaatuisella tavalla.

Menetelmät SDNF:n löytämiseksi

1. menetelmä

2. menetelmä

valitse rivit, joissa kaava saa arvon 1;

muodostamme konjunktioiden disjunktion sillä ehdolla, että jos muuttuja sisältyy konjunktioon, jonka arvo on 1, niin kirjoitetaan tämä muuttuja ylös, jos arvo on 0, niin sen negaatio. Saamme SDNF:n.

Lause 2. Jokainen muuttujien Boolen funktio, joka ei ole identtisesti tosi, voidaan esittää SCNF:ssä ja ainutlaatuisella tavalla.

Menetelmät SCNF:n löytämiseksi

1. menetelmä– käyttämällä vastaavia muunnoksia:

2. menetelmä– totuustaulukoiden käyttö:

valitse rivit, joissa kaava saa arvon 0;

muodostamme disjunktioiden konjunktion sillä ehdolla, että jos muuttuja sisältyy disjunktioon arvolla 0, niin kirjoitetaan tämä muuttuja, jos arvo on 1, niin sen negaatio. Saamme SKNF:n.

Esimerkki 1. Muodosta CNF-funktiot.

Ratkaisu

Poistetaan yhdistävä "" käyttämällä muuttujan muunnoslakeja:

= /de Morganin lait ja kaksoisnegatio/ =

/jakelulait/ =

Esimerkki 2. Anna kaava DNF:lle.

Ratkaisu

Ilmaistaan ​​loogiset toiminnot käyttämällä ja:

= /Luokitellaan negaatio muuttujiksi ja vähennetään kaksinkertaiset negatiivit/ =

= /jakauman laki/ .

Esimerkki 3. Kirjoita kaava muodossa DNF ja SDNF.

Ratkaisu

Käytämme logiikan lakeja, pelkistämme tämän kaavan muotoon, joka sisältää vain alkeiskonjunktioiden disjunktiot. Tuloksena oleva kaava on haluttu DNF:

SDNF:n muodostamiseksi luodaan totuustaulukko tälle kaavalle:

Merkitsemme ne taulukon rivit, joissa kaava (viimeinen sarake) saa arvon 1. Jokaiselle tällaiselle riville kirjoitetaan kaava, joka on tosi tämän rivin muuttujien joukkoon:

rivi 1: ;

rivi 3: ;

rivi 5: .

Näiden kolmen kaavan disjunktio saa arvon 1 vain rivien 1, 3, 5 muuttujajoukoissa ja on siksi haluttu täydellinen disjunktiivinen normaalimuoto (PDNF):

Esimerkki 4. Tuo kaava SKNF:lle kahdella tavalla:

a) käyttämällä vastaavia muunnoksia;

b) käyttämällä totuustaulukkoa.

Ratkaisu:

Muunnetaan toinen alkeisdisjunktio:

Kaava näyttää tältä:

b) laadi totuustaulukko tälle kaavalle:

Merkitsemme ne taulukon rivit, joissa kaava (viimeinen sarake) saa arvon 0. Jokaiselle tällaiselle riville kirjoitetaan kaava, joka on tosi tämän rivin muuttujien joukkoon:

linja 2: ;

rivi 6: .

Näiden kahden kaavan konjunktio saa arvon 0 vain rivien 2 ja 6 muuttujajoukoissa ja on siksi haluttu täydellinen konjunktiivinen normaalimuoto (PCNF):

Kysymyksiä ja tehtäviä itsenäiseen ratkaisuun

1. Käytä vastaavia muunnoksia, vähennä kaavat DNF:ksi:

2. Käytä vastaavia muunnoksia, tuo kaavat CNF:ään:

3. Muunna DNF CNF:ksi käyttämällä toista distributiivista lakia:

A) ;

4. Muunna annetut DNF:t SDNF:iksi:

5. Muunna annettu CNF SCNF:ksi:

6. Muodosta SDNF ja SCNF annetuille loogisille kaavoille kahdella tavalla: käyttämällä vastaavia muunnoksia ja käyttämällä totuustaulukkoa.

b) ;

Konjunktiivinen normaalimuoto on kätevä lauseiden automaattiseen todistamiseen. Mikä tahansa Boolen kaava voidaan pelkistää CNF:ksi. Tätä varten voit käyttää: kaksoisnegaation lakia, de Morganin lakia, distributiivisuutta.

Tietosanakirja YouTube

• 1 / 5

  Kaavat KNF:ssä:

  ¬ A ∧ (B ∨ C) , (\displaystyle \neg A\wedge (B\vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E) , (\näyttötyyli (A\vee B)\kiila (\neg B\vee C\vee \neg D)\kiila ( D\vee\neg E)) A∧B. (\näyttötyyli A\kiila B.)

  Kaavat ei KNF:ssä:

  ¬ (B ∨ C) , (\displaystyle \neg (B\vee C),) (A ∧ B) ∨ C , (\näyttötyyli (A\kiila B)\vee C,) A ∧ (B ∨ (D ∧ E)) . (\displaystyle A\wedge (B\vee (D\wedge E)).)

  Mutta nämä 3 kaavaa, jotka eivät ole CNF:ssä, vastaavat seuraavia CNF:n kaavoja:

  ¬ B ∧ ¬ C , (\näyttötyyli \neg B\kiila \neg C,) (A ∨ C) ∧ (B ∨ C) , (\näyttötyyli (A\vee C)\kiila (B\vee C),) A ∧ (B ∨ D) ∧ (B ∨ E) . (\displaystyle A\wedge (B\vee D)\wedge (B\vee E).)

  CNF:n rakentaminen

  Algoritmi CNF:n rakentamiseksi

  1) Päästä eroon kaikista kaavan sisältämistä loogisista operaatioista korvaamalla ne perusoperaatioilla: konjunktio, disjunktio, negaatio. Tämä voidaan tehdä vastaavilla kaavoilla:

  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) Korvaa koko lausekkeeseen liittyvä negatiivinen merkki yksittäisiin muuttujalauseisiin liittyvillä negatiivisilla kaavoilla:

  ¬ (A ∨ B) = ¬ A ∧ ¬ B , (\näyttötyyli \neg (A\vee B)=\neg A\kiila \neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B . (\displaystyle \neg (A\wedge B)=\neg A\vee \neg B.)

  3) Päästä eroon kaksoisnegatiivista.

  4) Käytä tarvittaessa distributiivisuus- ja absorptiokaavojen ominaisuuksia konjunktio- ja disjunktiooperaatioihin.

  Esimerkki CNF:n rakentamisesta

  Tuodaan kaava CNF:ään

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

  Muunnetaan kaava F (\displaystyle F) kaavaan, joka ei sisällä → (\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).)

  Tuloksena olevassa kaavassa siirrämme negaation muuttujiin ja vähennämme kaksoisnegatiivisia:

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

  Esimerkiksi seuraava kaava on kirjoitettu 2-CNF:llä:

  (A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . (\displaystyle (A\tai B)\maa (\neg B\tai C)\maa (B\tai \neg C).)

  Yksinkertainen konjunktio nimeltään konjunktio yksi tai useita muuttujia, klo Tämä jokainen muuttuja tapaa Ei lisää yksi ajat (tai oma itsensä, tai hänen kieltäminen).

  Esimerkiksi on yksinkertainen konjunktio,

  Disjunktiivinen normaali muoto(DNF) nimeltään disjunktio yksinkertainen konjunktiot.

  Lauseke on esimerkiksi DNF.

  Täydellinen disjunktiivinen normaali muoto(SDNF) nimeltään kuten tämä disjunktiivinen normaali muodossa, klo mikä V joka konjunktio mukana Kaikki muuttujia annettu lista (tai itse, tai heidän kieltäminen), ja V yksi Ja äänenvoimakkuutta samaokei.

  Lauseke on esimerkiksi DNF, mutta ei SDNF. Ilmaisu on SDNF.

  Samanlaiset määritelmät (konjunktion korvaaminen disjunktiolla ja päinvastoin) pätevät CNF:lle ja SKNF:lle. Esitetään tarkka sanamuoto.

  Yksinkertainen disjunktio nimeltään disjunktio yksi tai useita muuttujia, klo Tämä jokainen muuttuja mukana Ei lisää yksi ajat (tai oma itsensä, tai hänen kieltäminen).Esimerkiksi lauseke on yksinkertainen disjunktio,

  Konjunktiivi normaali muoto(KNF) nimeltään konjunktio yksinkertainen disjunktiot(esimerkiksi ilmaus on CNF).

  Täydellinen konjunktiivinen normaalimuoto (PCNF) on CNF, jossa jokainen yksinkertainen disjunktio sisältää kaikki tietyn listan muuttujat (joko itsensä tai niiden negaatiot) ja samassa järjestyksessä.

  Esimerkiksi ilmaisu on SKNF.

  Esitetään algoritmit siirtymille muodosta toiseen. Tietyissä tapauksissa (tietyllä luovalla lähestymistavalla) algoritmien käyttö voi luonnollisesti olla työvoimavaltaisempaa kuin yksinkertaiset muunnokset tietyn muodon tietyllä tavalla:

  a) siirtyminen DNF:stä CNF:ään

  Tämän siirtymän algoritmi on seuraava: laitamme kaksi negaatiota DNF:n yläpuolelle ja De Morganin sääntöjä käyttäen (koskematta ylempään negaatioon) pienennämme DNF:n negaatiota takaisin DNF:ksi. Tässä tapauksessa sinun on avattava sulut käyttämällä absorptiosäännöä (tai Blaken sääntöä). Tuloksena olevan DNF:n negaatio (ylempi) (taas de Morganin säännön mukaan) antaa meille välittömästi CNF:n:

  Huomaa, että CNF voidaan saada myös alkuperäisestä lausekkeesta, jos otamme pois klo sulkeiden ulkopuolella;

  b) siirtyminen CNF:stä DNF:ään

  Tämä siirtyminen suoritetaan yksinkertaisesti avaamalla sulut (absorptiosääntöä käytetään jälleen)

  Näin ollen saimme DNF:n.

  Käänteinen siirtyminen (SDNF:stä DNF:ään) liittyy DNF:n minimoimisen ongelmaan. Tästä keskustellaan tarkemmin osiossa. 5, tässä näytämme kuinka yksinkertaistaa DNF (tai SDNF) Blaken säännön mukaan. Tätä DNF-tyyppiä kutsutaan lyhennettynä DNF;

  c) lyhenne DNF (tai SDNF). sääntö Blake

  Tämän säännön soveltaminen koostuu kahdesta osasta:

  Jos DNF:n erillisten termien joukossa on termejä , niin koko disjunktioon lisätään termi TO 1 TO 2. Suoritamme tämän toiminnon useita kertoja (mahdollisesti peräkkäin tai samanaikaisesti) kaikille mahdollisille termipareille ja käytämme sitten normaalia absorptiota;

  Jos lisätty termi sisältyi jo DNF:ään, se voidaan hylätä kokonaan, esim.

  tai

  Lyhennetty DNF ei tietenkään ole yksiselitteisesti määritelty, mutta ne kaikki sisältävät saman määrän kirjaimia (esim. DNF , kun siihen on sovellettu Blaken sääntöä, voidaan saavuttaa tätä vastaava DNF):

  c) siirtyminen DNF:stä SDNF:ään

  Jos jostakin yksinkertaisesta konjunktiosta puuttuu muuttuja, esim. z, lisää lauseke siihen ja avaa sitten sulut (emme kirjoita toistuvia disjunktitermejä). Esimerkiksi:

  d) siirtyminen KNF:stä SKNF:ään

  Tämä siirtymä suoritetaan samalla tavalla kuin edellinen: jos yksinkertaisesta disjunktiosta puuttuu jokin muuttuja (esim. z, lisäämme siihen lausekkeen (tämä ei muuta itse disjunktiota), jonka jälkeen avaamme sulut jakelulain avulla:

  Siten SKNF saatiin CNF:stä.

  Huomaa, että minimaalinen tai pelkistetty CNF saadaan yleensä vastaavasta DNF:stä.

  Loogisten funktioiden normaalimuodot Boolen funktion esitystä yksikön Ki 2.7 aineosien konjunktiivitermien disjunktiomuodossa kutsutaan tämän funktion DNF:n disjunktiiviseksi normaalimuodoksi. sisältää täsmälleen yhden kaikista loogisista muuttujista negaatioilla tai ilman, niin tätä funktion esitysmuotoa kutsutaan tämän funktion täydelliseksi disjunktiiviseksi normaalimuodoksi SDNF. Kuten näet, kun kirjoitat SDNF-funktiota, sinun on luotava disjunktio kaikista mintermeistä, joille funktio saa arvon 1.

  
  Jaa työsi sosiaalisessa mediassa

  Jos tämä työ ei sovi sinulle, sivun alareunassa on luettelo vastaavista teoksista. Voit myös käyttää hakupainiketta

  
  

  Luento 1.xx

  Loogisten funktioiden normaalit muodot

  Boolen funktion esitys konjunktiivitermien disjunktiona (yksikön ainesosa) K i

  , (2.7)

  nimeltään disjunktiivinen normaalimuoto(DNF) tämän toiminnon.

  Jos kaikki DNF:n konjunktiivitermit ovat minterms , eli ne sisältävät täsmälleen yhden kaikista loogisista muuttujista negatiivisten kanssa tai ilman, niin tätä funktion esitysmuotoa kutsutaantäydellinen disjunktiivinen normaalimuoto(SDNF ) tämä toiminto. Sitä kutsutaan SDNF:ksi täydellinen , koska jokainen disjunktion termi sisältää kaikki muuttujat; disjunktiivinen , koska kaavan pääoperaatio on disjunktio. Konsepti "normaali muoto” tarkoittaa yksiselitteistä tapaa kirjoittaa kaava, joka toteuttaa tietyn funktion.

  Yllä oleva huomioon ottaen Lauseesta 2.1 seuraa seuraava lause.

  Lause 2. Mikä tahansa Boolen funktio(ei identtisesti 0) voidaan esittää SDNF:ssä, .

  Esimerkki 3. Otetaan taulukkoon annettu funktio f (x1, x2, x 3) (taulukko 10).

  Taulukko 10

  			f (x 1 , x 2 , x 3 )

  Kaavan (2.6) perusteella saamme:

  Kuten näet, kun kirjoitat SDNF-funktiota, sinun on luotava disjunktio kaikista mintermeistä, joille funktio saa arvon 1.

  Boolen funktion esitys disjunktiivisten termien konjunktiona (nolla aineosa) D i

  , (2.8)

  nimeltään konjunktiivinen normaalimuoto(CNF) tämän toiminnon.

  Jos kaikki disjunktiiviset CNF-termit ovat maxterms , eli ne sisältävät täsmälleen yhden funktion kaikista loogisista muuttujista negaatioiden kanssa tai ilman, silloin tällaista CNF:ää kutsutaantäydellinen konjunktiivinen normaalimuoto(SKNF) tämän toiminnon.

  Lause 3. Mikä tahansa Boolen funktio(ei ole identtinen 1:n kanssa) voidaan toimittaa SKNF:lle, ja tällainen esitys on ainoa.

  Lauseen todistus voidaan suorittaa samalla tavalla kuin Lauseen 2.1 todistus perustuen seuraavaan konjunktiivisen hajonnan Shannonin lemmaan.

  Shannonin Lemma . Mikä tahansa Boolen funktio f (x 1, x 2, …, x m) m:stä muuttujat voidaan esittää näin:

  . (2.9)

  On huomattava, että molemmat loogisen funktion esitysmuodot (DNF ja CNF) ovat teoreettisesti samanlaisia ​​ominaisuuksiltaan: mikä tahansa looginen kaava voidaan esittää sekä DNF:ssä (paitsi identtinen nolla) että CNF:ssä (paitsi identtinen). ). Tilanteesta riippuen funktion esitys muodossa tai toisessa voi olla lyhyempi.

  Käytännössä käytetään useimmiten DNF:ää, koska tämä muoto on henkilölle tutumpi: lapsuudesta lähtien hän on tottunut lisäämään tuloja kuin kertomaan summia (jälkimmäisessä tapauksessa hänellä on intuitiivisesti halu avata sulut ja siirtyä siten DNF:ään).

  Esimerkki 4. Funktiolle f (x 1 , x 2 , x 3 ), taulukon mukaan. 10, kirjoita se SKNF:lle.

  Toisin kuin SDNF, kun käännät SCNF:ää loogisen funktion totuustaulukkoon, sinun on tarkasteltava muuttujien yhdistelmiä, joissa funktio saa arvon 0, ja luoda konjunktio vastaavista max termeistä,mutta muuttujat on otettava käänteisellä inversiolla:

  On huomattava, että on mahdotonta siirtyä suoraan funktion SDNF:stä sen SCNF:ään tai päinvastoin. Kun tällaisia ​​muunnoksia yritetään, tulokset ovat funktioita, jotka ovat päinvastaisia ​​kuin halutut. SDNF- ja SCNF-funktioiden lausekkeet voidaan saada suoraan vain sen totuustaulukosta.

  Esimerkki 5. Funktiolle f (x 1 , x 2 , x 3 ), taulukon mukaan. 10, yritä vaihtaa SDNF:stä SKNF:ään.

  Käyttämällä esimerkin 2.3 tulosta saadaan:

  Kuten näet, yleisen käännöksen alla saimme loogisen funktion SCNF:n, joka on esimerkissä 2.4 saadun funktion käänteisarvo:

  koska se sisältää kaikki maksimitermit, jotka eivät ole tarkasteltavana olevan funktion SCNF:n lausekkeessa.

  1. Käyttämällä operaatioiden ominaisuuksia (katso taulukko 9) identiteetti (), sum modulo 2 (), implikaatio (), siirrymme operaatioihin AND, OR, NOT (Boolen perusteella).

  2. Negaation ominaisuuksia ja De Morganin lakeja käyttämällä (katso taulukko 9) varmistamme, että negatiiviset operaatiot koskevat vain yksittäisiä muuttujia, eivät kokonaisia ​​lausekkeita.

  3. Käyttäen loogisten operaatioiden JA ja TAI ominaisuuksia (katso taulukko 9) saadaan normaalimuoto (DNF tai CNF).

  4. Siirry tarvittaessa täydellisiin muotoihin (SDNF tai SKNF). Esimerkiksi saadaksesi SCNF:n sinun on usein käytettävä ominaisuutta: .

  Esimerkki 6. Muunna looginen funktio SKNF:ksi

  Suorittamalla yllä olevan algoritmin vaiheet järjestyksessä, saamme:

  Absorptio-ominaisuutta käyttämällä saamme:

  Siten olemme saaneet CNF-funktion f (x 1 , x 2 , x 3 ). Saadaksesi sen SCNF, sinun on toistettava jokainen disjunktio, josta jokin muuttuja puuttuu, kahdesti tällä muuttujalla ja sen negaatiolla:

  2.2.6. Loogisten funktioiden minimoiminen

  Koska sama looginen funktio voidaan esittää h henkilökohtaisia ​​kaavoja ja löytää sitten yksinkertaisin muoto R muuli, joka määrittelee Boolen funktion, yksinkertaistaa logiikkapiiriä, joka toteuttaa Boolen funktion tiota. Vähimmäismuoto l O looginen toimintojollain perusteella voimme pitää sellaista, joka sisältää minimimäärän hauskoja superpositioita Vastaanottaja perusteen mukaan sulkeet sallien. Tehokasta on kuitenkin vaikea rakentaa l algoritmi tällaiselle minimointille minimisulkujen saamiseksi r me.

  Tarkastellaan yksinkertaisempaa minimointiongelmaa yhdistelmäpiirien synteesissä, jossa ei etsitä funktion minimaalista sulkumuotoa, vaan sen minimaalista DNF:ää. Tähän tehtävään on olemassa yksinkertaisia, tehokkaita algoritmeja.

  Quinen menetelmä

  Minimoitava funktio on esitetty SDNF:ssä ja kaikki mahdolliset epätäydelliset liimaustoimenpiteet sovelletaan siihen

  , (2.10)

  ja sitten imeytyminen

  , (2.11)

  ja tätä vaiheparia sovelletaan toistuvasti. Siten on mahdollista alentaa termien järjestystä. Tätä menettelyä toistetaan, kunnes jäljellä ei ole yhtään termiä, joka voidaan liittää mihinkään muuhun termiin.

  Huomaa, että yhtälön (2.10) vasen puoli voidaan minimoida välittömästi yksinkertaisemmalla ja selkeämmällä tavalla:

  Tämä menetelmä on huono, koska tällaisella suoralla minimoitumisella konjunktiivitermit joko häviävät, vaikka on vielä mahdollisia tapauksia, joissa niitä käytetään liimaamiseen ja absorptioon muiden termien kanssa.

  On huomattava, että Quinen menetelmä on melko työvoimavaltainen, joten virheiden todennäköisyys muutosten aikana on melko korkea. Mutta sen etuna on, että teoriassa sitä voidaan käyttää mihin tahansa argumenttien määrään ja muuttujien määrän kasvaessa muunnokset yksinkertaistuvat.

  Karnaughin karttamenetelmä

  Carnot-karttojen (taulukoiden) menetelmä on visuaalisempi, vähemmän työvoimavaltainen ja luotettava tapa minimoida loogisia funktioita, mutta sen käyttö rajoittuu käytännössä 3-4 muuttujan funktioihin, maksimi 5-6 muuttujaan.

  Carnot kartta Tämä on kaksiulotteinen taulukkomuoto, joka esittää Boolen funktion totuustaulukon, jonka avulla voit helposti löytää loogisten funktioiden vähimmäis-DNF:t graafisessa visuaalisessa muodossa. Jokainen taulukon solu liittyy minimoitavan funktion SDNF-mintermiin ja siten, että taulukon mitkä tahansa symmetria-akselit vastaavat vyöhykkeitä, jotka ovat keskenään käänteisiä jonkin muuttujan suhteen. Tämä solujen järjestely taulukossa helpottaa SDNF:n tarttumistermien määrittämistä (poikkeavat vain yhden muuttujan inversiomerkistä): ne sijaitsevat taulukossa symmetrisesti.

  Totuustaulukot ja Carnaugh-kartat kahden kaistan JA- ja TAI-funktioille e Muuttujat on esitetty kuvassa. 8. Kortin jokaiseen soluun kirjoitetaan arvo A Tätä solua vastaavan argumenttiarvojen joukon funktion arvo N toveri

  A) JA b) TAI

  Riisi. 8. Esimerkki Karnaugh-kartoista kahden muuttujan funktioille

  Karnaughin kartassa And-funktiolle on vain yksi 1, joten sitä ei voi liimata mihinkään. Minimifunktion lauseke sisältää vain tätä 1 vastaavan termin:

  f = x y.

  TAI-funktion Carnot-kartassa on jo kolme ykköstä ja voit tehdä kaksi tarraparia, joista 1 vastaa termiä xy , käytetään kahdesti. Minimaalisen funktion lausekkeessa sinun on kirjoitettava yhteen liimattavien parien ehdot jättäen niihin kaikki muuttujat, jotka eivät muutu tälle parille, ja poistamalla muuttujat, jotka muuttavat arvoaan. Vaakasuoraan liimaukseen saamme x , ja pystysuoralle y , tuloksena saamme lausekkeen

  f = x + y.

  Kuvassa 9 näyttää kahden kolmen muuttujan funktion totuustaulukot ( A ) ja heidän Carnot-kartat ( b ja c). Funktio f 2 eroaa ensimmäisestä siinä, että sitä ei ole määritelty kolmelle muuttujajoukolle (taulukossa tämä on merkitty viivalla).

  Vähimmäis-DNF-funktiota määritettäessä käytetään seuraavia sääntöjä. Kaikki solut, jotka sisältävät numeron 1, yhdistetään suljetuiksi suorakaiteen muotoisiksi alueiksi, joita kutsutaan k-kuutiot, missä k = log 2 K, K määrä 1 suorakaiteen muotoisella alueella. Tässä tapauksessa jokaisen alueen tulee olla suorakulmio, jonka solujen lukumäärä on 2 k, jossa k = 0, 1, 2, 3, …. Jos k = 1 suorakulmio kutsutaan yksi on kuutio ja sisältää 2 1 = 2 yksikköä; k = 2 suorakulmio sisältää 2 2 = 4 yksikköä ja sitä kutsutaan kahden kuution; kun k = 3 alue 2 3:sta = 8 yksikköä kutsutaan kolmen kuution ; jne. Voidaan kutsua yksiköitä, joita ei voida yhdistää suorakulmioiksi nollakuutiot , jotka sisältävät vain yhden yksikön (2 0 = 1). Kuten voidaan nähdä, jopa k alueet voivat olla neliön muotoisia (mutta ei välttämättä), ja jos ne ovat parittomia k vain suorakulmioita.

  						b c

  Riisi. 9. Esimerkki Karnaugh-kartoista kolmen muuttujan funktioille

  Nämä alueet voivat mennä päällekkäin, eli samat solut voivat päästä eri alueille. Sitten minimaalinen DNF-funktio kirjoitetaan kaikkien vastaavien konjunktiivitermien disjunktioksi k - kuutiot.

  Jokainen Karnaugh-kartan osoitetuista alueista on esitetty minimaalisessa DNF:ssä konjunktiolla, jonka argumenttien määrä on k vähemmän kuin funktion argumenttien kokonaismäärä m eli tämä luku on yhtä suuri mk . Jokainen minimaalisen DNF:n konjunktio koostuu vain niistä argumenteista, joilla vastaavalle kartan alueelle on arvoja joko ilman inversioita tai vain inversioiden kanssa, eli ne eivät muuta niiden merkitystä.

  Siten karttasolujen peitossa suljetuilla alueilla tulee pyrkiä varmistamaan, että alueita on mahdollisimman vähän ja jokainen alue sisältää mahdollisimman monta solua, koska tällöin termien määrä minimaalisessa DNF:ssä on minimaalinen ja argumenttien määrä vastaavassa konjunktiossa on minimaalinen.

  Kuvan Karnaugh-kartan mukaiselle funktiolle. 9, b löydämme

  koska ylemmän suljetun alueen muuttujat x 1 ja x 2 niillä on arvot ilman inversioita alemmille x 1 merkitystä inversiolla ja x 3 ilman inversiota.

  Määrittämättömät arvot kartalla kuvassa. 9, V voidaan määritellä tarkemmin korvaamalla se nollalla tai yhdellä. Tälle funktiolle on selvää, että on kannattavampaa korvata molemmat määrittelemättömät arvot 1:llä. Tässä tapauksessa muodostuu kaksi aluetta, jotka ovat erityyppisiä 2-kuutioita. Sitten DNF-minimifunktion lauseke on seuraava:

  Suljettuja alueita rakennettaessa Carnot-kartta saa taittaa sylinteriksi sekä vaaka- että pystysuunnassa. R tikaalikirveitä vastakkaisten kasvojen liitolla R sinä, eli yksiköt, jotka sijaitsevat Carnotin symmetriakartan reunoilla h mutta voidaan myös yhdistää.

  Carnaugh-kartat voidaan piirtää eri tavoin (kuva 10).

  									x 2 x 3

  a b

  Riisi. 10. Erilaisia ​​tapoja kuvata Carnaughin karttoja
  3 muuttujan funktiolle

  Mutta kätevimmät vaihtoehdot Karnaugh-kartoille 2-4 muuttujan funktioille ovat ne, jotka on esitetty kuvassa. 11 taulukkoa, koska ne näkyvät jokaiselle solulle A Meillä on kaikki muuttujat suorassa tai käänteisessä muodossa.

  a b

  Riisi. yksitoista. Kätevin kuva Carnaugh-kartoista
  funktioille 3 ( a) ja 4 (b) muuttujat

  5 ja 6 muuttujan funktioille kuvassa 1 esitetty menetelmä. 10, V .

  Riisi. 12. Kuva Karnaughin kartasta 5 muuttujan funktiolle

  Riisi. 13. Kuva Karnaughin kartasta 6 muuttujan funktiolle

  Muita samankaltaisia ​​teoksia, jotka saattavat kiinnostaa sinua.vshm>
  9020.		KAKSIAISUUDEN PERIAATE. BOOLIEN FUNKTIOIEN LAAJENTAMINEN MUUTTUJIHIN. TÄYDELLINEN DISJUNKTIIVINEN JA KONJUNKTIIVINEN NORMAALIMUODOT	96,34 kt
  	Tämä lause on luonteeltaan rakentava, koska se sallii jokaisen funktion rakentaa kaavan, joka toteuttaa sen täydellisen d.n:n muodossa. f. Tätä varten merkitsemme kunkin funktion totuustaulukossa kaikki rivit, joilla
  6490.		Loogisten funktioiden kuvaus ja minimointi	187,21 kt
  	Suhde funktion argumenttien ja sen arvojen välillä ilmaistaan ​​sanallisessa muodossa. Esimerkki: Kolmen argumentin funktio saa arvon, kun kaksi tai useampi funktion argumentti on yhtä suuri. Koostuu totuustaulukon muodostamisesta, joka sisältää funktioarvot kaikille argumenttiarvojoukoille. Tässä esimerkissä saamme totuustaulukkoa käyttämällä seuraavan merkinnän muodossa DNF...
  6707.		Relaatiotietokantojen suunnittelu. Suunnitteluongelmat klassisessa lähestymistavassa. Normalisoinnin periaatteet, normaalimuodot	70,48 kt
  	Mikä on relaatiotietokantaprojekti? Tämä on joukko toisiinsa liittyviä suhteita, joissa määritetään suhteiden ensisijaiset avaimet ja määritetään joitain suhteiden lisäominaisuuksia, jotka liittyvät eheyden säilyttämisen periaatteisiin? Siksi tietokannan suunnittelun on oltava erittäin tarkka ja varmennettu. Itse asiassa tietokantaprojekti on perusta tulevalle ohjelmistopaketille, jota käytetään melko pitkään ja monien käyttäjien keskuudessa.
  4849.		Tilatoimintojen toteutusmuodot ja menetelmät	197,3 kt
  	Termillä ”toiminto” ei ole läheskään samaa merkitystä kotimaisessa ja ulkomaisessa tieteellisessä kirjallisuudessa. Filosofisesti ja yleissosiologisesti sitä pidetään "esineen ominaisuuksien ulkoisena ilmentymänä tietyssä suhdejärjestelmässä"; joukkona yksilöiden tai elinten tavallisia tai erityisiä toimia
  17873.		Loogisen UUD:n muodostaminen 3. luokan oppilaille	846,71 kt
  	Psykologiset ja pedagogiset näkökohdat loogisten universaalien toimien muodostumisongelmassa alakouluikäisillä Menetelmät loogisten UUD:iden muodostumisen arviointiin. Yleisen koulutusjärjestelmän yleisen koulutustoiminnan kehittämiskonseptin kehittäminen vastaa uusiin yhteiskunnallisiin tarpeisiin. Nykyaikaisen koulutusjärjestelmän tärkein tehtävä on UUD:n yleismaailmallisen koulutustoiminnan muodostaminen. Yleismaailmallisen koulutustoiminnan muodostuminen on avain kouluvaikeuksien ehkäisyyn.
  2638.		Loogisten yhteyksien tekninen toteutus automaattisissa estojärjestelmissä	1,04 Mt
  	Loogisten kytkentöjen tekninen toteutus automaattisissa estojärjestelmissä Kolmi- ja nelinumeroisten akkujen ohjausalgoritmien tekninen toteutus voidaan saavuttaa käyttämällä relekosketinta ja kontaktittomia diskreettejä ja integroituja logiikkaelementtejä...
  10203.		RISKIKESKEISEN LÄHESTYMISTAVAN KÄSITTEEN SOVELTAMINEN HÄTÄTILANTEEN ILMOITUKSEN JA KEHITTYMISEN RAKENTEELLISTEN JA LOOGISTEN MALLIEN RAKENTAMISEEN	70,8 kt
  	Yleinen riskianalyysi Tuotantoympäristö on kyllästynyt tehokkailla teknologisilla järjestelmillä ja teknologioilla, jotka tekevät ihmisen työstä tuottavaa ja fyysisesti vähemmän vaikeaa, mutta vaarallisempaa. Riskille on ominaista vaarallisen tilanteen alkamisen odottamattomuus ja äkillisyys. Joka päivä kohtaamme lukuisia riskejä, mutta suurin osa niistä on edelleen mahdollisia.
  11576.		Liiketoimien käsite, tyypit ja muodot. Vaaditun liiketoimimuodon noudattamatta jättämisen seuraukset	49,82 kt
  	Tapahtuman tunnistaminen kelpaamattomiksi. Kurssityön sovellettu arvo on transaktion käsitteen yksinkertaistamisessa eli sen julkisessa esittämisessä helpommin saavutettavissa olevassa muodossa.
  6213.		Funktion approksimaatio	3,08 Mt
  	Ensimmäinen koostuu tietyn analyyttisesti tai taulukkomuodossa määritellyn funktion korvaamisesta toisella funktiolla, joka on lähellä alkuperäistä mutta yksinkertaisempaa ja laskelmien kannalta kätevämpää. Esimerkiksi korvaamalla funktion polynomilla voit saada yksinkertaisia ​​kaavoja numeerista integrointia ja differentiointia varten; Taulukon korvaaminen likimääräisellä funktiolla mahdollistaa arvojen saamisen sen välipisteissä. Toinen ongelma syntyy myös: tietyn segmentin funktion palauttaminen tälle segmentille annetuista funktion arvoista erillisessä pistejoukossa. Vastaus tähän kysymykseen...
  14058.		Valtion toimintojen kehitys	29,99 kt
  	Venäjän valtion on oikeudellisena ilmiönä ennen kaikkea varmistettava valtion tarkoituksen toteutuminen sekä sen tärkeimmät perustuslailliset ominaispiirteet demokraattisena liittovaltion oikeudellisena sosiaalisena maallisena valtiona, jolla on tasavaltainen hallintomuoto. Valtion päätarkoitus määräytyy art.