Logika dla informatyków

Egzamin połówkowy z 30 listopada 2002

Rozwiązania wybranych zadań

Zadanie 1. Niech I oznacza relację identyczności na zbiorze X. Udowodnij, że relacja R ⊆ X × X jest relacją równoważności wtedy i tylko wtedy, gdy spełniony jest warunek

I ⊆ R ∧ R^{−1} D R ∧ RR ⊆ R.

Rozwiązanie. Jest to bardzo proste zadanie, tak proste, że chciałoby się napisać tylko, że jest oczywiste. Warunki I ⊆ R i RR ⊆ R są niemal identyczne odpowiednio z warunkami z definicji zwrotności i symetryczności relacji R. Z tego powodu przedstawiony dowód może będzie zbyt szczegółowy. Weźmy zbiór X i relację R ⊆ X × X.

Krok 1. Pokażemy, że R jest relacją zwrotną w zbiorze X wtedy i tylko wtedy, gdy I ⊆ R. Dowód równoważności składa się oczywiście z dowodu dwóch implikacji.

Najpierw załóżmy, że R jest relacją zwrotną w zbiorze X. Aby dowieść, że I ⊆ R, weźmy dowolny element p ∈ I. Oczywiście, p jest parą uporządkowaną (ponieważ I jest relacją), obie współrzędne p należą do X (gdyż I jest relacją w zbiorze X) i są sobie równe (dlatego, że I jest relacją identyczności). Tak więc p D ⟨x, x⟩ dla pewnego x ∈ X. Ponieważ R jest zwrotna, więc p D ⟨x, x⟩ ∈ R. W ten sposób dowód zawierania I ⊆ R został zakończony.

Aby dowieść zwrotność relacji R, wystarczy dla dowolnego elementu x ∈ X pokazać, że para ⟨x, x⟩ należy do R. Oczywiście, ⟨x, x⟩ ∈ I na podstawie definicji relacji identycznościowej. Stąd i z zawierania I ⊆ R otrzymujemy, że ⟨x, x⟩ ∈ R.

Krok 2. Teraz pokażemy, że relacja R jest symetryczna wtedy i tylko wtedy, gdy R^{−1} D R. Podobnie jak w kroku 1 udowodnimy dwie implikacje.

Jeżeli relacja R jest symetryczna, to dowolna para ⟨x, y⟩ z relacji R (a właściwie dowolny element relacji R) należy także do relacji R^{−1} . Tak jest, ponieważ z warunku ⟨x, y⟩ ∈ R wynika, że ⟨y, x⟩ ∈ R, a to z kolei oznacza, że ⟨x, y⟩ ∈ R^{−1} . Przedstawione rozumowanie świadczy o tym, że symetryczna relacja R spełnia warunek R ⊆ R^{−1} . Podobnie dowodzimy zawieranie odwrotne: jeżeli ⟨x, y⟩ ∈ R^{−1} , to korzystając z definicji relacji odwrotnej otrzymujemy, że ⟨y, x⟩ ∈ R, a jeżeli skorzystamy jeszcze z symetryczności R, to otrzymamy, że ⟨x, y⟩ ∈ R. Dla relacji symetrycznej prawdziwe są więc dwa zawierania: R ⊆ R^{−1} i R^{−1} ⊆ R. Wobec tego, prawdziwa jest też równość R D R^{−1} .

W drugą stronę, relacja spełniają warunek R D R^{−1} spełnia także zawieranie R ⊆ R^{−1} . To zawieranie oznacza, że R jest relacją symetryczną. Jeżeli bowiem ⟨x, y⟩ ∈ R, to na podstawie tego zawierania mamy, że ⟨y, x⟩ ∈ R^{−1} . Jeżeli teraz skorzystamy z definicji relacji odwrotnej, to otrzymamy, że ⟨y, x⟩ ∈ R.

