Kapitel 4: Aussagen-, Prädikatenlogik

Institut für Softwarewissenschaft – Universität Wien

P.Brezany 1

Kapitel 4: Aussagen-, Prädikatenlogik

Peter BrezanyInstitut für Softwarewissenschaft

Universität Wien, Liechtensteinstraße 221090 Wien

Tel. : 01/4277 38825E-mail : [email protected]

Sprechstunde: Dienstag, 11.30-12.30


P.Brezany 2

Logik und Mathematische Logik

Logik ist in der Theoretischen Informatik (TI) keine Wissenschaft, die uns richtiges Denken lehrt, sondern dasssie nur Aussagen darüber macht, unter welchen Bedingungenman aus der Gültigkeit von Voraussetzungen auf dieGültigkeit von Folgerungen schließen kann.

Weil hier also Logik betrieben und aufgebaut wird wie eine mathematische Theorie, heißt sie mathematische Logik.


P.Brezany 3

Aussagenlogik• Unter einer „Aussage“ wollen wir einen Satz der

natürlichen Sprache verstehen.• Es interessiert uns dabei nicht der syntaktische

Aufbau (Subjekt –Prädikat – Objekt), sondern die charakteristische Eigenschaft des betrachteten Gebildes, wahr oder falsch zu sein.

• Aussagen unterscheiden sich von anderen sprachlichen Gebilden dadurch, dass wir ihnen einen bestimmten Wahrheitswert zuteilen können – den Wahrheitswert „W“, wenn sie wahr, den Wahrheitswert „F“ wenn sie falsch sind, es aber keine weitere Möglichkeit gibt.

• Beispiele solcher Aussagen sind:– Baden ist eine Stadt in Niederösterreich.– Alle Menschen müssen sterben.– 7 ist größer als 4.

Sie haben alle den Wahrheitswert W.


P.Brezany 4

Aussagenlogik (2)• Folgende Aussagen haben den Wahrheitswert F:

– Junge Pferde nennt man Welpen.– 6 ist größer als 8.

• Eine Aussage wird im Folgenden durch A, B, C, ... repräsentiert. Da eine Aussage einen der beiden Werte annemen kann, spricht man auch von einer „Aussagenvariablen“ – für eine Variable A darf man beliebige Aussagen einsetzen, was die Zuweisung eines der Werte W oder F bedeutet.

• Sätze der Umgangssprache werden auf vielfache Weise miteinander verknüpft – durch die Verwendung von Bindewörtern wie „und“, „oder“, „wenn - dann“. In der Aussagenlogik lassen sich Verknüpfungen von Aussagen ebenfalls beschrieben.

• Die Definition einer Verknüpfung von Aussagen A, B wird dadurch beschrieben, dass der Wahrheitswert der Verknüpfung in Abhängigkeit von der Wahrheitswerten der Aussagen A, B angegeben wird. Das geschieht in Form einer sogenannten Wahrheitstabelle oder Wahrheitstafel.


P.Brezany 5

Aussagenlogische Formeln (AF)• Im Allgemeinen können wir Aussagen durch sogenannte

aussagenlogische Formeln beschreiben. Folgende Elemente können in diesen Formeln erscheinen

– Namen wie x für nicht-zusammengesetzte Aussagen (im weiteren werden wir solche Namen als atomare Formeln oder Atome bezeichnen). Zum Beispiel: „5 ist eine ungerade Zahl“.

– Verknüpfungsoperatoren (Konnektoren) wie , , usw., mit denen man aus einfachen Formeln komplexere zusammensetzen kann.

• Jetzt wollen wir zur Aussagenlogik einen formalen Kalkül vorstellen. Dabei werden wir unter anderem untersuchen,

– wie die Symbole , , usw. zusammenhängen – Syntax der Aussagenlogik,

– wie man komplexe Formeln auswertet, d.h. wie man feststellt, ob sie insgesamt wahr oder falsch sind – Semantik der Aussagenlogik, und

– wie man Formeln umformt, um sie in bestimmte einfachere Formen, sogenannte Normalformen, zu bringen.


P.Brezany 6

Aussagenlogische Formeln (2)• Aussagenlogische Formeln heißen auch

logische oder Booloesche Ausdrücke (BA) (nach dem englischen Mathematiker George Boole – 19. Jahrhundert, der das algebraische Studium von Wahrheitswerten initialisiert hat).

