\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 2006.
Homework 1, given Oct 12, due Oct 19}

\bigskip

\noindent
1. 
Compute the truth value of the formula
$(A \and (A \impl B)) \impl B$ under the interpretation
$A \rightarrow \false, B \rightarrow \true.$

\bigskip

\noindent
2. 
Prove by definition that for any two propositional formulae $\phi, \psi$:\\
if the formula $\phi \lequiv \psi$ is a tautology,
then $\phi \equiv \psi.$

\bigskip

\noindent
3. 
Prove by definition that for any two propositional formulae $\phi, \psi$:\\
 $\phi \equiv \psi$ if and only if $\phi \elc \psi$ and $\psi \elc \phi.$


\bigskip

\noindent
4. 
Prove by definition that for any propositional formulae
$\phi_1, \ldots, \phi_n, \psi$:\\
$\phi_1, \ldots, \phi_n\ \elc\ \psi$ if and only if
the formula
$\phi_1 \and \ldots \and \phi_n \and \not \psi$ is unsatisfiable.

\bigskip

\noindent
5. 
Give 5 truth reduction equivalences between propositional formulae.
(For instance, such an equivalence is $A \or \false\ \equiv\ A$).



\end{document}
