Matematyka Dyskretna

POJECIE ZBIORU Zbiory możemy określać (czy definiować) na różne sposoby. Najczęściej przez wyliczenie elementów, przez podanie cech (własności) wyróżniających w pewien sposób elementy zbioru, przez podanie metody obliczania kolejnych elementów. Wyjaśnimy to na przykładzie. Przykład Niech jedynymi elementami pewnego zbioru X będą liczby 1,3,5,7,9. Zapiszemy ten fakt jako X = {1,3,5,7,9} Nawiasy klamrowe symbolizują zbiór, a przecinki oddzielają poszczególne elementy zbioru. Ten sam zbiór X możemy określić wymieniając właściwości charakteryzujące jego elementy: X jest zbiorem tych liczb naturalnych, nieparzystych, które nie przekraczają 10. X = {x : x jest liczbą naturalną, nieparzystą i x<11} lub X = {x Î N : x jest liczbą nieparzystą, mniejszą od 11} Na koniec, zbiór X możemy opisać podając przepis, według którego obliczamy jego elementy: 1. Przyjmij i =1. 2. Wylicz 2i-1 i dołącz do tworzonego zbioru. 3. Zwiększ i o 1. 4. Zakończ, jeśli i=6, lub powtórz od punktu 2, jeśli i<6. Piszemy X= {2i-1: i=1,2,3,4,5}. To ostatnie sformułowanie jest szczególnie miłe sercu informatyka, który zwykle poszukuje algorytmicznych metod rozwiązywania zadań. Przykład Niech A będzie dwuelementowym zbiorem, A = {0,1}. Określimy nowy zbiór A*, jako zbiór wszystkich skończonych ciągów, włączając w to ciąg pusty, o elementach ze zbioru A. Zbiór A* nazywamy zbiorem słów nad alfabetem A. Przykładami elementów zbioru A* są ciągi (001), (000101), (111). Zbiór A* zawiera nieskończenie wiele elementów. W informatyce, ciągi tego typu służą do kodowania np. liczb. Jeśli (an,...,a0) jest  (n+1)-elementowym ciągiem z A*, to ciąg ten reprezentuje (koduje) liczbę a0 2^0 + a1 2^1 +... +an 2^n, na przykład ciąg (101) jest kodem liczby 5, a (1000) jest kodem liczby 8. Zwróćmy jeszcze uwagę na jeden wyróżniony zbiór: zbiór, który nie posiada elementów. Nazywamy go zbiorem pustym i oznaczamy przez Æ. Jest tylko jeden taki zbiór. Jeśli Y jest zbiorem tych liczb naturalnych, których kwadraty są liczbami ujemnymi, to Y nie posiada ani jednego elementu, Y jest zbiorem pustym.

SUMA ZBIORÓW

Na zbiorach określa się pewne operacje (działania), które pozwolą z danych zbiorów utworzyć nowe. W dalszej części wykładu omówimy operacje dwuargumentowe sumy,  przecięcia, różnicy i jednoargumentową operację uzupełnienia. Rodzina podzbiorów pewnej przestrzeni z tymi właśnie operacjami nazywa się algebrą zbiorów.

Definicja

Sumą zbiorów A i B nazywamy zbiór, którego elementami są wszystkie elementy zbioru A i wszystkie elementy zbioru B. Sumę zbiorów A i B oznaczamy A  B. Krótko zapiszemy

x  A  B wttw x  A lub x  B.

Przykład

Niech A = {2k : k  N} i B = {3n : n  N}. Wtedy A  B jest zbiorem wszystkich liczb, które dzielą się przez 2 lub przez 3,

A  B = { n  N : n dzieli się przez 2 lub przez 3}.

Liczba 15  A  B, bo dzieli się przez 3, a liczba 8  A  B, bo dzieli się przez 2. Liczba 6 należy też do zbioru A  B, bo dzieli się zarówno przez 2, jak i przez 3.

Operacja sumy, określona na zbiorach ma własności podobne do tych, jakie przysługują operacji dodawania w zbiorze liczb rzeczywistych. Poniżej wymienimy niektóre z nich.

Twierdzenie

Dla dowolnych zbiorów A, B, C zachodzą równości:

  A = A

A  A = A (prawo idempotentności)

A  B = B  A (prawo przemienności)

(A  B)  C = ( A  (B  C) (prawo łączności)

Dowody tych równości (pozostawiamy Czytelnikowi). Można je przeprowadzić wykazując, że x należy do lewej strony równości wtedy i tylko wtedy, gdy x należy do prawej strony równości.

Oczywiście zarówno zbiór A jak i zbiór B są podzbiorami zbioru A  B. Wynika stąd często stosowana własność monotoniczności:

 Dla dowolnych zbiorów A, B, C, D, jeśli A  C i B  D, to A  B  C  D.

Dowód

Załóżmy, że (1) A  C i (2) B  D. Jeżeli jakiś element x  A  B, to na mocy definicji sumy  x  A lub x  B. Jeśli x  A, to na mocy założenia (1), x  C, a stąd x  C  D. Jeśli x  B, to na mocy założenia (2), x  D, czyli należy także do C  D. Zatem każdy element zbioru A  B należy też do zbioru C  D.

Dla dowolnych zbiorów A i B, A  B wttw A  B = B.

Dowód

Załóżmy, że  A  B. Gdyby   x  A   oraz   x  B, to musiałoby być, że x  A. Wtedy jednak,  na mocy założenia,  x  B, sprzeczność. Odwrotnie, jeśli  x  B, to x należy do każdego większego zbioru, w szczególności x  A  B. Wynika stąd, że A  B implikuje A  B = B.

Załóżmy teraz, że  A  B = B i rozważmy element x, x  A. Oczywiście, x     . Wtedy jednak, na mocy założenia, że zbiory A  B i B są równe, mamy  x  B. Ponieważ rozważaliśmy dowolny element x, zatem A  B.

PRZECIĘCIE ZBIORÓW

Definicja

Iloczynem lub przecięciem zbiorów A i B nazywamy zbiór A  B składający się z elementów, które należą równocześnie do A i do B,

x  A  B wttw x A i x  B.

Przykład

(a) Niech A = {2i: i <16, i  N }, B={3i: i<11, i N}. Wtedy A  B zawiera tylko te liczby naturalne, które dzielą się zarówno przez 2 jak i przez 3 oraz nie są większe niż 30,

A  B = {0, 6, 12, 18, 24, 30} = {6i : i<6, i  N}.

(b) Niech X będzie zbiorem wszystkich studentów, a Y zbiorem wszystkich kobiet. Wtedy X  Y jest zbiorem wszystkich studentek

Na mocy definicji przecięcie zbiorów A  B jest zarówno podzbiorem A jak i podzbiorem B. W szczególnym przypadku takie przecięcie może być puste. Mówimy wówczas, że zbiory A i B są rozłączne.

Wprost z definicji iloczynu zbiorów wynika, że x A  B, gdy nie jest spełniony chociaż jeden z warunków definicji , czyli

x A  B wttw x  A lub x  B

Iloczyn zbiorów, podobnie jak suma, jest operacją łączną i przemienną a ponadto zachodzi prawo rozdzielności sumy względem iloczynu.

A  (B  C) = (A  B)  C (łączność)

A  B = B  A (przemienność)

A  (B  C) = (A  B)  (A  C) (rozdzielność)

Wymienione prawa przypominają analogiczne zasady rządzące sumą i iloczynem liczb rzeczywistych. Tu jednak kończy się analogia. Następujące prawa nie mają odpowiednika w arytmetyce liczb rzeczywistych.

A  A = A (prawo idempotentności)

A  (A  B) = A, A = A  (A  B) (prawa absorbcji, lub inaczej pochłaniania)

A  (B  C) = (A  B)  (A  C) (prawo rozdzielności iloczynu względem sumy)

Podobnie jak w przypadku sumy, inkluzje można "mnożyć" stronami. Zachodzi bowiem następujący fakt:

Jeśli A  C i B  D, to A  B  C  D.

Dowód. 

Załóżmy, że A  C i B  D . Jeżeli x  A  B, to zgodnie z definicją przecięcia, x  A i x  B. Na mocy przyjętych założeń mamy więc x  C i x  D, czyli x  C  D. Wynika stąd, że dowolny element zbioru A  B należy do zbioru C  D, czyli A  B  C  D.

RÓŻNICA ZBIORÓW Różnicą zbiorów A i B nazywamy zbiór A\B, którego elementami są te elementy zbioru A, które nie są elementami zbioru B: x  A\B wttw x  A i x  B Definicję powyższą można też krótko zapisać w postaci A\B = { x  A : x  B} Przykład (a) Niech A = {1, 2, 3, 4, 5, 6} i B={2i+1  N : i <5}. Wtedy A\B = {2, 4, 6}, a B\A = {7, 9}. (b) Niech Q oznacza zbiór wszystkich liczb wymiernych. Wtedy R\Q jest zbiorem liczb niewymiernych. Z przyjętej definicji różnicy wynika, że x  A\B wtedy i tylko wtedy, gdy któryś z warunków "x  A" lub "x  B" nie jest spełniony. Zatem x  A\B wttw x  A lub x  B Następujący lemat ustala związek między inkluzją, a różnicą zbiorów. W szczególności wynika z niego powszechnie znane prawo: "jeśli odejmiesz więcej to pozostanie mniej". Dla dowolnych zbiorów A, B, C, D, jeśli A  B i C  D, to A\D  B\C. Dla dowodu tej zależności, załóżmy, że A  B i C  D i rozważmy dowolny element x  A\D. Wtedy x  A i x D. Skoro x A, to x  B, bo A  B. Skoro x D, to x  C, bo C  D. Mamy więc ostatecznie, x  B i x  C, co oznacza, że x  B\C. Do najważniejszych praw rachunku zbiorów należą zależności wiążące sumę, różnicę i iloczyn zbiorów, zwane prawami de Morgana. Twierdzenie Dla dowolnych zbiorów A, B, C zachodzą równości (prawa de Morgana): A \ (B  C) = (A \ B)  (A \ C) A \ (B  C) = (A \ B)  (A \ C) Dowód Przedstawimy dowód pierwszego prawa De Morgana. 1. Jeśli x  (A \ B)  (A \ C), to x  A oraz x  B i x  C. Stąd x  A i x  (B  C), czyli x  A \ (B  C). Wykazaliśmy tym samym zawieranie (A \ B)  (A \ C)  A \ (B  C). W dowodzie implikacji odwrotnej wykorzystamy udowodnione wcześniej prawa rachunku zbiorów. Ponieważ B  (B  C) i C  (B  C), zatem na mocy lematu 1.5 mamy A \ (B  C)  (A \ B) i A \ (B  C)  (A \ C) . Stąd na mocy lematu 1.4 mamy A \ (B  C)  (A \ B)  (A \ C). 2. Zamiast dowodu, lewą i prawą stronę drugiej z równości zilustrujemy, przy pomocy diagramów Venna (por. Rys. 1.8). Dowody przy pomocy diagramów Venna są bardzo intuicyjne i przez to łatwiejsze, i chociaż nie do końca opisują szczegóły rozumowania, będziemy je czasami przedstawiać. Bardzo często, rozważane w zastosowaniach zbiory, są same podzbiorami jakiegoś jednego większego zbioru. Po prostu w swoich rozważaniach ograniczmy się tylko do elementów pewnego zbioru. Zbiór ten będziemy nazywać przestrzenią lub uniwersum. Jeśli U jest takim zbiorem i rozważamy tylko jego podzbiory, to różnicę U\A nazywamy uzupełnieniem zbioru A w uniwersum U i oznaczamy przez -A lub A^c (od angielskiego słowa complement). Prawa de Morgana zapisane dla operacji uzupełnienia przyjmują postać: - (A  B) = (- A)  (- B) - (A  B) = (- A)  (- B) Powyższe równości zachodzą dla dowolnych zbiorów A, B, będących podzbiorami tego samego uniwersum U. Czytamy: uzupełnienie sumy zbiorów jest równe iloczynowi uzupełnień, uzupełnienie iloczynu zbiorów jest równe sumie uzupełnień. Uwaga. Uważny czytelnik dostrzeże dualność praw rachunku zbiorów: jeśli w jakimś prawie sumę zastąpimy iloczynem, a iloczyn zastąpimy przez sumę, to otrzymamy również prawo rachunku zbiorów. Różnicą symetryczną zbiorów A i B nazywamy zbiór A B, elementami którego są te elementy zbioru A  B, które nie należą równocześnie do obu zbiorów A i B, por. Rys.1.9 x A  B wttw x (A  B)\(A  B) Zwróćmy uwagę na występującą w tej definicji alternatywę wykluczającą: x A  B wttw albo x A albo x  B). Dlaczego operacja ta nazywa się różnicą symetryczną? Wynika to z następującej charakteryzacji operatora  : A  B = (A\B)  (B\A) Prawdziwość powyższej równości wynika wprost z praw deMorgana A  B = (A  B)\(A  B) = (A  B)\ A  (A  B)\ B = (B\A)  (A\B) = (A\B)  (B\A) Przykład Niech A = {2i N : i<6} i B = {3i N: i< 6}. Wtedy A  B = {2,4,8,10,3,9,12,15}

