close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Anmeldung - Gebetsstätte Marienfried

EinbettenHerunterladen
Logik und Grundlagen
Martin Goldstern, Stefan Hetzl, WS 2013, WS 2014
1
Hinweis: Manche (sehr wenige) der folgenden Beispiele sind falsch, manche enthalten offene Fragen,
manche sind besonders schwierig. Die L¨osung eines falschen Beispiels besteht in einer Erkl¨arung,
was bzw. warum etwas falsch ist. (Ein falscher Allsatz kann zB durch ein Gegenbeispiel widerlegt
werden.)
Naive Mengenlehre
1. Welche der folgenden Aussagen gelten allgemein (d.h., f¨
ur beliebige x, x1 , y, . . .)? Begr¨
unden
Sie Ihre Antwort (Beweis oder Gegenbeispiel).
a. Wenn {x} = {y}, dann ist auch x = y.
b. Wenn {x, z} = {y, z}, dann ist auch x = y.
c. Wenn {x1 , x2 } = {y1 , y2 }, dann gilt zumindest eine der folgenden beiden Aussagen:
(a) x1 = y1 und x2 = y2 ;
(b) x1 = y2 und x2 = y1 .
d. Wenn {x1 , x2 , x3 } = {y1 , y2 , y3 }, dann ist zumindest eine der folgenden 6 Aussagen
wahr:
(123) x1 = y1 , x2 = y2 , x3 = y3 .
(132) x1 = y1 , x2 = y3 , x3 = y2 .
(213) x1 = y2 , x2 = y1 , x3 = y3 .
(231) x1 = y2 , x2 = y3 , x3 = y1 .
(312) x1 = y3 , x2 = y1 , x3 = y2 .
(321) x1 = y3 , x2 = y2 , x3 = y1 .
2. Von der Eigenschaft E wissen wir bereits, dass sie auf alle Singletons zutrifft. Nehmen wir
an, dass E immer dann auf eine Menge A ∪ {b} zutrifft, wenn E auf A zutrifft (und b beliebig
ist). K¨
onnen wir daraus schließen,
• . . . dass E f¨
ur alle endlichen nichtleeren Mengen gilt?
• . . . dass E f¨
ur alle nichtleeren Mengen gilt?
• . . . dass E f¨
ur alle h¨
ochstens abz¨ahlbaren nichtleeren Mengen gilt?
3. Zeigen oder widerlegen Sie: Wenn { {x}, {x, y} } = { {x }, {x , y } }, dann gilt x = x und
y=y.
4. Zeigen oder widerlegen Sie: Wenn { x, {x, y} } = { x , {x , y } }, dann gilt x = x und y = y .
5. Zeigen oder widerlegen Sie: Sei ∗ := {∅}. Wenn { {∅, x}, {∗, y} } = { {∅, x }, {∗, y } }, dann
gilt x = x und y = y .
Sei A eine Menge von Mengen. Eine Auswahlfunktion f¨
ur A ist eine Funktion f , die jedem Element
B ∈ A \ {∅} eines seiner Elemente zuweist, d.h. es muss also f¨
ur alle nichtleeren1 B ∈ A die
Beziehung f (B) ∈ B gelten. Geben Sie in den folgenden Aufgaben explizite Auswahlfunktionen
f¨
ur die jeweiligen Mengenfamilien an.
6. A6 sei die Familie aller Teilmengen von N.
7. A7 sei die Familie aller Teilmengen von Z.
8. A8 sei die Familie aller endlichen Teilmengen von R.
9. A9 sei die Familie aller Teilmengen von R.
¨
10. A10 sei die Familie aller Aquivalenzklassen
von Cauchyfolgen rationaler Zahlen.
∞
(Zwei Cauchyfolgen (xn )∞
,
(y
)
heißen
¨aquivalent, wenn die Folge (xn − yn )∞
n n=1
n=1
n=1 ihrer
Differenzen eine Nullfolge bildet.)
1 Oft
wird vorausgesetzt, dass die leere Menge ∅ kein Element von A ist.
Logik und Grundlagen
Martin Goldstern, Stefan Hetzl, WS 2013, WS 2014
2
11. A × B := {(x, y) : x ∈ A, y ∈ B}, wobei (x, y) := {{x}, {x, y}}. Zeigen Sie A × B ⊆
P(P(A ∪ B)) (wobei P(X) := {Y : Y ⊆ X}).
12. Wir schreiben B A f¨
ur die Menge aller Funktionen von A nach B. Welche der folgenden
Aussagen ist richtig?
B A ⊆ A × B,
13. Berechnen Sie
A,
B A ⊆ P(A × B),
A,
A,
B A ⊆ P(P(A ∪ B)),
B A ⊆ P(P((A × B)))
A f¨
ur jede der folgenden Mengen A:
A1 = {0, 1, 2, 3, 4}, A2 = {0, 2, 4, 6, . . .}, A3 = {1, 3, 5, . . .}, A4 = {3, 4, 5, 6}
In der ( offiziellen“) Sprache der Mengenlehre verwenden wir neben dem zweistelligen Relations”
symbol ε das Gleichheitszeichen, beliebig viele pr¨adikatenlogische Variable x, x1 , A, B, C, etc, die
logischen Konstanten
und ⊥, die Junktoren ∧, ∨, ¬, →, ↔ sowie die Quantoren ∀ und ∃, nicht
aber die Symbole ∅, {· · · }, ∪, ∩, etc.
¨
14. Ubersetzen
Sie die folgenden Formeln in die offizielle Sprache der Mengenlehre:
a. A = {x}
b. B = {x, y}
c. C = P ∩ Q
d. D =
E, wobei die rechte Seite als {x : ∃E ∈ E(x ∈ E)} definiert ist.
e. F =
{U, V }.
Aussagenlogik
15. Geben Sie f¨
ur jede der folgenden Formeln eine Baumdarstellung an, sowie Pr¨afix- und Postfixform. (Pr¨
afix=polnische Notation, Postfix=umgekehrte polnische Notation.)
p1 → ¬p2
(¬p1 ) → p2
¬(p1 → p2 )
¬(¬(p1 → p2 ))
p1
16. Geben Sie alle zweistelligen Operationen auf der Menge {wahr, falsch} an, und finden Sie
treffende Namen f¨
ur jede dieser Abbildungen. (Die Abbildung, die dem Paar (wahr, wahr) den
Wert wahr zuordnet, den drei anderen Paaren der Wert falsch, k¨onnte man zum Beispiel
Konjunktion“, oder und-Verkn¨
upfung“, oder beide“, oder Serienschaltung“ nennen.)
”
”
”
”
17. Wie viele dreistellige Operationen gibt es auf einer zweielementigen Menge? Wie viele nstellige?
18. Zeigen Sie:
a. ¬(p1 ∧ p2 ) ⇔ ¬p1 ∨ ¬p2 .
b. F¨
ur alle Formeln A und B gilt ¬(A ∧ B) ⇔ ¬A ∨ ¬B.
c. F¨
ur alle Formeln A und B gilt ¬(A ∨ B) ⇔ ¬A ∧ ¬B.
19. Zeigen Sie: (p ∧ q) ∨ (¬p ∧ ¬q) ⇔ (p → q) ∧ (q → p).
20. Seien A und B aussagenlogische Formeln. Dann gilt die Beziehung A ⇒ B“ genau dann,
”
wenn
⇒ A → B“ gilt, d.h., wenn die Formel A → B eine Tautologie ist.
”
21. Seien A und B aussagenlogische Formeln. Dann gilt A ⇒ B“ genau dann, wenn A∧(¬B) ⇒
”
”
⊥“ gilt.
Logik und Grundlagen
Martin Goldstern, Stefan Hetzl, WS 2013, WS 2014
3
Belegungen
Sei b eine Belegung, A eine Formel. Statt ˆb(A) = 1 sagen wir auch b erf¨
ullt die Formel A“.
”
22. Sei n ≥ 2. Wieviele Belegungen (der Variablen p1 , . . . , pn ) gibt es, die die Formel
(p1 → p2 ) ∧ (p2 → p3 ) ∧ · · · ∧ (pn−1 → pn )
erf¨
ullen?
23. Sei n ≥ 2. Geben Sie eine Formel (in den Variablen p1 , . . . , pn ) an, die von genau n Belegungen erf¨
ullt wird.
24. Sei n groß, k ≤ 2n . Geben Sie eine Formel (in den Variablen p1 , . . . , pn ) an, die von genau
k Belegungen erf¨
ullt wird. Versuchen Sie, eine m¨oglichst kleine Formel zu finden (mit etwa
O(n) Symbolen).
CNF, DNF
25. Welche der folgenden Formeln sind in CNF, welche in DNF?
¬p1 , ¬p1 ∨ p2 , ¬(p1 ∨ p3 ), ¬p1 ∧ p4 , ¬p1 → p5 , (¬p1 ∨ p6 ) ∧ p7 , (((p1 ∧ p2 ) ∨ p3 ) ∧ p4 )
Anmerkung: ¬“ bindet st¨
arker als die anderen Junktoren; ¬p1 ∨ p2 ist daher als ((¬p1 ) ∨ p2 ) zu
”
lesen.
26. Geben Sie zu 3 Formeln im vorigen Beispiel, die nicht in CNF sind, eine ¨aquivalente Formel
in CNF an.
27. Detto f¨
ur DNF.
Interpolation
28. Sei A eine Formel, die nur die Variablen p1 , . . . , pn verwendet, und sei B eine Formel, die
nur die Variablen pk , . . . , pk+ verwendet, 1 < k ≤ n < k + .
Nehmen wir weiters an, dass A ⇒ B gilt.
Zeigen Sie, dass es dann eine Formel C geben muss, die nur die Variablen pk , . . . , pn verwendet, sodass sowohl A ⇒ C als auch C ⇒ B gilt.
(Wir nennen so eine Formel C einen Interpolanten“.)
”
29. Sei A eine Formel, die nur die Variablen p1 , . . . , pn verwendet, und sei B eine Formel, die
nur die Variablen pk , . . . , pk+ verwendet, mit n < k. Nehmen wir weiters an, dass A ⇒ B
gilt. Dann gilt zumindest eine der folgenden Aussagen:
• A ⇒ ⊥. (Mit anderen Worten: A ist Kontradiktion.)
•
⇒ B. (Mit anderen Worten: B ist Tautologie.)
(Insbesondere gibt es also eine Formel C, die keine Variablen verwendet, und die A ⇒ C
und C ⇒ B erf¨
ullt.)
Logik und Grundlagen
Martin Goldstern, Stefan Hetzl, WS 2013, WS 2014
4
Erfu
¨ llbarkeit
Eine Menge Σ von aussagenlogischen Formeln heißt erf¨
ullbar“, wenn es eine Belegung b der in
”
Σ vorkommenden aussagenlogischen Variablen gibt, die f¨
ur alle A ∈ Σ die Bedingung ˆb(A) = 1
erf¨
ullt.
Wir nennen eine Menge Σ *erf¨
ullbar, wenn jede endliche Teilmenge von Σ erf¨
ullbar ist.
30. Sei Σ eine Menge von aussagenlogischen Formeln, A eine aussagenlogische Formel. Zeigen
Sie:
(a) Σ ist genau dann erf¨
ullbar, wenn zumindest eine der Mengen Σ∪{A}, Σ∪{¬A} erf¨
ullbar
ist.
(b) Σ ist genau dann *erf¨
ullbar, wenn zumindest eine der Mengen Σ ∪ {A}, Σ ∪ {¬A}
*erf¨
ullbar ist.
31. Geben Sie eine *-erf¨
ullbare Menge an, die nicht erf¨
ullbar ist.
32. Zeigen Sie:
(a) Wenn Σ *erf¨
ullbar ist, und f¨
ur jede aussagenlogische Variable p entweder p ∈ Σ oder
(¬p) ∈ Σ gilt, dann ist Σ auch erf¨
ullbar (und zwar durch genau eine Belegung).
(b) Wenn Σ *erf¨
ullbar ist, dann gibt es eine *erf¨
ullbare Menge Σ ⊇ Σ die die Bedingung
in (a) erf¨
ullt.
¨
Uberabz
ahlbare Mengen
¨
Wir betrachten eine aussagenlogische Sprache mit einer (m¨oglicherweise u
¨berabz¨ahlbaren) festen
Variablenmenge V . (Formeln und Klauseln sind weiterhin endlich.)
Eine Menge Σ von Formeln heißt *erf¨
ullbar, wenn jede endliche Teilmenge erf¨
ullbar ist. Σ heißt
maximal *erf¨
ullbar“, wenn M zwar *erf¨
ullbar ist, aber es keine echte Obermenge von Σ gibt, die
”
auch noch *erf¨
ullbar ist.
33. F¨
ur jede *erf¨
ullbare Menge Σ gibt es eine maximal *erf¨
ullbare Obermenge Σ ⊇ Σ. (Hinweis:
Wohlordnung, oder Lemma von Zorn, oder Lemma von Tukey.)
34. Sei Σ maximal *erf¨
ullbar. Dann ist Σ erf¨
ullbar, und es gibt genau eine Belegung b, die Σ
erf¨
ullt.
K¨
onig
Ein Baum (T, <) ist eine partiell geordnete Menge mit kleinstem Element, in der f¨
ur alle t ∈ T
die Menge T<t := {x : x < t} endlich und linear geordnet ist. Ein Ast ist eine maximale linear
geordnete Teilmenge. Lev(n, T ) = {t ∈ T : T<t hat n Elemente}.
35. Sei (T, <) ein unendlicher Baum, sodass Lev(n, T ) f¨
ur alle n endlich ist. Zeigen Sie, dass T
einen unendlichen Ast hat.
Document
Kategorie
Seele and Geist
Seitenansichten
11
Dateigröße
204 KB
Tags
1/--Seiten
melden