\documentclass[a4paper,12pt]{article}
%%\pagestyle{empty}

\usepackage[left=15mm,right=20mm,top=15mm,bottom=22mm]{geometry}
\usepackage{booktabs, multicol, hvfloat}
\usepackage{makeidx, graphicx, amsmath, amssymb, amsthm, ae}
\usepackage[bosnian]{babel}
%%\usepackage[cp1250]{inputenc}
\usepackage{mathtools} %xarrow


\usepackage{kbordermatrix}% http://www.hss.caltech.edu/~kcb/TeX/kbordermatrix.sty


\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}


\usepackage{pgfplots}
\pgfplotsset{compat=1.15}
\usepackage{mathrsfs}
\usetikzlibrary{arrows}
\usetikzlibrary{decorations.pathreplacing,decorations.markings} %%%for arrows

\usepackage{enumitem}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% for arrows in directed graph
\tikzset{
  % style to apply some styles to each segment of a path
  on each segment/.style={
    decorate,
    decoration={
      show path construction,
      moveto code={},
      lineto code={
        \path [#1]
        (\tikzinputsegmentfirst) -- (\tikzinputsegmentlast);
      },
      curveto code={
        \path [#1] (\tikzinputsegmentfirst)
        .. controls
        (\tikzinputsegmentsupporta) and (\tikzinputsegmentsupportb)
        ..
        (\tikzinputsegmentlast);
      },
      closepath code={
        \path [#1]
        (\tikzinputsegmentfirst) -- (\tikzinputsegmentlast);
      },
    },
  },
  % style to add an arrow in the middle of a path
  mid arrow/.style={postaction={decorate,decoration={
        markings,
        mark=at position .5 with {\arrow[#1]{stealth}}
      }}},
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\def\cm{{\mbox{\rm cm}}}
\def\Inn{{\mbox{\rm Inn}}}

\def\Ra{\Rightarrow}

\def\Sym{{\mbox{\rm Sym}}}
\def\RotSym{{\mbox{\rm RotSym}}}
\def\lcm{{\mbox{\rm lcm}}}
\def\id{{\mbox{\rm id}}}

\def\NN{{\mbox{$\mathbb N$}}}
\def\RR{{\mbox{$\mathbb R$}}}
\def\QQ{{\mbox{$\mathbb Q$}}}
\def\ZZ{{\mbox{$\mathbb Z$}}}
\def\T{{\mbox{$\mathbb T$}}}
\def\H{{\mbox{$\mathbb H$}}}
\def\Q{{\mbox{$\mathbb Q$}}}
\def\F{{\mbox{$\mathbb F$}}}
\def\C{{\mbox{$\mathbb C$}}}
\def\E{{\mbox{$\mathcal{E}$}}}
\def\I{{\mbox{$\mathcal{I}$}}}
\def\M{{\mbox{$\mathcal{M}$}}}

\def\S{{\mbox{$\mathcal{S}$}}}
\def\L{{\mbox{$\mathcal{L}$}}}
\def\G{{\mbox{$\mathcal{G}$}}}
\def\P{{\mbox{$\mathcal{P}$}}}

\def\B{{\mbox{$\mathcal{B}$}}}
\def\A{{\mbox{$\mathcal{A}$}}}
\def\O{{\mbox{$\mathcal{O}$}}}

\def\X{{\mbox{$\mathcal{X}$}}}
\def\V{{\mbox{$\mathcal{V}$}}}
\def\Y{{\mbox{$\mathcal{Y}$}}}
\def\W{{\mbox{$\mathcal{W}$}}}
\def\dist{{\mbox{\rm dist}}}
\def\GL{{\mbox{\rm GL}}}
\def\SL{{\mbox{\rm SL}}}
\def\NSD{{\mbox{\rm gcd}}}

\def\exc{{\mbox{\rm exc}}}
\def\ecc{{\mbox{\rm ecc}}}
\def\max{{\mbox{\rm max}}}
\def\Alt{{\mbox{\rm Alt}}}
\def\Aut{{\mbox{\rm Aut}}}
\def\Hom{{\mbox{\rm Hom}}}
\def\spec{{\mbox{\rm spec}}}
\def\rank{{\mbox{\rm rank}}}
\def\rang{{\mbox{\rm rang}}}
\def\mod{{\mbox{\rm mod}}}
\def\div{{\mbox{\rm div}}}
\def\trag{{\mbox{\rm trag}}}
\def\tr{{\mbox{\rm tr}}}
\def\dim{{\mbox{\rm dim}}}
\def\diag{{\mbox{\rm diag}}}
\def\Mat{{\mbox{\rm Mat}}}
\def\Sim{{\mbox{\rm Sim}}}
\def\ker{{\mbox{\rm ker}}}
\def\im{{\mbox{\rm im}}}
\def\mp{{\mbox{\rm mp}}}
\def\gcd{{\mbox{\rm gcd}}}

\def\K{{\mbox{$\pmb{K}$}}}
\def\J{{\mbox{$\pmb{J}$}}}



\def\j{{\mbox{$\pmb{j}$}}}

\def\0{{\mbox{\boldmath{$0$}}}}
\def\algmult{{\mbox{\rm alg\,mult}}}
\def\geomult{{\mbox{\rm geo\,mult}}}
\def\du{{\mbox{\rm \,d$u$}}}
\def\dx{{\mbox{\rm \,d$x$}}}
\def\dt{{\mbox{\rm \,d$t$}}}
\def\dy{{\mbox{\rm \,d$y$}}}
\def\dz{{\mbox{\rm \,d$z$}}}
\def\tg{{\mbox{\rm tg\,}}}
\def\arctg{{\mbox{\rm arc\,tg\,}}}
\def\arcsin{{\mbox{\rm arc\,sin\,}}}
\def\ctg{{\mbox{\rm ctg\,}}}

\def\a{{\mbox{\boldmath $a$}}}
\def\q{{\mbox{\boldmath $q$}}}
\def\b{{\mbox{\boldmath $b$}}}
\def\j{\mbox{\boldmath $j$}}
%%\def\u{{\mbox {\boldmath $u$}}}
\def\m{{\mbox {\boldmath $m$}}}
\def\n{{\mbox {\boldmath $n$}}}
\def\vv{{\mbox {\boldmath $v$}}}
\def\w{{\mbox {\boldmath $w$}}}
\def\x{\mbox{\boldmath $x$}}
\def\h{{\mbox {\boldmath $h$}}}
\def\y{\mbox{\boldmath $y$}}
\def\0{\mbox{\boldmath $0$}}
\def\z{\mbox{\boldmath $z$}}
\def\p{\mbox{\boldmath $p$}}
\def\l{\mbox{$\lambda$}}

\def\e{{\mbox{\boldmath $e$}}}
\def\ro{{\mbox{\boldmath $\rho$}}}



\newcommand{\ol}{\overline}
\newcommand{\Llra}{\Longleftrightarrow}
\newcommand{\Lra}{\Leftrightarrow}
\newcommand{\ra}{\rightarrow}
\newcommand{\LRa}{\Leftrightarrow}
\newcommand{\ora}{\overrightarrow}

\newcommand{\ds}{\displaystyle}



\DeclareMathOperator{\D}{{\cal D}}
\DeclareMathOperator{\Z}{{\cal Z}}
\DeclareMathOperator{\PP}{{\mathbb P}}





\newtheoremstyle{zaFiguru} %name
  {4.4mm}    %Space above, empty = `usual value'
  {4.5mm}    %Space below
  {\rm}   %Body font
  {}     %Indent amount (empty = no indent, \parindent = para indent)
  {\bf}   %Thm head font
  {}      %Punctuation after thm head
  {2mm}   %Space after thm head: \newline = linebreak
  {\thmname{#1} \thmnumber{{\Large #2.}}\thmnote{\,(#3)}}       %Thm head spec  

  
  
 

%%\swapnumbers
\theoremstyle{zaFiguru}
\newtheorem{zad}{}


\def\ug{{{\measuredangle}}}
\def\tr{{{\triangle}}}


\setlength{\textheight}{262mm}
\setlength{\textwidth}{180mm}
\begin{document}
\allowdisplaybreaks


\raggedright
\section{Mathematical Logic}

\begin{zad}
On a very special island, there are two types of people: knights and knaves. Knights always tell the truth, while knaves always lie. On the island, we encounter two inhabitants, Tom and Peter.
\begin{enumerate}[label=\rm~]
\item Peter says: "Tom is a knave."
\item Tom says: "We are both knights."
\end{enumerate}
What can we deduce about Peter?
\end{zad}

\begin{zad}
On a very special island, there are two types of people: knights and knaves. Knights always tell the truth, while knaves always lie. We listen to a conversation between two islanders, Zig and Zan.
\begin{enumerate}[label=\rm~]
\item Zig: "It is not true that Zan is a knave."
\item Zan: "Zig and I are not the same type."
\end{enumerate}
Who is a knight and who is a knave?
\end{zad}

\begin{zad}[{exam, November 2021}]
On a very special island, there are two types of people: knights and knaves. Knights always tell the truth, while knaves always lie. On the island, we meet two inhabitants, Blaž and Luka.
\begin{enumerate}[label=\rm~]
\item Blaž says: "Luka is a knight."
\item Luka says: "We are both knights."
\end{enumerate}
What is Blaž?
\end{zad}

\begin{zad}
Exactly one of the chests labeled $A$, $B$, $C$, and $D$ contains gold, and exactly one of the following statements is true. In which chest is the gold?
\begin{enumerate}
\item[$A$:] The gold is here.
\item[$B$:] The gold is in $A$ or $D$.
\item[$C$:] The gold is not here.
\item[$D$:] The gold is here.
\end{enumerate}
\end{zad}

\begin{zad}
Knights always tell the truth, while knaves always lie. Andrej, Bine, and Cene are either knights or knaves. Determine who is a knight and who is a knave based on the following statements:
\begin{enumerate}[leftmargin=1.6cm]
\item[Andrej:] "Bine is a knave, and Cene is a knight."
\item[Bine:] "If Andrej is a knave, then Cene is also a knave."
\item[Cene:] "I am not a knave, but at least one of the others is a knave."
\end{enumerate}
\end{zad}

\begin{zad}
On a very special island, there are two types of people: knights and knaves. Knights always tell the truth, while knaves always lie.

Today is dance day on the island, which means people are standing in circles, holding hands, and dancing. It is a time of joy, and it is especially difficult to distinguish knights from knaves.

Four individuals, namely Nika, Mikhail, Leon, and Timotej (in cyclic order), are holding hands in a circle. It appears that each of them says:
\begin{enumerate}[label=\rm~]
\item "I am in contact with exactly one knight!"
\end{enumerate}

Is this possible? If so, find at least one arrangement of knights and knaves among the four individuals. Can you find a solution where Mikhail is a knave? Find all solutions!
\end{zad}

\begin{zad}
Assume that the following statements are true:
\begin{enumerate}[label=$\bullet$]
\item Pinocchio always lies;
\item Pinocchio says: "All my hats are green."
\end{enumerate}
Can we deduce that any of the following statements is true?
\begin{enumerate}
\item[$A$:] Pinocchio has exactly one hat, which is green.
\item[$B$:] Pinocchio has at least one green hat.
\item[$C$:] Pinocchio has no green hats.
\end{enumerate}
\end{zad}








\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}










\newpage
\section{Logical Equivalences and Selected Forms of Statements}

\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item Express the compound statement $A\vee B$ using only the basic connectives $\neg$ and $\wedge$.
\item 
\hvFloat[floatPos=!htb,capPos=before,onlyText=true,]{} 
{
\begin{tabular}{ c|c|c } 
 $p$ & $q$ & $C$ \\ 
\hline
 0 & 0 & 1 \\ 
 0 & 1 & 1 \\ 
 1 & 0 & 0 \\ 
 1 & 1 & 1 \\ 
\end{tabular}
}
{
Suppose we have the table on the right. Find $C$.
}{fg}
\end{enumerate}
\end{zad}

\begin{zad}
The following compound statement is given:
$$
(\neg p \land \neg q) \lor \neg(q\land r).
$$
Construct a truth table.
\end{zad}

\begin{zad}
Is the following reasoning correct?
\begin{enumerate}[label=$\bullet$]
\item I think, therefore I am. I think, therefore I reason. Conclusion: I am, therefore I reason.
\end{enumerate}
\end{zad}

\begin{zad}[{exam, November 2021}]
The following compound statement is given:
$$
(A\Ra B) \land (B\Ra C).
$$
\begin{enumerate}[label=\rm(\alph*)]
\item Construct a truth table.
\item What can be said about the truth of statements $B$ and $C$ if the compound statement is true and $A$ is a true statement?
\item Write the {\bf negation} of the given compound statement in disjunctive form.
\end{enumerate}
\end{zad}

\begin{zad}
The following compound statement is given:
$$
(\neg A\lor B) \Lra (C\Ra A).
$$
\begin{enumerate}[label=\rm(\alph*)]
\item Construct a truth table.
\item What can be said about the truth of statements $A$ and $C$ if the compound statement is false and $B$ is true?
\item Write the negation of the given compound statement in disjunctive form.
\end{enumerate}
\end{zad}

\begin{zad}
For the given compound statement, construct a truth table and determine its conjunctive and disjunctive normal forms:
$$
(A\lor B)\land (\neg A\lor C)\Lra\neg (B\Ra\neg C).
$$
\end{zad}

\begin{zad}
For the following compound statement, provide the truth table, and determine the conjunctive and disjunctive normal forms:
$$
(A \Ra (B \Ra C)) \Ra ((A \Ra B) \Ra (A \Ra C))
$$
\end{zad}

\begin{zad}
The following compound statement is given:
\begin{equation}
\label{vn}
\neg A \land (A\Lra B) \Ra \neg B.
\end{equation}
What can be said about the truth of implication \eqref{vn}? 
In other words, is the statement true for all assignments, or is there an assignment for which the statement is false? Provide the solution in two different ways:
\begin{enumerate}[label=\rm(\roman*)]
\item Using a truth table.
\item Without using a truth table.
\end{enumerate}
\end{zad}

\begin{zad}
Determine the compound statement $\mathcal{I}$ such that $$(A\Rightarrow (\mathcal{I} \Rightarrow \neg B))\Rightarrow (A\wedge B) \vee \mathcal{I}$$
is a tautology.
\end{zad}













\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}










\newpage
\section{Methods of Proof}

\begin{zad}
Show that if $n$ is an integer and $3n+2$ is an odd number, then $n$ is an odd number.
\end{zad}

\begin{zad}
Prove by contradiction that the number $\log_{\sqrt{2}}{3}$ is irrational.
\end{zad}

\begin{zad}
Show that if $n$ is an even number, then $n^2 +3n$ is even.\\
Is the converse true?
\end{zad}

\begin{zad}
Let $n$ be an integer $(n\in\ZZ)$. Prove that $n^2\ge n$.
\end{zad}

\begin{zad}
Let $x$ and $y$ be real numbers such that $x<2y$. Prove the following implication:
\begin{center}
If $7xy\leq 3x^2 + 2y^2$, then $3x\leq y$.
\end{center}
\end{zad}

\begin{zad}
Show that if $n$ is an odd integer and $m$ is an even integer, then $n^2+3n+nm+1$ is an odd number. Explain each step of your proof!
\end{zad}

\begin{zad}[{exam, November 2021}]
Show that if $3nm+n+m$ is an even number, then both $n$ and $m$ are even numbers.
\end{zad}

\begin{zad}
Consider the statement:
$$
\text{If $x$ and $y$ are odd integers, then their product $xy$ is also an odd integer.}
$$
\begin{enumerate}[label=\rm(\roman*)]
\item Provide a direct proof of the above implication.
\item Provide a proof by contradiction of the above implication.
\end{enumerate}
\end{zad}

\begin{zad}
The reciprocal of a positive real number $x$ is $\frac{1}{x}$. Consider the statement:
\begin{enumerate}[label=$\bullet$]
\item If a real number $x$ is positive, then the sum of $x$ and its reciprocal is greater than or equal to $2$.
\end{enumerate}
\begin{enumerate}[label=\rm(\roman*)]
\item Provide a direct proof of the above implication.
\item Provide a proof by contradiction of the above implication.
\end{enumerate}
\end{zad}













\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}










\newpage
\section{Statements with Predicates and Quantifiers}

\begin{zad}
Which of the following statements are true, assuming the domain of discourse is the set of real numbers?
\begin{enumerate}[label=\rm(\roman*)]
\item $(\forall x)(\exists y)(x+y=0)$.
\item $(\exists x)(\forall y)(x+y=0)$.
\item $(\exists x)(\exists y)(x^2+y^2 =-1)$.
\item $(\forall x)[x>0 \Rightarrow (\exists y)(y<0 \wedge xy>0)]$.
\end{enumerate}
\end{zad}

\begin{zad}
\begin{enumerate}[label=\rm(\roman*)]
\item Express the compound statement $A\Lra B$ using only the basic connectives $\neg$ and $\wedge$.
\item Recall that $(\exists ! x)(x\in\RR\wedge \varphi(x))$ is read as ``There exists exactly one $x$ in $\RR$ such that $\varphi(x)$ holds''. Rewrite the following statement
$$
(\exists !a)(a\in\RR\land a>3\land a\le 4)
$$
without using the shorthand `$\exists !$'—that is, instead of using the quantifier $\exists !$, use the quantifiers $\exists$ and $\forall$. Determine the truth value of the given statement.
\end{enumerate}
\end{zad}

\bigskip
\bigskip

\hvFloat[floatPos=!htb,capPos=before,onlyText=true,]{}
{
\begin{tabular}{ c|c|c|c } 
 $p$ & $q$ & $r$ & $D$ \\ 
\hline
 1 & 1 & 1 & 0 \\ 
 1 & 1 & 0 & 0 \\ 
 1 & 0 & 1 & 0 \\ 
 1 & 0 & 0 & 1 \\ 
 0 & 1 & 1 & 0 \\ 
 0 & 1 & 0 & 1 \\ 
 0 & 0 & 1 & 1 \\ 
 0 & 0 & 0 & 0 \\
\end{tabular}
}
{
\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item Given the table on the right, find $D$.
\item The law of trichotomy states: ``For every pair of real numbers $a$, $b$, exactly one of the following is true: $a = b$, $a < b$, or $a > b$''.
\smallskip
Write the law of trichotomy using quantifiers and connectives ($\forall,\exists,\land,\lor,\neg,\Ra$).
\end{enumerate}
\end{zad}
}{fg}

\begin{zad}
The set $A$ is defined as follows:
$$
A=\{n\in\NN \mid n \text{ is an odd number } \land (\exists k)\big(k\in\NN \land n = k(k + 1)\big)\}.
$$
Show that $A$ is an empty set.
\end{zad}

\begin{zad}
Negate the following statement with quantifiers:
$$
(\forall a)(\forall b)((a^2 + b^2 = 0) \Rightarrow (a = 0) \vee (b= 0)).
$$
Determine whether the negation is a true statement.
\end{zad}

\begin{zad}
Express the following statement with quantifiers and prove it: There does not exist an odd number that can be expressed in the form $4j +1$ and $4k -1$ for integers $j$ and $k$.
\end{zad}













\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}










\newpage
\section{Sets. Union, Intersection, and Set Difference}

\begin{zad}
Let $A = \{1, 2, 5, 6, 7, 10, 11, 12\}$, $B = \{x \mid x \text{ is an odd integer and } 3\le x\le 10\}$, and $C = \{a, b, c, 4, 5, 6\}$.
\begin{enumerate}[label=\rm(\alph*)]
\item Fill in the blanks $\,\_\!\_\!\_\,$ with the most appropriate symbol $(\in,\notin,\subseteq,\not\subseteq)$:\newline
$7\,\_\!\_\!\_\,A$, $6\,\_\!\_\!\_\,B$, $10\,\_\!\_\!\_\,B$, $4\,\_\!\_\!\_\,A$, $b\,\_\!\_\!\_\,C$, $b\,\_\!\_\!\_\,B$, $\{2, 5, 12\}\,\_\!\_\!\_\,A$, $\{3, 5, 6\}\,\_\!\_\!\_\,B$, $\{a, b, 5\}\,\_\!\_\!\_\,C$.
\item Calculate $A\cup B$, $A\setminus B$, $\P(A\cap B)$, $(A\cap B) \times \{a, b\}$.
\end{enumerate}
\end{zad}

\begin{zad}
Let $A = \{2n - 1: n\in\ZZ\}$ be the set of all odd integers and let $B = \{(2n-1)^3 : n\in\ZZ\}$ be the set of all cubes of odd integers. Show that $B\subseteq A$.
\end{zad}

\begin{zad}
\begin{enumerate}[label=\rm(\roman*)]
\item Show that for any sets $A$, $B$, and $C$, the following holds:
$$
A\subseteq C  \wedge B\subseteq C \Rightarrow A\cup B\subseteq C.
$$
\item Determine the following sets:
\begin{enumerate}[label=$\bullet$]
\item $\{\emptyset, \{\emptyset\}\}\setminus \emptyset$.
\item $\{\emptyset, \{\emptyset\}\}\setminus \{\emptyset\}$.
\item $\{\emptyset, \{\emptyset\}\}\setminus \{\{\emptyset\}\}$.
\end{enumerate}
\end{enumerate}
\end{zad}

\begin{zad}
Find all sets $A, B, C$ such that $$B \setminus A = A \cup C = C \cap B = \{ 1 \}.$$
\end{zad}

\begin{zad}
Is the following statement true for any sets $A$, $B$, and $C$:
$$
\text{If $A\cap B\subseteq \overline{C}$ and $A\cup C \subseteq B$, then $A\cap C = \emptyset$.}
$$
\end{zad}

\begin{zad}
Justify whether the following statement holds for any sets $A$, $B$, and $C$:
$$
A\cap B=A\cap C \Rightarrow B=C.
$$
\end{zad}

\begin{zad}
Let $A$ and $B$ be arbitrary sets. Prove that:
$$
(A \cap B) \cup (B \setminus A) = B.
$$
\end{zad}

\begin{zad}
Let $X$ and $Y$ be subsets of a universal set $U$. Show that
$$
(X\cup Y)^c=X^c\cap Y^c.
$$
\end{zad}

\begin{zad}[{exam, November 2021.}]
\begin{enumerate}[label=\rm(\alph*)]
\item Let $A$ and $B$ be given sets. Show that $A\cap (B\setminus A)=\emptyset$. Explain each step of your proof.
\item Let $A$ and $B$ be subsets of a universal set $U$. Show that $A\subseteq B$ if and only if $\overline{B}\subseteq\overline{A}$. Explain each step of your proof.
\end{enumerate}
\end{zad}

\begin{zad}
Justify whether the following statement holds for any sets $A$, $B$, and $C$:
$$
(A\cup B)\cap(A\cup C)\subseteq \overline{A}\cup C.
$$
Explain each step of your proof.
\end{zad}

\begin{zad}
Let $A$, $B$, and $C$ be arbitrary sets. Prove that
$$
A\setminus (B\cap C) = (A\setminus B)\cup (A\setminus C).
$$
\end{zad}

\begin{zad}
Show that for any sets $A$, $B$, and $C$, the following holds:
$$
(A\cap B)\setminus C = (A\setminus C)\cap (B\setminus C).
$$
\end{zad}











\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}










\newpage
\section{Power Set}

\begin{zad}
Let $S=\{1,2,3\}$. Which of the following statements are true (if any exist)? For each statement, explain why it is true or false.
\begin{enumerate}[label=\rm(\alph*)]
\item $S\subseteq\P(S)$. 
\item $\P(S)\subseteq S$. 
\item $S\in\P(S)$. 
\item $(\forall x)(x \in S \Rightarrow x \in \P(S))$. 
\item $(\exists x)(x \in S \Rightarrow x \in \P(S))$.
\end{enumerate}
\end{zad}

\begin{zad}
Justify whether the following statement holds for any sets $A$ and $B$:
$$
A\subseteq B \Rightarrow \P(A)\subseteq\P(B).
$$
\end{zad}

\begin{zad}
Does $\mathcal{P}(A\times B) = \mathcal{P}(A) \times \mathcal{P}(B)$ hold? Provide a detailed justification.
\end{zad}

\begin{zad}
Justify whether the following statement is true or false:
\begin{enumerate}[label=\rm~]
\item If $\P(X)=\P(Y)$ for sets $X$ and $Y$, then $X$ and $Y$ are equal.
\end{enumerate}
\end{zad}

\begin{zad}
Let $A$ be a non-empty set. Determine which of the sets $$\emptyset,\{\emptyset\}, A, \{A\}, \{A,\emptyset\}$$ are elements of and which are subsets of the sets $\mathcal{P}(A)$ and $\mathcal{P}(\mathcal{P}(A))$.
\end{zad}






\section{Cartesian Product of Sets}

\begin{zad}
Does $\mathcal{P}(A\times B) = \mathcal{P}(A) \times \mathcal{P}(B)$ hold? Provide a detailed justification.
\end{zad}

\begin{zad}
Justify whether the following statement holds for any sets $A$, $B$, and $C$:
\begin{equation}
\label{zi}
A\times (B\cup C)= (A\times B)\cup (A\times C).
\end{equation}
\end{zad}








\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}










\newpage
\section{Relations}

\begin{zad}
Relations can be presented explicitly by listing all ordered pairs they consist of. For example, for $A = \{1, 2, 3, 4\}$, one possible relation on $A$ is:
$$
R = \{(1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4)\}.
$$
\begin{enumerate}[label=\rm(\roman*)]
\item Write the implicit form of the relation $R$. (What conditions must hold for $x \in A$ to be related to $y \in A$ under $R$?)
\item Is $R$ a reflexive relation?
\item Is $R$ a symmetric relation?
\item Is $R$ a transitive relation?
\end{enumerate}
\end{zad}

\begin{zad}[1st Exam, November 2021.]
On the power set $\P(M)$ of the set $M = \{1, 2\}$, we introduce a relation $R$ defined by:
$$
ARB \qquad \Longleftrightarrow \qquad
A\cup\{1\}=B\cup\{2\}.
$$
List all ordered pairs in $R$.
\end{zad}

\begin{zad}
Let $A=\{4,5,6,7,8\}$ with the following relation:
$$
R=\{(a,b)\in A\times A\mid b=a+2\}.
$$
\begin{enumerate}[label=\rm(\alph*)]
\item List all ordered pairs in $R$.
\item Is the relation $R$ transitive?
\item Is the relation $R$ antisymmetric?
\item Represent the relation with a $0-1$ matrix (label rows and columns with elements of the set $A$ to indicate which element of $A$ represents each row and column).
\end{enumerate}
\end{zad}

\begin{zad}
On the set of natural numbers $\NN$, we define a relation $\!\not|$:
$$
a\!\not| b 
\qquad\Longleftrightarrow\qquad
\mbox{$a$ does not divide $b$ (i.e., } \exists q,r\in\NN : b=aq+r
\land 1\le r< a).
$$
\begin{enumerate}[label=\rm(\alph*)]
\item List at least five elements of the relation $\!\not|$.
\item Is the relation $\!\not|$ reflexive?
\item Is the relation $\!\not|$ symmetric?
\item Is the relation $\!\not|$ antisymmetric?
\item Is the relation $\!\not|$ transitive?
\item Let $A=\{4,5,6,7,8\}$. Represent the relation $\!\not|$ on the set $A$ using a $0-1$ matrix (label rows and columns with elements of the set $A$).
\end{enumerate}
\end{zad}

\begin{zad}
Let $\ZZ$ be the set of integers. We have the following relation: 
$$
R=\{(a,b)\in \ZZ\times\ZZ \mid 5\mbox{ divides } a^3-b^3\}.
$$
\begin{enumerate}[label=\rm(\alph*)]
\item List at least five elements of the relation $R$.
\item Is the relation $R$ reflexive?
\item Is the relation $R$ symmetric?
\item Is the relation $R$ transitive?
\end{enumerate}
\end{zad}

\begin{zad}
On the set $A = \{1, 2,\ldots, 18\}$, we define a relation $R$:
$$
xRy
\qquad\Lra\qquad
y-x \mbox{ is a prime number.}
$$
\begin{enumerate}[label=\rm(\alph*)]
\item Determine the domain and range of the relation $R$.
\item Find the set $\{y\in A \mid 10Ry\}$.
\item Is the relation $R$ symmetric?
\item Is the relation $R$ transitive?
\end{enumerate}
\end{zad}














\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}










\newpage
\section{Equivalence Relation and Equivalence Class}

\begin{zad}[{2nd Exam, January 2022.}]
On the set of integers $\ZZ$, we define a relation $R$:
$$
aRb\qquad\Lra\qquad a=b\mbox{ or } a=-b.
$$
Show that $R$ is an equivalence relation and determine the equivalence classes.
\end{zad}

\begin{zad}
On the set of real numbers $\RR$, we define a relation $\sim$:
$$
x\sim y
\qquad\Lra\qquad 
\mbox{$x$ and $y$ are both positive, or both negative, or both zero.}
$$
Show that $\sim$ is an equivalence relation, determine the equivalence classes, and find the quotient set $\RR/_\sim$.
\end{zad}

\begin{zad}
On the set $S=\left\{\ds\frac{a}{b}\mid a,b\in\ZZ,b\ne 0\right\}$, we define a relation $\sim$:
$$
\frac{a}{b}\sim \frac{c}{d} 
\qquad\Lra\qquad 
ad=bc.
$$
Justify whether $\sim$ is an equivalence relation. If $\sim$ is an equivalence relation, find the equivalence classes $[\frac{2}{5}]_\sim$ and $[7]_\sim$, and explain the meaning of the quotient set $S/_\sim$.
\end{zad}

\begin{zad}
On the set of natural numbers $\NN$, we define a relation $R$:
$$
xRy \qquad\Llra\qquad
4 \mbox{ divides } x+3y.
$$
Show that $R$ is an equivalence relation and determine the equivalence classes.
\end{zad}

\begin{zad}
Let $S = \ZZ$. On the set $S$, we define a relation $R$ by:
$$
aRb \quad\Llra\quad 4 \mbox{ divides } a^2-b^2.
$$
\begin{enumerate}[label=\rm(\alph*)]
\item Show that $R$ is an equivalence relation on the set $S$.
\item Find the equivalence classes of the relation $R$.
\end{enumerate}
\end{zad}

\begin{zad}
On the set of real numbers $\RR$, we define a relation $\sim$:
$$
a\sim b\qquad\Lra\qquad a-b\in\ZZ.
$$
Justify whether $\sim$ is an equivalence relation. If $\sim$ is an equivalence relation, find the equivalence classes $[\frac{1}{2}]_\sim$ and $[\sqrt{2}]_\sim$.
\end{zad}

\begin{zad}
Let $E$ be the set of 4-bit binary strings:
$$
E=\{0000, 0001, 0010, 0011, \ldots, 1110, 1111\}.
$$
On $E$, we define a relation $R$ by:
$$
xRy
\qquad\Lra\qquad 
\mbox{$x$ and $y$ have the same number of 1s.}
$$
Show that $R$ is an equivalence relation and determine the equivalence classes. Provide a detailed justification of your answer.
\end{zad}

\begin{zad}[Theoretical Problem]
Let $S$ be a given nonempty set, $\sim$ an equivalence relation on $S$, and $[S]_{\sim}$ the quotient set of $S$. Prove that $[S]_{\sim}$ is a partition of $S$.
\end{zad}










\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}










\newpage
\section{Partial Order Relation}

\begin{zad}
Let $\NN$ be the set of natural numbers. On $\NN$, we define a relation $R$ by:
$$
xRy \qquad\Llra\qquad
\exists z\in\NN : xz=y.
$$
Verify that $R$ is a partial order relation.
\end{zad}

\begin{zad}
Let $\RR$ be the set of real numbers. On $\RR$, we define a relation $R$ by:
$$
aRb\qquad\Lra\qquad \exists k\in\NN_0 : b = 2^k a.
$$
\begin{enumerate}[label=\rm(\roman*)]
\item Write at least five elements of the relation $R$.
\item Is $R$ a partial order relation?
\item Is $R$ a linear order relation?
\end{enumerate}
Provide detailed justifications for all answers.
\end{zad}

\begin{zad}
Consider the divisibility relation $|$, defined on the set of positive integers, where $a|b$ is read as ``$a$ divides $b$''.
\begin{enumerate}[label=\rm(\roman*)]
\item Show that $|$ is a partial order relation on $\ZZ^+$.
\item Show that $|$ is not a linear order relation on $\ZZ^+$.
\end{enumerate}
\end{zad}

\begin{zad}
Let $S=\ZZ$ be the set of integers. On $S$, we define a relation $R$ by:
$$
aRb \qquad\Llra\qquad
\exists r\in\NN : b=a^r.
$$
\begin{enumerate}[label=\rm(\alph*)]
\item Is $R$ a partial order relation?
\item Is $R$ a linear order relation?
\end{enumerate}
\end{zad}

\begin{zad}
Let $\ZZ$ be the set of integers. On $\ZZ$, we define a relation $R$ by:
$$
xRy\qquad\Lra\qquad \exists n\in\NN_0 : x = y + n.
$$
Is $R$ a partial order relation? Is $R$ a linear order relation? Provide detailed justifications for your answers.
\end{zad}

\begin{zad}
Let $B_4$ be the set of natural numbers from $0$ to $15$. We represent these numbers in binary notation: the number $b\in B_4$ is written as $b=b_3b_2b_1b_0$, where each digit $b_i$ is either $0$ or $1$ (specifically, $b = b_3 2^3 + b_2 2^2 + b_1 2^1 + b_0 2^0$, e.g., $8=1000$, $2=0010$, $15=1111$, etc.). On $B_4$, we define a relation $\preceq$ by:
$$
a\preceq b
\quad\Longleftrightarrow\quad
\forall i~(a_i\le b_i).
$$
\begin{enumerate}[label=\rm(\roman*)]
\item Write at least five elements of the relation $\preceq$.
\item Is $\preceq$ a partial order relation?
\item Is $\preceq$ a linear order relation?
\end{enumerate}
Provide detailed justifications for all answers.
\end{zad}









\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}










