Daten verwalten (2)Daten verwalten (2) Logische Verknüpfungen als Grundlage für die Informationsgewinnung Werte von Aussagen: Wahrheitstabellen Grafische

• Daten verwalten (2)Daten verwalten (2)• Logische Verknüpfungen als Grundlage für die

Informationsgewinnung

• Werte von Aussagen: Wahrheitstabellen

• Grafische vs. formale Darstellung von Abfragen

• Boolesche Algebra

Agenda für heute, 28. April 2010

Das heutige Thema im Kontext des Informationsarbeitsplatzes

2/27

Informatik für Biol. & Pharm. Wissenschaften © Departement Informatik, ETH Zürich

Daten verwalten (2): Drei Stufen der Datenverwaltung

3/27

• Daten organisieren

• Daten speichern

• Daten wieder gewinnen

• Daten reorganisieren

Anwendung Informatik

• Entity-Relationship-Modell

• Datenbanken

• Daten austauschen

• Daten umformen

• Abfragen (z.B. mit SQL)

• Logische Verknüpfungen

• Datenformate

• Standards


Daten organisieren, Daten Speichern

Restrukturieren

Ursprüngliche Information

Verwaltbare Information•Metadaten werden zu Daten•Jede Zelle ein Datentyp

4/27

Name CH-Code Nährstoff Menge Einheit Hauptkomp.

Aprikose 18.1.2.1 Eisen 0.4 mg ja

Aprikose 18.1.2.1 Protein 0.8 g ja

Aprikose 18.1.2.1 Wasser 86.79 g ja

Bürli 12.1.2.Z.2 Kohlehydrate 48.8 g ja

Bürli 12.1.2.Z.2 Kalium 160 mg ja

Bürli 12.1.2.Z.2 Wasser 39.6 g ja

Metadaten

Name CH-Code Wasser Kohlehyd. Eisen Protein Kalium Hauptkomp.

Aprikose 18.1.2.1 86.79 g 12.1 g 0.4 mg 0.8 g 315 mg ja

Bürli 12.1.2.Z.2 39.6 g 48.8 g 2.0 mg 8.6 g 160 mg ja

Daten

Name CH-Code Wasser Kohlehyd. Eisen Protein Kalium Hauptkomp.

Aprikose 18.1.2.1 86.79 g 12.1 g 0.4 mg 0.8 g 315 mg ja

Bürli 12.1.2.Z.2 39.6 g 48.8 g 2.0 mg 8.6 g 160 mg ja


Daten organisieren, Daten speichern: Relationale Datenbank

Normalisieren

Relationale Operatoren (Select, Project, Join)

Ursprüngliche Information

Relationen

Umstrukturierte Information

5/27

Name Nährstoff Menge

Bürli Kohlehydrate 48.8

Bürli Wasser 39.6

Name CH-Code Nährstoff Menge Einheit Hauptkomp.

Aprikose 18.1.2.1 Eisen 0.4 mg ja

Bürli 12.1.2.Z.2 Kohlehydrate 48.8 g ja

Bürli 12.1.2.Z.2 Kalium 160 mg ja

Name CH-Code Nährstoff_id Menge

Aprikose 18.1.2.1 57 0.4

Aprikose 18.1.2.1 400 0.8

Bürli 12.1.2.Z.2 84 48.8

Bürli 12.1.2.Z.2 180 39.6

Nährstoff_id Nährstoff Einheit Hauptkomp.

57 Eisen mg ja

180 Wasser g ja

84 Kohlehyd. g ja

330 Kalium mg ja

• Daten verwalten (2)

• Logische Verknüpfungen als Grundlage für die Logische Verknüpfungen als Grundlage für die InformationsgewinnungInformationsgewinnung





Wiedergewinnen von Information mittels Aussagenlogik

Welche Nahrungsmittel enthalten weniger als 2 mg Eisen?

Name in Nahrungsmittel mit Nährstoff = Eisen und Menge < 2

6/27

Aussage

ausgewertet mit Tupel einer Datenbank

wahr(z.B. 1.7 mg Eisen)

Datenbankabfrage

falsch(z.B. 3.4 mg Eisen)

(z.B. 1.7 mg Kalzium)

Elemente der Aussagenlogik

• Eine Aussage hat einen Wahrheitswert ("wahr", "falsch")

• Aussagen können aus Teilaussagen zusammengesetzt sein

Nährstoff = Eisen und Menge < 2

• Diese Teilaussagen sind durch logische Operatoren verknüpft

Nährstoff = Eisen and Menge < 2

Der Wahrheitswert einer zusammengesetzten Aussage ist vollständig durch die Wahrheitswerte der Teilaussagen und die Art der Verknüpfung gegeben.

Informatik für Biol. & Pharm. Wissenschaften © Departement Informatik, ETH Zürich7/27


Logische Operatoren

p und q sind Teilaussagen (logische Operanden)

z.B. p steht für: Nährstoff = Eisen

q steht für: Menge < 2

Konjunktion: "sowohl p als auch q"

p and q

Disjunktion: "entweder p oder q"

p or q

Negation: "nicht p"

not p

• UND

• ODER

• NICHT

8/27


• Logische Verknüpfungen als Grundlage für die Informationsgewinnung

• Werte von Aussagen: WahrheitstabellenWerte von Aussagen: Wahrheitstabellen• Grafische vs. formale Darstellung von Abfragen



Werte von Aussagen: Wahrheitstabellen

• Logische Verknüpfungen anschaulich spezifizieren

• Für jede mögliche Kombination von Wahrheitswerten wird das Resultat der Verküpfung aufgelistet

9/27

p q Verknüpfung von p mit q

w w x

w f x

