Booleovská algebra.Booleovské binární a unární funkce. Základní zákony.
Tomáš Bayer | [email protected]
Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 1 / 30
Obsah přednášky
1 Booleovská funkce
2 Přehled unárních booleovských funkcí
3 Přehled binárních booleovských funkcí
4 Booleovská algebra
5 Tautologie a kontradikce
6 Převod pravdivostní tabulky na formuli
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 2 / 30
Booleovská funkce
1. Úvod
Spojité veličiny:Proměnné veličiny, které nabývají “nekonečného” množství hodnot.Lze je popsat spojitými proměnnými a vyjádřit reálnými datovými typy.
Diskrétní veličiny:Proměnné veličiny, které nabývají konečného množství hodnot.Lze je popsat diskrétními proměnnými a vyjádřit celočíselnýmidatovými typy.
Booleovská algebra:Proměnné veličiny nabývají hodnot 0,1.Hodnotu 0 lze interpretovat jako nepravda, hodnotu 1 jako pravda.Obě hodnoty lze simulovat fyzikálně: prochází proud, neprocházíproud.V informatice hraje velmi výraznou roli při konstrukci relací.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 3 / 30
Booleovská funkce
2. Booleovská funkce
DefinitionBooleovskou funkci f s argumenty x1, ..., xn označujeme takovou funkciy = f (x1, ..., xn), která libovolné kombinaci argumentů přiřadí funkční hodnotu
f (x1, ..., xn)→ {0,1}
Počet argumentů n obecně libovolný, většinou bývá konečný, n ∈ Z+:n = 1: unární booleovská funkce.n = 2: binární booleovská funkce.
Definiční obor booleovské funkce: xi = {0,1}, k = ‖Df‖ = 2n.Počet booleovských funkcí m = 2k .
Vektor kombinací βVektor β tvořený konečnou uspořádanou posloupností nul a jedničekvyjádřený ve tvaru (β1, β2, ..., βn), kde
βi = f (x1, ..., xn) =
{01
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 4 / 30
Booleovská funkce
3. Pravdivostní tabulka
Udává závislost funkčních hodnot f (x1, ..., xn) na hodnotáchargumentu (x1, ..., xn).
x1 x2 ... xn f (x1, ..., xn)0, 1 0, 1 ... 0, 1 0, 10, 1 0, 1 ... 0, 1 0, 10, 1 0, 1 ... 0, 1 0, 10, 1 0, 1 ... 0, 1 0, 10, 1 0, 1 ... 0, 1 0, 1... ... ... ... ...
Počet řádků pravdivostní tabulky dán definičním oborem booleovskéfunkce:
unární booleovská funkce = dva řádky x dva sloupce,binární booleovská funkce = čtyři řádky x tři sloupce.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 5 / 30
Přehled unárních booleovských funkcí
4. Unární booleovská funkce
Unární booleovská funkce pracuje pouze s jednou proměnnou:f (x)→ {0,1}.
Definiční obor unární funkce dán 21 hodnotami.Existuje 22
1unárních booleovských funkcí.
Přehled unárních booleovských funkcí:
Falsum.Negace.Aserce.Verum.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 6 / 30
Přehled unárních booleovských funkcí
5. Falsum
Funkci y = f1(x) nazýváme falsum, jestliže platí
f1(0,1)→ {0}.
Tato funkce libovolné hodnotě x přiřazuje hodnotu nepravda.
Pravdivostní tabulka funkce f1(x):
x f1(x)
0 01 0
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 7 / 30
Přehled unárních booleovských funkcí
6. Negace
Funkci y = f2(x) nazýváme negací, jestliže platí
f2(0,1) =
{1 pro x = 00 pro x = 1
.
Negace je nejznámější a nejčastěji používanou unární funkcí.Přiřazuje hodnotě f (x) opačnou hodnotu proměnné x .Označení negace: x .
Pravdivostní tabulka negace:
x f1(x)
0 11 0
V programovacích jazycích odvozených od jazyka C bývá negaceoznačována symbolem !.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 8 / 30
Přehled unárních booleovských funkcí
7. Aserce
Funkci y = f3(x) nazýváme asercí, jestliže platí
f2(0,1) =
{1 pro x = 10 pro x = 0
.
Aserce přiřazuje hodnotě f (x) hodnotu proměnné x .
Pravdivostní tabulka aserce:
x f1(x)
0 01 1
Tato funkce se v praxi příliš nepoužívá.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 9 / 30
Přehled unárních booleovských funkcí
8. Verum
Funkci y = f4(x) nazýváme verum, jestliže platí
f4(0,1)→ {1}
Tato funkce libovolné hodnotě x přiřazuje hodnotu pravda.
Pravdivostní tabulka verum:
x f1(x)
0 11 1
Tato funkce se v praxi příliš nepoužívá.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 10 / 30
Přehled binárních booleovských funkcí
9. Binární booleovská funkce
Binární booleovské funkce pracují s dvojicí argumentů x1, x2, platíf (x1, x2)→ {0,1}.
Definiční obor binární funkce dán 22 hodnotami.Existuje 22
12= 16 binárních booleovských funkcí.
Nejčastěji používané booleovské binární funkce:KonjunkceDisjunkceNegace konjunkceNegace disjunkceEkvivalenceNonekvivalenceImplikace.
Definiční obor každé binární booleovské funkce je tvořen 22
hodnotami.Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 11 / 30
Přehled binárních booleovských funkcí
10. Konjunkce
Konjunkcí neboli “logickým součinem” nazýváme takovou funkci fpopsanou následující pravdivostní tabulkou:
x1 x2 f (x1, x2)0 0 00 1 01 0 01 1 1
Funkční hodnota je rovna jedné pouze v případě, kdy jsou oba vstupníargumenty x1, x2 rovny jedné.Logický součin označujeme znakem ∧, zápis a ∧ b čteme jako “a i b”.Pro vyjádření konjunkce používáme logickou spojku AND.
V programovacích jazycích odvozených od jazyka C bývá konjunkceoznačována symbolem &&.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 12 / 30
Přehled binárních booleovských funkcí
11. Disjunkce
Disjunkcí neboli “logickým součtem” nazýváme takovou funkci fpopsanou následující pravdivostní tabulkou:
x1 x2 f (x1, x2)0 0 00 1 11 0 11 1 1
Poslední řádkou tabulky se disjunkce liší od “obyčejného” součtu.
Funkční hodnota je rovna nule pouze v případě, kdy jsou oba vstupníargumenty x1, x2 rovny nule.Logický součet označujeme znakem ∨, zápis a ∨ b čteme jako “a nebob”.Pro vyjádření disjunkce používáme logickou spojku OR.
V programovacích jazycích odvozených od jazyka C bývá disjunkceoznačována symbolem ||.
1 2 a f
1 10 1010 1111
1 0010 1010 1111
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 13 / 30
Přehled binárních booleovských funkcí
12. Negace konjunkce
Negaci logického součinu nazýváme takovou funkci f popsanounásledující pravdivostní tabulkou.
x1 x2 f (x1, x2)0 0 10 1 11 0 11 1 0
Funkční hodnota nabývá jedné v případě, kdy oba argumenty x1, x2nejsou rovny jedné.Tuto funkci nazýváme Shefferovou funkcí .
Pro její vyjádření používáme logickou spojku NAND.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 14 / 30
Přehled binárních booleovských funkcí
13. Negace disjunkce
Negaci logického součtu nazýváme takovou funkci f popsanounásledující pravdivostní tabulkou.
x1 x2 f (x1, x2)0 0 10 1 01 0 01 1 0
Funkční hodnota nabývá jedné v případě, kdy oba argumenty x1, x2nejsou jsou rovny nule.Tuto funkci nazýváme Pierceovou funkcí .
Pro její vyjádření používáme logickou spojku NOR.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 15 / 30
Přehled binárních booleovských funkcí
14. Nonekvivalence
Nonekvivalencí nazýváme takovou funkci f popsanou následujícípravdivostní tabulkou.
x1 x2 f (x1, x2)0 0 00 1 11 0 11 1 0
Funkce je analogií sčítání, označujeme ji znakem ⊕.Její hodnota je pravdivá pokud se oba argumenty x1, x2 liší.
Pro její vyjádření používáme XOR=”eXlucive OR”.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 16 / 30
Přehled binárních booleovských funkcí
15. Implikace
Implikací nazýváme takovou funkci f popsanou následujícípravdivostní tabulkou.
x1 x2 f (x1, x2)0 0 10 1 11 0 01 1 1
U implikace je důležité pořadí argumentů x1, x2, x1 je p°edpoklad a x2je tvrzení.
Implikaci lze interpretovat jako “Jestliže platí x1, pak platí x2”.Funkční hodnota nabývá hodnoty nepravda, pokud je první výrokpravdivý a druhá nepravdivý.
Pro vyjádření implikace používáme⇒.Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 17 / 30
Přehled binárních booleovských funkcí
16. Vztahy mezi booleovskými funkcemi
Každou booleovskou funkci lze vyjádřit kombinací ostatníchbooleovských funkcí stejné třídy.
Funkce lze vzájemně upravovat a zjednodušovat.
Úpravy musí být ekvivalentní, nesmí se při nich změnit pravdivostníhodnota výrazu.
PříkladSchefferova funkce: f (x1, x2) = x1 ∧ x2 = x1 ∨ x2.Pierceova funkce: f (x1, x2) = x1 ∨ x2 = x1 ∧ x2.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 18 / 30
Booleovská algebra
17. Booleovská algebra
Je tvořena booleovskými funkcemi s konečným počtem argumentů sdefinovanými algebraickými pravidly.V praxi pracuje pouze se 3 základními booleovskými unárními abinárními funkcemi: negací, konjunkcí, disjunkcí.
Booleovská formule:Konečný logický výraz obsahují kombinace elementárníchbooleovských funkcí, jehož pravdivost lze vyhodnotit (viz dále).
Minimalizace formule:Zápis logického výrazu s co nejmenším počtem logických funkcí aargumentů.Cílem zjednodušení a zpřehlednění formule.Praktické využití⇒šetření strojovým časem při vyhodnocování výrazu.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 19 / 30
Booleovská algebra
18. Booleovská formule a jejich identita
Booleovskou formulí označujeme logický výraz V tvořený konečnýmpočtem m booleovských funkcí f a n booleovských proměnných x
V = (f (1)(x1), f (1)(x2), ..., f (1)(xn), ..., ..., f (m)(x1), f (m)(x2), ..., f (m)(xn)).
Identita formulí:Ověřuje existenci ekvivalence mezi dvěma booleovskými formulemi.Využíváme zákony booleovské algebry (unární zákony,binární zákony)+ provádíme její minimalizaci.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 20 / 30
Booleovská algebra
19. Priorita booleovských operací
Udává, v jakém pořadí jsou jednotlivé booleovské operace prováděny=> analogie s běžnými aritmetickými operacemi.Vyhodnocování výrazu z leva do prava.
Pravidlo priority operací:Pravidlo priority operací platí následujícím způsobem:
1 Negace.2 Konjunkce.3 Disjunkce.
Změna priorit operací:Pořadí vyhodnocování booleovských operací lze změnitprostřednictvím závorek.
Příklad: platí následující ekvivalence?:V1(x , y , z) : x ∧ (y ∨ z ∧ x) = (x ∧ y) ∨ z ∧ x . Neplatí.V2(x , y , z) : (x ∧ y) ∨ z ∧ x) = x ∧ y ∨ z ∧ x . Platí.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 21 / 30
Booleovská algebra
20. Booleovské unární zákonyZákon dvojí negace:
x = x (1)Zákon vyloučení třetí možnosti:
x ∨ x = 1 (2)Zákon sporu:
x ∧ x = 0 (3)Zákony opakování (idempotence):
x ∨ x = x (4)x ∧ x = x (5)
Zákony neutrálnosti:
x ∨ 0 = x (6)x ∧ 1 = x (7)
Zákony agresivnosti:
x ∨ 1 = 1 (8)x ∧ 0 = 0 (9)
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 22 / 30
Booleovská algebra
21. Booleovské binární zákony (1/2)
Komutativní zákony:
x1 ∨ x2 = x2 ∨ x1 (10)x1 ∧ x2 = x2 ∧ x1 (11)
Asociativní zákony:
x1 ∨ (x2 ∨ x3) = (x1 ∨ x2) ∨ x3 (12)x1 ∧ (x2 ∧ x3) = (x1 ∧ x2) ∧ x3 (13)
Distributivní zákony:
x1 ∧ (x2 ∨ x3) = (x1 ∧ x2) ∨ (x1 ∧ x3) (14)x1 ∨ (x2 ∧ x3 = (x1 ∨ x2) ∧ (x1 ∨ x3) (15)
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 23 / 30
Booleovská algebra
22. Booleovské binární zákony (2/2)
De Morganovy zákony:
(x1 ∨ x2) = x1 ∧ x2 (16)(x1 ∧ x2) = x1 ∨ x2 (17)
Adsorpční zákony:
x1 ∨ (x1 ∧ x2) = x1 (18)x1 ∧ (x1 ∨ x2) = x1 (19)
Zákony adsorpce negace:
x1 ∨ (x1 ∧ x2) = x1 ∨ x2 (20)x1 ∧ (x1 ∨ x2) = x1 ∧ x2 (21)
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 24 / 30
Booleovská algebra
23. Příklad použití booleovských zákonů
Zjednodušte s využitím booleovských unárních a binárních zákonůnásledující formuli:
V (x1, x2) = (((x1 ∧ x2) ∨ (x1 ∧ x2))∨x1
V = ((x1 ∧ x2)∧(x1 ∧ x2))∨x1 ‖ (18) = ((x1 ∧ x2) ∧ (x1 ∧ x2)) ∨ x1 ‖ (2.)= 0 ∨ x1 ‖ (4) = x1.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 25 / 30
Tautologie a kontradikce
24. Tautologie
Představuje booleovskou formuli, která je vždy pravdivá.
Pro libovolnou kombinaci argumentů nabývá hodnoty pravda.Většina booleovských unárních a binárních zákonů představujítautologie.
Tautologie se ve formalizovaných jazycích používají při posuzováníidentity vztahů, důkazech, atd. Nejjednodušší tautologii představujezákon dvojí negace x = x .
Při navrhování podmínek sloužících k ukončení cyklu či rekurze jenutno dát pozor, aby formule nebyla tautologií, a nevznikl nekonečnýcyklus či nekonečná rekurze.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 26 / 30
Tautologie a kontradikce
25. Kontradikce
Kontradikce představuje booleovskou formuli, která je vždynepravdivá.
Pro libovolnou kombinaci argumentů nabývá hodnoty nepravda.Kontradikce je negací tautologie, tautologie je negací kontradikce.
Příkladem kontradikce je zákon sporu x ∧ x = 0.
Při navrhování podmínek sloužících k ukončení cyklu či rekurze jenutno dát pozor, aby formule nebyla kontradikcí, a nevznikl nekonečnýcyklus či nekonečná rekurze.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 27 / 30
Tautologie a kontradikce
26. Příklad
Ověřte, zda jsou následující formule tautologií či kontradikcí.V1(x) = x ∧ (x ∨ (x ∨ x)),V2(x1, x2) = ((x1 ∧ x2) ∨ x1) ∧ (x1 ∧ (x2 ∨ x1)).
Formuli V1(x) můžeme upravovat: V1(x) = x ∧ (x ∨ 1) ‖ 3= x ∧ (1) ‖ 9= x ∧ 0 ‖ 10 = 0. Formule V1(x) je kontradikcí.
Formuli V2(x1, x2) můžeme upravovat:V2(x1, x2) = ((x1 ∧ x2) ∨ x1) ∧ (x1) ‖ 20 = (x1) ∧ (x1) ‖ 19 = 0 ‖ 4 = 1.Formule V2(x1, x2) je tautologií.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 28 / 30
Převod pravdivostní tabulky na formuli
27. Vztah mezi formulí a pravdivostní tabulkou:Každou booleovskou formuli lze vyjádřit jako logický součet logických součinůjednotlivých argumentů a negací těchto argumentů.
Tento postup představuje rozklad booleovské formule V na součet součinů.
Každý řádek pravdivostní tabulky lze zapsat jako jako dílčí formuli Vi :
Vi(x1, ..., xn) = ({
x1x1
}∧{
x2x2
}∧ ... ∧
{xnxn
}) (22)
Výslednou formuli V lze vyjádřit jako disjunkci dílčích formulí Vi .
S jednotlivými řádky pravdivostní tabulky pracujeme následujícím způsobem:
vybereme pouze ty řádky, u kterých je funkční hodnota rovna 1,
pokud je hodnota argumentu xi = 1, je v algebraickém výrazu argument valgebraickém výrazu vyjádřen jako xi .
pokud je hodnota argumentu xi = 0, je v algebraickém výrazu argument valgebraickém výrazu vyjádřen jako x i .
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 29 / 30
Převod pravdivostní tabulky na formuli
28. Příklad
Booleovská formule V (x1, x2, x3) je dána následující pravdivostní tabulkou, nalezněte její
algebraické vyjádření.
x1 x2 x3 f (x1, x2, x3)
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0
Pak V1(x1, x2, x3) = x1 ∧ x2 ∧ x3, V3(x1, x2, x3) = x1 ∧ x2 ∧ x3, V6(x1, x2, x3) = x1 ∧ x2 ∧ x3.Výslednou formuli můžeme vyjádřit jakoV (x1, x2, x3) = V1(x1, x2, x3)∨V3(x1, x2, x3)∨V6(x1, x2, x3) = x1∧x2∧x3∨x1∧x2∧x3x1∧x2∧x3.
Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky a kartografie, Přírodovědecká fakulta UK.)Booleovská algebra. 30 / 30
Booleovská funkcePrehled unárních booleovských funkcíPrehled binárních booleovských funkcíBooleovská algebraTautologie a kontradikcePrevod pravdivostní tabulky na formuli
