Průvodce IB000 Matematické základy informatiky
Cvičení 2b: Množinový kalkul, posloupnosti
Obecná náplň cvičení
Množiny a množiny...
- Množinový kalkul, Vennovy diagramy, jednoduché ukázky a identity. Například: distributivita průniku vůči sjednocení i naopak; konkrétní protipříklad, proč rozdíl není asociativní; důkaz asociativity symetrického rozdílu.
- Pochopení chování symetrického rozdílu si vůbec zaslouží zvláštní pozornost i na více množinách; jak lze třeba zjednodušit výraz (A∪B)Δ(B∪C)Δ(C∪D) bez použití symetrického rozdílu? Jak zjednodušit výraz (AΔB)∩(BΔC)∩(CΔD)∩(DΔA)?
- Je dobré si znovu probrat definici uspořádané dvojice z přednášky - jak se chová a jak snadno dokázat, že rovnost dvojic znamená rovnost po složkách? (nezapomeňte v tom případ (x,x)!).
- Rekurentní posloupnosti, konkrétní ukázky, odhad řešení a využití indukce k důkazu správnosti řešení - pro náměty viz cvičení 2a nahoře.
Tato druhá část cvičení je poměrně jednoduchá a množinový kalkul obvykle nečiní potíže, až na symetrický rozdíl. Je dobré si všimnout a spojit příklady rekurentních posloupností s důkazy matematickou indukcí (které se výhodně používají k ověření vlastností či předpisů pro takto zadané posloupnosti) - viz cvičení 2a.
Upozornění k diagramům
- Pokud se Vennovy diagramy mají používat k důkazům množinových identit, je to v zásadě možné (s patřičným komentářem). Avšak není formálně možné je jednoduše využít vyvrácení množinového vztahu - u vyvrácení vztahu je třeba vždy podat konkrétní protipříklad volby množin, pro které vztah neplatí. Pouhý vybarvený diagram nestačí - proč?