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

• 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

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

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

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

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

• Werte von Aussagen: Wahrheitstabellen

• Grafische vs. formale Darstellung von Abfragen

• Boolesche Algebra

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

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

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

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

• Daten verwalten (2)

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

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

• Boolesche Algebra

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

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

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

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

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

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

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

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

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

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

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

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

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

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?

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

Das neue Plakat

© Raphael Theiler

16/27

Informatik für Biol. & Pharm. Wissenschaften © Departement Informatik, 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 )

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

• Daten verwalten (2)

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

• Werete von Aussagen: Wahrheitstabellen

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

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

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

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

Grafische vs. formale Darstellung logischer Verknüpfungen

Eisen

19/27

Menge and Eisen

Zink

Menge

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

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

Grafische vs. formale Darstellung logischer Verknüpfungen

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?

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

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))

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

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)

• Daten verwalten (2)

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

• Werte von Aussagen: Wahrheitstabellen

• Grafische vs. formale Darstellung von Abfragen

• Boolesche AlgebraBoolesche Algebra

Informatik für Biol. & Pharm. Wissenschaften © Departement Informatik, 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; 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

Informatik für Biol. & Pharm. Wissenschaften © Departement Informatik, 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

24/27

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

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

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?

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

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

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

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