BuK/IIm19/Spickzettel

Wiki-Quelltext dieser Seite.

= Vorlesung 1: Vorbereitungen =

== Aussagenlogik ==

'''Aussage:''' Satz, der w oder f sein kann

'''Aussageformen:''' Variablen für Aussagen, deren Belegung mit w oder f erfolgen kann

'''Verknüpfung von Aussagen:''' Konstruktion zusammengesetzer Ausdrücke durch Verwendung von Junktoren


'''Sprache der aussagenlogischen Ausdrücke'''

1. Die Zeichen ''w'' und ''f'' sind aussagenlogische Ausdrücke.

2. Lateinische Kleinbuchstaben (abzählbar unendlich viele) sind aussagenlogische Ausdrücke.

3. Sind ''A'' und ''B'' aussagenlogische Ausdrücke, so sind es auch $(A), \lnot A, A \land B, A \lor B, A \rightarrow B$ und $A \leftrightarrow B$

4. Keine anders konstruierten Zeichenketten sind aussagenlogische Ausdrücke.


'''Junktoren'''

{| border="1px" cellpadding="8" cellspacing="0"
|-style="text-align: center;background-color:lightgrey;"
|| || || Negation || Konjunktion || Disjunktion || Subjunktion || Bijunktion
|-style="text-align: center;"
|| || || nicht || und || oder || wenn ... dann ... || ... genau dann, wenn ...
|-style="text-align: center;"
|| $A$ || $B$ || $\lnot A$ || $A \land B$ || $A \lor B$ || $A \rightarrow B$ || $A \leftrightarrow B$
|-style="text-align: center;"
|| w || w || f || w || w || w || w
|-style="text-align: center;"
|| w || f || f || f || w || f || f
|-style="text-align: center;"
|| f || w || w || f || w || w || f
|-style="text-align: center;"
|| f || f || w || f || f || w || w
|-
|}

'''Achtung!:''' $\Rightarrow$ (Implikation) und $\Leftrightarrow$ (Äquivalenz) gehören nicht zur ''Objektsprache'', sondern sind wichtige Elemente der ''Metasprache''!


'''Erfüllbar:''' Eine Aussagenform ist ''erfüllbar'', wenn sie für mind. eine Belegung aller aussagenlogischen Variablen wahr ist.

'''Erfüllungsmenge:''' Alle Belegungstupel, welche die betrachtete Aussagenform wahr werden lassen.

'''Tautologie:''' Eine n-stellige Aussagenform heißt allgemeingültig oder Tautologie, wenn sie für alle $2^n$ Belegungen wahr ist.

 To be continued...

= Vorlesung 2: Berechenbarkeitsbegriff =

Ein '''Algorithmus''' ist:

* ein schrittweise ablaufendes Verfahren
* das Eingabedaten zu Ausgabedaten transformiert
* au eine Klasse von Problemen anwendbar
* eindeutig, endlich und terminiert


'''Berechenbarkeit:''' Eine Funktion f ist berechenbar, wenn es  einen Algorithmus gibt, der für jedes x € $D_f$ den zugehörigen Funktionswert $f(x)$ effektiv ermittelt.


'''Nicht formalisierbar bzw. nicht effizient:'''
# Unzugängliches (wenigstens) für Computer
# Praktisch Unmögliches


'''Cantorsches Diagonalisierungsverfahren 1. Art''' für ''Abzählbar unendliche Mengen''

'''Cantorsches Diagonalisierungsverfahren 2. Art''' für ''Überabzählbar unendliche Mengen''


'''Algorithmen und Programme'''

* Es gibt höchstens so viele Algorithmen wie Programme.
* Es gibt höchstens abzählbar unendlich viele Programme.
* Also stehen höchstens abzählbar unendlich viele Algorithmen überabzählbar unendlich vielen Wortfunktionen gegenüber.

'''Fazit (Kardinalzahlargument):''' Es gibt überabzählbar unendlich viele nicht berechenbare Funktionen bzw. unentscheidbare Prädikate.

= Vorlesung 3: Entscheidbarkeit=

== Entscheidbarkeit ==

Berechenbarkeit - Funktionen

Entscheidbarkeit - Mengen


Entscheidungsverfahren stoppen in endlicher Zeit und geben wahr oder falsch zurück.

Es gibt überabzählbar viele unlösbare Probleme


''' Relative Entscheidbarkeit'''

Eine Menge $M_1$ ist ''relativ entscheidbar'' zu $M_2$ ($M_1 , M_2 \subseteq A^*$), wenn die ''charakteristische Funktion $XM_1 , M_2$ mit

 $XM_1 , M_2$ (w
 = wahr, wenn $w € M_1$
 = falsch, wenn $w € M_2$ \ $M_1$

eine total berechenbare Funktion ist.


''' Absolute Entscheidbarkeit'''

Eine Menge $M \subseteq A^*$ ist (absolut) ''entscheidbar'', wenn M zu $A^*$ relativ entscheidbar ist, d.h. wenn $X_M,A^*$ ,kurz $X_M$ mit

 $X_M (w)$
 = wahr, wenn $w € M$
 = falsch, wenn $w € A^*$ \ $M$

eine total berechenbare Funktion ist.


Mit anderen Worten: M ist entscheidbar, wenn es eine Prozedur ''chi'' gibt, die für jedes eingegebene Wort ''w'' aus $A^*$ nach endlicher Zeit stoppt und entweder #t (w € M) oder #f (w € M) ausgibt.

 > (chi "bin_in_M")
$\#t$

 > (chi "bin_nicht_in_M")
$\#f$


'''Aufzählbarkeit'''

Eine Menge $M \subseteq A^*$ heißt (rekursiv) aufzählbar, wenn es entweder eine total berechenbare surjektive Funktion $f : \mathbb{N} \mapsto M$ gibt, oder es gilt $M = \empty$  Man nennt f eine
'''Aufzählprozedur''' oder ein '''Aufzählverfahren''' von M.