\documentclass[12pt]{article}
\usepackage{amsfonts}
 
\voffset=-3.0cm
\hoffset=-2.6cm
\textwidth=17.5cm
\textheight=24cm

\renewcommand{\not}{\neg}
\newcommand{\aand}{\wedge}
\newcommand{\oor}{\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 2012.
Homework 1, given Oct 17, due Oct 24}

\bigskip

\bigskip

\noindent
1.
Define the meta-function $L[\varphi]$ which gives the lenght of a
propositional formula.

Hint: use the induction principle suggested by the definition of
propositional logic formulae.

\bigskip

\noindent
2.
Using the definition above and the definition of the function $D[\varphi]$
(depth of a propositional formula) given in the lecture, prove that
$D[\varphi] \leq L[\varphi]$ for any propositional formula $\varphi.$

Hint: use the induction principle suggested by the definition of
propositional logic formulae.

\bigskip

\noindent
3.
Prove that
for any propositional formulae $\varphi, \psi$, if
$\varphi \elc \psi$ and $\psi \elc \varphi,$ then
$\varphi \equiv \psi.$

(See the style used in the lecture for proving the opposite implication.)

\bigskip

\noindent
4.
Prove that
for any propositional formulae
$\varphi, \psi:$
$\varphi \elc \psi$ iff
$\varphi \lequiv \psi$ is valid.

(The proof may be informal.)

\bigskip

\noindent
5.
Prove that
for any propositional formulae
$\varphi_1, \varphi_2, \ldots, \varphi_n, \psi,$
if
$\varphi_1, \varphi_2, \ldots, \varphi_n\ \elc \psi,$
then
$(\varphi_1 \aand \varphi_2 \aand \ldots \aand \varphi_n) \impl \psi$ is valid.

(See the style used in the lecture for proving the opposite implication.)

\end{document}