Diskrete Strukturen - 1. Kapitel - Logik

Logik, Aussagen und Aussagefunktionen, Logische Operanden

57 flashcards · Mathematics · by Pepper and Love

1. Abstraktion bedeutet "Unwesentliches weglassen" mit dem Ziel, das Wesentliche besser verstehen zu können.

2. Modellieren abstrahiert mittels

   des Erstellens eines Modells von der Realität - es sind Beschreibungen die sich auf das Wesentliche beschränken.

3. Kollektionen sind Ansammlungen von Objekten und sind Teil des Modells.

4. Mengen sind ?

   Kollektionen bei denen die Reihenfolge der Objekte nicht relevant ist, und auch nicht ob die mehrfach vorkommen. {1,2,3} ={2,1,3,4}

5. Tupel sind ?

   Kollektionen in denen die Reihenfolge der Objekte relevant ist, und ob die mehrmals vorkommen. [1,2,3]

6. Eine Aussage ist ?

   Ein Satz, von dem man eindeutig entschieden kann, ob er wahr oder falsch ist.

7. Eine Aussageform ist ?

   Ein Ausdruck der eine ( oder mehrere ) freie Variablen enthält und durch die Belegung aller freien Variablen in eine ( wahre oder falsche ) Aussage übergeht.

8. Ein unärer Operator

   Wirkt nur auf einen einzigen Operanden ( z.B. Negation ).

9. binäre Operanden

   sie verknüpfen zwei Operanden ( z.B. Konjunktion).

10. Negation (Verneinung)

    einer Aussage a ist genau dann wahr, wenn a falsch ist. Die Verneinung von a wird symbolisch mit a oder ¬a bezeichnet ( ” nicht a“). Der Tank ist voll. Die Verneinung ist ” Es trifft nicht zu, dass der Tank voll ist“ bzw., etwas einfacher, ” Der Tank ist nicht voll“. Achtung: Im ersten Moment möchte man als Verneinung vielleicht ”Der Tank ist leer“ sagen. Das ist aber nicht gleichbedeutend mit ” Der Tank ist nicht voll“, denn er könnte ja auch halb voll sein.

11. Verneinung von Aussage: ” Wenn Du zu meiner Party kommst, lernst Du nette Leute kennen.“

    ” Du kommst zu meiner Party und Du lernst nicht nette Leute kennen.“ ” Du kommst zu meiner Party, aber lernst keine netten Leute kennen.“ Erklärung: P = ” Du kommst zu meiner Party.“ L = ” Du lernst nette Leute kennen. " P→LP \rarr LP→L - dann sind die ersten beiden Vorschläge als P→¬LP \rarr ¬L P→¬L bzw. ¬P→¬L ¬P\rarr¬L¬P→¬L modellieren wenn man das in eine Wahrheitstabelle ausdruckt seht man das die beiden keine Negation sind weil die kein "0" ergeben. also wäre das hier die richtige Negation…

12. Was ist eine Konjunktion ?

    UND-Verknüpfung oder Konjunktion zweier Aussagen A und B ist eine Aussage die genau dann wahr ist, wenn beide Aussagen wahr sind, symbolisch A ∧\land∧ B

13. Was ist eine Disjunktion ?

    ODER-Verknüpfung oder Disjunktion zweier Aussagen A und A ist eine Aussage, die genau dann wahr ist, wenn mindestens eine der beiden Aussagen wahr ist, symbolisch A ∨\lor∨ B ( gelesen A oder B )

14. Was ist eine Alternation ( XOR ) ?

    das ausschließende "oder" im Sinn von Entweder...Oder wird symbolisch mit A xor B ( eng. eXclusive OR) oder A ⊕\oplus⊕ B ist wahr genau dann, wenn entweder A oder B wahr sind.

16. Was ist eine Subjunction ?

    WENN-DANN-Verknüpfung oder Subjunction A →\to→ B gelesen ( "Wenn A, dann B " ) ist dann wahr wenn beide wahr sind, oder beide falsch sind, oder A falsch ist und zu wahr wird, umgekehrt geht es nicht, A kann nicht wahr sein und zu falsch werden kurz gesagt: Subjunktion A→ B zweier Aussagen A und B ist nur dann falsch, wenn A wahr und B falsch ist