\newpage
\section{Functions}

\begin{zad}[{2nd exam, January 2022}]
The function $f : \ZZ \rightarrow \ZZ$ is defined by
$$
f(x) = x^2.
$$
Examine the injectivity, surjectivity, and bijectivity of the function $f$.
\end{zad}

\begin{zad}
Let $\RR$ be the set of real numbers, and let $f : \RR \rightarrow \RR$ be a function defined by
$$
f(x) = 5x + 12.
$$
Examine the injectivity, surjectivity, and find $f^{-1}(x)$.
\end{zad}

\begin{zad}
Consider the following relation:
$$
\{(x, y) \in \RR \times \RR : y^2 = \sqrt{x}\}.
$$
Determine if the given relation is a function on $\RR$. (Provide a detailed explanation of your answer.)
\end{zad}

\begin{zad}
Let $\RR^+_0 = \{x \in \RR \mid x \geq 0\}$. Consider the following relation:
$$
\{(x, y) \in \RR^{+}_0 \times \RR : y^2 = \sqrt{x}\}.
$$
Determine if the given relation is a function from $\RR^{+}_0$ to $\RR$. (Provide a detailed explanation of your answer.)
\end{zad}

\begin{zad}
Let $\RR^+_0 = \{x \in \RR \mid x \geq 0\}$. Consider the following relation:
$$
R = \{(x, y) \in \RR^+_0 \times \RR^+_0 : y^2 = \sqrt{x}\}.
$$
Determine if the given relation is a function on $\RR^+_0$. (Provide a detailed explanation of your answer.)
\end{zad}

