BOOLEOVA ALGEBRA

Milan Kora, [Link].

Visoka kola za primijenjeno raunarstvo
Zagreb
Zimski semestar 2013.

Booleova algebra
Osnovni matematiki aparat koriten u analizi i

projektiranju digitalnih sklopova

G. Boole:
"An Investigation of the Laws of Thought", London, 1854
C. E. Shannon:

"A Symbolic Analysis of Relay and Switching

Circuits", [Link], 1938
efikasna primijena za analizu relejnih

elektromehanikih sklopova

Aksiomatska definicija
Booleove algebre
E. V. Huntington:

"Sets of Independent Postulates for the Algebra of

Logic", 1904:

Poeljno: minimalni broj postulata

Neophodna svojstva:

konzistentnost:
niti jedan postulat iz skupa ne proturjei nekom drugom iz
istog skupa
nezavisnost:
niti jedan se postulat ne da dokazati pomou ostalih

Formalna definicija
konani skup objekata:

S A, B, C, d , e...x, y, z....

dvije binarne operacije: +,

Operatori (+, ) su zatvoreni s obzirom na S

skup osnovnih aksioma ( postulata)

Varijable [ A,B,...]

S - varijable su lanovi

skupa S
4

Aksiomi
A.1. Aksiom o neutralnim elementima
Postoji neutralni elementi 0 i 1 s obzirom na operatore
(+ i ) tako da vrijedi:
a) A + 0 = A
b) A1 = A

A.2. Aksiom o komplementu

Za svaki A postoji A S tako da vrijedi:

a) A A 0
b) A A 1
5

Aksiomi
A.3. Zakon komutacije
Operatori su komutativni:
a) A+B = B+A
b) BA = AB
A.4. Zakon distribucije
Operatori su distributivni jedan preko drugoga
a) A (B+C) = AB + AC
b) A+BC = (A+B)(A+C)
Aksiomi A.2. i A.4.b ne vrijede u obinoj algebri
6

Hijerarhija operatora
Komplement ""
logiko mnoenje ()
logiko zbrajanje (+)

Hijerarhija operatora
Zagrade mijenjaju redoslijed obavljanja operacija

na uobiajeni nain
Operatori se kolokvijalno nazivaju: mnoenje,
zbrajanje i komplementiranje
Radi se o logikima a ne aritmetikim
operacijama
0 i 1 su logike a ne aritmetike veliine
Dualnost (metateorem o dualnosti):

"Zamjenom operatora i neutralnih elemenata

u nekom postulatu dobiva se njegov dualni dio "
8

TEOREMI
T.1. Zakon dominacije
a) A + 1 = 1
b) A 0 = 0
Dokaz teorema:
A + 1 = (A + 1)1
=(A + 1)(A+ A )

A 1 A
A A
1
9

primjena aksioma A.1.b

[Link]

A.4.b
A.1.b
A.2.a
9

TEOREMI
T.2. Zakon idempotencije
a) A+A = A
b) AA = A
Dokaz: A+A = (A+A)1

A.1

( A A)( A A)

A.2
..

A A A

A.4

A0

A.2.

=A
10

10

TEOREMI
T.3. Zakon involucije

A A

T.4. Zakon apsorpcije

a) A+AB = A
b) A (A+B) =A
Dokaz

A+AB =A1+AB
=A(1+B)
=A1
=A
11

A.1
A.4
T.1

TEOREMI
T.5. Zakon asocijacije
a) (A+B)+C = A+(B+C)
b) (AB)C = A(BC)
T.6. De Morganov zakon

a) A B A B
b)

12

AB A B

TEOREMI
Dokaz
Supstitucija: A+B = X
Ako je teorem ispravan
mora biti:

X AB

Prema A.2. mora biti:

X X 1
X X 0

Ako se ponovno uvrste vrijednosti supstitucije:

13

Slijedi

L.1:
L.2:

( A B) ( A B ) 1

