Theoretische Informatik für Klasse 10: Online-Quizze und Übungen

Question 1

Übersetzen Sie die folgende Aussage in prädikatenlogische Notation: "Alle Schüler an dieser Schule haben Mathematik als Lieblingsfach".

Accepted Answer

∀x (Student(x) → Lieblingsfach(x, Mathematik))

Answer

∃x (Student(x) ∧ Lieblingsfach(x, Mathematik))

Answer

∀x (Lieblingsfach(x, Mathematik) → Student(x))

Answer

∃x (Student(x) ∨ Lieblingsfach(x, Mathematik))

Question 2

Es sind die Aussagen gegeben: p: 'Es regnet' und q: 'Die Sonne scheint'. Formuliert einen aussagenlogischen Ausdruck, der aussagt, dass es regnet, aber die Sonne nicht scheint.

Accepted Answer

p ∧ ¬q

Answer

¬(p ∨ q)

Answer

q → p

Question 3

Welche Menge ergibt sich aus der Schnittmenge der Menge A der durch 3 teilbaren natürlichen Zahlen und der Menge B der durch 5 teilbaren natürlichen Zahlen?

Accepted Answer

Die Menge aller durch 15 teilbaren natürlichen Zahlen

Answer

Die Menge aller durch 3 teilbaren natürlichen Zahlen

Answer

Die Menge aller natürlichen Zahlen

Answer

Die leere Menge

Question 4

Gegeben sind die Menge A der natürlichen Zahlen kleiner als 10 und die Menge B der ungeraden Zahlen kleiner als 10. Bestimme die Schnittmenge A ∩ B.

Accepted Answer

{1, 3, 5, 7, 9}

Answer

{1, 2, 3, 4, 5, 6, 7, 8, 9}

Answer

{2, 4, 6, 8}

Answer

∅

Question 5

Übersetze die Aussage "Alle Hunde sind Säugetiere" in prädikatenlogische Notation.

Accepted Answer

∀x(Hund(x) → Säugetier(x))

Answer

∀x(Säugetier(x) → Hund(x))

Answer

∃x(Hund(x) ∧ Säugetier(x))

Question 6

Überprüfe die Gültigkeit der Aussage: 'Ein gleichschenkliges Dreieck hat zwei gleiche Seiten.' Erstelle eine Wahrheitstabelle, um deine Antwort zu begründen.

Accepted Answer

A: Gültig, denn die Aussage ist in allen Fällen wahr.

Answer

B: Ungültig, denn es gibt Fälle, in denen die Aussage falsch ist.

Answer

C: Weder gültig noch ungültig, denn die Wahrheitstabelle zeigt gemischte Ergebnisse.

Question 7

Welche Aussage trifft auf die Mengen A und B zu? Menge A umfasst die natürlichen Zahlen kleiner als 5, und Menge B umfasst die ungeraden Zahlen kleiner als 5.

Accepted Answer

A ist eine echte Teilmenge von B.

Answer

A ist keine echte Teilmenge von B.

Question 8

Übersetze die Aussage "Es gibt mindestens einen Schüler, der Mathematik mag" in prädikatenlogische Notation.

Accepted Answer

∃x ∈ S : M(x)

Answer

∀x ∈ S : M(x)

Answer

∃x ∈ M : S(x)

Answer

∀x ∈ M : S(x)

Question 9

Beurteile das folgende Argument: "Alle Menschen sind sterblich. Sokrates ist ein Mensch. Folglich ist Sokrates sterblich." Ist dieses Argument logisch korrekt und wahr?

Accepted Answer

Das Argument ist sowohl logisch korrekt als auch wahr.

Answer

Das Argument ist logisch korrekt, aber nicht wahr, da die Aussage "Alle Menschen sind sterblich" nicht zutrifft.

Answer

Das Argument ist wahr, aber nicht logisch korrekt, da die Aussage "Alle Menschen sind sterblich" nicht zutrifft.

Answer

Das Argument ist weder logisch korrekt noch wahr.

Question 10

Welche der folgenden Aussagen über die Mengen A = {1, 2} und B = {3, 4} ist korrekt?

Accepted Answer

A und B sind disjunkt

Answer

A ist eine Teilmenge von B

Answer

B ist eine Teilmenge von A

Answer

A und B sind gleichmächtig

Question 11

Übersetzen Sie die Aussage **"Kein Lehrer ist älter als 50 Jahre"** in prädikatenlogische Notation.

Accepted Answer

∀x(Lehrer(x) → Alter(x) ≤ 50)

Answer

∃x(Lehrer(x) ∧ Alter(x) > 50)

Answer

∀x(Lehrer(x) → Alter(x) > 50)

Answer

∃x(Lehrer(x) ∧ Alter(x) ≤ 50)

Question 12

Übersetzen Sie die folgende Aussage in prädikatenlogische Notation: Es gibt einen Schüler in dieser Klasse, der sowohl Mathematik als auch Informatik mag.

Accepted Answer

∃x (Schüler(x) ∧ Mag(x, Mathematik) ∧ Mag(x, Informatik))

Answer

∀x (Schüler(x) → (Mag(x, Mathematik) ∨ Mag(x, Informatik)))

Answer

¬∃x (Schüler(x) ∧ (Mag(x, Mathematik) ∨ Mag(x, Informatik)))

Question 13

Was ist eine Bijektion zwischen zwei Mengen?

Accepted Answer

Eine Funktion, die jedem Element aus Menge A ein Element aus Menge B zuordnet und umgekehrt.

Answer

Eine Teilmenge von Menge A, die alle Elemente von Menge B enthält.

Answer

Eine Operation, die Menge A und Menge B vereinigt.

Answer

Eine Menge, die die Schnittmenge von Menge A und Menge B enthält.

Question 14

Übersetzen Sie die Aussage **Es gibt eine natürliche Zahl, die gerade ist** in die prädikatenlogische Schreibweise.

Accepted Answer

∃x (Nat(x) ∧ Gerade(x))

Answer

∀x (Nat(x) → Gerade(x))

Answer

∃x (Nat(x) ∨ Gerade(x))

Answer

∀x (Nat(x) ∧ Gerade(x))

Question 15

Welche der folgenden Aussagen ist eine Tautologie?

Accepted Answer

p ∧ (p → q)

Answer

p → ¬p

Answer

¬(p → q) → p

Answer

(p → q) → ¬q

Question 16

Sei P die Menge der Primzahlen und Q die Menge der Quadratzahlen. Welcher der folgenden Ausdrücke bezeichnet die Differenzmenge von P und Q?

Accepted Answer

P - Q

Answer

Q - P

Answer

P ∩ Q

Answer

P ∪ Q

Question 17

Welche der folgenden Aussagen ist ein Beispiel für einen Prädikatenkalkül?

Accepted Answer

x ist eine Primzahl.

Answer

x > 5

Answer

x + y = 10

Answer

x ist größer als y.

Question 18

Welche der folgenden Regeln der natürlichen Deduktion erlaubt es uns, aus den Annahmen p und q die Folgerung q → p abzuleiten?

Accepted Answer

Implikationsentfernung

Answer

Modus Ponens

Answer

Modus Tollens

Answer

Disjunktionseinführung

Question 19

Welche der folgenden Aussagen ist eine gültige Folgerung aus den Prämissen "Alle Menschen sind sterblich" und "Sokrates ist ein Mensch"?

Accepted Answer

Sokrates ist sterblich.

Answer

Alle sterblichen Wesen sind Menschen.

Answer

Sokrates ist unsterblich.

Answer

Es gibt keine unsterblichen Menschen.

Question 20

Frage: Was ist die Kardinalität einer Menge in der Mengenlehre? Nenne ein Beispiel für zwei Mengen mit gleicher Kardinalität.

Accepted Answer

Antwort: Die Kardinalität einer Menge ist die Anzahl ihrer Elemente.

Answer

Antwort: Die Kardinalität einer Menge ist die Summe ihrer Elemente.

Answer

Antwort: Die Kardinalität einer Menge ist ihr größtes Element.