PRODUKT KARTEZJAŃSKI ZBIORÓW

Para uporządkowana, jest to układ (x,y) dwóch obiektów, w których x jest poprzednikiem pary, a y następnikiem. Oczywiście, mając jakiekolwiek dwa obiekty możemy zawsze utworzyć parę uporządkowaną wskazując, który z nich jest poprzednikiem a który jest następnikiem. Na przykład, Kubuś Puchatek i jego Pan tworzą znaną parę uporządkowaną (Kubuś, Krzyś).

Parę uporządkowaną należy odróżnić od, po prostu, pary elementów lub zbioru dwuelementowego. {Kubuś, Krzyś} jest dwuelementowym zbiorem, w którym żaden z elementów nie jest w żaden sposób wyróżniony, nie mamy ustalonej kolejności obiektów. W parze uporządkowanej (Kubuś, Krzyś) kolejność jest istotna: Kubuś jest poprzednikiem, a Krzyś następnikiem w tej parze uporządkowanej.

W 1921 roku Kazimierz Kuratowski, podał definicję pary uporządkowanej (x, y) jako zbioru, którego elementami są dwa zbiory: jednoelementowy {x} i dwuelementowy {x, y},

(x, y) = ^df { {x}, {x, y}}

Takie pojęcie pary uporządkowanej jest zgodne z warunkiem równości par uporządkowanych : dwie pary uporządkowane (x,y) i (x', y') są równe, gdy mają równe zarówno poprzedniki jak i następniki

(x, y) = (x', y') wttw x = x' i y = y'

Wynika stąd, że

(Kubuś, Krzyś)  (Krzyś, Kubuś)

Definicja 

Produktem kartezjańskim zbiorów X i Y, oznaczanym przez X Y, nazywamy zbiór złożony z wszystkich par uporządkowanych (x,y) takich, że x X i y Y,

(x, y)  X Y wttw x X i y Y.

Z tej definicji wynika, że jeśli jeden ze zbiorów jest pusty, to produkt X Y też jest zbiorem pustym, bo nie można utworzyć ani jednej pary uporządkowanej. Jeśli natomiast X ma m elementów, a Y n elementów, to można utworzyć nm różnych par.

Przykład

 

1. Na płaszczyznę Euklidesową przywykliśmy patrzeć jako na zbiór wszystkich punktów postaci (x, y), gdzie x jest odciętą punktu a y rzędną punktu oraz xR i yR. Zatem płaszczyzna rzeczywista to po prostu produkt kartezjański RR.

 

2. Podobnie zbiór liczb zespolonych jest produktem RR. Dowolna liczba zespolona (x+iy) o części rzeczywistej x i części urojonej y, to nic innego jak para uporządkowana o poprzedniku x i następniku y.

 

3. Jeśli X= {1,2}, a Y = {a,b,c}, to produkt kartezjański X Y składa się z par uporządkowanych (1,a), (1,b), (1,c), (2,a), (2,b), (2,c).

 

4. Niech X i Y będą w tym przykładzie przedziałami w zbiorze liczb rzeczywistych, np. X=[2,4] a Y=[3,6]. Wtedy elementy produktu kartezjańskiego X Y wypełniają prostokąt, którego rzutami na osie układu są odpowiednio zbiory X i Y, por. Rys. 2.1.

W lemacie przedstawionym poniżej zanotujemy związki produktu kartezjańskiego z innymi operacjami na zbiorach.

Dla dowolnych zbiorów X, A, B zachodzą równości:

X  (A  B) = (X  A)  (X  B),

X  (A  B) = (X  A)  (X  B),

X  (A \ B) = (X  A) \ (X  B).

Dowody takich własności najczęściej przeprowadza się pokazując, że uporządkowana para (x, y) należy do lewej strony równości wtedy i tylko wtedy, gdy należy do prawej strony równości. Dla przykładu rozważmy trzecią z równości: (x, y) X (A\B) wttw x  X i y (A \ B) wttw x  X , y A i y  B wttw : (x, y)  (X  A) i : (x, y)  (X  B) wttw (x, y)  (X  A) \ (X  B).

PORÓWNYWANIE ZBIORÓW

Jest rzeczą naturalną, że mając wiele obiektów tego samego typu chcemy je ze sobą porównywać. Wprowadzimy teraz formalnie dwie relacje pozwalające porównywać zbiory.

Definicja 

Równość zbiorów

Powiemy, że dwa zbiory X i Y są równe, X = Y, wtedy i tylko wtedy, gdy dla dowolnego x, jeśli x X, to x Y i jeśli x Y , to x X. Będziemy stosowali również nieco krótszy zapis symboliczny :

X=Y wttw (x  X   x  Y) oraz (x Y  x  X).

W myśl tej definicji, dwa zbiory są równe, jeśli posiadają te same elementy. Oczywiście, wypisanie kilkakrotne tego samego elementu lub zapisanie elementów zbioru w innej kolejności, nie zmienia zbioru. Stąd mamy:

{1,2,3,4,5} = {x  N : 0<x<6 } = { 1,1,2,2,3,3,4,4,5,5} = {5,4,3,2,1}

{x  N : x² <0 } = {x  R : x= x+1} = {x: x jest pierwiastkiem rzeczywistym równania x² +2x + 2 = 0}.

Uwaga. W dalszym ciągu,  wypisując elementy zbioru w postaci{x₁,...,x_n} będziemy milcząco zakładali, że są one różne. Liczbę elementów w zbiorze {x₁,...,x_n} nazywać będziemy mocą zbioru i oznaczymy przez |{x₁,...,x_n}|, a więc |{x₁,...,x_n}|= n.

