Grundlagen der Logik in der Informatik - Exam

Aufgabe 2)

Wahrheitstabellen und logische ÄquivalenzDu hast gelernt, dass eine Wahrheitstabelle alle möglichen Wahrheitswerte einer logischen Aussage zeigt. Hier sind die wichtigsten Punkte, die Du beachten musst:

• Wahrheitstabelle: zeigt alle möglichen Wahrheitswerte einer logischen Aussage.
• Reihen: jede mögliche Kombination von Wahrheitswerten für alle beteiligten Variablen.
• Spalten: enthalten die Wahrheitswerte der Teilaussagen und der gesamten logischen Aussage.
• Logische Äquivalenz: zwei Aussagen sind logisch äquivalent, wenn sie in allen Fällen denselben Wahrheitswert haben.
• Notation: Aussagen A und B sind äquivalent: \ (A \equiv B\)
• Nützlichkeit: hilft bei der Vereinfachung logischer Ausdrücke und Validierung logischer Argumente.

Aufgabe 3)

Aussagenlogische Formeln und Normalformen Aussagenlogische Formeln und Normalformen sind zentrale Konzepte der Aussagenlogik, die strukturelle Eigenschaften und Vereinfachungen logischer Ausdrücke betreffen.

• Aussagenlogische Formel: Logischer Ausdruck aus Variablen, Junktoren (z.B. \(\land\), \(\lor\), \(eg\)) und Klammern
• Normalformen: Standardisierte Formen logischer Formeln, z.B. KNF, DNF
• Konjunktive Normalform (KNF): Formel als Konjunktion von Disjunktionen \(\bigwedge (\bigvee p_i)\)
• Disjunktive Normalform (DNF): Formel als Disjunktion von Konjunktionen \(\bigvee (\bigwedge p_i)\)
• Transformation: Jede Formel ist äquivalent umwandelbar in KNF/DNF

c)

3. Gegeben sei die aussagenlogische Formel \(D \lor (E \land F)\).

• Forme die gegebene Formel in die disjunktive Normalform (DNF) um.
• Zeige Schritt für Schritt den Umwandlungsprozess.
• Kurzbegründe den Umwandlungsprozess zur DNF.

Lösung:

Lösung:

1. Gegebene Formel: Die gegebene Formel lautet:

   D \lor (E \land F)

2. Schrittweise Umwandlung in die disjunktive Normalform (DNF):
   1. Schritt 1: Ausgangsformel:

      D \lor (E \land F)

   2. Schritt 2: Anwenden des Distributivgesetzes: Um die Formel als Disjunktion von Konjunktionen darzustellen, wenden wir das Distributivgesetz an. Das Distributivgesetz lautet:

      X \lor (Y \land Z) = (X \lor Y) \land (X \lor Z)

      Für unsere Formel bedeutet das:

      D \lor (E \land F) = (D \lor E) \land (D \lor F)

   3. Schritt 3: Darstellung in DNF: Die resultierende Formel \((D \lor E) \land (D \lor F)\) entspricht der disjunktiven Normalform (DNF), da sie als Disjunktion von Konjunktionen dargestellt ist.
3. Kurzbegründung des Umwandlungsprozesses zur DNF:
   • Die disjunktive Normalform (DNF) ist eine standardisierte Form, in der eine Formel als Disjunktion von Konjunktionen dargestellt wird.
   • Das Distributivgesetz ermöglicht es, eine gegebene Formel systematisch in die DNF zu überführen, indem die logischen Junktoren verteilt werden.
   • Durch die Umwandlung in die DNF wird die logische Struktur der Formel klarer dargestellt, was die Analyse und Weiterverarbeitung erleichtert.

Aufgabe 4)

Angenommen, Du hast eine Domäne D = {1, 2, 3} und eine Prädikatenlogik mit den folgenden Prädikaten:

• P(x): x ist eine Primzahl.
• Q(x): x ist eine gerade Zahl.
• R(x): x ist größer als 1.