Answer

Antwort: Die Kardinalität einer Menge ist ihre kleinste Teilmenge.

Question 21

Was ist eine Äquivalenzrelation? Nenne ein Beispiel aus dem Alltag.

Accepted Answer

Eine Äquivalenzrelation ist eine Beziehung zwischen Elementen einer Menge, die reflexiv, symmetrisch und transitiv ist.

Answer

Eine Äquivalenzrelation kann auf jede Menge angewendet werden.

Answer

Eine Äquivalenzrelation ist eine Beziehung, die sowohl transitiv als auch antisymmetrisch ist.

Question 22

Übersetzen Sie die folgende Aussage in prädikatenlogische Notation: "Es existiert eine reelle Zahl, die größer als 0 und kleiner als 1 ist."

Accepted Answer

∃x ∈ ℝ : 0 < x < 1

Answer

∀x ∈ ℝ : 0 < x < 1

Answer

∃x ∈ ℚ : 0 < x < 1

Answer

∀x ∈ ℕ : 0 < x < 1

Question 23

Welche Aussage ist eine logisch gültige Schlussfolgerung aus den Aussagen "Alle Menschen sind sterblich" und "Sokrates ist ein Mensch"?

Accepted Answer

Sokrates ist sterblich.

Answer

Sokrates ist unsterblich.

Answer

Alle sterblichen Wesen sind Menschen.

Question 24

Wie wirkt sich die Position von Quantoren in einem Ausdruck auf seine Bedeutung aus?

Accepted Answer

Die Position der Quantoren ist entscheidend für die Bedeutung des Ausdrucks.

Answer

Quantoren binden Variablen an einen bestimmten Wert.

Answer

Quantoren können nur in Aussagen verwendet werden, die eine universelle Quantifizierung ausdrücken.

Answer

Zwei Quantoren desselben Typs, die dieselbe Variable binden, können direkt nebeneinander stehen.

Question 25

Was ist eine rekursive Definition? Wähle die beste Beschreibung.

Accepted Answer

Eine Definition, die sich selbst verwendet.

Answer

Eine Definition, die unendlich viele Schritte benötigt.

Answer

Eine Definition, die auf Mengenlehre basiert.

Answer

Eine Definition, die einen Kreislauf enthält.

Question 26

Übersetzen Sie die Aussage in die prädikatenlogische Notation: "Es gibt eine natürliche Zahl kleiner als 10, die durch 3 teilbar ist."

Accepted Answer

∃x(Nat(x) ∧ x < 10 ∧ 3 | x)

Answer

∀x(Nat(x) ∧ x < 10 ∧ 3 | x)

Answer

∃x(Nat(x) ∧ x > 10 ∧ 3 | x)

Question 27

Frage: Was ist der Unterschied zwischen einer Aussageform und einer Aussage in der Aussagenlogik?

Accepted Answer

Eine Aussageform enthält Variablen, während eine Aussage konkrete Werte hat.

Answer

Eine Aussage kann wahr oder falsch sein, während eine Aussageform immer wahr ist.

Answer

Eine Aussageform enthält Quantoren, während eine Aussage keine Quantoren enthält.

Answer

Es gibt keinen Unterschied zwischen einer Aussageform und einer Aussage.

Question 28

Was ist eine Äquivalenzrelation? Nenne ein Beispiel aus dem Alltag.

Accepted Answer

Eine Äquivalenzrelation ist eine Beziehung zwischen Elementen einer Menge, die reflexiv, symmetrisch und transitiv ist.

Answer

Eine Äquivalenzrelation kann nur auf endlichen Mengen definiert werden.

Answer

Eine Äquivalenzrelation kann nur auf Mengen von Zahlen definiert werden.

Question 29

Was ist eine Bijektion zwischen zwei Mengen? Nenne ein Beispiel, das keine Eins-zu-eins-Abbildung ist.

Accepted Answer

Eine Bijektion ist eine Abbildung, die jedem Element der einen Menge genau ein Element der anderen Menge zuordnet und umgekehrt.

Answer