Dla dowolnych zbiorów X, Y, Z, jeśli X = Y oraz Y = Z, to X = Z.

Warto też zastanowić się przez chwilę nad zaprzeczeniem równości. Co to znaczy, że X  Y?  Zgodnie z przyjętą definicją równości, musi istnieć taki element zbioru X, który nie należy do Y, lub musi istnieć taki element zbioru Y, który nie jest elementem zbioru X. Na przykład, R  N, bo 2  R i 2 N. Z drugiej strony jednak, każda liczba naturalna jest liczbą rzeczywistą.

Definicja

Zawieranie zbiorów

Powiemy, że zbiór X jest zawarty w Y albo, że zbiór Y zawiera zbiór X , i piszemy X  Y wttw każdy element zbioru X jest równocześnie elementem zbioru Y.

Jeśli X  Y, to w szczególności X może być równe Y. Aby zaznaczyć, że taka sytuacja nie może mieć miejsca, piszemy X  Y. O relacji  mówimy, że jest to inkluzja albo relacja zawierania. Natomiast symbol  nazywamy zawieraniem właściwym. O zbiorze X, takim że X  Y (X  Y) mówimy, że jest podzbiorem zbioru Y (podzbiorem właściwym zbioru Y), a o Y mówimy, że jest nadzbiorem zbioru X.

Zbiory i zachodzące miedzy nimi związki, będziemy przedstawiali również graficznie w postaci obszarów (kół) na płaszczyźnie. Fakt, że zbiór A jest zawarty w zbiorze B można przedstawić na rysunku w postaci tzw. diagramu Venna.

1. Zbiór studentek jest oczywiście podzbiorem zbioru wszystkich osób studiujących w uczelni. Natomiast zbiór wszystkich studentów uczelni jest podzbiorem zbioru wszystkich studentów studiujących w Polsce.

2. Na szczególną uwagę zasługują pewne wyróżnione podzbiory zbioru liczb rzeczywistych zwane przedziałami. Przedziałem domkniętym o końcach a, b nazywamy zbiór [a, b] = {x  R : a  x  b}. Przedziałem otwartym o końcach a, b nazywamy zbiór (a, b) = {x  R : a  x  b}. Można mówić także o przedziałach otwarto domkniętych lub domknięto otwartych, jeśli jeden z końców przedziału do niego należy.

Zauważmy, że jeżeli nie jest prawdą, że zbiór A zawiera się w zbiorze B, to możliwe są następujące 3 przypadki

• albo A i B nie mają wspólnych elementów i w takim wypadku mówimy, że są to zbiory rozłączne,

• albo A jest nadzbiorem zbioru B, czyli wszystkie elementy zbioru B są elementami A,

• albo A ma takie elementy, które nie należą do B i B ma takie elementy, które nie należą do A.

Zauważmy, że zbiór A nie jest zawarty w B wtedy i tylko wtedy, gdy istnieje a, a   , a   

Przykład

Zbiór liczb podzielnych przez 2 nie jest podzbiorem zbioru liczb podzielnych przez 5, bo np.4 jest podzielne przez 2 i nie jest podzielne przez 5. Nie jest też odwrotnie: zbiór liczb podzielnych przez 5 nie jest podzbiorem zbioru liczb podzielnych przez 2, bo np. 15 jest podzielne przez 5, a nie jest podzielne przez 2

Twierdzenie

Dla dowolnych zbiorów A, B, C zachodzą następujące zależności:

•    A,

• A   A,

• Jeśli A  B i B  C, to  A  C.

Zależność 1 wyraża fakt, że zbiór pusty jest podzbiorem dowolnego zbioru. Rzeczywiście, mamy pokazać, że każdy element należący do zbioru  , należy też do A. Ale do zbioru pustego nie należy żaden element. Zatem zachodzi    A.
Zależność 2 jest oczywista, na mocy definicji zawierania.
Zależność 3, jest zwana prawem przechodniości dla relacji inkluzji. Aby wykazać jej słuszność, załóżmy, że A  B i B  C. Jeśli jakiś element a należy do zbioru A, to na mocy pierwszego założenia a  B, a z drugiego  a  C. Zatem, jeśli tylko a  A, to a  C.

Definicja

Zbiorem potęgowym nazywamy zbiór P(A)  złożony z wszystkich podzbiorów zbioru A. Zbiór potęgowy oznaczmy też czasem 2^A.

Przykład

(a) Niech A = {0, 1} wtedy zbiór wszystkich jego podzbiorów, P(A), składa się z 4 zbiorów , {0}, {1}, {0,1}. Zatem P(A) = {, {0},{1}, {0,1}}

(b) Jeśli B = {1,{2},{1,2}}, to  jego elementami są : liczba 1, zbiór jednoelementowy {2} oraz zbiór dwuelementowy {1,2}. Podzbiorami zbioru B są natomiast : zbiór pusty, podzbiory jednoelementowe {1}, {{2}}, {{1,2}}, podzbiory dwuelementowe {1,{2}}, {1,{1,2}}, {{2}, {1,2}} oraz jeden podzbiór trzyelementowy {1, {2}, {1,2}} identyczny z B. Zatem P(B) ma 8 elementów.

Uwaga. P(A) nigdy nie jest zbiorem pustym. Nawet, gdy A jest zbiorem pustym, to P(A) jest zbiorem jedno-elementowym, bo chociaż A nie posiada elementów, to ma jeden podzbiór  . Czyli P( ) = { }.

RELACJE RÓWNOWAŻNOŚCI

Przykład

Niech X oznacza zbiór samochodów, które zostały wyprodukowane w latach 1951-2000. Zdefiniujemy w zbiorze X relację binarną  taką, że dla dowolnych x, y X,

x  y wttw samochody x i y mają ten sam rok produkcji.

Relacja ta tworzy w zbiorze X pięćdziesiąt grup-klas. Oznaczmy te klasy kolejnymi liczbami rzymskimi I, II, III,... w taki sposób, że do klasy XL należą wszystkie te samochody, które zostały wyprodukowane w 1990 roku, a do klasy V - wszystkie te samochody, które zostały wyprodukowane w 1955r. Jeśli chcemy ustalić np. podatek drogowy, uzależniony od roku produkcji samochodu, to zamiast podawać wysokość podatku dla każdego x X, wystarczy określić funkcję Podatek na klasach I, II,...,L. Podatek (IX) = x oznacza, że właściciele samochodów wyprodukowanych w 1959 roku płacą podatek w wysokości x zł.

Zauważmy, że relacja  jest zwrotna (dla wszystkich x, xx), jest symetryczna (dla wszystkich x, y, jeśli xy, to y x) oraz jest przechodnia (jeśli xy i y z, to wszystkie trzy samochody zostały wyprodukowane w tym samym roku, czyli w szczególności, x i z są z tego samego roku). Własności zwrotności, symetrii i przechodniości przysługujące relacji = przeniosły się na relację .

Definicja

Relację binarną  określoną w zbiorze X nazywamy relacją równoważności wtedy i tylko wtedy, gdy relacja  jest zwrotna, symetryczna i przechodnia, tzn. dla wszystkich x, y, z  X,

1. x  x ,

2. x  y implikuje y  x,

3. jeśli x  y i y  z, to x  z.

Symbol relacji równoważności, jak to zwykle bywa w przypadku relacji binarnych, piszemy pomiędzy argumentami.

Przykładami relacji równoważności jest relacja równości, relacja równoległości prostych na płaszczyźnie, relacja podobieństwa trójkątów. Innym przykładem relacji równoważności jest relacja  zachodząca w zbiorze R^R wszystkich funkcji f : R → R określona następująco: dla dowolnych funkcji f, g ze zbioru R^R ,

f  g wttw f(x) = g(x) dla wszystkich x  R.

Na przykład, funkcje (x+1)*(x+1) i x² +2x +1 przyjmują te same wartości dla wszystkich argumentów, są więc w relacji . Relację tę oznacza się zwykle symbolem równości =.

Natomiast relacja r, określona w zbiorze R ^R warunkiem

f r g wttw f(x) = g(x) dla pewnego x  R,

nie jest relacją równoważności. Chociaż jest to relacja zwrotna i symetryczna, to nie jest to jednak relacja przechodnia. Weźmy na przykład trzy funkcje f(x) = x, g(x) = x², h(x) = 2^x. Mamy (f, g)  r , bo f(1) = g(1) =1, oraz (g, h)  r, bo g(2) = h(2)= 4, ale nie istnieje takie x R, dla którego 2 ^x = x (zawsze mamy x< 2 ^x ). Zwróćmy uwagę na różnicę między definicjami relacji  i relacji r. W pierwszym przypadku równość zachodziła dla wszystkich argumentów, natomiast w przypadku relacji r, wystarczy jeden punkt, w którym funkcje są zgodne. Taki warunek jest zbyt słaby by udowodnić przechodniość relacji r.

Przykład

(1) Niech będzie zbiór P programów napisanych w jakimś ustalonym języku programowania (np. w języku Java). Określimy relację binarną między programami następująco:

p₁  p₂ wttw dla dowolnych danych d, program p₁ kończy obliczenie dla d wtedy i tylko wtedy, gdy p₂ kończy obliczenie dla d, oraz, jeżeli dla tych samych danych oba programy mają obliczenie skończone, to wyniki tych programów są identyczne.

