%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%% file:      s3.tex                                                        %%%
%%% author:    Tatiana Jajcayová, Ján Komara                                 %%%
%%% email:     Jan.Komara@fmph.uniba.sk                                      %%%
%%% copyright: public domain                                                 %%%
%%% version:   2019/11/02                                                    %%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt,a4paper]{article}

\usepackage[slovak]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{amsmath}
\usepackage{amssymb}

\usepackage{lmodern}
\usepackage{indentfirst}

\renewcommand{\labelenumi}{{\normalfont (\alph{enumi})}}
\renewcommand{\labelenumii}{{\normalfont \roman{enumii}.}}

\newcommand{\nN}{\ensuremath{\mathbb N}}
\newcommand{\nZ}{\ensuremath{\mathbb Z}}
\newcommand{\nR}{\ensuremath{\mathcal R}}
\newcommand{\nL}{\ensuremath{\mathcal L}}
\newcommand{\nP}{\ensuremath{\mathcal P}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{3. domáca úloha z predmetu \\ 1-AIN-160 Matematika (3) ZS 2019/20}

\author{Tatiana Jajcayová \and Ján Komara}

%\date{}
\date{\today}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{1. príklad}

Nech $A = \{1,2,3,4,5,6\}$ a nech $\nR$ je relácia \emph{byť podmnožinou} 
$\subseteq_A$ definovaná na potenčnej množine $\nP(A)$. 
Už vieme, že táto relácia je čiastočné usporiadanie na $\nP(A)$. 

Nech $M = \{\{1\},\{2\},\{2,5\}\}$. Nájdite:
\begin{enumerate}
\item 
Počet horných ohraničení $M$, ktoré obsahujú
\begin{enumerate}
\item 
štyri prvky,
\item 
päť prvkov.
\end{enumerate}
\item 
Počet všetkých horných ohraničení $M$ a počet všetkých dolných ohraničení $M$.
\item $\sup(M)$ a $\inf(M)$.
\item 
Pripomeňme:
\begin{quote}
\emph{Definícia.}
Čiastočne usporiadaná množina $(A, \nR)$ sa nazýva zväz, ak  $\sup(\{x,y\})$ aj
$\inf(\{x,y\})$ existujú v $A$ pre každé $x,y \in A$.
\end{quote}
Je ${(\cal P}(A),{\subseteq_A})$ zväz? (Svoju odpoveď zdôvodnite.)
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 1. príkladu}

Táto časť obsahuje riešenie 1. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{2. príklad}

\begin{enumerate}
\item 
Dokážte, že čiastočne usporiadaná množina $(A,\nR)$ môže mať nanajvýš jeden 
najväčší prvok.
\item 
Uveďte príklad  čiastočne usporiadanej množiny $(A,\nR)$, ktorá má viac ako jeden 
maximálny prvok.
\item 
Použitím Hasseho diagramov identifikujte všetky izomorfné triedy ČUM 
(čiastočne usporiadaných množín) 
s piatimi prvkami, ktoré majú v Hasseho diagrame presne štyri úrovne.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 2. príkladu}

Táto časť obsahuje riešenie 2. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{3. príklad}

