\documentclass[a4paper,12pt]{scrartcl}

\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[ngerman]{babel}
\usepackage{fontenc}
\usepackage[pdftex]{graphicx}
\usepackage[left=2cm,right=2cm,top=3cm,bottom=4cm]{geometry}

\usepackage[usenames]{color}
\usepackage{colortbl}

\author{Malvin Gattinger}
\title{Logik SS2012 - Übungsblatt 9}
\date{}

\begin{document}
\parindent=0cm
\maketitle

\newcommand{\so}{\rightarrow}

\section*{Aufgabe 1}

(i)

\begin{tabular}{lll}

    & Satz & Expansion in $ U: \{a\} $ \\

(a) & $ \forall x Fx $ & $Fa$ \\

(b) & $ \forall xFx \so \exists x Gx $ & $ Fa \so Ga $ \\

(c) & $ \exists x (Fx \vee Hx) $ & $ Fa \vee Ha $ \\

(d) & $ \lnot ( \forall x G x \leftrightarrow \exists x ( H x \land \lnot F x )
) $ &
    $ \lnot ( Ga \leftrightarrow ( Ha \land \lnot Fa ) ) $ \\

\end{tabular}

\bigskip

(ii)

\begin{tabular}{lll}

    & Satz & Expansion in $ U: \{a,b,c\} $ \\

(a) & $ \forall x Fx $ &$ Fa \land Fb \land Fc $ \\

(b) & $ \forall xFx \so \exists x Gx $ &
    $ ( Fa \land Fb \land Fc ) \so ( Ga \vee Gb \vee Gc ) $\\

(c) & $ \exists x (Fx \vee Hx) $ &
    $ ( Fa \vee Ha ) \vee ( Fb \vee Hb ) \vee ( Fc \vee Hc ) $ \\

(d) & $ \lnot ( \forall x G x \leftrightarrow \exists x ( H x \land \lnot F x )
) $ &
    $ \lnot ( Ga \land Gb \land Gc \leftrightarrow ( Ha \land \lnot Fa ) \vee
    ( Hb \land \lnot Fb ) \vee ( Hc \land \lnot Fc )  ) $ \\

\end{tabular}



\section*{Aufgabe 2}

(a) \\ U: \{a\}, F: \{a\}, G: \{\}, H: \{\} \\ P ist falsch

\begin{itemize}
 \item[(a)] $ \forall x Fx $ expandiert in U zu $Fa$ und ist wahr.

 \item[(b)] $ \forall xFx \so \exists x Gx $ expandiert in U zu $ Fa \so Ga $.
  \\
  $\begin{array}{|c|c|c|}
  \hline
  Fa & Ga & Fa \so Ga \\
  \hline
  W & F & F \\
  \hline
  \end{array}$ \\

 \item[(c)] $ \exists x (Fx \vee Hx) $ expandiert in U zu  $ Fa \vee Ha $ \\
  $\begin{array}{|c|c|c|}
  \hline
  Fa & Ha & Fa \vee Ha \\
  \hline
  W & F & W \\
  \hline
  \end{array}$ \\

 \item[(d)] $ \lnot ( \forall x G x \leftrightarrow \exists x ( H x \land \lnot
    F x ) ) $
  expandiert in U zu
  $ \lnot ( Ga  \leftrightarrow ( Ha \land \lnot Fa ) ) $ . \\
  $\begin{array}{|c|c|c|c|c|c|c|}
  \hline
  Fa & Ga & Ha & \lnot Fa & Ha \land \lnot Fa &
    Ga  \leftrightarrow ( Ha \land \lnot Fa ) &
    \lnot ( Ga  \leftrightarrow ( Ha \land \lnot Fa ) ) \\
  \hline
  W & F & F & F & F & W & F \\
  \hline
  \end{array}$ \\

\end{itemize}

\bigskip

(b) \\ U: \{a,b\}, F: \{a\}, G: \{a,b\}, H: \{\} \\ P ist wahr