Taka relacja jest oczywiście zwrotna, symetryczna i przechodnia. Jest więc relacją równoważności. Zwróćmy uwagę, że dwa programy równoważne w sensie tej definicji mogą się bardzo istotnie różnić, np. kosztem realizowanego algorytmu.

(2) Niech G'= <V', E'> i G" = <V", E"> będą dwoma grafami i f funkcją wzajemnie jednoznacznie odwzorowującą zbiór wierzchołków V' na V", f : V'→ V", zachowującą relację sąsiedztwa, tzn. dla dowolnych v', u'  V',

(v', u')  E' wttw (f(v'), f(u')) E".

O przekształceniu f mówimy, że jest izomorfizmem odwzorowującym G' na G''.

Rozważmy teraz relację  zachodzącą między dwoma grafami wtedy i tylko wtedy, gdy istnieje izomorfizm odwzorowujący G' na G". O takich grafach mówimy, że są izomorficzne. Funkcja f(i)= 10*i ustala wzajemnie jednoznaczne przekształcenie pierwszego z grafów na drugi, zachowujące relację sąsiedztwa.

Relacja  rozważana w dowolnym zbiorze grafów, jest relacją równoważności. Rzeczywiście,

• jest relacją zwrotną, bo każdy graf jest izomorficzny z samym sobą (izomorfizm ustala funkcja identycznościowa f(x) = x),

• jest relacją symetryczną, bo jeśli f ustala izomorfizm między G' i G" , to f ^-1 ustala izomorfizm między G" i G',

• jest relacją przechodnią, bo jeśli f jest izomorfizmem odwzorowującym G na G', a g izomorfizmem odwzorowującym G' na G", to f  g jest izomorfizmem odwzorowującym G na G".

Każda funkcja całkowita f : X → Y wyznacza w zbiorze X relację równoważności  taką, że dla dowolnych x, x',

x  x' wttw f(x) = f(x').

Dowód

Zwrotność: Jeśli f jest funkcją całkowitą, to dla dowolnego x określona jest dokładnie jedna wartość f(x) i oczywiście f(x) = f(x).

