Relace - s důrazem především na binární

Podstatné je podrobné (hloubkové) pochopení toho, co jsou relace a jak je chápat v praktických ukázkách...

• Zavedení relace jako podmnožiny kartézského součinu. Reprezentace relace výčtem dvojic, tabulkou, maticí, grafem - co v těchto reprezentacích znamenají vlastnosti reflexivní, symetrická, antisymetrická, tranzitivní? Je třeba se soustředit na podrobné pochopení významu zmíněných vlastností a probírat konkrétní příklady těchto reprezentací na malých nosných množinách.
  Které relace s informatickým podtextem by už studenti mohli znát?

• Neformální pochopení reflexivních, symetrických a tranzitivních uzávěrů relací - na úrovni "přidání chybějících šipek" v obrázku relace.

• Probrání definice a "praktických" aspektů skládání relací, názorné zobrazení a tabulky. Inverze binární relace (což bude podrobněji probíráno u inverzí funkcí). Skládání relací je asociativní operací, není to však komutativní operace ani když probíhá nad stejnou nosnou množinou.

Relace ekvivalence

Jestliže je dostatek času, je vhodné již v tomto cvičení začít s relací ekvivalence jako užitečným příkladem (viz Cvičení 5).

Možné příklady k demonstraci vlastností relací

• Pro konkrétní výčet dvojic binární relace, například R={(a,a),(a,b),(a,c),(b,d),(d,a),(e,e),...}, nakreslit graf a zapsat matici této relace. Poté rozhodnout, které z vlastností reflexivní, symetrická, antisymetrická, tranzitivní pro tuto relaci platí a ukázat, co ona vlastnost znamená v konkrétní reprezentaci relace (poznání tranzitivní relace není až tak jednoduché!).
  • R = {(a,g),(b,h),(g,a),(g,h),(h,b),(h,g),(h,h)}
  • R = {(a,a),(b,b),(c,a),(c,c),(c,f),(d,d),(e,e),(f,c),(f,f),(g,g)}
  • R = {(a,a),(a,g),(b,c),(b,d),(c,b),(d,b),(e,f),(f,f),(g,a)}
  • R = {(a,d),(b,b),(c,c),(d,a),(d,d),(e,b),(e,c),(e,e),(e,g),(f,f),(g,e)}
  • R = {(a,g),(b,f),(c,i),(d,f),(d,h),(f,b),(f,d),(g,a),(g,i),(h,d),(i,c),(i,g)}
  • R = {(a,a),(a,b),(a,c),(a,f),(b,b),(c,b),(c,c),(c,f),(d,d),(e,e),(f,b),(f,c),(f,f)}
  • R = {(a,a),(a,b),(a,e),(c,c),(d,a),(d,b),(d,d),(d,e),(d,f),(e,a),(e,b),(e,e),(f,a),(f,b),(f,e)}
  • a nestačí-li předchozí, tak ještě  R = {(b,a),(b,b),(b,c),(b,d),(b,e),(b,f),(c,c),(c,d),(d,c),(d,d),(e,a),(e,b),(e,c),(e,d),(e,e),(e,f),(f,a),(f,b),(f,c),(f,d),(f,e),(f,f)}
• Lze zvolit libovolné další příklady z příslušného odpovědníku v IS, avšak lepší by bylo se podívat také na další ukázky relací, jaké si cvičící vymyslí a hned demonstruje na studentech (například nechť se studenti "shlukují" podle barvy vlasů, místa sezení nebo přibližné výšky). Kdy demonstrované relace budou ekvivalencemi?

• Vyvrátit několik studenty oblíbených bludů jako:
  • relace je symetrická <=> relace není antisymetrická ?
  • dvě relace mají nějakou vlastnost => jejich sjednocení/průnik ji má taky ?
  • relace R je popsána podmínkou typu "A nebo B" a relace popsaná jako "A" je symetrická => celá R je symetrická ?
• Vysvětlit (včetně obrázku), proč inverze složení "S po R" je složením "R^-1 po S^-1".
• Je třeba zdůraznit, že na řešení slovních úloh z odpovědníků (nyní odpovědník pro Lekci 5 a také 6) neexistují žádné "spolehlivé zkratky" - vlastnosti relací nebo jejich složenin se MUSÍ poctivě odvozovat z definic, ostatně to ukazují i předchozí vyvrácené bludy o relacích.

• Ukázky skládání relací, opět pro konkrétní zadání na malé nosné množině - relace R,S zapsané maticí či krátkým výčtem jako R={(a,a),(a,b),(a,c),(b,d),(d,a),(e,e)}, S = {(a,c),(b,h),(c,a),(c,e),(e,b),(e,c),(e,e)} a podobné (viz seznam relací výše). Zde je ještě více potřeba pochopit principy na úplně základních malých příkladech, které by se měly ukázat pomocnými obrázky stejně, jako byly slidy na přednášce.
• Důležitost existence "mezilehlého" prvku při skládání dvou relací, jednak na předchozích malých ukázkách relací a také na obecnějších příkladech ("studenti v posluchárně") jako:
  • Nechť R tvoří ty dvojice studentů (A,B) kde B sedí v řadě s číslem dvakrát vyšším než řada s A, dále S tvoří ty dvojice (A,B) kde A sedí v liché řadě a B v sudé řadě. Proč je složení "S po R" vždy prázdné?
  • R obsahuje ty dvojice (A,B) kde A sedí ve vyšší řadě než B a S obsahuje všechny ty (A,B) kde A sedí v poslední řadě. Opět je složení "S po R" vždy prázdné, proč?
  • Nakonec v R jsou všechny ty dvojice (A,B) kde B sedí v první řadě a v S jsou všechny ty dvojice (A,B) kde A sedí v první řadě. Lze tvrdit, že ve složení "S po R" bude každá dvojice studentů z posluchárny? (Proč ne?) 

Další volitelné příklady (pokud zbývá čas)

• Trochu obtížné, ale pěkné: V posluchárně jsou studenti A a B v relaci (A,B), právě když A sedí v první řadě nebo B sedí v poslední řadě. Dokažte, že je tato relace tranzitivní.
• A další obtížnější námět: Pro které základní množinové operace * platí, že složení relací "S po (P*R)" je totéž, co "S po P" * "S po R"?
  Podívejte se na platnost/neplatnost takových tvrzení v obrázkovém znázornění skládání (šipečkama).

• Pokročilé příklady skládání slovně popsaných relací, kde je třeba ad hoc kombinovat slovní popisy k získání "uchopitelné" definice té složené relace - demonstrováno na konkrétním příkladě z odpovědníku.
  Například určíme vlastnosti složené relace "S po R" kde jsou relace R a S dány následujícími výčty dvojic:
  • (A,B) je v R právě když A sedí ve stejné řadě jako B.
    (A,B) je v S právě když A nesedí ve stejné řadě jako B.
  • (A,B) je v R právě když A sedí ve stejné řadě jako B nebo v některé řadě před ním.
    (A,B) je v S právě když oba sedí ve stejné řadě a B není nalevo od A.
  • (A,B) je v R právě když A sedí ve stejné řadě jako B nalevo od B.
    (A,B) je v S právě když A sedí v některé řadě za B.