\begin{zad}
Let $a, b \in \RR$ and $b \neq 0$. The function $f : \RR \setminus \{0\} \rightarrow \RR \setminus \{a\}$ is defined by
$$
f(x) = a + \frac{b}{x}.
$$
Examine the injectivity, surjectivity, and bijectivity of the function $f$.
\end{zad}

\begin{zad}
Find an example of:
\begin{enumerate}[label=\rm(\alph*)]
\item An injective function $f : \NN \rightarrow \NN$ that is not surjective.
\item A function $f : \NN \rightarrow \NN$ that is surjective but not injective.
\end{enumerate}
\end{zad}

\begin{zad}
Let $\NN$ be the set of natural numbers, and let $g : \NN \times \NN \rightarrow \NN$ be a function defined by
$$
g(m, n) = 2^m \cdot 3^n.
$$
Examine the injectivity, surjectivity, and determine $g^{-1}$ (if it exists).
\end{zad}

\begin{zad}
Let $\ZZ$ be the set of integers, and let $f : \ZZ \times \ZZ \rightarrow \ZZ$ be a function defined by
$$
f(m, n) = m + n.
$$
Examine the injectivity, surjectivity, and determine $f^{-1}$ (if it exists).
\end{zad}

\begin{zad}
Let $f : A \rightarrow B$ be a function, and let $\im(f) := \{y \in B \mid (\exists x)((x, y) \in f)\}$. 
%%(note that $\im(f) \subseteq B$). 
Prove the following implication:
\begin{enumerate}[label=$\bullet$]
\item If $f$ is an injective function, then $f^{-1}$ is a function from $\im(f)$ to $A$.
\end{enumerate}
(In the above implication, $f^{-1}$ is the inverse relation of the relation $f$, i.e., $f^{-1} = \{(y, x) \mid (x, y) \in f\}$.)
\end{zad}

