Projektovanje

logičkih

sistema

Bulova algebra i De Morganovi

zakoni. Projektovanje logičkih

kola.

Projektovanje logičkih sistema 3 Coypright: Lejla Banjanović-Mehmedović

Prof.dr.Lejla Banjanović-Mehmedović

Sadržaj izlaganja

Projektovanje logičkih sistema 3 Coypright: Lejla Banjanović-Mehmedović

Bulova algebra i De Morganovi

zakoni.

Principi projektovanja logičkih kola

Primjeri sinteze logičkih kola

Bulova algebra

• Sve računarske operacije koje se izvode samo na ciframa 0 i 1 i

koje daju te iste vrijednosti nazivaju se logičke operacije.

• Logičke operacije:

• negacija, konjukcija i disjunkcija.

• Joše neke logičke operacije:

• negacija konjukcije (Shefferova operacija)

• negacija disjunkcije (Pierceova operacija ili operacija Lukasiewicza)

• ekskluzivna disjunkcija

• Grana matematike, koja proučava operacije konjukcije, disjunkcije

i negacije i pravila rada sa njima – Boolova algebra (Logička

algebra,prekidačka algebra)

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Pravila logičke algebre

• Aksiomi logičke algebre – određeni broj pravila se

proglašava elementarnim činjenicama logičke

algebre, koje se prihvataju bez dokaza i na kojima

se zasnivaju sva druga pravila i kompletna logička

algebra.

• Izbor aksioma nije jednoznačan!

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Logički izrazi i funkcije

• Logička funkcija je logički izraz koji opisuje izlaz kao

funkciju ulaza

L(x) = x

• x –ulazna varijabla.

• Primjer:

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Univerzalne logičke operacije

• Svaka logička funkcija se može izraziti preko operacija

konjukcije, disjunkcije i negacije.

• Dovoljne negacija i konjukcija, jer se i disjunkcija može

izraziti preko ove dvije operacije:

• Dovoljne negacija i disjunkcija, jer vrijedi formula:

• Svaka logička funkcija se može izraziti preko Shefferove

operacije (negacija konjukcije) ili alternativno preko

Pierceove funkcije (negacija disjunkcije); nazivaju se

univerzalne logičke operacije.

• NAND i NOR –univerzalna logička kola

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-MehmedovićX Y XY =XY X Y= 

Bulove operacije

• Bulova operacija

sabiranja korespondira

logičkom kolu “OR”,

prekidači u paralelnoj

vezi.

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Bulove operacije

• Bulova operacija

množenja korespondira

logičkom kolu “AND”,

prekidači u serijskoj

vezi.

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Bulove operacije

• Bulova operacija

komplementa korespondira

logičkom kolu “NOT”.

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Bazni Bulovi algebarski identiteti 1/2

• Aditivni:

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Bazni Bulovi algebarski identiteti 2/2

• Multiplikacioni:

• Dvojni komplement:

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Bazna svojstva Bulove algebre 1/5

• Svojstvo komutativnosti

aditivnosti

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

 Aditivna: Multiplikaciona:

Bazna svojstva Bulove algebre 2/5

• Komunitativno svojstvo

multiplikacije

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

 Aditivna: Multiplikaciona:

Bazna svojstva Bulove algebre 3/5

• Asocijativno svojstvo

aditivnosti

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

 Aditivna: Multiplikaciona:

Bazna svojstva Bulove algebre 4/5

• Asocijativno svojstvo

multiplikacije

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

 Aditivna: Multiplikaciona:

Bazna svojstva Bulove algebre 5/5

• Svojstvo distributivnosti

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

 Aditivna: Multiplikaciona:

Bulova pravila pojednostavljenja 1/3

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Bulova pravila pojednostavljenja 2/3

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Bulova pravila pojednostavljenja 3/3

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

EX-OR

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Primjer: Sistem za spaljivanje

toksičnih otpada

• Redudantni sistem:

• Sa više senzora

• Najmanje 2 senzora

detektuju vatru,

otvoreni ventil;

• 1 senzor –npr.

neispravan senzor

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Tabela istine za analizirani sistem

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Logički izrazi i logičke funkcije se često predstavljaju sa tzv. tabelom istine.

Ove tabele prikazuju vrijednost izraza odnosno funkcije za sve moguće kombinacije

vrijednosti promjenljivih koje se u njima pojavljuju.

Logički funkcija = Suma proizvoda svih ulaznih varijabli ili njihovih negacija (tzv.

mintermi) za koje je izraz u tabeli istinitosti 1.

Primjer pojednostavljenja logičke