Symetria: Ponieważ relacja = jest relacją symetryczną i wartości f(x) i f(x') są określone, to f(x) = f(x') implikuje f(x') = f(x). W konsekwencji x  x' wttw x'  x.

Przechodniość: Jeśli x  x' i x'  x'', to wartości funkcji f dla x, x' i x'' są takie same, a więc x  x''.

Przykład

1. Rozważmy funkcję f(x) = x mod 3 określoną dla liczb naturalnych i o wartościach naturalnych. Wartością funkcji f dla argumentu x jest reszta z dzielenia x przez 3. Funkcja f wyznacza relację równoważności  ,

n  m wttw f(n) = f(m)

taką, że wszystkie liczby podzielne przez 3 są w relacji z liczbą 0 (bo przy dzieleniu przez 3 dają resztę 0), wszystkie liczby, które przy dzieleniu przez 3 dają resztę 1 są w relacji  z liczbą 1, i wreszcie, wszystkie liczby naturalne, które przy dzieleniu przez 3 dają resztę 2, są w relacji z 2. Relacja  wyznaczyła z zbiorze N podział na trzy grupy liczb, w zależności od tego jaką te liczby dają resztę przy dzieleniu przez 3.

(2) Dany jest graf niezorientowany G = <V, E>, gdzie V jest zbiorem wierzchołków, a E zbiorem krawędzi grafu G. Zdefiniujemy w zbiorze V relację (relacja osiągalności),

x  y wttw istnieje w G droga łącząca wierzchołki x i y.

Tak zdefiniowana relacja jest relacją równoważności w zbiorze wierzchołków tego grafu. Mówimy o niej, że jest tranzytywnym (tzn. przechodnim) domknięciem relacji sąsiedztwa w grafie. Zwrotność i symetria relacji  są oczywiste. Sprawdźmy przechodniość. Jeżeli x  y i y  z, tzn. istnieje droga od x do y i istnieje droga od y do z. Jeżeli wykorzystamy najpierw drogę od x do y, a potem drogę od y do z, to znajdziemy tym samym drogę od x do z.

RELACJE PORZĄDKUJĄCE

 Definicja

Relację binarną  w zbiorze X nazywamy relacją porządku częściowego lub krótko relacją porządku wtedy i tylko wtedy, gdy jest ona zwrotna, antysymetryczna i przechodnia, tzn. dla wszystkich x, y, z  X,

1. x  x,

2. x  y i y  x implikuje x = y,

3. x  y i y  z implikuje x  z.

Relacje porządku zwykle będziemy oznaczać symbolem  . Zbiór, w którym określona jest relacja porządku nazywamy uporządkowanym, co zapisujemy <X,  >. Jeśli chcemy zaznaczyć, że relacja  zachodzi między elementami x i y, ale są one różne, to piszemy x  y, podobnie jak to czynimy w przypadku relacji  w zbiorze R.

ELEMENTY WYRÓŻNIONE ZBIORÓW UPORZĄDKOWANYCH

W zbiorze częściowo uporządkowanym <X,  > wyróżnimy pewne elementy ze względu na przyjęty porządek. Jeśli grupa osób ustawiła się w kolejkę przed okienkiem w banku, to kolejka ta wyznacza porządek obsługiwania tych osób. W tej grupie osoba pierwsza w kolejce jest w pewnym sensie wyróżniona, bo zostanie obsłużona jako pierwsza. Osoba stojąca na końcu kolejki, wyróżnia się tym, że będzie obsłużona jako ostatnia.

Definicja

Element x₀ nazywamy maksymalnym w zbiorze uporządkowanym <X,  > wtedy i tylko wtedy, gdy nie istnieje y  X, takie że x₀  y i x₀  y.

Element x₀ nazywamy minimalnym w zbiorze uporządkowanym <X,  > wtedy i tylko wtedy, gdy nie istnieje y  X takie, że x₀  y i y  x₀ .

Definicja

Element x₀ nazywamy najmniejszym w zbiorze uporządkowanym <X,  > wtedy i tylko wtedy, gdy dla każdego y  X, x₀  y.

Element x₀ nazywamy największym w zbiorze uporządkowanym <X,  > wtedy i tylko wtedy, gdy dla wszystkich y  X i y  x₀ .

PORZĄDEK LINIOWY I DOBRY PORZĄDEK Porządek częściowy, o którym była do tej pory mowa nie gwarantował, by można było porównywać dowolne elementy zbioru uporządkowanego. Ten punkt poświęcimy porządkom liniowym. Pozwalają one porównywać dowolne elementy zbioru, w którym są określone, tzn. dla dowolnych dwóch różnych elementów pozwolą ustalić, który z nich jest większy, a który mniejszy. Definicja Relację binarną  w zbiorze X nazywamy porządkiem liniowym wtedy i tylko wtedy, gdy  jest relacją porządku częściowego,  jest relacją spójną, tzn. dla dowolnych x, y  X, albo x  y albo y  x albo x = y. Niech < X,  > będzie zbiorem liniowo uporządkowanym, wtedy jeśli w X istnieje element maksymalny, to jest on elementem największym, jeśli w X istnieje element minimalny, to jest on elementem najmniejszym. Definicja Relacją binarną w X nazywamy dobrym porządkiem wtedy i tylko wtedy, gdy jest to porządek liniowy i dobrze ufundowany.

Przedmiotem badań rachunku zdań są "zdania": są to zdania w języku naturalnym, którym można przypisać wartość prawdy lub fałszu. Na tych zdaniach wykonujemy pewne operacje, które prowadzą do innych, bardziej złożonych zdań. W ten sposób powstaje rachunek, na kształt rachunków liczbowych, który dostarcza wzorców do naszych rozumowań i dowodów. Nie wszystkie wypowiedzi, zdania w języku polskim, są zdaniami w sensie rachunku zdań. Przykładem może być zdanie pytające : Jaka dziś pogoda? Nie sposób przypisać temu zdaniu wartości prawdy czy fałszu. Natomiast zdanie "Pada deszcz" jest już zdaniem, które możemy ocenić, czy jest, czy nie jest prawdziwe.  W języku naturalnym, z prostych zdań tworzymy bardziej złożone używając spójników. Również w rachunku zdań będziemy tworzyć zdania złożone za pomocą, tzw. spójników logicznych (nazywanych też funktorami zdaniotwórczymi) : nie, i, lub, implikuje, wtedy i tylko wtedy. Dla oznaczenia funktorów zdaniotwórczych zamiast tych słów będziemy stosowali odpowiednio znaki: negacji   koniunkcji  ,alternatywy  ,  implikacji → , równoważności  . Definicja Niech V będzie zbiorem zdań elementarnych (nazywać je będziemy zmiennymi zdaniowymi). Zbiór poprawnych wyrażeń, tzw.formuł rachunku zdań, jest to najmniejszy (w sensie inkluzji) zbiór wyrażeń zawierający V i taki, że jeśli p i q są zdaniami, to wyrażenia  p, (p  q), (p  q), (p → q), (p  q) są zdaniami. Przykład Często w matematyce, i nie tylko, używa się zwrotu "p jest warunkiem koniecznym i dostatecznym na to by zaszedł warunek q". Taki zwrot tłumaczy się na dwa zdania w rachunku zdań : ( p →  q) (p jest warunkiem koniecznym) (p → q) (p jest warunkiem dostatecznym) p jest warunkiem koniecznym dla q, bo gdyby p nie zachodziło, to nie zajdzie również q. p jest warunkiem dostatecznym, bo jeśli tylko zachodzi p, to zachodzi również q. Na przykład, rozważmy zdanie 'warunkiem koniecznym i dostatecznym na to by liczba dzieliła się przez 3, jest by suma jej cyfr była podzielna przez 3'. Zdanie to możemy zapisać w postaci dwóch warunków: jeśli suma cyfr danej liczby nie dzieli się przez 3, to liczba nie dzieli się przez 3 (warunekiem koniecznym na to by liczba dzieliła się przez 3 jest by suma jej cyfr dzieliła się przez 3), jeśli suma cyfr danej liczby dzieli się przez 3, to liczba też dzieli się przez 3 (warunkiem dostatecznym na to by liczba dzieliła się przez trzy jest by suma jej cyfr dzieliła się przez trzy). W dalszym ciągu wykładu, będziemy pomijać niektóre nawiasy w formułach. Zwykle, tak jak w arytmetyce, przyjmuje się priorytet operacji:  ,  ,  . W ten sposób  p  q  r  p oznacza formułę ((( p)  q)  ( r  p)).

RELACJE JEDNO I DWU CZŁONOWE

Niech X będzie dowolnym zbiorem. Każdy podzbiór A zbioru X wyznacza pewną własność W przysługującą jedynie elementom zbioru A zgodnie z definicją:

x ma własność W wttw x A

Zamiast 'x ma własność W' piszemy też krótko W(x). Na przykład, zbiór A= {2i+1: i N} jest podzbiorem zbioru liczb naturalnych, wyróżniającym się tym, że należą do niego tylko liczby nieparzyste. Zbiór A określa więc własność W= 'być liczbą nieparzystą'

W(x) wttw x jest liczbą nieparzystą

O własnościach wyznaczonych przez pewien podzbiór zbioru będziemy mówili, że są to relacje jednoczłonowe.

Rozważmy teraz sytuację, w której zbiór X jest sam produktem dwóch zbiorów, np.: X = Y  Z. Każdy podzbiór A takiego zbioru X składa się z par uporządkowanych (y, z) takich, że y Y i z Z. Wyznacza on pewną własność W dotyczącą par uporządkowanych

W(y, z) wttw (y, z)  A.

Inaczej mówiąc, W określa zależność między elementami zbiorów Y i Z. Na przykład, zbiór A= {(i, j)  N  N : i < j}, podzbiór produktu N N, wyznacza zależność W między liczbami naturalnymi polegającą na tym, że W(i, j) wttw drugi element pary (i, j) jest większy niż pierwszy element pary.

Definicja

Niech X i Y będą dwoma zbiorami. Dowolny podzbiór r produktu kartezjańskiego X  Y nazywamy relacją dwuczłonową (lub dwuargumentową lub binarną) w X  Y. Jeśli X=Y, to mówimy, że r jest relacją binarną w X. Jeśli (x, y)  r, to piszemy x r y i mówimy, że relacja r zachodzi między elementami x i y.

Przykład

1. Między liczbami naturalnymi 2 i 6, 2 i 8, 5 i 15, 6 i 24 i ogólnie liczbami postaci n i k* n , zachodzi zależność zwana relacją podzielności. Relacja podzielności, oznaczana przez |, jest relacją dwuczłonową przysługującą parom liczb naturalnych (x, y) wtedy i tylko wtedy, gdy x jest dzielnikiem y, tzn. x | y wttw wynik dzielenia y przez x jest liczbą naturalną.

2. Niech X będzie zbiorem pewnych produktów spożywczych, a Y zbiorem liczb rzeczywistych. W zbiorze par uporządkowanych X  Y możemy określić relację CENNIK: para (x, y)  CENNIK wttw cena produktu x wynosi y złotych.

3. Niech X będzie zbiorem miast w Polsce i Y =X. Określimy w X relację binarną r taką, że (x, y)  r wttw istnieje droga łącząca miasta x i y.

Definicja

Dziedziną relacji r X Y nazywamy zbiór D(r) tych x  X, dla których istnieje y Y, taki że (x,y) r, D(r) = {x X: istnieje y Y dla którego (x,y)  r }.

Przeciwdziedziną relacji r  X Y nazywamy zbiór D*(r) tych y Y, dla których istnieje x X, takie że (x,y)  r, D*(r) = {y Y: istnieje x X, dla którego (x,y)  r }.

Przykład

1. W zbiorze R, wszystkich liczb rzeczywistych, określimy relację binarną r: para (x,y)  r wttw x jest kwadratem liczby rzeczywistej. Dziedzinę tej relacji stanowi zbiór nieujemnych liczb rzeczywistych, przeciwdziedziną jest natomiast zbiór R.

2. Niech A będzie dowolnym zbiorem. Inkluzja, określona na podzbiorach zbioru A jest relacją dwuczłonową, której dziedziną i przeciwdziedziną jest zbiór potęgowy P(A).

Relacje dwuczłonowe określone w zbiorze R, można przedstawić geometrycznie jako zbiór punktów na płaszczyźnie, tak jak to było w przypadku podzbiorów produktu kartezjańskiego. Takie graficzne przedstawienie relacji nazywamy wykresem relacji.

Rozważmy jako przykład relację r1:

(x,y) r1 wttw y= x²

Wykresem tej relacji jest zbiór punktów spełniających warunek y = x², czyli parabola.. Dziedzinę relacji r stanowią wszystkie liczby rzeczywiste, a przeciwdziedzinę, zbiór liczb rzeczywistych nieujemnych.

Przykład

Niech X={1,2,3,4} i Y={5,6,7,8,9}. Wtedy relację r  X Y taką, że

(x, y)  r wttw x jest dzielnikiem y

można przedstawić jako macierz M(4 5). Macierz M ma 4 wiersze i 5 kolumn oznaczonych odpowiednio elementami zbiorów X i Y. Element znajdujący się na przecięciu itego wiersza i jtej kolumny M(i,j) wskazuje, czy para (i,j) należy, czy nie należy do relacji:

M(i, j) = '+' wttw (i, j)  r

W tym konkretnym przykładzie (2,6), (2,8), (4,8) itd. należą do relacji r, natomiast (2,7) i (2,9) nie należą do relacji r, i dlatego nie zostały zaznaczone odpowiadające tym parom pola.

Innym sposobem reprezentowania graficznego relacji jest graf relacji. Jest to rysunek składający się z węzłów, zaznaczonych na płaszczyźnie jako np.: punkty lub małe kółeczka, i krawędzi, zaznaczonych jako strzałki łączące węzły. Obowiązuje zasada:

węzły x i y są połączone strzałką biegnącą od x do y wttw (x, y)  r.

Ten rodzaj reprezentacji relacji dwuczłonowej można stosować w przypadku, gdy zbiory, w których określona jest relacja, są małe.

 

RODZAJE RELACJI

W tej części będziemy rozważali relacje binarne określone w zbiorze X. Oznacza to, że zarówno dziedzina jak i przeciwdziedzina relacji są podzbiorami tego samego zbioru X.

Definicja

Relację binarną r  X X nazywamy zwrotną wttw dla każdego x  X, para (x, x) należy do r.

Relację binarną r  X X nazywamy przeciwzwrotną wttw dla każdego x  X, para (x, x) nie należy do r .

r jest zwrotna wttw {(x, x) : x  X } r

r jest przeciwzwrotna wttw {(x, x) : x  X } r = 

Najbardziej charakterystycznym przykładem relacji zwrotnej jest relacja = w dowolnym zbiorze X. Składa się ona jedynie z par (x, x) dla wszystkich x  X. Przykładem relacji przeciwzwrotnej jest relacja < w zbiorze liczb rzeczywistych: oczywiście dla żadnej liczby rzeczywistej nie zachodzi x <x, czyli żadna para (x, x) do tej relacji nie należy.

Zastanówmy się jak może wyglądać macierz relacji zwrotnej. Ponieważ każdy x jest ze sobą w relacji, zatem wszystkie pozycje na głównej przekątnej macierzy muszą być zaznaczone. Poza tym mogą być zaznaczone jeszcze inne pozycje, nie wpłynie to na fakt, że tak określona relacja jest zwrotna. Równie prosto można rozpoznać relację zwrotną (określoną w skończonym zbiorze) patrząc na graf tej relacji: relacja jest zwrotna, jeśli przy każdym węźle jedna z krawędzi wychodzących z tego węzła jest skierowana do tego właśnie węzła (o takiej krawędzi mówimy, że jest to pętla).

W przypadku relacji przeciwzwrotnej, żadna z pozycji na głównej przekątnej macierzy relacji nie może być zaznaczona i żaden z węzłów grafu relacji nie ma pętli.

Przykład

Rozważmy relację podzielności w zbiorze {1,2,3,4,5,6,7,8,9}. Jest to relacja zwrotna, bo każda liczba jest swoim własnym dzielnikiem. 

Zauważmy, że relacja binarna może nie być ani zwrotna ani przeciwzwrotna: te pojęcia nie są przeciwstawne. 

• nie jest ona zwrotna, bo np. para (6,6) do niej nie należy,

• nie jest ona przeciwzwrotna, bo np. para (1,1) należy do tej relacji.

Definicja

Relację binarną r  X X nazywamy symetryczną wttw dla dowolnych x, y  X, jeśli para (x, y) należy do r , to para (y,x) też należy do r. Relację r nazwiemy przeciwsymetryczną (inaczej asymetryczną) wttw dla dowolnych x, y X z tego, że (x, y)  r wynika, że (y, x)  r.

Przykładem relacji symetrycznej jest relacja || równoległości prostych na płaszczyźnie:

l1 || l2 wttw prosta l1 jest równoległa do l2

Przykładem relacji przeciwsymetrycznej jest relacja < w zbiorze liczb rzeczywistych: jeśli x < y, to nie jest prawdą by y < x.

Zarówno relację symetryczną jak i przeciwsymetryczną bardzo łatwo rozpoznać, jeśli mamy jej macierz lub graf relacji. Macierz relacji symetrycznej jest symetryczna względem głównej przekątnej. Natomiast, graf relacji symetrycznej ma wszystkie krawędzie w obu kierunkach.

Zauważmy, że relacja może nie być ani symetryczna ani przeciwsymetryczna. Nie jest to relacja symetryczna, bp para (5,4) należy do relacji a para (4,5) nie należy. Nie jest to relacja przeciwsymetryczna, bo para (4,3) należy do relacji i para (3,4) też należy do relacji.

Definicja

Relację binarną r X X nazywamy antysymetryczną wttw dla dowolnych x, y  X, jeśli obie pary (x, y) i (y, x) należą do r, to x = y.

Przykładem relacji antysymetrycznej jest relacja  w zbiorze liczb rzeczywistych i relacja podzielności w zbiorze liczb naturalnych.

Definicja

Relację binarną r  X X nazywamy przechodnią wttw dla dowolnych x, y, z  X, jeśli (x,y)  r i (y,z)  r, to (x, z)  r.

Przykładem relacji przechodniej jest relacja < lub relacja  w zbiorze liczb rzeczywistych.

Przykład

Niech p będzie ustaloną liczbą całkowitą większą od 1. Zdefiniujemy relację  przystawania liczb modulo p następująco: dla dowolnych x, y całkowitych,

x  y (mod p) wttw (x - y) jest wielokrotnością p

Tak określona relacja

• jest zwrotna, bo (x-x)=0 = 0*p,

• jest symetryczna, bo jeśli ( x - y)= k* p dla pewnego k całkowitego, to (y - x)= (-k)*p,

• jest przechodnia, bo jeśli x  y (mod p) i y  z (mod p), to (x - y) =k* p i (y-z) = k'* p, a stąd (x - z) = (k + k')*p, czyli x  z (mod p).