\begin{zad}[Theoretical Exercise]
Let $f : A \rightarrow B$ be a function. If there exists a function $g : B \rightarrow A$ such that
$$
f \circ g = \id_B \qquad \text{and} \qquad g \circ f = \id_A,
$$
show that $f$ is a bijective function and $g = f^{-1}$.
\end{zad}

\begin{zad}[Theoretical Exercise]
Let $f : A \rightarrow B$ and $g : B \rightarrow A$ be given functions. Prove the following implications:
\begin{enumerate}[label=$\bullet$]
\item If $f \circ g = \id_B$, then $f \circ g$ is a surjective function.
\item If $f \circ g$ is a surjective function, then the function $f$ is also surjective.
\end{enumerate}
(In the first implication above, $\id_B$ is the identity function on the set $B$, i.e., $\id_B(b) = b$ for all $b \in B$.)
\end{zad}












\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}










\newpage
\section{Hasse Diagram. Lattice.}

\begin{zad}
Given is the relation $R=\{(a,b)\mid a\le b\}$ on the set $S=\{1,2,3,4\}$. 
\begin{enumerate}[label=\rm(\roman*)]
\item Show that $R$ is a partial order relation.
\item Sketch the Hasse diagram.
\item Does $S$ have the structure of a lattice with respect to the relation $R$? (Justify your answer!)
\end{enumerate}
\end{zad}

