\documentclass{beamer}
\usepackage[utf8x]{inputenc}
\usepackage{default}
\usepackage[ngerman]{babel}
\usepackage{colortbl}
%\mode<presentation>
%{
%  \usetheme{Warsaw}
%  \setbeamercovered{transparent}
%}
\usepackage{times}
\usepackage[T1]{fontenc}
\title{Formale Logik - SoSe 2012}
\subtitle{Versuch einer Zusammenfassung}
\author{Malvin Gattinger}
\date{}
\subject{Formale Logik - SoSe 2012} % PDF only

% Am Anfang jedes Unterabschnitts nochmal Gliederung:
\AtBeginSubsection[]
{
  \begin{frame}<beamer>{Gliederung}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}

% % Aufzählungen immer schrittweise:
%\beamerdefaultoverlayspecification{<+->}

\include{beamer_bar}

\begin{document}

\newcommand{\so}{\rightarrow}

\begin{frame}
  \vspace{-1cm}
  \titlepage
  \vspace{-2cm}
  \begin{center}
    \includegraphics[scale=0.3]{img/purity_2.png} \\
    \begin{tiny}http://xkcd.com/435/    \end{tiny}
  \end{center}
\end{frame}

\begin{frame}{Gliederung}
  \tableofcontents%[pausesections]
\end{frame}

\section{Einleitung}

\subsection{Was ist Logik?}

\begin{frame}
  \begin{itemize}
    \item Logik ist die Wissenschaft von den Gesetzen des Wahrseins und des
      Fürwahrhaltens.
    \item Logik beschreibt eine ideale Form des Denkens und Schließens.
    \item Logik beschäftigt sich \emph{nicht} damit wie wir tatsächlich denken.
  \end{itemize}
\end{frame}

\begin{frame}
  \begin{itemize}
    \item Logik ist die Wissenschaft von den Gesetzen des Wahrseins und des
      Fürwahrhaltens.
    \item Logik beschreibt eine ideale Form des Denkens und Schließens.
    \item Logik beschäftigt sich \emph{nicht} damit wie wir tatsächlich denken.
  \end{itemize}
  \begin{center}
    \includegraphics[scale=0.35]{img/Reality-Sucks.jpg}
  \end{center}
\end{frame}

\section{Begriffsklärungen}
\subsection{Sätze und Wahrheit}
\begin{frame}
  \begin{itemize}
    \item Aussagesätze können wahr oder falsch sein.
    \item \emph{Wahrheit} ist eine Eigenschaft von Aussagesätzen.
    \item Es gibt genau zwei Wahrheitswerte: Wahr, Falsch.
  \end{itemize}
  \begin{flushright}
    \includegraphics[scale=0.5]{img/popcorn.jpg}
  \end{flushright}
\end{frame}

\subsection{Argumente und Gültigkeit}
\begin{frame}
  \begin{itemize}
    \item Ein Argument ist eine Liste von Sätzen, von denen einer als Konklusion
      ausgewiesen ist. Die anderen Sätze heißen Prämissen.
    \item Ein Argument ist gültig genau dann, wenn es rational ist unter der
      Annahme, dass die Prämissen wahr sind, auch die Konklusion für wahr zu
      halten.
    \item Ein Argument ist schlüssig genau dann, wenn es gültig ist und seine
      Prämissen wahr sind.
    %FIXME Venn
  \end{itemize}
\end{frame}

\begin{frame}
  Argumente können auch mal überhaupt keine Prämissen haben! Ein solches
  Argument das nur aus einer Konklusion besteht ist gültig wenn diese eine
  Tautologie ist. Damit ist es auch schlüssig, denn alle (=keine) seine
  Prämissen sind wahr. Solche Argumente heißen auch Theoreme.
\end{frame}

\begin{frame}
  Argumente können auch mal überhaupt keine Prämissen haben! Ein solches
  Argument das nur aus einer Konklusion besteht ist gültig wenn diese eine
  Tautologie ist. Damit ist es auch schlüssig, denn alle (=keine) seine
  Prämissen sind wahr. Solche Argumente heißen auch Theoreme.
  \begin{center}
    \includegraphics[scale=0.5]{img/dafuq.jpg}
  \end{center}
  Beispiel:
  \begin{center}
    $ \vdash p \rightarrow ( q \rightarrow p ) $
  \end{center}
\end{frame}

\begin{frame}
  \begin{center}
    Also was wahr nochmal gültig?
  \end{center}
\end{frame}

\begin{frame}
  \begin{center}
    \vspace{-1cm}
    \includegraphics[scale=0.3]{img/bart-simpson-wahrheit-gueltigkeit.png}
  \end{center}
\end{frame}

\begin{frame}
  \begin{center}
    \includegraphics[scale=0.45]{img/true_argument.jpg}
  \end{center}
\end{frame}

\section{Aussagenlogik}
\subsection{PropLog}
\begin{frame}