f w x

f f x

w = wahr, f = falsch


Wahrheitstabelle für die Konjunktion

Die erste Zeile ist eine Kurzform für:"Falls p wahr ist und q wahr ist, dannist p and q wahr

Für alle Zeilen: wenn p dann q sonst falsch

Symbole: und, and, •,

10/27

p q p and q

w w w

w f f

f w f

f f f


Wahrheitstabelle für die Disjunktion

Beachte: p or q ist nur dann falsch wenn beide Teilaussagen falsch sind

Für alle: wenn p dann wahr sonst q

Symbole: oder, or, +,

11/27

p q p or q

w w w

w f w

f w w

f f f


Beispiele

Eisen ist magnetisch and Gold ist gelb

ist wahr

12/27

Eisen ist magnetisch and Gold ist magnetisch

ist falsch

Eisen ist magnetisch or Gold ist gelb

ist wahr

Eisen ist magnetisch or Gold ist magnetisch

ist wahr

Eisen ist gelb or Gold ist magnetisch

ist falsch

wahr and wahr

wahr and falsch

wahr or wahr

wahr or falsch

falsch or falsch


Wahrheitstabelle für die Negation

Symbole: nicht, not, ¬

13/27

Vorrangregelung der logischen Operatoren :

1. not 2. and 3. or 4. Vergleiche

Kann durch Setzen von Klammern aufgehoben werden

p not p

w f

f w

p or q and r ≠ (p or q) and r


Bemerkungen zur Disjunktion

Umgangssprachlich bedeutet "oder" meistens:

p oder q oder beide (sie ist intelligent oder sie studiert jede Nacht)

p or q bedeutet immer "p oder q oder beide" (siehe Wahrheitstabelle)

manchmal bedeutet "oder" jedoch:

p oder q aber nicht beide (sie telefoniert aus Basel oder aus Genf)

für diese Bedeutung wird die exklusive Disjunktion (xor) angewandt

14/27

Beachte: p xor q ist dann falsch wennbeide Teilaussagen entweder falschoder richtig sind.

p q p xor q

w w f

w f w

f w w

f f f


Disjunktion oder exklusive Disjunktion?

15/27

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?


Das neue Plakat

© Raphael Theiler

16/27


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 )

17/27

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

Tautologie

p or not p

Widerspruch

p and not p



• Werete von Aussagen: Wahrheitstabellen

• Grafische vs. formale Darstellung von AbfragenGrafische vs. formale Darstellung von Abfragen• Boolesche Algebra


Grafische vs. formale Darstellung logischer Verknüpfungen

Alle Nahrungsmittelmit Eisen

Alle Nahrungsmittel mit Zink

18/27

Logischer Ausdruck

(Menge < 2 mg) and (Nährstoff = Eisen) or (Nährstoff = Zink)

Mengendiagramme

Welche Nahrungsmittel enthalten weniger als 2 mg Eisen oder Zink?

Alle Nahrungsmittel mit Menge < 2 mg



Eisen

19/27

Menge and Eisen

Zink

Menge

(Menge < 2 mg) and (Nährstoff = Eisen) or (Nährstoff = Zink)



20/27

Logischer Ausdruck

(Nährstoff = Eisen) and (Menge < 2 mg) or

(Nährstoff = Zink) and (Menge < 2 mg)

Welche Nahrungsmittel enthalten weniger als 2 mg Eisen oder weniger als 2 mg Zink?


Wahrheitstabellen für die Analyse logischer Ausdrücke

< 2 mg Eisen Zink Eisen or Zink (Eisen or Zink) and < 2 mg

W W W W W

W W F W W

W F W W W

W F F F F

F W W W F

F W F W F

F F W W F

F F F F F

21/27

(Menge < 2 mg) and (( Nährstoff = Eisen) or (Nährstoff = Zink))


Wahrheitstabellen für die Analyse logischer Ausdrücke

< 2 mg Eisen Zink < 2 mg and Eisen < 2 mg and Eisenor Zink

W W W W W

W W F W W

W F W F W

W F F F F

F W W F W

F W F F F

F F W F W

F F F F F

22/27

(Menge < 2 mg) and ( Nährstoff = Eisen) or (Nährstoff = Zink)





• Boolesche AlgebraBoolesche Algebra


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; Kommutativ

(4) x + y = y + x; Kommutativ

(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

23/27

* nach George Boole, englischer Mathematiker, 1815 – 1864

http://www-gap.dcs.st-and.ac.uk/~history/PictDisplay/Boole.html


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

24/27

Wir ersetzen "wahr" mit "1" und "falsch" mit "0" und wenden die Boolesche Algebra auf logische Ausdrücke an.


Vereinfachung logischer Ausdrücke

25/27

Ananas und Banane oder Ananas und keine Banane oder keine Ananas und keine Banane

Wir möchten einen Fruchtsalat mit Ananas und Bananen oder mit Ananas und keinen Bananen oder mit keinen Ananas und keinen Bananen.

Können wir das einfacher sagen?

Was sagen wir überhaupt?


Vereinfachung logischer Ausdrücke

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?

26/27

Ananas und Banane oder Ananas und keine Banane oder keine Ananas und keine Banane

Ananas oder keine Banane


Verifizierung logischer Ausdrücke

27/27

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:1. Aussage2. Logischer Ausdruck (Symbole)3. Boolesche Algebra4. Ausdruck evaluieren

1. Ausdruck:

7. Ausdruck:

Danke für Ihre Aufmerksamkeit

Documents

Daten verwalten (2)Daten verwalten (2) Logische Verknüpfungen als Grundlage für die Informationsgewinnung Werte von Aussagen: Wahrheitstabellen Grafische