Rozvoj předčíselných představ 1 Eva Nováková Několik slov úvodem Předkládaný učební text je určen vám, studentům učitelství pro mateřské školy v prezenční i kombinované formě. Je studijní oporou k předmětu „Rozvoj předčíselných představ 1“, prvnímu semestru kurzu, který vás má vybavit potřebnými kompetencemi k rozvíjení matematických představ a zkušeností z reálného života dítěte v prostředí mateřské školy. V úvodu chci poděkovat PaedDr. Anně Stopenová, Ph.D. a RNDr. Jindřišce Eberové z Katedry matematiky Pedagogické fakulty UP v Olomouci. V letech strávených doktorským studiem se mi obě staly oporou v začátcích mého pedagogického působení na vysoké škole při vedení cvičení ze základů matematiky v oboru Učitelství pro 1. stupeň ZŠ. V tomto období byly rovněž zpracovány výukové materiály, s nimiž jsem ve své výuce pracovala a na jejichž ověřování jsem se podílela. S laskavým svolením obou autorek byly části těchto pracovních materiálů využity rovněž při zpracování této studijní opory. Děkuji rovněž kolegyním z Katedry matematiky Pedagogické fakulty MU v Brně RNDr. Růženě Blažkové, CSc. a RNDr. Mileně Vaňurové, CSc., za řadu cenných připomínek směřujících ke zkvalitnění textu. Využít zkušeností z reálného života a na základě nich rozvinout velký potenciál dětského prožívání vlastních aktivit vyžaduje od učitelky mateřské školy alespoň základní oborově předmětové znalosti. Potřebné základy vybraných partií matematiky poskytuje následující studijní materiál. Text je členěn do 9 kapitol. Záměrem autorky je navázat a udržovat s vámi kontakt prostřednictvím průvodce studiem. Každá z kapitol má zřetelně vymezené cíle a přibližný odhad času, který budete k prostudování kapitoly potřebovat (samozřejmě časová náročnost je zcela individuální, záleží na vašich předběžných znalostech a studijním nasazení). V průběhu výkladu, který se opírá o řešené příklady, jsou zdůrazněny důležité pasáže textu, kterým je třeba věnovat zvýšenou pozornost Studium vyžaduje samostatné vyřešení kontrolních úkolů, které byste po prostudování kapitoly měli umět vyřešit s oporou o klíč k řešení - výsledky kontrolních úkolů. Rozšíření a prohloubení vašich poznatků nad rámec základního učiva kurzu je umožněno prostudováním partií označených pro zájemce. V závěru každé kapitoly je uvedeno stručné shrnutí jejího obsahu a nejdůležitější pojmy k zapamatování. V předmětu budeme využívat vašich dosavadních znalostí a vlastních zkušeností s matematikou a jejími praktickými aplikacemi v roli žáků základních a středních škol. Půjde nám společně o to, ukázat matematické poznatky jako zajímavé a podnětné pro rozvoj vašich profesních kompetencí a rozvinout příznivý vztah k matematice. Autorka Obsah 1 Základní pojmy výrokové logiky 1.1 Výrok 1.2 Negace výroku 1.3 Složené výroky 1.3.1 Konjunkce výroků 1.3.2 Disjunkce výroků 1.3.3 Implikace výroků 1.3.4 Ekvivalence výroků 1.4 Výrokové formule. Tautologie, kontradikce a splnitelná formule 1.5 Užití poznatků logiky při řešení slovních úloh 2 Základní pojmy predikátové logiky 2.1 Výroková forma (predikát) 2.2 Kvantifikované výroky 2.3 Negace kvantifikovaného výroku 3 Množiny 3.1 Množina, prvek množiny, množinové relace 3.1.1 Množina a prvek množiny 3.1.2 Množinové relace (vztahy mezi množinami) 3.2 Množinové operace 3.2.1 Přehled množinových operací 3.2.2 Vlastnosti operací s množinami 3.2.3 Slovní úlohy, řešené pomocí množinových operací 4 Kartézský součin 5 Binární relace 5.1 Pojem binární relace 5.2 Vlastnosti binárních relací 6 Relace ekvivalence a rozklad množiny 7 Relace uspořádání 8 Relace zobrazení 9 Ekvivalence množin Použitá a doporučená literatura 1 Základní pojmy výrokové logiky Cíle Po prostudování této kapitoly budete schopni · používat a interpretovat základní pojmy výrokové logiky, · formulovat výroky, negovat je a přiřazovat jim pravdivostní hodnoty, · charakterizovat složené výroky (konjunkci, disjunkci, ostrou disjunkci, implikaci, ekvivalenci dvou výroků) a vytvořit tabulky pravdivostních hodnot složených výroků, tvořit nové (složené) výroky pomocí výrokotvorných spojek a pravdivostně je ohodnocovat, · rozlišit a charakterizovat výrokové formule (tautologie, kontradikce a splnitelné formule) a pravdivostně je ohodnocovat, · řešit některé slovní úlohy využitím znalostí výrokové logiky. Průvodce studiem: Logika je věda, která se zabývá usuzováním, pravdivostí, dokazatelností a vyvratitelností. Přitom jde pouze o formu sdělení, nezajímá nás, co konkrétně je sdělováno, jaký je obsah sdělení. V této kapitole se seznámíte se základními pojmy logiky, jejich používáním a vyhodnocováním. V dalších kapitolách budete těchto znalostí využívat. Předpokládejte, že kapitolu prostudujete přibližně za 6 hodin. Pro zájemce: Matematická logika jako jedno z odvětví matematiky vychází z prací řeckého filozofa Aristotela ze Stageiry (384 - 322 př.n. l.), který je považován za jednoho z nejuniverzálnějších myslitelů starověku. Žil v Aténách, kde založil vlastní filozofickou školu, významně zasáhl do zkoumání v řadě oborů - etika, estetika, přírodověda. Jeho dílo (spisy pod souborným názvem „Organon“) bylo v latinském překladu velmi rozšířené, až do 15. stol. bylo považováno za nezvratné a nezpochybnitelné. 1.1 Výrok Důležitá pasáž textu: Základním pojmem výrokové logiky je výrok. Výrokem rozumíme každé sdělení, o kterém můžeme rozhodnout, zda je pravdivé či nepravdivé. Každý výrok má právě jednu pravdivostní hodnotu (buď je pravdivý, nebo nepravdivý). Výrok má vždy tvar oznamovací věty. Výroky nejsou věty rozkazovací, tázací - tedy všechna sdělení, o jejichž pravdivosti nebo nepravdivosti nemůžeme rozhodnout. Příklady sdělení, která jsou výrokem: a) Čtverec je pravidelný čtyřúhelník. b) Dnes je pátek. c) Praha je hlavní město ČR. d) 5 < 2 e) Slepice má čtyři nohy. Příklady sdělení, která nejsou výrokem: a) Kolik je hodin? b) Narýsuj kružnici. c) x > 10 d) Trojúhelník je rovnostranný. e) Přímka x je rovnoběžná s přímkou y. Výrokům přisuzujeme pravdivostní hodnoty: výrok je pravdivý (pravda, p) …………… 1 výrok je nepravdivý (nepravda, n) ……….0 Ve výrokové logice abstrahujeme od obsahu jednotlivých výroků, zavádíme místo konkrétních výroků výrokové proměnné A, B,... . Krátce můžeme uvádět výrok A, výrok B. Průvodce studiem: Formulování výroků a přiřazování pravdivostních hodnot výrokům je činnost, kterou děti provádějí již v době, kdy se učí mluvit mateřským jazykem. Je proto účelné, abyste obdobně postupovali i při studiu a osvojování matematického jazyka. Doporučuji vám věnovat pozornost přesným formulacím výroků v jazyce matematiky, jejich symbolickým zápisům, upřesnění podstaty přiřazování pravdivostních hodnot výrokům, osvojení si způsobů usuzování a kontroly správnosti úsudků. Kontrolní úkoly: 1. Rozhodněte, která z těchto sdělení jsou výroky a zdůvodněte proč. U výroků rozhodněte o jejich pravdivosti. a) Základy výrokové logiky. b) Narýsuj kružnici. c) 27 + 16 = 33. d) Dnes venku prší. e) Adélka má červené tričko. 2. Zformulujte sami několik sdělení, která jsou (nejsou) výroky. Zdůvodněte. Průvodce studiem: Povšimněme si nepravdivého výroku 27 + 16 = 33. S uvedeným tvrzením (sdělením) nesouhlasíme, popíráme jej. Popřením tohoto výroku je tvrzení: 27 + 16 ≠ 33, které je pravdivým výrokem. 1.2 Negace výroku Průvodce studiem: V reálném životě můžeme vyslovit oznamovací větu: „Alenka má ráda kakao“. Uvedenou větu lze považovat za výrok (protože je možné v konkrétním případě rozhodnout, zda je sdělení pravdivé nebo nepravdivé; určitě nastane právě jedna z možností). Když ale Alenka kakao ráda nemá, vyjádříme tuto skutečnost výrokem: „Není pravda, že Alenka má ráda kakao“ nebo jinak stylizovaným výrokem „Alenka nemá ráda kakao“. Podívejme se, jak můžeme popsanou situaci vyjádřit v matematické logice. Nejprve definujeme pojem negace výroku. Důležitá pasáž textu: Připojíme-li před určitý výrok slova "není pravda, že", popř. provedeme stylistické úpravy, které mají týž význam jako uvedená slova, dostaneme negaci výroku. Negaci výroku A zapisujeme A¢ nebo ┐A . Je-li výrok A pravdivý, je jeho negace A¢ nepravdivá. Je-li výrok A nepravdivý, je jeho negace A¢ pravdivá. Výrok A: „Alenka má ráda kakao“. Negací výroku A je výrok A¢: „Není pravda, že Alenka má ráda kakao“ nebo „Alenka nemá ráda kakao“. O pravdivosti původního výroku i jeho negace bychom ovšem mohli rozhodnout až na základě posouzení konkrétní situace, např. „Alenka Nováková z předškolního oddělení MŠ Pohádka v Brně má - nemá ráda kakao“. Řešený příklad 1: Je dán výrok A: 3 . 5 = 15. Utvořte jeho negaci a určete pravdivostní hodnotu výroku A i jeho negace. Řešení: Pravdivostní hodnota výroku A je 1. Negací výroku A je výrok A´: Není pravda, že 3 . 5 = 15. Jiným způsobem vyjádření negace výroku A může být výrok: 3 . 5 ¹ 15. Pravdivostní hodnota výroku A´ je 0. Výrok A je pravdivý, potom výrok A´ je nepravdivý. Tabulka pravdivostních hodnot negace výroku: A A´ 1 0 0 1 Poznámka: Při vytváření negace je třeba dát pozor na úplné popření původního tvrzení. Řešený příklad 2: Je dán výrok B: „Tento papír je bílý“. Utvořte jeho negaci a určete pravdivostní hodnotu negace výroku B. Řešení: Negace výroku B: „Není pravda, že tento papír je bílý“. (Tento papír není bílý.) Výrok "Tento papír je černý" není negací výroku B. Kontrolní úkoly: 1. Vytvořte negace výroků : a) Filip má na hlavě čepici. b) Tatínek je vyšší než maminka. c) Sníh je bílý. d) 25 > 30 e) Náš Honza nepřišel domů. 2. Určete pravdivostní hodnotu výroku, utvořte jeho negaci a určete pravdivostní hodnotu negace výroku: a) Univerzita Karlova byla založena v roce 1348. b) Číslo 3 je prvočíslo. c) Číslo 0 je sudé číslo. 3. Formulujte negace výroků: a) Můj otec je starší než má matka. b) Měsíc březen nemá 32 dní. c) 3627 : 15 = 245 4. Který z následujících výroků je negací výroku „Petr nepřišel“: a) Michal přišel. b) Michal nepřišel. c) Není pravda, že Petr přišel. d) Petr přišel. 1.3 Složené výroky V běžné komunikaci se obvykle nevyjadřujeme jednoduchými větami, ale spojujeme je v souvětí. Ve výrokové logice nás především zajímají pravdivostní hodnoty složených výroků, které vytvoříme ze dvou nebo více výroků. Složené výroky jsou konjunkce, disjunkce, implikace a ekvivalence. Tvoříme je pomocí výrokotvorných spojek, tzv. funktorů, které zapisujeme zvláštními symboly (funktory). 1.3.1 Konjunkce výroků Důležitá pasáž textu: Konjunkce dvou výroků A a B je složený výrok, který vytvoříme pomocí spojky „a“ („a současně“). Označujeme jej A Ù B. Konjunkce je pravdivá, jsou-li oba výroky A, B pravdivé. V ostatních případech je konjunkce A Ù B nepravdivá. Řešený příklad: Výrok A: „Číslo 15 je liché číslo“. Výrok B: „Číslo 15 je dělitelné sedmi“. Konjunkce výroků AÙB: Číslo 15 je liché číslo a je dělitelné sedmi. Výrok A je pravdivý, proto pravdivostní hodnota výroku A je 1. Výrok B je nepravdivý, proto pravdivostní hodnota výroku B je 0. Pravdivostní hodnota konjunkce výroků A, B je 0, konjunkce je nepravdivá (viz 2. řádek tabulky). Pro pravdivostní hodnoty konjunkce výroků AÙB nastanou čtyři možnosti, které můžete zapsat následovně: 1. oba výroky A, B jsou pravdivé, konjunkce AÙ B je výrok pravdivý, 2. výrok A je pravdivý, výrok B je nepravdivý, konjunkce AÙB je výrok nepravdivý, 3. výrok A je nepravdivý, výrok B je pravdivý, konjunkce AÙB je výrok nepravdivý, 4. oba výroky A, B jsou nepravdivé, konjunkce AÙB je výrok nepravdivý. Uvedené možnosti můžeme přehledně vyjádřit tabulkou pravdivostních hodnot konjunkce dvou výroků: A B A Ù B 1 1 1 1 0 0 0 1 0 0 0 0 Poznámka: V běžné řeči je někdy obtížné rozeznat konjunkci v textu, který bývá ze stylistických důvodů zestručněn. Např. „Můj otec s matkou přišli domů“. Vyjadřuje konjunkci: „Můj otec přišel domů a má matka přišla domů“. Kontrolní úkoly: 1. Určete pravdivostní hodnoty konjunkcí: a) Karel IV. byl českým králem a římským císařem. b) 10 < 25 Ù 10 je číslo liché. c) Úhlopříčky v obdélníku jsou k sobě kolmé a navzájem se půlí. d) Dnes je pondělí a zítra je úterý. 2. Vyjádřete stručněji následující konjunkce. Určete pravdivostní hodnotu těchto složených výroků: a) Lukáš je synem paní Navrátilové a Lukáš je bratrem Jany. b) Číslo 3 je dělitelem čísla 132 a číslo 3 je dělitelem čísla 231. 3. Určete jednoduché výroky, z nichž jsou konjunkce složené. Rozhodněte o pravdivosti těchto výroků a pravdivosti konjunkce: a) Brno a Olomouc jsou moravská města. b) Čísla 24 a 54 jsou násobky čísla 8. c) Číslo 45 je dělitelné čtyřmi a sedmi. 1.3.2 Disjunkce výroků Důležitá pasáž textu: Disjunkce dvou výroků A, B je složený výrok, který vytvoříme pomocí spojky "nebo". Označujeme jej AÚB. Disjunkce je pravdivá, je-li pravdivý aspoň jeden z výroků A, B. Ve zbývajícím případě je disjunkce nepravdivá. Řešený příklad 1: Výrok A: „Dnes jsem zaspal“. Výrok B: „Dnes mi ujela tramvaj“. Disjunkce výroků AÚ B: „Dnes jsem zaspal nebo mi ujela tramvaj“. Pro pravdivostní hodnoty disjunkce AÚB výroků A, B nastanou čtyři možnosti, které můžeme zapsat následovně: 1. oba výroky A, B jsou pravdivé, disjunkce AÚB je výrok pravdivý, (zaspal jsem nebo mi ujela tramvaj) 2. výrok A je pravdivý, výrok B je nepravdivý, disjunkce AÚ B je výrok pravdivý, (zaspal jsem nebo mi neujela tramvaj) 3. výrok A je nepravdivý, výrok B je pravdivý, disjunkce AÚ B je výrok pravdivý, (nezaspal jsem nebo mi ujela tramvaj) 4. oba výroky A, B jsou nepravdivé, disjunkce AÚ B je výrok nepravdivý. (nezaspal jsem nebo neujela mi tramvaj) Uvedené možnosti můžeme přehledně vyjádřit tabulkou pravdivostních hodnot disjunkce dvou výroků: A B A Ú B 1 1 1 1 0 1 0 1 1 0 0 0 Řešený příklad 2: Výrok A: 2 > 2 Výrok B: 2 = 2 Disjunkce výroků A Ú B: 2 > 2 Ú 2 = 2, což můžeme zapsat 2 ³ 2. Pravdivostní hodnota výroku A je 0. Pravdivostní hodnota výroku A je 1. Pravdivostní hodnota disjunkce výroků A, B je 1, disjunkce je pravdivá (viz 3. řádek tabulky). Poznámka: Spojky "nebo" se v hovorové řeči používá ve vylučovacím smyslu na rozdíl od jazyka výrokové logiky. Řešený příklad: Výrok A: „Studuji učitelství pro mateřské školy na univerzitě v Brně“. Výrok B: „Studuji učitelství pro mateřské školy na univerzitě v Prešově“. Ve složeném výroku jsme zde použili spojky nebo ve vylučovacím smyslu (nepředpokládáme, že by student současně studoval stejný obor na dvou univerzitách). V matematice v tomto případě raději použijeme spojky "buď - nebo". Ostrá disjunkce výroků A Ú B: „Buď studuji učitelství pro mateřské školy na univerzitě v Brně, nebo v Prešově“. Ostrou disjunkcí dvou výroků A, B rozumíme takový výrok, který je pravdivý právě tehdy, když je právě jeden z výroků A, B pravdivý. Ostrou disjunkcí výroků A, B budeme značit A Ú B, kde funktor Ú odpovídá slovnímu spojení „buď... ,nebo...“. Pravdivostní hodnoty ostré disjunkce dvou výroků A Ú B jsou vyjádřeny v tabulce: A B A Ú B 1 1 0 1 0 1 0 1 1 0 0 0 Kontrolní úkoly: 1. Rozhodněte, zda se jedná o disjunkci nebo ostrou disjunkci. Určete pravdivostní hodnoty složených výroků: a) Dnes večer půjdu do divadla nebo do kavárny. b) Na tento los vyhraji auto nebo zájezd. c) Lionel Messi je hráčem Barcelony nebo Realu Madrid. d) 3 = 3 Ú 3 < 2 e) 12 < 7 Ú 3 ¹ 3 2. Zapište pomocí složených výroků: a) Přijde aspoň jeden z mých rodičů. b) Přijde právě jeden z mých rodičů. 3. Určete jednoduché výroky, z nichž jsou disjunkce složené. Rozhodněte o pravdivosti těchto výroků a pravdivosti disjunkce: a) Jirka si hrál s míčem nebo se stavebnicí. b) Odpoledne půjdeme na vycházku nebo na hřiště. c) 6:3 = 3.6 Ú (16:4):2 = 16: (4:2) 1.3.3 Implikace výroků Důležitá pasáž textu: Implikace ve složený výrok, který vznikne spojením dvou výroků pomocí výrazu „jestliže – pak“. Označujeme jej A => B. Implikace je nepravdivá, jestliže první výrok A (předpoklad) je pravdivý a současně druhý výrok B (tvrzení) je nepravdivý. V ostatních případech je implikace pravdivá. Řešený příklad: Výrok A: „Dnes půjdu do kina“. Výrok B: „Zítra se budu učit“. Implikace výroků A => B: „Jestliže dnes půjdu do kina, pak se zítra budu učit“. Pravdivostní hodnoty implikace dvou výroků A, B jsou vyjádřeny v tabulce: A B AÞ B 1 1 1 1 0 0 0 1 1 0 0 1 Průvodce studiem: Opět připomeňme z kap. 1.1. významnou skutečnost, že v (matematické) logice abstrahujeme od obsahové stránky jednotlivých sdělení (výroků). V hovorové řeči používáme spojení „jestliže - pak“ pro vyjádření vztahu mezi příčinou a následkem. Například ze skutečnosti, že „venku prší“ usuzujeme, že „je venku mokro“ (že je venku mokro je následkem toho, že venku prší). Ve výrokové logice však neklademe na vzájemnou obsahovou souvislost složených výroků žádné požadavky. Ukážeme si to na následujících ukázkách. Řešený příklad 1: Určete pravdivostní hodnotu implikace „Jestliže 2 . 2 = 5, pak dnes venku prší.“ Řešení: Výrok A: "2 . 2 = 5“ Výrok B: „Dnes venku prší“. Výrok A je nepravdivý. Výrok B může nebo nemusí být pravdivý. Implikace „Jestliže 2 . 2 = 5, pak dnes venku prší“ je pravdivá bez ohledu na pravdivostní hodnotu druhého výroku (to vyplývá ze třetího a čtvrtého řádku tabulky pravdivostních hodnot implikace). Uvědomte si tedy, že implikace v případě, kdy první výrok je nepravdivý, je vždy pravdivá. Řešený příklad 2: Utvořte implikaci výroků A, B a určete pravdivostní hodnotu implikací A => B a B => A. Výrok A: „Číslo 28 je liché“. Výrok B: „Číslo 28 je dělitelné číslem 7“. Řešení: Implikace A => B má tvar: „Jestliže je číslo 28 liché, pak je číslo 28 dělitelné číslem 7“. Výrok A je nepravdivý, výrok B je pravdivý. Implikace A => B je pravdivá. Implikace B => A má tvar: „Jestliže je číslo 28 dělitelné číslem 7, pak je číslo 28 liché“. Výrok A je pravdivý, výrok B je nepravdivý Implikace B => A je nepravdivá. V uvedeném příkladu si všimněte následujícího jevu. Je-li implikace A => B pravdivá, neznamená to, že by musela být také obrácená implikace B => A pravdivá. Implikaci B => A vzhledem k implikaci A => B nazýváme implikace obrácená. Tuto skutečnost můžete sledovat v následující tabulce: A B A Þ B B Þ A 1 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1 Kontrolní úkoly: 1. Utvořte implikace z následujících výroků: a) Výrok A……Překročil(a) jsem dovolenou rychlost jízdy. Výrok B……Zaplatil(a) jsem pokutu. b) Výrok A……Byl(a) jsem na dovolené u moře. Výrok B……Byl(a) jsem na dovolené v Chorvatsku. c) Výrok A……Číslo 28 je dělitelné čtyřmi. Výrok B……Číslo 28 je dělitelné dvěma. 2. Určete pravdivostní hodnoty implikací z úlohy 1. 3. Utvořte k implikacím v úloze 1 implikace obrácené a určete jejich pravdivostní hodnoty. Mají implikace a implikace k ní obrácená stejné pravdivostní hodnoty? Vysvětlete. 4. Rozhodněte, jakou pravdivostní hodnotu mají tyto implikace: a) Jestliže 2.5 = 12, pak 4.7 = 28. b) Jestliže 13 je sudé číslo, pak 39 je sudé číslo. c) Jestliže 231 je dělitelné sedmi, pak 3231 je dělitelné sedmi. d) Jestliže -8 >-10, pak 30 > 25. 5. Ve kterých dnech v týdnu jsou pravdivé implikace: a) Je-li dnes úterý, bude zítra pátek. b) Je-li dnes úterý, bude zítra středa. 1.3.4 Ekvivalence výroků Důležitá pasáž textu: Ekvivalence je složený výrok, který vznikne spojením dvou výroků pomocí výrazu „právě tehdy, když“ nebo "tehdy a jen tehdy, když". Označujeme jej A <=> B. Ekvivalence je pravdivá, jestliže oba výroky mají stejnou pravdivostní hodnotu (jsou oba pravdivé nebo jsou oba nepravdivé). Ve zbývajících případech je ekvivalence nepravdivá. Řešený příklad: Výrok A: „Zítra půjdu na koncert“. Výrok B: „Dnes se budu učit“. Ekvivalence výroků A<=> B: „Zítra půjdu na koncert právě tehdy, když se dnes budu učit“. Pravdivostní hodnoty ekvivalence dvou výroků A, B jsou vyjádřeny v následující tabulce: A B A<=> B 1 1 1 1 0 0 0 1 0 0 0 1 Kontrolní úkoly: 1. Určete pravdivostní hodnoty ekvivalence: a) Na klidné hladině vody se tvoří led, právě když teplota vody klesne pod bod mrazu. b) Číslo 26 je menší než 9 právě tehdy, když 27 je menší než 10. c) Číslo 54 je dělitelné 6 právě tehdy, když je dělitelné současně dvěma a třemi. d) 2 . 2 = 4 <=> 4 < 2 2. Rozhodněte, jakou pravdivostní hodnotu mají ekvivalence: a) Dostanu jedničku z písemky, právě když mám všechny úlohy správně vyřešeny. b) Když je na parkovišti volné místo, mohu zaparkovat. c) (27 > 26) <=> (27 < 10) 3. Náměty na praktická cvičení: a) Vyberte si krátký text z některého časopisu pro děti předškolního věku (Sluníčko, Mateřídouška aj.), vyhledejte v něm výroky, složené výroky a pokuste se je zapsat symbolicky pomocí logických spojek. b) Najděte definice v učivu matematiky, které mají tvar ekvivalence. Např.: Trojúhelník je rovnostranný, právě když má všechny strany shodné. 1.4 Výrokové formule. Tautologie, kontradikce a splnitelná formule Průvodce studiem: V předchozích kapitolách jste se seznámili se základními pojmy výrokové logiky. Vyjadřovali jsme je pomocí speciálních termínů a symbolů, které charakterizují jazyk logiky podobně jako jiné termíny jsou charakteristické pro jiné vědní disciplíny nebo jiné obory lidské činnosti. V matematice používáme řadu speciálních znaků, symbolů, například číslice 0, 1, 2, …9, znaky pro vztahy mezi čísly = , <, >, geometrické symboly aj. Uvádíme soubor znaků, které budeme dále používat: Pokusíme se vymezit soubor znaků, se kterými vystačíme ve výrokové logice. Jsou to: 1) Znaky pro výrokové proměnné A, , C, B... a znaky pro konstanty 1, 0, kde 1 značí pravdivý výrok, 0 nepravdivý výrok. 2) Znaky pro logické spojky (funktory) ´ , Ù , Ú , => , <=> , Ú . 3) Závorky ( ), {}, [ ] . Dosud jsme spojovali pouze dva výroky, možné je ale spojení i více výroků. Používá se závorek, které mají při zapisování výrazů výrokové logiky stejný význam jako závorky používané při početních operacích s čísly. Závorky udávají pořadí kroků, kterými je složitější výraz utvořen z jednodušších. Důležitá pasáž textu: Říkáme, že výrokové proměnné, konstanty, funktory a závorky tvoří abecedu výrokové logiky. Pomocí těchto znaků můžeme vytvářet libovolně složené výrazy, které nazýváme výrokovými formulemi (složenými výroky). Výrokové formule jsou tedy zápisy, ve kterých se vyskytují výrokové proměnné, logické spojky, závorky, přip. konstanty 1, 0 a přitom ze kterých po dosazení konkrétních výroků za výrokové proměnné vznikne výrok. Například (AÚB)´ =>C je výroková formule, ale A=>)BÙC není výroková formule. Jestliže nějaké výrazy X, Y jsou výrokovými formulemi, potom také X´ , Y ´, X ÙY, X Ú Y, X Ú Y, X => Y, X <=> Y jsou výrokové formule a žádné jiné výrazy nejsou výrokové formule. Stejně jako u složených výroků nás zajímá, jaké pravdivostní hodnoty nabývá výroková formule pro různé pravdivostní hodnoty jednotlivých výrokových proměnných. Pro každou výrokovou formuli nastane právě jedna z těchto možností: a) Výroková formule, která je vždy pravdivá pro jakékoliv pravdivostní hodnoty výrokových proměnných, se nazývá tautologie. b) Výroková formule, která je vždy nepravdivá pro všechny pravdivostní hodnoty výrokových proměnných, se nazývá kontradikce. c) Výroková formule, která je pro některé pravdivostní hodnoty výrokových proměnných pravdivá a pro jiné pravdivostní hodnoty výrokových proměnných nepravdivá, se nazývá splnitelná formule. Řešený příklad 1: Určete pravdivostní hodnoty výrokové formule (AÚ B)´ <=> (A´Ù B´) a porovnejte je. Řešení najdete v tabulce. A B A´ B´ AÚ B (AÚ B )´ A´ Ù B´ (AÚ B )´<=>( A´ Ù B´) 1 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 1 1 1 Jestliže vyhodnotíme například výrokovou formuli (AÚ B)´<=>(A´Ù B´), dostaneme ve všech případech pravdivostní hodnotu 1 bez ohledu na pravdivost či nepravdivost samotných výroků A, B. Tato výroková formule je tautologie. Řešený příklad 2: Určete pravdivostní hodnoty výrokové formule (A Ù B) <=> (A´Ú B) a porovnejte je. Řešení najdete v tabulce. A B A´ B´ (AÙ B ) A´ Ú B´ (A Ù B) <=> (A´Ú B) 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0 Jestliže vyhodnotíme například výrokovou formuli (AÙ B ) <=> A´ Ú B´, dostaneme ve všech případech pravdivostní hodnotu 0 bez ohledu na pravdivost či nepravdivost samotných výroků A, B. Tato výroková formule je kontradikce. Řešený příklad 3: Určete pravdivostní hodnoty výrokové formule (AÚ B )´ <=> (A´Ú B´) a porovnejte je. Řešení najdete v tabulce. A B A´ B´ AÚ B (AÚ B )´ A´ Ú B´ (AÚ B )´ <=> (A´Ú B´) 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 1 1 Jestliže vyhodnotíme například výrokovou formuli (AÚB)´ <=> (A´Ú B´), dostaneme v některých případech pravdivostní hodnotu 1, v některých případech pravdivostní hodnotu 0,bez ohledu na pravdivost či nepravdivost samotných výroků A, B. Tato výroková formule je splnitelná formule. Mají-li dvě výrokové formule stejné pravdivostní hodnoty, říkáme, že jsou logicky ekvivalentní (zapisujeme ~), neděláme mezi nimi rozdíl, jednu můžeme nahradit druhou. Spojíme-li je spojkou ekvivalence, dostaneme tautologii. Pro zájemce: Uvádíme několik ekvivalentních výrokových formulí: 1. (A Ù B) ~ (B Ù A) komutativnost konjunkce 2. (A Ú B) ~ (B Ú A) komutativnost disjunkce 3. (AÙ B)Ù C ~ AÙ ( BÙ C) asociativnost konjunkce 4. (AÚ B) Ú C ~ A Ú (BÚ C) asociativnost disjunkce 5. (A Ù B) Ú C ~ (A Ú C) Ù (B Ú C) distributivnost disjunkce vzhledem ke konjunkci 6. (A Ú B) Ù C ~ (A Ù C) Ú (B Ù C) distributivnost konjunkce vzhledem k disjunkci 7. (A´ )´ ~ A zákon dvojí negace 8. A Ú A´ ~ 1 zákon vyloučení třetí možnosti 9. A Ù A´ ~ 0 zákon sporu 10. (A <=> B) ~ (A => B) Ù (B => A) nahrazení ekvivalence pomocí implikace a konjunkce 11. (A Ú B)´ ~ (A´ Ù B´) de Morganův zákon 12. (A Ù B)´ ~ (A´Ú B´ ) de Morganův zákon 13. (A => B) ~ (B´ => A´ ) nahrazení implikace implikací obměněnou Kontrolní úkoly: 1. Vyberte si některá z výše uvedených vztahů a tvrzení ověřte. 2. Sestavte tabulky pravdivostních hodnota a rozhodněte, zda se jedná o tautologii, kontradikci nebo splnitelnou formuli.Všímejte si, jak závisí pravdivost či nepravdivost následujících výrokových formulí na pravdivosti či nepravdivosti výroků A, B. a) A Þ (B Þ A) b) (A Ú B)´Ù (A´Þ B) c) (A´ Ú B´) Þ (A Ú B)´ 3. Vytvořte tabulky pravdivostních hodnot výrokových formulí. Rozhodněte, zda se jedná o tautologii, kontradikci nebo splnitelnou formuli : a) (A ´ => A) => A b) B => (B => A) c) (A => B)´ <=> ( A Ù B´) d) (A <=> B)´ <=> (AÙ B´ ) Ú (A´Ù B) 1.5 Užití poznatků logiky při řešení slovních úloh Průvodce studiem: V následující kapitole naznačíme možnosti uplatnění poznatků z výrokové logiky, které jste si právě osvojili, jako vhodného nástroje k řešení slovních matematických úloh. Příklad je ukázkou tzv. matematizace reálné situace. Řešený příklad: V dílně pracují tři stroje podle následujících podmínek : a) Jestliže pracuje-li první stroj, pracuje i druhý stroj. b) Pracuje druhý nebo třetí stroj. c) Jestliže nepracuje první stroj, pak nepracuje ani třetí stroj. Jak pracují jednotlivé stroje ? Řešení: Zapíšeme jednotlivé podmínky úlohy (výroky o práci jednotlivých strojů) pomocí výrokových proměnných. Výrok "pracuje první stroj" zapíšeme pomocí výrokové proměnné A, výrok "pracuje druhý stroj" zapíšeme pomocí výrokové proměnné B, výrok "pracuje třetí stroj" zapíšeme pomocí výrokové proměnné C. Podmínky úlohy symbolicky zapíšeme výrokovými formulemi: A => B, B Ú C, A´ => C ´ Podmínky úlohy musí být splněny všechny současně, proto nás bude zajímat konjunkce K těchto tří podmínek. Vyjádříme ji výrokovou formulí: K ~ (A => B) Ù (B Ú C) Ù (A ´ => C´). Pro určení pravdivostních hodnot je dobré vytvořit tabulku, ze které vyčtete pravdivost konjunkce K. Vytvoříme tabulku pro 3 individuální výroky A, B, C. Dosud jsme vytvářeli tabulky pouze pro 2 výroky - abychom v tabulce zachytili všechny možné případy, jednotlivé pravdivostní hodnoty jsme zapsali do 4 řádků. Pro větší počet výroků určíme počet řádků jako 2^n, kde n je počet výroků. V naší úloze budeme tedy potřebovat 8 řádků (2^3), které vyplníme podle naší ukázky. Dbáme na to, abychom na žádnou možnost nezapomněli a abychom některou z možností nezapsali vícekrát. A B C A´ C´ AÞ B B Ú C A´Þ C´ K 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 1 0 Z tabulky zjistíte, že konjunkce je pravdivá ve třech případech (1., 2. a 6. řádek), existují tedy tři možnosti pro práci této trojice strojů: a) V 1. řádku tabulky je konjunkce pravdivá, pracují všechny tři stroje. b) V 2. řádku tabulky je konjunkce pravdivá, pracuje jen první a druhý stroj. c) V 6. řádku tabulky je konjunkce pravdivá, pracuje jen druhý stroj. Kontrolní úkoly: 1. Některý z žáků A, B, C rozbil okno. Bylo zjištěno, že v té době nebyl u okna žák A nebo u něj nebyl žák B. Když B nebyl u okna, nebyl tam ani A. Žák C byl u okna právě tehdy, když u něho nebyl žák A. Lze určit pachatele jednoznačně v případě, že byl právě jeden? 2. O třech podezřelých A, B, C byly prověřeny tyto informace: Jestliže spáchal čin B, pak je podezřelý i C. Spáchal-li trestný čin podezřelý C, pak mu pomáhal podezřelý A. Nespáchal-li čin podezřelý B, podílel se na činu i podezřelý C. Je-li vinen podezřelý A, není vinen podezřelý B. Jaký závěr musel učinit vyšetřující soudce? Shrnutí: Základním pojmem logiky je výrok. Pro každý výrok nastane právě jedna z možností – výrok je pravdivý (1), výrok je nepravdivý (0). Výroky můžeme negovat. Je-li výrok A pravdivý, je jeho negace A¢ nepravdivá a obráceně. Složené výroky jsou konjunkce, disjunkce, ostrá disjunkce, implikace a ekvivalence. Pravdivostní hodnoty složených výroků lze vyjádřit tabulkami. Konjunkce je pravdivá, právě když jsou oba výroky pravdivé. Disjunkce je pravdivá, právě když je aspoň jeden z výroků pravdivý. Ostrá disjunkce je pravdivá, když je právě jeden z výroků pravdivý. Implikace je nepravdivá, právě když je první výrok pravdivý, druhý nepravdivý, v ostatních případech je pravdivá. Ekvivalence je pravdivá, když mají oba výroky stejnou pravdivostní hodnotu. Výrokové formule jsou zápisy, ve kterých se vyskytují výrokové proměnné, logické spojky, závorky, přip. konstanty 1, 0 a přitom ze kterých po dosazení konkrétních výroků za výrokové proměnné vznikne výrok. Výrokové formule jsou tautologie, kontradikce a splnitelná formule. Pojmy k zapamatování: * výrok * pravdivostní hodnota výroku * negace výroku * konjunkce dvou výroků * disjunkce dvou výroků * ostrá disjunkce dvou výroků * implikace dvou výroků * ekvivalence dvou výroků * výroková formule, * tautologie, kontradikce, splnitelná formule, * logicky ekvivalentní výrokové formule, * matematizace reálné situace. Klíč - řešení kontrolních úloh: Kap. 1.1 Výrok 1a) Není výrok, nelze rozhodnout o pravdivosti. 1b) Není výrok, nelze rozhodnout o pravdivosti. 1c) Je výrok, nepravdivý. 1d) Je výrok, lze rozhodnout o pravdivosti - v daném čase a na daném místě může nastat právě jedna z možností (prší - neprší). 1e) Je výrok, lze rozhodnout o pravdivosti - v konkrétním případě může nastat právě jedna z možností (má - nemá). Kap. 1.2 Negace výroku 1a) Není pravda, že Filip má na hlavě čepici (Filip nemá na hlavě čepici). 1b) Není pravda, že tatínek je vyšší než maminka (tatínek není vyšší než maminka). 1c) Není pravda, že sníh je bílý (sníh není bílý). 1d) Není pravda, že 25 > 30 (25 < 30). 1e) Není pravda, že náš Honza nepřišel domů (náš Honza přišel domů). 2a) Výrok pravdivý, negace Univerzita Karlova nebyla založena v roce 1348 je nepravdivá. 2b) Výrok pravdivý, negace Číslo 3 není prvočíslo je nepravdivá. 2c) Výrok pravdivý, negace Číslo 0 není sudé číslo je nepravdivá. 3a) Můj otec není starší než má matka. 3b) Měsíc březen má 32 dní. 2c) 3627 : 15 ≠ 245 4 d) Petr přišel. 1.3.1 Konjunkce výroků 1a) Konjunkce je pravdivá, oba výroky jsou pravdivé. 1b) Konjunkce je nepravdivá, první výrok pravdivý, druhý výrok nepravdivý. 1c) Konjunkce je nepravdivá, první výrok nepravdivý, druhý výrok pravdivý. 1d) Lze rozhodnout v konkrétním případě podle konkrétního dne v týdnu (v pondělí je konjunkce pravdivá, v jiné dny nepravdivá). 2a) Lukáš je synem paní Navrátilové a bratrem Jany. 2b) Číslo 3 je dělitelem čísla 132 a čísla 231. Oba výroky jsou pravdivé, konjunkce pravdivá. 2c) Nula je číslo nekladné a nezáporné. Oba výroky jsou pravdivé, konjunkce pravdivá. 3a) Brno je moravské město. Olomouc je moravské město. Oba výroky jsou pravdivé, konjunkce je pravdivá. 3b) Číslo 24 je celočíselným násobkem čísla 8. Číslo 54 je celočíselném násobkem čísla 8. První výrok je pravdivý, druhý výrok je nepravdivý. Konjunkce je nepravdivá. 3c) Číslo 45 je dělitelné čtyřmi. Číslo 45 je dělitelné sedmi. První výrok je nepravdivý, druhý výrok je nepravdivý. Konjunkce je nepravdivá. 1.3.2 Disjunkce výroků 1a) Disjunkce, oba výroky mohou být pravdivé. Disjunkce je pravdivá. 1b) Ostrá disjunkce, pravdivý může být jen jeden z výroků. Ostrá disjunkce je pravdivá. 1c) Ostrá disjunkce, pravdivý může být jen jeden z výroků. Ostrá disjunkce je pravdivá. 1d) Disjunkce je pravdivá, první výrok pravdivý, druhý nepravdivý. 1e) Disjunkce je pravdivá, první výrok nepravdivý, druhý pravdivý. 2a) Přijde můj otec nebo má matka nebo přijdou oba rodiče - AÚB. 2b) Přijde můj otec (matka nepřijde) nebo přijde má matka (otec nepřijde) - AÚ B. 3a) Jirka si hrál s míčem. Jirka si hrál se stavebnicí. Disjunkce je pravdivá, je-li aspoň jeden z výroků pravdivý. 3b) Odpoledne půjdeme na vycházku. Odpoledne půjdeme na hřiště. Disjunkce je pravdivá, je-li aspoň jeden z výroků pravdivý. 3c) 6:3 = 3.6 je výrok nepravdivý, (16:4):2 = 16: (4:2) je výrok nepravdivý. Disjunkce je nepravdivá. 1.3.3 Implikace výroků 1a) Jestliže jsem překročil(a) dovolenou rychlost jízdy, pak jsem zaplatil(a) pokutu. 1b) Jestliže jsem byl(a) na dovolené u moře, pak jsem byl(a) na dovolené v Chorvatsku. 1c) Jestliže je číslo 28 dělitelné čtyřmi, pak je číslo 28 dělitelné dvěma. 3a) Jestliže jsem zaplatil(a) pokutu, pak jsem překročil(a) dovolenou rychlost jízdy. 3b) Jestliže jsem byl(a) na dovolené v Chorvatsku, pak jsem byl(a) na dovolené u moře. 3c) Jestliže je číslo 28 dělitelné dvěma, pak je číslo 28 dělitelné čtyřmi. 4a) Implikace pravdivá. 4b) Implikace pravdivá. 4c) Implikace nepravdivá. 4d) Implikace pravdivá. 5a) Implikace je nepravdivá jen v úterý, v ostatních dnech je pravdivá. 5b) Implikace je pravdivá v každém dni v týdnu. 1.3.4 Ekvivalence výroků 1a) Ekvivalence je pravdivá. 1b) Ekvivalence je pravdivá. 1c) Ekvivalence je pravdivá. 1d) Ekvivalence je ne pravdivá. 2a) Ekvivalence je pravdivá. 2b) Ekvivalence je pravdivá. 2c) Ekvivalence je nepravdivá. 1.4 Výrokové formule. Tautologie, kontradikce a splnitelná formule 2a) Tautologie. A B (B Þ A) A Þ (B Þ A) 1 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 2b) Kontradikce. A B A´ (A Ú B) (A Ú B)´ (A´Þ B) (A Ú B)´Ù (A´Þ B) 1 1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 1 0 1 0 0 2c) Splnitelná formule. A B A´ B´ A Ú B (A´ Ú B´) (AÚ B)´ (A´ Ú B´) Þ (A Ú B)´ 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1 1 3a) Splnitelná formule. A A´ (A ´ => A) (A ´ => A) => A 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 3b) Splnitelná formule. A B B => A B => (B => A) 1 0 1 1 1 0 1 1 0 1 0 0 0 1 0 0 3c) Splnitelná formule. A B B´ (A => B) (A => B)´ ( A Ù B´) (A => B)´ <=> ( A Ù B´) 1 1 0 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 1.5 Užití poznatků logiky při řešení slovních úloh 1. Pachatelem je žák C. 2. Podezřelý B je mimo podezření. 2 Základní pojmy predikátové logiky Cíle Po prostudování kapitoly budete schopni · používat a interpretovat základní pojmy predikátové logiky (výroková forma - predikát, definiční obor, obor pravdivosti), · pochopit souvislost mezi výrokovou formou, individuálním a kvantifikovaným výrokem, · formulovat obecný a existenční výrok, negovat je a přiřazovat jim pravdivostní hodnoty, Průvodce studiem: V předchozí kapitole jsme pracovali s tvrzeními, o jejichž pravdivosti bylo možné jednoznačně rozhodnout. Označili jsme je termínem výrok. Kromě výroků a složených výroků se často setkáváme se slovními vyjádřeními, které obsahují jeden nebo i více blíže neurčených údajů. Nejedná se o výroky, protože o jejich pravdivosti nemůžeme jednoznačně rozhodnout. Ukážeme si, jaký je význam takových sdělení v logice. Předpokládejte, že kapitolu prostudujete přibližně za 3 hodiny. 2.1 Výroková forma (predikát) Důležitá pasáž textu: Výroková forma (predikát) je sdělení ve tvaru oznamovací věty, které obsahuje jeden nebo více blíže neurčených údajů (proměnných). Nemůžeme proto rozhodnout, zda je tvrzení pravdivé nebo nepravdivé. Výrokové formy budeme označovat A(x), čteme A(x) je výroková forma o jedné proměnné x. Příklady výrokových forem: a) A(x): x < 5 b) B(x): číslo x je prvočíslo c) C(x): číslo x je dělitelem 28 d) D(x): student X studuje v 1. ročníku MU Ke každé výrokové formě přiřazujeme dvě množiny: definiční obor výrokové formy a obor pravdivosti výrokové formy. Definičním oborem D výrokové formy A(x) rozumíme množinu D, pro jejíž libovolný prvek d platí, že A(d) je výrok. Oborem pravdivosti P výrokové formy A(x) je podmnožina definičního oboru D, pro jejíž libovolný prvek a platí, že A(p) je pravdivý výrok. Z výrokových forem můžeme tvořit výroky tak, že proměnnou nahradíme některým prvkem definičního oboru proměnné. Říkáme, že tento prvek za proměnnou dosazujeme. Tím vzniká výrok, který nazýváme individuální. Ten může být pravdivý či nepravdivý. Řešený příklad: Je dána výroková forma A(x): x < 5. Určete její definiční obor a obor pravdivosti. Proměnnou x nahradíme některým prvkem z vhodně zvolené množiny, například prvkem z množiny přirozených čísel. Vždy dostaneme z výrokové formy A(x) výrok. Definičním oborem je množina D = N ={1,2,3,4,5,6,...}. Poznámka: Můžeme uvažovat dvě možnosti: a) množinu přirozených čísel N = {1,2,3,4,5,6,...} b) množinu přirozených čísel s nulou N[0 = ]{0, 1,2,3,4,5,6,...}. V našem řešení jsme za definiční obor považovali množinu přirozených čísel „bez nuly“, tj. N. Jestliže za x dosadíme z definičního oboru D číslo 1,2,3 nebo 4, dostaneme výrok, který je pravdivý (např. 4 < 5). Oborem pravdivosti je množina P ={1,2,3,4}. Obor pravdivosti je vždy podmnožinou definičního oboru (P Ì D). Dosadíme-li za x například číslo 7, dostaneme nepravdivý výrok 7 < 5. Číslo 7 není prvkem oboru pravdivosti. Kontrolní úkoly: 1. Rozhodněte, které sdělení je výrok a které výroková forma: a) 28 : 7 = 5 b) Praha je hlavní město ČR. c) Číslo x je dělitelné dvěma. d) Papír je bílý. e) Vltava je nejdelší z českých řek. f) Trojúhelník KLM je pravoúhlý. 2. Jsou dány výrokové formy: a) A(x): x|10 (čteme: x je dělitelem čísla 10) b) B(x): 12|x (čteme: číslo 12 dělí x) c) C(x): 2x £ 6. Určete obor pravdivosti výrokových forem A(x), B(x) a C(x), je-li jejich definičním oborem množina všech přirozených čísel N. 3. Určete definiční obory výrokových forem a obory pravdivosti výrokových forem: a) A(x): x je největším městem ČR b) B(y): y je prvočíslo menší než 10 c) C(z): z je přirozené číslo z|36 (z je dělitelem čísla 36) d) D(t): t^2 < 30 e) A(x): 2x + 1 = 3 2.2 Kvantifikované výroky Průvodce studiem: V předchozím řešeném příkladu jsme si ukázali, jak lze z výrokové formy dosazením za proměnnou některého prvku z definičního oboru vytvořit výrok. Výrok můžeme ale z výrokové formy vytvořit i jiným způsobem, tzv. kvantifikací. Takto vytvořený výrok označujeme jako kvantifikovaný výrok. Řešený příklad: Je dána výroková forma A(x): x < 5, kde za x můžeme dosadit libovolný prvek z množiny přirozených čísel N (x Î N). Jestliže k výrokové formě A(x): x < 5 připojíme "pro každé", dostaneme kvantifikovaný výrok: pro každé přirozené číslo platí, že x < 5. Sousloví „pro každé“ budeme nazývat obecný kvantifikátor a vzniklý výrok nazveme výrok obecný. Jestliže k výrokové formě A(x): x < 5 připojíme "existuje aspoň jedno", dostaneme kvantifikovaný výrok: existuje aspoň jedno přirozené číslo, pro které platí, že x < 5. Sousloví „existuje aspoň jedno“ budeme nazývat existenční kvantifikátor a vzniklý výrok nazveme výrok existenční. Je zřejmé, že obecný výrok z našeho řešeného příkladu je nepravdivý, existenční výrok je pravdivý. Důležitá pasáž textu: Je-li dána výroková forma A(x) s proměnnou x a definičním oborem D, potom kvantifikací výrokové formy A(x) rozumíme připojení jednoho z kvantifikátorů před výrokovou formu A(x): a) " x Î D; A(x) - čteme: Pro každé (pro libovolné, pro všechna) x z množiny D platí A(x). Uvedený výrok se nazývá výrok obecný. b) $ x Î D; A(x) - čteme: Existuje aspoň jedno x z množiny D tak, že platí A(x). Uvedený výrok se nazývá výrok existenční. Kontrolní úkoly: 1. Posuďte význam následujících vět a rozhodněte, které ze slov „každý, všichni, žádný, některý“ je možno doplnit nebo změnit, aby vznikl kvantifikovaný výrok: a) Vlaky ČD jezdí přesně podle jízdního řádu. b) Fanoušci Sparty jsou nesnášenliví. c) Prodavači jsou ochotní. d) Každý neměl zájem o seznámení. e) Všichni nemohli nastoupit. 2. Přečtěte kvantifikované výroky a rozhodněte o jejich pravdivosti: a) "x Î M: x nosí brýle (M je množina všech dětí ve třídě) b) $x Î M: x má 4 nohy (M je množina všech zvířat na farmě) c) $x Î M: x má babičku (M je množina všech dětí v MŠ) d) "x Î M: x je větší než 1 ((M je množina všech přirozených čísel). 2. 3 Negace kvantifikovaného výroku Průvodce studiem: V kapitole o výrokové logice jsme poznali způsob, kterým lze výrok negovat. Připomeňme, že negaci výroku jsme vytvořili tak, že jsme před výrok zařadili slovní spojení „není pravda, že“. Stejným způsobem budeme negovat i kvantifikované výroky. Ukážeme si to na příkladu. Řešený příklad: Negujte kvantifikované výroky a) " x Î N; x < 5. (Čteme: Všechna přirozená čísla x jsou menší než 5.) b) $ x Î N; x < 5. (Čteme: Existuje přirozené číslo x, které je menší než 5. Určete pravdivostní hodnoty výroků i jejich negací. Řešení: a) Negace obecného výroku: není pravda, že " xÎ N; x < 5 (není pravda, že pro každé přirozené číslo x platí, že x je menší než 5. To znamená, že existuje takové přirozené číslo x, které je větší nebo rovno 5. Zapíšeme pomocí existenčního kvantifikátoru: $ x Î N; x ³ 5. [ "x Î N; x < 5 ]´ ~ $ x Î N; x ³ 5. b) Negace existenčního výroku: není pravda, že $ x Î N; x < 5 (není pravda, že existuje přirozené číslo x takové, že x je menší než 5, neboli každé přirozené číslo je větší nebo rovno 5. Zapíšeme pomocí obecného kvantifikátoru: " x Î N; x ³ 5. [$ x Î N; x < 5 ]´ ~ " x Î N; x ³ 5. Výrok "x Î N; x < 5 je nepravdivý, jeho negace $ x Î N; x ³ 5 je pravdivá. Výrok $ x Î N; x < 5 je pravdivý, jeho negace " x Î N; x ³ 5 je nepravdivá. Důležitá pasáž textu: Kvantifikovaný výrok negujeme tak, že zaměníme kvantifikátor (obecný nahradíme existenčním nebo existenční nahradíme obecným) a negujeme výrokovou formu: [" x Î M; A(x)]´ ~ $ x Î M; A´(x) [$ x Î M; A(x)]´ ~ "x Î M; A´(x) Kontrolní úkoly: 1. Přečtěte a určete pravdivostní hodnotu výroků: a) "x Î N; x je sudé číslo. b) $x Î N; x je liché číslo. c) $x Î N; x + 2 = 1. 2. Negujte kvantifikované výroky z předešlé úlohy a určete pravdivostní hodnoty negovaných výroků. 3. Negujte kvantifikované výroky: a) Každý člověk je smrtelný. b) Všichni mi lhali. c) Všechna okna v této místnosti jsou otevřena. d) Existuje alespoň jeden trojúhelník, který je rovnostranný. e) Každý žák ve třídě 3.A umí násobilku. f) Všechny děti v mateřské škole umí jíst příborem. g) Existuje alespoň jedno dítě v mateřské škole, které je starší než 6 let. Shrnutí: Definičním oborem D výrokové formy A(x) o jedné proměnné x rozumíme množinu D, pro jejíž libovolný prvek d platí, že A(d) je výrok. Oborem pravdivosti P výrokové formy A(x) jedné proměnné x je podmnožina definičního oboru D, pro jejíž libovolný prvek a platí, že A(p) je pravdivý výrok. Z výrokové formy můžete tvořit výroky dvěma způsoby: a) dosazením za proměnnou z definičního oboru, vytvořený výrok se nazývá individuální výrok, b) kvantifikací užitím obecného nebo existenčního kvantifikátoru, vytvořený výrok se označuje jako kvantifikovaný výrok. Kvantifikované výroky můžeme negovat tak, že zaměníme kvantifikátor a negujeme výrokovou formu. Pojmy k zapamatování: * výroková forma (predikát), * definiční obor výrokové formy, obor pravdivosti výrokové formy, * kvantifikovaný výrok, obecný, existenční výrok, * negace kvantifikovaného výroku. Klíč - řešení kontrolních úkolů: Kap. 2.1 Výroková forma (predikát) 1. Výrokové formy jsou sdělení c, d, f. 2a) P[1 ]= {1,2,5,10} 2b) P[2 ]={12,24, 36, 48,…}[ ] 2c) P[3 ]= {1,2,3}. 3a) D = {množina všech měst v ČR}; P = {Praha}. 3b) D = {množina všech prvočísel}; P = {2,3,5,7}. 3c) D = N; P = {1, 2, 3, 4, 6, 9, 12, 18, 36}. 3d) D = N; P = {1, 2, 3, 4, 5}. 4a) P = {1} 4b) P = {1} 4c) P = {2, 3, 4, 5, 6} Kap. 2.2. Kvantifikované výroky 1a) například: Všechny vlaky ČD jezdí přesně podle jízdního řádu. Některé vlaky ČD jezdí přesně podle jízdního řádu. 2a) Všechny děti ve třídě nosí brýle. Obecný výrok je nepravdivý. 2b) Některá zvířata na farmě mají 4 nohy. Existenční výrok je pravdivý. 2c) Některé děti v MŠ mají babičku. Existenční výrok je pravdivý. 2d) Pro všechna přirozená čísla x platí x > 1. (Všechna přirozená čísla jsou větší než 1). Obecný výrok je nepravdivý (číslo 1 je přirozené číslo). Kap. 2. 3 Negace kvantifikovaného výroku 1a) Každé přirozené číslo je sudé (nepravdivý výrok). 1b) Existuje přirozené číslo, které je liché (pravdivý výrok). 1c) Existuje přirozené číslo, pro které platí: x + 2 = 1 (nepravdivý výrok). 2a) Existuje přirozené číslo, které není sudé (pravdivý výrok). 2b) Žádné přirozené číslo není liché (nepravdivý výrok). 2c) Pro žádné přirozené číslo neplatí, že x + 2 = 1 (pravdivý výrok). 3a) Existuje alespoň jeden člověk, který je nesmrtelný (nepravdivý výrok). 3b) Alespoň jeden mi nelhal. 3c) Alespoň jedno okno v této místnosti je zavřeno. 3d) Žádný trojúhelník není rovnostranný (nepravdivý výrok). 3e) Alespoň jeden žák ve třídě 3.A neumí násobilku. 3f) Alespoň jedno dítě v mateřské škole neumí jíst příborem (pravdivý výrok). 3g) Žádné dítě v mateřské škole není mladší než 6 let nebo má 6 let (nepravdivý výrok). Případ b), c), e) záleží na konkrétní situaci v místnosti. 3 Množiny Cíle Po prostudování kapitoly budete umět * vysvětlit základní pojmy z teorie množin, * určovat množiny (výčtem prvků a charakteristickou vlastností) a vyjadřovat vztahy mezi množinami, * znázorňovat množiny graficky, * vyjadřovat základní množinové operace, znázorňovat je graficky a formulovat jejich vlastnosti. Předpokládejte, že kapitolu prostudujete přibližně za 6 hodin. Průvodce studiem: Při vysvětlování základních pojmů z teorie množin budeme vycházet z vašich dosavadních znalostí, které jste někteří získali na předchozích stupních vzdělávání, ale také z vašich intuitivních zkušeností z reálného života. Množina a prvek množiny totiž patří v matematice mezi základní (primitivní) pojmy, které nedefinujeme, intuitivně vyplývají z našich zkušeností. Všichni přece víme, co se rozumí skupinou lidí, souborem hudebníků, sbírkou známek, stádem ovcí, atd. Uvedené soubory objektů zpravila v matematice označujeme pojmem množina. Pro zájemce: Teorie množin patří mezi základní a nejvýznamnější partie matematiky, přestože její zrod je poměrně nedávný. Za jejího tvůrce v podobě „intuitivní“ teorie množin je považován německý matematik Georg Cantor (1845 - 1915). Po prvotním odmítání a nepochopení se stala teorie množin „světem, do něhož se ponořila celá matematika“; měla zásadní význam pro další rozvoj matematiky. Ve druhé polovině 20. století se promítly její základy v podobě „množinové matematiky“ také do školního vzdělávání. 3.1 Množina, prvek množiny, množinové relace 3.1.1 Množina a prvek množiny Důležitá pasáž textu: Množinou označujeme takový soubor objektů, že o každém objektu můžeme rozhodnout, zda do uvažovaného souboru patří (je jeho prvkem) nebo nepatří (není jeho prvkem). Množiny budeme značit tiskacími písmeny velké abecedy A, B, C, ... a prvky (objekty) patřící do množiny písmeny malé abecedy a, b, c, .... Skutečnost, že objekt a je prvkem (elementem) množiny M budeme zapisovat aÎM a čteme „prvek a patří do množiny M“. Skutečnost, že prvek a nepatří do množiny M značíme aÏM a čteme „prvek a nepatří do množiny M“. Pro každou množinu M a pro každý objekt a nastane právě jedna z těchto dvou možností : aÎM, aÏM. Množinu určujeme dvojím způsobem : a) výčtem prvků - do složených závorek vypíšeme všechny prvky, ze kterých je množina tvořena. Např. A = {Praha, Brno, Ostrava, Plzeň, Liberec, Olomouc}, B = {1, 2, 3, 4}. Každý prvek v množině je zastoupen pouze jednou a zapisujeme ho právě jedním symbolem. b) charakteristickou vlastností - stanovíme kritérium příslušnosti pro všechny prvky množiny. Např. množina A je množina všech měst v ČR, které mají více než 100 000 obyvatel, B je množina všech přirozených čísel menších než 5. Symbolicky můžeme množinu B zapsat B = {x Î N; x < 5}, čteme: množina B je množina všech x patřících do N, pro něž platí x < 5. Pro další úvahy jsou důležité dvě významné množiny: a) základní množina - určitá předem zvolená množina, která obsahuje prvky všech množin, o nichž budeme jednat, které budeme z této množiny vybírat (množina Z). V našem příkladu je Z[1] množinou všech měst v ČR, [ ]Z[2 ] množinou všech přirozených čísel N, b) prázdná množina - která neobsahuje žádný prvek, značíme f nebo{}. Množina obsahující aspoň jeden prvek se nazývá neprázdná. Prázdnou množinou je například množina všech přirozených čísel větších než 1 a menších než 2. Pozor: zápis {f} nevyjadřuje prázdnou množinu, ale jednoprvkovou množinu s prvkem, kterým je prázdná množina. Poznámka: Množiny mohou být tvořeny libovolnými objekty, tedy i množinami. Je možné zavést množinu M, jejímiž prvky jsou množiny A, B, C, ..., K, tedy M = {A, B, C,..., K}. Pro množinu M se neužívá názvu množina množin, ale systém množin. Kontrolní úkoly: 1. Zapište výčtem množinu všech samohlásek ve svém jméně. 2. Načrtněte a popište čtyřúhelník, zapište výčtem množinu vrcholů čtyřúhelníka. 3. Množinu A = {2, 4, 6, 8} zapište charakteristickou vlastností. 4. Přečtěte symbolické zápisy a určete množiny výčtem prvků: a) A = {x Î N[0]; x < 6}, b) B = {x Î N; x = 6}, c) C = {x Î N[0]; 2 < x < 6}, d) D = {x Î N[0]; x + 8 < 3x - 6}, e) E = {x Î N; x^2 = x}. f) 5. Zapište symbolicky: a) množina všech jednociferných přirozených čísel, b) množina všech celých nezáporných čísel. 6. Uveďte příklady několika prázdných (neprázdných) množin. 3.1.2 Množinové relace (vztahy mezi množinami) V této kapitole se seznámíme se dvěma množinovými relacemi: množinovou inkluzí a rovností množin. Řešený příklad 1: Množina A je množina všech studentů PedF MU studujících obor učitelství pro mateřské školy. Množina B je množina všech studentů PedF MU. Jaký je vztah mezi množinami A, B? Řešení: Každý student množiny A patří do množiny B, ale každý student z B nemusí patřit do množiny A. Množina A je podmnožinou množiny B. Důležitá pasáž textu: Právě když každý prvek, který je prvkem množiny A, je také prvkem množiny B, říkáme, že množina A je podmnožinou množiny B, nebo množina B je nadmnožinou množiny A a zapisujeme A Ì B nebo B É A. Tento vztah se nazývá inkluze množin. Ke znázornění vztahů mezi množinami jednoduchým a srozumitelným způsobem výhodně využíváme množinových diagramů, které mohou mít různý tvar podle počtu znázorňovaných množin. Označujeme je Vennovy diagramy (podle anglického matematika Johna Venna). Řešený příklad 2: Jsou dány základní množina Z, Z = {1, 2, ..., 10} a dále množiny A = {x Î Z; x½3} (zápis x½3 čteme číslo x je dělitelem čísla 3), B = {xÎ Z; x½6}. Určete vztah mezi množinami A, B, Z. Zakreslete Vennův diagram. Řešení: Množiny A i B určíme výčtem: A = {1, 3}, B = {1, 2, 3, 6}a zakreslíme Vennův diagram. Příslušnost prvku do množiny vyznačíme křížkem do vnitřní oblasti čáry znázorňující množinu, tzv. pole diagramu (značku neumísťujeme na žádnou nakreslenou čáru). Vyznačili jsme Vennův diagram pro 2 množiny, vytvořili jsme 4 pole diagramu. Znázornění množin je patrné z následujícího grafického řešení. Pro vztahy mezi množinami A, B, Z platí: A Ì B, B É A - každý prvek množiny A patří do množiny B A Ì Z, B Ì Z - množiny A i B jsou podmnožinami základní množiny. Poznámka: Pro libovolnou množinu M platí inkluze: f Ì M, M Ì M a také f Ì f. Prázdná množina je podmnožinou každé množiny a každá množina je sama sobě podmnožinou. Důležitá pasáž textu: Množiny A, B se rovnají (zapíšeme A = B), právě když každý prvek množiny A je prvkem množiny B a současně každý prvek množiny B je prvkem množiny A (A Ì B Ù B Ì A). Množiny A, B obsahují tytéž prvky. Jestliže si množiny A, B nejsou rovny, píšeme A ¹ B (říkáme o nich, že jsou různé) a znamená to, že existuje aspoň jeden prvek množiny A, který nepatří do množiny B, nebo aspoň jeden prvek množiny B, který nepatří do A. Jestliže pro množiny A, B platí: A Ì B Ù A ¹ B, říkáme, že množina A je vlastní podmnožinou množiny B. Znázorníme takto: Symbolem prázdné množiny (značíme f) jsme vyznačili, že v daném elementárním poli není žádný prvek, tedy neexistuje prvek z množiny A, který by nepatřil množině B. Vennovým diagramem je znázorněno, že A = B. Značka f (symbol prázdné množiny) zapsaná ve dvou polích Vennova diagramu vyjadřuje, že v těchto polích nejsou žádné prvky a že všechny prvky množiny A patří současně do množiny B a všechny prvky množiny B patří současně do množiny A. Kontrolní úkoly: 1. Určete, jaký je vztah mezi množinami: a) A: množina všech obyvatel Brna, B: množina všech obyvatel ČR b) A: množina všech děvčat ve třídě 1. C, B: množina všech dětí ve třídě 1.C c) A: množina všech jednociferných přirozených čísel, B: množina všech přirozených čísel, která jsou menší než 10. 2. Je dána množina A = {a, b, c, d, e }. Určete alespoň 3 vlastní podmnožiny množiny A. 3. Nechť Z = {1, 2, 3,…,10} je základní množina. Znázorněte Vennovým diagramem tyto podmnožiny množiny Z: A = {3, 6, 9}, B = {x Î Z, x je prvočíslo}, C = {x Î Z, 2 < x < 10}. 4. Zapište všechny podmnožiny množiny A={3, 6,.9}. 3.2 Množinové operace Průvodce studiem: Termín „operace“ jistě znáte z hovorového jazyka v několika různých významech jako výkon, úkon, činnost, postup (lékařská operace, výrobní operace, vojenská operace aj.). V matematice a výuce matematiky se používá termín matematická (početní) operace k vyjádření například početních výkonů sčítání, odčítání, násobení, dělení s přirozenými čísly, se zlomky, reálnými čísly apod. V této kapitole definujeme a na příkladech vysvětlíme, co rozumíme množinovými operacemi doplněk množiny, sjednocení, průnik, rozdíl a symetrický rozdíl množin. 3.2.1 Přehled množinových operací Důležitá pasáž textu: Doplněk množiny (značíme A´) je množina, která obsahuje právě ty prvky základní množiny Z, jež nepatří do množiny A. Symbolicky zapíšeme: A´ = {x Î Z, x Ï A}. Sjednocení dvou množin A, B ( A Ì Z, B Ì Z) je množina S obsahující ty prvky ze základní množiny Z, které patří do alespoň jedné z množin A, B. Zapisujeme S = A È B. Průnik dvou množin A, B (AÌ Z, BÌZ) je množina P, která obsahuje právě ty prvky základní množiny Z, které patří do množiny A a současně do množiny B. Zapisujeme P = A Ç B. Množiny A, B, jejichž průnik je množina prázdná, se nazývají disjunktní. Rozdíl dvou množin A, B (značíme A - B) je množina, která obsahuje všechny prvky množiny A, které nepatří do množiny B. Symetrický rozdíl dvou množin A, B (značíme A D B) je množina, která obsahuje právě ty prvky základní množiny Z, jež patří právě do jedné z množin A, B. Řešený příklad: Je dána základní množina Z = {1,2,3,4,5,6,7,8,9,10} a množiny A = {2,4,6,8,10}, B = {3,6,9}. A) Určete doplněk A´ a znázorněte graficky. Řešení: A´ = {1, 3, 5, 7, 9}. B) Určete sjednocení množin A, B. Řešení: S = A È B = {2, 3, 4, 6, 8, 9, 10}. Pozor: Číslo 6, které je prvkem obou množin A i B, zapisujeme a v grafu vyznačujeme pouze jednou! C) Určete průnik množin A, B. Řešení: Využijeme znázornění situace v předešlém příkladu, P = A Ç B = {6}. Na obrázku je vyšrafováno pole, které představuje průnik množin A, B: D) Určete rozdíl množin A, B. Řešení: Použijeme opět Vennova diagramu, A - B = {2,4,8,10}. Schematické znázornění rozdílu množin A, B: E) Určete symetrický rozdíl množin A, B. Řešení: Použijeme opět Vennova diagramu, A D B = {2,3,4,8,9,10} Schematické znázornění symetrického rozdílu množin A, B: 3.2.2 Vlastnosti operací s množinami Průvodce studiem: Ve výuce matematiky na základní a střední škole jste poznali některé operace (početní výkony) s přirozenými čísly, se zlomky, s desetinnými čísly aj., a jejich vlastnosti. Podobně i pro množinové operace platí řada důležitých vlastností, které jsou vyjádřeny ve tvaru množinových rovností. Platnost množinových rovností ověřujeme pomocí Vennových diagramů. Některé vlastnosti operací s množinami uvedeme v přehledu. Platnost některých z nich ověříme v kontrolních úlohách. 1. A Ì A È B, B Ì A È B. 2. Jestliže A Ì B, pak platí A È B = B. 3. A È Z = Z, A È A = A, f È A = A. 4. Komutativnost: a) sjednocení A È B = B È A, b) průniku A Ç B = B ÇA. 5. Asociativnost: a) sjednocení (A È B) È C = A È (B È C), b) průniku (A Ç B) Ç C = A Ç (B Ç C). 6. Distributivnost: a) sjednocení vzhledem k průniku (A Ç B) È C = (A È C) Ç (B È C), b) průniku vzhledem ke sjednocení (A È B) Ç C = (A Ç C) È (B Ç C). 7. A È A´ = Z A Ç A´= f f´ = Z Z´= f f È f = f Z Ç Z = Z f È Z = Z È Z = Z Z Ç f = f Ç f = f 8. De Morganovy zákony: (A È B)´ = A´ Ç B´ (A Ç B)´ = A´ È B´ 9. Jestliže A ¹ B, potom A - B ¹ B - A 10. Jestliže A Ì B, potom A - B = f. Řešený příklad: Ověřte, že platí množinová rovnost: (A È B)´ = A´ Ç B´… (De Morganův zákon). Řešení: Množinovou rovnost ověříme pomocí Vennova diagramu. Znázorníme množinu na levé straně rovnosti, poté množinu na pravé straně rovnosti a výsledky porovnáme. Levá strana (A È B)´ A È B (A È B)´ Z obrázku vpravo je zřejmé, že levá strana rovnosti je znázorněna barevně na pravém obrázku. Pravá strana A´ Ç B´ A´ B´ A´ Ç B´ Z obrázku je zřejmé, že řešením je dvojitě vyšrafované pole. Na obou obrázcích jsou vyznačena stejná pole, z čehož vyplývá, že množinová rovnost (A È B)´ = A´ Ç B´ platí. Kontrolní úkoly: 1. Je dána základní množina Z = N, A = {x Î N, x £ 10}, B = {1, 3, 5, 7, 9, 11, 13}. Určete A´, B´, A È B, B Ç A, B – A, A D B. 2. Je dána množina Z = {x Î N, x £ 20} a množiny A = {x Î Z, xú 10}, B = {x Î Z, x £ 10}, C = {x Î Z, 4ú x}. Určete výčtem množiny A, B, C, A´, B´, C´ a znázorněte graficky. 3. Nakreslete Vennův diagram pro 3 množiny, vyšrafujte elementární pole taková, v nichž jsou pouze prvky, které a) patří do alespoň jedné z množin, b) patří do právě jedné z množin, c) patří do všech množin současně, d) nepatří do žádné z nich. 4. Pomocí Vennových diagramů rozhodněte, zda platí množinové rovnosti: a) (A È B) - C = (A - C) È (B - C) b) A - (B Ç C) = (A - B) È (A - C) 3.2.3 Slovní úlohy, řešené pomocí množinových operací Pro zájemce: V kapitole 1.5 jsme ukázali, jak lze využít poznatků logiky při řešení slovních úloh. Podobně můžeme uplatnit k řešení slovních úloh také znalosti o množinových operacích, jejich vlastnostech a znázorňování pomocí Vennových diagramů. Řešený příklad: Ze 129 studentů učitelství pro mateřské školy chodí pravidelně do menzy na oběd nebo na večeři 116 studentů, 62 studentů nechodí na oběd nebo nechodí na večeři. Přitom na obědy jich chodí o 47 více než na večeři. Kolik studentů chodí pouze na oběd? Řešení: Vyznačíme do Vennova diagramu množiny: množina O je množina všech studentů, kteří chodí do menzy na oběd, množina V je množina všech studentů, kteří chodí do menzy na večeři. Z podmínek úlohy je zřejmé, že všech studentů bylo 129, platí: a + b + c + d = 129 (1), přitom: a…počet žáků, kteří chodí na oběd, ale nechodí na večeři, b…počet žáků, kteří chodí na oběd i na večeři, c…počet žáků, kteří chodí na večeři, ale nechodí na oběd, d…počet žáků, kteří nechodí na oběd ani na večeři. Platí rovnice: a + b + c = 116 (2), a + c + d = 62 (3) , a + b = b + c + 47 (4). Řešením soustavy čtyř lineárních rovnic o čtyřech neznámých a, b, c, d dostaneme a = 48. Shrnutí: Množinou označujeme takový soubor objektů, že o každém objektu můžeme rozhodnout, zda do uvažovaného souboru patří (je jeho prvkem) nebo nepatří (není jeho prvkem). Množinu určujeme dvojím způsobem: výčtem prvků nebo charakteristickou vlastností. Množinové relace jsou rovnost množin (A se rovná B) a inkluze množin (A je podmnožinou B, B je nadmnožinou A). Ke znázornění vztahů mezi množinami využíváme množinových (Vennových) diagramů. Mezi množinové operace patří doplněk množiny, sjednocení a průnik množin, rozdíl a symetrický rozdíl množin. Jejich vlastnosti (komutativnost, asociativnost, distributivnost, de Morganovy zákony a jiné) ověřujeme také Vennovými diagramy. Pojmy k zapamatování: * množina, prvek množiny, základní množina, prázdná množina * rovnost a inkluze množin (podmnožina, nadmnožina), * Vennův diagram, * doplněk množiny, * sjednocení, průnik množin, * rozdíl, symetrický rozdíl množin, * komutativnost průniku, sjednocení, * asociativnost průniku, sjednocení, * distributivnost sjednocení vzhledem k průniku, průniku vzhledem ke sjednocení, * De Morganovy zákony. Klíč - řešení kontrolních úkolů: Kap. 3.1.1 Množina a prvek množiny 3. A = {x Î N; x < 10}, N je množina všech sudých čísel. 4a) A = {0,1,2,3,4,5} 4b) B = {6} 4c) C = {3,4,5} 4d) D = {7} 4e) E = {1} 5a) A = {x Î R; x > 0}, R je množina všech reálných čísel 5b) B = {x Î N; x < 10} 5c) C = {x Î Z; x ³ 0}, Z je množina všech celých čísel Kap. 3.1.2 Množinové relace (vztahy mezi množinami) 1a) A Ì B 1b) A = B 1c) A É B 1d) A = B 2. Například: B = {a}, C = {a,b}, D ={b,c,d}. 4. {}, {3}, {6}, {9}, {3,6}, {3,9}, {6,9}, {3,6,9}. Kap. 3.2 Množinové operace 1a) A´ = {x Î N, x >10}´ 1b) A È B = {1,2,3,4, 5,6,7,8,9,10,11 13} 1c) B Ç A = {1,3,5,7,9} 1d) B – A = {11, 13} 1e) A D B = {2,4,6,8,10,11,13} 2a) A = {1,2,5,10} 2b) B = {1,2,3,4,5,6,7,8,9,10} 2c) C = {4,8.12,16,20} 2d) A´= {3,4,6,7,8,9} 2e) B´ = {11,12,13,14,15,16,17,18,19,20} 2f) C´ = {1,2,3,5,6,7,9,10,11,13,14,15,17,18,19} 4 Kartézský součin Prostudování kapitoly Vám zabere cca 3 hodiny. Průvodce studiem: V předchozí kapitole jsme se zabývali operacemi s množinami. Zavedli jsme průnik množin, sjednocení množin, rozdíl množin a symetrický rozdíl množin. Nyní budeme studovat takové množiny, jejichž prvky jsou uspořádané dvojice. To nám umožní definovat další operaci s množinami - kartézský součin dvou množin. Cíle Po prostudování kapitoly budete umět * vysvětlit a používat uspořádané dvojice prvků, * definovat a určit kartézský součin dvou množin, * znázorňovat kartézský součin různými typy grafů * zjistit vlastnosti kartézského součinu. Uspořádanou dvojici vytvoříme z prvků x, y, tak, že prvek x je první složka a prvek y je druhá složka uspořádané dvojice. Budeme značit [x, y]. Uspořádané dvojice [x,y] a [u,v] jsou si rovny, právě když x = u a y = v (symbolicky zapíšeme [x,y] = [u,v] Û x = u Ù y = v). Je třeba si uvědomit, že ze dvou různých prvků x, y lze utvořit dvě uspořádané dvojice [x, y] a [y, x], které jsou různé. Poznámka: Je třeba rozlišovat zápisy {x,y} a [x,y]: {x, y} je dvouprvková množina vytvořená z prvků x, y, [x, y] je uspořádaná dvojice, kde první složkou je x a druhou složkou y. Řešený příklad 1: Adélka má tři halenky - bílou, zelenou, růžovou a dvě sukně - hnědou a modrou. Kolika a kterými způsoby se Adélka může obléci ? Řešení: Množinu všech halenek označíme A = {b, z, r}. Množinu všech sukní označíme B = {h, m}. Adélka může volit jednotlivé možnosti svého oblečení podle tabulky: halenky b z r b z r sukně h h h m m m Adélka si vybírá na oblečení určitý prvek z množiny všech uspořádaných dvojic [x, y], kde x je nějaká halenka a y je nějaká sukně, má 6 různých možností oblečení. Důležitá pasáž textu: Kartézský součin množin A, B je množina všech uspořádaných dvojic [a, b], kde aÎA, bÎB. Symbolicky: A x B = {[x, y]; xÎA Ù yÎB} Má-li množina A a prvků, množina B b prvků, pak kartézský součin A´B má a.b uspořádaných dvojic. Kartézský součin je tedy další operací s množinami. Platí: Je-li aspoň jedna množina A, B prázdná, je také jejich kartézský součin A´B prázdná množina, neboť není z čeho tvořit uspořádané dvojice. Platí i věta obrácená: Když není žádná z množin A, B prázdná, obsahuje kartézský součin A´B aspoň 1 uspořádanou dvojici. Může také nastat případ, že A = B a pak hovoříme o kartézské druhé mocnině A ´ A = A^2. Řešený příklad 2: Jsou dány množiny A = {1, 2, 3}, B = {a, b}. Vytvořte kartézské součiny A ´ B, B´ A. Rozhodněte, zda platí: A ´ B= B´ A. Řešení: Podle definice kartézského součinu budeme sestavovat všechny uspořádané dvojice, v nichž první složkou budou prvky množiny A, druhou složkou prvky množiny B. A ´ B = {[1,a], [1,b], [2,a], [2,b], [3,a], [3,b]} Obdobně pro druhý případ, kde první složku vybíráme z množiny B, druhou složku z množiny A. B ´ A = {[a,1], [a,2], [a,3], [b,1], [b,2], [b,3]} Všimněte si, že A´B ¹ B´A. Oba kartézské součiny obsahují sice stejný počet prvků (uspořádaných dvojic), ale uspořádané dvojice se nerovnají: např. do A ´ B patří [a,1], ale do B ´ A patří [1,a] a platí, že [a, 1] ¹ [1, a]. Řešená úloha ukazuje, že množinová operace kartézský součin není komutativní, tzn. A ´ B ¹ B ´ A pro A¹ B. Můžeme vytvořit také kartézský součin z prvků jedné množiny (například množiny A): A ´ A = { [1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3]}. Pro zájemce: Možná Vás zaujal název „kartézský“ součin a nevíte, odkud se vzal. Je odvozen od jména francouzského matematika a filozofa René Descarta, latinsky Cartesius, který v 1. polovině 17. století významně zasáhl do rozvoje řady vědních oborů - je považován za jednoho ze zakladatelů analytické geometrie. Kartézský součin výhodně znázorníme graficky několika typy grafů. Naučíme se sestrojovat a číst graf kartézský (bodový), šachovnicový a uzlový. Zvolíme množiny A, B z naší řešené úlohy: A = {1, 2, 3}, B = {a, b} a kartézský součin A ´ B = {[1,a], [1,b], [2,a], [2,b], [3,a], [3,b]}. a) kartézský graf kartézského součinu A ´ B: V rovině zvolíme dvě na sebe kolmé přímky (vodorovnou přímku označíme x, svislou y). Z dřívějšího studia víme, že těmto přímkám říkáme osy x, y v pravoúhlé (kartézské) soustavě souřadnic Na vodorovné přímce (ose x) vyznačíme obrazy prvků množiny A (první složky uspořádaných dvojic [x, y]) jako body, na svislé přímce (ose y) znázorníme obrazy prvků množiny B (druhé složky uspořádaných dvojic [x, y]) jako body. Obrazem každé uspořádané dvojice [x, y] Î A´B je průsečík kolmic k vodorovné a svislé ose, které jsou vedené v obrazu první a druhé složky uspořádané dvojice. Na obrázku je znázorněna uspořádaná dvojice [3, b]: Obrazem každého prvku množiny A je bod na ose x, prvku množiny B je bod na ose y. Obrazem každé uspořádané dvojice [x,y] je průsečík kolmic vedených v obrazu první složky a druhé složky uspořádané dvojice [x, y]. b) šachovnicový graf kartézského součinu A ´ B: V rovině opět zvolíme dvě na sebe kolmé osy (vodorovnou označíme x, svislou y). Na vodorovné ose x znázorníme prvky množiny A jako úsečky (první složky uspořádaných dvojic [x, y]), na svislé ose y znázorníme prvky množiny B jako úsečky (druhé složky uspořádaných dvojic [x, y]). Obrazem každé uspořádané dvojice [x, y] Î A´B je pole, které připomíná čtverec šachovnice. Na obrázku je opět znázorněna pouze uspořádaná dvojice [3, b]: Obrazem každého prvku množiny A je úsečka na ose x, prvku množiny B je úsečka na ose y. Obrazem každé uspořádané dvojice [x,y] je pole. c) uzlový graf kartézského součinu A ´ A: A ´ A = { [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]} Obrazem každého prvku množiny A je bod nebo kroužek v rovině, tzv. uzel grafu. Každou uspořádanou dvojici [x,y]ÎA´A znázorníme čarou se šipkou směřující od uzlu x k uzlu y, které obvykle říkáme orientovaná hrana. V kartézském součinu A´A se vyskytují uspořádané dvojice typu [x, x], pak je zakreslujeme obloučkem, který vychází a vstupuje do téhož uzlu, tzv. smyčkou. Je-li prvkem kartézského součinu uspořádaná dvojice [x, y] a současně [y, x], pak obě zakreslíme oboustranně orientovanou hranou. Obrazem každého prvku množiny A v uzlovém grafu je bod v rovině - uzel. Obrazem každé uspořádané dvojice v uzlovém grafu je šipka (orientovaná hrana) nebo smyčka. Poznámka: Uzlový graf kartézského součinu používáme zejména tehdy, nejsou-li množiny příliš početné. Jestliže A ¹ B, musíme pro zakreslení kartézského součinu nejprve vytvořit sjednocení množin S = A È B. Každý prvek sjednocení S znázorníme uzlem a dále pokračujeme popsaným způsobem. Pokud bychom tedy znázorňovali kartézský součin A ´ B uzlovým grafem, je třeba zakreslit jako uzly všechny prvky množiny A a všechny prvky množiny B. Šipkami se znázorní příslušné uspořádané dvojice. Kontrolní úkoly: 1. Určete chybějící složku v uspořádaných dvojicích [x, 2], [5,y] tak, aby uspořádané dvojice se: a) rovnaly uspořádané dvojici [5, 2], b) nerovnaly uspořádané dvojici [5, 2] 2. Určete výčtem kartézské součiny A ´ B, je-li: A = {4, 5, 6}, B = {a, b, c, d}, A = B = {4, 5, 6}, A = {4, 5, 6}, B = {} 3. Zapište množiny, z nichž jsou tvořeny kartézské součiny: a) A ´ B = {[2, 1], [2, 2], [2, 3], [2, 4]}, b) A ´ B = {[a, 1], [b, 1], [c, 1], [d, 1]}, c) A ´ B = {[2, 2], [3, 3], [2, 4], [2, 3], [3, 2], [3, 4]}, d) A ´ B = {[2, 1], [2, 2], [1, 1], [1, 2]} 4. Určete počet prvků v kartézském součinu A´B , má-li: množina A dva prvky, množina B sedm prvků, množina A tři prvky, množina B tři prvky, množina A jeden prvek, množina B jeden prvek, množina A dva prvky, množina B nemá žádný prvek 5. Určete počty prvků množin A, B, má-li kartézský součin: a) 12 prvků, b) 7 prvků 6. Znázorněte některé kartézské součiny z úlohy 3 na kartézském (uzlovém, šachovnicovém) grafu. Shrnutí: Z prvků množin lze vytvářet uspořádané dvojice - obsahují první a druhou složku. Množina všech uspořádaných dvojic [a, b], kde aÎA, bÎB, se nazývá kartézský součin množin A, B. Kartézský součin je množinová operace, která není komutativní. Kartézský součin dvou množin lze graficky znázornit kartézským (bodovým), šachovnicovým nebo uzlovým grafem. Pojmy k zapamatování: · uspořádaná dvojice prvků · kartézský součin dvou množin · grafy kartézského součinu (kartézský bodový, šachovnicový, uzlový) · vlastnosti kartézského součinu Klíč - řešení kontrolních úloh: Kap. 4 - Kartézský součin 1a) x=5, y=2 1b) x≠5, y≠2 2a) A ´ B = {[4,a], [4,b], [4,c], [4,d], {[5,a], [5,b], [5,c], [5,d], {[6,a], [6,b], [6,c], [6,d]} 2b) A ´ B = A^2 =^ {[4,4], [4,5], [4,6], [5,4], {[5,5], [5,6], [6,4], [6,5], [6,6]} 2c) A ´ B = f 3a) A = {2}, B = {1,2, 3,4} 3b) A = {a,b,c,d}, B ={1} 3c) A = {2,3}, B = {2,3,4} 3d) A = {1,2}, B = {1,2} 4) 14, 9, 1, 0. 5a) množina A může mít 1, 2, 3, 4, 6 nebo 12 prvků, množina B může mít 12, 6, 4, 3, 2 nebo 1 5b) množina A má 7 prvků, B má 1 prvek nebo A má 1 prvek, B má7 prvků. 5 Binární relace Prostudování kapitoly Vám zabere cca 6 hodin. Průvodce studiem: Slovo „relace“ jistě znáte z reálného života, vyjadřuje vztah. Známe například „cenové relace“ nebo v běžném životě je třeba Monika (matka) ve vztahu s Jitkou (dcera). V následující kapitole si ukážeme, že pojem (binární) relace je jedním z nejdůležitějších vztahů v matematice. Dozvíte se rovněž, proč jsme se zabývali kartézským součinem dvou množin. Množinám, které jsou částmi/podmnožinami kartézského součinu, se totiž říká relace. V případě kartézského součinu dvou množin vyjadřují jeho části dvojčlenné vztahy mezi prvky x Î A a prvky y Î B a proto hovoříme o dvojčlenných nebo-li binárních relacích. Cíle Po prostudování kapitoly budete umět * definovat pojem binární relace, určit ji výčtem i charakteristickou vlastností, * znázornit binární relaci kartézským a uzlovým grafem, * určit k dané relaci doplňkovou a inverzní, * určit obory relací, * definovat vlastnosti relací, zapsat je symbolicky a určit, jak se projevují vlastnosti relací v kartézském nebo uzlovém grafu. 5.1 Pojem binární relace Řešený příklad 1: Jsou dány množiny M = {1, 2, 4}, N = {3, 5} . Vytvořte kartézský součin M ´ N a zapište výčtem prvků množinu R[1] všech uspořádaných dvojic [x, y] z kartézského součinu M ´ N, kde x < y. Řešení: Kartézský součin obsahuje 6 uspořádaných dvojic: M ´ N = {[1,3], [1,5], [2,3], [2,5], [4,3], [4,5]}. Množina R[1] je určena charakteristickou vlastností a symbolicky zapsaná takto: R[1] = {[x, y] Î M ´ N, x < y}. Výčtem prvků určíme množinu R[1] tak, že vybereme z kartézského součinu M ´ N všechny uspořádané dvojice, v nichž je první složka menší než druhá složka: R[1] = {[1,3], [1,5], [2,3], [2,5], [4,5]} Platí: R[1] Ì M ´ N, množina R[1] obsahuje 5 uspořádaných dvojic. Důležitá pasáž textu: Každá podmnožina kartézského součinu A ´ B se nazývá binární relace z množiny A do množiny B. V případě, že platí A=B, pak hovoříme o binární relaci v množině A. Binární relace, jako každá jiná množina, může být určena: a) výčtem všech uspořádaných dvojic, b) charakteristickou vlastností všech uspořádaných dvojic. Řešený příklad 2: Je dána množina M = {1, 2, 3}. Vytvořte kartézský součin M ´ M a zapište výčtem prvků množinu R[2]všech uspořádaných dvojic [x, y] z kartézského součinu M ´ M, kde x < y. Řešení: Kartézský součin obsahuje 9 uspořádaných dvojic: M ´ M = {[1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3], }. Množina R[2] je určena charakteristickou vlastností a symbolicky zapsaná takto: R[2] = {[x, y] Î M ´ M, x < y}. Výčtem prvků určíme množinu R[2] tak, že vybereme z kartézského součinu M ´ M všechny uspořádané dvojice, v nichž je první složka menší než druhá složka: R[2] = {[1,2], [1,3], [2,3]}. Platí: R[2] Ì M ´ M, množina R[2] obsahuje 3 uspořádané dvojice. Skutečnost, že uspořádané dvojice [x, y] patří do relace R , zapisujeme [x, y] Î R (čteme uspořádaná dvojice prvků x, y patří do relace R) nebo x R y (čteme prvek x je v relaci s prvkem y). Relace označujeme zpravidla velkými písmeny např. R, S, T (množiny, ve kterých jsou prvky relace uspořádané dvojice na rozdíl od množin A, B, C,…). Příklady relací ze školské matematiky určené charakteristickou vlastností: - "být rovnoběžný" v množině přímek dané roviny, - "být menší" v množině všech přirozených čísel, - "žák x chodí do stejné třídy jako žák y", v množině všech žáků určité školy, ... Binární relace znázorňujeme nejčastěji kartézským nebo uzlovým grafem podle stejných pravidel jako při znázorňování kartézského součinu (podmínkou je, aby množina M nebyla příliš početná a znázornění se nestalo nepřehledným). Binární relace, která obsahuje všechny uspořádané dvojice kartézského součinu M ´ M, které nepatří do relace R, se nazývá doplňková relace R´ k relaci R. Platí R È R´= M ´ M a současně R Ç R´= Æ. V řešeném příkladu 2 jsme na množině M = {1, 2, 3} vytvořili kartézský součin M ´ M = {[1,1], [1,2], [1, 3], [2, 1], [2, 2], [2, 3], [3,1], [3,2], [3,3]} a binární relaci R[2] = {[x, y] Î M ´ M, x < y}, výčtem prvků R[2] = {[1, 2], [1, 3], [2, 3]}. Relace doplňková k relaci R[2] bude obsahovat 6 uspořádaných dvojic, v nichž není x < y: R[2]´ = {[1, 1], [2, 1], [2, 2], [3, 1], [3, 2], [3, 3]}, tj. R[2]´ = {[x, y] Î M ´ M, x ³ y}. Inverzní relaci R^-1 k relaci R dostaneme tak, že zaměníme pořadí složek ve všech uspořádaných dvojicích tvořících relaci R. K binární relaci R[2] z řešeného příkladu 2 vytvoříme R[2]^-1 = {[2,1], [3,1], [3,2]}. Inverzní relace k R obsahuje stejný počet uspořádaných dvojic jako R. Obory binárních relací Množina L(R) všech prvků x Î M, které jsou prvními složkami uspořádaných dvojic [x, y] Î R, se nazývá levý (první) obor relace. Množina P(R) všech prvků y Î M, které jsou druhými složkami uspořádaných dvojic [x, y] Î R, se nazývá pravý (druhý) obor relace R. Přitom je L(R) Ì M, P(R) Ì M. Může se stát, že L(R) = P(R) = M, ale tato rovnost platit nemusí. Řešený příklad 3: Mějme kartézský součin M ´ M a relaci R = {[2,1], [3,1], [3,2]} jako v předchozí řešené úloze 2. Určete levý (první) a pravý (druhý) obor relace R. Řešení: Levým definičním oborem relace R je množina L(R) = {1, 2}, pravým oborem relace R je množina P(R) = {2, 3}. Znázornění binárních relací Binární relace znázorňujeme nejčastěji kartézským nebo uzlovým grafem podle pravidel, která jste se naučili při znázorňování kartézského součinu. Kontrolní úkoly: 1. Přečtěte (nahlas!) symbolické zápisy R[1] = {[x, y] Î N ´ N, x < y}, N je množina všech přirozených čísel R[2 ]= {[x, y] Î M ´ M, y je násobkem x}, M = {1, 2, 3, 4, 5, 6} R[3 ]= {[x, y] Î M ´ M, y = 2x}, M = {1, 2, 3, 4} R[4] = {[x, y] Î M ´ M, x je shodná s y}, M je množina všech úseček v rovině. 2. Určete výčtem množiny uspořádaných dvojic relace R[2 ]a R[3]. Určete levý a pravý obor relací R[2 ]a R[3. ]Zdůvodněte, proč nelze určit výčtem množiny uspořádaných dvojic relací R[1 ]a R[4]. 3. Znázorněte relace R[2 ]a R[3 ]na kartézském a uzlovém grafu. 5.2 Vlastnosti binárních relací Řešený příklad: Je dána množina M = {1, 2, 3, 4} a v ní jsou výčtem uspořádaných dvojic definované binární relace jako podmnožiny kartézského součinu M ´ M: R[1] = {[1, 1], [1, 2], [2, 2], [3, 3], [4, 4]} R[2] = {[4, 4], [1, 2], [2, 1]} R[3] = {[1, 2], [2, 2], [1, 1], [2, 1]} R[4] = {[1, 2], [3, 4], [4, 1]} R[5] = {[3, 4], [4, 2], [2, 2]} R[6] = {[1, 2], [2, 3], [3, 4], [1, 4], [3, 1], [4, 2], [2, 1], [3, 3]}. Určete vlastnosti jednotlivých relací. Průvodce studiem: Uvedených relací využijeme k demonstraci jednotlivých vlastností binárních relací. Naučíme se názvy relací, jejich symbolické zápisy. Je třeba, abyste si zopakovali vše, co jste si osvojili v předcházejících kapitolách. Vlastnosti relací je třeba důkladně pochopit, protože je budete využívat v dalších kapitolách k popisu některých speciálních druhů binárních relací. Důležitá pasáž textu: a) Relace R v množině M je reflexivní právě tehdy, když pro " x Î M; [x, x] Î R (můžeme také zapsat jiným způsobem " x Î M; x R x). V řešené úloze zjistíme, že tuto vlastnost má relace R[1]. Podle definice reflexivnosti relace musí obsahovat všechny uspořádané dvojice typu [x,x], kde xÎM. Kromě těchto uspořádaných dvojic může ovšem relace obsahovat i další - v našem příkladu uspořádanou dvojici [1,2]. V uzlovém grafu se reflexivnost projeví tak, že kolem každého uzlu je smyčka. b) Relace R v množině M je symetrická právě tehdy, když pro "x, y Î M; [x, y] Î R => [y, x] Î R (můžeme také zapsat jiným způsobem " x, y Î M; x R y Þ y R x). V řešené úloze jsou symetrické relace R[2], R[3]. V obou relacích je k uspořádané dvojici [1,2] přítomna také dvojice [2,1] - nebo obráceně: k uspořádané dvojici [2,1] je v relaci přítomna i dvojice [1,2]. Relace R[1] není symetrická, protože ke dvojici [1,2] chybí [2,1]. Vlastnost symetričnosti relace snadno poznáme z uzlového grafu. V něm jsou všechny šipky oboustranné (tzv. dvojité orientované hrany). Vyskytne-li se v grafu jen jediná jednoduchá orientovaná hrana, relace není symetrická. Kolem uzlů mohou být smyčky, na symetričnost relace nemají žádný vliv. c) Relace R v množině M je tranzitivní právě tehdy, když pro "x, y, z Î M; ([x, y] Î R Ù [y, z] Î R) => [x, z] Î R (můžeme také zapsat jiným způsobem " x, y, z Î M; x R y Ù y R z Þ x R z). Příkladem tranzitivní relace je relace R[3 ] v řešené úloze. Ke zjištění, zda je relace tranzitivní, je třeba prošetřit všechny uspořádané dvojice určené výčtem nebo znázorněné uzlovým grafem. Snáze rozhodneme o tom, že tranzitivnost neplatí podle toho, když dokážeme, že některá uspořádaná dvojice chybí. Např. relace R[4 ]není tranzitivní, protože R[4] obsahuje [4,1] a také [1,2], pak by v této relaci měla být i uspořádaná dvojice [4,2]. Protože relace R[4 ]tuto uspořádanou dvojici neobsahuje, není relace R[4] tranzitivní. d) Relace R v množině M je antireflexivní právě tehdy, když pro "x Î M, [x, x] Ï R (můžeme také zapsat jiným způsobem " x Î M; x R´ x, kde R´ je relace doplňková). V řešené úloze má tuto vlastnost relace R[4], která neobsahuje žádnou uspořádanou dvojici typu [x,x].V uzlovém grafu se antireflexivnost projeví tak, že kolem žádného uzlu není smyčka. Objeví-li se v grafu jen jedna smyčka, relace není antireflexivní. Graf může obsahovat jednoduché i oboustranně orientované hrany. Např. R[3] není antireflexivní, protože obsahuje [1, 1], [2, 2]. e) Relace R v množině M je antisymetrická právě tehdy, když pro "x, y Î M; (x ¹ y Ù [x, y] Î R) => [y, x] Ï R (můžeme také zapsat jiným způsobem " x, y Î M; (x ¹ y Ù x R y) Þ y R´ x, kde R´ je relace doplňková ). V řešené úloze má tuto vlastnost relace R[5], protože k žádné uspořádané dvojici [x,y] (x je různé od y) neobsahuje relace dvojici [y,x].V uzlovém grafu se antisymetričnost projeví tak, že žádná orientovaná hrana (šipka) není obousměrná (dvojitá). Mohou se však kolem uzlu objevit smyčky. f) Relace R v množině M je souvislá neboli konektivní právě tehdy, když pro " x, y Î M; x ¹ y => ([x, y] Î R Ú [y, x] Î R) (můžeme také zapsat jiným způsobem " x, y Î M; x ¹ y Þ ( x R y Ú y R x) V řešené úloze má tuto vlastnost relace R[6. ]Každé dva prvky[ ]z množiny M jsou v zastoupeny v některé uspořádané dvojic. V uzlovém grafu se vlastnost projeví tak, že mezi každými dvěma uzly musí být jednoduchá nebo dvojitá orientovaná hrana, šipka. Mohou se vyskytnout i smyčky. Z našeho výkladu jste již poznali, že binární relace nemusí splňovat pouze jednu vlastnost. Může mít i vlastností více, které se vyskytují v různých kombinacích. V řešené úloze má relace R[3 ]vlastnosti symetričnosti i tranzitivnosti. Kontrolní úkoly: 1. Nakreslete uzlové a kartézské grafy binárních relací R[1], R[2], R[3], R[4], R[5], R[6] definované na množině M = {1, 2, 3, 4} z předchozí řešené úlohy. 2. Určete všechny vlastnosti relací R[1], R[2], R[3], R[4], R[5], R[6] definované na množině M = {1, 2, 3, 4} z předchozí řešené úlohy. Sledujte, jak se tyto vlastnosti projevují v jejich grafech. 3. Které vlastnosti relací se vzájemně vylučují a naopak, které může relace mít současně. Ukažte na uzlovém grafu. 4. Které z následujících binárních relací jsou symetrické, které tranzitivní: a) x je matkou y b) x je sourozenec y c) x bydlí ve stejném domě jako y d) x sedí ve stejné lavici jako y e) x sedí v lavici před y f) x mluví týmž jazykem jako y Můžete uvažovat i o dalších vlastnostech těchto relací. Shrnutí: Binární relace R v množině M je každá podmnožina kartézského součinu M ´ M. Binární relaci určujeme výčtem uspořádaných dvojic nebo charakteristickou vlastností. Znázorňujeme ji podobně jako kartézský součin graficky - obvykle kartézským nebo uzlovým grafem. U každé binární relace určujeme levý (první) a pravý (druhý) obor jako množinu všech prvních, resp. druhých složek uspořádaných dvojic. K binární relaci lze definovat relaci doplňkovou a inverzní. U binárních relací v množině M můžeme sledovat tyto vlastnosti: reflexivnost, symetričnost, tranzitivnost, antireflexivnost, antisymetričnost, konektivnost (souvislost). Každá relace může mít i několik vlastností. Pojmy k zapamatování: * binární relace * levý (první) a pravý (druhý) obor relace * grafy binárních relací * relace doplňková * relace inverzní * vlastnosti binárních relací Klíč - řešení kontrolních úkolů: Kap. 5.1: Pojem binární relace 2a) R[2 ]= {[1,1], [1,2], [1,3], [1,4], [1,5], [1,6], [2,2], [2,4], [2,6] [3,3], [3,6], [4,4], [5,5], [6,6]}, L(R[2]) = {1,2,3}, P(R[2]) = {1,2,3,4,5,6} R[3]= {[1,2], [2,4]}, L(R[3]) = {1,2,3}, P(R[3]) = {2,4} Množina N v R[1 ]i množina M v R[4 ]jsou množiny nekonečné. Kap. 5.2 Vlastnosti binárních relací: 2) R[1 ]je reflexivní, jinou vlastnost nemá. R[2 ]není reflexivní, je symetrická, není tranzitivní, není antireflexivní, není konektivní. R[3] není reflexivní, je symetrická, je tranzitivní, není antireflexivní, není konektivní. R[4] je antireflexivní, je antisymetrická, není reflexivní, není konektivní. R[5] není reflexivní, není symetrická, je antisymetrická, není antireflexivní, není konektivní. R[6] není reflexivní, není symetrická, není tranzitivní, není antireflexivní, není antisymetrická, je konektivní, 3) Relace nemůže být reflexivní a současně antireflexivní, symetrická a současně antisymetrická. Může mít současně vlastnosti reflexivnosti, symetričnosti, tranzitivnosti a konektivnosti. 4a) není symetrická, není tranzitivní 4b) je symetrická, je tranzitivní 4c) je symetrická, je tranzitivní 4d) je symetrická, je tranzitivní 4e) není symetrická, je tranzitivní 4f) je symetrická, je tranzitivní 6 Relace ekvivalence a rozklad množiny Prostudování této kapitoly Vám zabere cca 2 hodiny. Cíle Po prostudování této kapitoly byste měli umět: · vyjmenovat vlastnosti relace ekvivalence, · rozhodnout, zda relace je relací ekvivalence, · rozložit množinu na třídy (určit rozklad množiny), · vysvětlit vlastnosti rozkladu množiny, · určit reprezentanta třídy rozkladu. Průvodce studiem: Tato kapitola bezprostředně navazuje na kapitolu předchozí. Než se pustíte do studia, pořádně si zopakujte zejména první tři vlastnosti relací - reflexivnost, symetričnost, tranzitivnost. Význam kapitoly spočívá také v tom, že je východiskem pro jednu z definic přirozeného čísla. Důležitá pasáž textu: Relace R definovaná v M, která je reflexivní, symetrická a tranzitivní se nazývá relace ekvivalence na množině M. Řešený příklad 1: Je dána množina M přímek v rovině (viz obrázek). Na této množině uvažujme binární relaci R: „přímka x je rovnoběžná s přímkou y“, což můžeme symbolicky zapsat R = {[x, y] Î M ´ M, x ‖ y} [DEL: :DEL] Vyřešte následující úlohy: 1. Zapište množinu M všech přímek na obrázku. 2. Vytvořte kartézský součin M ´ M. 3. Zapište relaci R výčtem prvků. (Poznámka: V tomto případě budeme považovat i splývající přímky za rovnoběžné. Např. a ‖ a , tedy [a, a] Î R. 4. Nakreslete uzlový graf relace R. 5. Zjistěte vlastnosti relace R v množině M. 6. Rozhodněte, zda je relace R ekvivalence na množině M. Řešení: 1. M = {a, b, c, d, e, f} 2. M ´ M = {[a,a], [a,b], [a,c], [a,d], [a,e], [a,f], [b,a], [b,b],..., [f, f]} V kartézském součinu M ´ M zde nejsou vypsány všechny uspořádané dvojice. Množina M obsahuje 6 prvků, kartézský součin M ´ M tedy obsahuje 36 uspořádaných dvojic prvků. Chybějící dvojice si doplňte sami. 3. a) výčtem prvků: R = {[a, a], [b, b], [b, c], [b, d], [c, b], [c, c], [c, d], [d, b], [d, c], [d, d], [e, e], [e, f], [f, e], [f, f]}. b) charakteristickou vlastností: R = {[x, y] Î M ´ M, x ‖ y} 4. Můžete si nakreslit uzlový graf relace R: 5. Relace je na množině M reflexivní, symetrická a tranzitivní. 6. Relace R je relace ekvivalence na množině M. Prohlédněte si pozorně uzlový graf relace R ve výše uvedeném příkladu. Je patrné, že množina A s díky relaci R rozpadla na 3 části, podmnožiny {a}, {b, c, d}, {e, f}. V každé z nich jsou navzájem rovnoběžné přímky, tedy prvky, které jsou spolu v relaci. Je-li relace ekvivalence definovaná na množině M, rozkládá tuto množinu na třídy rozkladu T[1], T[2], T[3],… T[n]. Každá ekvivalence definovaná na množině umožňuje provést jediný takový rozklad. V naší řešené úloze jsme zjistili, že relace R je reflexivní, symetrická a tranzitivní, relace R je relace ekvivalence. Tato ekvivalence způsobuje rozklad množiny M na 3 třídy (na uzlovém grafu na obrázku vidíme, že graf se rozdělil na tři části): T = {T[1], T[2], T[3]} T[1] = {a} - s přímkou a není rovnoběžná žádná jiná přímka, tvoří samostatnou třídu rozkladu, T[2] = {b, c, d} - přímky b,c,d jsou navzájem rovnoběžné, patří do téže třídy rozkladu, T[3][ ]= {e, f} - přímky e,f jsou navzájem rovnoběžné, patří do téže třídy rozkladu. Obrázek názorně ukazuje rozklad množiny M. Prvky množiny T tj. množiny T[1], T[2], T[3], .., mají tyto vlastnosti: a) Každý prvek x Î M patří do některé z množin T[1], T[2], T[3], ...T[n],[ ] tj. platí: T[1]ÈT[2]È T È…T[n] = M. To znamená, že každý prvek množiny M patří do některé třídy rozkladu. b) Každé dvě množiny T[1], T[2], T[3], ... jsou navzájem disjunktní. To znamená, že žádný prvek množiny M patří právě do jedné třídy, nemůže patřit do dvou nebo několika tříd současně. c) Žádná z množin T[1], T[2], T[3], ... nemůže být prázdná. Důležitá pasáž textu: Množina T (systém množin), která má uvedené vlastnosti, se nazývá rozklad (klasifikace, třídění) množiny M. Prvky množiny T se jmenují třídy rozkladu. Každá třída rozkladu T je jednoznačně určena jejím libovolným prvkem. Říkáme, že kterýkoli prvek tuto třídu reprezentuje a nazývá se reprezentant třídy. Průvodce studiem: Učivo probrané kapitoly - relace ekvivalence, rozklad množiny na třídy - procvičíme také na úlohách, se kterými se v praxi v různých obměnách setkáváte: při třídění různých předmětů, objektů. Při třídění pojmů se vychází z nějakého znaku. Říkáme, že „objekt x má tentýž charakteristický znak jako objekt y“. Tato relace je relace ekvivalence, způsobí rozklad množiny na 2 třídy (do jedné třídy patří všechny prvky, které zvolený znak mají a do druhé třídy všechny ostatní objekty, které zvolený znak nemají). Takové třídění nazveme dichotomické. Kontrolní úkoly: 1. Které z následujících binárních relací jsou ekvivalence na množině Z všech obyvatel města Brna: a) x je narozen ve stejném znamení zvěrokruhu jako y b) x má menší hmotnost než y, c) x je vyšší než y, d) x bydlí ve stejné ulici jako y. 2. Vytvořte soubor geometrických útvarů (trojúhelník, čtverec, obdélník a kruh) vystřižením z barevných papírů (v červené, modré, žluté a zelené barvě). V souboru geometrických útvarů tak vytvoříte 16 prvků - 4 trojúhelníky, 4 čtverce, 4 obdélníky, 4 kruhy. a) Na tomto souboru definujte relaci R: „útvar x má stejný tvar jako útvar y“. Zdůvodněte,že se jedná o relaci ekvivalence. Nalezněte třídy rozkladu. Zdůvodněte správnost vytvořeného rozkladu. b) Najděte další relaci ekvivalence na tomto souboru a opět vytvořte rozklad. 3. Ukažte, že uvedené binární relace jsou ekvivalence a určete v jednotlivých případech třídy rozkladu: a) „x začíná týmž písmenem jako y“ na množině všech slov spisovné češtiny, b) „x má stejný věk jako y“ na množině obyvatel ČR, c) „x má stejnou nadmořskou výšku jako y“ na množině všech míst na Zemi, d) „x je menší než y“ na množině dětí ve třídě, Shrnutí: Relace R definovaná v M, která je reflexivní, symetrická a tranzitivní se nazývá relace ekvivalence. Jakákoliv relace ekvivalence definovaná na množině M, vytváří rozklad této množiny na takové třídy rozkladu, že každý prvek množiny M patří do jedné třídy rozkladu. Každé dvě třídy rozkladu jsou disjunktní a jejich sjednocení tvoří množinu M. Kterýkoli prvek, který třídu rozkladu reprezentuje se nazývá reprezentant třídy. Pojmy k zapamatování: · relace ekvivalence · vlastnosti relace ekvivalence (reflexivnost, symetričnost, tranzitivnost) · rozklad množiny na třídy na základě ekvivalence · vlastnosti rozkladu množiny · dichotomický rozklad · reprezentant třídy rozkladu Klíč - řešení kontrolních úkolů: 1. Ekvivalence jsou a), d). 7 Relace uspořádání Prostudování této kapitoly vám zabere přibližně 2 hodiny Průvodce studiem: Slovo „uspořádání“ má v praxi význam stanovení pořadí: první, druhý, třetí,… Ukážeme si matematický význam uspořádání a jeho vlastnosti. Využijeme k tomu dalších vlastností binárních relací. Cíle Po prostudování této kapitoly byste měli umět: · definovat relaci ostrého lineárního uspořádání, · rozhodnout, zda relace je relace uspořádání, · charakterizovat dobré uspořádání, · charakterizovat uspořádanou a dobře uspořádanou množinu, · určit první a poslední prvek uspořádané množiny. Řešený příklad: Na množině chlapců H = {Lukáš, Filip, Martin, Jakub} je dána binární relace „X je starší než Y“. Víme, že Filip je starší než Lukáš, Martin je starší než Lukáš, Martin je starší než Filip, Martin je starší než Jakub, Filip je starší než Jakub, Jakub je starší než Lukáš. Který z chlapců je nejstarší, který nejmladší? Situaci můžeme popsat jako množinu uspořádaných dvojic, tedy relaci R = {[F,L], [M,L], [M,F], [M,J], [F,J], [J,L]}. Díky relaci R můžeme chlapce z množiny H uspořádat podle jejich věku: M, F, J, L a můžeme mluvit o uspořádané množině H. Abychom ji odlišili od původní neuspořádané množiny H, značíme ji takto: ëHû = ë{M, F, J, L}û. Také můžeme říci, že v takto uspořádané množině je např. M před F, F před J, M před J,... Nejstarší je Martin, nejmladší je Lukáš, Tato relace je antireflexivní, antisymetrická, tranzitivní a konektivní (souvislá). Důležitá pasáž textu: Relace R v množině M, která je antireflexivní, antisymetrická, tranzitivní a konektivní (souvislá) se nazývá relace ostrého lineárního uspořádání. Poznámka: Protože jiným uspořádáním se nebudeme zabývat, budeme krátce zpravidla hovořit jen o uspořádání. Uspořádanou dvojici [x, y] Î R, kde R je relace uspořádání, zapisujeme x ≺ y a čteme prvek x je před prvkem y. Množina M, v níž je definováno uspořádání, se nazývá uspořádaná množina. Mezi uspořádané množiny budeme počítat i prázdnou množinu a všechny jednoprvkové množiny. Uspořádanou množinu M budeme označovat symbolem ëMû. V běžném životě se můžeme setkat s mnoha příklady uspořádaných množin: · Trpaslíci, jdoucí za sebou lesem v pohádce „O Sněhurce“. · Auta stojící na červenou na křižovatce v jednom pruhu. · Každý seznam osob zapsaných podle abecedy. · Závodníci, kteří dobíhají do cíle v běžeckém závodě. · Děti seřazené podle velikosti od nejmenšího po největší. · Obsah kapitol v knize. Řešený příklad: Je dána množina M = {1, 2, 3, 4} a na ní relace R. a) Určete vlastnosti relace R = {[2,1], [2, 3], [2, 4], [1, 3], [1, 4], [4,3]}. b) Uspořádejte množinu M na základě relace R. Řešení: a) Možností, jak úlohu řešit, je více. Jednou z nich je vytvoření uzlového grafu. Ze zápisu relace výčtem prvků i z grafu určíme vlastnosti relace: a) Relace neobsahuje žádnou uspořádanou dvojici [x,x], graf neobsahuje žádnou smyčku kolem žádného uzlu, tzn. že relace je antireflexivní, b) Relace neobsahuje uspořádané dvojice [x,y], [y,x], v grafu není žádná orientovaná hrana dvojitá (žádná oboustranná šipka), tzn. že relace je antisymetrická, c) V relaci platí, že " x,y Î M; x ¹ y Þ (xRy Ú yRx), každé dva uzly grafu jsou spolu spojeny hranou, tzn. že relace je souvislá, d) V relaci platí, že " x, y, z Î M; (xRy Ù yRz) Þ xRz, každé tři uzly grafu jsou spojeny tak, že relace je tranzitivní. Odpověď: Relace R je antireflexivní, antisymetrická, souvislá a tranzitivní. Relace, která má vyjmenované vlastnosti, se nazývá relace uspořádání. b) Budeme si všímat každé uspořádané dvojice a slovně vyjádříme, co znamená, že uspořádaná dvojice patří relaci R. Zápis: [2, 1] Î R znamená, že číslo 2 je před číslem 1, [2, 3] Î R znamená, že číslo 2 je před číslem 3, [2, 4] Î R znamená, že číslo 2 je před číslem 4. Tuto skutečnost můžeme zapsat symbolicky: 2 ≺ 1, 2 ≺ 3, 2 ≺ 4. Číslo 2 je tedy před všemi ostatními čísly. Zápis: [1, 3] Î R znamená, že číslo 1 je před číslem 3, [1, 4] Î R znamená, že číslo 1 je před číslem 4. Opět můžeme zapsat tuto skutečnost symbolicky: 1 ≺ 3, 1 ≺ 4. Číslo 1 je tedy před čísly 3, 4. Nyní už víme, že prvním číslem je číslo 2 a za ním následuje číslo 1. Zbývá už rozhodnout o pořadí čísel 3, 4. Protože do relace R patří [4, 3], což znamená že číslo 4 je před číslem 3, symbolicky zapsané 4 ≺ 3. Číslo 3 je tedy posledním prvkem. Relace R uspořádá množinu M takto: ëMû = ë{2,1,4,3}û. Uspořádání množiny můžeme poznat podle výčtu uspořádaných dvojic relace uspořádání, jak bylo uvedeno předcházejícím textu, ale i z uzlového grafu. Graf nám pomáhá při určování vlastností relace, a tedy také, zda relace je či není relací uspořádání. Uzlový graf si pořádně prohlédněte. Co vidíme? · Je jen jediný uzel, ke kterému nesměřuje žádná šipka (nebo také z něho vycházejí všechny šipky) to je tedy první prvek uspořádané množiny ëMû, číslo 2. · Je jen jediný uzel, ke kterému směřuje jedna šipka, to je druhý prvek ëMû, číslo 1. · Je jen jediný uzel, ke kterému směřují dvě šipky, to je třetí prvek ëMû, číslo 4. · Je jen jediný uzel, ke kterému směřují tři šipky, to je čtvrtý prvek ëMû, číslo 3. Z těchto čtyř bodů nám vyplyne uspořádání množiny ëMû = ë{2,1,4,3}û. K relaci R vytvoříme relaci inverzní R^-1 = {[1,2], [3, 2], [4, 2], [3, 1], [4,1], [3,4]}. Relace R^-1 je antireflexivní, antisymetrická, tranzitivní a souvislá. Je to tedy také relace uspořádání. Relace R uspořádala množinu M takto ëM [1]û = ë{2,1,4,3}û, relace R^-1 uspořádá množinu M takto ëM[2]û = ë{ 3,4,1,2}û. (R^-1 uspořádala prvky množiny M v opačném pořadí než relace R). Důležitá pasáž textu: Každá podmnožina uspořádané množiny je uspořádána právě tak, jako daná množina. Dvě uspořádané množiny jsou si rovny, obsahují-li tytéž prvky a mají-li přitom totéž uspořádání. Liší-li se uspořádané množiny ve svých prvcích nebo ve svém uspořádání, jsou různé. Řešený příklad: V pohádce „O veliké řepě“ se snaží vytáhnout řepu dědek, babka, vnučka, pes, kočka a myš. Ukažte, že se jedná o uspořádanou množinu, určete její první a poslední prvek. Řešení: Množina ëMû = ë{D, B, V, P, K, M}û. je uspořádaná, je na ní definována relace uspořádání (antireflexivní, antisymetrická, tranzitivní a souvislá). Prvním prvkem uspořádané množiny ëMû je dědeček (protože je před všemi ostatními), posledním prvkem je myš (protože všechny zbývající postavy z pohádky jsou před ní). Důležitá pasáž textu: Prvek x uspořádané množiny ëMû, který je před všemi ostatními prvky množiny ëMû, se nazývá první prvek množiny ëMû. Prvek y uspořádané množiny ëM û, před kterým jsou všechny ostatní prvky množiny ëM û, se nazývá poslední prvek množiny ëMû. Každá uspořádaná množina má nejvýše jeden první a nejvýše jeden poslední prvek. Uspořádaná množina ëMû se nazývá dobře uspořádaná, právě když každá její neprázdná podmnožina má první prvek. Takovou dobře uspořádanou množinou je ëMû = ë{D, B, V, P, K, M}û z naší pohádky. Například podmnožina L = ë{ V, P, K}û má první prvek, kterým je vnučka (protože je před všemi ostatními prvky množiny L). Je-li množina M dobře uspořádaná, pak relace R, která množinu dobře uspořádá, se nazývá dobré uspořádání v množině ëMû. Mezi dobře uspořádané množiny řadíme také prázdnou množinu a všechny jednoprvkové množiny. Kontrolní úkoly: 1. Najděte všechna uspořádání množiny A = {1,2,3,4}. Jednu si vyberte a na ní ověřte, že množina je v tomto případě dobře uspořádaná. 2. V množině M = {1, 2, 3, 4, 5, 6} je dána relace R = {[x, y] Î M x M, x > y}. Ověřte, že relace R je ostrým lineárním uspořádáním v množině M. 3. Nakreslete uzlové grafy relací R[1], R[2] a R[3] a upravte je tak, aby představovaly relace ostrého lineárního uspořádání v množině M = {a, b, c, d, e}. a) R[1] = {[a, c], [b, d], [d, e], [e, b]}, b) R[2] = {[a, b], [b, d], [e, c], [e, a], [d, c]}, c) R[3] = {[a, e], [b, c], [c, d], [e, b]}. Shrnutí: Relace R, která je antireflexivní, antisymetrická, tranzitivní a konektivní se nazývá relace ostrého lineárního uspořádání. Uspořádanou dvojici [x, y] Î R, kde R je relace uspořádání, budeme zapisovat x ≺ y a čteme prvek x je před prvkem y. Je-li relace R uspořádáním v množině M, je také inverzní relace R^-1 uspořádáním v množině M. Množina M, v níž je definováno uspořádání, se nazývá uspořádaná množina. Mezi uspořádané množiny budeme počítat i prázdnou množinu a všechny jednoprvkové množiny. Uspořádanou množinu M budeme označovat symbolem ëMû. Každá podmnožina uspořádané množiny je uspořádána právě tak, jako daná množina. Dvě uspořádané množiny jsou si rovny, obsahují-li tytéž prvky a mají-li přitom totéž uspořádání. Liší-li se uspořádané množiny ve svých prvcích nebo ve svém uspořádání jsou různé. Prvek x uspořádané množiny ëMû, který je před všemi ostatními prvky množiny ëMû, se nazývá první prvek množiny ëMû. Prvek y uspořádané množiny ëM û, před kterým jsou všechny ostatní prvky množiny ëM û, se nazývá poslední prvek množiny ëMû. Každá uspořádaná množina má nejvýše jeden první a nejvýše jeden poslední prvek. Uspořádaná množina ëMû se nazývá dobře uspořádaná, právě když každá její neprázdná podmnožina má první prvek. Je-li množina M dobře uspořádaná, pak relace R, která množinu dobře uspořádá, se nazývá dobré uspořádání v množině ëMû. Mezi dobře uspořádané množiny řadíme prázdnou množinu a všechny jednoprvkové množiny. Pojmy k zapamatování: · relace ostrého lineárního uspořádání · uspořádaná množina · první a poslední prvek uspořádané množiny · rovnost uspořádaných množin · dobře uspořádaná množina · relace dobrého uspořádání Klíč -řešení kontrolních úloh: 1. Množinu A lze uspořádat 16 různými způsoby, například: ë{1,2,3,4}û, ë{2,1,3,4}û, ë{3,1,2,4}û, ë{4,1,2,3}, ë{1,3,2,4}û, ë{1,4,2,3}û,… Každá takto uspořádaná množina má první prvek, je tedy uspořádaná dobře. 2. Relaci R zapíšeme výčtem uspořádaných dvojic: R= {[6,1], [6,2], [6,3], [6,4], [6,5], [5,1], [5,2], [5,3], [5,4], [4,1], [4,2], [4,3], [3,1], [3,2], [2,1]}. Je antireflexivní, antisymetrická, tranzitivní a konektivní (souvislá), splňuje vlastnosti ostrého lineárního uspořádání. 8 Relace zobrazení Cíle Po prostudování kapitoly budete umět: · definovat relaci zobrazení, pojmy vzor a obraz · definiční obor zobrazení a obor hodnot zobrazení, · poznat a určit druhy zobrazení, · poznat a vysvětlit význam prostého zobrazení. Prostudování kapitoly Vám zabere přibližně 2 hodiny. Průvodce studiem: Dosud jsme většinou uvažovali o případech relací „uvnitř“ jedné množiny, například M, které byly podmnožinami kartézského součinu M ´ M. Doporučuji vám vrátit se ke kapitole 4 a znovu si připomenout, že jsme obecně za kartézský součin A ´ B považovali množinu všech uspořádaných dvojic, kde první složka byla prvkem množiny A, druhá složka prvkem množiny B, tedy složek ze dvou různých množin. Ukažme si to na řešené úloze: Řešený příklad 1: Mějme množinu moravských měst A = {Brno, Ostrava, Olomouc, Přerov, Opava} a řek B = {Morava, Bečva, Dyje, Svratka, Odra}. Binární relace je určena vztahem „městem X protéká řeka Y. Určete výčtem uspořádaných dvojic tuto relaci. Do hledané relace R Ì A ´ B patří uspořádané dvojice [Brno, Svratka], [Ostrava, Odra], [Olomouc, Morava], [Přerov, Bečva]. První složkou relace nebude město Opava (žádná z uvedených řek jí neprotéká), druhou složkou relace nebude řeka Dyje (neprotéká žádným z uvedených měst). Jedná se tedy o binární relaci „z množiny do množiny“. Důležitá pasáž textu: Relaci Z Ì A x B nazveme zobrazením z množiny A do množiny B, právě když ke každému prvku a Î A existuje nejvýše jeden prvek bÎ B takový, že [a, b] Î Z. Jestliže [a, b] Î Z, pak prvek a se nazývá vzorem prvku b, prvek b se nazývá obrazem prvku a v zobrazení Z. První obor zobrazení se nazývá definiční obor zobrazení Z (někdy se také říká množina všech vzorů), označujeme O[1](Z) a druhý obor zobrazení se nazývá obor hodnot zobrazení Z (někdy se také říká množina všech obrazů) a označuje se O[2](Z). Řešený příklad 2: Jsou dány množiny A = {a, b, c, d}, množina B = {x, y, z, u}. Určete, která relace znázorněná uzlovým grafem je zobrazením. Řešení: Kartézský součin množin A´B obsahuje 16 (protože A i B mají po 4 prvcích) uspořádaných dvojic: A´B = {[a, x], [a, y], [a, z], [a, u], [b, x], [b, y], [b, z], [b, u], [c, x], [c, y], [c, z], [c, u], [d, x], [d, y], [d, z], [d, u]}. Prozkoumejme na obou uzlových grafech relace Z[1, ]Z[2]. Relace Z[1] je podmnožinou kartézského součinu A´B. Relace Z[1 ]na obrázku vlevo je zobrazením, protože splňuje definici zobrazení: ke každému prvku z množiny A je přiřazen nejvýše jeden prvek z množiny B, Z[1]={[a,y], [b,x],[d,z]}. Poznáme to z grafu zcela jednoduše - z každého uzlu grafu vychází nejvýše jedna šipka. Říkáme, že ke každému vzoru je přiřazen nejvýše jeden obraz. Relace Z[2] je podmnožinou kartézského součinu A´B. Relace Z[2] ={[b,x], [c,z], [c,u} na obrázku vpravo není zobrazením, neboť nesplňuje definici zobrazení: z uzlu c vycházejí dvě šipky (vzoru c jsou přiřazeny dva obrazy z, u. Průvodce studiem: V následujících řádcích se seznámíte se základními druhy (v některých publikacích se uvádí – typy) zobrazení. Vycházíme z definice zobrazení a budeme rozhodovat podle toho, v jakém vztahu jsou první (definiční) obor zobrazení k množině A a druhý obor (obor hodnot) zobrazení k množině B. Na obrázcích jsou znázorněny druhy zobrazení schematicky: O[1](Z) a O[2](Z) jsou vyšrafované kruhy. a) zobrazení z množiny A do množiny B je nejobecnějším typem, toto označení lze použít vždy. Jím není řečeno o oborech zobrazení (definičním oboru zobrazení - O[1](Z), oboru hodnot zobrazení O[2](Z)) nic víc, než O[1](Z) Ì A Ù O[1] ¹ A a O[2](Z) Ì BÙ O[2] ¹ B. Poznámka: Při určování typů zobrazení u konečných množin můžeme s určitou mírou zjednodušení chápat zobrazení z množiny A do množiny B jako zobrazení „necelé“ množiny A na „necelou“ množinu B. Znamená to, že v A existuje aspoň jeden prvek, který není vzorem žádného prvku z B a v B existuje aspoň jeden prvek, který není obrazem žádného prvku z A. b) v zobrazení z množiny A na množinu B platí, že O[1](Z) Ì A Ù O[1] ¹ A, O[2](Z) = B. Jedná se o zobrazení „necelé“ množiny A na „celou“ množinu B, to znamená, že v A existuje prvek, který není vzorem žádného prvku z B a každý prvek z B je aspoň jednou obrazem nějakého prvku z A), c) zobrazení Z je zobrazením množiny A do množiny B, právě když O[1](Z) = A, O[2](Z) Ì B Ù O[2] ¹ B, Jde tedy o zobrazení „celé“ množiny A na „necelou“ množinu B, tzn. každý prvek z A je vzorem a v B existuje aspoň jeden prvek, který není obrazem žádného prvku z A. d) zobrazení Z je zobrazením množiny A na množinu B, právě když platí O[1](Z) = A a O[2](Z)=B. Jde o zobrazení „celé“ množiny A na „celou“ množinu B (tzn. každý prvek z A je vzorem a každý prvek z B je aspoň jednou obrazem nějakého prvku z A). Každý druh (typ) zobrazení, který byl popsán výše, může být navíc prostým zobrazením. Důležitá pasáž textu: Zobrazení Z z A do B se nazývá prosté, právě když každým dvěma různým vzorům x[1], x[2] z množiny A přiřazujeme dva různé obrazy y[1], y[2] z množiny B. Pak hovoříme o: · prostém zobrazení z množiny A do množiny B, · prostém zobrazení z množiny A na množinu B, · prostém zobrazení množiny A do množiny B, · prostém zobrazení množiny A na množinu B. Prosté zobrazení množiny A na množinu B se nazývá vzájemně jednoznačné zobrazení. Řešený příklad: Nechť jsou dány množina A = {1, 2, 3, 4} a množina B = {a, b, c, d}. Rozhodněte, zda zobrazení Z[1] = {[1,a], [2,c], [3,d]} je prostým zobrazením. Řešení: Budeme rozhodovat podle definice prostého zobrazení. Relace Z[1] = {[1,a], [2,c], [3,d]} je zobrazení, protože každému prvku z množiny A je přiřazen nejvýše jeden prvek z množiny B. Je to zobrazení z množiny A do množiny B protože O[1](Z[1])ÌA a O[2](Z[1]) Ì B. Že jde o zobrazení prosté poznáme podle definice – ke každým dvěma různým vzorům x[1], x[2] Î A přiřazujeme dva různé obrazy y[1], y[2] z množiny B. Kontrolní úkoly: 1. Jsou dány množiny A, B: A = {a, b, c, d}, B = {1, 2, 3}. Rozhodněte, které z binárních relací R[1 ]- R[5 ] jsou zobrazení z A do B, určete jejich typ a posuďte, zda se jedná o zobrazení prosté: a) R[1] = {[a,1], [b,2], [d,3]} b) R[2] = {[a,2], [c,1], [a,2], [b,3]} c) R[3] = {[a,1], [b,2],[c, 3] [d,1]} d) R[4] = {[b,3]} e) R[5] = {[a,2], [c,1], [d,2], [b,3]} 2. Je dána množina skandinávských států S = {Švédsko, Norsko, Finsko, Dánsko} a množina měst M = {Stockholm, Oslo, Helsinky, Kodaň}. Určete zobrazení množiny S na množinu M a rozhodněte, zda se jedná o zobrazení prosté. 3. Zjistěte, zda se jedná o zobrazení a určete jeho typ: a) každý návštěvník divadla sedí právě na jednom sedadle, b) každý žák 3.A dostal na vysvědčení právě jednu známku z matematiky. 4. Uvažujte množinu všech cestujících v jisté tramvaji, množinu všech sedadel v této tramvaji a binární relaci určenou vztahem „osoba X sedí na sedadle Y“. Přemýšlejte o různých situacích v této tramvaji (např. „každý cestující sedí na jednom sedadle a ještě jsou dvě místa volná“) a rozhodněte, zda se jedná o zobrazení z množiny cestujících do množiny sedadel. Pokud ano, určete přesně typ tohoto zobrazení. 5. Na pískovišti si hrají Adélka, Agátka, Anežka, Anička a Alžbětka, které jsou dcerami paní Horákové, Dvořákové a Novákové. Určete, zda relace „každá z žen je matkou jedné z uvedených dívek“ je zobrazení a o který typ se jedná. Shrnutí: Zobrazení z množiny A do množiny B je každá binární relace Z, právě když ke každému prvku a Î A existuje nejvýše jeden prvek bÎ B takový, že [a, b] Î Z. Říkáme, že ke každému vzoru je přiřazen nejvýše jeden obraz. Rozlišujeme 4 typy zobrazení: * z množiny A do množiny B, * množiny A na množinu B, * z množiny A na množinu B, * množiny A na množinu B. Každý druh (typ) zobrazení, který byl popsán výše, může být navíc prostým zobrazením. Zobrazení je prosté, právě když každým dvěma různým vzorům x[1], x[2] z množiny A přiřazujeme dva různé obrazy y[1], y[2] z množiny B. Prosté zobrazení množiny A na množinu B se nazývá vzájemně jednoznačné zobrazení. Pojmy k zapamatování: * zobrazení, druhy (typy) zobrazení * první a druhý obor zobrazení * prosté zobrazení * vzájemně jednoznačné zobrazení Klíč - řešení kontrolních úloh: 1. R[1] - je prosté zobrazení z A na B R[2] - není zobrazení (prvek a je 1. složkou ve dvou uspořádaných dvojicích R[3] = {[a,1], [b,2],[c, 3] [d,1]} - je zobrazení A na B, není prosté (prvkům a, d je přiřazen stejný prvek 1) R[4] = {[b,3]} - je prosté zobrazení z A do B R[5] = {[a,2], [c,1], [d,2], [b,3]} - je zobrazení A na B, není prosté (prvkům a, d je přiřazen stejný prvek 2). 2. Zobrazení Z ={[Švédsko, Stockholm], [Norsko, Oslo], [Finsko, Helsinky], [Dánsko, Kodaň]} je prosté zobrazení S na M (zobrazení vzájemně jednoznačné). 3. a) prosté zobrazení množiny návštěvníků divadla do množiny sedadel (je-li vyprodáno, pak na množinu sedadel) b) zobrazení množiny žáků do množiny známek (bude-li ve třídě aspoň jedna pětka, pak na množinu známek) není prosté. 4. Jedná se o prosté zobrazení množiny cestujících do množiny sedadel. 5. Relace není zobrazením (některá z matek - vzor má více než jedno dítě - více než dva obrazy). 9 Ekvivalence množin Cíle Po prostudování kapitoly budete umět: · definovat ekvivalentní množiny, · definovat kardinální číslo, · definovat přirozené číslo. Prostudování kapitoly Vám zabere přibližně 2 hodiny. Důležitá pasáž textu: Množiny A, B nazýváme ekvivalentní a píšeme A ~ B, právě když existuje prosté (vzájemně jednoznačné) zobrazení množiny A na množinu B. Řešený příklad 1: Na obrázku jsou znázorněny množiny A, B, C. Určete, které z nich jsou navzájem ekvivalentní. Řešení: Mezi množinami A, B existuje prosté zobrazení množiny A na množinu B, resp. množiny B na množinu A (existuje vzájemně jednoznačné přiřazení A na B, resp. B na A). Naproti tomu nelze sestrojit prosté zobrazení množiny B na množinu C a prosté zobrazení množiny A na množinu C, to znamená, že množiny A a C a B a C navzájem ekvivalentní nejsou. Povšimněme si, že množiny A a B mají stejný počet prvků, množiny A a C, resp. B a C nemají stejný počet prvků. Jestliže dvě množiny mají stejný počet prvků, říkáme, že jsou navzájem ekvivalentní. Relace R "být ekvivalentní mezi množinami" je relací ekvivalence (je reflexivní, symetrická a tranzitivní). Proto k relaci R ~ přísluší rozklad systému množin M na třídy. V téže třídě rozkladu budou vždy právě všechny množiny, které jsou navzájem ekvivalentní, tj. mají stejný počet prvků. Každou třídu rozkladu nazveme kardinální číslo. Řešený příklad 2: Jsou dány množiny: A - množina dětských hrdinů knihy Bylo nás pět B - množina vrcholů pětiúhelníka C - množina okvětních lístků jabloňového květu Přesvědčte se, že množiny jsou navzájem ekvivalentní. Řešení: Existuje prosté zobrazení množiny A na množinu B (a obráceně: množiny B na množinu A): každé postavě z knihy přiřadíme právě jeden vrchol pětiúhelníka, zobrazení je vzájemně jednoznačné, obě množiny mají stejný počet prvků. Stejně posoudíme i relace mezi A a C, B a C, A a D, B a D, C a D. Ve všech případech se jedná o vzájemně jednoznačná zobrazení. Každé dvě množiny jsou navzájem ekvivalentní, patří do téže třídy rozkladu T[1 ]= {A, B, C, D}, mají stejné kardinální číslo (5). Řešený příklad 3: Rozhodněte, které množiny tvarů jsou navzájem ekvivalentní. (Připomeňte si: Dvě množiny jsou ekvivalentní, právě když existuje aspoň jedno prosté zobrazení jedné množiny na druhou.) Řešení: Vyznačte např. vzájemně jednoznačné zobrazení množiny trojúhelníků na množinu čtverců. 4 7 M 2 1 3 6 Kardinální čísla jsou tedy třídy navzájem ekvivalentních množin.. Místo pojmu „kardinální číslo“ se též užívá pojem „mohutnost množiny“, což vystihuje společnou vlastnost navzájem ekvivalentních množin. Ekvivalentní množiny mají stejné kardinální číslo, stejnou mohutnost. U konečných množin to znamená, že mají stejný počet prvků. Kardinální čísla konečných množin nazveme přirozená čísla. Např. kardinální číslo (třídu) množin, do které patří v naší úloze množina trojúhelníků, označíme 4. Kontrolní úkoly: 1. Posuďte, které z následujících množin jsou navzájem ekvivalentní: A - množina všech světových stran B - množina ročních období C = {1, 2, 3, 4, 5} D - množina rohů čtvercového stolu E = {Jana, Jarka, Jitka, Josefína, Jarmila}. Svá řešení odůvodněte. 2. Uveďte alespoň 5 příkladů množin, které jsou ekvivalentní s množinou A = {x Î N, x < 8}, kde N je množina všech přirozených čísel. Shrnutí: Množiny A, B nazýváme ekvivalentní a píšeme A ~ B, právě když existuje prosté (vzájemně jednoznačné) zobrazení množiny A na množinu B. Relace R "být ekvivalentní mezi množinami" je relací ekvivalence, přísluší k ní rozklad systému množin M na třídy, které nazveme kardinální čísla. Kardinální čísla konečných množin nazveme přirozená čísla. Pojmy k zapamatování: * A ~ B (množina A je ekvivalentní s množinou B), * kardinální číslo, * přirozené číslo Klíč - řešení kontrolních úloh: 1. Navzájem ekvivalentní jsou A, B, D. 2. S množinou A jsou ekvivalentní např. množina 7 aut na parkovišti, 7 lidí v autobusu,…. Průvodce studiem: Text, k jehož závěru jste právě dospěli, je pokusem zpracovat studijní materiál tak, aby vám byla poskytnuta možnost využít jej k samostatnému studiu - učební činnosti, řízené formou minimálního počtu kontaktních konzultací. Při samostatném studiu byste jako jeho uživatelé měli být postupně vedeni k proniknutí do dané problematiky, do příslušného pojmového systému, orientováni na postižení základních souvislostí. Je na vás, abyste posoudili, do jaké míry se tento záměr podařilo realizovat. Zkuste si nyní znovu položit otázku, kterou jste si v průběhu studia v různých obměnách již pravděpodobně položili: Jakou matematickou průpravu potřebuje ve svém přípravném vzdělávání učitelka mateřské školy? Potřebuje ji vůbec? Sama jsem si ji jako absolventka střední pedagogické školy kladla mnohokrát. Vím, že mezi mými spolužačkami na střední škole matematika nepatřila mezi stěžejní a oblíbené předměty, nepatří mezi ně ani mezi studentkami vysokoškolského studia učitelství pro mateřské školy. Vaše matematické znalosti jsou často chatrné, mezerovité, mnohdy formální. Jádrem vaší kvalifikace není odborná matematika, ale psychodidaktická kompetence – vytvářet klima, v němž se formuje a všestranně rozvíjí tvořivá aktivita dítěte. Přesto jsem přesvědčena, že určitý oborově matematický nadhled, solidní znalost odborné podstaty matematiky do vaší poznatkové výbavy patří. Text, se kterým jste se seznámili, vám má alespoň určitým dílem pomoci ve studiu i v praxi. Chce být pouze malým příspěvkem k získání takových teoretických poznatků, které se mohou stát užitečným návodem k jednání skrze vaše tvořivé myšlení. Přeji vám mnoho úspěchů ve studiu i v tvořivé práci s dětmi. Autorka Použitá a doporučená literatura: Blažková, R. (2010). Rozvoj matematických pojmů a představ u dětí předškolního věku. Elportál Brno: Masarykova univerzita. Coufalová, J. (1990). Základy elementární aritmetiky. Plzeň: FPe. Drábek, J., et al. (1985). Základy elementární aritmetiky pro studium učitelství 1. st. ZŠ. Praha: SPN. Eberová, J., & Stopenová, A. (1997). Matematika I. Olomouc: UP. Eberová, J. et. al. (2000). Cvičebnice matematiky pro studenty učitelství 1. st. ZŠ a spec. šk. Olomouc: UP. Fuchs, E. et. al. (1998). Standardy a testové úlohy z matematiky pro čtyřletá gymnázia. Praha: Prometheus. Hejný, M., & Stehlíková, N. (1999). Číselné představy dětí. Praha: UK. Hruša, K. (1970). Základy moderní matematiky pro učitele 1.-5. roč. ZDŠ. I. díl. Praha: SPN. Jelínek, M. (1973). Množiny. Praha: SPN. Jelínek, M. (1974). Relace a funkce. Praha: SPN. Kaslová, M. (2010). Předmatematické činnosti v předškolním vzdělávání. Praha: Raabe. Kolláriková, Z., Pupala, B. (eds.) Předškolní a primární pedagogika. Praha: Portál 2001 Lipková, L., & Petřík, J. (2001). Základy elementárnej matematiky. Prešov: PU. Novák, B., et al. (2004). Základy elementární matematiky v úlohách. Olomouc: UP. Novotná, V., et al. (1991). Cvičení z elementární aritmetiky a geometrie. Ostrava: OU. Perný, J. (2010). Kapitoly z elementární aritmetiky I. Liberec: TU. Sciacovelli, G. (1978). Nová matematika. Praha: SPN. Stopenová, A. (2013). Základy matematiky I. Olomouc: UP. Rámcový vzdělávací program pro základní vzdělávání. (2007). Praha: VÚP. Dostupné z http://www.nuv.cz/file/696/