Krok 3. Pokażemy jeszcze, że przechodniość relacji R jest równoważna zawieraniu RR ⊆ R. Załóżmy, że R jest relacją przechodnią i ⟨x, y⟩ ∈ RR. Z definicji złożenia relacji wynika, że

istnieje z taki, że ⟨x, z⟩ ∈ R i ⟨z, y⟩ ∈ R. Jeden z takich z oznaczmy symbolem z_{0}. Element z_{0} ma więc dwie własności: ⟨x, z_{0}⟩ ∈ R oraz ⟨z_{0}, y⟩ ∈ R. Z przechodniości relacji R otrzymujemy, że ⟨x, y⟩ ∈ R. Kończy to dowód zawierania RR ⊆ R.

Jeżeli RR ⊆ R, to relacja R jest przechodnia. Aby się o tym przekonać weźmy x, y i z takie, że ⟨x, y⟩ ∈ R i ⟨y, z⟩ ∈ R. Z definicji złożenia relacji wynika, że ⟨x, z⟩ ∈ RR. Założone zawieranie implikuje więc, że ⟨x, z⟩ ∈ R, i to kończy dowód przechodniości relacji R.

Krok 4. Z kroków 1, 2 i 3 wynika równoważność z zadania 1. Aby się o tym przekonać, wystarczy zauważyć, że jeżeli zdania φ_{i} są równoważne zdaniom ψ_{i} dla i D 1, 2, 3, to koniunkcja φ_{1} ∧ φ_{2} ∧ φ_{3} jest równoważna koniunkcji ψ_{1} ∧ ψ_{2} ∧ ψ_{3}.

Zadanie 2. Pokaż, że

▷A_{1} ∪ A_{2}◁ · − ▷B_{1} ∪ B_{2}◁ ⊆ ▷A_{1} · − B_{1}◁ ∪ ▷A_{2} · − B_{2}◁.  (1)

Czy zawieranie

▷A_{1} ∩ A_{2}◁ · − ▷B_{1} ∩ B_{2}◁ ⊆ ▷A_{1} · − B_{1}◁ ∪ ▷A_{2} · − B_{2}◁  (2)

jest prawdziwe dla dowolnych zbiorów A_{1}, A_{2}, B_{1} i B_{2}? Odpowiedź uzasadnij.

Rozwiązanie. Zaczynamy od pierwszej inkluzji. Zgodnie z definicją, aby dowieść zawieranie X ⊆ Y powinniśmy wziąć dowolny element x ∈ X i o tym elemencie dowieść, że należy do zbioru Y. Weźmy więc x ∈ ▷A_{1} ∪ A_{2}◁ · − ▷B_{1} ∪ B_{2}◁. Z definicji różnicy symetrycznej wiemy, że element ten spełnia równoważność

x ∈ ▷A_{1} ∪ A_{2}◁ ⇔ x ∉ ▷B_{1} ∪ B_{2}◁.  (3)

Na podstawie tej równoważności niewiele potrafimy rozstrzygnąć. Załóżmy więc dodatkowo, że zachodzi

Przypadek 1: x ∈ ▷A_{1}∪A_{2}◁. Z równoważności (3) otrzymujemy, że x ∉ ▷B_{1}∪B_{2}◁. Wobec tego, zarówno x ∉ B_{1}, jak i x ∉ B_{2}. Dalsze rozumowanie też będzie polegać na rozważeniu kolejnych przypadków.

Przypadek 1.1: x ∈ A_{1}. Wiemy już, że x ∉ B_{1}. Zachodzi więc także równoważność

x ∈ A_{1} ⇔ x ∉ B_{1},  (4)

np. dlatego, że w rozważany przypadku obie strony tej równoważności są prawdziwe, albo dlatego, że dowodzenie tej równoważności polega na wykazaniu dwóch implikacji stwierdzających, że przy pewnych założeniach zachodzą fakty, których prawdziwość udało nam się wcześniej ustalić. Równoważność (4) oznacza, że x ∈ ▷A_{1} · − B_{1}◁, i tym bardziej, x należy do prawej strony wzoru (1).