Profesor Grimaldi sa chystá na svoju prezentáciu na seminári z Diskrétnej 
matematiky. Ráno sa oblieka a množina $O$ obsahuje kusy šatstva, ktoré si dá na 
seba, aby pri prezentácii vyzeral slušne:
\begin{align*}
O = 
\{&
\text{sako}, 
\text{nohavice}, 
\text{košeľa}, 
\text{topánky}, 
\text{ponožky}, 
\text{spodky}, 
\text{tielko},
\\ &
\text{hodinky}, 
\text{kravata},
\text{okuliare}
\}
.
\end{align*}
Na množine $O$ definujme reláciu čiastočného usporiadania $\nR$ nasledovne:
\begin{quote}
$o_1 \nR o_2$, ak oblečenie $o_1$ si musí  profesor obliecť predtým ako si
oblečie oblečenie $o_2$.
\end{quote}
Napríklad, dvojica 
\(
(\text{košeľa}, \text{kravata}) \in \nR
\), 
lebo kravatu si nemôže uviazať bez toho aby mal na sebe košeľu, ale dvojice 
\(
(\text{košeľa}, \text{ponožky}) \notin \nR
\), 
ani 
\(
(\text{ponožky}, \text{košeľa}) \notin \nR
\),
lebo oblečenie košele a ponožiek je nezávislé a môže to urobiť v akomkoľvek 
poradí.
\begin{enumerate}
\item 
Nakreslite Hasseho diagram čiastočne usporiadanej množiny $(O,\nR)$.
\item 
$(O,\nR)$ nie je lineárne usporiadaná. Prečo?
\item 
Nájdite dve rôzne lineárne usporiadania $\nL_1$ a $\nL_2$ množiny $O$, ktoré 
rešpektujú čiastočné usporiadanie $\nR$ (t. j. $ \nR \subseteq \nL_i$ ) a v 
ktorých si profesor Grimaldi nasadí hodinky ako posledné.
\item 
Koľko je všetkých možných lineárnych usporiadaní $\nL$ množiny $O$, ktoré 
rešpektujú čiastočné usporiadanie $\nR$ a v ktorých si profesor Grimaldi 
nasadí okuliare ako prvé a nasadí hodinky ako posledné.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 3. príkladu}

Táto časť obsahuje riešenie 3. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{4. príklad}

Nech $h : \nR \rightarrow \nZ$ je funkcia definovanú nasledovne:
\begin{quote}
\(
h(x) = \lfloor x \rfloor = \text{najväčšie celé číslo menšie alebo rovné $x$.}
\)
\end{quote}
Nájdite všetky reálne čísla $x$, také, že
\begin{enumerate}
\item
$3 \lfloor x \rfloor =  \lfloor 3x \rfloor$
\item 
$\lfloor 3x \rfloor = 3$
\item 
$\lfloor x + 3 \rfloor = x + 3$
\item
$\lfloor x + 3 \rfloor = \lfloor x \rfloor + 3$
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 4. príkladu}

Táto časť obsahuje riešenie 4. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{5. príklad}

\begin{enumerate}
\item
Dokončite dôkaz z prednášky o obraze množiny vo funkcii, 
teda ukážte, že ak $f : A \rightarrow B$ a $X_1, X_2 \subseteq A$, tak
\[ f(X_1 \cup X_2)= {f(X_1) \cup  f}(X_2). \]
\item
Aký vzťah platí, ak nahradíme zjednotenie prienikom? 
Na príklade ukážte, že tam rovnosť platiť nemusí.
\item
Nech $X \subseteq A$ a $Y \subseteq B$ sú konečné množiny. Nech
\[ |X| = k \qquad |A| = m \qquad |Y| = l \qquad |B| = n. \]
Koľko je zobrazení $f$ z $A$ do $B$ takých, že $f(X) \supseteq Y$?
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 5. príkladu}

Táto časť obsahuje riešenie 5. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{6. bonusový príklad (2 extra body + fun)}

\emph{Ackermanova funkcia} $A: \nN \times \nN \rightarrow \nN$ 
sa dá rekurzívne definovať takto:
\begin{align*}
A(0, n) & = n + 1 && \text{ak $n \geq 0$}
\\
A(m, 0) & = A(m - 1, 1) && \text{ak $m > 0$}
\\
A(m, n) & = A(m - 1, A(m, n - 1)) && \text{ak $m, n > 0$.}
\end{align*}
(Ackermanova funkcia je dôležitá v informatike a v teórii rekurzívnych funkcií. 
Jej hodnoty rastú veľmi rýchlo aj pre malé vstupy. 
Napríklad $A(4, 2)$ je celé číslo s 19 729 číslicami v dekadickom zápise.)
\begin{enumerate}
\item 
Vyrátajte  $A(1, 3)$ a  $A(2, 3)$.
\item 
Dokážte, že $A(1, n) = n + 2$ pre všetky $n \in \nN$.
\item 
Ukážte, že $A(2, n) = 3 + 2n$ pre všetky $n \in \nN$.
\item 
Overte, že $A(3, n) = 2^{n + 3} - 3$ pre všetky $n \in \nN$.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 6. príkladu}

Táto časť obsahuje riešenie 6. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
