\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 2015.
Homework 5, given Nov 12, due Nov 19.}

\bigskip

\noindent
1. Show that neither $A \impl C$, nor $B \impl C$
are logical consequences of $(A \and B) \impl C$.
\bigskip

\noindent
2. Compute the truth value of the formula $\forall_{x} \exists_{y} (x + y) > c$ under the
interpretation: 
$$I\ =\ \{D_I = \{0, 1\}, c_I = 0, +_I = +_N', >_I = >_N \}$$
(the interpretations of $+$ and $>$ are the ones from the theory of natural numbers,
except for $1 +_I 1 = 1$).

\bigskip

\noindent
3. Give counterexamples showing that the equivalences
$$\forall_x (P[x] \or Q[x])\ \equiv\ (\forall_x P[x]) \or (\forall_x Q[x]))$$ and 
$$\exists_x (P[x] \and Q[x])\ \equiv\ (\exists_x P[x]) \and (\exists_x Q[x]))$$
do not hold.

\bigskip

\noindent
4. Show $\exists_x ((P[x] \impl Q))\ \equiv\ (\forall_x) P[x] \impl Q$
by reducing both sides to normal form.


\end{document}
