% -----------------------acknowledge for overleaf and designer of this template-----------------------
\documentclass[12pt]{exam}
\usepackage{amsthm}
\usepackage{libertine}
\usepackage[utf8]{inputenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{multicol}
\usepackage[shortlabels]{enumitem}
\usepackage{siunitx}
\usepackage{cancel}
\usepackage{graphicx}
\usepackage{pgfplots}
\usepackage{listings}


% automata
\usepackage{tikz}
\usetikzlibrary{automata, positioning, arrows}


\pgfplotsset{width=10cm,compat=1.9}
\usepgfplotslibrary{external}
\tikzexternalize

\newcommand{\class}{\Large Logic and Computation I, Autumn 2024 } % This is the name of the course 
\newcommand{\examnum}{Exercise 01-03} % This is the index of the homework
\newcommand{\examdate}{Due Date: } % This is the due date
\newcommand{\timelimit}{}





\begin{document}
\pagestyle{plain}
\thispagestyle{empty}

\noindent
\begin{tabular*}{\textwidth}{l @{\extracolsep{\fill}} r @{\extracolsep{8pt}} l}
\textbf{\class} & & \textit{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}\\
&&\\
\textbf{\examnum} & &\textit{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}\\ 
\textbf{\examdate} &&\\
\end{tabular*}\\
\rule[2ex]{\textwidth}{2pt}
% ---


\noindent \textbf{Exercise 1.3.1}\\
Let $f(x_1,  \ldots,x_n,y)$ be a primitive recursive function. Prove the following functions are also primitive recursive. 
$$F(x_1,  \ldots,x_n, z)= \Sigma_{y<z} f(x_1,\ldots ,x_n,y),$$
$$G(x_1,  \ldots,x_n, z)= \Pi _{y<z }f(x_1,  \ldots,x_n,y).$$
\bigskip

\noindent\underline{\textsf{Solution:}}

\vspace{8em}



\noindent \textbf{Exercise 1.3.2}\\
Let $f(x_1,  \ldots,x_n,y)$ be a primitive recursive function. Prove the following functions are also primitive recursive. 
$$F(x_1,  \ldots,x_n, z)= \Sigma_{y<z} f(x_1,\ldots ,x_n,y),$$
$$G(x_1,  \ldots,x_n, z)= \Pi _{y<z }f(x_1,  \ldots,x_n,y).$$
\bigskip

\noindent\underline{\textsf{Solution:}}

\vspace{8em}



\noindent\textbf{Exercise 1.3.3}\\
Prove that if $A(x_1,  \ldots, x_n, y)$ is primitive recursive, $\forall y \! < \! z \ A(x_1,  \ldots,x_n,y)$  and 
$\exists y \! < \! z \ A(x_1,  \ldots, x_n, y)$ are also primitive recursive. 

\bigskip
\noindent\underline{\textsf{Solution:}}



\newpage
\noindent\textbf{Exercise 1.3.4}

The symbol set $\Omega$ is the same as the example above. ``Terms'' are defined as below
\begin{itemize}\setlength\itemsep{0.8em}
\item [(1)]  $0$, $1$ are terms.
\item [(2)] if $s$ and $t$ are terms, so is $(s+t)$.
e.g., $((1+0)+1)$ is a term, but $(1+0)+1$ is not a term.
\end{itemize}
Show that the predicate ${\rm Term}(x)$ expressing ``$x$ is the G\"{o}del number of a term''  is primitive recursive.

\bigskip
\noindent\underline{\textsf{Solution:}}






\end{document}



