\documentclass[12pt]{article}
\usepackage{amsfonts}

\voffset=-3.0cm
\hoffset=-2.6cm
\textwidth=17.5cm
\textheight=24cm

\renewcommand{\not}{\neg}
\renewcommand{\and}{\wedge}
\renewcommand{\or}{\vee}
\newcommand{\impl}{\Rightarrow}
\newcommand{\lequiv}{\Leftrightarrow} %equivalence as logical connective
\newcommand{\all}{\forall}
\newcommand{\exi}{\exists}
\newcommand{\elc}{\models}  % semantic logical consequence
\newcommand{\ylc}{\vdash}  % syntactic logical consequence
%\equiv is already defined for === semantic equivalence
\newcommand{\union}{\cup}
\newcommand{\intersect}{\cap}
\newcommand{\true}{{\mathbb{T}}}
\newcommand{\false}{{\mathbb{F}}}


\pagestyle{empty}

\begin{document}

{\bf Logic 1, WS 2007.
Homework 5, given Nov 22, due Nov 29.}

\bigskip

\noindent
1.
Prove using sequent calculus:
$$ \all_x(P[x] \impl Q) \ylc (\exi_x P[x]) \impl Q $$

\bigskip

\noindent
2.
Prove using sequent calculus:
$$ \exi_x(P[x] \impl Q) \ylc (\all_x P[x]) \impl Q $$

\bigskip

\noindent
3.
Prove using refutation, normal forms, and resolution that
$$\all_x (\exi_y(S[y] \and V[x, y]) \impl (\exi_z(C[z] \and V[x, z])))$$
is a logical consequence of
$$ \all_y(S[y] \impl C[y]).$$

\bigskip

\noindent
4.
Apply the unification algorithm to:
$Q[x, y, z]$ and $Q[u,h[v,v],u].$

\end{document}
