\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 2, given Oct 14, due Oct 21}

\bigskip

\noindent
1. Write the truth tables for:

(a) $(\not (P \or Q)) \or (\not Q)$

(b) $(P \impl Q) \impl (Q \impl P)$

(c) $(\not P) \and (\not (P \impl Q))$



\bigskip

\noindent
2. Prove the following equivalences using equivalent rewriting (e.g. by
transforming both sides into conjunctive or disjunctive normal form):

(1)
$P \and Q \and (\not P \or \not Q) \equiv \not P \and \not Q \and (P \or Q)$

(2)
$P \or (P \impl (P \and Q)) \equiv \not P \or \not Q \or (P \and Q)$

\bigskip

\noindent
3. Prove the following formula using the natural style inferences which you
find appropriate, in a style similar to our natural style proofs from the
lecture:

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


\end{document}