\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}

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

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

\newcommand{\so}{\rightarrow}

\section*{Aufgabe 1}

\begin{minipage}[t]{0.43\textwidth}
a) \\
$\begin{array}{rcc}
1. & \lnot ( ( \lnot p \so \lnot q) \so (q \so p) ) &
(A) \\
2. & \lnot p \so \lnot q & (1) \\
3. & \lnot ( q \so p ) & (1) \\
4. & q & (3) \\
5. & \lnot p & (3) \\
6. & p \hspace{1cm} 7. \hspace{0.2cm} \lnot q & (2) \\
   & X                   \hspace{1.6cm} X  \\
\end{array}$ \\
Der negierte Satz liefert ausschließlich Widersprüche, d.h er ist eine
Kontradiktion. Der ursprüngliche, nicht-negierte Satz ist also eine Tautologie.
\end{minipage}
\hspace{0.01\textwidth}
\begin{minipage}[t]{0.54\textwidth}
b) \\
$\begin{array}{rcc}
1. & \lnot ( ( \lnot p \so q) \land (q \so r) \so
( \lnot p \so \lnot r) ) & (A) \\
2. & ( \lnot p \so q) \land (q \so r) & (1) \\
3. & \lnot ( \lnot p \so \lnot r ) & (1) \\
4. & \lnot p \so q & (2) \\
5. & q \so r & (2) \\
6. & \lnot p & (3) \\
7. & r & (3) \\
   & 8. p \hspace{1.4cm} 9. q & (4) \\
   & \hspace{1.2cm} X \hspace{1cm} 10. \lnot q \hspace{0.5cm}
11. \hspace{0.2cm} r & (5) \\
   & \hspace{3.3cm} X \hspace{1cm} ? \\
\end{array}$ \\
Der Baum bleibt offen, der negierte Satz ist also keine Kontradiktion.
Der ursprüngliche, nicht-negierte Satz ist also keine Tautologie.
\end{minipage}

\bigskip

c) \\
Das Argument $ \lnot p \so q , q \so r \models  \lnot p \so \lnot r $ ist
gültig, genau dann wenn der Satz \\ $ ( \lnot p \so q) \land (q \so r) \so
( \lnot p \so \lnot r) $ logisch wahr ist. \\

$\begin{array}{rcc}
1. & \lnot ( ( \lnot p \so q) \land (q \so r) \so ( \lnot p \so \lnot r) ) &
(A) \\
2. & ( \lnot p \so q ) \land (q \so r) & (1) \\
3. & \lnot ( \lnot p \so \lnot r )     & (1) \\
4. & \lnot p \so q & (2) \\
5. & q \so r & (2) \\
6. & \lnot p & (3) \\
7. & r & (3) \\
   & 8. p \hspace{2.5cm} 9. q & (4) \\
   & \hspace{1cm} X \hspace{1.5cm} 
     10. \lnot q \hspace{0.5cm} 11. r  & (5) \\
   & \hspace{2.5cm} X \\
\end{array}$ \\

Der negierte Satz führt nicht ausschließlich zu Widersprüchen, ist also keine
Kontradiktion. Der ursprüngliche, nicht-negierte Satz ist daher keine
Tautologie und das Argument somit ungültig.

\newpage

\section*{Aufgabe 2}

a) $ p, q \vdash p \land q $ \\
$\begin{array}{llll}
1   & (1) & p                    & A \\
2   & (2) &  \lnot  q              & A \\
1,2 & (3) & p \land  \lnot  q      & 1, 2 \land I  \\
\end{array}$

\bigskip

b) $ p \vee q , \lnot q \vee r , \lnot p \vdash r $ \\
$\begin{array}{llll}
1     & (1) & p \vee q                 & A \\
2     & (2) & \lnot q \vee r           & A \\
3     & (3) & \lnot p                  & A \\
1,3   & (4) & q                        & 1,3 \vee E \\
1,2,3 & (5) & r                        & 2,4 \vee E \\
\end{array}$

\bigskip

c) $ \lnot p \leftrightarrow q , \lnot q \vee r \vdash \lnot p \so r $
\\
$\begin{array}{llll}
1     & (1) & \lnot p \leftrightarrow q    & A \\
2     & (2) & \lnot p                      & A \\
3     & (3) & \lnot q \vee r               & A \\
1     & (4) & \lnot p \so q        & 1 \leftrightarrow E \\
1,2   & (5) & q                            & 2,4 \so E \\
1,2,3 & (6) & r                            & 3,5 \vee E \\
1,3   & (7) & \lnot p \so r        & 6 \so I (2) \\
\end{array}$

\end{document}