\begin{zad}
Let $S = \{1, 2, \ldots, 10\}$. A relation on the set $S$ is defined as follows:
$$
x R y \quad\Lra\quad x + y \text{ is even ~and~ } x\le y.
$$
\begin{enumerate}[label=\rm(\roman*)]
\item Show that $R$ partially orders the set $S$. 
\item Draw the Hasse diagram with respect to $R$.
\item Find all $R$-maximal elements, if they exist.
\item Does $S$ have the structure of a lattice with respect to $R$?
\end{enumerate}
\end{zad}

\begin{zad}
Given is a partial order relation $\{(A,B)\mid A\subseteq B\}$ defined on the power set $\P(S)$ of the set $S=\{a,b,c\}$. 
\begin{enumerate}[label=\rm(\alph*)]
\item Sketch the Hasse diagram.
\item Find the lower and upper bounds for the subset $\{\{a\}\}$.
\item Find the lower and upper bounds for the subset $\{\{a,c\}\}$.
\item Find the lower and upper bounds for the subset $\{\{a\},\{a,c\},\{c\}\}$.
\end{enumerate}
\end{zad}

\bigskip
\hvFloat[floatPos=!htb,capPos=after,onlyText=true,]{}
{
\includegraphics[scale=1.6]{diagram3s}
}
{
\begin{zad} 
The partial order relation $\preccurlyeq$ on the set $S = \{a, b, c, d, e, f, g, h, i\}$ is defined by the Hasse diagram on the left.
\begin{enumerate}[label=\rm(\alph*)]
\item Find all $\preccurlyeq$-lower bounds and the $\preccurlyeq$-greatest lower bound of the subset $\{d,e\}$, if they exist.
\item Find all $\preccurlyeq$-upper bounds and the $\preccurlyeq$-least upper bound of the subset $\{f,c\}$, if they exist.
\item Determine whether $S$ has the structure of a lattice with respect to $\preccurlyeq$. Justify your answer in detail.
\end{enumerate}
\end{zad}
}{fg}

