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\}_{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 poset ekvivalencií

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

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

Inými slovami: existuje vždy najmenšia ekvivalencia obsahujúca nejaké dve dané ekvivalencie? Charakterizujte ju.

Prémia 6

Dokážte, že pre každú podgrupu {$ H $} grupy {$ (Z,+) $} existuje {$ k\in\mathbb N $} také, že {$ H=k.\mathbb Z $}, kde

{$ k.\mathbb Z=\{k.x:x\in\mathbb Z\} $}

Prémia 7

Napíšte Turingov stroj, ktorý pri vstupe {$a^{n$} dá na výstupe {$a}{k_1}ba^{{k_2}b\dots ba}{k_l}b$}, kde {$k_1,\dots,k_l$} sú všetky delitele {$n$}.

Prémia 8

Nakreslite graf, ktorý má práve 5 automorfizmov. Musíte aj dokázať, že ich je práve 5.