dr Przemysław Szczepaniak
Podstawy Logiki i Teorii Mnogości
1
Instytut Matematyki i Informatyki
2008/2009
ZDANIA
1 Udowodnij prawa rachunku zdań poznane na wykładzie.
2 Sprawdź, które z poniższych zdań są tautologiami:
(a) (p ∨ q ∨ r) −→ (¬p −→ ((q ∨ r) ∧ ¬r)).
(b) ((p −→ q) ∧ (r −→ s)) −→ ((p ∧ s) −→ (q ∨ r)).
(c) ((p ∨ q) −→ r) −→ ((p −→ r) ∨ (q −→ r)).
(d) (p −→ q) ←→ ((p ∧ q) ←→ p).
(e) ((p ∨ q) ←→ (r ∨ s)) −→ ((p ←→ r) ∨ (q ←→ s)).
(f ) (p ←→ q) ←→ (p −→ q) ∧ (q −→ p).
3 Zaneguj zdania z przykładów (a), (b), (c) poprzedniego zadania. Ko-
rzystając z praw de Morgana, przekształć je do postaci, w której negacja
występuje jedynie przed zmiennymi zdaniowymi.
4 Sprawdź metodą skróconą, które z poniższych zdań są tautologiami:
(a) p −→ (q −→ p).
(b) (p −→ (q −→ r)) −→ ((p −→ q) −→ (p −→ r)).
(c) (¬p −→ ¬q) −→ ((¬p −→ q) −→ p).
(d) ((p −→ q) ∧ (q −→ r)) −→ (p −→ r).
5 Oto fragment raportu policji, sporządzonego przez młodego aspiranta:
Świadek nie był zastraszony lub też, jeśli Henry popełnił samo-
bójstwo, to testament odnaleziono. Jeśli świadek był zastraszony,
to Henry nie popełnił samobójstwa. Jeśli testament odnaleziono,
to Henry popełnił samobójstwo. Jeśli Henry nie popełnił samobój-
stwa, to testament odnaleziono.
Co komendant policji może wywnioskować z powyższego raportu, poza oczy-
wistym faktem, że należy zwolnić aspiranta? Spróbuj odpowiedzieć na py-
tania: Czy świadek był zastraszony? Czy Henry popełnił samobójstwo? Czy
testament odnaleziono?
.
1
Uwaga.
Ćwiczenia nie są oznaczone, przy zadaniach jest symbol
⋄
, przy trudniejszych
zadaniach jest symbol
⋆
.
1
6 Sprawdź, czy poniższe rozumowania są poprawne:
(a) Jeżeli Jan ożeni się z Marią, to Piotr go znienawidzi. Jeżeli Piotr ożeni
się z Marią, to Jan go znienawidzi. Zatem Piotr znienawidzi Jana lub Jan
znienawidzi Piotra.
(b) Jeżeli występuje spięcie w przewodzie elektrycznym, to światło gaśnie.
Światło nie gaśnie. Zatem nie występuje spięcie w przewodzie elektrycznym.
(c) Jeśli jest zimno, to trzeba ubrać płaszcz. Jeśli pada deszcz, to trzeba
wziąć parasol. Więc jeśli jest zimno i pada deszcz, to trzeba ubrać płaszcz i
wziąć parasol.
(d) Jeśli pacjent ma zapalenie oskrzeli, to zastosowanie antybiotyków przy-
niesie poprawę. Jeśli pacjent ma zapalenie płuc, to zastosowanie antybiotyków
przyniesie poprawę. Pacjent ma zapalenie oskrzeli lub zapalenie płuc. Zatem
zastosowanie antybiotyków przyniesie poprawę.
7 Podczas pewnej kampanii wyborczej Olek, Józek i Kazik wygłosili nastę-
pujące oświadczenia:
Olek: Józek zawsze kłamie,
Józek: Kazik zawsze kłamie,
Kazik: Olek zawsze kłamie.
Pokaż, że co najmniej dwóch spośród nich nie miało racji.
8
⋄
Kreskę Shefera określamy następująco: p|q = (¬p ∨ ¬q). Wyraź negację,
koniunkcję, alternatywę, implikację i równoważność za pomocą tego spójnika.
ZBIORY
9 Udowodnij prawa rachunku zbiorów poznane na wykładzie.
10 Pokaż, że dla dowolnych zbiorów A, B, C, D:
(a) A ⊆ B ∧ B ⊆ C −→ A ⊆ C,
(b) A ⊆ C ∧ B ⊆ C −→ A ∪ B ⊆ C,
(c) A ⊆ B ∧ A ⊆ C −→ A ⊆ B ∩ C,
(d) A ⊆ B ∧ C ⊆ D −→ A ∪ C ⊆ B ∪ D,
(e) A ⊆ B ∧ C ⊆ D −→ A ∩ C ⊆ B ∩ D.
11 Pokaż, że dla dowolnych zbiorów A, B poniższe warunki są równoważne:
1. A ⊆ B,
2. A ∩ B = A,
3. A ∪ B = B.
2
12 Pokaż, że A ∪ B jest najmniejszym w sensie inkluzji zbiorem zawierają-
cym jednocześnie zbiory A i B. Sformułuj i udowodnij analogiczny fakt dla
przekroju dwóch zbiorów.
13 Pokaż, że dla dowolnych zbiorów A, B, C:
(a) (A \ B) \ C = A \ (B ∪ C),
(b) A \ (B \ C) = (A \ B) ∪ (A ∩ C).
14
⋄
Pokaż następujące prawa różnicy symetrycznej: A△∅ = A, A△A = ∅,
A△B
= B△A, A△(B△C) = (A△B)△C.
15 Rozwiąż równanie [0, 1]△X = [−1,
1
2
).
16 Czy iloczyn kartezjański jest operacją łączną?
17 Pokaż, że dla dowolnych zbiorów A, B, C:
(a) (A ∪ B) × C = (A × C) ∪ (B × C),
(b) (A ∩ B) × C = (A × C) ∩ (B × C).
18 Wyznacz zbiory P (∅), P (P (∅)), P ({1, 2, 3}).
19 Pokaż, że A ⊆ B wtedy i tylko wtedy, gdy P (A) ⊆ P (B).
20 Czy dla dowolnych zbiorów A, B:
(a) P (A) ∩ P (B) = P (A ∩ B),
(b) P (A) ∪ P (B) = P (A ∪ B)?
KWANTYFIKATORY
21 Udowodnij prawa rachunku kwantyfikatorów poznane na wykładzie.
22 Używając jedynie symboli kwantyfikatorów, spójników logicznych oraz
=, <, ¬, +, ·, |, N, Z, R zapisz zdania:
(a) istnieje nieparzysta liczba naturalna,
(b) nie ma największej liczby naturalnej,
(c) niektóre liczby naturalne są pierwsze,
(d) każda liczba naturalna daje przy dzieleniu przez 2 resztę 0 lub 1,
(e) x jest najmniejszą liczbą naturalną,
(f ) wśród liczb naturalnych istnieje liczba najmniejsza,
(g) suma kwadratów dwóch liczb rzeczywistych jest zawsze nieujemna,
3
(h) równanie x
2
+ x + 4 = 0 nie ma rozwiązań w zbiorze liczb rzeczywistych,
(i) równanie x
2
− x −
2 = 0 ma dwa rozwiązania całkowite,
(j) równanie 2x + a = 0 ma rozwiązanie całkowite dla dowolnego a ∈ Z,
(k) dla dwóch (różnych) liczb rzeczywistych dodatnich ich średnia arytme-
tyczna jest mniejsza niż średnia geometryczna,
(l) liczba z jest największym wspólnym dzielnikiem liczb x i y,
(m) każde dwie liczby naturalne mają najmniejszą wspólną wielokrotność,
(n) istnieje dokładnie jedna nieparzysta liczba naturalna.
23 Czy zdania z poprzedniego zadania są prawdziwe? Odpowiedź uzasadnij.
24 Zaprzecz zdaniom z zadania 22.
25 Przedstaw graficznie zbiór {(x, y) ∈ R
2
: ϕ(x, y)} jeśli ϕ(x, y) to formuła
x < y
, x ¬ y, x · y < 1, |x · y| ¬ 1, |x + y| < 1, x · y ¬ 1 −→ x · y = 1.
DZIAŁANIA UOGÓLNIONE
26 Znajdź
S
∞
n
=1
A
n
oraz
T
∞
n
=1
A
n
jeśli
(a) A
n
= {x ∈ R : x ¬ n},
(b) A
n
= {x ∈ R : −n < x ¬
1
n
}
,
(c) A
n
= {x ∈ R :
1
n
¬ x ¬ n}
,
(d) A
n
= {x ∈ R : 1 −
1
n
< x <
3 −
1
n
}
,
(e) A
n
= {x ∈ R : n < x ¬ n + 1},
(f ) A
n
= {x ∈ R : n
2
< x < n
+ 10},
(g) A
n
= {x ∈ R : (−1)
n
< x <
2 +
(−1)
n
n
}
.
27 Znajdź
S
{A
t
: t ∈ R} oraz
T
{A
t
: t ∈ R} jeśli
(a) A
t
= {(x, y) ∈ R
2
: y = t · x},
(b) A
t
= {(x, y) ∈ R
2
: x
2
+ y
2
¬ t
2
}
.
28 Wyznacz sumę oraz przekrój pustej rodziny podzbiorów zbioru R.
29 Udowodnij następujące własności działań uogólnionych:
(a) (
S
t∈T
A
t
)
c
=
T
t∈T
A
c
t
,
(b) (
T
t∈T
A
t
)
c
=
S
t∈T
A
c
t
,
(c)
T
t∈T
(A
t
∩ B
t
) = (
T
t∈T
A
t
) ∩ (
T
t∈T
B
t
),
(c)
S
t∈T
(A
t
∪ B
t
) = (
S
t∈T
A
t
) ∪ (
S
t∈T
B
t
),
(d)
S
t∈T
(A
t
∩ B
t
) ⊆ (
S
t∈T
A
t
) ∩ (
S
t∈T
B
t
),
(e)
T
t∈T
(A
t
∪ B
t
) ⊇ (
T
t∈T
A
t
) ∪ (
T
t∈T
B
t
).
W podpunktach (d) i (e) pokaż, że inkluzji nie można zastąpić równością.
4
RELACJE
30 Zbadaj, czy poniższe relacje są zwrotne, przeciwzwrotne, symetryczne,
słabo antysymetryczne, antysymetryczne, przechodnie, spójne:
(a) xRy ←→ x jest tej samej płci co y,
(b) xRy ←→ x jest bratem y,
(c) xRy ←→ x < y, na R,
(d) xRy ←→ x ¬ y, na R,
(e) xRy ←→ x|y, na N,
(f ) xRy ←→ x|y, na Z,
(g) xRy ←→ x ⊆ y, na P (Ω),
(h) xRy ←→ x ∩ y = ∅, na P (Ω),
(i) xRy ←→ 2|x + y, na N,
(j) xRy ←→ |x| < |y|, na R,
(k) xRy ←→ x + y 2, na R.
31 Czy każdą relację R na X można rozszerzyć do relacji (a) zwrotnej na
X
, (b) przeciwzwrotnej na X, (c) symetrycznej na X, (d) słabo antysy-
metrycznej na X, (e) antysymetrycznej na X, (f) przechodniej na X, (g)
spójnej na X?
32 Podaj przykład relacji która
(a) jest zwrotna, symetryczna i nie jest przechodnia,
(b) jest zwrotna, słabo antysymetryczna i nie jest przechodnia,
(c) jest symetryczna, przechodnia i nie jest zwrotna,
(d) jest słabo antysymetryczna, przechodnia i nie jest zwrotna.
33
⋄
Ile na zbiorze n-elementowym jest relacji (a) zwrotnych, (b) syme-
trycznych, (c) zwrotnych i symetrycznych, (d) antysymetrycznych, (e) słabo
antysymetrycznych?
FUNKCJE
34 Niech f : N
2
−→ N
będzie funkcją określoną wzorem f(n, k) = nk.
(a) Czy f jest różnowartościowa?
(b) Czy f jest „na”?
(c) Znajdź f [{2, 4} × {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}].
(d) Znajdź f [{2} × {2
n
: n ∈ N}].
(e) Znajdź f
−
1
[{4, 5}].
5
35 Niech f : R
2
−→ R
2
będzie funkcją o wzorze f(x, y) = (x + y, x − y).
(a) Czy f jest różnowartościowa?
(b) Czy f jest „na”?
(c) Znajdź f [R × {0}].
(d) Znajdź f
−
1
[{(1, 1)}].
(e) Znajdź f [L] oraz f
−
1
[L], gdzie L jest prostą o równaniu y = x + 1.
36 Niech f (x) = |x + 1|, g(x) = 3x − 6, h(x) = −x
2
. Napisz wzory złożeń
(a) h◦g ◦f , (b) f ◦g ◦h, (c) g ◦f ◦f ◦f , (d) h◦g ◦f ◦g ◦g, (e) f ◦g ◦f ◦h◦h.
37 Niech f : X −→ Y oraz A, A
1
, A
2
⊆ X
i B, B
1
, B
2
⊆ Y
. Pokaż, że
(a) f [A
1
∪ A
2
] = f[A
1
] ∪ f[A
2
],
(b) f [A
1
∩ A
2
] ⊆ f[A
1
] ∩ f[A
2
],
(c) f [A
1
\ A
2
] ⊇ f[A
1
] \ f[A
2
],
(d) f
−
1
[B
1
∪ B
2
] = f
−
1
[B
1
] ∪ f
−
1
[B
2
],
(e) f
−
1
[B
1
∩ B
2
] = f
−
1
[B
1
] ∩ f
−
1
[B
2
],
(f ) f
−
1
[B
1
\ B
2
] = f
−
1
[B
1
] \ f
−
1
[B
2
],
(g)
⋄
A ⊆ f
−
1
[f[A]],
(h)
⋄
B ⊇ f
[f
−
1
[B]].
38 Znajdź przykłady pokazujące, że zawierania w podpunktach poprzed-
niego zadania nie można zastąpić równością.
39
⋄
Pokaż, że jeśli f : X −→ Y , g : Y −→ Z są funkcjami takimi, że g ◦ f
jest różnowartościowa, a f jest „na”, to g jest funkcją różnowartościową. Czy
założenie, że f jest „na” jest istotne?
40
⋄
Pokaż, że f jest funkcją różnowartościową wtedy i tylko wtedy, gdy
f
[A ∩ B] = f[A] ∩ f[B] dla dowolnych zbiorów A i B.
RÓWNOWAŻNOŚCI
41 Pokaż, że ≡ jest relacją równoważności na zbiorze Z, jeśli
(a) n ≡ k ←→ 3|n + 2k,
(b) n ≡ k ←→ 5|n
2
− k
2
.
42 Pokaż, że ≃ jest relacją równoważności na X oraz wyznacz przestrzeń
ilorazową X/
≃
, jeśli
(a) (n, k) ≃ (n
′
, k
′
) ←→ max{n, k} = max{n
′
, k
′
}
, X = {0, 1, 2, 3, 4}
2
,
(b) x ≃ y ←→ (∃α > 0)(α · x = y), X = R,
(c) u ≃ v ←→ (∃α 6= 0)(α · u = v), X = R
2
.
6
43 Ile jest relacji równoważności na zbiorze {1, 2, 3}?
44 Podaj przykład relacji równoważności na N, która ma jedną 1-elementową,
dwie 2008-elementowe i dwie nieskończone klasy abstrakcji.
PORZĄDKI
45 Podaj za pomocą diagramów Hassego przykłady częściowych porządków
w których
(a) są dwa 3-elementowe łańcuchy i jeden 3-elementowy antyłańcuch,
(b) jest element najmniejszy, są dokładnie dwa elementy maksymalne oraz
4-elementowy łańcuch i 3-elementowy antyłańcuch,
(c) jest nieskończony łańcuch i nieskończony antyłańcuch,
(d) jest dokładnie jeden element minimalny i nie ma elementu najmniejszego.
46 Wskaż w porządku (P (N) \ {∅}, ⊆) elementy wyróżnione.
47 Pokaż, że (N \ {0}, |), (N \ {0, 1}, |) są częściowymi porządkami. Znajdź
w każdym z nich elementy wyróżnione, o ile takie elementy istnieją.
48 Pokaż, że jeśli w częściowym porządku istnieje element największy, to
jest on jedynym elementem największym. Pokaż, że element największy jest
jednocześnie maksymalny.
49 Pokaż, że jeśli X jest zbiorem skończonym, to w częściowym porządku
(X, ) istnieje co najmniej jeden element maksymalny.
50 Pokaż, że jeśli X jest zbiorem skończonym i w częściowym porządku
(X, ) istnieje dokładnie jeden element maksymalny, to jest on elementem
największym. Czy założenie skończoności zbioru X jest istotne?
51
⋄
Pokaż, że jeśli R i S są relacjami częściowo porządkującymi, to R ∩ S
też jest relacją częściowo porządkującą. Czy wtedy R ∪ S też jest relacją
częściowo porządkującą?
52 Pokaż, że jeśli liniowo porządkuje skończony zbiór X, to dobrze
porządkuje X. Podaj przykład pokazujący, że założenie skończoności zbioru
X
jest istotne.
7
TEORIA MOCY
53 Pokaż, wskazując odpowiednią bijekcję, że (a) (0, 1) ∼ (1, 4), (b) (0, ∞) ∼
R
, (c) (−1, 1) ∼ R, (d) Z ∼ N, (e)
⋆
[0, ∞) ∼ (0, ∞).
54
⋄
Pokaż, że
(a) A ∪ B ∼ C ∪ D, jeśli A ∼ C, B ∼ D, A ∩ B = ∅ i C ∩ D = ∅,
(b) A × B ∼ C × D, jeśli A ∼ C i B ∼ D,
(c) P (A) ∼ P (B), jeśli A ∼ B,
(d) P (A) ∼ {0, 1}
A
.
55 Jakiej mocy jest zbiór punktów płaszczyzny o obu współrzędnych wy-
miernych?
56 Pokaż, że R \ Q jest zbiorem nieprzeliczalnym.
57
⋆
Pokaż, że |R \ Q| = c.
58 Pokaż, że dowolna rodzina parami rozłącznych niezdegenerowanych (tzn.
niepustych i niejednoelementowych) przedziałów na prostej jest przeliczalna.
59 Czy zbiór, którego każdy właściwy podzbiór jest przeliczalny, sam jest
przeliczalny?
60 Czy istnieje zbiór X taki, że |P (X)| = ℵ
0
?
61
⋄
Czy rozważana w dowodzie faktu (0, 1) × (0, 1) ∼ (0, 1) funkcja jest na
zbiór (0, 1)?
62 Pokaż, że
(a) |{X ⊆ N : |X| < ℵ
0
}|
= ℵ
0
,
(b) |{X ⊆ Z : |X ∩ N| < ℵ
0
}|
= c,
(c) |{X ⊆ R : |X| < ℵ
0
}|
= c.
63
⋄
Pokaż, że (a) ℵ
ℵ
0
0
= c, (b) c
ℵ
0
= c, (c) c + c = c, (d) ℵ
0
+ c = c, (e)
ℵ
0
· c
= c, (f) cc > c.
64
⋄
Jaka jest moc zbioru wszystkich ciągów liczb rzeczywistych zbieżnych
do zera? A moc zbioru wszystkich ciągów liczb całkowitych zbieżnych do
zera?
8