Midtermový príklad zo ZDM - help me

answered Nov 15 '14

Viktor Chlumský
765 ●14 ●24

Správná odpověd je pouze d.

Proč? Tak nejdřív můžu ukázat protipříklady pro a, b, c:

$A = \{ 1, 2, 3, 4 \}$

$B = \{ 1, 2 \}$

a) $f(\{ 1 \}) = f(\{ 2 \}) = B$

b) $f(\{ 3 \}) = f(\{ 4 \}) = \emptyset$

c) $f(\{ 1 \}) = f(\{ 2 \}) = \emptyset$

Když dám do funkce dvě různé podmnožiny, vyjde tatáž podmnožina, a tudíž to není prosté zobrazení.

U možnosti d) protipříklad nenajdu, ale to samo o sobě nedokazuje, že to platí. Korektní matematický důkaz teď vymýšlet nebudu, ale já jsem si to představil například tak, že pokud by podmnožiny byly reprezentované jako bitové vektory, kde by jednotlivé bity označovaly, zda příslušná položka z A v podmnožině je nebo ne, pak to poslední zobrazení vlastně odpovídá funkci XOR (s podmnožinou B), a je známo, že operaci XOR jde vrátit (pokud to zxoruju s tím samým znova), takže musí být prostá, protože kdyby mi pro 2 různé vstupy vyšlo totéž, podle výsledku už by nešlo rozeznat, která ze 2 možností byla na začátku.

Snad je tahle úvaha trochu pochopitelná.