funkcije

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Primjer: Realizacija logičke funkcije

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Ekvivalentne transformacije logičkih

izraza

• Za dva logička izraza se kaže da su ekvivalentni

ukoliko uzimaju iste vrijednosti za ma kako izabrane

vrijednosti promjenljivih koje se u njima javljaju.

• Dva ekvivalentna logička izraza uvijek se mogu svesti

jedan na drugi primjenom konačno mnogo

transformacija izraženih pravilima logičke algebre.

• De Morganove teoreme - izrazito značajne!

• Cilj: Pronalaženje najjednostavnije logičke funkcije

koja je ekvivalentna polaznoj logičkoj funkciji -

minimizacija logičke funkcije!

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Realizacija logičkih kola pomoću NI i

NILI kola

• Svako logičko kolo se može realizovati pomoću NI ili

NILI logičkih kola, što je od praktičnog značaja pri

realizaciji integralnih digitalnih kola.

• Problemi realizacije Bulovih funkcija pomoću

isključivo NI ili NILI kola (homogenizacija kola) mogu

se rješiti i analitičkim postupkom, primjenom De

Morganovih pravila.

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Realizacija logičkih kola pomoću NI i

NILI kola

• Nakon uvođenja negacija u polazni izraz (parcijalno)

primenjujemo De Morganove teoreme tako da:

• eliminišemo zbirove, prevodeći ih u proizvode negiranih

varijabli, kod realizacije pomoću NI kola.

• eliminišemo proizvode, prevodeći ih u zbirove negiranih

varijabli, kod realizacije pomoću NILI kola.

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

DeMorganova pravila

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Primjer korištenja pravila: Sistem

rezervoara

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Peikazati sa NI kolima

Projektovanje logičkih kola

Projektovanje logičkih sistema 3 Coypright: Lejla Banjanović-Mehmedović

Projektovanje logičkih

kola

• Logička sinteza i optimizacija

• Logička sinteza - generisanje skupa

logičkih izraza koje opisuju logičke

funkcije koje su potrebne za

realizaciju kola.

• Određenim metodama možemo

dobiti optimalni dizajn

• Fizički dizajn

• Implementacija funkcionalnosti

logičkog kola na zadanom čipu

(pozicioniranje specifičnih

logičkih elemenata na ciljani čip,

savremeni trendovi...)

Projektovanje logičkih sistema 3 Coypright: Lejla Banjanović-Mehmedović

Projektovanje logičkih kola

• Dizajn:

• Computer aided design (CAD) software tools –sadrži alate za

šematski dizajn, logičku sintezu i optimizaciju, simulaciju i fizički

dizajn.

• Problem sa složenijim logičkim kolima

• Korištenjem industry-standard design language HDL: Verilog,

VHDL

• HDL (hardverski opisni jezik) sličan kompjuterskom

programskom jeziku, umjesto za opis programa koristi se za

opis hardverske strukture.

Projektovanje logičkih sistema 3 Coypright: Lejla Banjanović-Mehmedović

Projektovanje fiksnih logičkih kola

Projektovanje logičkih sistema 3 Coypright: Lejla Banjanović-Mehmedović

Primjer projektovanja

sistema korištenjem HDL

(Verilog)

module GenTakta(clk,state);

input clk;

output reg state;

reg[25:0] counter;

always@(posedge clk)

begin

counter<=counter+1'b1;