Eine Bijektion ist eine Abbildung, die die Anzahl der Elemente in beiden Mengen gleich lässt.

Answer

Eine Bijektion ist eine Abbildung von einer Menge auf sich selbst.

Answer

Eine Bijektion ist eine Abbildung, die nur eine endliche Anzahl von Elementen zuordnet.

Question 30

Frage:
Die Menge A besteht aus allen rationalen Zahlen zwischen 0 und 1. Ist die Menge A endlich oder unendlich?

Accepted Answer

Unendlich

Answer

Endlich

Question 31

Formulieren Sie die Aussage "Jede gerade Zahl ist durch 2 teilbar" in prädikatenlogischer Schreibweise.

Accepted Answer

∀x (Gerade(x) → Teilbar_durch_2(x))

Answer

∃x (Gerade(x) → Teilbar_durch_2(x))

Answer

¬∀x (Gerade(x) → Teilbar_durch_2(x))

Answer

∃x (Gerade(x) ∧ ¬Teilbar_durch_2(x))

Question 32

Welche Aussage lässt sich logisch aus den Aussagen "Alle Menschen sind sterblich" und "Sokrates ist ein Mensch" ableiten?

Accepted Answer

Sokrates ist sterblich.

Answer

Einige Sterbliche sind Menschen.

Answer

Alle Griechen sind sterblich.

Answer

Keine Aussage kann abgeleitet werden.

Question 33

Welche Mengenoperation ergibt eine Menge, die alle Elemente enthält, die sowohl in Menge A als auch in Menge B enthalten sind?

Accepted Answer

Schnittmenge

Answer

Vereinigung

Answer

Differenzmenge

Answer

Symmetrische Differenzmenge

Question 34

Welche Aussage beschreibt die Beziehung zwischen der Potenzmenge einer Menge und der Menge selbst?

Accepted Answer

Die Menge selbst ist immer eine Teilmenge ihrer Potenzmenge.

Answer

Die Potenzmenge einer Menge ist immer eine Teilmenge der Menge selbst.

Answer

Die Potenzmenge einer Menge ist immer leer.

Answer

Die Potenzmenge einer Menge hat immer die gleiche Anzahl von Elementen wie die Menge selbst.

Question 35

Welche der folgenden Aussagen ist eine universelle Aussage?

Accepted Answer

Alle Katzen sind Säugetiere.

Answer

Einige Menschen sind Vegetarier.

Answer

Es gibt keine weißen Raben.

Answer

Die Hauptstadt Deutschlands ist Berlin.

Question 36

Welche Menge enthält die Zahlen 2, 4, 6, 8, 10?

Accepted Answer

{x | x ist eine gerade Zahl kleiner als 10}

Answer

{x | x ist eine ungerade Zahl kleiner als 10}

Answer

{x | x ist eine natürliche Zahl kleiner als 10}

Answer

{x | x ist eine Primzahl kleiner als 10}

Question 37

Welche Aussage trifft auf die Menge der rationalen Zahlen zu?

Accepted Answer

Sie ist abzählbar unendlich.

Answer

Sie ist endlich.

Answer

Sie ist überabzählbar unendlich.

Answer

Sie ist leer.

Question 38

Welche logische Verknüpfung ist wahr, wenn mindestens eine der Aussagen wahr ist?

Accepted Answer

Disjunktion

Answer

Konjunktion

Answer

Implikation

Answer

Äquivalenz

Question 39

Welche Menge ergibt sich aus der Vereinigung von A = {1, 2, 3} und B = {3, 4, 5}?

Accepted Answer

{1, 2, 3, 4, 5}

Answer

{1, 3}

Answer

{2, 4, 5}

Answer

{3}

Question 40

Welche Aussage beschreibt eine partielle Funktion?

Accepted Answer

Für einige Elemente aus A existiert kein Element in B

Answer

Für jedes Element aus A existiert ein eindeutiges Element in B

Answer

Für jedes Element aus B existiert ein eindeutiges Element in A

Answer

Für kein Element aus A existiert ein Element in B

Question 41

Welche Menge ist eine Teilmenge von {1, 2, 3, 4, 5}?