\begin{columns}
  \begin{column}{0.7\textwidth}
  PropLog verwendet folgende Zeichen:
  \begin{enumerate}
    \item $ p, q, r, ... $ für Elementarsätze
    \item Junktoren:
      $\begin{array}{cccccc}
	\neg & \wedge & \vee  \\
	Negation & Konjunktion & Disjunktion \\
	``nicht'' & ``und'' & ``oder'' \\
      \end{array}$
      \bigskip
      $\begin{array}{cccccc}
	\rightarrow & \leftrightarrow \\
	Konditional & Bikonditional \\
	``wenn dann'' & ``genau \ dann \ wenn''
      \end{array}$
  \end{enumerate}
  Beispiel-Satz: ``Wenn Franz Erdbeer- oder Schokoladen-Eis isst, dann geht er
  nicht spazieren.''\\
  $ p $ : Franz isst Erdbeer-Eis. \\
  $ q $ : Franz isst Schokoladen-Eis. \\
  $ r $ : Franz geht spazieren.
  \begin{center}
    $ ( p \vee q ) \rightarrow \neg r $
  \end{center}

  \end{column}
  \begin{column}{0.3\textwidth}
\includegraphics[scale=0.6]{img/disjunction-ice.jpg}
  \end{column}

\end{columns}

\end{frame}

\subsection{Wahrheitstabellen}
\begin{frame}
  Beispiel-Aufgabe: \\ Prüfen Sie mit Hilfe einer Wahrheitstabelle ob der
  folgende Satz logisch wahr ist.

 \begin{center}
  $ ( ( p \rightarrow q ) \land \lnot q ) \rightarrow \lnot p $ \\
  \vspace{0.5cm}
  $\begin{array}{|c|c|c|c|c|c|c|c|c|}
  \hline
  p & q & p \rightarrow q & \lnot q & ( p \rightarrow q ) \land \lnot q &
  \lnot p & ( ( p \rightarrow q ) \land \lnot q ) \rightarrow \lnot p \\
  \hline
  W & W & W & F & F & F & W \\
  W & F & F & W & F & F & W \\
  F & W & W & F & F & W & W \\
  F & F & W & W & W & W & W \\
  \hline
  \end{array}$ \\
 \end{center}
  \begin{flushright}
    \includegraphics[scale=0.15]{img/truestory.jpg}
  \end{flushright}
\end{frame}


\subsection{Semantische Bäume}

\begin{frame}

  Mit einem semantischen Baum lässt sich (nur!) die Frage beantworten:
  \begin{center}
  \begin{LARGE}Ist dieser Satz eine Kontradiktion?\end{LARGE}
  \end{center}

  \emph{SEMANTISCHE} Bäume, \\ denn die Grundfrage für alle 9 Regeln ist: \\
  \begin{center}
    \begin{Large}Was heißt es, dass dieser Satz wahr ist?\end{Large}
  \end{center}
\end{frame}

\begin{frame}
  \begin{center}
    \includegraphics[scale=0.8]{img/hipster-tree.jpg}
  \end{center}
\end{frame}