\begin{zad}[{2nd colloquium, January 2022}]
Let the relation of divisibility $R$ be defined on the set $S = \{2, 4, 5, 6, 7, 10, 14, 18, 20, 24, 25\}$:
$$
xRy\qquad\Lra\qquad x \text{ divides } y.
$$
\begin{enumerate}[label=\rm(\alph*)]
\item Draw the Hasse diagram with respect to $R$.
\item Find all $R$-maximal elements, if they exist.
\item Find all $R$-minimal elements, if they exist.
\item Find all $R$-lower bounds of the subset $\{24\}$, if they exist.
\item Find the $R$-greatest lower bound of the subset $\{24\}$, if it exists.
\item Determine whether $S$ has the structure of a lattice with respect to $R$.
\end{enumerate}
\end{zad}

\begin{zad}
Draw the Hasse diagram of the partial order $(D(60), |)$. Here, $D(60) = \{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60\}$ and $|$ is the relation of divisibility. Also, find $|$-$\sup(\{20, 30\})$, $|$-$\sup(\{2, 6\})$, $|$-$\sup(\{2, 15\})$, $|$-$\inf(\{20, 30\})$, and $|$-$\inf(\{6, 5\})$, if they exist.
\end{zad}

\begin{zad}
The partial order $R$ on the set $S$ is given by the following Hasse diagram.
\begin{center}
\includegraphics[scale=1.1]{4a}
\end{center}
Does the set $S$ have the structure of a lattice with respect to $R$? Justify your answer in detail.
\end{zad}












