ZÁKLADNÍ POJMY VÝROKOVÉ LOGIKY
Výrok je každé sdělení, o němž má smysl říci, že je buď pravdivé nebo nepravdivé.
Pozn. Není důležité, zda o pravdivosti či nepravdivosti výroku umíme rozhodnout. Podstatné je, zda má smysl o pravdivosti uvažovat, zda má smysl položit si otázku: „Je pravda, že...?"
Rozhodněte, které z následujících vět jsou výroky:
1. Právě začalo pršet.
2. Na Marsu existují živé organismy.
3. Karel IV. byl v Praze r. 1348.
4. Rozvoj matematických představ.
5. Pojď k tabuli.
6. Číslo 4 je dělitelem čísla 134.
7. 100:5 = 20
8. 4 + x = 9
Ve výrokové logice nás nezajímá konkrétní obsah výroků, ale jejich pravdivost (pravdivostní hodnota).
Každému výroku je možné přiřadit pravdivostní hodnotu:
Je-li výrok pravdivý, je jeho pravdivostní hodnota 1.
Je-li výrok nepravdivý, jeho pravdivostní hodnota je 0.
Negace výroku A je výrok 7A, který je pravdivý v případě, že výrok A je nepravdivý.
Složené výroky
Z jednoduchých výroků můžeme tvořit složené výroky pomocí tzv. výrokotvorných spojek:
- „a", „a současně", „a zároveň" (a)
- „nebo" (v)
- „buď, nebo" (V)
- Jestliže, pak"; „A implikuje B " (^>)
- „právě tehdy, když" (<=>)
Konjunkce výroků A, B je výrok A a B, který je pravdivý v případě, že jsou oba výroky pravdivé.
Disjunkce (alternativa) výroků A, B je výrok A vB, který je pravdivý v případě, že je alespoň jeden z výroků A, B pravdivý.
Ostrá disjunkce výroků A, B je výrok A V B, který je pravdivý v případě, že je právě jeden z výroků A, B pravdivý.
Implikace výroků A, B je výrok A=> B, který je nepravdivý jen v případě, že první výrok je pravdivý a druhý výrok je nepravdivý. Ve všech ostatních případech je implikace pravdivá.
Ekvivalence výroků A, B je výrok Ao5, který je pravdivý v případě, že oba výroky mají stejnou pravdivostní hodnotu.
Pomocí výrokotvorných spojek můžeme výroky různě skládat a uvažovat pak o jejich pravdivosti (obsah jednotlivých výroků nás nezajímá):
Mluvíme pak o výrokových formulích. Jsou to zápisy, ve kterých se objevují výrokové proměnné A,B, P, Q, .. log. spojky, závorky a to tak, že když dosadíme za výrokové proměnné konkrétní výroky, dostaneme výrok: Např. \AaB) o (lA v/l 5).
Pak nás zajímá, jaké pravdivostní hodnoty nabývá výsledný výrok v závislosti na pravdivosti výroků A, B.
Typy formulí: tautologie, kontradikce, splnitelná výr. formule. Tautologie výrokové logiky - příklady.
Základní množinové pojmy, vztahy mezi množinami, množinové operace
Množina je takový souhrn objektů, že o každém objektu můžeme rozhodnout, zda do uvažovaného souhrnu objektů patří nebo nepatří.
Pro každou množinu A a pro každý objekt a nastane právě jedna ze dvou možností:
buď a e A nebo a gA .
Množina může být určena výčtem prvků nebo pomocí charakteristické vlastnosti, tj. jako obor pravdivosti výrokové formy.
Např. A = {2, 3, 5, 7} = {x e N; x je prvočíslo a x < 10}
Množina A je podmnožinou (částí) množiny B, právě tehdy, když každý prvek množiny A je též prvkem množiny B. Zapisujeme A c B .
Množina A se rovná množině B (značíme A = B) právě tehdy, když každý prvek množiny A je prvkem množiny B a současně každý prvek množiny B je prvkem množiny A.
(Platí tedy: A = B, právě když A c B a B c A.)
Doplněk množiny A vzhledem k základní množině Zje množina všech prvků množiny Z, které nepatří do množiny A.
A' = {xeZ;xčA}
Sjednocení množin A, B je množina prvků, které patří alespoň do jedné z množin A, B.
AuB = {ieZ;xEAvi6B}
Průnik množin A, B je množina prvků, které patří do množiny A a současně do množiny B.
AnB = {ieZ;ieAa eB}
Rozdíl množin A, B je množina, která obsahuje právě ty prvky množiny A, které nepatří do množiny B
A-B = {ieZ;xeAaxěB}
Symetrický rozdíl množin A, B je množina, která obsahuje ty prvky, které patří právě do jedné z množin.
AAB = {;teZ;;teAv xeB }
Množinové situace lze přehledně graficky znázornit pomocí množinových (tzv. Vennových) diagramů. Množiny jsou v nich znázorněny pomocí oblastí roviny ohraničených jednoduchými uzavřenými křivkami. V případě dvou (tří, čtyř, n) množin je základní množina rozdělena na 4 (8, 16, 2n) elementárních polí.
Vlastnosti množinových operací a jejich ověřování.
Kvantifikované výroky. Výrokové formy. Logické úlohy.
Ve školské matematice, ale i běžně v různých životních situacích se používají vyjádření typu
všichni, ne všichni, někdo, nikdo, žádný, každý, kterýkoliv, některý, aspoň jeden apod., která vedle číslovek také vyjadřují počet nebo množství - jsou to tzv. kvantifikátory (v širším smyslu).
V logice vystačíme se dvěma kvantifikátory:
Obecný kvantifikátor (vx - „pro každé x platí ...")
Existenční kvantifikátor (ax - „existuje aspoň jedno x ..., pro které platí ...") Negace kvantifikovaných výroků.
Není pravda, že všichni jsou tady. — Aspoň jeden tady není.
Není pravda, že si všichni umyli ruce. - Aspoň jeden si neumyl ruce.
Není pravda, že někdo neumí zpívat. — Každý umí zpívat.
Není pravda, že někdo tady umí hrát na kytaru. - Nikdo (každý) tady neumí hrát na kytaru.
Výrokové formy.
Sdělení, v nichž se vyskytuje jedna nebo více proměnných. V případě, že za proměnné dosadíme z tzv. definičního oboru výrokové formy, dostaneme z ní výrok.
Obvykle nás zajímá obor pravdivosti výrokové formy, tj. množina prvků, pro něž dostaneme z výrokové formy pravdivý výrok.
Příklady:
Žák X dnes chybí. x+ 10 < 13
(Obor pravdivosti závisí na tom, jak je určen definiční obor)
Z výrokové formy můžeme také dostat výrok, vážeme-li všechny proměnné pomocí kvantifikátorů: obecnéhovnebo existenčního a.
Např. vx e N: x + 10 < 13 (Pro každé přirozené číslo x je ...) je nepravdivý výrok
3x6 N: x+10<13 (Existuje přirozené číslo x takové, že ...) je pravdivý výrok.
Pravidla odvozování
Úsudek - spojení několika výroků, kdy poslední z nich (závěr) se odvozuje z předcházejících (tzv. premis)
Pravidla odvozování - formálně správné úsudky.
Např.
-iX,XV Y
Y
X=> Y,X
Y
Pravidla odvozování používáme při odvozování důsledků z daných předpokladů. Za výrokové proměnné dosazujeme výroky (jednotlivé, složené nebo kvantifikované).
O správnosti těchto úsudku se můžeme přesvědčit pomocí tabulek pravdivostních hodnot příslušných formulí (musí jít o tautologie)
Pozor na NESPRÁVNÝ úsudek, který se často užívá místo (x): -—
Přesvědčte se o jeho nesprávnosti, tj. ohodnoťte výrokovou formuli:
[(X => Y) A -,*] => -iY
Pravidla odvozování predikátové logiky
Podobně, jako se vytvářejí pravidla odvozování výrokové logiky, lze tvořit pravidla odvozování predikátové logiky, tzn., že se v jejich zápisech vyskytují kvantifikované výroky obsahující výrokové formy o několika proměnných.
Na ukázku uvedeme jeden jednoduchý případ. Ověříme, že následující zápis je zápisem pravidla odvozování:
(V^6D)[i4(x)=>B(x)],(3^e£>)[i4(^)] (3xED)[B(x)]
Připomeňme, že vedení úvah o pravidlech odvozování predikátové logiky je rozsáhlé a značně komplikované (zejména uvažujeme-li výrokové formy o více proměnných). Závěry o těchto pravidlech se však většinou opírají o již připomenutá pravidla odvozování výrokové logiky (větší rozsáhlost možností je dána možnou volbou kvantifikátorů.
Příklady
1. Kdo se dobře učil, stal se váženým člověkem. Nejsem vážený člověk, tedy jsem se dobře neučil. (P)
2. Kdo se dobře učil, stal se váženým člověkem. Jsem vážený člověk, tedy jsem se dobře učil. (N)
3. Žádný student není bohatý člověk a někteří moudří lidé nejsou bohatí. Odtud plyne, že někteří studenti jsou moudří lidé. (N)
4. Každý student je moudrý člověk a někteří studenti jsou bohatí. Odtud plyne, že někteří moudří lidé jsou bohatí. (P)
5. Každý levný výrobek je dobře prodejný a některé levné výrobky jsou kvalitní. Odtud plyne, že některé dobře prodejné výrobky jsou kvalitní. (P)
6. Každý duševně zdravý člověk může studovat logiku, přičemž žádný z Karlových přátel ji studovat nemůže. Potom žádný z Karlových přátel není duševně zdráv. (P)
Binární relace v množině, vlastnosti binárních relací, ekvivalence, uspořádání.
Binární relace v množině M je libovolná podmnožina kartézského součinu M x M.
Znázornění binárních relací
Kartézský graf relace R - sestrojíme dvě na sebe kolmé přímky x, y (vodorovnou a svislou). Na vodorovnou přímku (osu) znázorníme pomocí bodů všechny prvky množiny, z níž vybíráme první složky dvojic, na svislou přímku (osu) znázorníme pomocí bodů všechny prvky množiny, z níž vybíráme druhé složky dvojic. (Obvykle jsou sousední body na obou osách od sebe stejně vzdáleny.) Uspořádanou dvojici [<2,Z?]eR znázorníme bodem, který je průsečíkem dvou přímek procházejících body a, b a rovnoběžných po řadě se svislou a vodorovnou osou.
Uzlový graf relace R v množině M - v rovině znázorníme pomocí bodů (tzv. uzlů) všechny prvky množiny M (pokud bychom znázorňovali relaci z množiny A do množiny B, pak znázorníme všechny prvky sjednocení množina A a B). Uspořádanou dvojici [a,b]eR znázorníme pomocí šipky (tzv. orientované hrany), která vychází z uzlu a a směřuje do uzlu b. V případě, že <2 = b, nazýváme šipku smyčkou. Pokud sou v relaci R dvojice [a,b] a [b,a], znázorníme je "dvojšipkou" (tzv. neorientovanou hranou).
Vlastnosti relací v množině M
Binární relace R v množině M je reflexivní právě tehdy, když
(vxeM) ([x,x]eR), tzn. obsahuje všechny uspořádané dvojice [x,x], kde xeM.
Binární relace R v množině M je antireflexivní právě tehdy, když
(vxeM) ([x,x]gR), tzn. neobsahuje žádnou uspořádanou dvojici typu [x,x], kde xeM.
Binární relace R v množině M je symetrická právě tehdy, když
(vx,yeM) ([x,y]eR => [y,x]eR), tzn. s každou uspořádanou dvojicí [x,y] obsahuje i dvojici ([y,x].
Binární relace R v množině M je antisymetrická, právě tehdy, když
(vx,yeM) ((x * y a [x,y]eR) =*[y,x]gR), tzn. s žádnou dvojicí [x,y] různých prvků neobsahuje dvojici [y,x]. Binární relace R v množině M je tranzitivní právě tehdy, když
(vx,y,zeM) ([x,y]eR a [y,z]eR) => [x,z]eR),
tzn. jestliže se v relaci vyskytují „na sebe navazující dvojice", pak musí relace obsahovat i dvojici, jejíž první složkou je 1. složka z první dvojice a druhou složkou je 2. složka z druhé dvojice.
Binární relace R v množině M je souvislá právě tehdy, když
(vx,yeM) (x * y => ([x,y]eR v [y,x]eR),
tzn. každé dva různé prvky z množiny M musí být „spolu v relaci".
Binární relaci U v množině M nazýváme ostré lineární uspořádání v M, právě když je antisymetrická, tranzitivní, souvislá a antireflexivní.
Pro každou ostře lineárně uspořádanou množinu platí, že každý její prvek má jednoznačně stanovené pořadí.
První a poslední prvek ostře lineárně uspořádané množiny.
Uspořádaná množina je dobře uspořádaná, jestliže každá její neprázdná podmnožina má první prvek. Každá konečná ostře lineárně uspořádaná množina je dobře uspořádaná.
Binární relaci R v množině M nazýváme relací ekvivalence na M, právě když je reflexivní, symetrická a tranzitivní.
Každá relace ekvivalence na množině M vytváří rozklad této množiny, což je systém neprázdných podmnožin (tzv. tříd rozkladu) množiny M takových, že průnik každých dvou tříd je prázdná množina a sjednocení všech tříd rozkladu tvoří množinu M.
Jinak lze také říci, že říci, že rozklad množiny M je systém neprázdných podmnožin (tzv. tříd rozkladu) množiny M takových, že každý prvek množiny M patří právě do jedné z těchto tříd.
Zobrazení z množiny do množiny, typy zobrazení
Nechť R je relace z množiny A do množiny B splňující vlastnosti: Ke každému prvku aeA existuje nejvýše jeden prvek beB takový, že [a,b] e R. Tato relace se nazývá zobrazení z množiny A do množiny B. Značíme R: A —>• B.
Nechť R je zobrazení z množiny A do množiny B.
■ Jestliže [a,b] e R, pak prvek a e A nazýváme vzorem prvku b e B v zobrazení R; prvek b eB nazýváme obrazem prvku aeAv zobrazení R.
■ Množina Oi(R) = {a e A: existuje b e B takové, že [a,b] e R} se nazýva definiční obor zobrazení R. Platí Oi(R) <z A.
■ Množina C>2(R) = {beB: existuje aeA takové, že [a,b] e R} se nazýva obor hodnot zobrazení R. Platí 02(R) cz B.
Příklad. Jsou dány množiny A = {x, y, z}, B = {a, b}. Rozhodněte, zda dané relace z množiny A do množiny B jsou zobrazení z A do B, případně určete definiční obor a obor hodnot zobrazení.
a) Ri = {[x,a], [y,b], [z,a], [z,b]},
b) R2={[x,a], [z,b]},
c) R3 = {[x,a], [y,a], [z,a]}.
Rozlišujeme následující typy zobrazení R:
I) Je—li Oi(R) = A a 02(R) c B a (^(R) ^ B, nazývá se R zobrazení množiny A do množiny B.
II) Je-li Oi(R) c A a Oi(R) f A a 02(R) = B, nazývá se R zobrazení z množiny A na množinu B.
III) Je-li Oi(R) = A a 02(R) = B, nazývá se R zobrazení množiny A na množinu B.
IV) Je-li Oi(R) c A a Oi(R) ± A a 02(R) c B a 02(R) íf B, nazývá se R zobrazení z množiny A do množiny B.
Příklad. Jsou dány množiny A = {x, y, a, c}, B = {c, x, b, z}.
a) Rozhodněte, o jaký typ zadaných zobrazení se jedná?
1) R={[x,z], [c,c], [y,c]}.
2) S = {[x,z], [y,z], [a,z], [c,x]}.
b) Zapište výčtem prvků jednu binární relaci z množiny A do množiny B, která není zobrazením.
c) Zapište výčtem prvků
1) jedno zobrazení Ri typu z množiny A do množiny B,
2) jedno zobrazení R2 množiny A do množiny B,
3) jedno zobrazení množiny A na množinu B,
4) jedno zobrazení z množiny A na množinu B.
Zobrazení R z množiny A do množiny B se nazývá prosté právě tehdy, když relace R"1 je zobrazení z množiny B do množiny A.
Důsledek: Zobrazení R z množiny A do množiny B je prosté právě tehdy, když
a) ke každému y fB existuje nejvýše jedno x e A takové, že [x,y] e R,
b) ke každým dvěma různým vzorům xi, x2 e A přiřadíme dva různé obrazy yi, y2 e B v zobrazení R.
Hovoříme pak o:
■ Prostém zobrazení množiny A do množiny B,
■ Prostém zobrazení z množiny A na množinu B,
■ Prostém zobrazení množiny A na množiny B,
■ Prostém zobrazení z množiny A do množiny B.
Prosté zobrazení množiny A na množinu B nazýváme bijektivní zobrazení nebo také vzájemně jednoznačné zobrazení.
Příklad . Jsou dány množiny A = {1,2,3,4},B = {a, b, c, d}. Rozhodněte, o jaký typ zobrazení se jedná a zdaje toto zobrazení prosté:
a) Ri={[l,a], [2,c], [3,d]},
b) R2 = {[l,a], [2,c], [3,d], [4,a]},
c) R3={[2,a],[l,c], [3,b], [4,d]}.
Permutací konečné množiny A nazýváme každé prosté zobrazení množiny A na množinu A (vzájemně jednoznačné zobrazení).
Příklad. Zapište všechny permutace tříprvkové množiny A = {x, y, z}.
Definice: Nechť R je zobrazení z množiny M do množiny N a S je zobrazení z množiny N do množiny K. Pak relace R o S je zobrazení a nazývá se složené zobrazení ze zobrazení R a S.
Příklad. Složte permutace P2 o P3, P3 o P2, P4 o P6 z předchozího příkladu..
Řekneme, že množiny A, B jsou ekvivalentní právě tehdy, když existuje prosté zobrazení množiny A na množinu B. Značíme A ~ B.
Příklad: Dány množiny A = {a, b, c}, B = {x, y}, C = {1, 2, 3}. Rozhodněte, které množiny jsou ekvivalentní.
R: Množiny A, B nejsou ekvivalentní (neexistuje prosté zobrazení množiny A na množinu B). Množiny A, C jsou ekvivalentní (existuje prosté zobrazení množiny A na množinu C, například R = {[a,3],[b,l],[c,2]}), tj. A ~ C.
Množina M je vlastní podmnožinou množiny N právě tehdy, když M je podmnožinou N a současně M ^ N.
Řekneme, že množina A je konečná právě tehdy, když žádná vlastní podmnožina množiny A není ekvivalentní s množinou A.
Řekneme, že množina B je nekonečná právě tehdy, když existuje alespoň jedna vlastní podmnožina množiny B, která je ekvivalentní s množinou B.
Příklad. Uvažujme množinu N všech přirozených čísel a množinu S všech kladných sudých čísel. Zjistěte, zda jsou ekvivalentní.
Řešení: Připomeneme, žeN = {1, 2, 3, 4, 5,...}, S = {2, 4, 6, 8 , 10,...}. Uvažujme relaci R = {[x,y] e N x S; y = 2x}.
Relace R je prosté zobrazení množiny N na množinu S, neboť ke každému x e N existuje právě jedno y e S takové, že [x,y] e R, ke každému y e S existuje právě jedno x e N takové, že [x,y] e R. Tedy N ~ S.
Množina N všech přirozených čísel je nekonečná, neboť je ekvivalentní s množinou S všech kladných sudých čísel, přičemž S je vlastní podmnožinou množiny N.
Nechť A, B jsou konečné množiny. Pak platí: A ~ B <=> \A \ = \B | , tedy dvě konečné množiny jsou ekvivalentní, právě když mají stejný počet prvků.
Binární operace v množině
Definice 1: Nechť M je libovolná neprázdná množina. Binární operací o v množině M rozumíme zobrazení z množiny kartézského součinu M x M do množiny M.
•  Jestliže v binární operaci je vzoru [x,y] e M x M přiřazen obraz z e M, píšeme:
1. x o y = z; prvek z e M se nazývá výsledek operace o.
2. o:MxM^M.
Poznámka 1. Zápisu [[x,y], z] e o, odpovídá zápis x o y = z (tj. z je výsledek operace o).
Příklad 1. a) Zápisu [[1,2], 3] e +, odpovídá 1 + 2 = 3 (tj. 3 je výsledek operace sčítání čísel 1 a 2). ^^^^
b) Zápisu [[2,3], 6] e •, odpovídá 2 • 3 = 6 (tj. 6 je výsledek operace
Poznámka 2. Označení binárních operací: +, •, o, *,
Příklady binárních operací ve školské matematice:
1) Sčítání (+), odčítání (-), násobení (•), dělení (:), umocňování,... (pracujeme s nimi v číselných množinách).
2) Sjednocení (), průnik (), rozdíl ( - ), symetrický rozdíl (a) množin,... (pracujeme s nimi v systémech množin).
Určení binární operace: Tabulkou nebo předpisem.
součet
násobení čísel 2 a 3).
součin
Vlastnosti binárních operací:
Definice : Binární operace o v množině M, která má vlastnost, že je definována pro každou uspořádanou dvojici [x,y] e M x M, se nazývá operace neomezeně definovaná v množině M (zkráceně operace definovaná na množině M). Značíme ND.
Symbolicky: (Vije M)(a z £ M)[x o y = z].
Definice: Binární operace o definovaná na množině M (je ND), se nazývá komutativní právě tehdy, když platí:
(\/x, y £ M)[ x O y = y O x].
Značíme K.
Definice: Binární operace o definovaná na množině M, se nazývá asociativní právě tehdy, když platí:
(V x, y, z £ M)[ (x o y) o z = x o (y o z)].
Značíme A.
Definice: Nechť v množině M je definována binární operace o. Existuje-li prvek e e M, pro který platí:
(V x e M)[ xoe = eox = x]. Pak se prvek e £ M nazývá neutrálním prvkem množiny M vzhledem k operaci o.
Značíme EN.
Poznámka. Je-li operace o komutativní, pak v zápisu vlastnosti EN lze vynechat jedna ze dvou stran rovnosti x o e nebo e o x.
Definice : Nechť v množině M je definována binární operace o a nechť e je neutrální prvek množiny M vzhledem k operaci o. Prvek ô £ M nazýváme inverzním prvkem k prvku a £ M v operaci o v množině M právě tehdy, když platí:
ä o a = a o ä = e.
Jestliže (V a e M)(a ä e M)[ ä o a = a o ä = e], řekneme, že ke každému prvku množiny M existuje prvek inverzní vzhledem k operaci o. Značíme El.
Poznámka . Je-li operace o komutativní, pak v zápisu vlastnosti El lze vynechat jedna ze dvou stran rovnosti ä o a = a o ä.
Definice : Říkáme, že binární operace o definovaná na množině M má vlastnost řešitelnost základních rovnic právě tehdy, když platí:
(Va, b e M) )(a x, y e M)[ ao x = b y o a = b]. Značíme ZR.
Poznámka. Je-li operace o komutativní, pak v zápisu vlastnosti ZR lze vynechat jedna z výrokových forem a o x = b nebo y o a = b.
Definice: Nechť v množině M je definována binární operace o. Existuje-li prvek g e M, pro který platí:
(\/xeM)[xo g = gox = g]. Pak se prvek g nazývá agresivním prvkem množiny M vzhledem k operaci o.
Určování vlastností operací
I. Určených předpisem - přímým výpočtem
II. Určených tabulkou:
ND - tabulka zcela vyplněna prvky množiny M
K - tabulka souměrná podle hlavní diagonály
A - kromě výjimek nelze z tabulky přímo poznat - viz dále
EN - existuje řádek a sloupec shodný se záhlavím tabulky
El - v každém řádku a každém sloupci tabulky je neutrální prvek
ZR - v každém řádku i sloupci tabulky jsou všechny prvky množiny M
Agresivní prvek g e M poznáme tak, že v celém jemu příslušejícím řádku i sloupci se vyskytuje pouze prvek g.
Užitečné vztahy: K ^> ND, A ^> ND, El ^> EN (užívají se v obměněném tvaru)
A => (El o ZR) Určování asociatívnosti z tabulek:
1. Pohledem (velmi zřídka)
2. Ověřením všech možných trojic prvků (s využitím cvičení 9 - 13, s. 123 -124)   (těžkopádné a zdlouhavé)
3. Využitím obměny implikace A => ND a implikace A => (El <=> ZR)
4. Podle tvrzení: „ Operace, která splňuje EN a El a ZR a současně není asociativní, existuje na množině o nejméně pěti prvcích".
Užití na příkladech:
ad 1. Např.
0	a	b	c
a	a	a	a
b	a	a	a
c	a	a	a
ad 3. Nej častější případ - rozbor implikace A ^> (El <=> ZR). Je-li u El a ZR rozdílná pravdivostní hodnota, pak operace není asociativní. Jsou-li u El a ZR pravdivostní hodnoty 1, pak postupujeme podle bodu 4 (v písemných pracích jsou zadávány tabulky o maximálně čtyřech prvcích). Jsou-li u El a ZR pravdivostní hodnoty 0, pak je nutno postupovat podle bodu 1 nebo 2. Zpravidla jde o bod 1, kdy určíme asociativnost přímo z tabulky.
Algebraické struktury s jednou operací
Uspořádaná dvojice (M, o), kde M je neprázdná množina, ve které je definována binární operace o, se nazývá algebraická struktura s jednou operací.
Příklad: Příklad algebraických struktur: (N, +), (C, -), (Q - {0}, :), (R, •)
Definice:
I. Algebraická struktura (M, o) se nazývá grupoid právě tehdy, když operace oje neomezeně definovaná v množině M (ND).
II. Grupoid (M, o), jehož operace o je asociativní, se nazývá pologrupa (ND, A).
III. Pologrupa (M, o) taková, že v M existuje neutrální prvek vzhledem k operaci (M, o) a ke každému prvku a e M existuje prvek inverzní ä e M, se nazývá grupa (ND, A, EN, El).
Jestliže v případech L, II., III. je operace o komutativní, pak hovoříme o komutativním grupoidu, komutativní pologrupě, komutativní grupě.
	Vlastnost operace o	Algebraická struktura
