Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI MATEMATIKA U INFORMATICI

Logička funkcija KNF

Brojni sistemi, Bulova algebra, binarna aritmetika itd.

Logička funkcija KNF

Postod Srdjan01 » Četvrtak, 26. Novembar 2020, 17:02

Pozdrav, evo imam još jedan zadatak u kojem je zadana logička funkcija, pa imam nekoliko pitanja.
Zadatak glasi:
Zadana je logička funkcija
[dispmath]F(A,B,C,D)=(A+B+C)(A+C+D)(AB+D)[/dispmath] [inlmath]a)[/inlmath] Odrediti algebarski izraz za logičku funkciju u obliku potpune KNF.
[inlmath]b)[/inlmath] Minimizovati funkciju [inlmath]F[/inlmath] primjenom Karnoove metode.
[inlmath]c)[/inlmath] Realizovati funkciju dobijenu pod [inlmath]b)[/inlmath] primjenom minimalnog broja NI logičkih kola, sa dovoljnim brojem ulaza

I ja sam probao:
[inlmath]a)[/inlmath]
Kako bih našao potpunu KNF, ja odredim DNF, pa napravim tablicu i iz tablice iščitam potpuni oblik KNF.
[dispmath]F(A,B,C,D)=(A+B+C)(A+C+D)(AB+D)=\\
=(A+AC+AD+AB+BC+BD+AC+C+CD)(AB+D)=\\
=(A+AD+AC+AB+BC+BD+C+CD)(AB+D)=\\
=(A(1+D+C+B)+C(1+B+D)+BD)(AB+D)=\\
=(A+C+BD)(AB+D)=\\
=AB+AD+ABC+CD+ABD+BD=\\
=AB(C+1+D)+AD+CD+BD=AB+AD+CD+BD[/dispmath] I sada sam ja ovu funkciju koja je data u zadatku malo preoblikovao, pa je pitanje da li to smijem da uradim? Kako bih našao potpunu DNF, a kasnije KNF nastavljam dalje:
[dispmath]AB(C+\overline{C})(D+\overline{D})+A(B+\overline{B})(C+\overline{C})D+(A+\overline{A})(B+\overline{B})CD+(A+\overline{A})B(C+\overline{C})D=\\
=ABCD+AB\overline{C}\overline{D}+ABCD+AB\overline{C}D+A\overline{B}CD+A\overline{B}\overline{C}D+ABCD+A\overline{B}CD+\overline{A}BCD+\\
+\overline{A}\overline{B}CD+ABCD+AB\overline{C}D+\overline{A}BCD+\overline{A}B\overline{C}D=\sum(3,5,7,9,11,12,13,15)[/dispmath] Sada postavim u tabelu, jedinice na ove vrijednosti, a KNF očitam tako što gledam nule, pa dobijam da je KNF:
[dispmath](A+B+C+D)(A+B+C+\overline{D})(A+B+\overline{C}+D)(A+\overline{B}+C+D)\cdot\\
\cdot(A+\overline{B}+\overline{C}+D)(\overline{A}+B+C+D)(\overline{A}+B+\overline{C}+D)(\overline{A}+\overline{B}+\overline{C}+D)[/dispmath] E sada, pod [inlmath]b)[/inlmath] kaže minimizovati funkciju [inlmath]F[/inlmath] primjenom Karnoove metode. Ne razumijem da li trebam minimizovati DNF ili KNF, pa da dobijem MDF ili MKF, ili nešto treće?
[inlmath]c)[/inlmath]
Ja sam pretpostavio, da treba minimizovati KNF, pa dobijamo da je:
[dispmath]F=(B+D)(A+D)(\overline{C}+D)(A+B+C)[/dispmath] I sada trebam ovakvu funkciju realizovati preko minimalnog broja NI logičkih kola.
Ako neko može da mi odgovori na ova pitanja koja sam postavio, i da kaže svoje mišljenje da li se ovako može uraditi zadatak?
Unaprijed Hvala! :)
Korisnikov avatar
 
Postovi: 86
Zahvalio se: 31 puta
Pohvaljen: 57 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+
  • +1

Re: Logička funkcija KNF

Postod Daniel » Petak, 27. Novembar 2020, 22:55

Srdjan01 je napisao:I sada sam ja ovu funkciju koja je data u zadatku malo preoblikovao, pa je pitanje da li to smijem da uradim? Kako bih našao potpunu DNF, a kasnije KNF nastavljam dalje:
[dispmath]AB(C+\overline{C})(D+\overline{D})+A(B+\overline{B})(C+\overline{C})D+(A+\overline{A})(B+\overline{B})CD+(A+\overline{A})B(C+\overline{C})D=\\
=ABCD+AB\overline{C}\overline{D}+ABCD+AB\overline{C}D+A\overline{B}CD+A\overline{B}\overline{C}D+ABCD+A\overline{B}CD+\overline{A}BCD+\\
+\overline{A}\overline{B}CD+ABCD+AB\overline{C}D+\overline{A}BCD+\overline{A}B\overline{C}D=\sum(3,5,7,9,11,12,13,15)[/dispmath]

