F7210 číslicová technika
Booleova algebra


•buď Bn třída všech funkcí f(x1,…xn) definovaných na {0,1}n, funkce z Bn nazýváme Boleovy funkce
•
•

?
•
•
•Kolik různých vektorů hodnot argumentů obsahuje definiční obor Boolleovy funkce f(x1,…xn) ?
•
•




?
•
•
•Kolik různých vektorů hodnot argumentů obsahuje definiční obor Boolleovy funkce f(x1,…xn) ?
•2n
•
•

?
•
•
•
•Kolik různých funkcí obsahuje třída Bn všech funkcí f(x1,…xn) definovaných na {0,1}n ?
•Třída Bn obsahuje právě







?
•
•
•
•Kolik různých funkcí obsahuje třída Bn všech funkcí f(x1,…xn) definovaných na {0,1}n ?
•Třída Bn obsahuje právě

Definice operací
•0+0=0
•0+1=1+0=1+1=1
•1.1=1
•0.1=1.0=0.0=0
•1=0
•0=1

•Booleova dvouhodnotová algebra je algebra s oborem {0,1} a třídou operací {+,.,- }
•+ logické sčítání,
•. logické násobení
•- negace




základní pravidla Booleovy algebry
•pravidlo agresivnosti a neutrálnosti prvků 0,1
•      x+1 = 1, x · 1 = x
•      x+0 = x, x · 0 = 0
•Pravidlo komutativní
•      x+y = y+x, x · y = y · x
•Pravidlo asociativní
•      x+(y+z) = (x+y)+z, x · (y · z) = (x · y) · z
•
•




základní pravidla Booleovy algebry
•Pravidlo distributivní
•x · (y + z) = ?
•x · (y + z) = (x · y) + (x · z)
•
•x+(y · z) = ?
•x+(y · z) = (x+y) · (x+z),
•
•
•




základní pravidla Booleovy algebry
•pravidlo idempotentnosti
•x+x=?,
•x+x=x,
•x · x=?
•x · x=x
•pravidlo absorpce
•x+(x · y) = ?,
•x+(x · y) =x,
•x · (x + y) = ?,
•x · (x + y) = x




základní pravidla Booleovy algebry
•pravidlo o vyloučeném třetím
•x+x¯=?,
•x+x¯=1,
•x·x¯=?,
•x·x¯=0
•pravidlo involuce
•(x¯)¯=x,
•de Morganova pravidla
•(x+y)¯=?,
•(x+y)¯=x¯·y¯,
•(x·y)¯=?,
•(x·y)¯=x¯+y¯,

x
y
F(x,y)
0
0
1
0
1
1
1
0
0
1
1
0







x
y
F(x,y)
𝑥∗𝑦
0
0
0
0
1
1
1
0
0
1
1
0




x
y
F(x,y)
𝑥∗𝑦

x
y
F(x,y)
𝑥∗𝑦







zjednodušte






příklad
•Př:
•f(x,y,z)def =(x+y)≡x·z
•
•
•

x
y
z
x+y
xz
1
1
1
0
1
1
1
0
1
0
0
1
1
1
0
0
1
0
1
0
0
0
0
0

x
y
z
x+y
xz
1
1
1
1
1
xyz
0
1
1
1
0
1
0
1
1
1
xy¯z
0
0
1
0
0
x¯y¯z
1
1
0
1
0
0
1
0
1
0
1
0
0
1
0
0
0
0
0
0
x¯z¯z¯

Příklad
•f = x¯·y¯·z¯ + x¯·y¯·z+ x·y¯· z + x·y·z


normální součtová (součinová) forma
•Př:
•f(x,y,z)def =(x+y)≡x·z
•f=(x+y)·x·z+ (x+y)¯ ·(x·z)¯
•f=x·x·z+y·x·z + x¯·y¯(x ¯+ z ¯)
•f=x·x·z+y·x·z + x¯·y¯·x ¯+ x¯·y¯ ·z ¯
•f=xz+ x¯·y¯
•
•

normální formy
•primitivní term x~=x, x~=x¯
•elementární součin (součet): součin (součet) konečného počtu navzájem různých primitivních termů
včetně jedničky (nuly)
•

Elementární součin součet, př.
•1
•x
•x·y
•a¯·x
•x¯y¯
•x ·y ·x
•(x ·y)¯
•x ·x¯
•0
•x
•X+y
•a¯+x
•x¯+y¯
•x +y +x
•(x +y)¯
•x +x¯

normální formy
•hodnost h elementárního součinu (součtu) odpovídá počtu písmen v něm obsažených
•Př. h(x+z+y)=?
• h(x+z+y)=3