if(counter>=26'b10000101100000111011000000)

state<=1;

else

state<=0;

end

Projektovanje logičkih sistema 3 Coypright: Lejla Banjanović-Mehmedović

Analiza i sinteza logičkih kola

Projektovanje logičkih sistema 3 Coypright: Lejla Banjanović-Mehmedović

Proces određivanja

funkcije koju obavlja

postojeća mreža – analiza

(dosadašnji primjeri).

Obrnut zadatak,

projektovanje nove mreže

koja implementira željeno

funkcionalno ponašanje –

sinteza (ono što nas čeka).

Principi projektovanja logičkih

kola

• Specifikacija problema (razumjeti problem - specificirati šta uređaj traba da radi)

• Identifikacija potrebnih ulaznih i izlaznih varijabli

• Funkcionalna veza ulaznih i izlaznih varijabli

• Tabele istinitosti (SOP, POS, Minterm/Maxterm izrazi)

• Sinteza i optimizacija (sinteza- transformiše dizajnerske zahtjeve u logički dizajn)

• Booleova algebra, Karnoughove mape

• Implementacija logičkih izraza korištenjem logičkih kola (diskretna logička kola)

• Simulacija, fizički dizajn (transformiše logički graf u layout za fabrikaciju (CAD

alat; hardverski jezik, npr. Verilog)

Projektovanje logičkih sistema 3 Coypright: Lejla Banjanović-Mehmedović

Sinteza logičkih kola

• Zadatak sinteze logičkih kola se rješava u četiri etape:

1. Formulisanje tablice istinitosti na osnovu zadate namjene kola

2. Generisanje odgovarajuće Bulove funkcije

3. Uprošćavanje ili minimizacija dobijene Bulove funkcije

4. Realizacija minimizovane Bulove funkcije pomoću raspoloživih logičkih kola

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Vremenski dijagrami korisni za indikaciju funkcionalnog

ponašanja logičkih krugova.

CD

AB 00 01 11 10

00 1

01 1 1

11 1 1

10 X X X X

Kreiranje tabela

istinitosti

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Konjuktivne i disjunktivne forme

• Literal – bilo koja logička promjenljiva ili njena negacija.

• Logički izraz koji je literal ili konjukcija više literala u kojoj se ni

jedna promjenljiva ne javlja više od jednaput, naziva se

elementarna konjukcija.

• Logički izraz koji je literal ili disjunkcija više literala u kojoj se ni

jedna promjenljiva ne javlja više od jednaput, naziva se

elementarna disjunkcija.

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-MehmedovićABDA B D 

Disjunktivne forme

• Disjunktivna forma - logički izraz koji ima oblik disjunkcije više

prostijih izraza (članova).

• Disjunktivna normalna forma (DNF) ili suma proizvoda (SOP)

– svaki od izraza je elementarna konjukcija .

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-MehmedovićA BC ABC A BC AB 

Konjuktivne forme

• Konjuktivna forma - logički izraz koji ima oblik konjukcije više

prostijih izraza (članova)

• Konjuktivna normalna forma (KNF) ili proizvod suma (POS) –

svaki od izraza je elementarna disjunkcija

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović( )( )A B C A B C  ( )ABC B C

Konjuktivne i disjunktivne forme

• Za funkciju n varijabli, forma proizvoda, u kojoj se svaka od n

varijabli pojavljuje jednom naziva se minterma.

• Savršena disjunktivna normalna forma (SDNF) - disjunktivna

normalna forma mintermi

• Za funkciju n varijabli, forma sume, u kojoj se svaka od n

varijabli pojavljuje jednom naziva se maksterma.

• Savršena konjuktivna normalna forma (SKNF) - konjuktivna

normalna forma makstermi

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-MehmedovićY ABC ABC ABC=  ( )( )( )Y A B C A B C A B C=      

Formiranje logičkog izraza iz tabele

istinitosti

• SDNF - disjunkcija svih mintermi, za koje

je izraz u tabeli istinitosti 1.

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

A B C Y

0 0 0 1

0 0 1 1

0 1 0 0

0 1 1 1

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 1..( )Y ABC ABC ABC ABC ABC SDNF=    

Formiranje logičkog izraza iz tabele

istinitosti

• SKNF - konjukcija svih makstermi, za koje

je izraz u tabeli istinitosti 0.

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

A B C Y

0 0 0 1

0 0 1 1

0 1 0 0

0 1 1 1

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 1( )( )( )..( )Y A B C A B C A B C SKNF=      

Primjeri

sinteze

logičkih kola

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Primjer 1: Kontrola rasvjete

• Velika prostorija ima troje vrata i prekidač u blizini vrata za

kontrolu rasvjete u sobi. Moguće je uključiti ili isključiti rasvjetu,

promjenom stanja svakog od prekidača (tri ulazne varijable

(x1,x2,x3)).

• Pretpostavimo da je svjetlo isključeno, ako su svi prekidači otvoreni

(isključeni). Zatvaranje bilo kojeg od prekidača, će upaliti svjetlo.

Potom uključenje drugog prekidača će isključiti rasvjetu.

• Rasvjeta će biti uključena ako je tačno jedan prekidač uključen

(zatvoren) i isključena ako su dva (ili nijedan) prekidač uključen.

Ako je rasvjeta isključena, kada su dva prekidača zatvorena, mora

biti moguće je uključiti, pritiskom na treći prekidač.

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Primjer 1: Kontrola rasvjete

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Primjer 1: Kontrola rasvjete

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Primjer 2: Komparator signala

• Neka je potrebno projektovati logičko kolo koje

ima funkciju komparatora dva signala x i y.

Izlazni signal treba da bude:

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Primjer 2: Komparator signala

• NI funkcija

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

SOP:

Primjer 3: Pumpni sistem

• Rad svake od četiri pumpi se kontroliše pomoću

električnog signala koji ima napon od 5V, ako je

pumpa u radu, a nulti napon ako je u kvaru.

• Neophodno je da bar dvije od četiri pumpe budu

stalno u radu, a u protivnom bi trebalo aktivirati

zvučni alarm. Alarmni uređaj se aktivira

naponskim signalom od 5V.

• Projektovati logičko kolo, sastavljeno od NILI kola,

koje će u slučaju potrebe aktivirati alarmni

uređaj.

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Primjer 3: Pumpni sistem

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Funkcija alarma ima logičku

vrijednost 1 (alarmantna situacija)

ako nijedna ili najviše jedna od 4

promenljivih ima jediničnu vrijednost

(pumpa u radu), dok su ostale

jednake nuli.

Primjer 3: Pumpni sistem

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

 Primjenom De Morganovih pravila, ekvivalentna izraz se bazira

na NILI kolima. Za realizaciju je neophodno ukupno 14 NILI kola

(8+6 invertora, označenih kružićima)

Primjer 4: Sistem

rezervoara

• Za održavanje nivoa (dopunjavanjem) u 4

rezervoara (A,B,C,D), na raspolaganju su 2

pumpe, P1 i P2, što je dovoljno u

normalnom režimu. Kada u nekom

rezervoaru nivo padne ispod dozvoljenog,

automatski se generiše signal koji uključuje

pumpu radi korekcije nivoa.

• Pumpu P2 može da “pozove” svaki od 4

rezervoara a pumpu P1 samo rezervoari C i

D.

• Alarmantna situacija nastaje kada neki od

rezervoara ne može da priključi pumpu jer je

zauzeta.

• Formirati kolo za generisanje alarmnog

signala pomoću NI logičkih kola!

Projektovanje logičkih sistema 3 Coypright: Lejla Banjanović-Mehmedović

Primjer 4: Sistem rezervoara

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Pozivni signal ima vrijednost

1 ako rezervoar poziva

pumpu, a 0 ako nema

potrebe za pumpom

Alarm ima vrednost 1

ako 3 ili više rezervoara traži

pumpu, ili ako pumpu

istovremeno pozivaju rezervoari A

i B

Primjer 4: Sistem rezervoara

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Sistem upravljanja

protivpožarnim sistemom

zgrade

Projektovati logičko kolo za kontrolu sistema za upravljanje

protupožarnim sistemom zgrade. Protupožarni sistem

opremljen je senzorima za mjerenje temperature u

prostoriji(ST), detektorom dima(DD), senzorom prisutnosti

ljudi(SP), vanjskim senzorom temperature (VT) i senzorom

brzine vjetra(BV).

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Specifikacija zadatka

Aktiviraj alarm: Aktivira se kada je temperatura u prostoriji iznad određnog

praga (ST) i detektiran je dim u prostoriji (DD).

Aktiviraj sistem za gašenje požara: Aktivira se kada je temperatura u prostoriji

iznad određnog praga (ST) i detektiran je dim u prostoriji (DD), ali samo ako

nema prisutnih ljudi u prostoriji (SP).

Otvori vrata za evakuaciju: Aktivira se kada je temperatura u prostoriji iznad

određnog praga (ST) i detektiran je dim u prostoriji (DD), ali samo ako ima

prisutnih ljudi u prostoriji (SP).

Aktiviraj sprinkler sistem: Aktivira se kada je temperatura u prostoriji iznad

određnog praga (ST) i detektiran je dim u prostoriji (DD), ali samo ako nema

prisutnih ljudi u prostoriji (SP) i vanjska temperatura nije iznad određnog praga

(VT).

Aktiviraj sistem za dojavu vatrogascima: Aktivira se kada je temperatura u

prostoriji iznad određnog praga (ST) i detektiran je dim u prostoriji (DD), ali

samo ako nema prisutnih ljudi u prostoriji (SP), vanjska temperatura nije iznad

određnog praga (VT) i brzina vjetra je iznad određnog praga (BV).

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Realizacija ideje

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Tabela istine

Skracenice:

ST - senzor temperature

DD - detektor dima

SP - senzor prisutnost ljudi

VT - senzor vanjske temperature

BV - brzina vjetra

GP - sistem zagasenje pozara

VZE - vrata za evakuaciju

DV - dojava vatrogascima

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović

Optimizacija - Boolova algebra

Projektovanje logičkih sistema

3 Coypright: Lejla Banjanović-Mehmedović