( A B) ( A B ) 0
( A B) A B

L.1

( A AB ) B
( A A)( A B ) B

T.4

1 ( A B ) B

A.2.

A (B B )

A 1

1
14

A.3., T.5.

A.1.,T.5.

A.2.
T.1.

L.2

( A B) A B

AA B BA B

0 B 0 A
00
0

15

A.4
A.2.
T.1.
T.2.

T.7. Generalizirani De Morganov

teorem
a)
b)

A B C A B C
A B C A B C
A B C

Dokaz:

16

A X

supstitucija:
X=B+C

AX

T.6.

A (B C)

supstitucija za X

A (B C )

T.6.

A B C

T.5

Zakon simplifikacije
T.8. Zakon simplifikacije
a)
AB AB
b)

A
( A B) ( A B ) A

Dokaz

17

AB AB

A (B B )

A.4.

A 1

A.2.

A.1.

Dvolana Booleova algebra

S = {0,1}
A.1.:
A+0=A; A1=A
A.2.: A A 1 ; A A 0
T.1.:
A+1=1; A0=0
Uvrtavanjem 0 i 1 slijedi:

A
0

A+B

AB

18

Dokaz konzistencije : realni sustav

Druge Booleove algebre

Elementi su skupovi
Booleovih algebri

algebra skupova je formalno jedna od

Vennovi dijagrami
AB=A B

A+B=A B

U
A

U
A

A B

19

A B

A
AA

Booleove funkcije
Razni izrazi
ista tablica
f AB A B
Primjer:
f A

Konstrukcija tablice
uvrtavanjem:

20

ista funkcija

A
0

B
0

AB
0

AB+ AB
0

0
1
1

1
0
1

0
0
1

0
1
0

0
1
0

0
1
1

B AB

Minterm
S dvije ulazne promjenljive veliine mogue je nainiti

etiri razliite operacije logikih umnoaka:

AB, AB, AB, AB
Tablica stanja za mogue vrijednosti na ulazu
U izlaznom stupcu se dobije samo jedna jedinica
Minterm logika operacija koja na izlazu daje
jedinicu (1) samo za jednu ulaznu kombinaciju
Ostvaruje se operacijom I
Dvije ulazne varijable etiri razliita minterma
21

Minterm
Primjer: realizacija minterma m2 s tri ulazne varijable
Minterm m2 = izlaz je 1 za ulaznu kombinaciju 010
Logika jednadba minterma: m2= A B C

22

m2

Minterm
Kad je potrebno ostvariti logiku operaciju koja na

izlazu daje jedinicu (1) za vie ulaznih kombinacija,

koristi se logiki zbroj minterma

23

Y=AB C + A B C

Minterm

24

Maksterm
S dvije ulazne promjenljive veliine mogue je nainiti

etiri razliite operacije logikih zbrojeva:

A+B, A+B, A+B, A+B
Tablica stanja za mogue vrijednosti na ulazu
U izlaznom stupcu se dobije samo jedna nula (0)
Maksterm logika operacija koja na izlazu daje
nulu(0) samo za jednu ulaznu kombinaciju
Ostvaruje se operacijom ILI
Dvije ulazne varijable etiri razliita maksterma
25

Maksterm
Primjer: realizacija maksterma M2 s tri ulazne

varijable
Maksterm M2 = izlaz je 0 za ulaznu kombinaciju 010
Logika jednadba maksterma: M2= A + B +C

26

M2

Maksterm
Kad je potrebno ostvariti logiku operaciju koja na

izlazu daje jedinicu (0) za vie ulaznih kombinacija,

koristi se logiki umnoak maksterma

27

Y=(A+B + C) (A + B + C)

Maksterm

28

29

Napiite tablino zadanu funkciju kao sumu

minterma i kao produkt maksterma
A B C f mintermi

Makstermi

0 0 0 1

m0

M0

0 0 1 0

m1