17. Was ist eine Bijunktion ( Äquivalenz ) ?

    GENAU-DANN-Verknüpfung oder Bijunktion ( auch Äquivalenz ) A ⇔ B ( "A genau dann, wenn B") ist dann wahr wenn beide wahr oder falsch sind, wenn A →\to→ B wahr und B →\to→ A wahr ist ( wenn die beiden verknüpften Aussagen gleiche Wahrheitswerte haben) A ⇔ B bedeutet dasselbe wie “A ↔ B ∧ B ↔ A”. Man sagt: “ A genau dann, wenn B” oder “A dann und nur dann, wenn B”. dan spricht man von einer Äquivalenz. “x gerade ⇔ x durch 2 teilbar”

18. Was ist eine Tautologie ?

    Aussageformen bzw. logische Ausdrucke, die unabhängig von der Belegung ihrer Variablen immer wahr sind. A ⇐ B heißen Implikationen, A ⇔B heißen Äquivalenzen.

19. Das Kommutativgesetz (Logikgesetze):

    bedeutet, dass die Operanden einer binären Operation vertauscht werden können, ohne dass sich der Wert des Ausdrucks ändert A ∧ B ⇔ B ∧ A A ∨ B ⇔ B ∨ A

20. Das Assoziativgesetz (Logikgesetze):

    ” freie Partnerwahl“ ist es egal, ob sich B erst mit dem linken Partner A verbandelt und das Ergebnis dann mit C - oder ob B erst mit dem rechten Partner C anbandelt und das Ergebnis dann mit A. man kann die Klammern auch weglassen (es müssen die gleichen Operanden sein, sonst gibt es Präzedenz) A ∧ (B ∧ C) ⇔ (A ∧ B) ∧ C A ∨ (B ∨ C) ⇔ (A ∨ B) ∨ C

21. Das Distributivgesetz (Logikgesetze):

    A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C) A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C)

22. Logische Äquivalenzregeln: Ersetzen der Implikation

    ( A →\to→ B ) ⇔ ( ¬A ∨ B) (Die Subjunktion kann also durch eine Kombination aus Negation und Disjunktion umschrieben werden)

23. Logische Äquivalenzregeln: Ersetzen der Äquivalenz:

    (A ↔ B) ⇔ (A →\to→ B) ∧ (B →\to→ A)

24. Logische Äquivalenzregeln: de Morgan

    ¬(A ∧ B) ⇔ (¬A ∨ ¬B) ¬(A ∨ B) ⇔ (¬A ∧ ¬B)

25. Logische Äquivalenzregeln: doppelte Negation

    ¬¬A ⇔ A

26. Logische Äquivalenzregeln: Absorption

    Hier ist die Erklärung:

27. Was ist eine faule Auswertung ?

    Wenn wir in binären Operanden einen konstanten Wahrheitswert haben der uns sofort den Wert des Ausdruckes zeigt. Disjunktion: A ∨ 1 ( wird immer wahr sein) wir können direkt 1 schrieben. Konjunktion: A ∧ 0 ( wird immer falsch sein) wir können direkt 0 schreiben.

28. Was ist mit tertium non datur gemeint ?

    Lateinisch für ” eine dritte Möglichkeit gibt es nicht“ – eine dritte Möglichkeit neben A und ¬A A ∨ ¬A ⇔ 1 (Tautologie) A ∧ ¬A ⇔ 0 (keine Tautologie) Die Negation von A ∧ ¬A : macht ¬ ( A ∧ ¬A ) zu einer Tautologie.

29. Was ist mit neutrales Element gemeint ?

    A ∨ 0 ⇔ A A ∧ 1 ⇔ A

30. Was ist mit Idempotenz gemeint ?

    A ∨ A ⇔ A A ∧ A ⇔ A

31. Beispiel: Aussagenlogisches Rechnen

