Habel / Eschenbach Logik–13 [1]

Entscheidbarkeitsprobleme in der Logik

• Theoreme zur Entscheidbarkeit / Unentscheidbarkeit semantischer Probleme

• Aussagenlogik:

Gültigkeit, Erfüllbarkeit, Unerfüllbarkeit, Folgerbarkeit, Äquivalenz sind entscheidbar

• Prädikatenlogik:

◊ Gültigkeit, Erfüllbarkeit, Unerfüllbarkeit, Folgerbarkeit, Äquivalenz sind nicht entscheidbar

◊ Gültigkeit, Unerfüllbarkeit, Folgerbarkeit, Äquivalenz sind semi-entscheidbar

• Ausdruckskraft – Berechnungseigenschaften

• Monadische Prädikatenlogik

• Aussagenlogik – Prädikatenlogik (eine Zusammenfassung)

• Das Dilemma: Ausdruckskraft – Berechnungseigenschaften

• Logik in der Informatik: Jenseits von F1

Habel / Eschenbach Logik–13 [2]

Algorithmus

Informelle Charakterisierung:• „Ein Algorithmus ist eine präzise, d.h. in einer festgelegten Sprache abgefasste,

endliche Beschreibung eines allgemeinen Verfahrensunter Verwendung ausführbarer elementarer Verarbeitungsschritte.“ [Bauer & Goos, 1982; s.a. Folie 5 von P1]

Die intuitive Idee:• Ein Algorithmus legt fest, wie für ein vorgegebenes Problem (aus einer Klasse von

Problemen) eine Lösung berechnet wird.• Alle Schritte der Problemlösung sind durch den Algorithmus festgelegt.• Die Berechnung der Lösung ist nach einer endlichen Anzahl von Berechnungsschritten

abgeschlossen, d.h. der Algorithmus terminiert.

Die zentrale Frage:• Wie kann die Idee des Algorithmus in einer präzisen, expliziten Weise charakterisiert

werden?

Theorie der Berechenbarkeit Vorlesung F3

Habel / Eschenbach Logik–13 [3]

Theorie der Berechenbarkeit & Formalisierung des Begriffs desAlgorithmus

Die Ausgangssituation:• Gegeben ein Problem P. Gibt es einen Algorithmus, der P löst?

Prinzipiell zwei Möglichkeiten:• Es gibt einen Algorithmus, der P löst. Dies kann am besten dadurch gezeigt werden,

dass ein entsprechender Algorithmus angegeben und seine Korrektheit bewiesen wird.• Es gibt keinen Algorithmus, der P löst. Dies kann nur dadurch gezeigt werden, dass

bewiesen wird, dass es keinen derartigen Algorithmus geben kann.• Konsequenz: Es muss eine explizite Definition des Begriffs ‘Algorithmus’ existieren, um

überhaupt die Existenz eines Algorithmus’, der ein vorgegebenes Problem P löst,untersuchen zu können.

Die historische Entwicklung:• In den 20er- und 30er-Jahren: Suche nach Beweisverfahren in Logik und Mathematik.• 1936 / 1937: Formale, explizite Definitionen von Berechenbarkeit und Algorithmus:

• Alonzo Church, Stephen Kleene, Emil Post: rekursive Funktionen• Alan Turing: universal-algorithm machine

Habel / Eschenbach Logik–13 [4]

Problemklassen: Berechenbarkeit und Berechnungskomplexität

Gegeben ein Problem bzw. eine Problemklasse• Gibt es Algorithmen, die das Problem lösen?

D.h. existiert• eine rekursive Funktion, die für das Problem als Eingabe einen Ausgabewert berechnet?• eine Turing-Maschine, die für das Problem als Eingabe einen Ausgabewert berechnet?

Wenn ein derartiger Algorithmus existiert, heisst er berechenbar (computable).Das Verfahren wird als effektiv bezeichnet.

• Falls Algorithmen existieren, die das Problem effektiv lösen, dann stellt sich die Frage nachder Komplexität des Verfahrens.