M1

0 1 0 0

m2

M2

0 1 1 1

m3

M3

1 0 0 1

m4

M4

1 0 1 0

m5

M5

1 1 0 1

m6

M6

1 1 1 0

m7

M7

Rjeenje
Funkcija kao suma minterma

f= A B C + A B C + A B C + A B C = (0,3,4,6)
Funkcija kao produkt Maksterma
f= (A + B + C)(A + B + C)(A + B + C)(A + B + C)=
= (1,2,5,7)

Odreivanje logikog izraza iz tablice

- kanonski oblik logike funkcije
Primjer:
Iskljuivo ILI ( EX OR)
f AB AB
vi = vrijednost funkcije za tu ulaznu kombinaciju
mi = minterm ; Mi = maksterm; i = 0,1,....(r-1); r = broj redaka
Struktura standardne tablice: rastui redoslijed binarnih brojeva

32

f AB AB

A B

AB A B

mi

Mi

0 = v0

m0 A B

1 = v1

m1 A B

M3 A B

1 = v2

m2 AB

M3 A B

0 = v3

m3 AB

M3 A B

M0 A B

B
A

Vrijednost funkcije 1
Ispunjeno u drugom i treem retku
v1
a) A = 0 ; B = 1
v2
b) A = 1 ; B = 0
Napisano drugaije:
AB 1
a) A =1; B=1
b) A=1; B 1
AB 1

f A B AB
Openito:

r 1

f
n = broj varijabli
33

i 0

vi mi
r 2 n

Vrijednost funkcije 0
V0
V3

a) A = 0 ; B = 0
b) A = 1 ; B = 1
A = 0 ;B = 0

A B 0
A B 0

f ( A B) ( A B )
r 1

openito

f (vi Si )
i 0

Funkcije su jednake:
( A B)( A B ) AA A B AB BB

0 A B AB 0

A B AB AB A B

34

A.4.

A.2
A.1., A.3.

Skraeno pisanje standardne tablice kombinacija

Npr

f ( A, B) A B AB
0 1

1 0

f ( A B) ( A B )

35

m , m 1,2
1

(M , M ) (0,3)
0

Nekanonski oblici funkcije

pretvorba u kanonski oblik
1. metoda
Svaki lan mnoiti s ( X X )
varijable
Npr

gdje su s X oznaene nedostajue

y A B C
A B C

A.1., A.2.

A ( B B )(C C ) B C ( A A )

A.4.

A BC A B C A BC A B C AB C A B C
ABC ABC ABC ABC ABC
36

(0,1,2,3,5)

2. Metoda: uvrtavanjem 0 i 1 konstruirati standardnu tablicu

kombinacija
y A B C

37

(0,1,2,3,5)

Funkcija u drugom kanonskom

obliku
[Link]
Varijable koje nedostaju u svakom lanu treba dodati kao X X

Npr

f A( A B)
( A B B)( A B)
( A B)( A B)( A B)
( A B)( A B)
(0,1)

A.2.b, A.1.a
A.4.b
T .2.

2. Metoda: Konstruirati tablicu uvrtavanjem 0 i 1

38

Komplement funkcije
Komplementarna funkcija: vrijednosti funkcije komplementirane
( 0 u 1 i obratno)
Npr

A
0
0
1
1

39

B
0
1
0
1

f
1
0
0
0

f
0
1
1
1

mi
AB
AB
AB
AB

Mi
A B
A B
A B
A B

r 1

v m
i

i 0

r 1

v m
i

i 0

Komplement funkcije
Izraunati komplement funkcije:

40

Algebarski zadana funkcija

Primjena De Morgana
f ( A, B) AB
f ( A, B) AB A B A B

Odnosi izmeu minterma i maksterma:

41

mi M i

Dualna funkcija
Dualna funkcija, ( metateorem o dualnosti), dobiva se tako da
se meusobno zamijene operatori i, ako postoje u izrazu,
konstante 0 i 1.
Ako je funkcija f :
f f ( A, B, C,...,,, ,0,1),

Dualna funkcija je:

f D f ( A, B, C,...,,, ,1,0).

Npr

f AB CD,

f D ( A B) (C D) AC C B AD BD
[ f D ] D ( A C )(C B )( A D)( B D).
42

dualna funkcija od f
dualni oblik funkcije f

Generalizirani De Morgan
A B C ... A B C ...

pomou dualne funkcije

f ( A, B, C,...) f D ( A, B , C ,...).

Primjer primjene
f ( A, B, C ) A B C A B C A BC ,
f ( A, B , C ) ABC ABC AB C ,
f f D ( A, B , C ) ( A B C )( A B C )( A B C ).

43

Funkcije jedne i dvije varijable

Broj funkcija od n varijabli:

n1

44

2n

2n

2 4

16

256

16

64K = 65 536

32

4G = 4 294 967 296

Funkcije jedne varijable:

A
0

f0
0

f1
0

f2
1

f3
1

f0 = 0
f1 = A
f2 =1
f3 = A

Funkcije dviju varijabli

AB

f0

fl

f2

f3

f4

f5

f6

f7

f8

f9

f10 f11 f12 f13 f14 f15

00

01

10

11

45

Razliite funkcije 2 varijable

Funkcija

Ime

Primjedbe

f1 AB

A B

I-funkcija
(konjunkcija)

f 2 AB

A/ B

Inhibicija

B inhibira A

A B

Iskljuivo ILI

ili A ili B, ali ne

oboje

A B

ILI-funkcija
(disjunkcija)

f 6 AB A B

f7 A B
f8 A B

f 9 AB A B
f10 B
f11 A B

f14 AB

46

Simbol za
operator

A B

NILI

NE-ILI

AB

Ekvivalencija

Komplement

NE-B

A B

implikacija

Ako A, onda B

A B

NI

NE-I

Realizacija i simboli
ISKLJUIVO ILI funkcija

f AB AB

=1

47

A
B

f=A+B

NILI funkcija

f A B

Ekvivalencija

f 9 AB A B

48

f A B

f 9 AB A B

3. Osnove digitalne logike

Implikacija

f11 A B

Inhibicija

f 2 AB

49

f11 A B

f 2 AB

NI funkcija

f14 AB

50

f14 AB

50

Skupine osnovnih funkcija

1.

I ILI NE

2.

I-NE

3.

ILI-NE

A B A B AB,

4.

NI

A A A

5.

NILI

6.

Itd.
NI i NILI su UNIVERZALNE FUNKCIJE

51

A B A B A B,

A A A

AB AB

A B A B

AB A B

A B AB

51

Implementacija I, ILI i NE s univerzalnim funkcijama

NE

ILI
A

A A A

A B

A B

AB A B
B

A A A

A B

A A A

A B A B
B

A A A

A
B

52

A
B

A B

A B

A B

Funkcije vie varijabli

Skupina I, ILI , NE proizvoljan broj varijabli
2.
Iskljuivo ILI
Primjer za 3 varijable A B B A; ( A B) C A ( B C).
1.

f ( A, B,C ) A B C AB C A BC ABC A B C.
f ( A, B ,C ) ( AB AB) C ( AB AB)C ( AB AB)C AB C A BC ABC A B C.
( AB AB)C ( A B)( A B) C ) [ AA AB AB B B)]C ABC ABC

53

f ( A, B,C ) A B C

Neparna funkcija
(vrijedi i za Iskljuivo ILI)

Vanost EX-ILI
aritmetiki sklopovi
zatita poruka od pogreaka prilikom prijenosa
generiranje pseudo-sluajnih nizova
(kodiranje, kriptiranje)
Simboli

2k+1

54

Primjer EX-ILI funkcije

55

Ekvivalencija = logiki identitet

