Logika dla informatyków – relacje.pdf

(133 KB) Pobierz
104389759 UNPDF
Relacje
Czym są relacje? Trudno powiedzieć, a u Huzarosa trudno nawet stwierdzić, że to jest
potrzebne do życia. Więc powiedzmy, że jest „czymś”, co łączy dwa obiekty. Nie
wiem, liną, pewnym „związkiem”, „połączeniem” (tak będę nazywać pojedyncze
relacje), czymś takim.
Powiedzmy, że mamy zbiór, składający się z 10 facetów i 10 dziewczym. Możemy je
połączyć (tak, te uśmieszki są kierowane w dobrą stronę) w dowolne pary. Poza tym,
że będziemy mieć niesamowitą orgię, zbiór takich wszystkich możliwych „par”
możemy nazwać „iloczynem kartezjańskim” zbiorów głupich chłopów i czasem
niegłupich bab (te przymiotniki to fakty, nie będziemy się nad nimi rozwodzić).
Jeżeli mamy dwa zbiory – zbiór A oraz zbiór B, to iloczyn kartezjański możemy
krótko określić jako A x B.
Przykład:
Mamy zbiór A, składający się z cyfr: 2, 3, 4
I zbiór B, składający się z cyfr: 1, 5, 6.
Trzeba dodać, że odpowiednie „pary” zazwyczaj zapisuje się w ostrych nawiasach
„<”, „>”. Iloczyn kartezjański będzie się składać z następujących elementów:
{<2,1>,<2,5>,<2,6>, //to, z czym można „połączyć” dwójkę ze zbioru A
<3,1>,<3,5>,<3,6>, //to, z czym można „połączyć” trójkę ze zbioru A
<4,1>,<4,5>,<4,6>} //to, z czym można „połączyć” czwórkę ze zbioru A.
Proszę wybaczyć, ale nie pamiętam, a szczerze powiedziawszy – nie chce mi się
zaglądać do skryptu i spojrzeć, czy tutaj można dołączyć zbiory puste – proszę mnie
kopnąć, jeżeli tak faktycznie jest.
Ogólnie, relacją jest pewien zbiór elementów z takiego iloczynu kartezjańskiego.
Mówiąc prosto (i wracając do przykładu z parami), każdą orgię można nazwać
relacją. Obojętnie, ile par weźmiesz, i tak będziesz mieć coś, co możesz nazwać
relacją.
Relacje
autor: Verbox
1/12
Relacje mogą mieć różne „fajne” cechy.
Relacja symetryczna
Są to takie, w których obydwa elementy „się przyciągają”. Jeżeli Ty kogoś kochasz, a
ten/ta ktoś kocha także Ciebie, to można to nazwać relacją symetryczną. Jeżeli jakiś
obiekt jest w relacji z jakimś, to także po „odwróceniu ich” taka relacja będzie
zachodzić.
Zawile? Jeżeli kogoś lubisz, to ten ktoś musi lubić także Ciebie, by zachodziła pełna
„symetria”. Jeżeli jakiś autobus jedzie z Wrocławia do Częstochowy, to by zachodziła
pełna „symetria”, to musi także jechać z Częstochowy do Wrocławia.
I przykładem iście „kolejowym” ostatecznie postaram się wytłumaczyć znaczenie
symetrii w relacjach.
Załóżmy, że jakiś pociąg zawozi „studentów” (przecież 50 oblanych w
programowaniu nie może się nazywać studentami informatyki) z Opola do
Wrocławia. Oznaczmy sobie ten „przewóz” (zauważcie, że na bilecie będzie
napisane „relacja”).
<Opole, Wrocław>
Dobrze by było, by także jeździł taki pociąg z Wrocławia do Opola, w końcu nie
wszyscy wytrzymają kilka tygodni w jednym mieście z Huzarosem.
<Wrocław, Opole>
A więc w naszej bazie mamy następujące „połączenia”:
<Opole, Wrocław>
<Wrocław, Opole>
No dobra, załóżmy, że chcemy mieć krakusów we Wrocławiu, żeby zachwycali się
naszą „wspaniałą” Politechniką, może któryś z mieszkańców, po zobaczeniu Rataja
stwierdzi, że to także siedziba Świętego Mikołaja. Więc stwórzmy „połączenie” z
Krakowa do Wrocławia.
<Kraków, Wrocław>
Pomimo zachwycania się Wrocławiem, krakusy chciałyby wrócić do domu. By
zachować niejako „symetrię”, zróbmy połączenie odwrotne.
Relacje
autor: Verbox
2/12
<Wrocław, Kraków>
W naszej „bazie” mamy więc cztery połączenia (dla lepszego dalszego tłumaczenia,
ponumeruję je):
1) <Opole, Wrocław>
2) <Wrocław, Opole>
3) <Kraków, Wrocław>
4) <Wrocław, Kraków>
A teraz weźcie skrypt Huzarosa i przeczytajcie, co pisze w definicji. Oto, co pisze
(uwaga! Ważna kolejność)
Jeżeli (każdy) obiekt A jest w relacji z obiektem B, to by nazwać tę relację, to (każdy)
obiekt B musi być w relacji z obiektem A. (Tym, co widzicie w nawiasach, nie
przejmujcie się, zaraz to wyjaśnimy)
Teraz szybciutko sobie przypominamy implikację, czyli => z prawa rachunku zdań.
Wiemy, że takie zdanie jest fałszywe wtedy i tylko wtedy, gdy następnik (czyli to „po
strzałeczce”) jest bullshitem, czyli nieprawdą.
Spójrzmy na te nasze cztery połączenia. Sprawdźmy, czy ta relacja jest relacją
symetryczną.
Bierzemy pierwszą z brzegu, czyli bramkę numer 1. Jest to „połączenie” <Opole,
Wrocław>. No dobra, mamy takie połączenie. Jeżeli teraz zamienimy kolejność, to
wyjdzie nam relacja <Wrocław, Opole>. Spójrzmy na zapis „pół-logiczno-
semantyczny”:
Jeżeli jest relacja <Opole, Wrocław> => musi być relacja <Wrocław, Opole>
To jest warunek konieczny do tego, by dana relacja była symetryczna! Jeżeli mamy
dwa obiekty w relacji (a pamiętajmy, że relacją nazywamy także zbiór takich
„połączeń”, nie tylko jedną), to możemy ją nazwać symetryczną wtedy i tylko wtedy,
gdy wszystkie relacje mają swoje „lustrzane” odbicia.
Wróćmy do tego warunku. Czy mamy wśród tych połączeń połączenie <Wrocław,
Opole>? Oczywiście, ale nie otwierajmy od razu szampanów! Huzaros tylko na to
czeka, by z mikrofonem w okularach pokazać na nas palcem i swoim
charyzmatycznym głosem rzec „Haha, ale nie sprawdziłeś wszystkich relacji,
głupcze!”.
Cóż, no to sprawdzamy. Bierzemy drugą relację, czyli <Wrocław, Opole>. No dobra,
Relacje
autor: Verbox
3/12
ale już pokazaliśmy, że istnieje „lustrzane” odbicie. Już oczyma wyobraźni widzimy
Huzarosa i ten znikający z jego urodziwej twarzy uśmieszek. No to sprawmy, by
zniknął kompletnie!
Bierzemy trzecie połączenie, czyli <Kraków, Wrocław>. Sprawdzamy, czy istnieje
połączenie „lustrzane”, czyli <Wrocław, Kraków>. Istnieje? Tak!
Sprawdzanie czwartej relacji nie jest konieczne, bo wiemy, że jest ona „lustrzanym”
odbiciem trzeciej.
A więc tak, proszę państwa, nasza relacja jest symetryczna.
Przykład
Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {<a,b>, <b,a>,
<c,a>}. Sprawdzić, czy ta relacja jest symetryczna.
No dobra, spójrzmy na pierwsze „połączenie” (wybaczcie, tak sobie nazywam
relację, dla mnie jest to po prostu łatwiejsze do wyobrażenia sobie). Mamy
połączenie <a,b>, a więc sprawdźmy, czy mamy połączenie <b,a>. Mamy? A i
owszem!
Dobra, ale wiemy, że dla każdej (to jest właśnie te niepokojące słówko z nawiasów z
poprzedniej strony) relacji musi istnieć „lustrzane” odbicie, by taka relacja była
symetryczna. Mamy połączenie <c,a>. Niestety, musimy spojrzeć prawdzie w oczy.
Nie mamy „lustrzanego” odpowiednika w naszej relacji. Więc niestety, ta relacja nie
jest symetryczna.
Przykład
Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {0}. Sprawdzić,
czy ta relacja jest symetryczna.
By nie było wątpliwości - „0” oznacza zbiór pusty.
Jak widzimy, nic nie widzimy, a nie widzimy żadnej relacji. Każdy od razu zaznaczy,
że relacja nie jest symetryczna, ale czy tak jest faktycznie.
Spójrzcie raz jeszcze na niby-definicję, a właściwie na pierwsze słowo. Chwila, czy
implikacja nie jest prawdziwa, jeżeli poprzednik (czyli to „przed strzałeczką”) jest
fałszem. Hmm...
Oczywiście, że jest prawdziwa! Wystarczy spojrzeć na tabelę prawdy implikacji, by
Relacje
autor: Verbox
4/12
się przekonać, że musi być taka relacja, by można było szukać jej lustrzanego
odbicia. Nie ma mocy, po prostu „coś” trzeba sprawdzić i „coś” musi być w relacji,
by można było szukać symetrii.
Dlatego zauważcie, że w poprzednim przykładzie nie przejmowaliśmy się tym, że w
zbiorze jest jeszcze literka „d”. Jest gdzieś w jakimś połączeniu? Nie? To pierdoli
nas, idziemy dalej.
Dlatego ostateczna odpowiedź brzmi – tak, ta relacja jest symetryczna.
Moje wątpliwości
Przykład
Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {<a,b>, <b,a>,
<c,c>}. Sprawdzić, czy ta relacja jest symetryczna.
Dwie pierwsze relacje są wyjaśnione powyżej. Widzimy także relację <c,c>. Niestety,
nie jestem w stu procentach pewien, czy takie „połączenie” możemy nazwać
symetrycznym (o zwrotności za chwilę). Według mnie, ta relacja jest symetryczna, bo
albo uznajemy, że odbiciem lustrzanym relacji <c,c> jest ona sama, albo uznajemy,
że pierwsza część implikacji nie jest zbytnio prawdziwa. Ale to tylko moje zdanie, jak
wyrazicie swoje zdanie – ten felerny przykład się poprawi.
Relacja zwrotna
Mówiąc krótko, jeżeli relacja jest zwrotna, to każdy element z danego zbioru musi
być w relacji z samym sobą (musi być połączony z samym sobą). To jedyna taka
„cecha” relacji (prócz spójności), że wymaga „uczestnictwa” każdego elementu
zbioru. Spójrzmy na przykład:
Przykład
Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {<a,a>, <b,b>,
<c,c>, <d,d>, <a,b>}. Sprawdzić, czy ta relacja jest zwrotna.
Najpierw popatrzmy na elementy zbioru. Mamy element „a”. No dobra, to szukamy
połączenia „a” z samą sobą. Poszukiwania nie trwają długo – mamy relację <a,a>.
Tak samo z literką b. Znaleźliśmy? Odhaczamy na „liście” literkę a. Ale trzeba
spojrzeć na wszystkie elementy zbioru X. Literka „b” jest w relacji z samą sobą?
Świetnie. „c” też? Fenomenalnie i kapitalnie. A literka „d”? A i owszem.
A reszta relacji nas nie interesuje, więc z relacją <a,b> możemy zrobić to, co miejmy
Relacje
autor: Verbox
5/12

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin