\documentstyle[11pt,abstract]{article}
\headheight 0pt
\setlength{\textwidth}{6.25in}          % normal width of text on page
\setlength{\oddsidemargin}{0in}   % left margin less 1 inch, odd #'ed pgs
\setlength{\evensidemargin}{.25in}  % right margin less 1 inch, even #'ed pgs
\input math
\newcommand{\rarrow}{\rightarrow}
\newcommand{\darrow}{\leftrightarrow}
\renewcommand{\phi}{\varphi}
\begin{document}
\pagestyle{empty}

\begin{center}
{\Large COMP 409/509\\
Assignment No. 1}\\
\bigskip
{\bf Due date: Sept.~14, 2021}
\end{center}
\bigskip

\noindent
{\bf Note}:
\begin{enumerate}
\item
The submitted assignment needs to be typeset in LaTeX.
\item
{\bf Teamwork}: You are expected to complete this assignment in pairs. 
By signing your name on the assignment you are asserting
that the work submitted was done collaboratively, and you have
adhered to Rice University's Honor Code.
At the very least, team work entails:
\begin{itemize}
\item
discussing each problem and agreeing on a sketch of the solution,
\item
reviewing the written solutions for technical correctness and
typographical errors,
\item
doing a joint codewalk over all written programs,
\item
dividing labor equally (roughly), and
\item
being able to explain every answer as if it is your own answer.
\end{itemize}
\item
Note on the submission the total number of hours put by
each partner separately and by the two partners together.
\end{enumerate}


\noindent
{\sf Syntax of Propositional Logic}:
\begin{enumerate}
%\item
%Consider the collection $SuperForm$ of all sets $F$ such that
%\begin{enumerate}
%\item
%$Prop \subseteq F$
%\item 
%If $\varphi$ and $\psi$ are in $F$, then $(\neg\varphi)$ and
%$(\varphi\circ\psi)$ are also in $F$
%\end{enumerate}
%Show that $SuperForm$ is closed under intersection. From this conclude 
%that $Form$ is the intersection of all sets in $SuperForm$.
\item
Show that there are no formulas of length 2,3, or 6, but that every
other length is possible.
\item
Show that between every left parenthesis and right parenthesis in a
formula $\phi$ there is at least one occurrence of a propositional
connective.
\item
Let $\phi$ be a formula, let $p$ be the number of parentheses
(left and right) in $\phi$ and let $l$ be the length (number of
symbols) of $\phi$. What are the minimum and maximum values of $p/l$?
\item
Let $\phi$ be a formula, let $c$ be the number of occurrences of
binary connectives ($\wedge$, $\vee$, $\rightarrow$, and
$\leftrightarrow$) in $\phi$, and let $s$ be the number of occurrences
of atomic propositions in $\phi$.  Show that $s=c+1$.
\item
Give examples of formulas $\alpha$ and $\beta$ and expressions
$\gamma$ and $\delta$ such that $(\alpha \wedge \beta)$ and $(\gamma
\wedge \delta)$ are identical, but $\alpha$ is different than $\gamma$.
\item
The BNF for formulas in {\em prefix notation\/} (also called
{\em Polish notation}) is
$$Form := AP \vert \neg Form \vert \bigcirc Form Form,$$
where $\bigcirc$ is a binary propositional connective.
Note that this syntax does not use parentheses.
For example, the prefix notation for $((p \wedge q) \rightarrow p)$ is
$\rightarrow \wedge p q p$.
Formulate and prove a unique-readability theorem for formulas in
prefix notation.
\item
We say that $\theta$ is a {\em subformula\/} of $\phi$ if
\begin{itemize}
\item
$\theta$ is $\phi$,
\item
$\phi$ is $(\neg\psi)$ and $\theta$ is a subformulas of $\psi$, or
\item
$\phi$ is $(\psi_1\circ\psi_2)$ and $\theta$ is either a subformulas 
of $\psi_1$ or a subformula of $\psi_2$.
\end{itemize}
Let $\alpha$ and $\beta$ be expressions.
We say that $\beta$ is a {\em subexpression\/} of $\alpha$ if
$\alpha=\gamma \beta \delta$, for some expressions $\gamma$ and
$\delta$.
Prove that if $\alpha$ and $\beta$ are formulas and $\beta$ is
a subexpression of $\alpha$, then $\beta$ is a subformula of $\alpha$.
\item
{\sf Well Formedness}:
\begin{itemize}
\item
Describe an algorithm that checks whether a given expression is a
formula.
\item
Analyze the time and space requirements of your algorithm.
\item
Implement the algorithm in your favorite programming language and
use the program to check which of the following expressions is a 
formula (attach a listing of the code).
\begin{enumerate}
\item
$((\neg(A \vee B)) \wedge C)$
\item
$(A \wedge B) \vee C$
\item
$A \rightarrow (B \wedge C)$
\item
$((A \leftrightarrow B) \rightarrow (\neg A))$
\item
$((\neg A ) \rightarrow B \vee C)$
\item
$(((C \vee B \wedge A) \leftrightarrow D)$
\item
$((\vee A) \wedge (\neg B))$
\item
$(A \wedge (B \wedge C)))$
\end{enumerate}
\end{itemize}
\end{enumerate}
\end{document}