Komplexitätstheorie: KomplexitätshierarchienSuche nach effizienten Verfahren.

• Fragen der Berechenbarkeit und Komplexität beziehen sich primär auf Problemklassen!

Theorien der Berechenbarkeit und Komplexität Vorlesung F3

Habel / Eschenbach Logik–13 [5]

Probleme, Algorithmen, Entscheidungsprobleme

• Ein Problem P spezifiziert eine Funktion fP : DP → RP (‘Problemfunktion’).DP spezifiziert die Probleminstanzen, RP die Lösungsinstanzen.

• Ein Algorithmus A spezifiziert / berechnet eine Funktion fA: DA → RA(‘Algorithmusfunktion’).

DA spezifiziert die Eingabeinstanzen, RA die Ausgabeinstanzen.

• Ein Problem P ist ein Entscheidungsproblem,wenn fP eine Boolesche Funktion ist, d.h. wenn RP = {0, 1} bzw. RP = {false, true}.

• Ein Algorithmus A ist ein Entscheidungsalgorithmus,wenn fA eine Boolesche Funktion berechnet.

• Problem P ist entscheidbar, wenn die Boolesche Problemfunktion fP durch einenEntscheidungsalgorithmus A berechnet wird, d.h. wenn fP = fA.

Habel / Eschenbach Logik–13 [6]

Entscheidungsprobleme in Aussagen- und Prädikatenlogik

Entscheidungsprobleme:

1. Gültigkeit einer Formel F bzw. einer endlichen Formelmenge {Fi | i ∈ Ι}

2. Erfüllbarkeit einer Formel F bzw. einer endlichen Formelmenge {Fi | i ∈ Ι}

3. Unerfüllbarkeit einer Formel F bzw. einer endlichen Formelmenge {Fi | i ∈ Ι}

4. Folgerbarkeit einer Formel G aus einer endlichen Formelmenge {Fi | i ∈ Ι}

5. Äquivalenz von zwei Formeln F und G bzw. zwei endlichen Formelmengen{Fi | i ∈ Ι} und {Gj | j ∈ J}

• Für jedes dieser Entscheidungsprobleme existiert eine aussagenlogische und eineprädikatenlogische Variante:• Für (1) – (3): DP = DA = LAL DP = DA = LPL

bzw. DP = DA = ℘(LAL) DP = DA = ℘(LPL)

• Für (4)): DP = DA = ℘(LAL) x LAL DP = DA = ℘(LPL) x LPL

Habel / Eschenbach Logik–13 [7]

Entscheidbarkeitsresultate für die Aussagenlogik

• Gültigkeit einer Formel F bzw. einer endlichen Formelmenge {Fi | i ∈ Ι}

• Erfüllbarkeit einer Formel F bzw. einer endlichen Formelmenge {Fi | i ∈ Ι}

• Unerfüllbarkeit einer Formel F bzw. einer endlichen Formelmenge {Fi | i ∈ Ι}

• Folgerbarkeit eine Formel G aus einer endlichen Formelmenge {Fi | i ∈ Ι}

• Äquivalenz von zwei Formeln F und G bzw. zwei endlichen Formelmengen{Fi | i ∈ Ι } und {Gj | j ∈ J }

sind (für die Aussagenlogik) entscheidbar, denn:• Wahrheitstafelmethode ist ein algorithmisches Verfahren, um Erfüllbarkeit bzw.

Unerfüllbarkeit, und somit auch Gültigkeit und Folgerbarkeit, zu prüfen.

• Der Resolutionsalgorithmus der Aussagenlogik entscheidet ebenfalls Erfüllbarkeit bzw.Unerfüllbarkeit einer Formel (in KNF).

• Die Verfahren zur Prüfung von Formeln (auf Erfüllbarkeit bzw. Unerfüllbarkeit) könnenauch zur Prüfung der entsprechenden Eigenschaften von Formelmengen verwendet werden.