GRAFY

Przedstawienie pojęcia grafu poprzedzimy krótką historyjką, którą zwykle opowiada się z tej okazji. Otóż szwajcarski matematyk Leonard Euler, przebywając w Królewcu, miał zwyczaj spacerować po mieście. Poszczególne części miasta, położonego na obu brzegach rzeki Pregoły i jej dwu wyspach, połączone były siedmioma mostami. Euler starał się znaleźć taką drogę, która pozwoliłaby mu przejść raz po każdym z mostów. Rozwiązanie problemu mostów królewieckich ukazało się w pracy Eulera opublikowanej w 1736 roku, dając początek nowej gałęzi matematyki - teorii grafów.

Grafy,  to proste figury geometryczne składające się z punktów i odcinków lub strzałek łączących niektóre z nich. Tak właśnie ilustrowaliśmy relacje. Matematyczna definicja grafu odsyła nas do pojęcia relacji.

Definicja

Grafem (lub grafem zorientowanym) nazywamy parę uporządkowaną G = <V, E>, gdzie V jest niepustym zbiorem, a E podzbiorem produktu V  V. Elementy zbioru V nazywamy węzłami lub wierzchołkami grafu, a elementy zbioru E nazywamy krawędziami grafu.

Każdy graf jednoznacznie wyznacza pewną relację binarną w zbiorze V,

(x, y)  r wttw (x, y)  E.

