\documentclass{article}

% \newcommand{\showpoints}{yes}

% \usepackage[magyar]{babel}
% \usepackage[latin2]{inputenc}
\usepackage{t1enc}
\usepackage{times}
\usepackage{alltt}
\usepackage{amssymb}
\frenchspacing

% page setup for A4
\topmargin -1,5cm                       % two more cms on the top
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep
     
\textheight 8.9in
\advance \textheight by 4cm     % four more cms on the bottom

\oddsidemargin -0,8cm           % shift a bit to the left
\evensidemargin 0pt
\marginparwidth 2cm             % give a bit more margin
     
\textwidth 6.5in
     
\advance\hoffset by -3mm        % A4 is narrower.
\advance\voffset by  8mm        % A4 is taller.

\parindent=0cm
\parskip=.2cm
\pagestyle{empty}

% aux. commands
\newcommand{\ntt}[1]{\texttt{#1}}
\newcommand{\stt}[1]{{\small\texttt{#1}}}
\newenvironment{allstt}{\begin{alltt}\small}{\end{alltt}}
\newcommand{\bs}{\symbol{92}}
\newcommand{\ul}{\symbol{95}}


\newcommand{\cE}{$\mathcal{E}$\ }
\newcommand{\ciE}{\mathcal{E} }
\newcommand{\cR}{$\mathcal{R}$}
\newcommand{\ciR}{\mathcal{R} }
\newcommand{\ciT}{\mathcal{T} }
\newcommand{\cT}{$\mathcal{T}$}
\newcommand{\ciL}{\mathcal{L} }
\newcommand{\cL}{$\mathcal{L}$\ }
\newcommand{\ciI}{\mathcal{I}}
\newcommand{\cI}{$\mathcal{I}$}
\newcommand{\ciA}{\mathcal{A}}
\newcommand{\cA}{$\mathcal{A}$}

% colouring
\def\colouring{0} % set this to 1 to enable colors
%\def\colouring{1} % set this to 0 to disable colors
\ifnum \colouring > 0
  \newcommand{\iv}[1]{\textcolor{mmagenta}{\texttt{#1}}}
  \newcommand{\dm}[1]{\textcolor{mlblue}{\texttt{#1}}}
  \newcommand{\class}[1]{\textcolor{mred}{\texttt{#1}}}
  \newcommand{\prop}[1]{\textcolor{mblue}{\texttt{#1}}}
  \newcommand{\lit}[1]{\textcolor{morange}{\texttt{#1}}}
  \newcommand{\op}[1]{\textcolor{mgreen}{\texttt{#1}}}
  \newcommand{\ivC}[1]{\textcolor{mmagenta}{#1}}
  \newcommand{\dmC}[1]{\textcolor{mlblue}{#1}}
  \newcommand{\classC}[1]{\textcolor{mred}{#1}}
  \newcommand{\propC}[1]{\textcolor{mblue}{#1}}
  \newcommand{\litC}[1]{\textcolor{morange}{#1}}
  \newcommand{\opC}[1]{\textcolor{mgreen}{#1}}
  \newcommand{\dliv}[1]{\textcolor{mmagenta}{\textsf{#1}}}
  \newcommand{\dldm}[1]{\textcolor{mgreen}{\texttt{#1}}}
  \newcommand{\dlclass}[1]{\textcolor{mred}{\textsf{#1}}}
  \newcommand{\dlprop}[1]{\textcolor{mblue}{\textsf{#1}}}
  \newcommand{\dllit}[1]{\textcolor{morange}{\textsf{#1}}}
  \newcommand{\dlop}[1]{\textcolor{mgreen}{\textsf{#1}}}
  \newcommand{\ifcolour}[1]{#1}
\else
  \newcommand{\iv}[1]{\texttt{#1}}
  \newcommand{\dm}[1]{\texttt{#1}}
  \newcommand{\class}[1]{\texttt{#1}}
  \newcommand{\prop}[1]{\texttt{#1}}
  \newcommand{\lit}[1]{\texttt{#1}}
  \newcommand{\op}[1]{\texttt{#1}}
  \newcommand{\ivC}[1]{#1}
  \newcommand{\dmC}[1]{#1}
  \newcommand{\classC}[1]{#1}
  \newcommand{\propC}[1]{#1}
  \newcommand{\litC}[1]{#1}
  \newcommand{\opC}[1]{#1}
  \newcommand{\dliv}[1]{\textsf{#1}}
  \newcommand{\dldm}[1]{\texttt{#1}}
  \newcommand{\dlclass}[1]{\textsf{#1}}
  \newcommand{\dlprop}[1]{\textsf{#1}}
  \newcommand{\dllit}[1]{\textsf{#1}}
  \newcommand{\dlop}[1]{\textsf{#1}}
  \newcommand{\ifcolour}[1]{}
\fi



\newcommand{\mypair}[1]{\langle\,#1\,\rangle}

\renewcommand{\textfraction}{0}
\renewcommand{\floatpagefraction}{1}
\renewcommand{\topfraction}{1}
\renewcommand{\bottomfraction}{1}

\newcommand*{\ilink}[1]{\textsf{#1}}
\newcommand*{\code}[1]{\texttt{#1}}
\newenvironment{myverbatim}{\tt\obeylines\obeyspaces\frenchspacing\medskip\setlength{\parindent}{0em}}{\medskip}



\newcommand{\alphenumi}{
%\renewcommand{\itemindent}{0.3em}
\renewcommand{\labelenumi}{(\alph{enumi})}}

\newcommand{\swtitle}{


\centerline{Semantic and Declarative Technologies}

\smallskip
\centerline{Final exam, May 14--17, 2020}

\smallskip

}
\usepackage {paralist}

\makeatletter
\renewcommand{\p@enumii}{}
\makeatother
  
\begin{document}
% \bigskip

\vspace*{-1cm}

\swtitle

\bigskip
% \bigskip

% \textbf{Part I} -- 50 minutes
% \medskip p

This is an  open book test, you can use the printed version of the slides
and/or the textbook. 

\begin{enumerate}

\item Consider the interpretation $\ciI =
\mypair{\Delta,{I}}$, where
\label{task1}

\vspace*{-5mm}

\begin{minipage}[t]{0.5\textwidth}
\begin{eqnarray}
\Delta &=& \{\dldm{Nick}, \dldm{Mary}, \dldm{Ann},
  \dldm{Steve}, \dldm{John}, \dldm{Paul}\}\nonumber\\
%  \dlclass{Human}^{I} &=& \Delta \nonumber\\
 \dlclass{Female}^{I} &=& \{\dldm{Mary}, \dldm{Ann}\}\nonumber\\
 \dlprop{hasChild}^{I} &=& \{\mypair{\dldm{Nick}, \dldm{Ann}},\mypair{\dldm{Mary},
  \dldm{Ann}},\nonumber\\
                    & & \hspace*{0.5em}\mypair{\dldm{Ann}, \dldm{John}},\mypair{\dldm{Steve},
  \dldm{John}},\mypair{\dldm{Ann}, \dldm{Paul}},\mypair{\dldm{Steve},
  \dldm{Paul}}\}    \nonumber\\
\dlclass{BlueEyed}^{I} &=& \{\dldm{Nick},\dldm{Steve},\dldm{Ann},\dldm{Paul}\}\nonumber%\\
%\dlclass{Father}^{I} &=& \{\dldm{Nick},\dldm{Steve}\}\label{interp:y} \nonumber\\
%\dlclass{FatherOfGirls}^{I} &=& \{\dldm{Nick}\}  \fullstop \nonumber
\end{eqnarray}
\end{minipage}

\bigskip

 Consider also the TBox {\cT} consisting of the following axioms: 


\vspace*{-5mm}

\begin{eqnarray}
  \dlclass{Grandchild} &\equiv&  
  \exists \dlprop{hasChild}^-.\exists  \dlprop{hasChild}^-.\top \label{Gc:i}\\
 \dlclass{Grandchild} \sqcap \dlclass{BlueEyed} &\sqsubseteq&   \forall \dlprop{hasChild}^-.\forall  \dlprop{hasChild}^-.\dlclass{BlueEyed} \label{Gc:ii}
\end{eqnarray}

%% Statement (\ref{Gc:i}) is a definitional axiom, while
%% (\ref{Gc:ii}) is a General Concept Inclusion axiom.

\begin{enumerate}
\item Assuming that axiom 
  (\ref{Gc:i})  holds in   {\cI}, which set corresponds to the
  concept \dlclass{Grandchild} in  {\cI}?           

\item For both the left and the right hand side of (\ref{Gc:ii}) provide an
  English phrase describing those belonging to the given concept. As an
  example, such a phrase for the right hand side of (\ref{Gc:i}) could be:
  ``those having a parent who has a parent'' or ``those having a
  grandparent''.  

\item Provide the meaning for both the left and the right hand side of
  (\ref{Gc:ii}), i.e.\ give subsets of $\Delta$
  that correspond to these two concept expressions in {\cI}.  

\item Decide if  (\ref{Gc:ii}) holds in {\cI}.       
\end{enumerate}



\item  Transform the following  sentences into a $\mathcal{SHIQ}$ TBox using
the concepts and roles written in \textsf{grotesque} font. Anything in
parentheses is explanation only, and should not be formalized.

(Our universe contains \textsf{Human}s and \textsf{Robot}s). Each human is a
\textsf{Creature}, and each robot is also a creature \emph{(a-b)}. No one can be both a human and a
robot \emph{(c)}.  \textsf{Kimak}s are a subgroup of humans
\emph{(d)}. (Relationships \textsf{hasEnemy} and \textsf{hasEmployer} are
defined. Role \textsf{hasEnemy} is not necessarily symmetrical, i.e.\ from
$a$ has enemy $b$ it does not necessarily folow that $b$ has enemy $a$.)  A
human cannot be an employer of a robot \emph{(e)}, and robots have no
enemies \emph{(f)}.    

  A \textsf{Tyrant} is defined as someone who is a kimak, has at least two enemies
  who are non-kimak creatures, and who has a robot employer \emph{(g)}.    

Give at least one non-trivial re-formulation (at least two formulations
alltogether) for statements \emph{(e)} and
\emph{(f)}.  $C \sqsubseteq \bot$ vs. $C \equiv \bot$ and $\top \sqsubseteq
C$ vs. $\top \equiv C$ are considered trivial re-formulations.




\item Consider the following subsumption check, with respect to an
  empty TBox:\label{task3}

\vspace*{-5mm}

\begin{eqnarray}
\exists \textsf{hC}.\textsf{C} \sqcap \exists \textsf{hC}.\textsf{B} \sqsubseteq
  \exists \textsf{hC}.(\textsf{C} \sqcap \textsf{B}) \sqcup \forall \textsf{hC}.(\textsf{C} \sqcup \textsf{B}) \sqcup  
(\geqslant 3 \textsf{hC}).\label{Gc:schk}
\end{eqnarray}

\begin{enumerate}

\item Rewrite the above axiom  into a somewhat formalized English sentence (\textsf{hC} stands
   for ``has child'', \textsf{C} stands for ``clever'' and \textsf{B}
  stands for ``blonde'').

  Use the following format: ``If $x$ \ldots then either $x$ \ldots''.   

\item Transform the above subsumption check to a concept satisfiability
  check for a concept, call it $C_0$.      

\item Produce the negation normal form of $C_0,$ call it $C_1$.  

\item Does  subsumption (\ref{Gc:schk}) hold? (That is, is it true in all
  interpretations?) A ``yes'' or ``no'' answer is enough.\label{task3:yesno}     

\end{enumerate}


\smallskip

\begin{center}
{\bf The following tasks are \emph{optional}}
\end{center}

% \smallskip


\item Re task \ref{task1}: Change the meaning of
  $\dlclass{BlueEyed}$ in interpretation {\cI} so that your answer to
  subquestion (d) changes to its opposite (i.e.\ if the answer was
  ``yes'', it changes to ``no'' and if the answer was
  ``no'', it changes to ``yes'').     

\item Re task \ref{task1}:
Show that the axiom (\ref{Gc:iii}) below, is a consequence of the TBox
{\cT} containing the axioms (\ref{Gc:i}) and  (\ref{Gc:ii}).     

\vspace*{-5mm}

\begin{eqnarray}
 \dlclass{BlueEyed} &\sqsubseteq&   \forall \dlprop{hasChild}^-.\forall  \dlprop{hasChild}^-.\dlclass{BlueEyed} \label{Gc:iii}
\end{eqnarray}

Hint: show that an \emph{arbitrary} counterexample for (\ref{Gc:iii}) is a counterexample for
(\ref{Gc:ii}) as well.


\item Regarding task \ref{task3}: Justify your answer to subquestion
  \ref{task3} (\ref{task3:yesno}). 


\end{enumerate}

\end{document}