Przypadek 1.1: x ∈ A_{2}. W tym przypadku, tak jak w poprzednim, dowodzimy, że x ∈ A_{2} ⇔ x ∉ B_{2}, i w konsekwencji, x należy do drugiego składnika prawej strony wzoru (1).

Przypadek 2: x ∉ ▷A_{1} ∪ A_{2}◁. Z równoważności (3) otrzymujemy teraz, że x ∈ ▷B_{1} ∪ B_{2}◁. Mamy więc sytuację analogiczną do opisanej w przypadku 1. Dalszy dowód prowadzimy tak, jak w przypadku 1 zastępując A_{1} i A_{2} zbiorami B_{1} oraz B_{2}, i odwrotnie.

Zawieranie (2) jest też prawdziwe dla wszystkich zbiorów i można się o tym przekonać w bardzo podobny sposób. Proponuję, aby zainteresowane osoby same przekształciły podany dowód zawierania (1) w dowód inkluzji (2). W przypadku 1 w przekształconym dowodzie powinna być rozważana sytuacja, w której x ∉ B_{1} ∩ B_{2}.

Rozwiązanie (drugi sposob). Będziemy korzystać z następująch praw rachunku zbiorów:

X · − Y D ▷X \ X◁ ∪ ▷Y \ X◁,
▷X ∪ Y ◁ \ Z D ▷X \ Z◁ ∪ ▷Y \ Z◁,
X \ ▷Y ∪ Z◁ ⊆ X \ Y.

Posługując się tymi prawami oraz monotonicznością sumy mnogościowej można wykazać, że

▷A_{1} ∪ A_{2}◁ · − ▷B_{1} ∪ B_{2}◁ D ▷▷A_{1} ∪ A_{2}◁ \ ▷B_{1} ∪ B_{2}◁◁ ∪ ▷▷B_{1} ∪ B_{2}◁ \ ▷A_{1} ∪ A_{2}◁◁ D
D ▷A_{1} \ ▷B_{1} ∪ B_{2}◁◁ ∪ ▷A_{2} \ ▷B_{1} ∪ B_{2}◁◁ ∪ ▷B_{1} \ ▷A_{1} ∪ A_{2}◁◁ ∪ ▷B_{2} \ ▷A_{1} ∪ A_{2}◁ ⊆
⊆ ▷A_{1} \ B_{1}◁ ∪ ▷A_{2} \ B_{2}◁ ∪ ▷B_{1} \ A_{1}◁ ∪ ▷B_{2} \ A_{2}◁ D ▷A_{1} · − B_{1}◁ ∪ ▷A_{2} · − B_{2}◁.

Jeżeli wprowadzimy pojęcie dopełnienia zbioru, to w dowodzie zawierania (2) możemy wykorzystać wzór

X · − Y D X^{c} · − Y^{c}.

Zauważmy, że

\begin{matrix}▷A_{1} ∩ A_{2}◁ · − ▷B_{1} ∩ B_{2}◁ D ▷A_{1} ∩ A_{2}◁^{c} · − ▷B_{1} ∩ B_{2}◁^{c} D ▷A_{1}^{c} ∪ A_{2}^{c}◁ · − ▷B_{1}^{c} ∪ B_{2}^{c}◁ ⊆ \\ ⊆ ▷A_{1}^{c} · − B_{1}^{c}◁ ∪ ▷A_{2}^{c} · − B_{2}^{c}◁ D ▷A_{1} · − B_{1}◁ ∪ ▷A_{2} · − B_{2}◁. \end{matrix}

Zadanie 5. Dla jakich zbiorów C prawdziwe jest zdanie stwierdzające, że dla dowolnych zbiorów A i B zachodzi

A × C ⊆ B × C ⇒ A ⊆ B  (5)