normální součtová (součinová) forma
•normální součtovou ndf (součinovou nkf) formou nazýváme součet (součin) konečného počtu navzájem
různých  elementárních součinů (součtů)
•ndf (nkf) se nazývá ndf (nkf) Boleovy funkce f je li rovna této funkci
•každou funkci lze převést na ndf (nkf)

normální součtová (součinová) forma
•Př:
•f(x,y,z)def =(x+y)≡x·z
•f=(x+y)·x·z+ (x+y)¯ ·(x·z)¯
•f=x·x·z+y·x·z + x¯·y¯(x ¯+ z ¯)
•f=x·x·z+y·x·z + x¯·y¯·x ¯+ x¯·y¯ ·z ¯
•f=xz+ x¯·y¯
•
•

•f=xyz+ xy¯z+ x¯y¯z¯ + x¯y¯z
•f=xz+ x¯y¯
•

•buď dána třída boleovských proměných {x1,….xn}. Elementární součet  se nazývá maxterm nebo
konstituent nuly na dané třídě, obsahuje-li primitivní termy všech proměnných x1,….xntj.
Mi=xi1+….+xin, existuje jeden a jen jeden vektor hodnot  argumentů na kterém Mi nabývá hodnot nula
•Elementární součin  se nazývá minterm nebo konstituent jednotky na dané třídě, obsahuje-li
primitivní termy všech proměnných x1,….xntj. mi=xi1·….·xin, existuje jeden a jen jeden vektor
hodnot  argumentů na kterém mi nabývá hodnot jedna.

•Ndf (nkf) se nazývá úplnou na třídě argumentů {x1,…xn}, je-li každý její elementární
součin(součet) minterm (maxterm) na dané třídě proměnných úndf (únkf).
•úndf (únkf) se nazývá úndf (únkf) Boleovy funkce f(x1,…xn) úndf(f) (únkf(f)), je-li rovna této
funkci
•

Vyjádření Booleovských proměnných
•Stav Boleovských proměnných vyjadřujeme stavovým indexem s
•Stavový index je číslo,  které dostaneme, považujeme-li vektor hodnot <a1..an> proměnných x1..xn,
za binární číslo o n řádech
•Naopak cifru na místě i tého řádu stavového indexu lze chápat jako hodnotu i té složky vektoru
<a1..an>

Věta 1.2
•Ke každé Booleově fci f existuje jedna a jen jedna úndf (unkf)
•Důkaz:
•Buď f(x1..xn)ϵBn  nechť fk je hodnota funkce na f na k tém vektoru  hodnot argumentů
x1..xn, mk minterm a Mk maxterm korespondující s uvažovaným vektorem hodnot argumentů

•Úplné normální formy funkce f
•Úndf (f)= f0 m0 + f1 m1 + .. f2^n-1 m2^n-1
•Únkf (f)= (f0 +M0 ) (f1 +M1 ) .. (f2^n-1 +M2^n-1)
•Úndf *(f)= g0 m0 + g1 m1 + .. g2^n-1 m2^n-1
•Únkf *(f)= (g0 +M0 ) (g1 +M1 ) .. (g2^n-1 +M2^n-1)
•

•úndf(f), (únkf(f)) je tedy ekvivalentní součtu (součinu) těch mintermů mk (maxtermů) Mk
•Pro které jsou hodnoty fk fce f rovny jedné (nule). Na k tém vektoru argumentů buď mk=1, ml=0,
k≠l; Mk=0, Ml=1, k≠l,
•hodnoty úndf(f), (únkf(f)) na k tém vektoru jsou rovny hodnotám fk funkce f(x1,…xn).
•Index k je zvolen libovolně

Algoritmus přechodu od tab.  K undf (uknf) Booleovy funkce
1.vybereme v matici hodnot funkce všechny vektory hodnot argumentů na kterých funkce nabývá
hodnoty 1 (0)
2.Zapíšeme mintermy (maxtermy) odpovídající těmto vektorům, má-li argument x~ v daném vektoru
hodnotu  1 (0) napíšeme  jeho aserci (negaci), má-li x~ v daném vektoru hodnotu  0,napíšeme jeho
negaci (aserci).
3.Všechny takto získané mintermy (maxtermy) uvedeme do relace operátorem součtu (součinu)

příklad
•Př:
•f(x,y,z)def =(x+y)≡x·z
•
•
•

x
y
z
x+y
xz
1
1
1
1
1
xyz
0
1
1
1
0
1
0
1
1
1
xy¯z
0
0
1
0
0
x¯y¯z
1
1
0
1
0
0
1
0
1
0
1
0
0
1
0
0
0
0
0
0
x¯z¯z¯

Příklad
•f = x¯·y¯·z¯ + x¯·y¯·z+ x·y¯· z + x·y·z