Habel / Eschenbach Logik–13 [8]

Unentscheidbarkeitsresultate für die Prädikatenlogik

Die Resultate:• Das Erfüllbarkeitsproblem ist in der Prädikatenlogik nicht entscheidbar.

• Das Gültigkeitsproblem ist in der Prädikatenlogik nicht entscheidbar.

Das Unerfüllbarkeitsproblem, das Folgerbarkeitsproblem und das Äquivalenzproblem sindebenfalls unentscheidbar.

• Es gibt keinen Algorithmus, der bei Eingabe einer beliebigen prädikatenlogischen Formelentscheidet, ob diese Formel erfüllbar ist.

• Es gibt keinen Algorithmus, der bei Eingabe einer beliebigen prädikatenlogischen Formelentscheidet, ob diese Formel gültig ist.

Habel / Eschenbach Logik–13 [9]

Wie lässt sich Unentscheidbarkeit beweisen?

Zwei „Klassiker“ der Unentscheidbarkeit:

• das Postsche Korrespondenzproblem

• das Halte-Problem für Turingmaschinen

Beide Probleme sind unentscheidbar!

Reduktionsmethode:• Gegeben ein Problem P und ein bekanntermassen unentscheidbares Problem P*.

• Reduktion von P auf P*, etwa in der folgenden Weise:Bestimme ein Lösungsverfahren für P* auf der Basis eines – angenommenen –Lösungsverfahrens für P. D.h.: zeige:

# Wenn P entscheidbar ist, dann ist P* entscheidbar.• Also: Wenn die Beziehung # nachgewiesen ist, dann kann P nicht entscheidbar sein.

Schönings Unentscheidbarkeitsbeweis (S. 72ff.) basiert auf einer Reduktion auf dasPostsche Korrespondenzproblem.

Habel / Eschenbach Logik–13 [10]

Entscheidbarkeit / Semi-Entscheidbarkeit

Entscheidbarkeit eines Problems PJA!I hat die Eigenschaft P.

InstanzAlgorithmischer Test

auf die problemspezifischeEigenschaft P

NEIN!I hat die Eigenschaft P nicht.

Semi-Entscheidbarkeit eines Problems P„Hat die Eigenschaft P!“ fallsI die Eigenschaft P hat.

InstanzAlgorithmischer Test

auf die problemspezifischeEigenschaft P

Hält (eventuell) nicht an, fallsI die Eigenschaft P nicht hat.

Habel / Eschenbach Logik–13 [11]

Semi-Entscheidbarkeitsresultate für die Prädikatenlogik

• Das Unerfüllbarkeitsproblem der Prädikatenlogik ist semi-entscheidbar.Begründung: Resolutionsverfahren.

• Das Gültigkeitsproblem der Prädikatenlogik ist semi-entscheidbar.Begründung: Reduktion der Gültigkeitsprüfung auf Unerfüllbarkeitsprüfung

• Das Folgerbarkeitsproblem der Prädikatenlogik ist semi-entscheidbar.Begründung: Reduktion der Folgerbarkeitsprüfung auf Unerfüllbarkeitsprüfung.

Jede gültige Inferenz kann als gültig nachgewiesen werden!

Habel / Eschenbach Logik–13 [12]

Nicht-Semi-Entscheidbarkeit der Erfüllbarkeit in der Prädikatenlogik

• Das Erfüllbarkeitsproblem der Prädikatenlogik ist nicht semi-entscheidbar.

Begründung:

• Wäre das Erfüllbarkeitsproblem semi-entscheidbar,so könnten wir folgenden Algorithmus konstruieren:

Gegeben sei eine Formel F: Auf F wenden wir gleichzeitig die Semi-Entscheidungs-algorithmen Au für Unerfüllbarkeit und Ae für Erfüllbarkeit an.

Da F entweder erfüllbar oder unerfüllbar ist, würde entweder Au oder Ae nach endlichvielen Schritten mit einem positiven Resultat terminieren.