(jednaka 1 kad su svi bitovi jednaki 0 ili 1

f x1x2 ...xn x1x2 ...xn .

NI funkcija

f NI X 0 X1... X n
NILI funkcija

f NILI X 0 X1 ... X n
56

Jo neke funkcije vie varijabli

Logiki prag
m ulaza u 1, m < n
Majoritet (glasanje)
veinska funkcija
> n/2 ulaza u 1

n ulaza
m

n ulaza

n
2

Samo m"
upravo m ulaza u 1, m < n
n ulaza

57

Pretvaranje funkcije u NI-oblik

( f = suma produkata) metoda supstitucije

I NE NI

ILI NI NE (n puta)

Pravilo: zamijeniti osnovne funkcije ( I,ILI i NE)

s funkcijom NI

58

ILI

Algebarska metoda
primijeniti T3 (involucija) na izraz kojim je definirana Booleova funkcija
primijeniti T8 (de Morganov zakon)

2n 1

f ( x1 , x2 ,..., xn ) i Pi
i 0

0 P0 1 P1 ... 2n 1 P2n 1
0 P0 1 P1 ... 2n 1 P2n 1
Npr

59

f A BC A BC ( A ) ( BC )

Pretvaranje funkcije u NILI-oblik ( f = produkt suma)

metoda supstitucije
zamijeniti osnovne funkcije kombinacijom NILI koja ispunjava istu
funkciju
primijeniti T3 (involucija)
( eliminirati dvostruku primjenu funkcija NE )

ILI NE NILI I NILI NE (n puta )

ILI

60

Konano:

Pravilo: zamijeniti sve funkcije NILI funkcijama

Algebarski:

f A( B C )( D E ) A ( B C ) ( D E ).

61

Nepotpuno specificirane funkcije

Primjer:
Funkcija koja ispituje je li dekadska
znamenka
A = a3a2a1a0 prikazana u BCD kodu neparna
f = m(1, 3, 5, 7, 9) +
d(10, 11, 12, 13, 14, 15)
= M(0, 2, 4, 6, 8)
d(10, 11, 12, 13, 14, 15)

Nije vana vrijednost funkcije (engl.

don't care) u tablicu kombinacija
upisuje se "X"

62

Pozitivna i negativna logika:

Pridruivanje logikih vrijednosti naponskim
razinama

pozitivna logika:

1
0

negativna logika:

63

vii napon
nii napon
I/ILI ILI/I
vii napon
nii napon
I/ILI ILI/I

0
1

Tablica diodnog I sklopa

[Link]

[Link].

U0
R
A

Ru

B
Ru

Uizl
uA

64

uB

A
B

f=AB

A
B

f=A+B

Tablica diodnog ILI sklopa

[Link].

[Link].

A
B
Ru

Ru
R

uG

uG

65

uizl

A
B

f=A+B

A
B

f=AB

Vremenski hazard:

stvarni (kombinacijski) sklopovi: postoji kanjenje (td)!

promatrati ostvarenu logiku funkciju + td
A
B

AB

Dt

D (AB)

operator kanjenja

neoekivano ponaanje sklopa u prijelaznoj pojavi

hazard (rizik):
pojava privremenog krivog impulsa koji u odreenim
sluajevima moe prouzrokovati pogrean rad sklopa
66

Statiki 0-hazard
A

td1

td 2

f A A 0

Statiki 0-hazard: generiranje impulsa 1 na

izlazu logikog sklopa koji je, statiki gledano,
prije i poslije promjene na ulazu/ulazima bio u 0

t
A

td1

Statiki 1-hazard: izlaz statiki u 1, a za

prijelazne pojave generira se 0. (Dodati invertor
na izlazu)

td1

td 2

67

Dinamiki hazard
generiranje jednog ili vie impulsa

prilikom promjene stanja na izlazu

izlaz

68

LITERATURA:
Uro Peruko: Digitalni sustavi
Str. 79 89

69