\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}}}
\newcommand{\nov}[1]{{\overline #1}}
\newcommand{\arrow}{\rightarrow}

\pagestyle{empty}

\begin{document}

{\bf Mathematical Logic, WS 2018.
Homework 6, given Dec. 4, due Dec 11.}

\bigskip

\noindent
1.
Find the sequent calculus rules for equivalence (in the assumptions and in the goals) by using
$$ \varphi \lequiv \psi\ \equiv\ (\varphi \and \psi) \or (\not \varphi \and \not \psi) $$ and the rules for negation, conjunction, and disjunction.

\bigskip

\noindent
2.
Modifiy the sequent proof of:
$$ (A \or B) \impl C\ \ylc\ (A \impl C) \and (B \impl C).$$
\begin{description}
\item[(a)] Use $(A \impl B)$ instead of $(A \impl C).$ 
\item[(b)] Use Modus Ponens, Implied Goal or other special rules in order to simplify the proof.
\item[(c)] Use unit propagation.
\end{description}
\bigskip

\noindent
3.
Compute the truth value:
$\langle P[x] \impl P[f[x]] \rangle_I^{\{x \arrow 1\}}$
with respect to the interpretation

$I:\ \{
D_I = \{0, 1\},\ 
a_I = 0,\ 
f_I = \{0 \arrow 1, 1 \arrow 0\},\ 
P_I = \{0 \arrow \false, 1 \arrow \true\}\}$.

\bigskip

\noindent
4.
Investigate the interaction between the existential quantifier and the logical
connectives $\and, \or$. Find a counterexample for the non-equivalence.

\bigskip

\noindent
5.
Write and prove the deMorgan equivalence for the negation of the existential
quantifier.

\end{document}

 
