OSTRAVSKÁ UNIVERZITA OSTRAVA PEDAGOGICKÁ FAKULTA
MATEMATIKA ve studiu učitelství 1. stupně základní školy
Vilma Novotná, Bohuslav Pisklák
Ostrava 2003
Obsah I. Úvod do teorie množin a matematické logiky
4
1. Výroková logika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2. Pojem množiny a množinová symbolika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3. Výrokové formy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
4. Množinové vztahy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
5. Množinové operace
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
6. Složené výrokové formy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
7. Obecný a existenční výrok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
II. Kartézský součin a binární relace
13
1. Kartézský součin dvou množin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2. Binární relace v množině . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3. Vlastnosti binárních relací v množině . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
4. Relace ekvivalence a rozklad množiny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
5. Relace uspořádání, uspořádání množiny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
6. Relace zobrazení, zobrazení množin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
III. Binární operace a matematické struktury
22
1. Binární operace v množině a jejich vlastnosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
2. Algebraické struktury s jednou binární operací . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3. Algebraické struktury se dvěma binárními operacemi . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
4. Homomorfismus a izomorfismus algebraických struktur . . . . . . . . . . . . . . . . . . . . . . . . . .
26
IV. Číselné soustavy
29
1. Vyjádření přirozeného čísla v číselné soustavě a převody
. . . . . . . . . . . . . . . . . . . . . . . . .
V. Základy teorie dělitelnosti
29 30
1. Dělitelnost celých čísel, znaky dělitelnosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
2. Největší společný dělitel a nejmenší společný násobek přirozených čísel . . . . . . . . . . . . . . . . .
32
3. Prvočísla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
4. Neurčité rovnice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
VI. Zavedení polookruhu všech přirozených čísel
36
1. Kardinální čísla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
2. Ordinální čísla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
3. Peanova množina . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
4. Slovní úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
2
5. Analytická a syntetická metoda řešení složené slovní úlohy . . . . . . . . . . . . . . . . . . . . . . . .
41
6. Konstrukce oboru integrity celých čísel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
7. Konstrukce tělesa racionálních čísel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
8. Rovnost, rovnice, nerovnost, nerovnice
44
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Přehled některých použitých symbolů
45
Literatura
47
3
I. Úvod do teorie množin a matematické logiky 1. Výroková logika Každé srozumitelné sdělení u něhož dovedeme jednoznačně rozhodnout, zda je pravdivé nebo nepravdivé, přičemž z těchto možností nastane právě jedna, nazýváme výrokem. Pro snadnější práci s výroky a přehlednost využíváme abecedu výrokové logiky. Abecedu výrokové logiky tvoří: • Znaky pro výrokové proměnné: p, q, r, . . . (resp. p1 , p2 , . . . , pn ). Znaky pro konstanty P, N , kde P značí výrok pravdivý a N výrok nepravdivý. • Znaky pro výrokotvorné spojky: ¬, ∧, ∨, ∨, ⇒, ⇔, tj. funktory. • Pomocné znaky: (
), [
], {
}, tj. závorky.
Tvrzení „výrok p je pravdivýÿ označujeme symbolem 1, „výrok q je nepravdivýÿ symbolem 0. (P h(p) = 1; P h(q) = 0). Negací výroku p rozumíme výrok ¬p (čti není pravda, že p), který je nepravdivý, je-li výrok p pravdivý a je pravdivý, je-li p výrok nepravdivý. Konjunkcí výroků p, q rozumíme výrok p ∧ q (čti p a zároveň q), který utvoříme tak, že libovolné výroky p, q spojíme výrokotvornou spojkou „aÿ. Konjunkce p ∧ q je výrok pravdivý, jsou-li oba výroky pravdivé. Disjunkcí výroků p, q rozumíme výrok p ∨ q (čti p nebo q), který utvoříme tak, že libovolné výroky p, q spojíme výrokotvornou spojkou „neboÿ. Disjunkce p ∨ q je výrok pravdivý, je-li aspoň jeden z výroků pravdivý. Ostrou disjunkcí výroků p, q rozumíme výrok p∨q (čti buď p nebo q), který utvoříme tak, že před prvním z výroků umístíme „buďÿ a před druhý z nich pak „neboÿ. Ostrá disjunkce p∨q je výrok pravdivý, je-li právě jeden z výroků pravdivý. Implikací výroků p, q rozumíme výrok p ⇒ q (čti jestliže p pak q), který utvoříme tak, že před první výrok umístíme „ jestližeÿ a před druhý „potomÿ. Implikace p ⇒ q je výrok nepravdivý, je-li první výrok p pravdivý a druhý výrok q nepravdivý. V ostatních případech je impliace pravdivá. Ekvivalencí výroků p, q rozumíme výrok p ⇔ q (čti p právě když q), který utvoříme tak, že libovolné výroky p, q spojíme výrokotvornou spojkou „právě kdyžÿ. Ekvivalence p ⇔ q je výrok pravdivý, mají-li oba výroky stejnou pravdivostní hodnotu. Při slovním vyjádření konjukce, implikace a ekvivalence výroků se používají i další výrokotvorné spojky nebo slovní obraty. U konjukce výroků p ∧ q jsou to „iÿ, „a zároveňÿ, „a současněÿ, „a takéÿ. Implikaci výroků p ⇒ q můžeme zformulovat také „ jestliže p, pak qÿ, „p implikuje qÿ, „z p plyne qÿ, „p je postačující podmínkou pro qÿ, „q je nutnou podmínkou pro pÿ, „q platí tehdy, platí-li pÿ, „p platí jen tehdy, platí-li qÿ. A konečně ekvivalenci výroků p ⇔ q můžeme vyjádřit „výrok p je ekvivalentní s výrokem qÿ, „z p plyne q a zároveň z q plyne pÿ, „p je nutnou a postačující podmínkou pro qÿ, „p platí tehdy a jen tehdy, platí-li qÿ, „p platí právě tehdy, když platí qÿ.
4
Přehledná tabulka výroků výrokové proměnné p p, q p, q p, q
zápis výroku ¬p p∧q p∨q p∨q
název výroku
p, q
p⇒q
negace výroku konjunkce výroků disjunkce výroků ostrá disjunkce výroků implikace výroků
p, q
p⇔q
ekvivalence výroků
Přehledná tabulka pravdivostních hodnot výroků výroky negace konjunkce disjunkce p, q 1 1 1 0 0 1 0 0
¬p 0 0 1 1
p∧q 1 0 0 0
p∨q 1 1 1 0
výrokotvorná spojka není pravda, že ...a ... . . . nebo . . . buď. . . nebo. . .
funktor
jestliže. . . , potom. . . . . . právě když. . .
⇒
ostrá disjunkce p∨q 0 1 1 0
¬ ∧ ∨ ∨
⇔
implikace
ekvivalence
p⇒q 1 0 1 1
p⇔q 1 0 0 1
K dalším základním pojmům patří výroková formule. Výrokovou formulí rozumíme: a) každou výrokovou proměnnou p, q, r, . . ., b) výrokové konstanty P, N , c) jsou-li libovolné výrazy Φ, Ψ výrokovými formulemi, potom i (¬Φ), (Φ∧Ψ ), (Φ∨Ψ ), (Φ∨Ψ ), (Φ ⇒ Ψ ), (Φ ⇔ Ψ ) jsou výrokové formule, d) žádné jiné výrazy výrokové formule nejsou. Příklady výrokových formulí jsou výrazy p ⇔ q, (¬p ∧ q) ⇒ r, (r ⇔ q) ∨ (q ⇒ p), utvořené pomocí výrokové abecedy, pro něž je charakteristické, že funktory spojují dvě výrokové proměnné (konstanty), nebo dvě závorky se dvěma výrokovými proměnnými, nebo závorku se dvěma výrokovými proměnnými a proměnnou atd. Výrazy např. (p ⇒), (p∧) ∨ q utvořené také znaky výrokové abecedy výrokovými formulemi nejsou, neboť není splněna charakteristická vlastnost výše uvedená. Výrokovou formuli o n výrokových proměnných obecně zapisujeme Ψ (p , p2 , . . . , pn ). tautologie Výrokové formule: splnitelná formule kontradikce Tautologií nazýváme výrokovou formuli Ψ (p , p , . . . , pn ), která má tu vlastnost, že z ní vznikne výrok pravdivý pro libovolnou kombinaci pravdivostních hodnot v ní figurujících výrokových proměnných. Značíme ` Ψ (p , p , . . . , pn ). Příklady některých tautologií: (p ∨ q) ⇔ (q ∨ p) [(p ∧ q) ∧ r] ⇔ [p ∧ (q ∧ r)] [(p ∧ q) ∨ r] ⇔ [(p ∨ r) ∧ (q ∨ r)] ¬(p ∧ q) ⇔ ¬p ∨ ¬q ¬(p ∨ q) ⇔ ¬p ∧ ¬q
komutativnost disjunkce asociativnost konjunkce distributivnost disjunkce vzhledem ke konjunkci zprava
) de Morganovy zákony
Splnitelnou formulí nazýváme výrokovou formuli Ψ (p , p , . . . , pn ) , která má tu vlastnost, že z ní vznikne výrok pravdivý pro libovolnou kombinaci pravdivostních hodnot a výrok nepravdivý pro jinou libovolnou kombi-
5
naci pravdivostních hodnot v ní figurujících výrokových proměnných. Kontradikcí nazýváme výrokovou formuli Ψ (p , p , . . . , pn ), která má tu vlastnost, že z ní vznikne výrok nepravdivý pro libovolnou kombinaci pravdivostních hodnot v ní figurujících výrokových proměnných. Říkáme, že výroková formule Φ je logicky ekvivalentní s výrokovou formulí Ψ , právě když výroková formule Φ ⇔ Ψ je tautologie, což symbolicky zapisujeme ve tvaru Φ ∼ Ψ . 2. Pojem množiny a množinová symbolika Obsah pojmu množina vymezíme intuitivně takto: Množinou budeme rozumět jakýkoliv soubor vzájemně rozlišitelných objektů, které budeme nazývat jejími prvky. Přitom budeme předpokládat, že každá množina je svými prvky jednoznačně určena. Množiny budeme většinou značit velkými latinskými písmeny A, B, C, . . . , Z, jejich prvky pak malými latinskými písmeny a, b, c, . . . Bude-li to zapotřebí, budeme při označování množin a jejich prvků používat také indexů. Např. M1 , M2 , Mn nebo a1 , a2 , an . Výrok „a je prvek množiny Aÿ zapisujeme symbolicky ve tvaru a ∈ A, jeho negaci pak ve tvaru a 6∈ A. Množinu graficky znázorňujeme jako část roviny omezené uzavřenou křivkou, jejíž vnitřní body znázorňují prvky množiny a vnější body prvky, které množině nepatří. Např.
V některých úvahách budeme nadále předpokládat, že množiny, o nichž bude řeč, byly vytvořeny z prvků nějaké předem zvolené množiny Z. Tuto množinu nazýváme množinou základní, resp. univerzální. V matematice vystupují v roli základních množin velmi často např. číselné obory, pro něž zavedeme toto označení: N N0 C Q R
— — — — —
množina množina množina množina množina
všech všech všech všech všech
přirozených čísel bez nuly, přirozených čísel s nulou, celých čísel, racionálních čísel, reálných čísel.
Pro podmnožiny množin C, Q, R se užívá někdy těchto označení, např.: Q+ — Q+ 0 — Q− — Q− 0 —
množina množina množina množina
všech všech všech všech
kladných racionálních čísel, nezáporných racionálních čísel, záporných racionálních čísel, nekladných racionálních čísel.
Při určování konkrétních množin v rámci zvolené základní množiny Z používáme některé z následujících metod: a) Určení množiny výčtem prvků (taxativně). Tato metoda je vhodná pro určování konečných množin, zpravidla s malým počtem prvků. Jsou-li např. x, y, z všechny prvky množiny A a b1 , b2 , . . . , bn všechny prvky množiny B, pak píšeme A = {x, y, z}, B = {b1 , b2 , . . . , bn }. Přitom přepokládáme, že každý prvek množin A, B je uveden ve složených závorkách jen jednou a pořadí, v němž jsou prvky zapsány, je zcela libovolné.
6
b) Určení množiny charakteristickou vlastností všech jejích prvků. Princip spočívá v tom, že určíme vhodnou výrokovou formu V (x), tj. výraz, který obsahuje proměnnou, s oborem proměnnosti Z tak, aby jejím oborem pravdivosti byla právě daná množina. Výroková forma V (x) reprezentuje tu vlastnost, kterou mají právě jen prvky základní množiny Z patřící do definované množiny a žádné jiné. Je-li daná množina A určena výrokovou formou V (x), pak píšeme A = {x ∈ Z; V (x)}. Množinové úvahy se často týkají malého počtu množin. Situace zahrnující dvě, tři, čtyři množiny lze přehledně znázornit systémem přihrádek, kterými jsou Vennovy diagamy pro 2, 3, 4 množiny. Vennovy diagramy jsou standardizovaná grafická přihrádková schémata, která vznikají překřížením uzavřených čar. Při znázornění dvou uzavřených čar musíme vytvořit čtyři části (přihrádky, komponenty), tří čar osm a čtyř uzavřených čar pak šestnáct komponent. Tam, kde je znázornění množin pomocí Vennových diagramů nevhodné, používáme jejich znázornění na číselné ose. Vennovy diagramy pro 2 množiny
Vennovy diagramy pro 3 množiny
Vennovy diagramy pro 4 množiny
3. Výrokové formy Výrokovou formou rozumíme každé sdělení, které obsahuje alespoň jeden neurčený údaj zvaný proměnná. Např. √ a ≤ 10; 7 < ; x + y = 15; p + r + s > 0; 2x + 3 = 1. Z uvedeného vyplývá, že u uvedených výrazů nelze určit jejich pravdivost, resp. nepravdivost. Podle počtu těchto proměnných hovoříme potom o výrokové formě o jedné proměnné, o dvou proměnných, respektive o výrokové formě o n proměnných a označujeme po řadě A(x), B(x, y), V (x1 , x2 , x3 , . . . , xn ). Další úvahy zaměříme na výrokové formy o jedné proměnné x. Každé výrokové formě V (x), chceme-li ji studovat, přiřazujeme tři množiny: množinu O, zvanou obor proměnné x výrokové formy V (x), množinu D, zvanou definiční obor výrokové formy V (x), množinu P , zvanou obor pravdivosti výrokové formy V (x).
7
Obor proměnné x výrokové formy V (x) je množina O všech prvků, které přichází v úvahu jako hodnoty proměnné x figurující ve V (x). Definiční obor výrokové formy V (x) je množina D všech prvků z množiny O, které po dosazení do výrokové formy V (x) za proměnnou x změní V (x) na výrok. Obor pravdivosti výrokové formy V (x) je množina P všech prvků z množiny O, které po dosazení do výrokové formy V (x) za proměnnou x změní V (x) na výrok pravdivý. Obor proměnné x výrokové formy V (x) volíme, zbývající obory určujeme. Z vymezení daných oborů plyne, že D ⊂ O, P ⊂ O, P ⊂ D. 4. Množinové vztahy Nejprve si uveďme, že k množinovým vztahům zařadíme pojmy rovnost a různost množin, množinovou inkluzi a doplněk množiny. Dále pak zavedeme definici potenčního systému. Jestliže dvě množiny obsahují tytéž prvky, pak říkáme, že jsou si rovny a píšeme A = B. Jestliže naopak neplatí, že A = B, pak píšeme A 6= B, přičemž říkáme, že množiny A, B jsou různé. Množina, která neobsahuje žádné prvky, se nazývá prázdná. Množina, která není prázdná, se nazývá neprázdná. Prázdnou množinu zapisujeme symbolicky: ∅ nebo { }; zápis {∅} neoznačuje prázdnou množinu, ale množinu jednoprvkovou, jejímž prvkem je množina prázdná. Množina A je podmnožinou nebo také částí množiny B, což zapisujeme A ⊂ B, právě tehdy, když pro všechny prvky x ze základní množiny Z platí, jestliže x náleží množině A, pak také náleží množině B. Symbolicky: A ⊂ B ⇔ ∀x ∈ Z : x ∈ A ⇒ x ∈ B. Příklad grafického znázornění:
Právě popsaný vztah nazýváme množinovou inkluzí. Jestliže množina A je podmnožinou množiny B a současně jsou tyto množiny různé, pak říkáme, že množina A je vlastní částí nebo vlastní podmnožinou množiny B. Je-li A množina, která je podmnožinou základní množiny Z, pak všechny prvky, které do množiny A nepatří, tvoří množinu A0 , kterou nazýváme doplněk množiny A vzhledem k základní množině Z. Symbolicky:
A0 = {x ∈ Z; x 6∈ A}.
8
Graficky:
Potenčním systémem množiny A nazveme množinu P(A) definovanou vztahem P(A) = {X ⊂ Z; X ⊂ A}. Potenční množina libovolné množiny A je tedy systém množin, jehož prvky jsou právě všechny podmnožiny množiny A a žádné jiné. 5. Množinové operace V tomto článku pojednáme o sjednocení, průniku, rozdílu a symetrickém rozdílu množin. Sjednocením libovolných dvou množin A a B nazýváme množinu A ∪ B definovanou vztahem A ∪ B = {x ∈ Z; x ∈ A ∨ x ∈ B}. Množina A ∪ B obsahuje všechny ty prvky základní množiny, které patří alespoň do jedné z obou množin A a B a žádné jiné. Diagram znázorňující sjednocení A ∪ B:
Průnikem libovolných dvou množin A a B nazýváme množinu A ∩ B definovanou vztahem A ∩ B = {x ∈ Z; x ∈ A ∧ x ∈ B}. Do množiny A ∩ B patří právě všechny ty prvky základní množiny, které jsou současně obsaženy v obou množinách A, B a žádné jiné. Diagram znázorňující průnik A ∩ B:
Množiny A a B se nazývají navzájem disjunktní právě tehdy, je-li A ∩ B = ∅. Rozdílem množin A a B v tomto pořadí nazýváme množinu A \ B definovanou vztahem A \ B = {x ∈ Z; x ∈ A ∧ x 6∈ B}. Z definice vyplývá, že množina A \ B obsahuje právě všechny prvky základní množiny, které náleží množině A a nenáleží množině B a žádné jiné. Diagram znázorňující rozdíl A \ B:
Symetrickým rozdílem libovolných dvou množin A a B v tomto pořadí nazýváme množinu A 4 B definovanou vztahem A 4 B = {x ∈ Z; x ∈ A∨x 6∈ B}.
9
Množina A 4 B obsahuje všechny prvky základní množiny, které náleží právě do jedné z množin A, B a žádné jiné. Diagram znázorňující rozdíl A 4 B:
6. Složené výrokové formy V tomto článku se budeme zabývat výrokovými formami o jedné proměnné. Víme, že výroková forma A(x) je jisté sdělení s jedním neurčeným údajem, který značíme x a nazýváme ho proměnnou. Ke každé výrokové formě A(x), B(x), . . . jsme zavedli obor proměnné O, definiční obor D a obor pravdivosti P nebo A, B, . . . Množina A = {x ∈ D; A(x)} je vyjádřena charakteristickou vlastností prvků a tuto vlastnost určuje výroková forma A(x). Množina D je definiční obor výrokové formy A(x). Množina A = {x ∈ D; A(x)} je tedy obor pravdivosti výrokové formy A(x) . Obdobné platí pro množinu B = {x ∈ D; B(x)}. Spojíme-li výrokové formy o téže proměnné x s týmž definičním oborem D výrokotvornými spojkami, které známe z výrokové logiky, obdržíme konjunkci, disjunkci, ostrou disjunkci, implikaci a ekvivalenci výrokových forem, resp. negaci výrokové formy. Konjunkcí výrokových forem A(x), B(x) o jedné proměnné x s týmž definičním oborem nazýváme výrokovou formu A(x) ∧ B(x) (čti A(x) a zároveň B(x)) o téže proměnné x s týmž definičním oborem, z níž vznikne pravdivý výrok, právě když za proměnnou x dosadíme takový prvek společného definičního oboru, jenž dává pravdivé výroky po dosazení do obou výrokových forem A(x), B(x). Příklad 1: Nechť A(x) : x | 6, B(x) : x ≤ 5. Jejich oborem proměnné O = N, definičním oborem D = N. Množina A = {x ∈ D; x | 6} = {1, 2, 3, 6} je obor pravdivosti výrokové formy x | 6, množina B = {x ∈ D; x ≤ 5} = {1, 2, 3, 4, 5} je obor pravdivosti výrokové formy x ≤ 5. Konjukcí výrokových forem A(x) ∧ B(x) je x | 6 ∧ x ≤ 5. Obor pravdivosti konjukce výrokových forem je {x ∈ D; x | 6 ∧ x ≤ 5} = {1, 2, 3} = A ∩ B. Disjunkcí výrokových forem A(x), B(x) o jedné proměnné x s týmž definičním oborem nazýváme výrokovou formu A(x) ∨ B(x) (čti A(x) nebo B(x)) o téže proměnné x s týmž definičním oborem, z níž vznikne pravdivý výrok, právě když za proměnnou x dosadíme takový prvek společného definičního oboru, jenž dává pravdivé výroky po dosazení aspoň do jedné z výrokových forem A(x), B(x). Příklad 2: Disjunkcí výrokových forem A(x) : x | 6, B(x) : x ≤ 5 s definičním oborem D = N je x | 6 ∨ x ≤ 5. Obory pravdivosti jednotlivých výrokových forem (viz př. 1). Obor pravdivosti disjunkce výrokových forem je {x ∈ D; x | 6 ∨ x ≤ 5} = {1, 2, 3, 4, 5, 6} = A ∪ B. Ostrou disjunkcí výrokových forem A(x), B(x) o jedné proměnné x s týmž definičním oborem nazýváme výrokovou formu A(x) ∨ B(x) o téže proměnné x s týmž definičním oborem, z níž vznikne pravdivý výrok, právě když za proměnnou x dosadíme takový prvek společného definičního oboru, jenž dává pravdivé výroky po dosazení do právě jedné z výrokových forem A(x), B(x). Příklad 3: Ostrou disjunkcí výrokových forem (viz př. 1) je A(x)∨B(x) : x | 6∨x ≤ 5, oborem pravdivosti A(x) ∨ B(x) je {x ∈ D; x | 6∨x ≤ 5} = {4, 5, 6} = A 4 B. Implikací výrokových forem A(x), B(x) o jedné proměnné x s týmž definičním oborem nazýváme výrokovou formu A(x) ⇒ B(x) (čti jestliže A(x), potom B(x)) o téže proměnné x s týmž definičním oborem, z níž vznikne
10
nepravdivý výrok, právě když za proměnnou x dosadíme takový prvek společného definičního oboru, jenž dává po dosazení do výrokové formy A(x) výrok pravdivý a po dosazení do výrokové formy B(x) výrok nepravdivý. Příklad 4: Implikací výrokových forem A(x), B(x) (viz př. 1) je A(x) ⇒ B(x) : x | 6 ⇒ x ≤ 5, oborem pravdivosti A(x) ⇒ B(x) je {x ∈ D; x | 6 ⇒ x ≤ 5} = {1, 2, 3, 4, 5, 7, 8, 9, . . .} = A0 ∪ B = (A \ B)0 . Ekvivalencí výrokových forem A(x), B(x) o jedné proměnné x s týmž definičním oborem nazýváme výrokovou formu A(x) ⇔ B(x) o téže proměnné x s týmž definičním oborem, z níž vznikne pravdivý výrok, právě když za proměnnou x dosadíme takový prvek společného definičního oboru, jenž dává po dosazení do obou výrokových forem A(x), B(x) výroky téže pravdivostní hodnoty. Příklad 5: Ekvivalencí výrokových forem A(x), B(x) (viz př. 1) je A(x) ⇔ B(x) : x | 6 ⇔ x ≤ 5, oborem pravdivosti A(x) ⇔ B(x) je {x ∈ D; x | 6 ⇔ x ≤ 5} = {1, 2, 3, 4, 5, 7, 8, 9, . . .} = (A ∩ B) ∪ (A ∪ B)0 = (A 4 B)0 . Negací výrokové formy A(x) o jedné proměnné x nazýváme výrokovou formu ¬A(x) (čti není pravda, že A(x)), z níž vznikne výrok pravdivý, právě když za proměnnou x dosadíme takový prvek z definičního oboru, jenž dává po dosazení do výrokové formy A(x) výrok nepravdivý. Příklad 6: Negací výrokové formy A(x) (viz př. 1) je ¬A(x) : x - 6, oborem pravdivosti ¬A(x) je {x ∈ D; x - 6} = {4, 5, 7, 8, . . .} = A0 . Stručný přehled o jednotlivých výrokových formách, jejich zápisu a o jejich oborech pravdivosti vyjádřených charakteristickou vlastností i množinovou operací dává následující tabulka: výroková forma zápis konjunkce A(x) ∧ B(x) disjunkce A(x) ∨ B(x) ostrá disjunkce A(x)∨B(x)
obor pravdivosti char. vlastností {x ∈ D : A(x) ∧ B(x)} {x ∈ D : A(x) ∨ B(x)} {x ∈ D : A(x)∨B(x)}
implikace
A(x) ⇒ B(x)
{x ∈ D : A(x) ⇒ B(x)}
ekvivalence
A(x) ⇔ B(x)
{x ∈ D : A(x) ⇔ B(x)}
negace
¬A(x)
{x ∈ D : ¬A(x)}
obor pravdivosti množ. operací A∩B A∪B A4B = = (A \ B) ∪ (B \ A) (A \ B)0 = = A0 ∪ B (A 4 B)0 = (A ∩ B) ∪ (A ∪ B)0 A0
7. Obecný a existenční výrok Z výrokových forem V (x) můžeme vytvořit individuální výroky tak, že za proměnnou x dosadíme libovolné prvky základní množiny Z (oboru proměnné) nebo také tak, že proměnnou x výrokové formy V (x) kvantifikujeme. Kvantifikace se provádí tím způsobem, že před výrokovou formu V (x) předřadíme jedno z následujících tvrzení: „Existuje aspoň jeden prvek x ∈ M , pro nějž platí . . . ÿ. Toto tvrzení se nazývá existenční kvantifikátor a symbolicky jej zapisujeme ∃x ∈ M :. Další možné slovní vyjádření existenčního kvantifikátoru je „Pro aspoň jeden prvek x ∈ M platí . . . ÿ. Tvrzení: „Pro každý prvek x ∈ M platí . . . ÿ nebo „Pro všechny prvky x ∈ M platí . . . ÿ se nazývá obecný kvantifikátor, symbolický zápis: ∀x ∈ M :. Kvantifikujeme-li výrokovou formu V (x) existenčním kvantifikátorem, dostaneme výrok „Existuje aspoň jeden prvek x ∈ M , pro nějž platí V(x)ÿ nebo také „Pro aspoň jeden prvek x ∈ M platí V (x)ÿ, který nazýváme existenční výrok a zapisujeme ∃x ∈ M : V (x). Příklad 1: ∃x ∈ N0 : x < 3. Pravdivostní hodnota existenčního výroku P h( ∃x ∈ N0 : x < 3) = 1. Předřadíme-li před výrokovou formu V (x) obecný kvantifikátor, dostaneme výrok „Pro každý prvek x ∈ M
11
platí V (x)ÿ, který nazveme obecný výrok a zapisujeme ∀x ∈ M : V (x). Příklad 2: ∀x ∈ R: x2 > 0. Pravdivostní hodnota obecného výroku P h( ∀x ∈ R: x2 > 0) = 0. Specifickým příkladem existenčního výroku je tvrzení „Pro právě jeden prvek x ∈ M platí V (x)ÿ nebo „Existuje právě jeden prvek x ∈ M , pro který platí V (x)ÿ. Zápis: ∃!x ∈ M : V (x). Příklad 3: ∃!x ∈ N0 : x2 − 2x = 0. Pravdivostní hodnota existenčního výroku P h( ∃!x ∈ N0 : x2 − 2x = 0) = 0. Negování obecného a existenčního výroku provádíme podle následujícího pravidla: obecný (existenční) kvantifikátor nahradíme existenčním (obecným) kvantifikátorem a negujeme výrokovou formu. Konkrétně: ¬[ ∀x ∈ M : V (x)] ∼ ∃x ∈ M : ¬V (x) ¬[ ∃x ∈ M : V (x)] ∼ ∀x ∈ M : ¬V (x) Příklad 4: ¬( ∀x ∈ R: x2 > 0) ∼ ∃x ∈ R: x2 ≤ 0, P h[ ¬( ∀x ∈ R: x2 > 0)] = 1, ¬( ∃x ∈ N0 : x < 3) ∼ ∀x ∈ N0 : x ≥ 3, P h[ ¬( ∃x ∈ N0 : x < 3)]=0. V souladu s výše uvedeným můžeme nyní uvést symbolický zápis definice množinové inkluze a rovnosti množin: A ⊂ B ⇔ ∀x ∈ Z: x ∈ A ⇒ x ∈ B, A = B ⇔ ∀x ∈ Z: x ∈ A ⇔ x ∈ B, nebo také A = B ⇔ ∀x ∈ Z: (x ∈ A ⇒ x ∈ B) ∧ (x ∈ B ⇒ x ∈ A).
12
II. Kartézský součin a binární relace 1. Kartézský součin dvou množin Uspořádanou dvojicí prvků nazýváme množinu (a, b) definovanou vztahem (a, b) = {{a}, {a, b}}. Prvek a se nazývá první složka a prvek b se nazývá druhá složka uspořádané dvojice. Množina {a, b} udává složky uspořádané dvojice (a, b), množina {a} pak určuje, kterou z těchto složek je nutno chápat jako první. Pro libovolné dvě uspořádané dvojice prvků (a, b), (c, d) platí: 1. a 6= b ⇒ (a, b) 6= (b, a), 2. (a, b) = (c, d) ⇔ a = c ∧ b = d. Kartézským součinem libovolných dvou množin A, B v tomto pořadí nazýváme množinu A×B definovanou vztahem A × B = {(x, y); x ∈ A ∧ y ∈ B}. Platí-li A = B, potom A × A = A2 = {(x, y) : x ∈ A ∧ y ∈ A} nazýváme konkrétně druhá mocnina množiny A nebo kartézský čtverec množiny A. Příklad 1: A = {a, 3, p}, B = {0, p}, A × B = {(a, 0), (a, p), (3, 0), . . .}, A × A = {(a, a), (a, 3), (a, p), . . .}. Kartézský součin libovolných dvou množin A, B znázorňujeme grafem a) kartézským, b) uzlovým, c) šachovnicovým. Uveďme si stručný postup při sestrojování jednotlivých grafů a jejich charakteristické znaky v případě, že množiny A, B jsou určeny výčtem prvků. Kartézský graf kartézského součinu A × B: Zvolíme si dvě kolmé přímky, např. vodorovnou a svislou. Na vodorovné přímce znázorníme jednotlivé prvky množiny A jako body, na svislé přímce znázorníme jednotlivé jednotlivé prvky množiny B opět jako body. Potom každým vyznačeným bodem vedeme kolmici k přímce, na níž leží a vyznačíme průsečíky všech takto sestrojených kolmic. Tyto průsečíky jsou obrazy prvků kartézského součinu A × B, tedy znázornění uspořádaných dvojic (x, y) ∈ A × B. Šachovnicový graf kartézského součinu A × B: Zvolíme si dvě kolmé přímky, např. vodorovnou a svislou, a jednotkovou úsečku. Daným prvkům množiny A přiřadíme jednotkové úsečky na vodorovné přímce a jednotlivým prvkům množiny B přiřadíme jednotkové úsečky na svislé přímce. Každým vyznačeným bodem vedeme kolmici na přímku, na níž leží. Dostaneme čtvercovou síť. Každý čtvereček v rovině je obraz prvku kartézského součinu A × B, tedy je obrazem uspořádané dvojice (x, y) ∈ A × B. Uzlový graf kartézského součinu A × B: Výčtem prvků určíme množinu A ∪ B a každý její prvek znázorníme v rovině jako kroužek, kterému říkáme uzel. Jednotlivé uspořádané dvojice (x, y) ∈ A×B znázorníme tak, že vyznačíme kolem uzlu smyčku, eventuelně úsečku se šipkou směřující od uzlu x k uzlu y, jestliže x 6= y. Případně vyznačíme smyčku grafu za předpokladu, že x = y. Úsečky se šipkami nazýváme orientované hrany.
13
Následující tabulka shrnuje obrazy prvků množin A, B a A × B v jednotlivých grafech. název grafu kartézský šachovnicový uzlový
obraz prvku množin A, B bod na příslušné přímce jednotková úsečka na příslušné přímce kroužek, uzel
obraz prvku množiny A × B bod v rovině čtvereček v rovině oblouk se šipkou, orientovaná hrana
Příklad 2: Grafické znázornění kartézského součinu A × B, viz příklad 1. Kartézský graf:
Šachovnicový graf:
Uzlový graf:
A ∪ B = {a, 3, p, 0}
Pro libovolné množiny A, B(A ⊂ Z, B ⊂ Z) platí: A × B = ∅ ⇔ A = ∅ ∨ B = ∅. Pro libovolné množiny A, B, C, D, které jsou podmnožinami základní množiny Z, platí: a) (A ∪ B) × C
=
(A × C) ∪ (B × C),
C × (A ∪ B)
=
(C × A) ∪ (C × B),
(A ∩ B) × C
=
(A × C) ∩ (B × C),
b)
14
C × (A ∩ B)
=
(C × A) ∩ (C × B),
(A − B) × C
=
(A × C) − (B × C),
C × (A − B)
=
(C × A) − (C × B),
c)
d) (A ⊂ B) ∧ (C ⊂ D)
⇒
(A × C) ⊂ (B × D).
Množinové rovnosti uvedené v případě ad a) se nazývají distributivnost kartézského součinu vzhledem ke sjednocení zprava, resp. distributivnost kartézského součinu vzhledem ke sjednocení zleva. Obdobně pojmenujeme množinové rovnosti v případech ad b) i ad c). 2. Binární relace Binární relací V z množiny A do množiny B rozumíme jakoukoliv podmnožinu kartézského součinu A × B. Symbolicky: V ⊂ A × B. Množinu všech prvních složek a uspořádaných dvojic (a, b), které patří do relace V (V ⊂ A × B), nazýváme první obor relace. Symbolicky zapíšeme: O1 (V ) = {a ∈ A; ∃b ∈ B : (a, b) ∈ V }. Množinu všech druhých složek b uspořádaných dvojic (a, b), které patří do relace V (V ⊂ A × B), nazýváme druhý obor relace. Symbolicky zapíšeme: O2 (V ) = {b ∈ B; ∃a ∈ A : (a, b) ∈ V }. Binární relací S v libovolné neprázdné množině M rozumíme jakoukoliv podmnožinu kartézského součinu M × M . Symbolicky: S ⊂ M × M . Množinu všech prvních složek a uspořádaných dvojic (a, b), které patří do relace S, nazýváme první obor relace S v M a značíme O1 (S). Symbolicky: O1 (S) = {a ∈ M ; ∃b ∈ M : (a, b) ∈ S}. Množinu všech druhých složek b uspořádaných dvojic (a, b), které patří do relace S, nazýváme druhý obor relace S v M a značíme O2 (S). Symbolicky: O2 (S) = {b ∈ M ; ∃a ∈ M : (a, b) ∈ S}. V následující části textu budeme pojednávat o binárních relacích v množině, tj. kdy je relace S podmnožinou kartézského součinu M × M (tj. „kartézského čtverceÿ). Typy relací v množině: Prázdnou množinu jakožto binární relaci v libovolné množině M nazýváme prázdnou relací v této množině. Množinu M × M jakožto binární relaci v množině M nazýváme úplnou relací v této množině. Poznámka: Prázdná relace je z hlediska množinové inkluze minimální binární relací, kterou lze v dané množině M definovat. Přitom úplná relace je maximální binární relací, kterou můžeme v dané množině určit. Jednotkovou relací v množině M nazveme relaci SM definovanou vztahem: SM = {(a, b) ∈ M × M ; a = b}.
15
Doplňkovou (komplementární) relací k libovolné relaci S, která je definovaná v množině M , nazveme relaci S 0 určenou vztahem: S 0 = (M × M ) \ S. Inverzní relací k libovolné binární relaci S, která je definovaná v množině M , nazveme relaci S −1 určenou vztahem: S −1 = {(a, b) ∈ M × M ; (b, a) ∈ S}. Relace v množině i relace z množiny do množiny zpravidla znázorňujeme opět grafy: a) kartézským, b) uzlovým, a) šachovnicovým. 3. Vlastnosti binárních relací v množině Vlastnosti binárních relací v množině: Relace R v množině M se nazývá reflexivní, právě když pro každý prvek x z množiny M platí: (x, x) ∈ R. Relace R v množině M se nazývá antireflexivní, právě když pro každý prvek x z množiny M platí: (x, x) 6∈ R. Relace R v množině M se nazývá symetrická, právě když pro každé dva prvky x, y z množiny M platí: (x, y) ∈ R ⇒ (y, x) ∈ R. Relace R v množině M se nazývá antisymetrická, právě když pro každé dva prvky x, y z množiny M platí: [x 6= y ∧ (x, y) ∈ R] ⇒ (y, x) 6∈ R. Relace R v množině M se nazývá tranzitivní, právě když pro každé tři prvky x, y, z z množiny M platí: [(x, y) ∈ R ∧ (y, z) ∈ R] ⇒ (x, z) ∈ R. Relace R v množině M se nazývá konektivní (souvislá), právě když pro každé dva prvky x, y z množiny M platí: x 6= y ⇒ [(x, y) ∈ R ∨ (y, x) ∈ R]. 4. Relace ekvivalence a rozklad množiny Relaci R v množině M nazýváme relací ekvivalence, právě když je reflexivní, symetrická a tranzitivní. Relace R v množině M , pro kterou platí, že O1 (R) = M , se nazývá relací na množině M , vyplývá to z její reflexivnosti. Rozkladem libovolné neprázdné množiny M rozumíme systém podmnožin M1 , M2 , . . ., Mn , . . ., který splňuje následujícíc vlastnosti: • Mi 6= ∅, i = 1, 2, . . . , n, . . ., • M1 ∪ M2 ∪ M3 ∪ · · · ∪ Mn ∪ · · · = M , • Mi ∩ Mj = 0, pro každé i 6= j. M1 , M2 , . . . , Mn , . . . nazýváme třídami rozkladu množiny M . Z uvedeného je zřejmé, že systém podmnožin množiny M může být i nekonečný. Poznámky: Kterákoliv relace ekvivalence definovaná na množině M , vytváří její rozklad. Každý rozklad množiny M indukuje relaci R, která je relací ekvivalence. Jednotlivé třídy rozkladu M vytvořené relací ekvivalence na množině M pojmenujeme třídami ekvivalentních prvků. Shrneme-li: Každá relace ekvivalence R definovaná na množině M vytváří rozklad této množiny a obráceně ke každému rozkladu množiny M přísluší relace ekvivalence R.
16
Příklad: Vytvořte všechny možné rozklady množiny A = {x ∈ C; x ∈ h2, 5)}. Množinu A, která je dána charakteristickou vlastností, můžeme v tomto případě určit i výčtem prvků: A = {2, 3, 4}. K řešení úlohy lze využít potenčního systému množiny A. P(A) = {∅, {2}, {3}, {4}, {2, 3}, {2, 4}, {3, 4}, {2, 3, 4}}, pak A1 = {{2}, {3}, {4}}, A2 = {{2, 3}, {4}}, A3 = {{2, 4}, {3}}, A4 = {{3, 4}, {2}}, A5 = {{2, 3, 4}}. Množiny A1 –A5 splňují všechny podmínky definice. Rozklad A1 nazýváme nejjemnějším a rozklad A5 nejhrubším rozkladem množiny A. Rozklad množiny A na třídy budeme označovat AR . 5. Relace uspořádání, uspořádání množiny Jednotlivé typy uspořádání rozlišujeme na základě souhrnu jistých vlastností binárních relací v množině, viz. kapitola 3. Relace R definovaná v množině A se nazývá relací uspořádání právě tehdy, když je antisymetrická a tranzitivní. Relace R definovaná v množině A se nazývá relací ostrého uspořádání právě tehdy, když je antireflexivní, antisymetrická a tranzitivní; neostrého uspořádání, je-li reflexivní, antisymetrická a tranzitivní. Relace R definovaná v množině A se nazývá relací lineárního uspořádání právě tehdy, když je antisymetrická, tranzitivní a konektivní. Relace R definovaná v množině A se nazývá relací ostrého lineárního uspořádání právě tehdy, když je antireflexivní, antisymetrická, tranzitivní a konektivní; neostrého lineárního uspořádání, je-li reflexivní, antisymetrická, tranzitivní a konektivní. Poznámka: Jestliže relace R definovaná v množině A je antireflexivní, antisymetrická a konektivní, pak ji nazýváme relací trichotomickou. Přičemž antisymetrii a konektivnost můžeme vyjádřit symbolicky: ∀x, y ∈ A : x 6= y ⇒ [(x, y) ∈ R∨(y, x) ∈ R]. Pro přehlednost a srozumitelnost nyní zavedených pojmů uveďme následující tabulku: Typy relací uspořádání: uspořádání ostré uspořádání neostré uspořádání lineární uspořádání ostré lineární uspořádání neostré lineární uspořádání
R / /
AR / / -
S -
AS / / / / / /
T / / / / / /
K / / /
Poznámka: R – reflexivnost, AR – antireflexivnost, S – symetrie, AS – antisymetrie, T – tranzitivnost, K – konektivnost, / – splněná vlastnost.
17
Příklady jednotlivých typů relací, které budou dány výčtem prvků a znázorněny na uzlových grafech. Připomeňme R ⊂ M × M , přičemž M = {3, 4, 5, 6}. a) relace uspořádání: Ra = {(3, 4), (5, 3), (5, 4), (6, 6), (3, 3)},
b) relace ostrého uspořádání: Rb = {(6, 3), (6, 5), (5, 4), (6, 4)},
c) relace neostrého uspořádání: Rc = {(3, 3), (4, 4), (5, 5), (6, 6), (3, 5)},
d) relace lineárního uspořádání: Rd = {(6, 3), (6, 4), (6, 5), (3, 4), (3, 5), (5, 4), (5, 5)},
e) relace ostrého lineárního uspořádání: Re = {(4, 3), (4, 5), (4, 6), (3, 5), (3, 6), (6, 5)},
f) relace neostrého lineárního uspořádání: Rf = {(3, 3), (4, 4), (5, 5), (6, 6), (5, 4), (5, 3), (5, 6), (4, 3), (4, 6), (6, 3)}.
18
Množina A, v níž je definována relace uspořádání se nazývá uspořádaná množina. Množina A, v níž je definována relace lineárního uspořádání R se nazývá lineárně uspořádaná množina. Zapisujeme ji (A, R). Množina A, v níž je definována relace ostrého lineárního uspořádání se nazývá ostře lineárně uspořádaná množina. Ostře linárně uspořádanou množinu zapíšeme p Ap . Je-li R relace uspořádání v množině A, pak okolnost, že prvek a předchází před prvkem b, zapíšeme vztahem: R
a ≺ b. (Prvek a předchází před prvkem b v uspořádání R). Příklad: Je dána množina M = {k, l, m, n} a relace U , jejíž vyjádření znázorňuje uzlový graf:
U
U
U
Pak platí m ≺ l ≺ n ≺ k. U je relace ostrého lineárního uspořádání a pMp = {m, l, n, k} je ostře lineárně uspořádaná množina. První a poslední prvek lineárně uspořádané množiny zavedeme těmito definicemi: Nechť (A, R) je lineárně uspořádaná množina, pak prvek a ∈ A se nazývá první prvek této množiny právě tehdy, když R
∀x ∈ A : x 6= a ⇒ a ≺ x. Nechť (A, R) je lineárně uspořádaná množina, pak prvek b ∈ A se nazývá poslední prvek této množiny právě tehdy, když R
∀x ∈ A : x 6= b ⇒ x ≺ b. V závěru tohoto přehledu základních poznatků se ještě seznámíme s pojmy dobrého uspořádání a dobře uspořádané množiny. Jestliže má každá neprázdná podmnožina lineárně uspořádané množiny (A, R) první prvek, pak množinu (A, R) nazýváme dobře uspořádanou množinou a relaci R dobrým uspořádáním v množině A. 6. Relace zobrazení, zobrazení množin Zde se budeme orientovat na binární relace, které budou podmnožinami kartézského součinu A × B. U vlastností relací (kap. II. 3.), ekvivalence a uspořádání (kap. II. 4.; 5.) jsme se setkávali s uzlovými grafy, které mohly mít více hran než uzlů. Nyní se však zaměříme na relace, kdy z každého uzlu vychází nejvýše jedna orientovaná hrana. Na kartézském grafu se tato vlastnost relací projeví tím, že v každém sloupci grafu A × B leží nejvýše jeden bod grafu dané relace.
19
Relace Z z množiny A do množiny B (Z ⊂ A × B) se nazývá zobrazení z množiny A do množiny B právě tehdy, když je splněna podmínka ∀a ∈ A ∀b1 , b2 ∈ B : [(a, b1 ) ∈ Z ∧ (a, b2 ) ∈ Z] ⇒ b1 = b2 . Tzn., že ke každému prvku a ∈ A existuje nejvýše jeden prvek b ∈ B takový, že platí (a, b) ∈ Z. Prvek a ∈ A nazýváme vzorem a prvek b ∈ B jeho obrazem, je-li relace Z zobrazení. První obor relace O1 (Z), která je zobrazením z množiny A do množiny B nazýváme definičním oborem; druhý obor O2 (Z) této relace pak oborem hodnot. Schematické znázornění relace zobrazení Z z množiny A do množiny B.
Schematické znázornění dalších případů: • Zobrazení Z z množiny A na množinu B.
• Zobrazení Z množiny A do množiny B.
• Zobrazení Z množiny A na množinu B.
Zobrazení Z z množiny A do množiny B se nazývá prosté, právě když Z −1 je zobrazení z množiny B do množiny A. Toto zobrazení Z −1 nazýváme inverzním zobrazením k zobrazení Z. V praxi se zpravidla využívá podmínky: Zobrazení Z z množiny A do množiny B je prosté, jestliže pro každé y ∈ B platí, že je obrazem nejvýše jednoho prvku x ∈ A. Případně, mají-li v zobrazení Z každé dva různé prvky definičního oboru různé obrazy. Prosté zobrazení Z množiny A na množinu B nazýváme také vzájemně jednoznačným zobrazením. Na kartézském grafu je prosté zobrazení charakteristické tím, že v každém sloupci (tj. kolmici k vodorovné přímce, na níž je vyznačena množina A) a rovněž i každém řádku (tj. kolmici ke svislé přímce, na níž je vyznačena množina B) je nejvýše jeden bod grafu. Prosté zobrazení na uzlovém grafu charakterizuje vlastnost — z každého 20
uzlu znázorňujícího prvek množiny A vychází nejvýše jedna orientovaná hrana a do každého uzlu, který znázorňuje prvek množiny B, nejvýše jedna orientovaná hrana vchází. Poznámka: Je-li A = B, pak jde o zobrazení v množině. V matematické literatuře se pro některé typy zobrazení používá termínu surjekce, injekce, bijekce. Konkrétně pak zobrazení množiny A na množinu B nazýváme surjekcí. Prosté zobrazení množiny A do množiny B nazýváme injekcí a prosté zobrazení množiny A na množinu B nazýváme bijekcí. Každé prosté zobrazení konečné množiny A na množinu A (A = B) nazýváme permutací množiny A. V případě, že množina vzorů a obrazů je lineárně uspořádaná a zobrazení Z je prosté, můžeme ještě zavést zobrazení podobné. Budiž (A, R1 ) a (B, R2 ) lineárně uspořádané množiny. Prosté zobrazení Z množiny A na množinu B, která má vlastnost R1 R2 ∀x, y ∈ A : x ≺ y ⇒ Z(x) ≺ Z(y), se nazývá podobné zobrazení (A, R1 ) na (B, R2 ). Schematické znázornění:
Ekvivalence a podobnost množin Množiny A a B jsou ekvivalentní právě tehdy, když existuje prosté zobrazení množiny A na množinu B, což symbolicky zapíšeme: A ∼ B.
Na základě definice ekvivalentních množin lze zavést pojem konečné množiny. Množina M je konečná právě tehdy, když není ekvivalentní s žádnou svou vlastní podmnožinou. Lineárně uspořádané množiny (A, R1 ) a (B, R2 ) jsou podobné právě tehdy, když existuje podobné zobrazení Z lineárně uspořádané množiny (A, R1 ) na lineárně uspořádanou množinu (B, R2 ). Symbolicky zapíšeme (A, R1 ) ≈ (B, R2 ). Jestliže (A, R1 ) a (B, R2 ) jsou dvě lineárně uspořádané množiny a Z podobné zobrazení (A, R1 ) na (B, R2 ), pak platí: Je-li a první prvek (A, R1 ), pak Z(a) je první prvek (B, R2 ); je-li b poslední prvek (A, R1 ), pak Z(b) je poslední prvek (B, R2 ). Poznámka: Každé dvě lineárně uspořádané množiny, které jsou podobné, jsou také ekvivalentní. Obrácené tvrzení neplatí.
21
III. Binární operace a matematické struktury 1. Binární operace v množině a jejich vlastnosti Binární operací ◦ v libovolné neprázdné množině A rozumíme každé zobrazení z množiny A × A do množiny A. Jestliže v binární operaci ◦ přísluší vzoru (a, b) ∈ A × A obraz c ∈ A píšeme a ◦ b = c. Prvek c je výsledkem operace ◦ s prvky a, b v tomto pořadí. Binární operaci v množině můžeme označovat různými symboly, např. ◦, ∗, , 4, ⊕, , ∩, ∪, také +, −, ·, :, atd. Mimo aritmetických operací sčítání (symbol +), odčítání (symbol −), násobení (symbol ·), dělení (symbol :) v číselných množinách jsou operace také zadávány předpisem nebo operační tabulkou. Operační tabulky se užívají zpravidla v konečných množinách, které mají malý počet prvků. Příklad operace ∗ dané předpisem v množině celých čísel C: a ∗ b = a + b − 1. Příklad operace ◦ dané operační tabulkou v množině ◦ k k m l k m l
A = {k, l, m}: l m k l . l m m k
Binární operace ◦ v množině A se nazývá definovaná na množině A (neomezeně definovaná v množině A), právě když má tu vlastnost, že ke každé dvojici prvků a, b ∈ A existuje výsledek operace c ∈ A. Symbolicky: ∀a, b ∈ A ∃c ∈ A : a ◦ b = c. Příklad 1: Sčítání v množině N0 je operace neomezeně definovaná v N0 . Odčítání v množině N0 není neomezeně definovaná operace v N0 , např. 5 − 8 ∈ / N0 . Binární operace definovaná na množině A se nazývá komutativní, právě když ∀a, b ∈ A : a ◦ b = b ◦ a.
Příklad 2: Sčítání v množině C je operace definovaná na množině C a komutativní. Odčítání v C je operace definovaná na množině C, není komutativní, např. 5 − 8 6= 8 − 5. Binární operace definovaná na množině A se nazývá asociativní právě tehdy, když ∀a, b, c ∈ A : (a ◦ b) ◦ c = a ◦ (b ◦ c). Příklad 3: Sčítání v množině C je operace neomezeně definovaná v C, asociativní. Odčítání v množině C je operace neomezeně definovaná v C, není asociativní v C, např. (8 − 5) − 2 6= 8 − (5 − 2). Budiž ◦ libovolná operace definovaná v množině A. Prvek e ∈ A se nazývá neutrální prvek množiny A vzhledem k operaci ◦, právě když ∀a ∈ A : a ◦ e = e ◦ a = a. V množině existuje nejvýše jeden neutrální prvek vzhledem k operaci ◦. Příklad 4: V množině N0 existuje právě jeden neutrální prvek vzhledem k operaci sčítání, je jím přirozené číslo nula. V množině C neexistuje neutrální prvek vzhledem k operaci odčítání. Protikladem neutrálního prvku množiny vzhledem k operaci je agresivní prvek. Budiž ◦ libovolná operace definovaná v množině A. Prvek g ∈ A se nazývá agresivní prvek množiny A vzhledem k operaci ◦, právě když ∀a ∈ A : a ◦ g = g ◦ a = g. Příklad 5: V množině N0 existuje agresivní prvek vzhledem k operaci násobení, je jím 0 ∈ N0 .
22
Budiž ◦ libovolná lineární operace definovaná v množině A a e ∈ A je neutrální prvek množiny vzhledem k operaci ◦. Prvek a ∈ A nazveme inverzní prvek k prvku a ∈ A, právě když platí a ◦ a = a ◦ a = e. Jestliže ◦ je libovolná asociativní operace v množině A, e ∈ A je neutrální prvek množiny A vzhledem k operaci ◦, pak k libovolnému prvku a ∈ A existuje nejvýše jeden inverzní prvek a ∈ A vzhledem k operaci ◦. Příklad 6: Neutrálním prvkem množiny R vzhledem k operaci násobení je číslo 1 ∈ R. Inverzním prvkem například k prvku a = 5 v R je prvek a = 15 ∈ R, platí 5 · 15 = 15 · 5 = 1. K číslu 0 ∈ R neexistuje inverzní prvek vzhledem k operaci násobení. Binární operace ◦ definovaná na množině A má vlastnost řešitelnosti základních rovnic, nebo-li je operací s dělením, právě když ∀a, b ∈ A ∃x, y ∈ A : a ◦ x = b ∧ y ◦ a = b. Nechť ◦, ∗ jsou dvě libovolné operace definované na množině A. Říkáme, že operace ∗ je distributivní vzhledem k operaci ◦, právě když ∀a, b, c ∈ A : (a ◦ b) ∗ c = (a ∗ c) ◦ (b ∗ c) ∧ c ∗ (a ◦ b) = (c ∗ a) ◦ (c ∗ b). První rovnost nazýváme distributivnost zprava, druhou distributivnost zleva. Příklad 7: V množině celých čísel je násobení distributivní vzhledem ke odčítání zleva i zprava. V množině přirozených čísel není sčítání distributivní vzhledem k násobení, např. (3 · 5) + 3 6= (3 + 3) · (5 + 3). Budiž v množině A definována operace ◦. Jestliže k prvkům a, b ∈ A lze jednoznačně přiřadit prvky x, y ∈ A tak, že platí a = b◦x, a = y ◦b, jsou tím v množině A určeny dvě další operace 4, tak, že platí a4b = x, ab = y. Operace 4, se nazývají inverzní operace k operaci ◦ v množině A. Je-li operace ◦ komutativní, potom existuje jediná inverzní operace k operaci ◦. Příklad 8: V množině C je definováno sčítání. Inverzní operací ke sčítání v množině C je odčítání, platí a = b + x ∧ a = y + b, x = y = a − b. 2. Algebraické struktury s jednou binární operací Množina, v níž je definovaná aspoň jedna binární operace, se nazývá algebraická struktura nebo také operační systém. V následujícím se budeme zabývat algebraickými strukturami s jednou binární operací, budeme je značit např. (G, ◦), kde G je libovolná neprázdná množina a ◦ operace v množině definovaná. Příklad 1: (N, +), (C, −), (Q, ·), (R, :) jsou příklady algebraických struktur s jednou binární operací, kde nosičem struktur jsou uvedené číselné množiny. Podle vlastností operace ◦ v množině G zavádíme grupoid, pologrupu, monoid a grupu. Algebraická struktura (G, ◦) se nazývá grupoid, právě když operace ◦ je neomezeně definovaná v množině G. Příklad 2: Algebraická struktura (C, −), (R+ , :) jsou příklady grupoidů, odčítání v C má vlastnost ND v C, dělení v R+ je operace neomezeně definovaná. Grupoid (G, ◦) se nazývá pologrupa, právě když operace ◦ je asociativní. Nebo také Algebraická struktura (G, ◦) se nazývá pologrupa, právě když operace ◦ je ND v G a A.
23
Příklad 3: Algebraická struktura (C, ∗), kde operace ∗ je dána předpisem x ∗ y = x, je pologrupa. (N, +) je komutativní pologrupa, operace + je navíc komutativní. Pologrupa (G, ◦) se nazývá monoid, právě když množina G obsahuje neutrální prvek vzhledem k operaci ◦. Nebo také: Algebraická struktura (G, ◦) se nazývá monoid, právě když operace ◦ je ND v G, A a množina G má neutrální prvek vzhledem k operaci ◦. Příklad 4: Algerbaická struktura (N0 , +), (N, ·), (R, ·) jsou příklady komutativních monoidů, operace v daných číselných množinách mimo vyjmenovaných vlastností jsou ještě komutativní. Monoid (G, ◦) se nazývá grupa, právě když ke každému prvku a ∈ G existuje inverzní prvek a ∈ G. Nebo také: Algebraická struktura (G, ◦) se nazývá grupa, právě když operace ◦ v množině G je ND, A, množina G má neutrální prvek vzhledem k operaci ◦ a ke každému prvku množiny G existuje inverzní prvek v G. Příklad 5: Algebraické struktury (C, +), (Q, +), (R, +), (R, ◦), kde operace ◦ je dána předpisem x ◦ y = x + y − 1, jsou příklady komutativních grup (operace v daných množinách jsou ještě i komutativní). Přehled algebarických struktur s jednou operací: Vlastnosti operace ◦: ND — ke každým dvěma prvkům x, y ∈ G existuje x ◦ y ∈ G, A — operace je asociativní, N — množina G obsahuje neutrální prvek vzhledem k operaci ◦, I — ke každému prvku a ∈ G existuje inverzní prvek a ∈ G operace ◦.
Je-li operace ◦ na množině G ještě komutativní, pak struktury nazýváme komutativním grupoidem, komutativní pologrupou, komutativním monoidem, komutativní grupou. Příklady struktur, kde nosičem jsou číselné množiny, k nimž přísluší aritmetické operace +, −, ·, : N N0 C Q R
+ kom. pologrupa kom. monoid kom. grupa kom. grupa kom. grupa
− — — grupoid grupoid grupoid
kom. kom. kom. kom. kom.
· monoid monoid monoid monoid monoid
: — — — — —
3. Algebraické struktury se dvěma binárními operacemi Nechť M je libovolná neprázdná množina a ◦, ∗ jsou dvě různé binární operace v ní definované. V algebraické struktuře se dvěma operacemi (M, ◦, ∗) budeme operaci ◦ nazývat aditivní operací (nebo sčítání), operaci ∗ multiplikativní operací (nebo násobení). Neutrální prvek množiny M vzhledem k aditivní operaci ◦ nazveme nulovým prvkem množiny M a označíme symbolem h (nebo cifrou 0), neutrální prvek množiny M vzhledem k operaci ∗ nazveme jednotkovým prvkem a označíme jej j (nebo cifrou 1). A konečně inverzní prvek a ∈ M k
24
prvku a ∈ M vzhledem k operaci ◦ nazveme opačným prvkem a zapíšeme a = −a, inverzní prvek b ∈ M k prvku b ∈ M vzhledem k operaci ∗ nazveme převráceným prvkem a zapíšeme b = 1b = b−1 . Příklad 1: Algebraická struktura se dvěma operacemi je např. (R, ◦, ∗), kde operace jsou dány předpisem x ◦ y = x + y + 1, x ∗ y = x + y + xy. Struktura má nulový prvek h = −1, jednotkový prvek j = 0, opačným prvkem např. k číslu 5 je 5 = −7, převráceným prvkem k číslu 5 je 5 = − 56 . Podle vlastností obou operací definovaných v množině M zavádíme polookruh, okruh, obor integrity a těleso. Algebraická struktura (M, ◦, ∗) se nazývá polookruh, právě když aditivní operace ◦ je ND v M , K, A, multiplikativní operace ∗ je ND v M , A, D vzhledem k operaci ◦. Je-li operace ∗ K, potom (M, ◦, ∗) je komutativní polookruh. Příklad 2: Struktury (P(M ), ∪, ∩), (P(M ), ∩, ∪), (N, +, ·) jsou komutativní polookruhy. Polookruh (M, ◦, ∗) se nazývá okruh, právě když jeho aditivní komutativní pologrupa je grupa. Je-li operace ∗ komutativní, potom (M, ◦, ∗) je komutativní okruh. Příklad 3: Struktura (A, ◦, ∗), kde A = {x ∈ R; x > 0}, operace jsou dány předpisem x ◦ y = x + y − 1, x ∗ y = x + y − xy, je komutativní okruh. Pro další úvahy si zavedeme pojem zbytková třída podle modulu m, kde m je libovolné přirozené číslo větší než jedna. Zbytkovou třídou podle modulu m nazveme množinu všech celých čísel, které při dělení modulem m dávají týž zbytek. Příklad 4: Nechť m = 4. Při dělení libovolného celého čísla modulem 4 může vzniknout zbytek 0 nebo 1 nebo 2 nebo 3. Množinu všech celých čísel, která při dělení 4 dává zbytek nula, nazveme zbytkovou třídou nula (zápis (0)) podle modulu 4, je tedy (0) = {. . . , −12, −8, −4, 0, 4, 8, 12, . . .}. Obdobně obdržíme další zbytkové třídy (1) = {. . . , −11, −7, −3, 1, 5, 9, . . .}, (2) = {. . . , −10, −6, −2, 2, 6, 10, . . .}, (3) = {. . . , −9, −5, −1, 3, 7, 11, . . .}. Množina C4 = {(0), (1), (2), (3)} se nazývá množina zbytkových tříd podle modulu 4. V Cm = {(0), (1), (2), . . . , (m − 2), (m − 1)} zavedeme operace ⊕, předpisem (p) ⊕ (r) = (s), (∗) (p) (r) = (n), kde s resp. n je zbytek při dělení p + r resp. pr modulem m. Příklad 5: V (C4 , ⊕, ) jsou operační tabulky sestrojeny podle předpisů (∗). ⊕ (0) (1) (2) (3)
(0) (0) (1) (2) (3)
(1) (1) (2) (3) (0)
(2) (2) (3) (0) (1)
(0) (1) (2) (3)
(3) (3) (0) (1) (2)
Algebraická struktura (C4 , ⊕, ) je komutativní okruh.
25
(0) (0) (0) (0) (0)
(1) (0) (1) (2) (3)
(2) (0) (2) (0) (2)
(3) (0) (3) (2) (1)
Nechť (M, ◦, ∗) je okruh. Prvky a, b ∈ M , pro které platí a 6= h, b 6= h, a ∗ b = h (h je nulový prvek množiny M vzhledem k operaci ◦) se nazývají dělitelé nuly okruhu M . Příklad 6: Okruh (C4 , ⊕, ) má dělitele nuly (2), dělitelé nuly okruhu (C10 , ⊕, ) jsou (2), (4), (5), (6), (8). Komutativní okruh (M, ◦, ∗), který neobsahuje dělitele nuly, se nazývá obor integrity. Příklad 7: Algebraická struktura (C, +, ·) je obor integrity. Okruh (M, ◦, ∗) mající aspoň dva různé prvky a jehož nenulové prvky tvoří grupu vzhledem k multiplikativní operaci se nazývá těleso. (M \ {h}, ∗) se nazývá multiplikativní grupa tělesa. Je-li operace ∗ komutativní, je (M, ◦, ∗) komutativní těleso. Příklad 8: Algebraické struktury (Q, +, ·), (R, +, ·), (C7 , ⊕, ) jsou komutativní tělesa. Přehled algebraických struktur se dvěma operacemi:
Vysvětlivky ND1 , ND2 K1 , K 2 A1 , A2 D N1 N2 I1 I2 O
neomezená definovanost operací na množině, komutativnost operací, asociativnost operací, distributivnost multiplikativní operace k aditivní operaci, množina obsahuje nulový prvek, množina obsahuje jednotkový prvek, ke každému prvku množiny existuje opačný prvek, ke každému prvku množiny mimo nulový prvek existuje převrácený prvek, neexistují dělitelé nuly.
4. Homomorfismus a izomorfismus algebraických struktur Nechť jsou dány dva grupoidy (A, ◦), (B, ∗). Zobrazení ϕ množiny A na množinu B (surjekce) nazýváme homomorfním zobrazením (homomorfismem) grupoidu (A, ◦) na grupoid (B, ∗), právě když ∀a, b ∈ A : ϕ(a◦b) = ϕ(a)∗ϕ(b). Poznámka: Vlastnost surjekce danou obecným výrokem můžeme slovně zformulovat: pro každé dva prvky množiny A (množiny vzorů) platí: obraz výsledku operace se vzory se rovná výsledku operace s obrazy. Příklad 1: Homomorfním obrazem komutativního monoidu (N0 , ·) je komutativní monoid (C4 , ). Schématicky můžeme homomorfismus grupoidů znázornit takto:
26
Ze znázornění je patrné, že grupoid (A, ◦) je homomorfním obrazem grupoidu (B, ∗). Nechť (A, ◦), (B, ∗) jsou libovolné dva grupoidy a ϕ libovolné homomorfní zobrazení (A, ◦) na (B, ∗). Pak platí: (a) Je-li operace ◦ komutativní, pak je komutativní také operace ∗. (b) Je-li operace ◦ asociativní, pak je asociativní také operace ∗. (c) Má-li (A, ◦) neutrální prvek e, pak i (B, ∗) má neutrální prvek e0 , přičemž platí e0 = ϕ(e). (d) Nechť (A, ◦), (B, ∗) mají po řadě neutrální prvky e, e0 . Existuje-li k prvku a ∈ A inverzní prvek a ∈ A, pak k prvku ϕ(a) ∈ B existuje inverzní prvek ϕ(a) ∈ B, přičemž platí ϕ(a) = ϕ(a). Speciálním případem homomorfního zobrazení je izomorfní zobrazení, které také nazýváme oboustranný homomorfismus. Izomorfní zobrazení zavedeme obdobně: Nechť jsou dány dva grupoidy (A, ◦), (B, ∗). Prosté zobrazení ϕ množiny A na množinu B (bijekce) nazýváme izomorfním zobrazením (izomorfismem) grupoidu (A, ◦) na grupoid (B, ∗), právě když ∀a, b ∈ A : ϕ(a◦b) = ϕ(a)∗ϕ(b) a zapíšeme (A, ◦) ∼ = (B, ∗). Příklad 2: Grupoidy (R+ , :) a (R, −) jsou izomorfní. Bijekce ϕ množiny R+ na množinu R je dána předpisem ϕ(x) = log x a splňuje ∀x, y ∈ R+ : log(x : y) = log x − log y. Schematické zobrazení izomorfismu je analogické znázorněnému homomorfismu, jen vodorovně orientované hrany obsahují i opačnou směrovou orientaci. I z tohoto popisu znázornění vyplývá, že se vlastnosti operací v izomorfismu přenášejí oběma směry. I pro algebraickou strukturu se dvěma operacemi zavedeme, obdobně jako u algebraické struktury s jednou operací, homomorfismus a izomorfismus. Nechť jsou dány dva polookruhy (A, ◦, ∗), (B, ⊕, ). Zobrazení ϕ množiny A na množinu B (surjekce) se nazývá homomorfním zobrazením polookruhu (A, ◦, ∗) na polookruh (B, ⊕, ), právě když ∀a, b ∈ A : ϕ(a ◦ b) = ϕ(a) ⊕ ϕ(b) ∧ ∀a, b ∈ A : ϕ(a ∗ b) = ϕ(a) ϕ(b). Příklad 3: Homomorfním obrazem oboru integrity (C, +, ·) je komutativní okruh (C4 , ⊕, ). Je-li (A, ◦, ∗) polookruh, pak každá algebraická struktura (B, ⊕, ), která je jeho homomorfním obrazem v homomorfním zobrazení ϕ, je rovněž polookruh. Má-li (A, ◦, ∗) (a) nulový prvek, pak jeho homomorfním obrazem je nulový prvek (B, ⊕, ), (b) k prvku a opačný prvek −a, pak ϕ(−a) = −ϕ(a) ∈ B, (c) jednotkový prvek, pak jeho homomorfním obrazem bude jednotkový prvek (B, ⊕, ), (d) k prvku a prvek převrácený a−1 , pak ϕ(a−1 ) = [ϕ(a)]−1 ∈ B, (e) operaci ∗ komutativní, pak je také operace komutativní v B. Oboustranný homomorfismus polookruhů neboli izomorfismus zavedeme takto: Nechť jsou dány dva polookruhy (A, ◦, ∗), (B, ⊕, ). Prosté zobrazení ϕ množiny A na množinu B (bijekci) nazýváme izomorfním zobrazením (izomorfismem) polokruhu (A, ◦, ∗) na polookruh (B, ⊕, ) právě tehdy, když ∀a, b ∈ A : ϕ(a ◦ b) = ϕ(a) ⊕ ϕ(b) ∧ ∀a, b ∈ A : ϕ(a ∗ b) = ϕ(a) ϕ(b). Zapisujeme (A, ◦, ∗) ∼ = (B, ⊕, ).
27
Závěrem zavedení základních pojmů uveďme tentokrát schematické znázornění izomorfismu z předchozí definice.
Algebraické struktury, které jsou navzájem izomorfní, se liší pouze významem svých prvků a operací. Můžeme zhruba říci, že v obou se počítá „stejněÿ. To nám umožňuje převádět výpočty z jedné algebraické struktury do druhé, která je s ní izomorfní a v níž se počítá snáze, a nalezené výsledky převádět zase zpět.
28
IV. Číselné soustavy 1. Vyjádření přirozeného čísla v číselné soustavě a převody Nechť z > 1 je libovolně zvolené přirozené číslo. Potom každé přirozené číslo a ≥ 1 lze právě jedním způsobem vyjádřit ve tvaru a = an z n + an−1 z n−1 + . . . + a2 z 2 + a1 z + a0 , (1) kde všechna čísla an , an−1 , . . . , a0 jsou menší než z, an 6= 0. Vyjádříme-li libovolné přirozené číslo a ve tvaru a = an z n + an−1 z n−1 + . . . + a2 z 2 + a1 z + a0 , říkáme, že je zapsáno v číselné soustavě o základu z, nebo v z–adické soustavě. Symboly an , an−1 , . . . , a0 nazveme číslice neboli cifry. Číslice ai , kde i = 0, 1, . . . , n se nazývá číslice i–tého řádu, nebo číslice řádu i. Přičemž z je základ číselné soustavy, z i , kde i = 0, 1, . . . n se nazývá jednotka i–tého řádu, neboli řádu i. Zápis čísla ve tvaru (1) nazveme rozvoj přirozeného čísla v z–adické soustavě, zkrácený zápis a = (an an−1 . . . a2 a1 a0 )z nazveme poziční zápis. Číslo a je (n + 1) ciferné. Příklad 1: Nechť z = 5. Přirozené číslo v pětkové číselné soustavě se zapisuje číslicemi 0, 1, 2, 3, 4. Poziční zápis přirozeného čísla (1203)5 vyjádříme jako rozvoj a dostaneme (1203)5 = 1 · 53 + 2 · 52 + 0 · 51 + 3 · 50 . Cifra 1 je řádu třetího, . . . , cifra 3 je řádu nultého, 53 je jednotka třetího řádu, . . . , 50 je jednotka nultého řádu. Číslo (1203)5 je čtyřciferné a čteme je po cifrách jedna, dvě, nula, tři o základu pět. Nechť z = 10, potom říkáme, že je přirozené číslo zapsáno v desítkové soustavě nebo dekadické soustavě. Jednotlivé cifry, kterými se toto číslo zapisuje, tj. 0, 1, 2, . . . 9 mají názvy po řadě nula, jednička, dvojka, . . . devítka. Poziční zápis čísla a nemá závorky ani index, tj. a = an an−1 . . . a2 a1 a0 . V rozvoji čísla a = an 10n + an−1 10n−1 + . . . + a2 102 + a1 101 + a0 100 označuje a0 počet jednotek nultého řádu (jednotek), a1 počet jednotek prvního řádu (desítek), a2 počet jednotek druhého řádu (stovek), a3 počet jednotek třetího řádu (tisíců) atd. Platí 1 · 101 = 10 · 100 , 1 · 102 = 10 · 101 , . . . 1 · 10k = 10 · 10k−1 pro k ∈ N, neboli jedna jednotka vyššího řádu obsahuje deset jednotek řádu o jedna nižšího. Když je číslo a alespoň čtyřciferné, cifry se seskupují do trojic, které nazýváme třídy. Třída jednotek: a2 a1 a0 , třída tisíců a5 a4 a3 , třída milionů a8 a7 a6 atd. Příklad 2: Nechť z = 10. Pojmenování čísla 1234567 nám nečiní potíže, poziční zápis nemá závorky ani index základu. Cifra jednička je šestého řádu, . . . cifra sedmička je nultého řádu. Rozvoj čísla 1234567 = 1 · 106 + 2 · 105 + 3 · 104 + 4 · 103 + 5 · 102 + 6 · 101 + 7 · 100 , třída milionů . . . 1, třída tisíců . . . 234, třída jednotek . . . 567. Číslo je sedmiciferné. Ze dvou přirozených čísel zapsaných v soustavě o témže základu je větší to, v jehož zápisu je více cifer. Mají-li zápisy obou čísel stejný počet číslic, pak je větší to číslo, v jehož zápisu číslice nejvyššího řádu označuje větší přirozené číslo. Jsou-li v zápisech obou čísel o stejném počtu číslic stejné všechny číslice řádu vyššího než k–tého a číslice řádu k–tého jsou různé, pak je větší to číslo, v jehož zápisu číslice řádu k–tého označuje větší přirozené číslo. Příklad 3: (110111)2 > (1101)2 , 3728 > 18; (3201)5 < (4312)5 , 6842 < 9564; (111011)2 > (110011)2 , 12627 > 12532.
29
V. Základy teorie dělitelnosti 1. Dělitelnost celých čísel, znaky dělitelnosti Celé číslo a je dělitelné celým číslem b, b 6= 0, právě když existuje aspoň jedno celé číslo x takové, že platí a = bx. Zapisujeme b|a. Stručný zápis: b|a ⇔ ∃x ∈ C : a = bx b|a čteme: celé číslo b dělí celé číslo a, celé číslo b je dělitelem celého čísla a, celé číslo a je násobkem celého čísla b, celé číslo a je dělitelné celým číslem b. Příklad 1: 4|20 ⇔ ∃x ∈ C : 20 = 4x, x = 5. Nechť a je libovolné celé číslo, a 6= 0. Celá čísla 1, −1, a, −a, která jsou vždy děliteli čísla a, nazýváme samozřejmými (triviálními) děliteli čísla a. Ostatní dělitelé čísla a, pokud existují, se nazývají nesamozřejmí (netriviální) dělitelé čísla a. Jestliže k celému číslu a 6= 0 existují taková celá čísla b, c tak, že platí a = bc, pak čísla b, c nazýváme sdruženými děliteli čísla a. Přirozené číslo p > 1, které má pouze samozřejmé dělitele, nazýváme prvočíslo. Příklad 2: Nechť a = 4. Samozřejmí dělitelé čísla 4 jsou 1, −1, 4, −4; nesamozřejmí dělitelé jsou 2, −2. Sdružení dělitelé 1, 4; −1, −4; 2, 2; −2, −2. Když pro libovolná dvě celá čísla a, b, b 6= 0 platí kterýkoliv ze vztahů b|a, −b|a, b| − a, −b| − a, pak platí i všechny ostatní. Příklad 3: Platí 5|20, −5|20, 5| − 20, −5| − 20. Proč? 5|20 ⇔ ∃x ∈ C : 20 = 5x, x = 4, −5|20 ⇔ ∃y ∈ C : 20 = −5y, y = −4, 5| − 20 ⇔ ∃w ∈ C : −20 = 5w, w = −4, −5| − 20 ⇔ ∃z ∈ C : −20 = −5z, z = 4. Pro libovolná celá čísla a, b, c, a 6= 0 platí (a|b ∧ a|c) ⇒ a|(b ± c),
(2)
(a|b ∨ a|c) ⇒ a|(bc),
(3)
[a|(b ± c) ∧ a|b] ⇒ a|c.
(4)
Příklad 4: Daná tvrzení můžeme po řadě ilustrovat (5|15 ∧ 5|25) ⇒ 5|(15 ± 25), (5|10 ∨ 5|3) ⇒ 5|(10 · 3), [5|(15 ± 25) ∧ 5|15] ⇒ 5|25. Je-li celé číslo a součtem dvou celých číslel, z nichž jedno je náslobkem celého čísla b, pak druhé dává při dělení číslem b týž zbytek jako číslo a. Příklad 5: Určete zbytek (aniž dělíte) při dělení čísla 151 číslem 14.
30
Řešení: 151 si vyjádříme jako součet dvou sčítanců, z nichž jeden je násobkem čísla 14, tj. 151 = 140 + 11. 140 je desetinásobek čísla 14, číslo 11 dává týž zbytek při dělení číslem 14 jako, když číslem 14 dělíme číslo 151. Závěr: 151 při dělení číslem 14 dává zbytek 11. Následující věty uvádí, jaký zbytek dávají přirozená čísla v desítkové soustavě při dělení čísly 2, 5, 10, 4, . . . Dělíme-li přirozené číslo aspoň dvojciferné v desítkové soustavě dvěma (pěti, deseti), dostaneme stejný zbytek, jako když dělíme dvěma (pěti, deseti) jeho cifru nultého řádu. Příklad 6: Určete zbytek, který dostanete při dělení čísla 3727 čísly 2, 5, 10. Řešení: 7 je cifra nultého řádu. Zbytek při dělení číslem 2 je 1, zbytek při dělení číslem 5 je 2, zbytek při dělení číslem 10 je 7. Přirozené číslo, které je aspoň trojciferné v desítkové soustavě, dává při dělení čtyřmi (100, 50, 25, 20) týž zbytek, jako dělíme-li čtyřmi (100, 50, 25, 20) jeho poslední dvojčíslí. Příklad 7: Určete zbytek při dělení čísla 3727 čísly 4, 20, 25, 50, 100. Řešení: Poslední dvojčíslí je 27. Zbytek při dělení číslem 4 je 3, při dělení 20 je 7, při dělení 25 je 2, při dělení 50 a 100 je 27. Přirozené číslo, které je aspoň čtyřciferné v desítkové soustavě, dává při dělení osmi (1000, 500, 250, 200, 125, 40) týž zbytek, jako dělíme-li osmi (1000, 500, 250, 200, 125, 40) jeho poslední trojčíslí. Příklad 8: Určete zbytek při dělení čísla 3727 čísly 8, 40, 125, 200, 250, 500, 1000. Řešení: Poslední trojčíslí je 727. Zbytek při dělení 8 je 7, při dělení 40 je 7, při dělení 125 je 102, při dělení 200 je 127, při dělení 250 je 227, při dělení 500 je 227, při dělení 1000 je 727. Přirozené číslo v desítkové soustavě dává při dělení třemi (9) týž zbytek, jako dělíme-li třemi (9) jeho ciferný součet. Příklad 9: Určete zbytek při dělení čísla 3427 čísly 3 a 9. Řešení: Ciferný součet čísla 3427 je 16 (3 + 4 + 2 + 7), zbytek při dělení číslem 3 je 1, při dělení 9 je 7. Přirozené číslo v desítkové soustavě při dělení jedenácti dává týž zbytek, jako dělíme-li jedenácti součet cifer sudých řádů zmenšený o součet cifer lichých řádů daného čísla.
31
Příklad 10: Určete zbytek při dělení čísla 3427 číslem 11. Řešení: Součet cifer sudých řádů (7 + 4) zmenšíme o součet cifer lichých řádů (2 + 3), tj. 11 − 5 = 6. Zbytek je 6. Další věty hovoří o tom, kdy jsou přirozená čísla dělitelná 2, 5, 10, 4, . . . Přirozené číslo, které je v desítkové soustavě aspoň dvojciferné, je dělitelné dvěma (5, 10), právě když je dělitelná dvěma (5, 10) jeho cifra nultého řádu. Přirozené číslo, které je v desítkové soustavě aspoň trojciferné, je dělitelné čtyřmi (100, 50, 25, 20), právě když je dělitelné čtyřmi (100, 50, 25, 20) jeho poslední dvojčíslí. Přirozené číslo, které je v desítkové soustavě aspoň čtyřciferné, je dělitelné osmi (1000, 500, 250, 200, 125, 40), právě když je dělitelné osmi (1000, 500, 250, 200, 125, 40) jeho poslední trojčíslí. Přirozené číslo v desítkové soustavě je dělitelné třemi (9), právě když je třemi (9) dělitelný jeho ciferný součet. Přirozené číslo v desítkové soustavě je dělitelné jedenácti, právě když je jedenácti dělitelný součet cifer sudých řádů zmenšený o součet cifer lichých řádů daného čísla. 2. Největší společný dělitel a nejmenší společný násobek přirozených čísel (bez nuly) Největším společným dělitelem přirozených čísel a, b rozumíme největší číslo z množiny D(a, b) společných dělitelů čísel a, b. Největšího společného dělitele přirozených čísel a, b označujeme D(a, b). Nebo také: Největší číslo, kterým jsou přirozená čísla a, b dělitelná, se nazývá nějvětší společný dělitel čísel a, b, tj. D(a, b). Poznámka: Určujeme-li největší společný dělitel z čísel a1 , a2 , . . . an , potom zapíšeme D(a1 , a2 , . . . , an ). Příklad 1: Nechť a = 8, b = 12. Množina dělitelů čísla 8 je D(8) = {1, 2, 4, 8}, množina dělitelů čísla 12 je D(12) = {1, 2, 3, 4, 6, 12}. Množina společných dělitelů čísel 8, 12, tj. D(8, 12) = D(8)∩D(12) = {1, 2, 4}, tedy D(8, 12) = 4. Přirozená čísla a1 , a2 , . . . , an , která jsou navzájem různá, a pro něž platí D(a1 , a2 , . . . , an ) = 1, se nazývají nesoudělná. Příklad 2: Čísla 2, 5, 8, 21, 39 jsou čísla nesoudělná, platí D(2, 5, 8, 21, 39) = 1. Přirozená čísla a1 , a2 , . . . , an , která jsou navzájem různá a mají aspoň jednoho společného dělitele různého od jedné, se nazývají čísla soudělná. Příklad 3: Čísla 4, 12, 136 jsou čísla soudělná, mají aspoň jednoho společného dělitele různého od jedné, jsou to čísla 2, 4. Přirozená čísla a1 , a2 , . . . , an , která mají tu vlastnost, že všechny dvojice navzájem různých čísel, které z nich můžeme utvořit, jsou čísla nesoudělná, se nazývají po dvou nesoudělná. Příklad 4: Čísla 2, 5, 9, 17 jsou po dvou nesoudělná, platí D(2, 5) = 1, D(2, 9) = 1, D(2, 17) = 1, D(5, 9) = 1, D(5, 17) = 1, D(9, 17) = 1. Jsou-li čísla a1 , a2 , . . . , an po dvou nesoudělná, jsou také nesoudělná. Obrácené tvrzení neplatí. Příklad 5: Čísla 2, 5, 9, 17 jsou po dvou nesoudělná, jsou také nesoudělná, platí D(2, 5, 9, 17) = 1.
32
Každý společný dělitel čísel a1 , a2 , . . . , an je dělitelem jejich největšího společného dělitele. Příklad 6: Nechť a1 = 8, a2 = 12; platí-li D(8) = {1, 2, 4, 8}, D(12) = {1, 2, 3, 4, 6, 12}, D(8, 12) = {1, 2, 4}, D(8, 12) = 4, potom 1|4, 2|4, 4|4. Následující věty dávají návod pro určení největšího společného dělitele čísel a1 , a2 , . . ., an . Je-li přirozené číslo k, k 6= 0, pak pro přirozená čísla a1 , a2 , . . . , an je D(ka1 , ka2 , . . . , kan ) = k · D(a1 , a2 , . . . , an ). Příklad 7: D(24, 32, 136) = 8 · D(3, 4, 17) = 8 · 1 = 8 Čísla 3, 4, 17 jsou nesoudělná, protože D(3, 4, 17) = 1. Nechť a1 , a2 , . . . , an jsou přirozená čísla a pro přirozené číslo m platí 1 ≤ m < r. Označíme-li D(a1 , a2 , . . . , am ) = d1 , D(am+1 , am+2 , . . . , an ) = d2 , pak D(a1 , a2 , . . . , an ) = D(d1 , d2 ). Příklad 8: Máme určit D(21, 75, 25, 49). Vypočítáme D(21, 49) = 7, D(25, 75) = 25, potom D(21, 75, 25, 49) = D(7, 25) = 1. Nechť a, b jsou libovolná přirozená čísla, potom platí: b|a ⇒ D(a, b) = b. Nechť a, b jsou libovolná přirozená čísla, potom platí: b - a ⇒ D(a, b) = D(b, z), kde z je zbytek při dělení čísla a číslem b. Poslední dvě uvedené věty jsou základem postupu zvaného Eukleidův algoritmus postupného dělení. Eukleides žil asi v letech 365–300 př. n. l. Příklad 9: Eukleidovým algoritmem určete D(252, 132). Určíme, zda 132|252. Zjistíme, že 132 - 252, zbytek je 120. Proto tedy počítáme D(132, 120). Určíme, zda 120|132. Zjistíme, že 120 - 132, zbytek je 12, počítáme proto D(120, 12) = 12. Zkrácený zápis D(252, 132) = D(132, 120) = D(120, 12) = 12, neboli D(252, 132) = 12. Jestliže největší společný dělitel přirozených čísel a, b je roven D(a, b), potom existují celá čísla x, y taková, že platí: ax + by = D(a, b). Příklad 10: Nechť D(8, 12) = 4, potom platí 8x + 12y = 4. Řešením jsou např. dvojice čísel x1 = −1, y1 = 1, x2 = 2, y2 = −1, atd. Nejmenším společným násobkem přirozených čísel a, b rozumíme nejmenší číslo z množiny N(a, b) společných násobků čísel a, b. Nejmenší společný násobek přirozených čísel a, b označujeme n(a, b). Poznámka: Určujeme-li nejmenší společný násobek z čísel a1 , a2 , . . . , an , potom zapíšeme n(a1 , a2 , . . . , an ).
Příklad 11: Nechť je a = 8, b = 12. Množina násobků čísla 8 je N(8) = {8, 16, 24, 32, 40, 48, . . .}, množina násobků čísla 12 je N(12) = {12, 24, 36, 48, . . .}. Množina společných násobků čísel 8, 12, tj. N(8, 12) = N(8)∩N(12) = {24, 48, 72, . . .}, tedy n(8, 12) = 24. Každý určený společný násobek přirozených čísel a1 , a2 , . . . , an je násobkem jejich nejmenšího společného násobku. 33
Příklad 12: Nechť a1 = 8, a2 = 12. Platí-li N(8) = {8, 16, 24, 32, 40, 48, . . .}, N(12) = {12, 24, 36, 48, . . .}, N(8, 12) = {24, 48, 72, . . .}, n(8, 12) = 24, potom 24|24, 24|48, 24|72, . . . Následující věty opět dávají návod, jak vypočítat nejmenší násobek přirozených čísel. Je-li dáno přirozené číslo k, k 6= 0, pak pro přirozená čísla a1 , a2 , . . . , an je n(ka1 , ka2 , . . . , kan ) = k · n(a1 , a2 , . . . , an ).
Příklad 13: n(14, 28, 78) = 2 · n(7, 14, 35) = 2 · 7 · n(1, 2, 5) = 2 · 7 · 10 = 140 Nechť a1 , a2 , . . . , an jsou přirozená čísla a pro přirozené číslo m platí 1 ≤ m < r. Označíme-li n(a1 , a2 , . . . , am ) = n1 , n(am+1 , am+2 , . . . , an ) = n2 , pak n(a1 , a2 , . . . , an ) = n(n1 , n2 ). Příklad 14: Určete n(4, 5, 6, 20). Vypočítáme n(4, 5) = 20, n(6, 20) = 60, pak n(4, 5, 6, 20) = n(20, 60) = 60. Jsou-li a1 , a2 přirozená čísla, D(a1 , a2 ) jejich největší společný dělitel, n(a1 , a2 ) jejich nejmenší společný násobek, potom: a1 a2 = D(a1 , a2 ) · n(a1 , a2 ). Příklad 15: Nechť a1 = 8, a2 = 12, D(8, 12) = 4, n(8, 12) = 24, potom ověřte, zda platí 8 · 12 = 4 · 24. 3. Prvočísla Přirozené číslo p > 1 nazýváme prvočíslem, právě když má pouze samozřejmé dělitele. Přirozené číslo a 6= 1, které není prvočíslo, nazýváme číslo složené. Tedy přirozené číslo a, které mimo samozřejmých dělitelů má i nesamozřejmé dělitele, nazýváme složeným číslem. Jestliže je přirozené číslo a složené, pak nejmenší nesamozřejmý dělitel je prvočíslo, pro které platí vztah p2 ≤ a. Není-li přirozené číslo a dělitelné prvočíslem p, jehož druhá mocnina není větší než a, pak je toto číslo prvočíslo. Jestliže součin přirozených čísel a, b je dělitelný prvočíslem p, pak p dělí alespoň jedno z čísel a, b. Každé složené přirozené číslo a můžeme vždy vyjádřit jako součin konečného počtu prvočísel: a = p1 · p2 · p3 . . . pn . Každé složené přirozené číslo a lze vyjádřit právě jedním způsobem ve tvaru a = pe11 · pe22 · pe33 . . . penn , kde p1 , p2 , p3 , . . . , pn jsou různá prvočísla a exponenty e1 , e2 , e3 , . . . , en nenulová přirozená čísla. Uvedenou rovnost nazýváme prvočíselným rozkladem přirozeného složeného čísla a v součin prvočísel, nebo rozklad čísla a na prvočinitele, případně kanonickým rozkladem. Prvočísla p1 , p2 , p3 , . . . , pn nazýváme prvočinitele rozkladu.
34
Počet navzájem různých kladných dělitelů určíme ze vztahu α = (e1 + 1) · (e2 + 1) · (e3 + 1) . . . (en + 1), kde e1 , e2 , e3 , . . . , en jsou exponenty v prvočíselném rozkladu. 4. Neurčité rovnice Lineární neurčitou rovnicí o dvou neznámých x, y rozumíme rovnici ax + by = c, kde a 6= 0, b 6= 0, koeficienty a, b, c jsou celá čísla, neznámé x, y jsou také celá čísla. Tato rovnice se také nazývá diofantovská, diofantská, podle řeckého matematika Diofanta z Alexandrie (žil ve druhé polovině 3. století n. l.), autora spisu Arithmétika, který neurčité rovnice již řešil. Řešením rovnice ax + by = c rozumíme uspořádanou dvojici celých čísel (x0 , y0 ), pro kterou platí ax0 + by0 = c. Řešit neurčitou rovnici znamená nalézt množinu všech jejich řešení. Jestliže platí c = 0, pak má rovnice nekonečně mnoho celočíselných řešení. Řešením jsou dvojice celých čísel (x, y), pro která platí x = Bt, y = −At, kde t ∈ C, A =
a ,B d
= db , d = D(a, b).
Jestliže c 6= 0, rovnice je řešitelná, právě když D(a, b) dělí c, což zapíšeme D(a, b)|c. Má-li rovnice jedno celočíselné řešení (x0 , y0 ), pak má řešení nekonečně mnoho. Všechna řešení lze pak vyjádřit ve tvaru x = x0 + Bt, y = y0 − At. Při řešení slovních úloh pomocí neurčitých rovnic je zpravidla množina řešení omezena podmínkami dané slovní úlohy. Řešení neurčitých rovnic se třemi neznámými x, y, z je obdobné řešení úloh se dvěma neznámými. Výsledkem pak jsou trojice řešení (x0 , y0 , z0 ), (x1 , y1 , z1 ), . . .
35
VI. Zavedení polookruhu všech přirozených čísel 1. Kardinální čísla Úvodem si připomeňme pojmy: Množiny A, B jsou ekvivalentní, právě když existuje alespoň jedno prosté zobrazení množiny A na množinu B. Uvedenou okolnost značíme A ∼ B. Množina A je konečná právě tehdy, když žádná vlastní podmnožina množiny A není ekvivalentní s množinou A. Množina A, která není konečná, je nekonečná. Z daného vyjádření plyne, že množina B je nekonečná, když existuje aspoň jedna vlastní podmnožina množiny B, která je s touto množinou ekvivalentní. Třída rozkladu, do které patří množina A z neprázdného systému množin M a všechny množiny s množinou A ekvivalentní, nazýváme kardinálním číslem této množiny. Značíme | A |. Kardinální číslo vyjadřujeme také jako mohutnost množiny. Symbolicky: | A |= {X ∈ M ; X ∼ A}. Množiny A, B jsou ekvivalentní právě tehdy, když mají stejná kardinální čísla. Symbolicky: A ∼ B ⇔| A |=| B | . Reprezentantem třídy | A | nazveme jakoukoliv podmnožinu X, pro kterou platí X ∼ A. Přirozenými čísly nazveme kardinální čísla konečných množin. Nerovnosti mezi kardinálními čísly: Kardinální číslo množiny A je menší než kardinální číslo množiny B, což zapíšeme: | A |<| B |, právě když | A |6=| B | a množina A je ekvivalentní s vlastní podmnožinou B ∗ množiny B. Sčítání kardinálních čísel: Součtem kardinálních čísel | A |, | B | nazveme kardinální číslo sjednocení množin A, B , tj. | A ∪ B |. Přičemž musí platit, že A ∩ B = ∅. Operace sčítání je neomezeně definovaná v množině kardinálních čísel, vzhledem k tomu, že výsledek operace sčítání mezi každými kardinálními čísly bude kardinální číslo z uvedeného systému množin. Tato operace je také komutativní, protože platí: A ∪ B ∼ B ∪ A. Rovněž i asociativní, protože platí: (A ∪ B) ∪ C ∼ A ∪ (B ∪ C). Kardinální číslo prázdné množiny, tj. | ∅ | je neutrálním prvkem této operace na množině kardinálních čísel. Z uvedeného můžeme vyvodit, že algebraická struktura ({| X |; X ∈ M }; +) je komutativním monoidem. Násobení kardinálních čísel: Součinem kardinálních čísel | A |, | B | nazveme kardinální číslo kartézského součinu množin A, B , tj. | A × B |. Operace násobení je neomezeně definovaná v množině kardinálních čísel, vzhledem k tomu, že výsledek této operace mezi každými kardinálními čísly bude kardinální číslo z uvedeného systému množin. Tato operace je také komutativní, protože platí: A × B ∼ B × A. Rovněž i asociativní, protože platí: (A × B) × C ∼ A × (B × C). Kardinální číslo každé jednoprvkové množiny je neutrálním prvkem této operace na množině kardinálních čísel. Z uvedeného můžeme vyvodit, že algebraická struktura ({| X |; X ∈ M }; ·) je komutativním monoidem. Shrnutí: Algebraická struktura ({| X |; X ∈ M }; +, ·) je komutativní polookruh s nulovým a jednotkovým prvkem vzhledem k okolnosti, že uvedená operace násobení mezi kardinálními čísly je distributivní vzhledem k zavedené operaci sčítání.
36
2. Ordinální čísla Připomeňme: Lineárně uspořádané množiny (A, R1 ) a (B, R2 ) jsou podobné, právě když existuje podobné zobrazení množiny lineárně uspořádané množiny (A, R1 ) na lineárně uspořádanou množinu (B, R2 ) . Uvedenou okolnost značíme (A, R1 ) ≈ (B, R2 ). Třída rozkladu, do které patří dobře uspořádaná množina [A] = (A, R1 ) z neprázdného systému množin G a všechny množiny s dobře uspořádanou množinou [A] podobné, nazýváme ordinálním číslem této množiny. Jak již bylo uvedeno označíme ji [A]. Symbolicky můžeme zapsat: ord[A] = {[X] ∈ G; [X] ≈ [A]}. Množiny (A, R1 ) a (B, R2 ) jsou podobné právě tehdy, když mají stejná ordinální čísla. Symbolicky: [A] ≈ [B] ⇔ ord[A] = ord[B]. Reprezentantem třídy ord[A] nazveme jakoukoliv dobře uspořádanou množinu [X], pro kterou platí [X] ≈ [A]. Přirozenými čísly nazveme ordinální čísla konečných dobře uspořádaných množin. Úsek dobře uspořádané množiny: Nechť je dána dobře uspořádaná množina [A] = (A, R1 ) a x ∈ A, pak úsekem dobře uspořádané množiny [A] určených prvkem x je dobře uspořádaná množina [Ax ], podle předem zavedených vztahů. Nerovnosti mezi ordinálními čísly: Ordinální číslo dobře uspořádané množiny [A] je menší než ordinální číslo množiny [B], což zapíšeme ord|A| < ord|B|, právě když dobře uspořádaná množina [A] = (A, R1 ) je podobná s některým úsekem dobře uspořádané množiny [B] = (B, R2 ) . Sčítání ordinálních čísel: Právě když pro dvě dobře uspořádané množiny [A] = (A, R1 ), [B] = (B, R2 ) platí, že jejich průnikem je množina prázdná, což vyjádříme zápisem A ∩ B = ∅, pak, když [S] = (A ∪ B, R3 ), kde je dobré uspořádání R3 dáno takto: • je-li x ∈ A ∧ y ∈ B, pak je také xR3 y, • je-li xR1 y, pak je xR3 y, • je-li xR2 y, také je xR3 y, čímž definujeme, že ord[S] = ord[A] + ord[B]. Operace sčítání je neomezeně definovaná, vzhledem k tomu, že výsledek operace sčítání mezi každými ordinálními čísly bude ordinální číslo z uvedeného systému množin. Násobení ordinálních čísel: Právě když jsou dány dobře uspořádané množiny [A] = (A, R1 ), [B] = (B, R2 ), pak, je-li [T ] = (A × B, Rk ), kde dobré uspořádání Rk je zavedeno: (a, b)Rk (a1 , b1 ), právě když bR2 b1 ∨ (b = b1 ∧ aR1 a1 ), definujeme ord[T ] = ord[A] · ord[B].
3. Peanova množina V doposud uvedeném textu v němž jsme používali pojem množiny, byla zatím opomenuta okolnost, že jsme ji jistým způsobem nezavedli. Abychom se tímto „nedostatkemÿ vyrovnali zavedeme pojem Peanovy množiny v následujících axiómech. Množina P se nazývá Peanovou množinou, jestliže splňuje následující vlastnosti: • Ke každému prvku x ∈ P existuje právě jeden prvek x0 ∈ P , který nazýváme následovníkem prvku x. • Množina P obsahuje prvek e, který není následovníkem žádného prvku této množiny. • Každé dva různé prvky množiny P mají dva různé následovníky. • Princip matematické indukce: Když pro množinu M platí − obsahuje prvek e ∈ P , − obsahuje-li prvek x ∈ P , pak obsahuje i jeho následovníka x0 ∈ P , 37
pak tedy platí, že množina M obsahuje všechny prvky množiny P. Daný prvek y ∈ M , pro nějž platí y 0 = x se nazývá předchůdce prvku x ∈ M . Tzn., že uvedený vztah můžeme zapsat: y =0 x. Vlastnosti: • Prvek e je jediný prvek Peanovy množiny, který není následovníkem žádného jiného prvku množiny P . • Každý prvek x 6= e má právě jednoho předchůdce. • Každý prvek množiny P je různý od svého následovníka. • Množina M je nekonečná množina. • Úsekem Peanovy množiny P , který je příslušný k prvku a, je množina U (a) ⊂ P , pro níž platí − a 6∈ U (a), − jestliže existuje prvek 0 a, platí, že 0 a ∈ U (a), − když je x ∈ U (a), pak je také 0 x ∈ U (a), když 0 x existuje. • Ke každému prvku množiny P existuje právě jeden úsek. • Pro každý prvek a ∈ P platí , že a ∈ U (a) ∪ {a} = U (a0 ) . • Jestliže a ∈ U (b), pak je i U (a) ⊂ U (b). • Jestliže a 6∈ U (b), pak je U (b) ⊂ U (a) . • Každý ze dvou úseků množiny P je jeden úsekem druhého. • Žádné dva různé úseky množiny P nejsou ekvivalentní. • Žádný úsek množiny P není ekvivalentní se svou vlastní podmnožinou. Množinu nazýváme konečnou, právě když je ekvivalentní s libovolným úsekem Peanovy množiny. Poznámka: Množinu kardinálních čísel konečných množin budeme označovat - Pk . Kardinální čísla konečných množin se nazývají přirozenými čísly. Množinu ordinálních čísel konečných dobře uspořádaných množin budeme označovat - Pω . Ordinální čísla dobře uspořádaných konečných množin nazveme přirozenými čísly. Peanovu množinu budeme označovat - P . Definujme ještě operace sčítání a násobení v množině P : x ⊕ e = x ∧ x ⊕ y 0 = (x ⊕ y)0 x e = e ∧ x y0 = x y ⊕ x
) atd.
Množiny Pk , Pω a P vzhledem k zavedeným operacím jsou polookruhy z nichž každý obsahuje nulový i jednotkový prvek. Navíc jsou vzájemně izomorfní. Přirozená čísla vzhledem k daným izomorfismům Pk Pω P |U (e)| = ord|U (e), < | = e = |U (e0 )| = ord|U (e0 ), < | = e0 = |U ((e0 )0 )| = ord|U ((e0 )0 ), < | = (e0 )0 = .. .. .. . . .
budeme označovat následujícím způsobem: N 0 1 2 .. .
38
4. Slovní úlohy Pojem slovní úlohy: Slovní úlohy jsou úlohy, ve kterých je závislost mezi danými a hledanými čísly vyjádřena slovní formulací. Je nezbytné pomocí vhodné úvahy zjistit, jaké početní operace musíme s danými čísly udělat, abychom našli čísla, která máme vypočítat. Postup při řešení slovní úlohy: a) rozbor b) matematizace problému, znázornění c) řešení d) zkouška e) odpověď ad a) dokonalé pochopení textu (zadání); ujasnění si toho, co známe a co máme vypočítat; objevení vztahu mezi údaji; znázornění situace; kladení vhodných otázek ad b) logické vyústění rozboru; zápis rovnicí, nerovnicí, početním příkladem ad c) vyřešení vytvořeného početního příkladu; řešení rovnice nebo nerovnice ad d) potvrzení numerické správnosti; potvrzení věcné reálné správnosti ad e) písemná, odpovídající příslušné otázce (úkolu), opětovná konfrontace výsledku s realitou (vytváření zodpovědnosti) Základní klasifikace slovních úloh • jednoduché — v průběhu řešení je použit jen jeden početní výkon • složené — v průběhu řešení používáme více než jeden početní výkon Klasifikace jednoduchých slovních úloh Úlohy • aditivní (A) • multiplikativní (M) Označení úlohy A1 A1 A1 A2 A2 A2 M1 M1 M1 M2 M2 M2
Aritmetická operace + − − + − − · : : · : :
Orientační charakteristika názvu úlohy Ze dvou částí určit celek Z celku a první části určit druhou část Z celku a druhé části určit první část Zvětšení o daný počet jednotek Zmenšení o daný počet jednotek Porovnávání rozdílem Určení součtu stejných sčítanců Rozdělování na stejné části Rozdělování po stejných částech Zvětšení čísla několikrát Zmenšení čísla několikrát Porovnávání podílem
39
Číslo úlohy 1 2 3 4 5 6 7 8 9 10 11 12
Příklady jednoduchých slovních úloh daných typů Označení úlohy A1
Číslo úlohy 1
A1
2
A1
3
A2 A2
4 5
A2
6
M1 M1
7 8
M1
9
M2 M2
10 11
M2
12
Zadání úlohy (text) Vašek má 3 kostky a Zdeněk 4 kostky. Kolik kostek mají dohromady? Jana a Petra měly má misce 8 pomerančů. Jana si vzala 2 pomeranče. Kolik pomerančů zůstalo Petře? Jana a Petra měly na misce 8 pomerančů. Petra se vzala 6 pomerančů. Kolik pomerančů zůstalo Janě? Ve 3. A je 22 žáků. Ve 3. B o 4 žáky více. Kolik žáků je ve 3. B? Na výlet jelo 20 chlapců. Děvčat jelo na výlet o 4 méně. Kolik děvčat jelo na výlet? Monika má v knihovně 40 knih. Ivana 25 knih. O kolik knih má Ivana méně než Monika? Karel ušetří každý týden 5 korun. Kolik korun ušetří za 3 týdny? Maminka rozdělila svým 3 dětem 27 hrušek. Každý dostal stejně. Kolik hrušek dostalo každé dítě? Dědeček rozdělil vnukům 40 korun. Každému dal 10 korun. Kolik vnuků podělil? Pavel má 15 kuliček. Jirka 3 krát více. Kolik kuliček má Jirka? Auto ujede za hodinu 50 km. Chodec za stejnou dobu ujde 10 krát méně. Kolik km za hodinu ujde chodec? Strom měří 8 metrů. Keř má výšku 2 metry. Kolikrát je keř menší než strom?
40
5. Analytická a syntetická metoda řešení složené slovní úlohy Příklad: Jana zaplatila za nákup v papírnictví 121 korun. Koupila 4 stejná balení ubrousků, 6 fixů po 7 korunách a 3 sešity po 9 korunách. Kolik korun stálo 1 balení ubrousků ?
Matematizace složené slovní úlohy • pomocí soustavy rovnic: 4·x a+b b c d
= = = = =
a 121 c+d 6·7 3·9
1. 2. 3. 4.
HÚ DÚ DÚ DÚ DÚ
analytický postup
• systémem závorek: x = {121 − [(6 · 7) + (3 · 9)]} : 4 x = [121 − 6 · 7 + 3 · 9] : 4
1. DÚ
2. DÚ 3. DÚ
HÚ 4. DÚ
41
• postupným řešením jednoduchých úloh: 3 · 9 = 27 6 · 7 = 42 27 + 42 = 69 121 − 69 = 52 x = 52 : 4
4. 3. 2. 1.
DÚ DÚ DÚ DÚ HÚ
syntetický postup
Charakteristika základních postupů řešení složené slovní úlohy Analytický postup znamená, že vyjdeme z otázky a sestavíme jednoduchou slovní úlohu, pomocí níž můžeme na otázku odpovědět - přičemž však alespoň jeden potřebný údaj k řešení této jednoduché slovní úlohy není znám. K určení tohoto údaje sestavíme další jednoduchou slovní úlohu, atd. dokud všechny vstupní údaje ještě neznáme. Při syntetickém postupu vycházíme naopak z daných údajů a vždy za dvou z nich - vhodně zvolených - vypočteme v jednoduché slovní úloze další potřebný údaj. Z tohoto údaje a z dalšího údaje z textu sestavíme pak další jednoduchou slovní úlohu. Tak pokračujeme, dokud nezískáme údaj potřebný k odpovědi na otázku celé úlohy.
6. Konstrukce oboru integrity celých čísel V předchozím textu byl zaveden polookruh přirozených čísel, který je nezbytné rozšířit na obor integrity celých čísel. Budeme postupovat následujícím způsobem: Na kartézském součinu N × N zavedeme relaci předpisem (a, b) ∼ (c, d) ⇔ a + d = b + c. Relace ∼ je relací ekvivalence, neboť se dá dokázat, že uvedená relace je reflexivní, symetrická a tranzitivní. Tato relace ∼ vytváří rozklad množiny na třídy. Množinou všech celých čísel budeme rozumět všech tříd rozkladu vytvořeného relací ekvivalence ∼ definovanou na kartézském součinu N ∼ N . Dále je nezbytné na zavedené množině celých čísel definovat binární operace. Nechť jsou dána celá čísla A, B, která jsou po řadě reprezentována uspořádanými dvojicemi [a, b] a [c, d], pak jejich součtem A + B rozumíme celé číslo, jež je reprezentováno uspořádanou dvojicí [a + c, b + d]. Symbolicky: [a, b] ∈ A ∧ [c, d] ∈ B ⇒ [a + c, b + d] ∈ A + B. Nechť jsou dána celá čísla A, B, která jsou po řadě reprezentována uspořádanými dvojicemi [a, b] a [c, d], pak jejich součinem A · B rozumíme celé číslo, jež je reprezentováno uspořádanou dvojicí [ac + bd, ad + bc]. Symbolicky [a, b] ∈ A ∧ [c, d] ∈ B ⇒ [ac + bd, ad + bc] ∈ A · B. Je nezbytné ověřit, tj. dokazujeme, že uvedené definice nezáleží na výběru reprezentantů. Dále pak je třeba ověřit, že: 1. binární operace sčítání a násobení jsou komutativní a asociativní, 2. binární operace násobení je distributivní vzhledem k operaci sčítání, 3. nulový prvek je nulové celé číslo, které je reprezentováno uspořádanou dvojicí [n, n], 4. jednotkový prvek je celé číslo, jež je reprezentováno uspořádanou dvojicí [x + 1, x], 5. opačné číslo k celému číslu, které je reprezentováno uspořádanou dvojicí [a, b] je celé číslo, jež je reprezentováno uspořádanou dvojicí [b, a]. Rozdílem A − B dvou celých čísel A, B je číslo X, pro které platí A = B + X. Shrneme-li: Algebraická struktura celých čísel vzhledem k uvedeným operacím (tj. sčítání a násobení) je oborem integrity s nulovým a jednotkovým prvkem.
42
7. Konstrukce tělesa racionálních čísel Podobně, jako když jsme rozšiřovali polookruh (N ; +, .) na obor integrity (C; +, .), budeme i nyní požadovat, aby nová algebraická struktura (Q; +, .) všech racionálních čísel měla i další vlastnosti: • aby se v ní počítalo podle stejných pravidel jako v oboru integrity (C; +, .), • abychom celá čísla mohli považovat za čísla racionální, • abychom mohli každé racionální číslo vyjádřit pomocí čísel celých. Jestliže se nám takové rozšíření skutečně podaří nalézt, potom je ihned zřejmé, že nově vzniklá množina čísel musí být vzhledem k operacím sčítání a násobení tělesem, a to dokonce tělesem komutativním. Vezměme množinu M, M ⊂ C × C, která se skládá ze všech uspořádaných dvojic celých čísel, jejichž druhá složka je nenulová. Těmto uspořádaným dvojicím říkáme zlomky a budeme je zapisovat takto: xy ; (x je čitatel, y jmenovatel zlomku ). Tedy M = xy ∈ C × C; y 6= 0. V množině M definujeme binární relaci: ∼= [ ab , dc ] ∈ M 2 ; ad = bc. Potom bude například platit: , −5 , 10 , 15 , 20 , 25 , 105 , . . .}, [5, 3] = { −10 −6 −3 6 9 12 15 63 [5, 3] = [−10, −6] = [−5, −3] = [10, 6] = [15, 9] = . . . Definice: Nechť jsou dána racionální čísla A, B, která jsou reprezentována zlomky racionální číslo, které je reprezentované zlomkem ad+bc . bd Symbolicky: Jestliže
a b
∈Aa
c d
∈ B, potom
ad+bc bd
a c , . b d
Součtem A + B budeme rozumět
∈ A + B.
Je třeba dokázat, že součet nezávisí na výběru reprezentantů: 0 0 0 0 0 0 0 0 c Jestliže ab ∼ ab0 a dc ∼ dc0 , potom ad+bc ∼ a db0+b , tedy ac ∼ ab0 dc0 . bd d0 bd Součinem A · B racionálních čísel A, B budeme rozumět racionální číslo reprezentované zlomkem
ac . bd
Stručně: Jestliže ab ∈ A a dc ∈ B, potom ac ∈ A · B. bd Dále dokazujeme, že uvedená definice nezáleží na výběru reprezentantů. Dále pak: Je třeba dokázat, že: obě definované operace jsou komutativní, asociativní a operace násobení je distributivní vzhledem k operaci sčítání; nulový prvek je racionální číslo [0, x], x 6= 0; jednotkový prvek je racionální číslo [x, x], kde x je libovolné nenulové celé číslo; opačné číslo k číslu [a, b] je číslo [−a, b] = [a, −b]; rozdílem čísel [a, b], [c, d] je číslo [a, b] − [c, d] = [a, b] + [−c, d] = [ad − bc, bd]; převrácené číslo k číslu [a, b], je-li a 6= 0, je číslo [b, a]; podílem čísel [a, b], [c, d], kde c 6= 0, je číslo [a, b] · [d, c] = [ad, bc]. Algebraická struktura ( Q; +, . ) je komutativní těleso. Tvrzení o racionálních číslech a jejich vlastnostech: Pro libovolná celá čísla a, b, c, d, k ∈ C, b 6= 0, d 6= 0 platí: 1. 2. 3. 4. 5. 6. 7.
a b a b a b a b a b a b a b
c právě tehdy, když d ak = bk , je-li k 6= 0, + dc = ad+bc , bd c ad−bc − d = bd , · dc = ac , bd ak ·k = b , : dc = ad , je-li c 6= 0. bc
=
ad = bc,
Je třeba dokázat, že nezávisí na výběru reprezentantů: 0 0 0 0 Jestliže ab ∼ ab0 a dc ∼ dc0 , přičemž ac ∼ ab0 dc0 , potom ad+bc ∼ bd bd
43
a0 d0 +b0 c0 . b0 d0
8. Rovnost, rovnice, nerovnost, nerovnice Základní pojmy: Výraz — termín, který používáme k označení v matematickém jazyce. Konstanta — každý výraz, jež označuje jeden daný objekt. Proměnná — výraz, který neoznačuje určitou věc, prvek množiny; což v matematice vyjádříme pomocí písmena. Označení — matematické výrazy vytvořené jen z konstant. Označovací forma — matematické výrazy, které obsahují alespoň jednu proměnnou. Rovnost zpravidla charakterizujeme pomocí výrazů, které neobsahují proměnnou. Př.: 5 + 3 = 8; 3 · 7 = 7 · 3 Rovnicí rozumíme matematický zápis rovnosti dvou výrazů. Přičemž jeden z nich je označovací forma a druhý je označení nebo opět označovací forma. Př.: 4 = 3 − x; y = 2x Pojmy nerovnost a nerovnice vytvoříme analogicky vzhledem k předchozím pojmům s použitím symbolů: <; >; ≤ ; ≥.
44
Přehled některých použitých symbolů p, q, r ¬p p∨q p∨q p∧q p⇒q p⇔q Φ(p , p , . . . , pn ) Φ∼Ψ a Φ(p , p , . . . , pn ) A(x) ¬A(x) A(x) ∨ B(x) A(x)∨B(x) A(x) ∧ B(x) A(x) ⇒ B(x) A(x) ⇔ B(x) A, B, C a, b, c a∈A b 6∈ A ∅, {} A⊂B A=B A 6= B P(M ) a|b a≥b akb a⊥b A∪B A∩B A4B A\B A0 (a, b) A×B R0 R−1 (M, R) A∼B (M1 , R1 ) ≈ (M2 , R2 ) (M, ◦) (M, ◦, ∗) (M, ◦) ∼ = (M2 , ∗)
výroky (výrokové proměnné) negace výroku disjunkce výroků p, q ostrá disjunkce výroků p, q konjunkce výroků p, q implikace výroků p, q ekvivalence výroků p, q výroková formule výroková formule Φ je logicky ekvivalentní s výrokovou formulí Ψ výroková formule Φ je tautologie výroková forma o jedné proměnné x negace výrokové formy o jedné proměnné x disjunkce výrokových forem o téže proměnné x ostrá disjunkce výrokových forem o téže proměnné x konjunkce výrokových forem o téže proměnné x implikace výrokových forem o téže proměnné x ekvivalence výrokových forem o téže proměnné x množiny prvky množiny prvek a náleží množině A, prvek a patří do množiny A, a je prvkem množiny A prvek b nenáleží množině A, prvek b nepatří do množiny A, b není prvkem množiny A množina prázdná množina A je podmnožinou množiny B, množina B je nadmnožinou množiny A množina A je rovna množině B množina A je různá od množiny B potenční systém množiny M číslo a dělí číslo b, číslo b je násobkem čísla a číslo a je větší nebo rovno číslu b přímka a je rovnoběžná s přímkou b přímka a je kolmá na přímku b sjednocení množin A, B průnik množin A, B symetrický rozdíl množin A, B rozdíl množin v daném pořadí doplněk množiny A vzhledem k základní množině uspořádaná dvojice prvků a, b kartézský součin množin A, B doplňková relace relace inverzní lineárně uspořádaná množina množina A je ekvivalentní s množinou B lineárně uspořádaná množina (M1 , R1 ) je podobná lineárně uspořádané množině (M2 , R2 ) algebraická struktura s jednou operací algebraická struktura se dvěma operacemi algebraické struktury jsou izomorfní
45
D(a, b) N(a, b) D(a, b) N (a, b)
množina všech společných dělitelů čísel a, b množina všech společných násobků čísel a, b největší společný dělitel čísel a, b největší společný násobek čísel a, b
46
Literatura [1] Benda, P. Sbírka maturitních příkladů z matematiky. Praha: SPN, 1983. [2] Blažek, J. a kol. Algebra a teoretická aritmetika. I.díl. Praha: SPN, 1983. [3] Burian, K., Libicher, J. Algebra I. . Skripta PF Ostrava, 1982. [4] Bušek, I. Řešené maturitní úlohy z matematiky. Praha: SPN, 1985. [5] Dvořák, F., Ženčáková, R. Základy moderní matematiky. Skripta PF UP Olomouc, 1974. [6] Hájek, J. Úvod do teorie množin a matematické logiky. Skripta PF UJEP Brno, 1975. [7] Križalkovič, K., Cuninka, A., Šedivý, O. Riešené úlohy z modernej matematiky. Bratislava: Alfa, 1974. [8] Libicher, J. Algebra. Algebraické struktury. Skripta PF Ostrava, 1973. [9] Novotná, V., Pisklák, B. Cvičení z elementární aritmetiky a elementární geometrie, část I. . Skripta PdF OU Ostrava, 1996. [10] Šedivý, J. O modernizaci školské matematiky. Praha: SPN, 1973. [11] Šindelář, K., Kopka, J. Matematika pro učitele základních škol. Praha: SPN, 1980. [12] Viktora, V. Matematika I pro studium učitelství 1. stupně základní školy. Skripta PF UJEP Brno, 1974.
47