• BA sind ähnlich artitmetischen Ausdrücken – dort sind Operanden, die die Werte W und F (statt integers) representieren, und Operatoren, and (), or () statt , +) und Klammern werden angewendet, um die Reihenfolge der Auswertung bestimmen zu helfen.

• Man muß lernen, wie man die auf Deutsch oder Englisch ausgedrückten Behauptungen als Formeln ausdrückt.


P.Brezany 7

Syntax der Aussagenlogik Zunächst wollen wir definieren, was wir unter einer Formel (der

Aussagenlogik) verstehen: eine einfache oder mit den schon bekannten Konnektoren zusammengesetzte Aussage.

Definition: Gegeben sei eine nichtleere, abzählbare Menge Var von atomaren Formeln (auch Atome oder manchmal auchVariablen genannt), deren Elemente wir üblicherweise mit x, y, z, x o.ä. bezeichnen. Eine Formel der Aussagenlogik (AL) (über Var) ist induktiv wie folgt definiert:

• Induktionsbeginn: Jede atomare Formel aus Var ist eine Formel.• Induktionsschritt: Sind F und G bereits Formeln der AL, so sind

auch F, (F G), (F G) Formeln der AL. F heißt auch Negation, (F G) heißt auch

Konjuktion, und (F G) heißt auch Disjunktion.• Ein Literal ist eine atomare Formel oder die Negation einer

atomaren Formel. FAL ist die Menge aller aussagenlogischen Formeln. Var (F) ist die Menge aller der atomaren Formeln, die in der Formel

F vorkommen.


P.Brezany 8

Syntax der Aussagenlogik – BNF Grammatik (2)

<AF> ::= W | F | <identifier> | ( <AF>) | (<AF> <AF>) | (<AF> <AF>) | (<AF> <AF>) | (<AF> = <AF>)


P.Brezany 9

Semantik der Aussagenlogik

Die Semantik der AL festzustellen heißt anzugeben, was eine Formel bedeutet. Genauer gesagt geht es darum, zu definieren, wann eine AL-Formel wahr oder falsch ist.

„Wahr“ (W) und „falsch“ (F) (oder true und false) heißen Wahrheitswerte. Wir setzen voraus, dass jede atomare Formel entweder den Wahrheitwert W oder F annimmt, das heißt, wir arbeiten mit einer zweiwertigen Logik.

Bemerkung: Es gibt auch andere Logiken, z.B. die dreiwertige, die mit den Wahrheitswerten W, F und „?“ arbeitet (der dritte steht für „unbestimmt“), oder die Fuzzy Logic, bei der die Variablen Werte aus dem Kontinuum [0,1] annehmen. Je näher an 1 der Wert einer Formel ist, umso „wahrer“ ist sie.


P.Brezany 10

Semantik der Aussagenlogik (2) Eine atomare Formel x steht für irgendeine Aussage, vieleicht für