Rozwiązanie. Najpierw spróbujemy dowieść implikację (5). Mamy więc zbiory A, B i C, zakładamy, że zbiory te spełniają założenie A × C ⊆ B × C. W tej sytuacji staramy się dowieść, że A ⊆ B. Aby dowieść to zawieranie, bierzemy x ∈ A i próbujemy wykazać, że x ∈ B. Oczywiście, powinniśmy skorzystać z założenia. Łatwo zauważyć, że w tym celu przydałaby się para o pierwszej współrzędnej x i drugiej należącej do C. Aby taką parę utworzyć, musimy mieć element zbioru C. Jest to proste pod warunkiem, że C jest zbiorem niepustym. Wtedy zbiór C ma przynajmniej jeden element. Jeden z elementów zbioru C oznaczamy symbolem c i tworzymy parę ⟨x, c⟩. Ta para należy do iloczynu kartezjańskiego A × C. Na podstawie założenia stwierdzamy, że należy także do iloczynu B × C. Jeżeli ⟨x, c⟩ ∈ B × C, to także x ∈ B.

Przedstawione rozumowanie pozwala dowieść implikację (5), ale wymaga dodatkowego założenia, że zbiór C jest niepusty. Nietrudno zauważyć, że w przypadku, gdy C jest zbiorem pustym, to puste są także zbiory A×C i B ×C, i w konsekwencji, poprzednik implikacji (5) jest prawdziwy dla dowolnych zbiorów A i B. Jeżeli przyjmiemy, że A jest dowolnym zbiorem niepustym (np. zbiorem liczb naturalnych), a B jest zbiorem pustym, to następnik implikacji (5) będzie fałszywy, i to samo będzie można powiedzieć o całej implikacji.

Ostatecznie otrzymujemy, że implikacja A × C ⊆ B × C ⇒ A ⊆ B zachodzi dla wszystkich zbiorów A i B wtedy i tylko wtedy, gdy C nie jest zbiorem pustym.

Zadanie 7. Niech f będzie bijekcją przekształcającą zbiór A w A. Zdefiniujmy relację R ⊆ A^{2} przyjmując, że

xRy ⇔ f ▷x◁ D y.

Symbolem R_{∞} oznaczamy przechodnie domknięcie relacji R, czyli relację ⋃ _{nD1}^{∞} R^{n}, gdzie R^{1} D R oraz R^{nC1} D R^{n}R. Czy

1. R_{∞} jest relacją równoważności?

2. R_{∞} jest relacją równoważności, jeśli A jest zbiorem skończonym?

Odpowiedzi uzasadnij.

Rozwiązanie (część pierwsza). Najpierw zauważmy, że jeżeli funkcję f będziemy traktować jak relację, to warunek f ▷x◁ D y będzie równoważny z ⟨x, y⟩ ∈ f. Tak więc

⟨x, y⟩ ∈ R ⇔ xRy ⇔ f ▷x◁ D y ⇔ ⟨x, y⟩ ∈ f,

czyli relacja R jest tożsama z funkcją f. Wobec tego, relacja R^{n} jest niczym innym, jak n-krotnym złożeniem funkcji f.

Na ogół przechodnie domknięcie relacji R zdefiniowanej w zadaniu nie jest relacją równoważności. Tak jest np. dla zbioru liczb całkowitych Z i funkcji f : Z → Z zdefiniowanej wzorem f ▷k◁ D k C 1. Funkcja f jest oczywiście bijekcją. Dla dowolnego n ∈ N relacja R^{n} spełnia dla wszystkich x, y ∈ Z równoważność

xR^{n}y ⇔ y D x C n.

Jeżeli przedstawione argumenty nie implikują tej równoważności w sposób oczywisty, to proponuję sprawdzenie jej przez indukcję ze względu na n.

