\documentclass[11pt]{article}
\usepackage{hw}
\newcommand{\mdot}{\cdot}
\newcommand{\fa}{\forall}
\begin{document}

\dotitle{7}{Thursday, November 9}


\begin{enumerate}

\item  Let $L$ be a language with two unary predicates, $A$ and $B$. Consider
the equivalence
\[
\fa x (A(x) \lor B(x)) \liff \fa x A(x) \lor \fa x B(x).
\]
\begin{enumerate}

\item Show that one direction is valid, using only semantic notions.
In particular, your answer should make it clear that you know what ``valid'' means!

\item Show that the other direction is not valid.
\end{enumerate}

\item Find a prenex sentence (i.e.~one where all the quantifiers occur up
front) equivalent to 
\[
\lnot (\ex x A(x) \limplies \fa y B(y)).
\]

\item Fix a language, $L$, which has one binary relation
symbol, $R$. Which of the following statements are true and which are
false? Justify your answers.
\begin{enumerate}
\item If $\varphi$ is any sentence, either $\models \varphi$ or
$\models \lnot \varphi$.
\item If $\varphi$ is any sentence and $\gmdl{A}$ is any structure,
either $\gmdl{A} \models \varphi$ or $\gmdl{A} \models \lnot
\varphi$.
\item If $\varphi$ is any sentence and $\Gamma$ is any set of
sentences, then either $\Gamma \models \varphi$ or $\Gamma \models
\lnot \varphi$.
\end{enumerate}


%\item Give natural deduction proofs of the following validities (using the 4 quantifier rules, and not defining $\exists\varphi$ as $\neg\fa\neg\varphi$\ !).
%\begin{enumerate}

%\item $\lnot \ex x \ph(x) \limplies \fa x \lnot \ph(x)$

%\item  $\ex x \lnot \ph(x) \limplies \lnot \fa x \ph(x)$

%\item $(\ex x \ph \limplies \psi) \limplies \fa x (\ph \limplies \psi)$, 
%where $x$ is not free in $\psi$.

%\end{enumerate}


\item Determine whether the following syllogism is valid (justify your answer).

\begin{quote}
Some Greeks are not slaves.\\
No slaves are women.\\
Therefore, some women are not Greek.
\end{quote}


\item In van Dalen, do problems  2 (i,ii) and 9 (iv) on p.~80.

\item\addstar In van Dalen, do problem 15 on p.~81.
  
%\item The language of \emph{monoids} has a constant symbol $1$ and a
%  binary function symbol, written $x\mdot y$. The axioms for monoids
%  are associativity, $\fa x,y,z\ (x\mdot(y\mdot z) = (x\mdot y)\mdot
%  z)$, and $1$ is a (two-sided) unit, $\fa x\ (1\mdot x = x)$ and $\fa
%  x\ (x\mdot 1=x)$.
 
%\begin{enumerate}
  
%\item Use natural deduction to show that every monoid can be ordered
%  by defining $x\leq y$ iff $\exists z (x\mdot z=y)$, i.e.\ show that
%  this relation is reflexive and transitive.
  
%\item\addstar Is it always a partial ordering? That is, is it
%  necessarily antisymmetric, in the sense that $x\leq y$ and $y\leq x$
%  implies $x=y$?

%\end{enumerate}
\end{enumerate}
\end{document}