Mapy
•Každou Booleovu funkci f(x1,…xn) lze zobrazi jedním a jen jedním způsobem jako podtřídu třídy
vrcholů n rozměrné jednotkové krychle
•Zvolme v n-rozměrném prostoru souřadnicový systém ˂x1,…xn˃. Protože n rozměrná krychle obsahuje 2n
vrcholů vi, lze psát pro i tý minterm (maxterm)
•mi(x1…..xn)↔ vi(x1…..xn)
•Mi(x1…..xn)↔ vi(x1…..xn)
•Kde i je stavový index i tého vrcholu krychle
•Protože ke každé funkci f existuje jediná undf(f) (unkf(f)),
•Je uvedené zobrazení jediné
•

•Svobodova mapa Booleovy funkce f(x1,…xn), čtvercová nebo obdélníková matice rozdělená pro n
proměnných na 2n polí. Každému poli mapy koresponduje jeden a jen jeden vrchol vi n rozměrné
jednotkové krychle. Vrcholu v0 je přiřazeno levé horní pole, v2n-1, pravé dolní pole.
•

•Počet řádků a sloupců závisí na způsobu rozkladu  třídy argumenů {x1,…xn} na dvě podtřídy.



?
•Je-li {x1,…xn} = {x1,…xk} ∩ {xk+1,…xn}
•Jaký je počet sloupců a řádků?
•počet sloupců 2k
•počet řádků 2n-k

příklad
•Úndf(f)=x1¯·x2·x3¯·x4¯·x5+x1·x2¯·x3¯·x4·x5+
•x1·x2·x3¯·x4¯·x5¯+ x1·x2·x3·x4·x5
•

0
1
2
3
4
5
6
7
0
1
•
2
•
3
•
•
x1
x2
0
0
0
1
1
0
1
1
x5
0
1
0
1
0
1
0
1
x4
0
0
1
1
0
0
1
1
x3
0
0
0
0
1
1
1
1

•Nechť o je oblast v m rozměrném vektorovém prostoru definovaná nerovností g(x1,…xm)≥0
•g je všude definovaná spojitá fce
•Zaveďme booleovskou funkci (o) predikantem (g(x1,…xm)≥0)
•Je-li dána Booleova fce
•f(x1,…xn) = f0 m0 + f1 m1 + .. f2^n-1 m2^n-1
•f(x1,…xn)= (f0 +M0 ) (f1 +M1 ) .. (f2^m-1 +M2^n-1)
•Kde m≥n
•

•Pak je-li mi (x1,…xn)∈o →(o)=1
•je-li mi (x1,…xn)∉o →(o)=0
•Analogicky pro Mi
•Uvažujme oblasti o1, …. on, určené nerovnostmi
•g1(x1,…xm)≥0,……, gn(x1,…xm)≥0
•mi ∈ ∩ oi ⇄ (∀i) (mi ∈ oi )→&i (oi)=1
•Mi ∈ ⋃ oi ⇄ (∃i) (Mi ∈ oi )→⋁i (oi)=1
•Euler-Vennův diagram
•
•

Karnaugh Veithovy mapy
0
1
z
x
y
•
•
•

Karnaugh Veithovy mapy
00
10
01
11
x
x
y




x
y
x
y
x
y
x
y
x
y
x
y

Karnaugh Veithovy mapy
z
x
y
z

Karnaugh Veithovy mapy
x
z
w
y
}

x
z
w
y
}
x
w
y
}

Úplné soustavy Booleových funkcí
•Existuje triviální úplná soustava v uzavřené třídě Bn, kterou tvoří ? funkcí této třídy
•
•

•Věta:
•Funkce logického součtu, součinu a negace tvoří úplnou soustavu v Bn
•Soustavy funkcí {·,¯ } {+,¯} tvoří base třídy Bn
•

důkaz?



důkaz
•x+x¯=1,
•x·x¯=0
•(x+y)¯=x¯·y¯,
•(x·y)¯=x¯+y¯,
•Věta: Ke každé Booleově fci f existuje jedna a jen jedna úndf (unkf)

•Ukažte, že soustavy
•{· }
•{+}
•{¯}
•{+,·}
•Nejsou samy o sobě úplné
•

Minimalisace Booleovy funkce
•Minimalisací B.fce rozumíme proceduru ustanovení jejího nejjednosuššího vyjádření ve tvaru
komposice funkcí libovolně zvolené úplné soustavy S funkcí.
•Za nejjednosušší vyjádření pokládáme obvykle výraz tvořený minimálním možným počtem komposicí.
•Vyjádření minimalisované B. fce ve tvaru ndf s nejmenším počtem písmen.