Dla tej funkcji f relacja R_{∞} nie jest zwrotna, a nawet jest antyzwrotna. Dla wszystkich x ∈ Z, założenie xR_{∞} x można sprowadzić do sprzeczności w następujący sposób: warunek xR_{∞} x oznacza, że ⟨x, x⟩ ∈ ⋃ _{nD1}^{∞} R^{n}. Tak więc dla pewnej liczby m > 0 mamy ⟨x, x⟩ ∈ R^{m}, czyli xR^{m}x. Z podanej charakteryzacji relacji R^{m} wynika, że x D x C m. Jest to możliwe tylko, gdy m D 0. Przeczy to jednak warunkowi m > 0.

Jeżeli R_{∞} nie jest zwrotna, to nie jest relacją równoważności. Można też dowieść w podobny sposób, że R_{∞} nie jest też symetryczna.

Rozwiązanie (część druga). Założenie o skończoności zbioru A implikuje, że R_{∞} jest relacją równoważności. Dla dowolnego x ∈ A, rozważamy funkcję I : N → A taką, że I ▷n◁ D f^{n}▷x◁ dla wszystkich n ∈ N (I ▷n◁ to wartość n-krotnego złożenia funkcji f dla argumentu x, f^{0}▷x◁ D x). Gdyby funkcja f była różnowartościowa, to zbiór A byłby nieskończony. Dla skończonego zbioru A funkcja f nie jest różnowartościowa. Tak więc możemy znaleźć dwie liczby naturalne p, q takie, że p < q oraz f^{p}▷x◁ D I ▷p◁ D I ▷q◁ D f^{q}▷x◁. Składanie funkcji jest operacją łączną i zachowuje różnowartościowość. Wobec tego, f^{p}▷x◁ D f^{q}▷x◁ D f^{p}▷f^{q−p} ▷x◁◁. Różnowartościowości funkcji f^{p} implikuje także równość f^{p−q} ▷x◁ D x. Udowodniliśmy więc, że jeżeli A jest zbiorem skończonym, to dla dowolnego x ∈ A istnieje liczba dodatnia r taka, że

f^{r}▷x◁ D x.  (6)

Udowodniona własność oznacza, że relacja R_{∞} jest zwrotna. Aby się o tym przekonać, bierzemy x ∈ A i liczbę r > 0 spełniającą (6). Z równości (6) wynika, że ⟨x, x⟩ ∈ f^{r} D R^{r}. Zawieranie R^{r} ⊆ R_{∞} implikuje zaś, że ⟨x, x⟩ ∈ R_{∞} .

Równość (6) implikuje także, że jeżeli iterujemy obliczanie wartości funkcji f zaczynając od argumentu x, to otrzymujemy w kółko te same wartości

f ▷x◁, f^{2}▷x◁, …, f^{r}▷x◁ D x, f ▷x◁, f^{2}▷x◁, …, f^{r}▷x◁ D x, f ▷x◁, …

Spostrzeżenie to pozwala dowieść symetryczność relacji R_{∞} . Najpierw jednak zauważmy, że równość (6) zachodzi także dla wszystkich wielokrotności r. Świadczą o tym następujące obliczenia będące fragmentem dowodu indukcyjnego:

f^{▷kC1◁r}▷x◁ D f^{kr}▷f^{r}▷x◁◁ D f^{kr}▷x◁ D x.

Teraz możemy przystąpić do dowodu, że relacja R_{∞} jest symetryczna. Przypuśćmy, że ⟨x, y⟩ ∈ R_{∞} . Na podstawie definicji R_{∞} stwierdzamy, że ⟨x, y⟩ ∈ R^{n} dla pewnej dodatniej liczby naturalnej n. Ponieważ relacja R^{n} jest równa f^{n}, więc f^{n}▷x◁ D y. Weźmy liczbę naturalną k taką, że n < kr. Dla tej liczby k mamy kr − n > 0 oraz

f^{kr−n}▷y◁ D f^{kr−n}▷f^{n}▷x◁◁ D f^{kr}▷x◁ D x.

Udowodniona równość oznacza, że

⟨y, x⟩ ∈ f^{kr−n} D R^{kr−n} ⊆ R_{∞} .