\begin{itemize}
 \item[(a)] $ \forall x Fx $ expandiert in U zu $ Fa \land Fb $ . \\
  $\begin{array}{|c|c|c|c|}
  \hline
  Fa & Fb & Fa \land Fb \\
  \hline
  W & F & F \\
  \hline
  \end{array}$ \\

 \item[(b)] $ \forall xFx \so \exists x Gx $ expandiert in U zu
  $ ( Fa \land Fb ) \so ( Ga \vee Gb ) $ . \\
  $\begin{array}{|c|c|c|c|c|c|c|}
  \hline
  Fa & Fb & Ga & Gb & Fa \land Fb & Ga \vee Gb & Fa \land Fb \so Ga \vee Gb \\
  \hline
  W & F & W & W & F & W & W \\
  \hline
  \end{array}$ \\

 \item[(c)] $ \exists x (Fx \vee Hx) $ expandiert in U zu
  $ ( Fa \vee Ha ) \vee ( Fb \vee Hb ) $ . \\
  $\begin{array}{|c|c|c|c|c|c|c|}
  \hline
  Fa & Ha & Fb & Hb & Fa \vee Ha & Fb \vee Hb &
    ( Fa \vee Ha ) \vee ( Fb \vee Hb )\\
  \hline
  W & F & F & F & W & F & W \\
  \hline
  \end{array}$ \\

 \item[(d)] $ \lnot ( \forall x G x \leftrightarrow \exists x ( H x \land \lnot
F x ) ) $
  expandiert in U zu 
  $ \lnot ( ( Ga \land Gb ) \leftrightarrow
    ( Ha \land \lnot Fa ) \vee ( Hb \land \lnot Fb ) ) $ . \\
  $\begin{array}{|cccccccccccccccccccc|}
  \hline
\lnot & (
( & Ga & \land & Gb & ) & \leftrightarrow & ( & Ha & \land & \lnot & Fa & ) &
\vee & ( & Hb & \land & \lnot & Fb & ) ) \\
  \hline
  & & W &   & W &   &   &   & F &   & F & W &   &   &   & F &   & W & F & \\
  & &   & W &   &   &   &   &   & F &   &   &   &   &   &   & F &   &   & \\
  & &   & W &   &   &   &   &   &   &   &   &   & F &   &   &   &   &   & \\
  & &   &   &   &   & F &   &   &   &   &   &   &   &   &   &   &   &   & \\
 W & &  &   &   &   &   &   &   &   &   &   &   &   &   &   &   &   &   & \\
  \hline
  \end{array}$ \\

\end{itemize}

\section*{Aufgabe 3}

(a) $ \forall x Fx \so  \forall xGx \vdash  \forall x(Fx \so Gx) $

Für das Universum mit nur einem Element $U:\{a\}$ haben Prämisse und Konklusion
die gleiche Expansion, daher benötigen wir für ein Gegenmodell mindestens
zwei Elemente. Betrachten wir also die Expansionen in $U:\{a,b\}$: \\
Prämisse: $ ( Fa \land Fb ) \so ( Ga \land Gb ) $ \\
Konklusion: $ ( Fa \so Ga ) \land ( Fb \so Gb ) $

\smallskip

Nun können wir zum Beispiel $F: \{a\}$, $G: \{b\}$ wählen und erhalten damit:

\smallskip

Prämisse:\\
$\begin{array}{|ccccccccccc|}
  \hline
  ( & Fa & \land & Fb & ) & \so & ( & Ga & \land & Gb & ) \\
  \hline
  & W &   & F & &   & & F &   & W & \\
  &   & F &   & &   & &   & F &   & \\
  &   &   &   & & W & &   &   &   & \\
  \hline
\end{array}$

\smallskip

