Projekty IB015

Relace

Ve studijním textu k Úvodu do informatiky si můžete osvěžit pojmy binární relace, reflexivity, symetrie, antisymetrie a tranzitivity binární relace a operace jejich uzávěrů, dále operace inverzní relace a skládání relací. Také budete potřebovat vědět, co je ekvivalence, co je uspořádání a co je předuspořádání, spolu s pojmy rozkladu, nejmenšího, minimálního, největšího a maximálního prvku a jádra předuspořádání. Potřebný je také pojem funkce (totální i parciální) z pohledu relací.

Napište program, který načte ze vstupu nosnou množinu (tj. množiny A tak, že všechny dané relace budou podmnožiny A × A) zadanou výčtem, dále pak potřebné relace zadané výčtem a nakonec libovolný z následujících dotazů (na které patřičně odpoví, opět výčtem):

  • je relace R (zadaná dříve ve vstupu) reflexivní (sym., antisym., tranz.)?
  • co je reflexivní (symetrický, tranzitivní, příp. jejich kombinace) uzávěr R?
  • co je R-1?
  • co je R po S?
  • je-li R ekvivalence, co je rozkladem nosné množiny podle R?
  • je-li R uspořádání, co jsou nejmenší, minimální, největší a maximální prvky?
  • je-li R předuspořádání, co je jeho jádrem?
  • je R funkce?

Rovněž umožněte pracovat se sjednocením, průnikem a doplňkem relací. Při výpisu výčtem nezapomeňte, že i relace jsou množiny a tedy je vhodné eliminovat vícenásobné výskyty téže dvojice ve vypisované relaci.

Příklad vstupu (doplněk se značí apostrofem):

A = {a,b,c,d,e,f}
R = {(a,a),(b,b),(c,c),(d,d),(e,e),(f,f)}
S = {(a,b),(b,a)} ∪ {(c,c)}
V = {}'

Tedy A je nosná množina o 6 prvcích, R je identická relace, S je symetrická relace a V je totální relace A × A (je doplňkem prázdné relace). Nyní ukázky některých dotazů a odpovědí:

? refl(R)
True

? V'
{}

? ekviv(S ∪ R)
yes: {a,b},{c},{d},{e},{f}

? func(R)
yes, total

Je na Vás, abyste dobře zvolili potřebné datové typy.

Odhadovaný počet řešitelů: 3.