´

Cwiczenie 3

Rachunek zbiorów

3.1

Zadania teoretyczne

3.1.1

Zbiór i zale˙zno´sci mi ˛edzy zbiorami

1. Poda´c elementy zbiorów:

(a) {a, b, a}

(b) {{a}}

(c) {{a, b} , {a}}

(d) ∅

(e) {∅}

(f) {x ∈ N : x
2}

(g) {x ∈ N : x = 2 ∨ x = 3}

(h)

x

∈ N : x

2

= 4



(i) {x ∈ N : |3 − x| < 3}

(j)

x

∈ R : x

2

+ 4x + 4
0



2. Zbada´c jakie relacje (inkluzji, równo´sci) zachodz ˛

a mi ˛edzy zbiorami:

(a) A = {a, b, c, d}, B = {a, c, d}

Odpowied´z: A
⊂ B, B ⊂ A, A
= B.

(b) A = {a, b}, B = {a, c, d}

(c) A = {{a, b} , {c, d} , c, d}, B = {{a, b} , c}

(d) A = ∅, B = {a, b, c}

(e) A = {{a} , a, ∅}, B = {a}

(f) A = {{a, b} , {a} , b, ∅}, B = {{a} , b, {∅}}

(g) A = {x ∈ N : x > 2}, B = {y ∈ N : y > 2}

3.1.2

Prawa rachunku zbiorów

1. Udowodni´c i sprawdzi´c na diagramach Venna:

(a) A ∪ (A ∩ B) = A

Rozwi ˛

azanie:

• korzystamy z definicji sumy i iloczynu zbiorów:

[x ∈ A ∨ (x ∈ A ∧ x ∈ B)] ⇔ x ∈ A

• oznaczaj ˛

ac p – x ∈ A, q – x ∈ B zapisujemy formuł ˛e:

[p ∨ (p ∧ q)] ⇔ p

• poniewa˙z otrzymana formuła jest tautologi ˛a, to równo´s´c A ∪ (A ∩ B) = A jest prawdziwa.

12

(b) A − B = A ∩ B

(c) (A − B) ∩ B = ∅

(d) (A − B) ∪ B = A ∪ B

(e) A = (A ∩ B) ∪ (A ∩ B)

2. Udowodni´c i sprawdzi´c na diagramach Venna prawa de Morgana dla zbiorów.

3. Udowodni´c wzory:

(a) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

(b) (A ∪ B) − C = (A − C) ∪ (B − C)

(c) A − (B ∪ C) = (A − B) − C

(d) [(A − B) = (B − A)] ⇒ (A = B)

(e) [(A ⊂ B) ∧ (C ⊂ D)] ⇒ (A ∩ C) ⊂ (B ∩ D)

(f) (A ∪ B) − (A ∩ B) = (A − B) ∪ (B − A)

4. Która z podanych inkluzji jest prawdziwa, a która fałszywa:

(a) (A ∩ B) ⊂ (A ∪ B)

(b) (A ∪ A) ⊂ A

(c) (A ∩ A) ⊂ A

(d) (A − B) ⊂ (A ∪ B)

(e) (A − B) ⊂ (A ∩ B)

(f) (A ∩ B) ⊂ A

Odpowied´z: Inkluzje a, b, c, d, f s ˛

a prawdziwe; inkluzja e jest fałszywa.

3.1.3

Działania na zbiorach

1. Wyznaczy´c 2

A

dla zbiorów:

(a) A = {a, b, c}

(b) A = ∅

(c) A = {∅}

2. Dane s ˛

a zbiory A = {0, 1, 2, 8}, B = {0, 1, 2, 3, 4}. Znale´z´c:

(a) A ∪ B

(b) A ∩ B

(c) A − B

(d) B − A

(e) A ⊕ B

3. Niech U = {1, 2, 3, 4, 5} b ˛edzie przestrzeni ˛

a. Znale´z´c dopełnienie zbiorów:

(a) A = {2, 3, 5}

(b) B = {1, 2}

4. Dane s ˛

a zbiory A =

x

∈ R : x

2

+ 6x + 8 < 0



, B =

x

∈ R : x

2

+ 3x < 0



. Znale´z´c:

(a) A ∩ B

(b) A ∪ B

(c) A − B

(d) A

5. Dla zbiorów A

t

= {x ∈ R : −t
x
t + 1} wyznaczy´c



t∈T

A

t

oraz



t∈T

A

t

, gdzie:

(a) t ∈ N

(b) t ∈ {1, 2, 3}

13

3.2

Zadania praktyczne

3.2.1

Wst ˛ep

Twórcami j ˛ezyka Prolog s ˛

a Alain Colmerauer i Robert Kowalski. Kowalski podał podstawy teoretyczne, nato-

miast Colmerauer opracował w 1972 roku j ˛ezyk programowania. Nazwa jest skrótem od Programming in Logic,
co oznacza programowanie w logice. Prolog zyskał popularno´s´c w latach osiemdziesi ˛

atych, kiedy Japonia wybrała

go na j ˛ezyk komputerów pi ˛

atej generacji, a firma Borland wprowadziła na rynek kompilator Turbo-Prolog.

Pierwotne zastosowania Prologu dotyczyły dowodzenia twierdze´n logicznych i przetwarzania j ˛ezyka natural-

nego. Poniewa˙z Prolog operuje głównie na symbolach, nadaje si ˛e tak˙ze do rozwi ˛azywania zagadnie´n sztucznej
inteligencji takich, jak wnioskowanie logiczne, podejmowanie decyzji czy rozgrywanie gier.

Praca z Prologiem polega na zasadzie zapyta´n. Zapytanie mo˙ze by´c proste, np. Czy 2 jest wi ˛eksze od 1?

