Zadania prémií z predmetu Diskrétna matematika a logika

Prémia 1

Dokážte, že ak A,B,C sú množiny také, že

Math(A\cup B=B\cup C=A\cup C)

a zároveň

Math(A\cap B=B\cap C=A\cap C,) potom platí A=B=C.

Prémia 2

Nájdite systém (množinu množín) Math(\{A\}_{i\in I}) (I je množina indexov) s takýmito vlastnosťami:

1. Pre každú konečnú množinu Math(F\subseteq I) platí, že Math(\big\cap_{i\in F}A_i\not =\emptyset).

2. Math(\big\cap_{i\in I}A_i=\emptyset).

Prémia 3

Dokážte De Morganov zákon

Math((A\cup B)^c=A^c\cap B^c)

pre množiny čisto pomocou rovností uvedených na prednáške.

Prémia 4

Zistite, či je relácia Math(\rho) na Math(\mathbb R^+) daná predpisom

Math(x\rho y:\Leftrightarrow x^y\leq y^x)

antisymetrická a tranzitívna.

Prémia 5

Nech A je nejaká množina, nech Eq(A) je množina všetkých ekvivalencií na A. Zrejme Math((Eq(A),\subseteq)) je poset. Nech Math(\rho,\theta\in Eq(A)).

Dokážte, že množina ekvivalencií

Math((\{\gamma\in Eq(A):\rho,\theta\subseteq\gamma\},\subseteq))

má najmenší prvok a popíšte, ako vyzerá.

Inými slovami: Existuje najmenšia ekvivalencia obsahujúca dve dané ekvivalencie? Charakterizujte ju.