Przechodniość relacji R_{∞} wynika z zadania 114, które miało być robione na ćwiczeniach.

Z przedstawionych rozumowań otrzymujemy, że jeżeli zbiór A jest skończony, to relacja R_{∞} jest zwrotna, symetryczna. Wiemy też, że jest przechodnia. Tak więc dla zbioru skończonego A, relacją R_{∞} jest równoważnością.

Zadanie 8. Niech A, B będą dowolnymi zbiorami. Kiedy równanie

A ∪ X D B

1. ma dokładnie jedno rozwiązanie,

2. ma nieskończenie wiele rozwiązań,

3. nie ma rozwiązań?

Odpowiedź uzasadnij.

Rozwiązanie. Jeżeli równanie A ∪ X D B ma rozwiązanie, to jest taki zbiór C, że A ∪ C D B. Wtedy oczywiście zbiór A jest podzbiorem B. Także na odwrót, jeżeli A ⊆ B, to zbiór X D B \ A spełnia równanie A ∪ X D B.

Udowodniliśmy więc, że równanie A∪X D B ma rozwiązanie wtedy i tylko wtedy, gdy A ⊆ B. Tym samym odpowiedzieliśmy na pytanie 3: równanie A∪X D B nie ma rozwiązania wtedy i tylko wtedy, gdy A ⊈ B.

Załóżmy, że A ⊆ B. Scharakteryzujemy rozwiązania równania A∪X D B. Warunek A∪C D B implikuje, że C jest podzbiorem B oraz zawiera różnicę B \ A. Prawdziwa jest także implikacja odwrotna: jeżeli B \ A ⊆ C ⊆ B, to

B D A ∪ ▷B \ A◁ ⊆ A ∪ C ⊆ A ∪ B D B,

a więc C spełnia równanie A ∪ X D B. Tak więc zbiorem rozwiązań równania A ∪ X D B jest

{X : B \ A ⊆ X ⊆ B}.

Policzymy jeszcze liczbę elementów tego zbioru, albo jego moc. W tym celu definiujmy funkcję f określoną w zbiorze P▷A◁ wszystkich podzbiorów zbioru A i przyjmującą wartości dane wzorem

f ▷Y ◁ D Y ∪ ▷B \ A◁.

Łatwo dowodzi się, że funkcja f przekształca P▷A◁ na zbiór rozwiązań równania A ∪ X D B. Co więcej, jest to funkcja różnowartościowa. Jeżeli bowiem f ▷Y_{1}◁ D f ▷Y_{2}◁ dla pewnych Y_{1}, Y_{2} ∈ P▷A◁, to

Y_{1} D ▷Y_{1} ∪ ▷B \ A◁◁ ∩ A D f ▷Y_{1}◁ ∩ A D f ▷Y_{2}◁ ∩ A D ▷Y_{2} ∪ ▷B \ A◁◁ ∩ A D Y_{2}.

Tak więc funkcja f ustala rownoliczność zbioru P▷A◁ i zbioru rozwiązań równania A ∪ X D B. Oznacza to, że równanie A ∪ X D B ma tyle elementów, co zbiór P▷A◁ (albo zbiór rozwiązań równania A ∪ X D B jest tej samej mocy, co zbiór P▷A◁).

Teraz łatwo odpowiedzieć na pytania 2 i 3. Jeżeli A jest niepusty to ma przynajmniej dwa podzbiory: zbiór pusty i samego siebie. Tak więc równanie A ∪ X D B ma dokładnie jedno rozwiązanie wtedy i tylko wtedy, gdy A jest zbiorem pustym.

Zbiory skończone mają skończenie wiele podzbiorów, a nieskończone — nieskończenie wiele. Wobec tego, równanie A ∪ X D B ma nieskończenie wiele rozwiązań wtedy i tylko wtedy, gdy A jest zbiorem nieskończonym.

Rozwiązania przygotował Antoni Kościelski