„Das Wort Opossum enthält genau soviel ò´ wie `p´“ oder für „Das Wort Lemur hat genau halb so viele Buchstaben wie das Wort Gürteltier.“ Ob x wahr ist oder falsch, hängt davon ab, für welche Aussage x steht.

Auch eine zusammengesetzte Formel steht für viele verschiedene Aussagen, manche davon wahr, andere falsch, je nachdem, wofür die atomaren Formeln stehen. Für zusammengesetzte Formeln kan man z.B. aber sagen: F G ist wahr genau dann, wenn sowohl F als auch G wahr sind. Man kann also von der Bedeutung einer Formel abstrahieren und ihren Wahrheitswert angeben in Abhängigkeit von den Wahrheitswerten der Teilformeln. Da man das auch für Teilformeln wieder tun kann bis hinunter auf die Ebene der Atome, kann man insgesamt den Wahrheitswert einer Formel angeben in Abhängigkeit von den Wahrheitswerten der Atome, die darin vorkommen. Wenn wir jeder atomaren Formel einen (beliebigen, aber festen) Wahrheitswert zuweisen, so heißt das eine Belegung.


P.Brezany 11

Semantik der Aussagenlogik (3)

Definition: Ein Wahrheitwert ist ein Wert aus der Menge {W, F}. Eine Belegung ist eine Abbildung A: Var {W, F}, die jeder atomaren Formel einen Wahrheitswert zuweist.

Wir erweitern A auf eine Abbildung A: FAL {W, F}, die jeder AL-Formel einen Wahrheitswert zuweist wie in den folgenden Wahrheitstafeln spezifiziert wird.


P.Brezany 12

Wahrheitstafeln• Konjuktion („und“)

A B A B

F F FF W FW F FW W W

• Disjunktion („oder“)A B A B

F F FF W WW F WW W W


P.Brezany 13

Wahrheitstafeln (2)• Implikation A heißt die Prämisse, B die Conclusio

A B A B der Folgerung

F F WF W WW F FW W W

• Äquivalenz A B A B

F F W F W F

W F FW W W

Schlagwort: „aus etwas Falschem kann man allesfolgern“


P.Brezany 14

Wahrheitstafeln (3)• Negation

A A

F W W F

Definition: TautologieEine Formel heißt allgemeingültig (oder Tautologie), wenn sie für alle Werte der in ihr vorkommenden Aussagenvariablen den Wert W annimmt.Anders ausgedrückt heißt eine Formel Tautologie, wenn sie für alle Belegungen den Wert W annimt.

Beispiele für allgemeingültige Formeln sind: A A oder A (A B) B


P.Brezany 15

Wahrheitstafeln (4)

• Konjunktion, Disjunktion, Implikation und Äquivalenz werden als zweistellige Junktoren genannt. Die Negation – eine einstellige Verknüpfung.


P.Brezany 16

Auswertung von konstanten AF• Konstante AF – sie enthält nur Konstanten als

Operanden

• Fall 1: Der Wert von W ist W; der Wert von F ist F.

• Fall 2: Der Wert von (A), (A B), ..., wo A und B sind Konstanten W oder F ist durch die Wahrheitstafeln gegeben.

• Fall 3: Der Wert einer konstanten AF, die mehr als 1 Operator enthält wird durch die wiederholte Anwendung des Falls 2 bestimmt.


P.Brezany 17

Auswertung von AF in einem Zustand

AF wie (A B) kann in einem Programm auf mehreren Stellen erscheinen, z.B. C := (A B) oder if (A B) then ... . Wenn einer dieser Anweisungen ausgeführt wird, wird AF im aktuellen maschinen „Zustand“ ausgewertet, um W oder F zu produzieren.

Definition: Ein Zustand s ist eine Funktion s: Id {W, F}

Id – Identifikatoren

Definition: AF ist well-defined im Zustand s, wenn jeder Identifikator in AF mit entweder W oder F assoziert ist.


P.Brezany 18

Auswertung von AF in einem Zustand (2) Definition: Sei AF e well-defined im Zustand s.

Dann s(e), der Wert von e in s, ist der Wert, den man bekommt, wenn man alle Identifikatoren B in e durch ihre Werte s(B) ersetzt und evaluiert den resultierenden konstanten AF.


P.Brezany 19

AF als Mengen von Zuständen

Eine AF representiert, oder beschreibt, die Menge von Zuständen in denen sie wahr ist. Umgekehrt, für jede Menge Zuständen, die nur Identifikatoren assoziiert mit W und F enthalten, können wir eine AF ableiten, die diese Menge repräsentiert.

Die leere Menge, die Menge, die keine Zustände enthält, ist durch die AF F repräsentiert, weil F in keinem Zustand wahr ist.

Die Menge aller Zustände ist durch die AF W repräsentiert, weil W in allen Zuständen wahr ist.


P.Brezany 20

AF als Mengen von Zuständen (2) Beispiel:

Die Menge von 2 Zuständen { (B, W), (C, W), (D, W) } und { (B, F), (C, W), (D, F) }

ist repräsentiert durch die AF:

(B C D) (B C D) --------------------------------------- Bemerkung: Die Verbindung zwischen einer AF und der von

ihr repräsentierten Menge von Zuständen ist so stark, dass wir oft beide Konzepte gleichsetzen. Z.B. statt zu schreiben: „die Menge von Zuständen, in denen B C wahr ist“, können wir schreiben: „die Zustände in B C“.


P.Brezany 21

Modell für eine Formel Definition: Ein Modell für eine Formel F ist eine

wahrmachende Belegung, also eine Belegung A mit A(F) = W.

Beispiel: Ein Modell für die Formel (x (y z)) ist z.B. die Belegung A1 mit

A1(x) = true, A1(y) = false und A1(z) = false.

Aber auch die folgende Belegung A2 ist ein Modell:

A2(x) = false, A2(y) = false und A2(z) = true.


P.Brezany 22

Erfüllbare, unerfüllbare Formeln, Tautologie

Definition: Eine Formel F heißt erfüllbar, falls sie mindestens ein Modell besitzt, ansonsten heißt sie unerfüllbar. Wenn F von jeder Belegung erfüllt wird, heißt F Tautologie oder gültig.

Satz: Eine Formel F ist eine Tautologie genau dann, wenn F unerfüllbar ist.


P.Brezany 23

SAT und TAUTDefinition:

SAT := { F FAL } | F is erfüllbar }

TAUT := { F FAL } | F is Tautologie }

SAT und TAUT bezeichnen Sprachen, Sprache der erfüllbaren („saturierbaren“) bzw. der gültigen AL-Formeln, und die Wörter dieser Sprachen sind AL-Formen.

SAT und TAUT bezeichnen aber auch Probleme, nämlich die Fragen „Ist F SAT?“ und „Ist F TAUT?“

Beide Probleme sind entscheidbar; man kann einen Algorithmus angeben, der für jede AL-Formel F in endlicher Zeit entscheidet, ob F erfüllbar bzw. gültig ist: das Verfahren der Wahrheitstafeln.


P.Brezany 24

Äquivalenz von Formeln• Äquivalenz von Formeln

1. A1 A2 = A2 A1

2. A1 A2 = A2 A1

3. (A1 A2) A3 = A1 (A2 A3 )

4. (A1 A2) A3 = A1 (A2 A3 )

5. (A1 A2) A3 = (A1 A3) (A2 A3 )

6. (A1 A2) A3 = (A1 A3) (A2 A3 )

7. A1 A1 = A1 A1 A1 = A1

8. (A1 A2) = A1 A2

9. (A1 A2) = A1 A2

de Morganschen Regeln


P.Brezany 25

Konjuktive und disjunktive Normalform

Manchmal ist es vorteilhaft, Formeln durch Umformungen zu vereinfachen. Wir werden jetzt 2 Normalformen für AL-Formeln vorstellen.

Normalformen sind Einschränkungen auf der Syntax der AL, aber so, dass man jede beliebige Formel umformen kann in eine äquivalente Formel in Normalform.

Normalformen sind auch wichtig für die maschinelle Verarbeitung von logischen Formeln (und es gibt inzwischen sehr viele Algorithmen, die AL-Formeln verarbeiten und dadurch logische Schlüsse ziehen – z.B. intelligente Agenten): Wenn alle Formeln nur noch eine eingeschränkte Syntax haben, dann muß ein Algorithmus nicht so viele mögliche Formel-Formen berücksichtigen.


P.Brezany 26

Konjuktive und disjunktive Normalform (2)

Definition: 1. Eine Formel F ist in konjuktiver Normalform (KNF)

genau dann, wenn F eine Konjuktion von Disjunktionen von Literalen ist.

2. Eine Formel F ist in disjunktiver Normalform (DNF) genau dann, wenn F eine Disjunktion von Konjunktionen von Literalen ist.

Beispiel: Die Formel F = (x ((y z) w)) ist in keiner Normalform. Die Formel F´= (x y) (x z) (x w) ist zu F äquivalent und in DNF. Die Formel F´´ = x (y z w) ist zu F äquivalent und in KNF.


P.Brezany 27

Regelsysteme In der Logik werden Regelsysteme (Ableitungs-

oder Inferenzregeln) angegeben, die es erlauben, aus einer Menge von als wahr angenommenen Formeln (Axiome) weitere Formeln (Theoreme) abzuleiten.

Die Ableitung einer Formel heißt auch (formaler) Beweis der Formel.

Beispiel für andere eine Anwendung: Intelligente Softwareagenten (siehe folgende Folien).


P.Brezany 28

Regeln Die allgemeine Form einer Regel kann wie folgt geschrieben werden:

wenn Prämisse(n) dann Konklusion(en)(statt Prämisse werden auch oft die Begriffe „Bedingung“,„Vorausetzung“ oder „Situation“ und statt Konklusion „Aktion“oder Hypothese“ verwendet.)Obige Form der Regel sagt aus, daßim Falle der Erfüllung der Prämisse(n) die Konklusion(en) zur Ausführung gelangt (gelangen).

Regeln können folgende Form haben:• wenn P dann Q• wenn P1 und P2 und ... und Pn dann Q1 und Q2 und ... und Qm• wenn P1 oder P2 oder ... oder Pn dann Q

Regeln, die neue Fakten produzieren, werden Produktionsregelngenannt.


P.Brezany 29

Regeln (2)Architektur eines

Produktionssystem

Regeln

Wissensbasis FaktenbasisInferenzmecha- nismus

Fakten

Act

Recognize Select


P.Brezany 30

Arbeitsweise eines Produktionssystems

Beispiel: Insgesamt gibt es in unserer Wissensbasis vier Regeln:

R1: wenn A > 50 dann B = 45R2: wenn B < 40 dann C = 0R3: wenn B >= 40 dann D = 100R4: wenn A > 60 dann E = 20

Die Faktenbasis enthält das faktum A = 100. Recognize: R1 und R4 sind Kandidaten; Select: R1 ist ausgewählt; Action: B = 45 wird in die Faktenbasis geschrieben. Dann R3 usw.


P.Brezany 31

Ein Agent in seiner Umgebung


P.Brezany 32

Agentenbeschreibung: Simple-Reflex-Agent

Wie beschreiben wir nun Agenten? Wir könnten eine Funktion action : P A (P – perceptions (Wahrnehmungen), A – Aktionen)

benutzen.

Condition-action rules


P.Brezany 33

Agentenbeschreibung: Simple-Reflex-Agent (2)

function SIMPLE-REFLEX-AGENT (percept) returns actionstatic: rules // a set of condition-action rules

env-state INTERPRET-INPUT(percept) rule RULE-MATCH(env-state, rules) action RULE-ACTION[rule]return action


P.Brezany 34

Prädikatenlogik• Bei der Einführung des Prädikatenbegriffs werden

wir uns auf die Menge IN der natürlichen Zahlen beschränken (der Einfachkeit halber).

• Mögliche Aussagen sind: a ist eine gerade Zahl, b ist teilbar durch 3, c ist eine Primzahl, d ist eine Summe von a und b, usw.; eine solche Aussage über einzelne Elemente, über Paare von Elementen oder allgemeiner über n-Tupel von Elementen wird als Prädikat über der Menge IN bezeichnet.

• Man spricht von einem n-stelligen Prädikat über IN, wenn es die Aussage über je n Elemente macht. In Abhängigkeit von den gewählten Elementen nimmt ein Prädikat den Wahrheitswert W oder F an.

• Ist P ein n-stelliges Prädikat über der Menge M, so wird der Funktionswert von P für das n-Tupel (x1, .., xn) mit P(x1, .., xn) bezeichnet. Die Symbole P, Q, ... – Prädikatsvariablen.


P.Brezany 35

Allquantor Definition:

Es sei P ein einstelliges Prädikat über M. Dann wird durch x P(x) genau dann eine wahre Aussage bezeichnet, wenn P für alle x M den Wert W annimmt. P heißt dann Allquantor oder Generalisator.

x P(x) wird gelesen als „für alle xM ist P(x) wahr“.

Z.B. kann man die Tatsache, daß durch 6 teilbare Zahlen auch durch 3 teilbar sind, ausdrücken als x N (x mod 6 = 0 x mod 3 = 0).


P.Brezany 36

Existenzquantor Definition:

Es sei P ein einstelliges Prädikat über M. Dann wird durch x P(x) genau dann eine Wahre Aussage bezeichnet, wenn es in M (mindestens) ein Element a gibt, für das P den Wahrheitswert W annimmt. P heißt dann Existenzquantor oder Partikulisator.

Beispiel: „Es gibt mindestens ein Wort der deutschen Sprache, das genau 5 è´ und keine anderen Vokale enthält“ oder in Zeichen x (D(x) E(x)), falls D(x) heißt „x ist ein Wort der deutschen Sprache“ und E(x) steht für „x enthält genau 5 è´ und keine anderen Vokale“.


P.Brezany 37

Freie und gebundene Variablen Nehmen wir das Prädikat: i : m i < n: xi > 0 (1.) Die Wahrheit dieses Prädikats im Zustand s ist von

den Werten von m, n und x in s, aber nicht vom Wert i abhängig, und die Bedeutung dieses Prädikat wird sich nicht ändern, wenn wir i durch j ersetzen.

Identifikatoren m, n und x sind freie Variablen des Prädikats.

Der Identifikator i ist gebunden in (1.) und ist gebunden zu dem Quantifier in diesem Prädikat.

Documents

Kapitel 4: Aussagen-, Prädikatenlogik