Untersuche die folgenden Aussagen:

a)

1. Formuliere die Aussagen A1: Jede Zahl in D ist eine Primzahl und A2: Es gibt mindestens eine Zahl in D, die eine Primzahl ist, in der Prädikatenlogik.

• Für A1 benutze den Allquantor.
• Für A2 benutze den Existenzquantor.

Lösung:

Um die Aussagen A1 und A2 in der Prädikatenlogik zu formulieren, verwenden wir die gegebene Domäne D = {1, 2, 3} sowie die Prädikate P(x), Q(x) und R(x).

• A1: Jede Zahl in D ist eine Primzahl.

Diese Aussage erfordert die Verwendung eines Allquantors, der besagt, dass für alle Elemente in der Domäne die Bedingung gilt.

∀x ∈ D: P(x)

In Worten: Für alle x in D gilt: x ist eine Primzahl.

• A2: Es gibt mindestens eine Zahl in D, die eine Primzahl ist.

Diese Aussage erfordert die Verwendung eines Existenzquantors, der besagt, dass es mindestens ein Element in der Domäne gibt, für das die Bedingung gilt.

∃x ∈ D: P(x)

In Worten: Es gibt mindestens ein x in D, für das gilt: x ist eine Primzahl.

b)

2. Zeige, ob A1 in der gegebenen Domäne D wahr oder falsch ist, indem Du die Definition der Prädikate verwendest. Begründe Deine Antwort.

Lösung:

Um zu zeigen, ob die Aussage A1 in der gegebenen Domäne D wahr oder falsch ist, sollten wir die Definitionen der Prädikate verwenden und jedes Element der Domäne prüfen.

Domäne D = {1, 2, 3}

Prädikate:

• P(x): x ist eine Primzahl.
• Q(x): x ist eine gerade Zahl.
• R(x): x ist größer als 1.

A1: Jede Zahl in D ist eine Primzahl.

In Prädikatenlogik ausgedrückt: ∀x ∈ D: P(x)

Jedes Element in der Domäne muss das Prädikat P(x) erfüllen, damit die Aussage wahr ist.

Prüfen wir die Prädikate für jedes Element in der Domäne D:

• x = 1: Ist 1 eine Primzahl? Nein. Also ist P(1) falsch.
• x = 2: Ist 2 eine Primzahl? Ja. Also ist P(2) wahr.
• x = 3: Ist 3 eine Primzahl? Ja. Also ist P(3) wahr.

Da P(1) falsch ist, ist die Aussage ∀x ∈ D: P(x) (A1) insgesamt falsch.

Schlussfolgerung: A1 ist falsch, weil 1 keine Primzahl ist und somit die Bedingung P(x) nicht für alle Elemente in der Domäne D erfüllt ist.

c)

3. Zeige, ob A2 in der gegebenen Domäne D wahr oder falsch ist, indem Du die Definition der Prädikate verwendest. Begründe Deine Antwort.

Lösung:

Um zu zeigen, ob die Aussage A2 in der gegebenen Domäne D wahr oder falsch ist, sollten wir die Definition der Prädikate verwenden und jedes Element der Domäne prüfen.

Domäne D = {1, 2, 3}

Prädikate:

• P(x): x ist eine Primzahl.
• Q(x): x ist eine gerade Zahl.
• R(x): x ist größer als 1.

A2: Es gibt mindestens eine Zahl in D, die eine Primzahl ist.

In Prädikatenlogik ausgedrückt: ∃x ∈ D: P(x)

Mindestens ein Element in der Domäne muss das Prädikat P(x) erfüllen, damit die Aussage wahr ist.

Prüfen wir die Prädikate für jedes Element in der Domäne D:

• x = 1: Ist 1 eine Primzahl? Nein. Also ist P(1) falsch.
• x = 2: Ist 2 eine Primzahl? Ja. Also ist P(2) wahr.
• x = 3: Ist 3 eine Primzahl? Ja. Also ist P(3) wahr.

