\documentstyle[12pt]{article}

\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} % logical connective equivalence
\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{\nov}[1]{{\overline{#1}}}




\pagestyle{empty}

\begin{document}

{\bf Logic 1, WS 2004.
Homework 3, given Oct 21, due Oct 28}

\bigskip

\noindent
1. Prove the following lemma:\\
For any formulae $\phi$, $\phi_1$, $\phi_2$, if $\phi_1 \equiv \phi_2$,
then $(\phi \impl \phi_1) \equiv (\phi \impl \phi_2)$.

\bigskip

\noindent
2. Prove the correctness of the following two sequent rules:

$$
(\and\ylc)\ \frac
{\Phi, \varphi_1, \varphi_2 \ylc \Psi}
{\Phi, \varphi_1 \and \varphi_2 \ylc \Psi}
\ \ \ \ \ \ \ 
(\ylc\not)\ \frac
{\Phi, \psi \ylc \Psi}
{\Phi \ylc \Psi, \not \psi}
$$

\bigskip

\noindent
3. Formulate the correctness of the sequent calculus presented in the lecture
and give a summary of the proof of it.

\bigskip

\noindent
4. Construct the sequent deduction for the following formula using the sequent
rules which you find appropriate (preferably those ones which
correspond to the natural style proof shown during the lecture):

$((A \or B) \impl C) \lequiv ((A \impl C) \and (B \impl C))$


\end{document}