\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 Mathematical Logic, WS 2019.
Homework 1, given Oct 8, due Oct 15}

\bigskip

\bigskip

\noindent
1.
Define inductively the function $L[\varphi]$ which gives the length of a propositional formula $\varphi$,
the function $D[\varphi]$ which gives the depth of a propositional formula,
and the function $V[\varphi]$ which gives the set of variables of the propositional formula.  

\bigskip

\noindent
2.
Prove inductively that $D[\varphi]\leq L[\varphi]$.

\bigskip

\noindent
3.
Write the truth table for implication.

\bigskip

\noindent
4.
Find the formula whose validity is equivalent with the statement
$\varphi_1, \varphi_2, \ldots, \varphi_n\ \elc \psi$ and prove the respective
equivalence.

\end{document}