Konklusion:\\
$\begin{array}{|ccccccccccc|}
  \hline
  ( & Fa & \so & Ga & ) & \land & ( & Fb & \so & Gb & ) \\
  \hline
  & W &   & F & &   & & F &   & W & \\
  &   & F &   & &   & &   & W &   & \\
  &   &   &   & & F & &   &   &   & \\
  \hline
\end{array}$

\smallskip

In der Interpretation $ U:\{a,b\}, F:\{a\}$, $G:\{b\} $ sind die Prämisse des
Arguments wahr und die Konklusion falsch. Also ist das Argument ungültig.


\bigskip


(b) $ \exists x (Fx \vee Gx) \vdash \forall x F x \vee \forall xGx $

Interpretation: $ U:\{a,b\}, F:\{a\}, G:\{\} $

\smallskip

Die Expansion der Prämisse $ \exists x (Fx \vee Gx) $ in $ U: \{a,b\} $ ist
$ ( Fa \vee Ga ) \vee ( Fb \vee Gb ) $ .

$\begin{array}{|ccccccccccc|}
  \hline
  ( & Fa & \vee & Ga & ) & \vee & ( & Fb & \vee & Gb & ) \\
  \hline
  & W &   & F & &   & & F &   & F & \\
  &   & W &   & &   & &   & F &   & \\
  &   &   &   & & W & &   &   &   & \\
  \hline
\end{array}$

\smallskip

Die Expansion der Konklusion $\forall x F x \vee \forall xGx$ in $ U: \{a,b\} $
ist $ ( Fa \land Fb ) \vee ( Ga \land Gb ) $ . 

$\begin{array}{|ccccccccccc|}
  \hline
  ( & Fa & \land & Fb & ) & \vee & ( & Ga & \land & Gb & ) \\
  \hline
  & W &   & F & &   & & F &   & F & \\
  &   & F &   & &   & &   & F &   & \\
  &   &   &   & & F & &   &   &   & \\
  \hline
\end{array}$

\smallskip

In der Interpretation $ U:\{a,b\}, F:\{a\}, G:\{\} $ sind die Prämisse des
Arguments wahr und die Konklusion falsch. Also ist das Argument ungültig.

\bigskip

(c) $ \forall x \exists yF ^2 xy \vdash \exists x \forall y F ^2 xy $

Interpretation: $ U:\{a,b\}, F ^2 :\{<a,a>,<b,b>\} $ 

\smallskip

Wir betrachten also die Expansionen in $U:\{a,b\}$:

Die Prämisse $ \forall x \exists y F ^2 xy $ wird epxandiert zu
$ \forall x (F^2 xa \vee F^2 xb) $  und dies wird expandiert zu
$ (F^2 aa \vee F^2 ab) \land (F^2 ba \vee F^2 bb) $ .

$\begin{array}{|ccccccccccc|}
  \hline
  ( & F^2 aa & \vee & F^2 ab & ) & \land & ( & F^2 ba & \vee & F^2 bb &  ) \\
  & W &   & F & &   & & F &   & W & \\
  &   & W &   & &   & &   & W &   & \\
  &   &   &   & & W & &   &   &   & \\
  \hline
\end{array}$

\smallskip

Die Konklusion $ \exists x \forall y F ^2 xy $ wird expandiert zu
$ \forall x (F^2 xa \land F^2 xb) $  und dies wird expandiert zu
$ (F^2 aa \land F^2 ab) \vee (F^2 ba \land F^2 bb) $ ,

$\begin{array}{|ccccccccccc|}
  \hline
  ( & F^2 aa & \land & F^2 ab & ) & \vee & ( & F^2 ba & \land & F^2 bb &  ) \\
  & W &   & F & &   & & F &   & W & \\
  &   & F &   & &   & &   & F &   & \\
  &   &   &   & & F & &   &   &   & \\
  \hline
\end{array}$

\smallskip 

In der Interpretation $ U:\{a,b\}, F ^2 :\{<a,a>,<b,b>\} $  sind die Prämisse
des Arguments wahr und die Konklusion falsch. Also ist das Argument ungültig.


\end{document}