\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}










\newpage
\section{Equivalence of Sets}

\begin{zad}
Show that $\NN$ (the set of natural numbers) and $\ZZ$ (the set of integers) are two equinumerous sets.
\end{zad}

\begin{zad}
Find a bijection between the interval $(0,1)$ and the interval $(a,b)$.
\end{zad}

\begin{zad}[exam, February 2021]
First, show that there exists an injective function $f : \ZZ \to \NN$. Then prove that $|\ZZ| = |\NN|$.
\end{zad}

\begin{zad}[{2nd colloquium, January 2022}]
Let $2\NN$ be the set of all even numbers (i.e., $2\NN=\{2n \mid n \in \NN\}$). 
First, show that there exists an injective function $f : \ZZ \to 2\NN$. Then prove that $|\ZZ| = |2\NN|$.
\end{zad}

\begin{zad}[2nd colloquium, January 2021]
Show that the intervals $[2,\infty)$ and $[-3,3)$ are equinumerous.
\end{zad}

\begin{zad}[exam, June 2021]
Show that the intervals $(0, 2)$ and $[1, 3)$ are equinumerous.
\end{zad}

\begin{zad}
First, show that there exists an injective function $f : \ZZ \times \ZZ \to \NN \times \NN$. Then prove that $|\ZZ \times \ZZ| = |\NN \times \NN|$.
\end{zad}

\begin{zad}
Let $\NN$ be the set of natural numbers and $\ZZ$ be the set of integers. Justify whether the statement 
$$
|\ZZ \times \ZZ| = |\NN|
$$
holds for the sets $\ZZ \times \ZZ$ and $\NN$.
\end{zad}



\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}






\end{document}
