\documentclass[12pt]{article}
\usepackage{amsfonts}

\voffset=-3.0cm
\hoffset=-2.6cm
\textwidth=17.5cm
\textheight=24cm

\renewcommand{\not}{\neg}
\newcommand{\nov}[1]{{\overline #1}} % negation by overbar
\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 6, given Dec 7, due Dec 14}

\bigskip

\noindent
1. Give the definition of the truth value of an existential formula under
an interpretation. (Hint: this is the dual of the definition given in the
lecture for the truth value of an universal formula.)


\bigskip

\noindent
2. In the example given during the lecture (a certain interpretation for the
formula\\
 $\forall_{x} (P[x] \impl Q[f[x], a]$), compute the truth value of this
formula for the assignment ${x \leftarrow 2}.$


\bigskip

\noindent
3. Give an example of concrete formulae for which
$\all_{x} (\varphi \or \psi)$ is not equivalent to
$(\all_{x} \varphi) \or (\all_{x} \psi).$ 


\bigskip

\noindent
4. By equivalent transformations, show how to express the formula
$(\exi P[x]) \impl Q$ into an universally quantified formula.
(Hint: this is the dual of the equivalence given in the
lecture.)

\end{document}