Accepted Answer

{1, 2}

Answer

{6, 7}

Answer

{2, 4, 6}

Answer

{Ø}

Question 42

Welche Aussage beschreibt eine bijektive Funktion?

Accepted Answer

Für jedes Element aus A existiert ein eindeutiges Element in B und umgekehrt

Answer

Für jedes Element aus A existiert ein eindeutiges Element in B, aber nicht umgekehrt

Answer

Für einige Elemente aus A existiert kein Element in B, aber umgekehrt schon

Answer

Für kein Element aus A existiert ein Element in B und umgekehrt

Question 43

Welche der folgenden Aussagen ist ein Widerspruch?

Accepted Answer

A und nicht A

Answer

A oder nicht A

Answer

Wenn A, dann B. A. Also B

Answer

Wenn A, dann B. Nicht A. Also nicht B

Question 44

Welche Menge ist das Komplement von {2, 4, 6} in der Grundmenge {1, 2, 3, 4, 5, 6}?

Accepted Answer

{1, 3, 5}

Answer

{1, 2, 3}

Answer

{2, 4, 6}

Answer

{2, 4, 6, 8}

Question 45

Übersetzen Sie die Aussage in prädikatenlogische Notation: "Alle Schüler, die sowohl Mathematik als auch Informatik mögen, sind intelligent."

Accepted Answer

∀x (Schüler(x) ∧ (Mag(x, Mathematik) ∧ Mag(x, Informatik)) → Intelligent(x))

Answer

∃x (Schüler(x) ∧ (Mag(x, Mathematik) ∧ Mag(x, Informatik)) → Intelligent(x))

Answer

∀x (Schüler(x) ∧ (Mathematik(x) ∧ Informatik(x)) → Intelligent(x))

Answer

∃x (Schüler(x) ∧ (Mathematik(x) ∨ Informatik(x)) → Intelligent(x))

Question 46

Welche der folgenden Operationen ist assoziativ?

Accepted Answer

Vereinigung von Mengen

Answer

Komplement von Mengen

Answer

Schnittmenge von Mengen

Answer

Differenz von Mengen

Question 47

Welche der folgenden Aussagen ist wahr über deterministische endliche Automaten (DFA)?

Accepted Answer

Ein DFA kann nur eine akzeptierende Zustandsmenge haben.

Answer

Ein DFA kann mehrere akzeptierende Zustandsmengen haben.

Answer

Ein DFA kann nicht-deterministische Übergänge haben.

Question 48

Welche der folgenden syntaktischen Kategorien ist eine Nichtterminale?

Accepted Answer

Answer

;

Answer

int

Answer

while

Question 49

Welche der folgenden Eigenschaften ist für rekursiv aufzählbare Sprachen charakteristisch?

Accepted Answer

Sie können durch eine Turingmaschine akzeptiert werden, die bei Annahme anhält.

Answer

Sie sind immer endlich.

Question 50

Welche der folgenden Aussagen ist in der Prädikatenlogik eine allgemeine Aussage?
(Eine allgemeine Aussage gilt für alle Elemente einer Menge.)

Accepted Answer

∀ x (P(x) → Q(x))

Answer

P(a)

Answer

∃ x (P(x) ∧ Q(x))

Question 51

Welche der folgenden Aussagen beschreibt die Cantor-Menge korrekt?

Accepted Answer

Eine perfekte, nirgends dichte Menge

Answer

Eine abzählbare Menge

Answer

Eine überabzählbare Menge

Answer

Eine endliche Menge

Question 52

Welche der folgenden Beweise ist ein indirekter Beweis?
(Ein indirekter Beweis nimmt die Negation der Behauptung an und leitet einen Widerspruch her.)

Accepted Answer

Annahme der Negation der Behauptung und Herleitung eines Widerspruchs

Answer

Aufzählung aller möglichen Fälle

Answer

Konstruktion eines Gegenbeispiels

Question 53

Welcher der folgenden Algorithmen hat eine worst-case time complexity von O(n^2)?
(Die worst-case time complexity gibt die längste Zeit an, die der Algorithmus für eine Eingabe der Größe n benötigt.)