Odwrotnie, każda relacja binarna r w zbiorze X, wyznacza jednoznacznie graf, którego węzłami są elementy zbioru X, a krawędziami uporządkowane pary (x, x') należące do r. Zwykle będziemy rozważali grafy skończone, tzn. o skończonej liczbie wierzchołków.

Typowymi przykładami grafów są schematy różnego rodzaju sieci: np. sieci dróg, sieć wodociągowa, sieć telekomunikacyjna, itd. Kilka przykładów grafów zostało już przedstawionych jako ilustracje relacji binarnych.

Definicja

Niech G = <V, E> będzie grafem. Wierzchołki połączone krawędzią będziemy nazywać sąsiednimi lub incydentnymi. Drogą w grafie G nazywamy ciąg wierzchołków v₀,v₁,...v_n, taki, że kolejne wierzchołki v_i, v _i+1 są incydentne, tzn. (v_i , v_i+1 )  E dla każdego i=0,1,...,n-1. Długość drogi, to liczba jej krawędzi. Jeśli w tym ciągu v₀ = v_n, to powiemy, że droga jest zamknięta. Jeśli wszystkie wierzchołki drogi zamkniętej są różne z wyjątkiem pierwszego i ostatniego wierzchołka, to taką drogę nazywamy cyklem.

Gra Shannona

Dany jest niezorientowany, spójny graf G i dwa wyróżnione jego wierzchołki A i B. Dwaj gracze wykonują naprzemiennie ruchy. Gracz 1, w każdym ruchu umacnia (np. zaznaczając ją grubą kreską) jedną z istniejących krawędzi. Gracz 2, w każdym ruchu usuwa (skreśla) jedną z nie umocnionych krawędzi grafu.

Celem dla gracza 1 jest zbudowanie drogi łączącej wierzchołki A i B. Celem dla gracza 2 jest uniemożliwienie graczowi 1 zbudowania tej drogi. Wygrywa gracz, który pierwszy osiągnie swój cel. Miłej zabawy.

KONGURENCJE

Pewne relacje równoważności mają dodatkowo własność, że jeśli wykonuje się operacje na elementach równoważnych, to wyniki tych operacji są też równoważne. Takie relacje równoważności nazywa się kongruencjami. Najprostszym przykładem kongruencji jest relacja równości. Dokładniej o kongruencjach w dowolnych systemach algebraicznych będziemy mówili w wykładzie 10. Teraz poznamy pewne szczególne przykłady kongruencji.

Niech p > 0 i x mod p oznacza, jak zwykle, resztę, a x div p oznacza iloraz otrzymany z dzielenia całkowitego x przez p (tzn. x div p jest największą liczbą całkowitą mniejszą lub równą x/p, czyli x div p =  x/p ). Mamy więc dwie operacje dwuargumentowe mod i div,

mod : Z  N^>0 → N^>0 , div : Z  N^>0 → Z

spełniające w zbiorze liczb całkowitych zależność

p * (x div p) + x mod p = x. (*)

Zwróćmy uwagę, że reszta z dzielenia przez p jest liczbą naturalną mniejszą niż p. Zatem 5 mod 3 = 2, a (-5) mod 3 = 1, bo 3*(-2) +1 = -5.

Rozważmy relację równoważności określoną dla wszystkich liczb całkowitych x,y Z następująco:

x  y (mod p) wttw x mod p = y mod p.

Czytamy: x przystaje do y modulo p wtedy i tylko wtedy, gdy reszty z dzielenia przez p liczb x i y są takie same. Relację  nazywamy relacją kongruencji modulo p. Relacja przystawania jest przykładem relacji równoważności. Łatwo sprawdzić, że dla dowolnych x ,y Z,

x  x (mod p)

jeśli x  y (mod p), to y  x (mod p)

Jeśli x  y (mod p) i y  z (mod p), to x  z (mod p).

Własności zwrotności, symetrii i przechodniości są konsekwencją tych właśnie cech przysługujących relacji równości, użytej w definicji przystawania.

ZDANIA

Przedmiotem badań rachunku zdań są "zdania": są to zdania w języku naturalnym, którym można przypisać wartość prawdy lub fałszu. Na tych zdaniach wykonujemy pewne operacje, które prowadzą do innych, bardziej złożonych zdań. W ten sposób powstaje rachunek, na kształt rachunków liczbowych, który dostarcza wzorców do naszych rozumowań i dowodów.

Nie wszystkie wypowiedzi, zdania w języku polskim, są zdaniami w sensie rachunku zdań. Przykładem może być zdanie pytające : Jaka dziś pogoda? Nie sposób przypisać temu zdaniu wartości prawdy czy fałszu. Natomiast zdanie "Pada deszcz" jest już zdaniem, które możemy ocenić, czy jest, czy nie jest prawdziwe. 

W języku naturalnym, z prostych zdań tworzymy bardziej złożone używając spójników. Również w rachunku zdań będziemy tworzyć zdania złożone za pomocą, tzw. spójników logicznych (nazywanych też funktorami zdaniotwórczymi) : nie, i, lub, implikuje, wtedy i tylko wtedy. Dla oznaczenia funktorów zdaniotwórczych zamiast tych słów będziemy stosowali odpowiednio znaki: negacji   koniunkcji  ,alternatywy  ,  implikacji → , równoważności  .

Definicja

Niech V będzie zbiorem zdań elementarnych (nazywać je będziemy zmiennymi zdaniowymi). Zbiór poprawnych wyrażeń, tzw.formuł rachunku zdań, jest to najmniejszy (w sensie inkluzji) zbiór wyrażeń zawierający V i taki, że jeśli p i q są zdaniami, to wyrażenia  p, (p  q), (p  q), (p → q), (p  q) są zdaniami.

Przykład

Często w matematyce, i nie tylko, używa się zwrotu "p jest warunkiem koniecznym i dostatecznym na to by zaszedł warunek q". Taki zwrot tłumaczy się na dwa zdania w rachunku zdań :

( p →  q) (p jest warunkiem koniecznym)

(p → q) (p jest warunkiem dostatecznym)

p jest warunkiem koniecznym dla q, bo gdyby p nie zachodziło, to nie zajdzie również q. p jest warunkiem dostatecznym, bo jeśli tylko zachodzi p, to zachodzi również q. Na przykład, rozważmy zdanie 'warunkiem koniecznym i dostatecznym na to by liczba dzieliła się przez 3, jest by suma jej cyfr była podzielna przez 3'. Zdanie to możemy zapisać w postaci dwóch warunków:

• jeśli suma cyfr danej liczby nie dzieli się przez 3, to liczba nie dzieli się przez 3 (warunekiem koniecznym na to by liczba dzieliła się przez 3 jest by suma jej cyfr dzieliła się przez 3),

• jeśli suma cyfr danej liczby dzieli się przez 3, to liczba też dzieli się przez 3 (warunkiem dostatecznym na to by liczba dzieliła się przez trzy jest by suma jej cyfr dzieliła się przez trzy).

W dalszym ciągu wykładu, będziemy pomijać niektóre nawiasy w formułach. Zwykle, tak jak w arytmetyce, przyjmuje się priorytet operacji:  ,  ,  . W ten sposób  p  q  r  p oznacza formułę ((( p)  q)  ( r  p)).

TAUTOLOGIE

W rachunku zdań na szczególną uwagę zasługują zdania lub schematy zdań, utworzone ze zmiennych zdaniowych za pomocą funktorów zdaniotwórczych, których wartością jest zawsze prawda, tzn. te, które są spełnione przez wszystkie możliwe wartościowania zmiennych zdaniowych. Są to tautologie.

Definicja

Zdanie złożone, którego wartością jest prawda, niezależnie od wartości zmiennych zdaniowych w nim występujących, nazywamy tautologią lub prawem rachunku zdań. Zdanie złożone, którego wartością jest fałsz, niezależnie od wartości zmiennych zdaniowych w nim występujących, nazywamy zdaniem sprzecznym.

Jeżeli formuła zależna od zmiennych zdaniowych p₁,..., p_n jest tautologią, to wstawiając na miejsce zmiennych zdaniowych dowolne zdania otrzymamy zawsze zdanie prawdziwe. Co więcej, jeśli na miejsce zmiennych wstawimy dowolne schematy zdań (dowolne formuły), to otrzymany schemat będzie również tautologią.

FUNKCJE ZDANIOWE

Niech X będzie niepustym zbiorem.Funkcją zdaniową jednej zmiennej x, której zakresem zmienności jest przestrzeń X, nazywamy wyrażenie (x), w którym występuje zmienna x i które staje się zdaniem prawdziwym lub fałszywym, gdy w miejsce zmiennej x wstawimy dowolny obiekt ze zbioru X.

Przestrzeń X może sama być produktem kartezjańskim zbiorów X₁  ... X_n. Wtedy zmienna x przyjmuje jako wartości elementy tego produktu. Mówimy wówczas, że mamy do czynienia z funkcją zdaniową n-argumentową. Zwykle, dla uproszczenia zapisu, będziemy pisali (x), rozumiejąc, że x może być jedną zmienną lub wektorem zmiennych.

Przykład

1. (x) = (2x+x²) >0 dla x Z , jest funkcją zdaniową zależną od jednej zmiennej x przebiegającej liczby całkowite. Jeśli za x podstawimy konkretną wartość, np. 5, to wartością funkcji (x) jest prawda, ponieważ (10+25) jest liczbą dodatnią. Jeśli wartością x jest liczba -1, to wartością funkcji zdaniowej (x) jest w tym przypadku fałsz, bo (2*(-1) + (-1) ² ) < 0.

2. (x,y) = (x² + y² ) >0 dla (x,y) R², jest funkcją zdaniową zależną od dwóch zmiennych x i y przyjmujących wartości rzeczywiste. Jeśli na miejsce zmiennych wstawimy konkretne liczby, to otrzymamy zdanie, np." jeden do kwadratu dodać dwa do kwadratu jest liczbą dodatnią", albo "zero do kwadratu dodać zero do kwadratu jest większe od zera". W pierwszym przypadku otrzymane zdanie jest prawdziwe, a w drugim fałszywe.

KWANTYFIKATORY

Zwroty "dla każdego x", "istnieje takie x, że" nazywa się kwantyfikatorami. Pozwalają one budować nowe predykaty (nowe funkcje zdaniowe) z już istniejących. Niech (x) oznacza funkcję zdaniową, w której występuje tylko jedna zmienna x.

Zwroty "dla każdego x, (x)", "dla wszystkich x, (x)", "dla dowolnego x, (x)" wszystkie oznaczają zdanie prawdziwe, jeżeli niezależnie od tego jaka konkretna wartość a zostanie wstawiona na miejsce zmiennej w predykacie (x), otrzymane zdanie (a/x) będzie prawdziwe, tzn. wszystkie możliwe wartości zmiennej x spełniają funkcję zdaniową (x).

W logice i w matematyce przyjęło się oznaczać kwantyfikator "dla każdego x" symbolem odwróconego A, tzn. (x). Kwantyfikator ten nazywamy ogólnym lub uniwersalnym.

Przykładami funkcji zdaniowych z użyciem kwantyfikatora ogólnego są wyrażenia:

(x) (x<0), (x) ((x-3 = 0)  (x+1 < 4)) → (x< 1), ((x)(x> 0)  (y) ((y < 4) → (y < 1))).

Zwrot "istnieje takie x, że" (czasami używany w formie "dla pewnego x, ") nazywa się kwantyfikatorem szczegółowym lub egzystencjalnym. Dla oznaczenia tego kwantyfikatora używa się odwróconej litery E, tzn. piszemy (x). Rozumiemy, że funkcja zdaniowa (x) poprzedzona tym kwantyfikatorem tworzy zdanie prawdziwe, jeśli istnieje pewien obiekt a, który wstawiony w miejsce zmiennej w predykacie (x) spowoduje, że otrzymamy zdanie prawdziwe (a/x). Na przykład, wyrażenie (x-3 = 0) jest funkcją zdaniową określoną w zbiorze liczb rzeczywistych. Natomiast (x) (x-3 = 0) jest zdaniem prawdziwym, które stwierdza, że istnieje taka liczba rzeczywista a, dla której a-3 = 0.

Definicja

Zmienną x występującą w funkcjach zdaniowych (x) (x) lub (x) (x) nazywamy zmienną związaną, a dokładniej zmienną związaną przez kwantyfikator uniwersalny, w pierwszym przypadku, i zmienną związaną przez kwantyfikator egzystencjalny, w drugim przypadku. Funkcja zdaniowa (x) występująca bezpośrednio po symbolu kwantyfikatora jest zakresem tego kwantyfikatora, tzn. ten kwantyfikator dotyczy wszystkich wystąpień zmiennej x w funkcji zdaniowej .

Jeśli jakaś zmienna nie jest związana przez żaden kwantyfikator, to mówimy, że jest to zmienna wolna.

Definicja

Zdanie ( x) (x) jest prawdziwe w X (tzn. wartością tego zdania jest 1) wtedy i tylko wtedy, gdy każdy element zbioru X spełnia funkcję zdaniową (x) , tzn. gdy {x  X: (x)}= X.

Zdanie ( x) (x) jest prawdziwe w X (tzn. ma wartość 1) wtedy i tylko wtedy, gdy chociaż jeden element spełnia funkcję zdaniową (x), tzn. jeśli {x  X: (x)} .

Definicja

Niech (x, x₁, x₂, ..., x_n) będzie funkcją zdaniową o zmiennych wolnych x, x₁, x₂,..., x_n, których wartości należą odpowiednio do zbiorów X, X₁, X₂,..., X_n. Powiemy, że ciąg (a₁,a₂,..., a_n)  X₁ X₂  ... X_n spełnia funkcję zdaniową (x) (x, x₁,x₂,...x_n) wttw istnieje takie a  X, że (a/x, a₁/x₁,a₂/x₂,..., a_n/x_n) jest zdaniem prawdziwym.

Element (a₁, a₂, ..., a_n)  X₁ X₂ ... X_n spełnia funkcję zdaniową (x) (x, x₁,x₂,...x_n) wttw dla dowolnego a X, (a/x, a₁/x₁, a₂/x₂, ..., a_n/x_n) jest zdaniem prawdziwym.

 

Niech (x,y) będzie dowolną funkcją zdaniową określoną w przestrzeni X  Y. Wtedy

{x  X : (y) (x,y)} =  _{y Y}{x  X : (x,y)},

{x  X : (y) (x,y)} =  _yY{x  X : (x,y)}.

Dla dowolnych funkcji zdaniowych  i  zachodzą następujące równoważności

(1) ( (x))(x) (x) ((x) → (x)),

(2) ( (x))(x)  (x) ((x)  (x)).

TAUTOLOGIE RACHUNKU PERDYKATÓW

Definicja

Formułę  rachunku predykatów nazywamy tautologią (lub prawem rachunku funkcyjnego), jeżeli jej wartością jest prawda, niezależnie od wartości zmiennych oraz interpretacji symboli relacyjnych i funkcyjnych w niej występujących, tzn. dla każdej struktury STR i dla każdego wartościowania v zmiennych w tej strukturze mamy STR, v |= .

Jeśli  jest tautologią rachunku zdań, to podstawiając za zmienne zdaniowe występujące w  dowolne formuły rachunku funkcyjnego otrzymujemy tautologię rachunku predykatów.

Przykład

Formuła (p  p) jest tautologią rachunku zdań, zatem formuły (xy   xy), ((y)(x + y >z)   (y)(x + y >z)) są tautologiami rachunku predykatów. Natomiast formuła (xy  x>y) nie jest tautologią, bo relacja  nie musi być uzupełnieniem relacji >. Możemy wybrać jako interpretację relacji > zwykłą relację większości w strukturze liczb rzeczywistych, a jako interpretację relacji , np. relację =. W konsekwencji, przy tak wybranej interpretacji, nie zawsze wartością formuły (xy  x>y) jest prawda. Krótko mówiąc, formuła  (x y) jest w zbiorze liczb rzeczywistych równoważna formule (x > y), ale przy innej interpretacji symboli relacyjnych  i >, w innym zbiorze nie musi tak być.

Zamiast " jest tautologią rachunku funkcyjnego" piszemy krótko |= . Jeśli przez X_str oznaczymy zbiór wszystkich formuł prawdziwych w pewnej strukturze STR, to zbiór tautologii TAUT jest przecięciem teoriomnogościowym wszystkich zbiorów X_str.

Tautologie rachunku predykatów są schematami funkcji zdaniowych prawdziwych w dowolnym zbiorze. Prawdziwość tych wyrażeń nie wynika z przyjętego znaczenia dla symboli pozalogicznych, czy z przyjętego wartościowania zmiennych, a jest konsekwencją jedynie tylko struktury wyrażenia. Następujący lemat przedstawia kilka przykładów tautologii.

Dla dowolnych formuł (x) i (x) następujące formuły są tautologiami rachunku predykatów:

1. (x) (x) → (x (x)

2. ( (x) (x)) → ((x)   (x))

3. (x) (((x)  (x))  ((x) (x)  (x) (x))

4. (x)((x)  (x))  ((x) (x)  (x) (x))

WARIACJE

Zmodyfikujemy teraz nieco nasze pierwsze zadanie o rozmieszczaniu przedmiotów w pudełkach. Załóżmy, że w każdym pudełku może się zmieścić co najwyżej jeden obiekt. Na ile sposobów można, przy tym założeniu, rozmieścić n przedmiotów w m pudełkach?

Rozważmy hotel, w którym, znajduje się 10 jednoosobowych pokoi. Na ile sposobów możemy w tych pokojach umieścić 7 gości? W oczywisty sposób tłumaczymy ten problem na problem pudełek: pokoje to pudełka, a goście hotelowi, to obiekty, które chcemy w nich umieścić. Używając terminologii funkcji, pytamy, ile jest funkcji, ze zbioru gości w zbiór pokoi hotelowych takich, że żadni dwaj goście nie zostaną przypisani do tego samego pokoju. Pytamy zatem o funkcje różnowartościowe.

Ponieważ każda funkcja określona na skończonym zbiorze jest jednoznacznie wyznaczona przez ciąg swoich wartości, a każdy ciąg jest funkcją określoną na liczbach naturalnych, zatem zamiast mówić o funkcjach różnowartościowych możemy mówić o ciągach, których wyrazy nie powtarzają się.

Definicja

Ciąg n-elementowy, którego wyrazy nie powtarzają się, nazywa się n wyrazową wariacją bez powtórzeń.

Rozważmy n-elementowy zbiór X i m-elementowy zbiór Y i zastanówmy się, ile różnych funkcji całkowitych różnowartościowych f : X → Y możemy utworzyć. Oczywiście, jeśli n>m, to nie ma takich funkcji. Załóżmy więc, że n m.

Dla pierwszego elementu zbioru X, wartość funkcji możemy określić na jeden z m sposobów. Jeśli jednak przypiszemy temu elementowi wartość y₁ Y (tzn. umieścimy go w jednym z m pudełek), to następny element zbioru X może mieć przypisaną już tylko jedną z m-1 wartości, powiedzmy y₂ (pudełko y₁ jest już zajęte). Trzeciemu z kolei elementowi zbioru X możemy przyporządkować każdy z (m-2)-elementów (bo pudełka y₁ i y₂ są już zajęte) itd. Ogółem mamy więc m*(m-1)* (m-2)* ...(m-n+1) możliwych określeń funkcji różnowartościowych z X w Y.

Liczba n- wyrazowych wariacji bez powtórzeń w zbiorze m elementowym wynosi m*(m-1)* (m-2)* ...*(m-n+1).

PERMUTACJE Permutacje, to mówiąc nieformalnie różne ustawienia elementów danego zbioru skończonego, w których każdy element występuje dokładnie raz. Definicja Permutacją n-elementowego zbioru X nazywamy dowolny ciąg n-elementowy o różnych wyrazach należących do zbioru X. Inaczej mówiąc, permutacja, to funkcja różnowartościowa ze zbioru {1,...,n} w zbiór X. Liczba permutacji w dowolnym zbiorze n-elementowym wynosi n!, dla dowolnej liczby naturalnej n.

KOMBINACJE

Załóżmy, że w pewnej grze każdy gracz otrzymuje pięć kart i graczowi jest obojętne w jakiej kolejności je otrzyma, gdyż np. gra rozpoczyna się dopiero wtedy, gdy otrzyma wszystkie 5 kart. Jeśli tak, to 5-elementowe zestawy

D, K, 10, 9, W

K, 10, 9, W, D

są takie same.

Definicja

Liczbę k-elementowych podzbiorów zbioru n-elementowego oznaczamy przez
i nazywamy symbolem dwumianowym Newtona. k-elementowe podzbiory zbioru n-elementowego nazywamy k-elementowymi kombinacjami.

ZLICZANIE

W zbiorze n elementowym można określić 2 ^n*n relacji binarnych.

W zbiorze n-elementowym można określić 2^(n-1)n relacji zwrotnych.

W zbiorze n-elementowym można określić 2^(n+1)n/2 relacji symetrycznych.

Liczbą Stirlinga S(n,k) nazywamy liczbę podziałów zbioru n-elementowego na k części (bloków).

Liczba różnych relacji równoważności jakie możemy zdefiniować w zbiorze n-elementowym wynosi  _k=1,...,n S(n,k).

Liczba funkcji odwzorowujących X na Y gdzie |X| = n i |Y|= k, wynosi k!*S(n,k).

ZASADA WŁĄCZANIA I WYŁĄCZANIA

Niech X₁,..., X_n będą zbiorami skończonymi i niech X = X₁ ...  X_n. Jak zależy liczba elementów zbioru X od liczby elementów zbiorów X₁,...,X_n?

Rozważmy najpierw sytuację prostą, gdy n=2, tzn. X = X₁  X₂,

Przykład

1. X₁ = {1,2}, X₂ = {3,4,5}. Wtedy |X₁  X₂| = |{1,2,3,4,5}| = |X₁ | + |X₂| = 2 + 3 = 5.

2. X₁ = {1,2,3}, X₂ = { 2,3,4,5}. Wtedy |X₁  X₂| = |{1,2,3,4,5}| = 5  |X₁ | + |X₂| = 3 + 4 .

Jeśli zbiory X_1, X₂ są rozłączne, to |X| = |X₁| + |X₂|. Jeśli natomiast zbiory X_1, X₂ nie są rozłączne, to sumując po prostu |X₁| + |X₂|, elementy należące do przecięcia policzylibyśmy dwa razy.

Dla dowolnych zbiorów skończonych X_{1 ,} X₂ , |X₁  X₂| = |X₁ | + |X₂| - |X₁  X₂|.

Dla dowolnych zbiorów skończonych X_{1 ,} X_{2 ,} X_{3 ,}

|X₁  X₂  X₃| = |X₁ | + |X₂| + |X₃| - |X₁  X₂|- |X₁  X₃| -|X₂  X₃|+ |X₁  X₂  X₃|.

ZASADA SZUFLADKOWA

Jeśli skończony zbiór X podzielimy na n podzbiorów, to co najmniej jeden z podzbiorów będzie miał co najmniej |X|/n elementów.

Gdyby każdy z podzbiorów, na które podzielimy zbiór X miał mniej elementów niż |X|/n , to moc sumy tych zbiorów byłaby mniejsza niż |X|.

Przykład

Przypuśćmy, że pewne 9 osób O1, ..., O9, waży razem 810kg. Czy dowolna trójka tych osób może wsiąść do windy o udźwigu 250 kg?

Rozważmy tablicę:

O1 O2 O3 ... O7 O8 O9
O2 O3 O4 ... O8 O9 O1
O3 O4 O5 ... O9 O1 O2

Suma wag w każdym wierszu tablicy wynosi 810kg, czyli razem w trzech wierszach mamy 2430kg. Kolumny tej tablicy tworzą 9 różnych trójek. Na mocy zasady szufladkowej Dirichleta, przynajmniej w jednej kolumnie suma wag wynosi co najmniej 2430/9 = 270kg. Czyli istnieje (co najmniej jedna) taka trójka osób, które nie mogą razem wsiąść do windy.

Niech f będzie funkcją całkowitą określoną na zbiorze X, f : X→ Y oraz niech |X| > k*|Y|. Wtedy co najmniej dla jednego y, przeciwobraz f ^-1({y}) ma więcej niż k elementów.

---