Da P(2) wahr ist und P(3) ebenfalls wahr ist, haben wir mindestens ein Element in D gefunden, das das Prädikat P(x) erfüllt.

Schlussfolgerung: A2 ist wahr, weil es mindestens eine Zahl in der Domäne D gibt (2 und 3), die eine Primzahl ist.

d)

4. Formuliere die Aussagen B1: Jede Zahl in D ist entweder gerade oder größer als 1 und B2: Es gibt mindestens eine Zahl in D, die weder gerade noch größer als 1 ist, in der Prädikatenlogik. Überprüfe die Wahrheitswerte der Aussagen B1 und B2 in der Domäne D. Begründe Deine Antworten.

Lösung:

Um die Aussagen B1 und B2 in der Prädikatenlogik zu formulieren und ihre Wahrheitswerte in der Domäne D zu überprüfen, verwenden wir die gegebene Domäne D = {1, 2, 3} sowie die Prädikate P(x), Q(x) und R(x).

Domäne D = {1, 2, 3}

Prädikate:

• P(x): x ist eine Primzahl.
• Q(x): x ist eine gerade Zahl.
• R(x): x ist größer als 1.

• B1: Jede Zahl in D ist entweder gerade oder größer als 1.

In Prädikatenlogik ausgedrückt: ∀x ∈ D: (Q(x) ∨ R(x))

Jedes Element in der Domäne muss die Bedingung erfüllen, damit die Aussage wahr ist.

Prüfen wir die Prädikate für jedes Element in der Domäne D:

• x = 1: Ist 1 gerade oder größer als 1? Q(1) ist falsch (1 ist nicht gerade), aber R(1) ist falsch (1 ist nicht größer als 1). Also ist (Q(1) ∨ R(1)) falsch.
• x = 2: Ist 2 gerade oder größer als 1? Q(2) ist wahr (2 ist gerade) und R(2) ist wahr (2 ist größer als 1). Also ist (Q(2) ∨ R(2)) wahr.
• x = 3: Ist 3 gerade oder größer als 1? Q(3) ist falsch (3 ist nicht gerade), aber R(3) ist wahr (3 ist größer als 1). Also ist (Q(3) ∨ R(3)) wahr.

Da (Q(1) ∨ R(1)) falsch ist, ist die Aussage ∀x ∈ D: (Q(x) ∨ R(x)) (B1) insgesamt falsch.

• B2: Es gibt mindestens eine Zahl in D, die weder gerade noch größer als 1 ist.

In Prädikatenlogik ausgedrückt: ∃x ∈ D: ¬(Q(x) ∨ R(x))

Mindestens ein Element in der Domäne muss die Bedingung erfüllen, damit die Aussage wahr ist.

Prüfen wir die Prädikate für jedes Element in der Domäne D:

• x = 1: Ist 1 weder gerade noch größer als 1? Q(1) ist falsch (1 ist nicht gerade) und R(1) ist falsch (1 ist nicht größer als 1). Also ist ¬(Q(1) ∨ R(1)) wahr.
• x = 2: Ist 2 weder gerade noch größer als 1? Q(2) ist wahr (2 ist gerade) und R(2) ist wahr (2 ist größer als 1). Also ist ¬(Q(2) ∨ R(2)) falsch.
• x = 3: Ist 3 weder gerade noch größer als 1? Q(3) ist falsch (3 ist nicht gerade), aber R(3) ist wahr (3 ist größer als 1). Also ist ¬(Q(3) ∨ R(3)) falsch.

Da ¬(Q(1) ∨ R(1)) wahr ist, ist die Aussage ∃x ∈ D: ¬(Q(x) ∨ R(x)) (B2) wahr.

Schlussfolgerung:

• B1: Falsch, weil 1 weder gerade noch größer als 1 ist.
• B2: Wahr, weil 1 weder gerade noch größer als 1 ist.