(M, o)	ND	Grupoid
	ND K	Komutativní grupoid
	ND A	Pologrupa
	ND A K	Komutativní pologrupa
	ND A EN EI	Grupa
	ND A EN EI K	Komutativní grupa
Příklady algebraických struktur s jednou operací
1. (N, +) ... komutativní pologrupa s neutrálním prvkem e = 0
2. (N, -) ... není ani grupoid
4. (N, ■) ... komutativní pologrupa s neutrálním prvkem e = 1
5. (N, : ) ...není ani grupoid
6. (C, +) ... komutativní grupa
7. (C, -) ... grupoid s vlastností ZR
operace odčítání není K: a - x = b y - a = b, x = a -b y = b + a,
a   b e i   b + aeC, tj. obě rovnice jsou pro lib. a, b e C vždy řešitelné
8. (C, ■) ... komutativní pologrupa
9. (C, : ) ...není ani grupoid
10. (Q, +), (R, +) ... komutativní grupy s neutrálním prvkem
11. (Q, -), (R, -)... grupoid s vlasností ZR
12. (Q, •), (R, •)... komutativní pologrupy
13. (Q,:), (R,:)... není ani grupoid
14. (Q - {0}, •), (R - {0}, •) ... komutativní grupa
Důkazy v komutativní grupě:
a • b = ä • b ,    ä = a,   a-c = b- c=>a = b apod.
C M, ®, O)
0 - SeĹtínž f EN- snuÁciy jbt-VúÁ , Oj   Ä m -CC    cfé&čij'firKÁ. 4. -frnr&u, Q. toa.'jUt.7n't EH -Jieh^tkriy'/srní, /y   ä - á/« ^   6<ü.na.'u»,'jt,rTtJL £
cl.
cc
O:  WA a (*Z)
OD®
o
(tum.)®: höaPi ä k a£aj a El a 2$ Q; NOa^(aM)
OD®
/?vĺ££i'/-ZuJ<   lt£ííits»v'/?>l<.Ĺvli*Á£> fortAto
C a éO, 6-ŕ O, a Ob =oj
•IlÜSrO (kenn.) ® - /Vöa^aZa Sa/a EIa2R O : a/OaA (a#)/ 0Z>®
(M- -LOjjO)- Jt^^sty vicLitjlOfJi' A/D, A, EN, Et, 2R.
\+i')i C**'*'')- / *'"ty^'ty
í
(ť?fo )
Ä O y Y
Nechť/ je vzájemně jednoznačné zobrazení množiny G na množinu H, nechť (G, o), (H, □) jsou alg. struktury (alespoň grupoidy). Pak zobrazení/nazveme izomorfismus (G, o) na (H, □), jestliže platí:
(Vij eG)f(xoy)=f(x)nf(y). Píšeme (G, o) = (H, □).
Nechť (G, o), (H, □) jsou struktury (alespoň grupoidy), nechť (G, o) = (H, □) (tj. obě struktury jsou izomorfní). Pak platí:
1. G ~H.
2. Má-li jedna z operací o, □ některou z vlastností K, A, EN, El, ZR, má tuto vlastnost i druhá z těchto operací.
Obě operace mají tedy tytéž vlastnosti.
3. Obě algebraické struktury (G, o), (H, □) jsou téhož typu. Přiklaď. Nechť G = {a, b, c, d}, H ={1, -1, i, -i}.
0	a	b	c	d
a	a	b	c	d
b	b	a	d	c
c	c	d	b	a
d	d	c	a	b
•	1 -1	i -i
1	1 -1	i -i
-1	-1 1	-i i
i	i -i	-1 1
-i	-i i	1 -1
Množina Hjq množina všech řešení rovnice x4 = 1 v oboru komplexních čísel, operace • na množině Hjq pak „obyčejné" násobení. Kdo není seznámen s komplexními čísly, tomu postačí vědět, že i - i = -1.
Definujeme-li nyní vzájemně jednoznačné zobrazení/množiny G na množinu H předpisem f (a) = l,f(b) = -l,f(c) = i,f(d) = -i, snadno se přesvědčíme pohledem na tabulky, že toto zobrazení je izomorfismus, tedy platí vztah (G, o) = (H, •).