32. Logische Schlussregeln: Kettenschlussregel

    (A→B) ∧ (B →\to→ C) ⇔ (A →\to→ C) ( wenn aus A dan B und aus B dan C dan ist aus A dan C ) – Sei A wahr. ∗ Da A → B und A wahr sind, muss auch B wahr sein. ∗ Da B → C und B wahr sind, muss auch C wahr sein. Insbesondere ist in dem Fall A → C wahr. – Sei A falsch. Dann ist A → C automatisch wahr.

33. Logische Schlussregeln: Widerspruchsregel

    (¬B→(A ∧ ¬A)) ⇒ B da (A ∧ ¬A) tertium non datur ist, immer falsch, um einen wahren Ausdruck zu haben muss ¬B falsch sein, daher ist B wahr

34. Was versteht man unter Logischen Schlussregeln ?

    Seien φ und ψ Aussageformeln in Aussagenvariablen A, B,... Wir schreiben φ ⇒ ψ und sagen, dass ψ logisch aus φ folgt, wenn folgende Bedingung erfüllt ist: jede Kombination von Wahrheitswerten für A, B, . . ., die φ zu einer wahren Aussage macht, macht auch ψ zu einer wahren Aussage. Insbesondere gilt also φ ⇔ ψ genau dann, wenn φ ⇒ ψ und ψ ⇒ φ. Man setzt dabei stets voraus, dass die Schlussregel korrekt ist im folgenden Sinne: falls φ1, . . . , φn wahr sind, so ist auch ψ wahr. eine Folgerung i…

35. Logische Schlussregeln: Modus ponens

    (A→B) ∧ A ⇔ B Grundform des direkten Beweises: Begründung der Korrektheit: Sind die beiden Prämissen wahr, so ist A wahr ( da es eine Konjunktion ist ) A → B wahr und bei dem A wahr ist, ist auch B wahr weil eine Subjunktion von wahr nur wahr implizieren kann oder die wäre falsch

36. Logische Schlussregeln: Modus tollens

    (A → B) ∧¬B ⇔¬A Begründung der Korrektheit: Sind die Prämissen wahr, so ist ¬B wahr, also B falsch (In der Konjunktion Ausdruck) (A → B) wahr und B falsch, also A falsch und dammit ¬A wahr

37. Logische Schlussregeln: Negationsregel

    ¬(A → B) ⇔ (¬B ∧ A) um ¬(A → B) wahr zu sein, muss (A → B) falsch sein, um falsch zu sein muss A wahr sein, und B falsch und um eine Äquivalenz zu haben muss die Konjunktion wahre werte haben daher (¬B ∧ A)

38. Logische Schlussregeln: Kontrapositionsregel

    (A → B) ⇔ (¬B → ¬A) um immer eine Äquivalenz zu haben, müssen die Ausdrucke immer wahr sein - im Fall das A falsch ist und B richtig, wenn man die Plätze bei der Negation nicht vertauschen würde hätte man ¬A → ¬B ( wahr zu falsch) und dan wäre der Ausdruck auch falsch, daher ¬B → ¬A

39. Ersetzt man in einer Aussage a irgendeine Konstante durch eine Variable x, so entsteht eine Aussageform a(x) (auch Aussagefunktion genannt).

40. Aussageformen haben zwei Bestandteile: Variablen und den Rest. Dieser Rest wird in der Logik als Prädikat bezeichnet. Die Aussageform ” x ist größer als 1“ hat die Variable x und das Prädikat ” ist größer als 1“.

41. Aussagen in Prädikate umformen: Wer schlau ist, der studiert.

    • Schlau(x) steht für: x ist schlau. • Studieren(x) steht für: x studiert. • Definitionsbereiche: x ist eine beliebige Person • Schlau(x)→Studieren(x)

42. Aussagen in Prädikate umformen: Wer schlau ist und gerne programmiert, der studiert Informatik.

    Schlau(x) ∧ Programmieren(x)→Studieren(x, Informatik)

43. Was ist eine All-Aussage ?

    gegeben ist eine Aussageform A(x). Die Aussage "für alle x ( aus einer bestimmten Menge) gilt A(x)" - ist wahr genau dann, wenn A(x) für alle in Frage kommenden x wahr ist. Symbolische Schreibweise: ∀ x ∈ M : A(x) wobei ∀ ”für alle” gelesen wird (oder “für jedes”). Das Symbol ∀ heißt All-Quantor.