\begin{frame}
  Beispiel-Aufgabe: \\ Prüfen Sie mit Hilfe eines semantischen Baums ob der 
  folgende Satz logisch wahr ist.
  \begin{center}
    $ ( \lnot p \so \lnot q) \so (q \so p) $
  \end{center}
  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}$ \\
  Die Floskel zum auswendig lernen lautet:
  \emph{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{frame}

\begin{frame}
  Beispiel-Aufgabe: \\ Prüfen Sie mit Hilfe eines semantischen Baums ob der
  folgende Satz 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{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}$ \\

  \emph{Der Baum bleibt offen, der negierte Satz ist also keine Kontradiktion.
  Der ursprüngliche, nicht-negierte Satz ist also keine Tautologie.}
\end{frame}


\subsection{Beweise im Kalkül}

\begin{frame}
  \begin{columns}
    \begin{column}{0.5\textwidth}
      10 ``einfache'' Schlussregeln:
      \begin{center}
	$\begin{array}{rrrrr}
	  \land I & \land E & \vee I & \vee E & A \\
	  \so I & \so E & \leftrightarrow I & \leftrightarrow I & RAA \\
	\end{array}$ \\
      \end{center}
      Lesen! Lernen! Anwenden! Verstehen!
    \end{column}
    \begin{column}{0.5\textwidth}
      \includegraphics[scale=0.4]{img/lerntrichter.jpg}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \begin{columns}
    \begin{column}{0.5\textwidth}
      Beispiel-Aufgabe: \\ Beweisen Sie das folgende Argument:
      \begin{center}
	$ p \so \lnot q , \ \lnot p \so \lnot r \ \vdash \ \lnot ( q \land r ) $
      \end{center}
      \definecolor{myg}{RGB}{210,210,210}
      \arrayrulecolor{myg}
      $\begin{array}{llll}
      1   & (1) & p \so \lnot q        & A \\
      2   & (2) & \lnot p \so \lnot r  & A \\
      & ? \\
      & ? \\
      & ? \\
      & ? \\
      & ? \\
      & ? \\
      & ? \\
      & ? \\
      & ? \\
      & ? \\
      \hline
      1,2 & (??) & \neg ( q \land r )  & ? \\
      \end{array}$
    \end{column}
    \begin{column}{0.5\textwidth}
      \includegraphics[scale=0.3]{img/profit.jpg}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  Falls es mal nicht klappt ...
\end{frame}

\begin{frame}
  \begin{center}
    \includegraphics[scale=0.5]{img/plan_b.jpg}
  \end{center}
\end{frame}

\begin{frame}
  \begin{columns}
    \begin{column}{0.6\textwidth}
      Beispiel-Aufgabe: \\ Beweisen Sie das folgende Argument:
      \begin{center}
	$ p \so \lnot q , \lnot p \so \lnot r \vdash \lnot ( q \land r ) $
      \end{center}
      \definecolor{myg}{RGB}{210,210,210}
      \arrayrulecolor{myg}
      $\begin{array}{llll}
      1   & (1) & p \so \lnot q        & A \\
      2   & (2) & \lnot p \so \lnot r  & A \\
      \hline
      3   & (3) & q \land r            & A \\
      3   & (4) & q                    & 3 \land E \\
      4   & (5) & r                    & 3 \land E \\
      \hline
      6   & (6) & p                    & A \\
      1,6 & (7) & \neg q              & 1,6 \so E \\
      1,3 & (8) & \neg p              & 4,7 RAA (6) \\
      \hline
      9   & (9) & \neg p              & A \\
      2,9 & (10) & \neg r             & 2,9 \so E \\
      2,3 & (11) & p                   & 4,10 RAA (9) \\
      \hline
      1,2 & (12) & \neg ( q \land r )  & 8,11 RAA (3) \\
      \end{array}$
    \end{column}
    \begin{column}{0.3\textwidth}
      \includegraphics[scale=0.4]{img/longcat.png}
    \end{column}
  \end{columns}
\end{frame}

\section{Prädikatenlogik}
\subsection{PredLog}
\begin{frame}
  \emph{PredLog} verwendet folgendes Vokabular:
  \begin{itemize}
   \item Alles was es in \emph{PropLog} schon gab
   \item Prädikate: $ F $ , $ G $ , $ H^3 $ ...
   \item Individuenkonstanten: $ a $ , $ b $ , ...
   \item Existenz und Allquantor: $ \exists $ , $ \forall $
   \item Individuenvariablen: $ x $ , $ y $, ...
   \item Das Identitätszeichen: $ = $
  \end{itemize}

\end{frame}


\subsection{Beweise im Kalkül}
\begin{frame}
  6 weitere Regeln zur Einführung und Beseitigung der 3 neuen Zeichen: \\
  \begin{center}
    $\begin{array}{lll}
      \forall I & \exists I & = I \\
      \forall E & \exists E & = E \\
    \end{array}$
  \end{center}
\end{frame}

\begin{frame}
  Beispiel-Aufgabe:\\
  Beweisen Sie folgende beiden Satzfolgen:
  \begin{center}
    $ \forall x ( P x \so q )  \dashv \vdash  \exists x P x \so q $
  \end{center}
\end{frame}

\begin{frame}
  $ \vdash $ : \\
  $\begin{array}{llll}
  1     & (1) & \forall x ( P x \so q )             & A \\
  2     & (2) & \exists x P x                       & A \\
  3     & (3) & P a                                 & A \\
  1     & (4) & P a \so q                           & 1 \forall E \\
  1,3   & (5) & q                                   & 3,4 \so E \\
  1,2   & (6) & q                                   & 2,5 \exists E ( 3 ) \\
  1     & (7) & \exists x P x \so q                 & 6 \so I (2) \\
  \end{array}$
\end{frame}

\begin{frame}
  $ \dashv $ : \\
  $\begin{array}{llll}
  1     & (1) & \exists x P x \so q                 & A \\
  2     & (2) & P a                                 & A \\
  2     & (3) & \exists x P x                       & 2 \exists I \\
  1,2   & (4) & q                                   & 1,3 \so E \\
  1     & (5) & Pa \so q                            & 5 \so I (2) \\
  1     & (6) & \forall x ( P x \so q )             & 5 \forall I \\
  \end{array}$
\end{frame}


\begin{frame}
\begin{center}
  \includegraphics{img/success.jpg}
\end{center}\end{frame}

\subsection{Gegenmodelle}
\begin{frame}
  Im Kalkül können Argumente nur bewiesen, aber nicht widerlegt werden! Die
  Tatsache, dass wir keinen Beweis finden zeigt \emph{nicht} dass das Argument
  ungültig ist.

  In diesem Fall konstruieren wir ein Gegenmodell indem wir eine mögliche /
  denkbare Welt erfinden.

  Eine Interpretation (Modell) besteht immer aus:
  \begin{itemize}
    \item Universum
    \item Extensionen für Prädikate
    \item Wahrheitswerten für Elementarsätze
  \end{itemize}

\end{frame}

\begin{frame}
  \begin{center}
    \includegraphics[scale=0.5]{img/philosoraptor-fiction.jpg}
  \end{center}
\end{frame}

\begin{frame}
  \begin{center}
    \includegraphics[scale=0.5]{img/honk_iff.jpg}
  \end{center}
  \begin{center}
    \url{http://w4eg.de/malvin/uni/logik12}
  \end{center}
\end{frame}

\end{document}