Accepted Answer

Bubble Sort

Answer

Quick Sort

Answer

Binary Search

Question 54

Welche der folgenden Aussagen beschreibt eine Turingmaschine korrekt?

Accepted Answer

Ein theoretisches Modell einer Rechenmaschine, die auf einem unendlichen Band arbeitet

Answer

Ein Algorithmus zur Lösung komplexer Probleme

Answer

Ein physikalisches Gerät zur Durchführung von Berechnungen

Question 55

Welche der folgenden Aussagen beschreibt das Halting-Problem korrekt?

Accepted Answer

Es gibt keinen Algorithmus, der für jedes Programm und jede Eingabe bestimmen kann, ob das Programm auf der Eingabe halten wird

Answer

Es gibt einen Algorithmus, der für jedes Programm und jede Eingabe bestimmen kann, ob das Programm auf der Eingabe halten wird

Question 56

Welche der folgenden Aussagen ist eine notwendige Bedingung für die Korrektheit eines Algorithmus?

Accepted Answer

Der Algorithmus gibt immer das richtige Ergebnis für jede gültige Eingabe aus

Answer

Der Algorithmus hat eine polynomielle worst-case time complexity

Answer

Der Algorithmus ist einfach zu implementieren

Question 57

Welche der folgenden Mengen ist eine Teilmenge von {1, 2, 3, 4}?

Accepted Answer

{2, 4}

Answer

{1, 2, 4, 5}

Answer

{1, 3, 5}

Answer

{3, 4, 5}

Question 58

Welche der folgenden Mengen ist die Vereinigungsmenge von {1, 2, 3} und {3, 4, 5}?

Accepted Answer

{1, 2, 3, 4, 5}

Answer

{1, 3}

Answer

{3, 4}

Answer

{1, 2, 3, 4, 5, 6}

Question 59

Welche der folgenden Aussagen ist eine formale Aussage?

Accepted Answer

Alle Menschen sind sterblich.

Answer

Die Sonne scheint.

Answer

Peter ist groß.

Answer

Ist es kalt?

Question 60

Welche der folgenden Aussagen ist ein Beispiel für eine induktive Argumentation?

Accepted Answer

Ich habe drei Würfe mit einem Würfel gemacht und jedes Mal eine gerade Zahl erhalten. Daher muss der Würfel fair sein.

Answer

Alle Dreiecke haben drei Seiten.

Question 61

Welche der folgenden Aussagen ist ein Beispiel für eine deduktive Argumentation?

Accepted Answer

Wenn alle Hunde Säugetiere sind und alle Säugetiere Wirbeltiere sind, dann sind alle Hunde Wirbeltiere.

Answer

Ich habe drei Würfe mit einem Würfel gemacht und jedes Mal eine ungerade Zahl erhalten. Daher muss der Würfel unfair sein.

Question 62

Welche der folgenden Aussagen ist eine Tautologie? Eine Tautologie ist eine Aussage, die immer wahr ist, unabhängig von den Wahrheitswerten ihrer Teil aussagen.

Accepted Answer

Entweder regnet es oder es regnet nicht.

Answer

Wenn es regnet, dann ist die Straße nass.

Answer

Entweder regnet es oder die Straße ist nass.

Answer

Es regnet nur, wenn die Sonne scheint.

Question 63

Welche der folgenden Aussagen ist eine wahre Aussage über die Menge {1, 2, 3, 4}?

Accepted Answer

Die Mächtigkeit der Menge ist 4.

Answer

Die Menge ist leer.

Answer

Die Menge enthält die Zahl 5.

Answer

Die Menge ist unendlich.

Question 64

Welche der folgenden Aussagen ist eine wahre Aussage über das Halteproblem?

Accepted Answer

Das Halteproblem ist ein unlösbares Problem in der Theoretischen Informatik.

Answer

Das Halteproblem ist nur für rekursive Funktionen relevant.

Answer

Das Halteproblem kann mit Hilfe einer Turing-Maschine gelöst werden.