\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 2008.
Homework 1, given Oct 15, due Oct 22}

\bigskip

\noindent
1.
Define inductively the function ``the set of propositional variables of a propositional formula''.

\bigskip

\noindent
2.
Define inductively the function ``the depth of a propositional formula''.
The depth of a formula is the depth of the tree which represents the formula.
This tree has logical connectives as internal nodes and propositional variables
as the leaves.
Every subtree corresponds to a subformula,
has as root the main logical connective of this subformula,
and as subtrees the sub-subformulae related by this logical connective.
Examples:
Detph[$A$] = 0;
Depth[$A \oor B$] = 1;
Depth[$A \impl (A \oor B)$] = 2.
Depth[$(A \aand B) \impl (A \oor B)$] = 2.

\bigskip

\noindent
3.
Prove that the depth of a formula is less or equal to the length of that formula.

\bigskip

\noindent
4.
Write the truth table for the formula:
$$ ((A \oor B) \aand (A \impl C) \aand (B \impl C)) \impl C. $$

\bigskip

\noindent
5.
Using rewriting to normal form, prove the equivalence of the formulae:
$(A \oor B) \impl C$
and
$(A \impl C) \aand (B \impl C)$.

\end{document}