Upload
wolfgang-laubenstein
View
113
Download
0
Embed Size (px)
Citation preview
Agenda für heute, 13. Januar 2006
• Informationssysteme: ETH-BibliothekInformationssysteme: ETH-Bibliothek• Logische Verknüpfungen als Grundlage für die
Informationsgewinnung
• Mengendiagramme
• Boolesche Algebra
© Institut für Computational Science, ETH Zürich
ETH-Bibliothek
Vortrag von Frau E. Benninger• Grösste Bibliothek der Schweiz
• Schwerpunkte im Bereich des elektronischen Informationsangebotes
2/25
• Informationssysteme: ETH-Bibliothek
• Logische Verknüpfungen als Grundlage für die Logische Verknüpfungen als Grundlage für die InformationsgewinnungInformationsgewinnung
• Mengendiagramme
• Boolesche Algebra
© Institut für Computational Science, ETH Zürich
Wiedergewinnung von Information: Relationale Datenbank
Normalisieren
Relationale Operatoren (Select, Project, Join)
Ursprüngliche Information
Relationen
Wiedergewonnene Information
3/25
© Institut für Computational Science, ETH Zürich
Wiedergewinnung von Information: Aussagenlogik
Welche Nahrungsmittel enthalten mehr als 2mg Eisen?
OperationSuche
Name in Nahrungsmittel mit Nährstoff_id = 57 und Menge 2
4/25
Aussage
angewandt auf Tupel einer Datenbank
wahr falsch
© Institut für Computational Science, ETH Zürich
Elemente der Aussagenlogik
• Eine Aussage hat einen Wahrheitswert ("wahr", "falsch").
• Aussagen können aus Teilaussagen zusammengesetzt sein.
• Diese Teilaussagen sind durch logische Operatoren (Konjunktion, Disjunktion, Negation) verknüpft.
5/25
Der Wahrheitswert einer zusammengesetzten Aussage ist vollständig durch die Wahrheitswerte der Teilaussagen und die Art und Weise wie diese in der Aussage verknüpft sind, gegeben.
© Institut für Computational Science, ETH Zürich
Konjunktion
p und q seien Teilaussagen, w = wahr, f = falsch
Der Wahrheitswert von p and q wird durch die Wahrheitstabelle der Konjunktion präzise definiert:
p q p and q
w w w Die erste Zeile ist eine Kurzform für:w f f "Falls p wahr ist und q wahr ist, dann f w f ist p and q wahr. f f f
Symbole: und, and, •,
6/25
© Institut für Computational Science, ETH Zürich
Beispiel
AnanasYogurt and Bananen-Yogurt
Ein computergesteuerter Roboter würde mir nur etwas aus dem Laden zurück bringen, wenn sowohl ein Ananas als auch ein Bananen-Yogurt findet!
7/25
© Institut für Computational Science, ETH Zürich
Disjunktion
p und q seien Teilaussagen, w = wahr, f = falsch
Der Wahrheitswert von p or q wird durch die Wahrheitstabelle der Konjunktion präzise definiert:
p q p or q
w w w Beachte: p or q ist nur falsch wennw f w beide Teilaussagen falsch sind. f w w f f f
Symbole: oder, or, +,
8/25
© Institut für Computational Science, ETH Zürich
Beispiel
AnanasYogurt or Bananen-Yogurt
Ein computergesteuerter Roboter würde mir diejenige Sorte welche vorhanden ist aus dem Laden zurück bringen, oder beide Sorten wenn beide vorhanden sind!
9/25
© Institut für Computational Science, ETH Zürich
Negation
p sei eine (Teil)aussage, w = wahr, f = falsch
Der Wahrheitswert von not p wird durch die Wahrheitstabelle der Negation präzise definiert:
p not p
w f
f w
Symbole: nicht, not, ¬
10/25
Reihenfolge der Auswertung von Operatoren in logischen Ausdrücken:
1. NOT 2. AND 3. OR
© Institut für Computational Science, ETH Zürich
Bemerkung zur Disjunktion
Umgangssprachlich bedeutet "oder" manchmal:
p oder q oder beide (sie ist intelligent oder sie studiert jede Nacht)
manchmal bedeutet es:
p oder q aber nicht beide (sie telefoniert aus Basel oder aus Genf)
"oder" in letzterem Sinn wird exklusive Disjunktion (xor) genannt.
p or q ist durch die Wahrheitstabelle definiert und bedeutet immer
"p oder q oder beide".
11/25
© Institut für Computational Science, ETH Zürich
Disjunktion oder exklusive Disjunktion?
12/25
Genauer: drink and >1 Glas xor drive
Genauer: drink xor drive Aber stimmt das?
Genauer: drink and ≤ 1 Glas and drive or drink and > 1 Glas and not drive
Stimmts jetzt?
© Institut für Computational Science, ETH Zürich
Ein paar Spezialfälle
Logische Äquivalenzennot p or not q not ( p and q ) (de Morgan)not p and not q not ( p or q )
Tautologie Widerspruch
p or not p p and not p
p not p p or not p w f w f w w
p not p p and not p w f f f w f
13/25
© Institut für Computational Science, ETH Zürich
Logische Operatoren im Web: "+" und "-"
Inklusion und ExklusionAnstelle der logischen Operatoren "and", "or" und "not" setzen Suchhilfen oft auch die Zeichen "+" und "-" ein.
Mit dem "+"-Operator (Inklusion oder Einschluss) sagen wir, dass der nachfolgende Suchbegriff auf jeden Fall im Suchergebnis enthalten sein muss.
Der "-"-Operator (Exklusion oder Ausschluss) schliesst Dokumente im Suchergebnis aus, welche den nachfolgenden Suchbegriff enthalten.
Beispiel
Vogelgrippe –China
Es werden nur Dokumente gesucht, in denen der Begriff "China" nicht enthalten ist.
14/25
• Informationssysteme: ETH-Bibliothek
• Logische Verknüpfungen als Grundlage für die Informationsgewinnung
• MengendiagrammeMengendiagramme• Boolesche Algebra
© Institut für Computational Science, ETH Zürich
Grafische und formale Darstellung logischer Verknüpfungen
Namen allerNahrungsmittel
Alle Nahrungsmittel mit Nährstoff 57(Eisen)
15/25
Logischer Ausdruck
Nährstoff_id = 57 AND Menge > 2
Mengendiagramme
Welche Nahrungsmittel enthalten mehr als 2mg Eisen?
Alle Nahrungsmittel mit Menge > 2
© Institut für Computational Science, ETH Zürich
Beispiele logischer Verknüpfungen
Bücher über Südfrankreich
Bücher über Wein
Bücher über Weinanbaugebiete
Alle Bücher (Grundmenge)
16/25
© Institut für Computational Science, ETH Zürich
Bücher über Südfrankreich
Bücher über Wein
Suche: Bücher über Weinanbaugebiete in Südfrankreich
Logischer Ausdruck: Weinanbau AND Südfrankreich
17/25
"wahr" für alle Bücher in dieser Schnittmenge
Bücher über Weinanbaugebiete
© Institut für Computational Science, ETH Zürich
Suche: Bücher Südfrankreich oder über Wein oder über beides
Logischer Ausdruck: Wein OR Südfrankreich
Bücher über Wein
Bücher über Südfrankreich
18/25
Bücher über Weinanbaugebiete
© Institut für Computational Science, ETH Zürich
Suche: Bücher über Südfrankreich aber nicht über Wein
Logischer Ausdruck: Südfrankreich AND NOT Wein
Bücher über Wein
Bücher über Südfrankreich
19/25
Bücher über Weinanbaugebiete
© Institut für Computational Science, ETH Zürich
Suche: Bücher über Weinanbau oder über Wein oder über beides, aber nur wenn Südfrankreich nicht vorkommt
Logischer Ausdruck: (Weinbau OR Wein) AND NOT Südfrankreich
Bücher über Südfrankreich
Bücher über Wein
20/25
Bücher über Weinanbaugebiete
© Institut für Computational Science, ETH Zürich
Wahrheitstabellen für die Analyse logischer Ausdrücke
SüdFr Weinanb Wein NOT SüdFr Weinanb OR Wein (Weinanb OR Wein) AND NOT Südfr
W W W F W F
W W F F W F
W F W F W F
W F F F F F
F W W W W W
F W F W W W
F F W W W W
F F F W F F
Beispiel Wir suchen Bücher über Weinanbau oder über Wein oder über beides, aber nur wenn Südfrankreich nicht vorkommt
21/25
• Informationssysteme: ETH-Bibliothek
• Logische Verknüpfungen als Grundlage für die Informationsgewinnung
• Mengendiagramme
• Boolesche AlgebraBoolesche Algebra
© Institut für Computational Science, ETH Zürich
Boolesche Algebra
Eine Menge M mit zwei Verknüpfungen "•" und "+" heisst Boolesche* Algebra, wenn für alle x, y, z M gilt:
(1) x • (y • z) = (x • y) • z; Assoziativ
(2) x + (y + z) = (x + y) + z; Assoziativ
(3) x • y = y • x; Assoziativ
(4) x + y = y + x; Assoziativ
(5) x • (x + y) = x; Absorption
(6) x + (x • y) = x; Absorption
(8) x • (y + z) = (x • y) + (x • z); Distributiv
(8) x + (y • z) = (x + y) • (x + z); Distributiv
22/25
* nach George Boole, englischer Mathematiker, 1815 – 1864
© Institut für Computational Science, ETH Zürich
Boolesche Algebra
(9) es gibt ein Element 0 M mit 0 • x = 0 und 0 + x = x für alle x M ;Neutrales Element
(10) es gibt ein Element 1 M mit 1 • x = x und 1 + x = x für alle x M ;
Neutrales Element
(11) zu jedem x M existiert genau ein y M mit x • y = 0 und x + y = 1;
Komplementäres Element
23/25
Wir ersetzen "wahr" mit "1" und "falsch" mit "0" und wenden die Boolesche Algebra auf logische Ausdrücke an.
© Institut für Computational Science, ETH Zürich
Vereinfachung logischer Ausdrücke am Beispiel des Yogurt
1. (A • B) + (A • ¬B) + (¬A • ¬B)
2. [A • (B + ¬B)] + (¬A • ¬B) Distributivgesetz
3. (A • 1) + (¬A • ¬B) komplementäres Element bez. +
4. A + (¬A • ¬B) neutrales Element bez. •
5. (A + ¬A) • (A + ¬B) Distributivgesetz
6. 1 • (A + ¬B) komplementäres Element bez. +
7. A + ¬B neutrales Element bez. •
Aber . . . sind der 1. und der 7. Ausdruck auch äquivalent?
24/25
Ananas und Banane oder Ananas und keine Banane oder keine Ananas und keine Banane
Ananas oder keine Banane
© Institut für Computational Science, ETH Zürich
Verifizierung logischer Ausdrücke
25/25
A B ((A • B) + (A • ¬B)) + (¬A • ¬B)
1 1 1 1 1 1 1 0 0 1 0 0 0
1 0 1 0 0 1 1 1 1 1 0 0 1
0 1 0 0 1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 1 1 1 1
Schritt: 1 2 1 5 1 3 1 6 1 4 1
A B A + ¬B
1 1 1 1 0
1 0 1 1 1
0 1 0 0 0
0 0 0 1 1
Schritt: 1 2 1
Reihenfolge:AussageLogischer Ausdruck (Symbole)Boolesche AlgebraAusdruck evaluieren
1. Ausdruck:
7. Ausdruck:
Wir wünschen Ihnen ein schönes Wochenende.