VÝUKOVÝ MATERIÁL Identifikační údaje školy
Číslo projektu Název projektu Číslo a název šablony Autor Tematická oblast Číslo a název materiálu Anotace Vytvořeno Určeno pro Přílohy
Vyšší odborná škola a Střední škola, Varnsdorf, příspěvková organizace Bratislavská 2166, 407 47 Varnsdorf, IČO: 18383874 www.vosassvdf.cz, tel. +420412372632 CZ.1.07/1.5.00/34.1076 Pro vzdělanější Šluknovsko 32 – Inovace a zkvalitnění výuky prostřednictvím ICT 0207 Mgr. Bc. Jan Škoda Programování VY_32_INOVACE_0207_0113 Booleova algebra Žák si upevní učivo o Booleově logice 16. 7. 2013 3. ročník oboru Informační technologie Bez příloh
Metodický list • Učitel: • Výklad s projekcí elektronického učebního materiálu. • Ukázka obecného postupu činností. • Monitorování činnosti žáků.
• Žák: • Sleduje výkladovou projekci a demonstraci učitele. • Procvičuje.
Booleova algebra
Booleova algebra • Booleova algebra (čti „búlova˙), nazvaná podle irského matematika a logika George Boolea (1815– 1864). • Je užitečná v mnoha matematických disciplínách a má velmi široké uplatnění v technických aplikacích. • Tvoří teoretický základ pro navrhování rozmanitých regulovacích a rozhodovacích systémů.
Definice • Booleova algebra je definována jako množina prvků (proměnných A, B, …,X, Y, které mohou nabývat hodnot buď 0 nebo 1) v níž je definována ekvivalence (rovnost) mezi prvky a v níž jsou axiomaticky zavedeny některé vlastnosti operací vytvářejících logické funkce příslušného úplného souboru. • Podle principu substituce můžeme potom nahrazovat logické výrazy, které jsou si ekvivalentní (rovné).
Axiomy •1*1=1 •1*0=0*1=0 •0*0=0 •0+0=0 •0+1=1+0=1 •1+1=1 •0=1 •1=0
Zákony • • • • • • • •
Zákon Komutativní Asociativní Distributivní Vyloučení třetího Agresivnosti 0 a 1 Neutrálnosti 0 a 1 Absorbce
• Absorbce negace • Dvojité negace • De Morganovy zákony Zdroj: Autor
Součet A+B=B+A A + (B + C) = (A + B) + C (A + B) . (A + C) = A + (B . C) A + not(A) = 1 A+1=1 A+0=A A+A=A A+A.B=A A . (not(A) + B) = A . B not(A). (A + B) = not(A) . B not(not(A))= A not(A + B) = not(A) . not (B)
Součin A.B=B.A A . (B + C) = (A . B) .C A . B + A . C = A . (B + C) A . Not(A) = 0 A.0=0 A.1=A A.A=A A . (A + B) = A A + not(A) . B = A + B not(A) + A . B = not(A) + B not(not(A)) = A not(A . B) = not (A) + not(B)
Booleova algebra • Booelova algebra je jediná soustava pravidel a zákonů (viz. tabulka), která slouží k popisu vztahů mezi dvouhodnotovými logickými proměnnými. • V podstatě se jedná o pravidla popisují nejčastější logické operace. • Používají se zde tři logické funkce: • negace, • konjunkce, • disjunkce.
Disjunkce • Logická disjunkce (používají se pro ni symboly OR nebo ) je binární logická operace jejíž hodnota je pravda, právě když alespoň jedna vstupní hodnota je pravda. • V logice a matematice je disjunkce označením pro „nebo“. • Například „ Prší nebo svítí slunce.“ je disjunkce.
A
B
Y=A+B
0
0
0
0
1
1
1
0
1
1
1
1
Zdroj: Autor
Konjunkce • Logická konjunkce (používají se pro ni symboly AND, & nebo ) je binární logická operace jejíž hodnota je pravda, právě když obě vstupní hodnoty jsou pravda. • V logice a matematice je konjunkce označením pro „a“. • Například „Prší a zároveň svítí slunce.“ je konjunkce.
A
B
Y=A·B
0
0
0
0
1
0
1
0
0
1
1
1
Zdroj: Autor
Negace • Negace výroku (graficky ¬, ′; textově non či not) je v matematické logice opačná pravdivostní hodnota k výroku. • V logice a matematice je negace označením pro „not“.
A
Y=A
0
1
1
0
Zdroj: Autor
Výlučný logický součet • Exkluzivní disjunkce (někdy též vylučovací nebo, exkluzivní OR či zkratkou XOR) je logická operace, jejíž hodnota je pravda, právě když každá vstupní hodnota nabývá, v porovnání s ostatními vstupy, unikátní hodnotu. • V logice a matematice je exkluzivní disjunkce označením pro „buď …, anebo …“. • Například „Počítač je buď zapnutý, anebo vypnutý.“ je exkluzivní disjunkce. A
B
Y=A⊕B
0
0
0
0
1
1
1
0
1
1
1
0
Zdroj: Autor
Logická funkce NAND • Logický člen neboli hradlo je základní stavební prvek logických obvodů, který vyčísluje logickou funkci. • Typicky má jeden či více vstupů a jediný výstup.
A
B
Y=A nand B
0
0
1
0
1
1
1
0
1
1
1
0
Zdroj: Autor
Logická funkce NOR • Logický člen neboli hradlo je základní stavební prvek logických obvodů, který vyčísluje logickou funkci. • Typicky má jeden či více vstupů a jediný výstup.
A
B
Y=A+B
0
0
1
0
1
0
1
0
0
1
1
0
Zdroj: Autor
Implikace • Logická implikace je logická operace se dvěma proměnnými (binární operace), jejíž hodnota je nepravda, právě když hodnota první proměnné je pravda a druhá je nepravda. • Označuje se symbolem nebo →, který naznačuje, že implikace není komutativní čili obě proměnné nelze zaměnit. • Příklad: „ Jestliže je číslo x dělitelné čtyřmi, pak je i dělitelné dvěma.“ je implikace. A
A B
B 0
0
1
0
1
1
1
0
0
1
1
1
Zdroj: Autor
Ekvivalence • Název ekvivalence je v logice používán pro binární logický operátor značený symbolem ⇔ nebo ↔. • Významově odpovídá tento operátor větné konstrukci "právě když" nebo také "tehdy a jen tehdy, když" — ekvivalence tedy říká, že spojovaná tvrzení platí pouze zároveň (obě ano, nebo obě ne). • Příklad: „ Zpěvačky jsou úspěšné právě tehdy, když jsou hezké.“ je ekvivalence. A
A⇔B
B 0
0
1
0
1
0
1
0
0
1
1
1
Zdroj: Autor
Výrokové formule • V matematice a logice se pojmem výroková logika označuje formální odvozovací systém, ve kterém atomické formule tvoří výrokové proměnné. • Tautologie je výroková formule, která je vždy pravdivá. • Kontradikce je výroková formule, která je vždy nepravdivá.
Příklad • Určete pravdivostní ohodnocení formule ABAB.
A
B
A
B
AB
1
1
0
0
0
0
1
1
0
0
1
0
1
1
0
1
1
0
1
0
0
0
0
1
1
0
0
1
Zdroj: Autor
AB ABAB
Úlohy • Sestavte pravdivostní tabulku a rozhodněte, zdali se jedná o tautologii nebo kontradikci. • • • • • • • •
(AB)(AB) (AB)(BA) (AB)(AB) (AB)(AC) (BC)(AC) (AC)B (AB)(AB) (XY)Z(XZ)Y
Zdroje • Booleova algebra. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2013 [cit. 2013-07-16]. Dostupné z: http://cs.wikipedia.org/wiki/Booleova_algebra. • DVOŘÁČKOVÁ, Petra. Booleova algebra [online]. Brno, 2012 [cit. 2013-07-16]. Dostupné z: https://is.muni.cz/th/322248/pedf_b/ Booleova_algebra.pdf. Bakalářská práce. Masarykova univerzita. • KLIMEŠ, Cyril. Booleova algebra [online]. 2012 [cit. 2013-07-16]. Dostupné z: http://www1.osu.cz/~klimesc/public/files/Pocitacove% 20systemy/Prednasky/04%20-%20Booleova%20algebra.pdf. • ŠTĚPÁNEK, Luboš. Booleova algebra [online]. 2013 [cit. 2013-07-16]. Dostupné z: http://mks.mff.cuni.cz/library/BooleovaAlgebraLS/ BooleovaAlgebraLS.pdf. • ŽÁČKOVÁ, Lucie. Booleova algebra. Logické řízení [online]. 2007 [cit. 2013-07-16]. Dostupné z: http://195.178.89.122/CAAC_PHP/CAAC/ cesky/logrizen/b_algebra/b_algebra.php.