Somit hätten wir ein Entscheidungsverfahren für Erfüllbarkeit und für Unerfüllbarkeitkonstruiert.

Es ist nicht möglich, alle nicht-gültigen Inferenzen als nicht-gültig nachzuweisen.

Habel / Eschenbach Logik–13 [13]

Monadische Prädikatenlogik

Monadische Formel (Definition)

Eine Formel F aus LPL ist monadisch, falls sie ausser den logischen Symbolen(Junktoren und Quantoren) sowie den Variablen und Konstantensymbolennur einstellige Prädikatensymbole enthält.

Ein prädikatenlogisches System LPL, das nur monadische Formeln enthält,wird als Monadische Prädikatenlogik bezeichnet.

Theoreme der monadischen Prädikatenlogik1. Falls F eine Formel einer monadischen Prädikatenlogik ist, so gilt:

F ist erfüllbar genau dann,wenn F erfüllbar ist in einem Modell dessen Domäne maximal 2k r Elemente enthält,wobei k die Anzahl der einstelligen Prädikate in F und r die Anzahl der Variablen in F ist.

2. Es gibt ein Entscheidungsverfahren für die Erfüllbarkeit der monadischen Prädikatenlogik.• (1) korrespondiert zum Theorem von Löwenheim-Skolem:

Jede erfüllbare Formel der Prädikatenlogik besitzt ein abzählbares Modell.• (2) ist ein Konsequenz von (1).

Habel / Eschenbach Logik–13 [14]

Logiken: Ausdruckskraft und Berechnungseigenschaften

Ausdruckskraft BerechnungseigenschaftenAussagenlogik keine interne Strukturierung

atomarer Aussagen nur ja/nein Fragen behandelbar

• Entscheidbarkeit derUnerfüllbarkeit / Gültigkeit

• Erfüllbare Formeln habenendliche Modelle

monadischePrädikatenlogik(Klassenlogik)

einstellige Prädikate einfache Syllogismen Ergänzungsfragen behandelbar

• Entscheidbarkeit derUnerfüllbarkeit / Gültigkeit

• Erfüllbare Formeln habenendliche Modelle

Prädikatenlogik Prädikate beliebiger Stelligkeit komplexe Syllogismen Ergänzungsfragen behandelbar

• Semi-Entscheidbarkeit derUnerfüllbarkeit / Gültigkeit

• Erfüllbare Formeln habenabzählbare Modelle

Habel / Eschenbach Logik–13 [15]

Logiken: Ausdruckskraft und Berechnungseigenschaften (2)

• Grössere Ausdruckskraft führt – häufig – zu ungünstigeren Berechnungseigenschaften• Entscheidbarkeit → Semi-Entscheidbarkeit (Effektivität)

• endliche Modelle → abzählbare Modelle

• Komplexität der Berechnungsverfahren (Effizienz)

Welche Ausdruckskraft benötigt wird, hängt vom Anwendungsgebiet ab!

• Was bleibt – in diesem Dilemma – zu tun?• Wähle die billigste Logik, die das Anwendungsgebiet zulässt,

z.B. suche monadische Teilbereiche.• Suche effiziente Verfahren für spezifische Formelklassen

z.B. Hornlogik, Logik-Programmierung, eingeschränkte Resolutionsverfahren.• Untergliedere die Menge der Terme! [→ Sortenlogiken]

• Berücksichtige Strukturen der Domäne! [→ temporale Logiken]

Habel / Eschenbach Logik–13 [16]

Logik für InformatikerInnen: Jenseits von F1

• Aussagenlogik & Prädikatenlogik: weitere Kalküle

• Erweiterung der Ausdruckskraft logischer Sprachen• Modallogiken• Zeit-Logik• nicht-monotone Logiken• mehrwertige Logiken

• Verbesserung der Berechnungseigenschaften• terminologische Logik• Sortenlogik• effiziente Schlussverfahren für spezifische Formelklasse• Strategien des Schliessens