\documentclass{article}

\title{Voortgezette Logica\\
2005-2006\\
Oefenopgaven\\
Week 1}
\author{Docent: Joost J. Joosten}

\begin{document}
\maketitle

\section*{Natuurlijke deductie}

Geef bewijzen met natuurlijke deductie van de volgende
formules.

\begin{enumerate}
\item
$(\varphi \wedge \psi \to \sigma) \to (\varphi \to (\psi \to \sigma))$

\item
$(\varphi \wedge \psi \to \sigma) \to (\psi \to (\varphi \to \sigma))$

\item
$(\varphi \to \psi ) \to (\varphi \wedge \chi \to \psi)$

\item
$\varphi \vee \psi \to \varphi \vee (\varphi \vee \psi)$

\item
$\varphi \vee (\varphi \vee \psi) \to \varphi \vee \psi$

\item
$\varphi \to (\psi \to \varphi \wedge \psi)$

\item
$\varphi \wedge \psi \to \psi \wedge \varphi$

\item
$(\varphi \wedge \psi) \vee \varphi \to \varphi$

\item
$\varphi \to (\varphi \wedge \psi) \vee \varphi$

\item
$(\varphi \to (\psi \wedge \chi ))\to (\varphi \to \psi )\wedge (\varphi \to \chi)$

\item
$(\varphi \to \psi )\wedge (\varphi \to \chi)\to (\varphi \to (\psi \wedge \chi ))$


\item
$(\varphi \vee \psi \to \chi) \to ((\varphi \to \chi) \wedge (\psi \to \chi))$

\item
$(\varphi \vee \psi ) \wedge (\psi \to \varphi) \to \varphi$

\item
$(\varphi \to \chi)\wedge (\psi \to \chi) \to (\varphi \vee \psi \to \chi)$



\end{enumerate}


\section*{Constructies met bewijzen}

Geef (informele) bewijzen voor de volgende uitspraken.

\begin{enumerate}

\item
Als $\vdash \varphi \wedge \psi$, dan $\vdash \varphi$ en 
$\vdash \psi$.

\item
Als $\vdash \varphi \vee \psi$ en $\vdash \neg \varphi$, dan 
$\vdash \psi$.


\item
Als $\vdash \varphi$ en $\vdash \psi$, dan $\vdash \varphi \wedge \psi$.


\item
Als $\vdash \varphi \to \psi$ en $\vdash \neg \psi$, dan ook
$\vdash \neg \varphi$.

\item
Als $\vdash \varphi \to \neg \varphi$ en $\vdash \neg \varphi \to \varphi$ (dit was
een mogelijke definitie van paradox), dan
$\vdash \bot$. 

\item
Als $\vdash \varphi \to \neg \varphi$, dan $\vdash \neg \varphi$.

\end{enumerate}


\section*{Valse honden en baasjes}

In deze opgaven vindt kwantificatie plaats over de verzameling
van honden en mensen. We gebruiken de volgende vertaalsleutel.


\begin{center}
\begin{tabular}{ll}
$H(x)$ & $x$ is een hond\\
$V(x)$ & $x$ is vals\\
$B(x,y)$ & $x$ is het baasje van $y$\\
\end{tabular}
\end{center}

\section*{Vertalingen}
Vertaal de volgende zinnen naar predicaatlogische formules.

\begin{enumerate}
\item
Iedere hond is vals


\item
Geen hond is vals



\item
Sommige honden zijn
vals (er is een hond die vals is)

\item
Sommige honden zijn vals en sommige honden zijn niet  vals

\item
Iedere hond heeft een baasje


\item
Sommige honden hebben een baasje (Er zijn honden met een baasje)

\item
Ieder is z'n eigen baas


\item
Als een hond vals is, dan is z'n baas vals


\item
Als een hond vals is, dan is z'n baas een hond

\item
De baas van een hond is niet ook een hond

\item
Soms is de hond de baas van het baasje


\item
Als iemand een valse baas heeft, dan heeft 'ie een hond


\item
Als iemand een valse baas heeft, dan heeft 'ie een valse hond

\item
Een baasje is nooit een hond

\item
Iedere baas is een hond






\end{enumerate}

\section*{Predicaatlogica en natuurlijke deductie}

Bewijs met behulp van natuurlijke deductie de volgende uitspraken.

\begin{enumerate}
\item
$\vdash \forall x (\varphi (x)\rightarrow \psi (x))
\rightarrow 
(\forall x \varphi (x)\rightarrow \forall x \psi (x))$
\item
$\vdash \forall x \varphi (x) \rightarrow
\neg \forall x \neg \varphi (x)
$
\item
$\vdash \exists x\ \varphi (x) \wedge \psi \rightarrow
\exists x (\varphi (x) \wedge \psi )\ \ \ \ x\not \in {\sf FV}(\psi )$
\item
$\vdash 
\exists x A(x)\vee \exists x B(x)\rightarrow
\exists x (A(x) \vee B(x) )$
\item
$\vdash  \forall x (\varphi (x) \vee \psi)  \rightarrow
\forall x \varphi (x) \vee \psi \ \ \ \ x\not \in {\sf FV}(\psi )
$
\item
$\vdash (\forall x \varphi (x) \vee \psi)  \rightarrow
\forall x (\varphi (x) \vee \psi)\ \ \ \ x\not \in {\sf FV}(\psi )
$
\item
$\vdash
\forall x \varphi (x) \rightarrow \neg \exists x \neg \varphi (x)
$
\item
$\vdash \exists x \neg \varphi (x) \rightarrow 
\neg \forall x \varphi (x)$
\item
$\vdash
\neg \forall x \varphi (x)\rightarrow 
\exists x \neg \varphi (x)
$

\end{enumerate}

\section*{Constructieve bewijzen}

Geef constructieve natuurlijke deductie bewijzen voor de volgende tautologie\"en.

\begin{enumerate}
\item
$
\neg \neg \neg \psi \to \neg \psi
$

\item
$
\exists x\ (\phi (x) \vee \psi (x)) \to \exists x \ \phi (x) \vee \exists x \ \psi (x)
$

\item
$
 \exists x \ \phi (x) \vee \exists x \ \psi (x) \to
\exists x\ (\phi (x) \vee \psi (x)) 
$

\item
$
\forall x\ (\phi (x) \to \psi) 
\to
(\exists x\ \phi (x) \to \psi)
$

\item
($\exists x\ \phi (x) \to \psi)
\to
\forall x\ (\phi (x) \to \psi) 
$

\item
$\forall x\ (\phi (x) \to \psi) 
\to
\forall x\ (\phi (x) \to \psi) 
$
\end{enumerate}



\end{document}