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