44. Die Aussage ” Fur alle x (aus einer bestimmten Menge) gilt a(x)“ ist wahr genau dann, wenn a(x) für alle in Frage kommenden x wahr ist. Abkürzend schreibt man für diese All-Aussage ∀ x ∈ M : A(x).

45. Die Aussage ” Es gibt ein x (aus einer bestimmten Menge), sodass a(x)“ ist wahr genau dann, wenn a(x) für zumindest eines der in Frage kommenden x wahr ist. Symbolisch schreibt man diese Existenz-Aussage ∃ x ∈ M : A(x).

46. Was ist eine Existenz-Aussage ?

    Die Aussage “Es gibt ein x (aus einer bestimmten Menge), sodass A(x)” wahr ist genau dann, wenn A(x) für zumindest eines der in Frage kommenden x wahr ist. Symbolische Schreibweise: ∃ x ∈ M : A(x) wobei ∃ “es gibt (mindestens) ein” gelesen wird (oder auch: “es existiert (mindestens) ein” oder “für (mindestens) ein”). Das Symbol ∃ heißt Existenz-Quantor.

47. Quantifizierte Aussagen ( Quantoren ) haben 3 wesentliche Bestandteile: Quantor, die Variablen mit Mengenangabe und Prädikate.

48. Modellieren sie diese Aussage mit Quantoren: ” Jede natürliche Zahl ist positiv“

    Quantor: Jede, Variable: natürliche Zahl ( Zahl aus der Menge der natürlichen Zahlen), Prädikat: ist positiv ∀(n ∈ N | n > 0)

49. Was entsteht durch die Negation von All- und Existenz-aussagen ?

    Durch die Verneinung einer All-Aussage entsteht eine Existenz-Aussage, und umgekehrt entsteht durch die Verneinung einer Existenz-Aussage eine All-Aussage.

50. Verneinen Sie diese Aussage (Quantoren): Es gibt einen Studenten, der Spanisch spricht.

    Die Aussage hat die Form ” ∃x: x spricht Spanisch“ (wobei x ein beliebiger Student ist). Verneinung: ” ∀x: x spricht nicht Spanisch“, in Worten also: ” Fur jeden Studenten gilt: Er/sie spricht nicht Spanisch“, bzw. ” Kein Student spricht Spanisch“.

51. Ist die verknüpfte Aussage a → b wahr, so spricht man von einem logischen Schluss (oder einer Implikation) und schreibt a ⇒ b. Für a ⇒ b sagt man: ” Aus a folgt b“ oder ” a impliziert b“, oder ”Wenn a, dann b“ oder ” a ist hinreichend fur b“ oder ” b ist notwendig für a“.

52. Negieren Sie: ∀ x ∈ Menschen : Mögen_mathematik(x)

    ∃ x ∈ Menschen : mögen_nichtMathe(x)

53. Umformen Sie die Aussage mit Quantoren: "Alle schlauen Menschen studieren Informatik."

    ∀x ∈ M: schlau(x)→studieren(x, Informatik)

54. Umformen Sie die Aussage mit Quantoren: "Bälle, die groß sind, sind auch rot." (Relativsatz)

    Formel: ∀x : E(x)→F(x)

55. Formel: Kein Ball ist rot.

    ¬∃y : F(x)

56. Was versteht man unter Äquivalenzoperator ?

    Klammern machen klar, in welcher Reihenfolge Operatoren ausgewertet werden müssen. Um vieles ausklammern zu vermeiden wird das Äquivalenzen Symbol genutzt z.B. A →\to→ B ⇔ ¬A ∨ B statt (A →\to→ B) = (¬A ∨ B) A ⇔ B druckt aus, dass A und B immer und garantiert den gleichen Wahrheitswert haben. Das Symbol ⇔ wird als Äquivalenzoperator bezeichnet und ”gleichbedeutend mit“ oder ” äquivalent zu“ ausgesprochen.

57. Was versteht man unter Präzedenz ?