?- 2 > 1.
Yes

lub zło˙zone np. Czy 2 jest wi ˛eksze od 1 i czy 3 jest mniejsze od 2?

?- 2 > 1, 5 < 3.
No

Uwaga 3.1 Koniunkcj ˛e zapyta´n realizuje przecinek (,), za´s alternatyw ˛e – ´srednik (;). Ka˙zde zapytanie musi
ko´nczy´c si ˛e kropk ˛

a.

Prolog interpretuje zapytanie i drukuje odpowied´z. Odpowied´z mo˙ze mie´c posta´c:

1. Yes – odpowied´z twierdz ˛

aca,

2. No – odpowied´z negatywna,

3. zmienne i ich warto´sci – s ˛

a drukowane, je˙zeli stanowi ˛a odpowied´z na zapytanie. Po wydrukowaniu jednej

odpowiedzi, program czeka na decyzj ˛e u˙zytkownika. Aby wy´swietli´c kolejne rozwi ˛azanie, nale˙zy nacisn ˛a´c

´srednik (;). Aby zrezygnowa´c z szukania dalszych odpowiedzi, nale˙zy nacisn ˛

a´c Enter.

Uwaga 3.2 W Prologu zmienne zaczynaj ˛

a si ˛e wielk ˛

a liter ˛

a (np. X, Kto, Delta).

3.2.2

Działania na zbiorach w j ˛ezyku Prolog

W j ˛ezyku Prolog zbiory s ˛

a reprezentowane w postaci listy, na przykład:

Zbiór

Lista

∅

[]

{a, b, c}

[a,b,c]

{{a} , {b, c}}

[[a],[b,c]]

Działania na zbiorach realizuj ˛

a predykaty podane w tabeli:

Nazwa

Operacja

Predykat

przynale˙zno´s´c

x

∈ A

member(x, A)

inkluzja (podzbiór)

A

⊂ B

subset(A, B)

suma

C

= A ∪ B

union(A, B, C)

iloczyn

C

= A ∩ B

intersection(A, B, C)

ró˙znica

C

= A − B

subtract(A, B, C)

Pozostałe działania mo˙zna zdefiniowa´c z wykorzystaniem wymienionych powy˙zej (por. wykład).

14

3.2.3

Przebieg ´cwiczenia

1. Uruchomi´c interpreter j ˛ezyka SWI-Prolog.

2. Zapyta´c: Czy 2 > 1 i 3 < 2?

?- 2 > 1, 3 < 2.
No

3. Zapyta´c: Czy 2 > 1 lub 3 < 2?

4. Zbada´c przynale˙zno´sci:

(a) x ∈ {a, b}

?- member(x, [a,b]).
No

(b) x ∈ {a, x}

(c) ∅ ∈ {∅, a, b}

(d) {a, b} ∈ {a, b, c}

(e) {a, b} ∈ {{a, b} , b, c}

5. Poda´c wszystkie elementy zbiorów:

(a) {a, b}

?- member(X, [a,b]).
X = a;
X = b;
No

(b) ∅

(c) {∅}

(d) {{a, b} , {b} , b}

(e) {{a} , b, {∅}}

6. Dla zbiorów A = {a, {b, c}}, B = {a, {b, c} , d} zbada´c inkluzje:

(a) A ⊂ B

?- A = [a,[b,c]], B = [a,[b,c],d], subset(A,B).
A = [a, [b, c]]
B = [a, [b, c], d]
Yes

(b) B ⊂ A

7. Zbada´c równo´s´c zbiorów A = {a, b}, B = {b, a}.

Wskazówka: A = B ⇔ (A ⊂ B ∧ B ⊂ A)

8. Dla zbiorów A = {a, b, c, d}, B = {a, c, e} wyznaczy´c:

(a) A ∪ B

?- A = [a,b,c,d], B = [a,c,e], union(A,B,Suma).
Suma = [b, d, a, c, e]

(b) A ∩ B

(c) A − B

(d) B − A

(e) (A ∪ B) − B

(f) A ⊕ B

9. Dla zbiorów U = {a, b, c, d} , A = {a, c} , B = ∅ wyznaczy´c A, A, B, U, B − A.

10. Dla zbiorów U = {1, 2, 3, 4, 5} , A = {1, 2} , B = {2, 3, 4} zbada´c prawa wył ˛

aczonego ´srodka, sprzeczno´sci

i de Morgana.

15

3.2.4

Zadania dla dociekliwych (elementarz programowania)

1. Zdefiniowa´c predykat comp(A, U, Wynik) (complement) wyznaczaj ˛

acy dopełnienie A do przestrzeni U .

Rozwi ˛

azanie:

• uruchamiamy edytor Emacs:

?- emacs.

• wpisujemy kod:

comp(A, U, Wynik) :-

subtract(U, A, Wynik).

• zaznaczamy wpisany kod

• wybieramy z menu: Compile | Consult selection

• wprowadzamy zapytanie:

?- U = [1, 2, 3], A = [1], comp(A, U, DopA).
U = [1, 2, 3],
A = [1],
DopA = [2, 3].

Uwaga:

• mo˙zna tak˙ze zapisa´c plik na dysku: File | Save as ... pod nazw ˛a comp.pl

• ... i załadowa´c poleceniem

?- [comp].

2.

Zdefiniowa´c predykat symmdiff (symmetric difference) wyznaczaj ˛

acy ró˙znic˛e symetryczn ˛a dwóch zbiorów.

3. Zdefiniowa´c predykat equal (equality) sprawdzaj ˛

acy równo´s´c dwóch zbiorów.

16