Nepotrebno mnogo posla, ali u principu nije pogrešno. Jedino što ovde imaš grešku, izostavio si [inlmath]ABC\overline D[/inlmath] zbog čega ti je i iz rezultata izostalo [inlmath]14[/inlmath].
Samim tim si u potpunoj KNF dobio jedan član viška (obeležen crveno):
Srdjan01 je napisao:Sada postavim u tabelu, jedinice na ove vrijednosti, a KNF očitam tako što gledam nule, pa dobijam da je KNF:
[dispmath](A+B+C+D)(A+B+C+\overline{D})(A+B+\overline{C}+D)(A+\overline{B}+C+D)\cdot\\
\cdot(A+\overline{B}+\overline{C}+D)(\overline{A}+B+C+D)(\overline{A}+B+\overline{C}+D){\color{red}(\overline{A}+\overline{B}+\overline{C}+D)}[/dispmath]

Možeš i proveriti – za [inlmath]A=1[/inlmath], [inlmath]B=1[/inlmath], [inlmath]C=1[/inlmath], [inlmath]D=0[/inlmath] taj član bi bio [inlmath]0[/inlmath] pa bi i ceo izraz bio [inlmath]0[/inlmath], dok bi zadata funkcija za tu kombinaciju imala vrednost [inlmath]1[/inlmath].

Ali, kao što rekoh, previše posla. Radi dobijanja potpune KNF, mogao si jednostavno napraviti tabelu za početni izraz, i tamo gde su nule odmah uneti te kombinacije promenljivih u potpunu KNF. Drugi način, bez tabele, bio bi da početni izraz transformišeš:
[dispmath]\begin{align}
F(A,B,C,D)&=(A+B+C)(A+C+D)(AB+D)\\
&=(A+B+C+D\overline D)(A+B\overline B+C+D)(A+D)(B+D)\\
&=(A+B+C+D\overline D)(A+B\overline B+C+D)(A+B\overline B+C\overline C+D)(A\overline A+B+C\overline C+D)
\end{align}[/dispmath] I sada svaki od ovih članova rastaviš koristeći distributivnost logičkog sabiranja u odnosu na logičko množenje (ovde to važi, analogno distributivnosti disjunkcije u odnosu na konjunkciju, za razliku od klasične algebre u kojoj ne važi distributivnost sabiranja u odnosu na množenje). Npr. [inlmath](A+B+C+D\overline D)[/inlmath] bi se rastavilo na [inlmath](A+B+C+D)(A+B+C+\overline D)[/inlmath], zatim bi se [inlmath](A+B\overline B+C+D)[/inlmath] rastavilo na [inlmath](A+B+C+D)(A+\overline B+C+D)[/inlmath] itd. Neki članovi će se primenom ovog postupka pojaviti više od jednog puta, njih naravno skratiš.
Možeš uočiti da je ovaj postupak potpuno analogan postupku traženja potpune DNF, s tim da gde ti je tamo bilo množenje ovde ti je sabiranje i obratno, gde su ti tamo bile nule ovde su ti jedinice i obratno. Npr. kod traženja potpune DNF izraz [inlmath]ABD[/inlmath] bi proširio kao [inlmath]AB(C+\overline C)D=ABCD+AB\overline CD[/inlmath], a ovde bi izraz [inlmath](A+B+D)[/inlmath] proširio tako da bude [inlmath](A+B+C\overline C+D)=(A+B+C+D)(A+B+\overline C+D)[/inlmath].

Srdjan01 je napisao:E sada, pod [inlmath]b)[/inlmath] kaže minimizovati funkciju [inlmath]F[/inlmath] primjenom Karnoove metode. Ne razumijem da li trebam minimizovati DNF ili KNF, pa da dobijem MDF ili MKF, ili nešto treće?
[inlmath]c)[/inlmath]

Po meni, trebalo je to da bude precizirano. Ali, budući da se [inlmath]a)[/inlmath] odnosilo na KNF, logično bi bilo da treba minimizovati KNF.

Srdjan01 je napisao:Ja sam pretpostavio, da treba minimizovati KNF, pa dobijamo da je:
[dispmath]F=(B+D)(A+D){\color{red}(\overline{C}+D)}(A+B+C)[/dispmath]

Negde imaš grešku, crveni član ti je višak. Ispalo bi da za [inlmath]C=1[/inlmath] i [inlmath]D=0[/inlmath] funkcija [inlmath]F[/inlmath] mora imati vrednost [inlmath]0[/inlmath], međutim ako [inlmath]C=1[/inlmath] i [inlmath]D=0[/inlmath] uvrstimo u početni izraz za funkciju videćemo da ona ipak može biti [inlmath]1[/inlmath] (onda kada je [inlmath]AB=11[/inlmath]).
I uopšte kad radiš ove zadatke, preporučljivo je da napraviš tabelu i za početni izraz za funkciju i za ove izraze koje dobiješ, i proveriš da li se sve vrednosti u tabeli poklapaju.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 8666
Lokacija: Beograd
Zahvalio se: 4723 puta
Pohvaljen: 4626 puta


Povratak na MATEMATIKA U INFORMATICI

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 1 gost


Index stranicaTimObriši sve kolačiće boarda
Danas je Ponedeljak, 17. Maj 2021, 21:02 • Sva vremena su u UTC + 1 sat [ DST ]
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs