Strona główna

Wykład 2 Zagadnienia podstawowe dotyczące metod formalnych w informatyce c d


Pobieranie 75.65 Kb.
Data17.06.2016
Rozmiar75.65 Kb.

Wykład 2

Zagadnienia podstawowe dotyczące metod formalnych w informatyce c.d.

2. Podstawowe pojęcia


    1. Teoria mnogości

Zbiór w pojęciu potocznym oznacza połączoną w jedność wielość przedmiotów lub całość utworzoną z wielu przedmiotów traktowanych jako części tej całości.

Jest to fundamentalne pojęcie matematyczne.



Metody definiowania zbioru:

  • przez wyliczenie: np. zbiór liczb naturalnych N={1,2,...},

zbiór liczb całkowitych C={..-2,-1,0,1,2,..}

zbiór elementów bez podanego znaczenia Z2={z1, z2, z3,...}

zbiór pusty  = {}


  • przez podanie własności elementów zbioru: Z3={x : x>=0  xN}

Z4=(x : x*x+x=0}={0,-1}

zbiór liczb rzeczywistych R={n/m: nC  mN }

Możliwe jest wystąpienie sprzeczności definicji (antynomia)

Przykład 2.1
Antynomia Russella: Definicja pewnej rodziny zbiorów jest postaci Z={x: xx}, gdzie Z jest rodziną zbiorów, w których elementami są zbiory x takie, że nie są swoimi elementami. Zakładamy, że istnieje takie Z, że ZZ. Jednak elementy tego zbioru mają własność, że ZZ, stąd wystąpiła sprzeczność. Z drugiej strony każdy element zbioru spełniający ZZ należy do zbioru Z, czyli powinno być prawdziwe ZZ, co jest również sprzecznością.

  • przez podanie sposobu wyznaczenia elementów np. Z5={xi: x1=1, xi= xi-1xi}

  • przy definiowaniu zbiorów nie są istotne: kolejność wyliczenia elementów albo ich powtórzenia.

Przykład 2.2

Przykłady zbiorów występujących w języku C, C++:

int ={-N1, ,0,..,N2}, gdzie N1, N2 są liczbami naturalnymi-reprezentacja stałoprzecinkowa

float={-N3*1,...,0,..., N4*2}, gdzie N3, N4 są ułamkami stałoprzecinkowymi (mantysa),B stałą liczbą całkowitą oraz E1, E2 liczbami całkowitymi ze znakiem stałoprzecinkowymi (cecha)


ZbiórNazw={x1 x2 ...xn: x1 jest literą, xk dla k=2,3,...,n jest literą lub cyfrą}

np. {clrscr, printf, x1}


Podstawowe definicje:


  • należenie elementu x do zbioru A: xA np. 1 {1,2,3}

  • nie należenie elementu x do zbioru A: xA np. 4{1,2,3}

  • podzbiór: A jest podzbiorem B, czyli AB, wtedy i tylko wtedy, gdy xA i xB. Symbol  jest symbolem zawierania. Symbol inkluzji  oznacza, że AB i jednocześnie przynajmniej jeden element ze zbioru B nie należy do A

np. {1,2}{1,2,3}, zbiór prostokątów zawiera się w zbiorze czworokątów

  • identyczność zbiorów: A=B, wtedy i tylko wtedy, gdy oba zbiory mają dokładnie te same elementy, czyli AB i BA.

np. {-1, 1,2}={2,-1,1}={-1,2,1,2}, zbiór trójkątów równobocznych jest równy zbiorowi trójkątów równokątnych

  • iloczyn/przekrój zbiorów: AB={x: xA  xB} np. {1,2,3}{2,3,4}={2,3}

  • zbiory rozłączne: AB={}= np. {1,2,3}{4,5}=

  • suma zbiorów: AB={x: xA  xB} np. {1,2,3}{2,3,4}={1,2,3,4}

  • różnica zbiorów: A\B={x: xA  xB} np. {1,2,3}\{2,3,4}={1}

  • uogólniona iloczyn/przekrój zbiorów:  i I Xi = {x: iI xXi }

  • uogólniona suma zbiorów:  i I Xi = {x: iI xXi }

  • uniwersum zbiorów: zbiory są najczęściej definiowane jako podzbiór pewnego zadanego zbioru Z pełnego zwanego uniwersum

Rodziną zbiorów X nazywamy zbiór, którego elementami są podzbiory zbioru Z.

  • dopełnienie zbioru: Z-A jest dopełnieniem zbioru AZ, oznaczamy go jako –A, czyli -A={x: xZ  AZ  xA} np. Z={1,2,3,4,5}, A={1,2,3} i –A={4,5}

  • liczność zbioru: Dla zbioru skończonego X card(X) oznacza liczbę jego różnych elementów czyli moc zbioru X. Dla zbiorów nieskończonych można jedynie porównywać zbiory, czy są równoliczne.

  • zbiór potęgowy: Zbiór wszystkich podzbiorów zbioru X oznacza się symbolem 2X i nazywa się go zbiorem potęgowym zbioru X, czyli 2X ={x: xX}

Dla dowolnego skończonego zbioru X zachodzi card(2X) = 2card(X)

np. X={1,2,3}, 2X ={, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}



  • zbiory równoliczne:

Zbiory A i B skończone są równoliczne, gdy card(A)=card(B)

Zbiory X i Y (nie muszą być skończone) są równoliczne, jeżeli istnieje wzajemnie jednoznaczne odwzorowanie zbioru X na zbiór Y.

np. zbiór liczb parzystych jest równoliczny ze zbiorem liczb naturalnych,

zbiór wszystkich liczb rzeczywistych jest równoliczny ze zbiorem liczb

{x: -1 


  • zbiory przeliczalne:

Każdy zbiór o mocy równej ze zbiorem liczb naturalnych N jest zbiorem przeliczalnym.

(1) Każdy zbiór X jest przeliczalny wtedy i tylko wtedy, gdy istnieje ciąg nieskończony (xn) taki, że X={ xn:nN} i n  n’  xn  xn.

(2) Podzbiór zbioru przeliczalnego jest pusty skończony lub przeliczalny.

np. zbiór liczb parzystych jest przeliczalny.

(3) Jeśli X jest zbiorem przeliczalnym, to zbiór wszystkich skończonych ciągów o wyrazach ze zbioru jest także przeliczalny.


  • zbiory nieprzeliczalne: istnieją zbiory nieprzeliczalne czyli takie, które nie są ani skończone, ani przeliczalne.

np. zbiór potęgowy zbioru liczb naturalnych, zbiór wszystkich liczb rzeczywistych lub liczb rzeczywistych z przedziału (0,1), zbiór liczb niewymiernych są zbiorami nieprzeliczalnymi, gdyż można udowodnić, że nie spełniają twierdzenia (1).

  • rodzaje nieskończoności: nieskończoność liczb naturalnych zwana przeliczalnością i nieskończoność zwana nieprzeliczalnością. Nieprzeliczalność zbioru potęgowego liczb naturalnych jest nieskończonością zwaną continuum.

Aksjomatyczny system teorii mnogości Zermelo_Fraenkla-Skolema

Opiera się na dwóch pojęciach pierwotnych: Z(x)- x jest zbiorem i xy- x jest elementem y. System ten uwalnia teorię mnogości od antynomii Russella.

[A1] – aksjomat ekstensjonalności

x (xX  xY)  X=Y

Dwa zbiory są równe, gdy mają te same elementy.

[A2] – aksjomat tworzenia par

X z [zX  (z=x  z=y)]

[A3] - aksjomat podzbiorów

Y X x[xX  xY  L(x)]

[A4] – aksjomat sumy

X S x [xS  Y (xY  YX)]

Niech X będzie rodziną zbiorów tj. zbiorem, którego elementy są zbiorami. Dla każdej takiej rodziny istnieje zbiór S, którego elementami są dokładnie te obiekty, które są elementami zbiorów należących do X.

[A5] – aksjomat zbioru potęgowego

X Y S [SY  S  X]

Dla każdego zbioru X istnieje rodzina zbiorów Y, której elementami są wszystkie podzbiory X. Rodzinę tę nazywamy zbiorem potęgowym i oznaczamy jako 2X.

[A6] – aksjomat ufundowania

X [X  x (xX y(yx  yX)]

Głosi on, że w każdym niepustym zbiorze X istnieje taki element x, którego z kolei żaden element y nie jest elementem owego zbioru X.

[A7] – aksjomat nieskończoności

X [X  Y(YX  Y  {Y}  X)]

Jest to jedno z wielu możliwych ujęć. Glosi on, że istnieje zbiór, którego elementem jest zbiór pusty i który się tym odznacza, że wraz z każdym elementem zawiera zbiór złożony z tego właśnie elementu i zbioru, którego ten element jest jedynym elementem. Jest więc zbiór {, {}, {, {}}, {, {},{, {}}},...}

[A8] – aksjomat zastępowania

x y z X (xXL(x,y)L(y,z)(y=z) Y y (yY  x (xXL(x,y))

Dla każdego elementu ze zbioru X istnieje dokładnie jedno y takie, że spełniony jest predykat L(x,y). Wtedy dla każdego zbioru X istnieje zbiór Y, do którego należą wszystkie i tylko te elementy y, które przy pewnym x ze zbioru X spełniają predykat L.

[A9] – aksjomat wyboru

S[X Y ([XS  YS  X  Y   (XX  XY = )])

 W X (XS  x y (yWX  y=x))]

Stwierdza on, że dla każdego zbioru S niepustych i rozłącznych zbiorów X i Y istnieje zbiór zawierający dokładnie po jednym elemencie z każdego z tych zbiorów. Poprzednik tego zdania głosi, że S jest zbiorem niepustych i wzajemnie rozłącznych zbiorów, zaś następnik głosi, że istnieje zbiór W zawierający po jednym elemencie z każdego ze zbiorów należących do S.


Do prostych zastosowań wystarcza oprzeć się na aksjomatach [A1],[A2],[A3],[A4],[A5] i ewentualnie [A9]. Aksjomaty A[6],[A7],[A8],[A9] są potrzebne dla potrzeb własnych teorii mnogości. Aksjomaty [A1] do [A9] można zredukować do układu [A1],[A4],[A5],[A6,[A7],[A8],[A9].

    1. Teoria relacji

Pary uporządkowane: jeżeli x oraz y są dwoma elementami, niekoniecznie różnymi, to (x, y) albo jest parą uporządkowaną, zaś x i y są składnikami tej pary.

Parą nieuporządkowaną jest natomiast zbior 2-elementowy {x, y}={y, x}.

Dwie pary oraz identyczne czyli =, wtedy i tylko wtedy, gdy x=u i y=v.



trójka uporządkowana: => itp.

Przykład 2.3

Niech nazwa  ZbiórNazw, wartość_ASCIIstring, wartość_intint

dwie pary proste: ,

czwórka złożona: ,

nazwa,<,,>>

np. , data_ważności, <,,>>



Produkt kartezjański (iloczyn kartezjański) zbiorów:

Iloczynem kartezjańskim zbiorów X i Y, oznaczony jako XY, nazywamy zbiór wszystkich par uporządkowanych, których pierwsze elementy należą do zbioru X, a drugie zaś- do zbioru Y: X  Y= { : xX  yY}

np. X={1,2},Y={2,4}, X  Y= {<1,2>,<1,4>,<2,2>,<2,4>}



Kwadrat zbioru kartezjańskiego: X  X = X2.

np. X={1,2}, X  X={<1,1>,<1,2>,<2,1>,<2,2>}



N-krotny produkt kartezjański zbiorów X1, ..., Xn jest zbiorem n-krotek:

X1  ...  Xn = {1,..., xn>: xk Xk  k {1,...,n}}

X  ...  X = Xn dla X występującego n razy.

Relacją nazywamy wszelki związek zachodzący miedzy dwoma lub więcej przedmiotami, np. rówieśnictwo, przyjaźń, posiadanie większego ciężaru między przedmiotami, podzielność między liczbami, podobieństwo między figurami.
Relacje są wyrażane przez predykaty dwu- lub więcej argumentowe w tym samym sensie, w jakim predykaty jednoargumentowe wyrażają własności indywidualnych przedmiotów. Liczba argumentów w predykacie wynika z liczby członów relacji.

np. dwuczłonowy predykat „jest ojcem” wyraża relację między ojcem i synem

trójargumentowy predykat „...leży między...a...” wyraża relacje trójczłonową między punktami prostej
Teoria relacji jest konstruowana w ramach teorii mnogości. Stąd relacje dwuczłonowe jako własności par uporządkowanych przedmiotów, między którymi zachodzą, są utożsamiane ze zbiorami takich par, odpowiednio relacje trójczłonowe ze zbiorami trójek itd.

np. relacja podzielności ograniczona do zbioru liczb naturalnych wiekszych od 1, a mniejszych od 7 jest zbiorem: {<2,2>, <3,3>, <4,4>, <5,5>, <6,6>, <4,2>, <6,2>, <6,3>}



Konsekwencja tego podejścia: Wszelkie dwa zbiory, które mają identyczne elementy, są identyczne. Stąd dowolne dwie relacje zachodzące między tymi samymi przedmiotami są w związku z tym tą samą relacją!

Trudno to zaakceptować przy potocznym pojęciu relacji jako własności, gdzie np. relacja bycia przyjacielem jest inną relacją niż relacja rówieśnictwa, mimo że zachodzi między tymi samymi osobami.


Relacja binarna R określona na zbiorach X i Y jest podzbiorem produktu kartezjańskiego XY, czyli R XY. Jeżeli X=Y, to R jest relacją binarną na X.


Symboliczne wyrażanie relacji: jeśli jest elementem relacji to mamy: R, xRy, R(x,y), R: XY (jako odwzorowanie)

Jeżeli R1, R2  XY, to równość relacji R1= R2 jest równością odpowiednich zbiorów par R1= R2.

Jeżeli relacja R jest relacją binarną na XY, to jej dziedziną jest zbiór:

dom(R)= {x X: yY R }

natomiast jej przeciwdziedziną jest zbiór:

ran(R)= {y Y: xX R }

Sumę dziedziny i przeciwdziedziny nazywamy polem relacji.

np. dziedziną relacji bycia mężem jest zbiór wszystkich żonatych mężczyzn, przeciwdziedziną zbiór wszystkich mężatek, polem zbiór wszystkich osób pozostających w związku małżeńskim.



Reprezentowanie relacji:

  1. w


    postaci tabeli b) zbiór punktów na płaszczyźnie




x1

x2

...

xn

x1

+

+




-

x2

-

-




+

...




-







xn

-

-




-



Rachunek relacji

Na relacjach jako zbiorach par, trójek itd. obowiązują te działania, które obowiązują na zbiorach, czyli: dodawanie, mnożenie, odejmowanie i dopełnianie.

Działania określone tylko dla relacji:


np. konwersem relacji mniejszości jest relacja większości, konwersem relacji zwierzchnictwa jest relacja bycia podwładnym

  • iloczynem względnym relacji (złożeniem relacyjnym, superpozycją) relacji R i S nazywamy relację, która zachodzi między x i y zawsze i tylko, gdy istnieje z takie, że między x i z zachodzi relacja R, zaś między z i y zachodzi relacja S. Oznaczamy ją symbolem RS={: zX ( R  S)}


Własności relacji

  • relacja R jest zwrotna w zbiorze X  xX (R)

równość w zbiorze liczb, rówieśnictwo w zbiorze ludzi

  • relacja R jest przeciwzwrotna w zbiorze X  xX (R)

mniejszość w zbiorze liczb, starszeństwo w zbiorze ludzi

  • relacja R jest symetryczna w zbiorze X  x,yX(RR)

podobieństwo w zbiorze trójkątów, pokrewieństwo w zbiorze ludzi

  • relacja R jest asymetryczna w zbiorze Xx,yX(RR)

mniejszość w zbiorze liczb, ojcowstwo w zbiorze ludzi

  • relacja R jest antysymetryczna w Xx,yX(xyRR)

nie większość(), relacja bycia podzielnikiem w zbiorze liczb

  • relacja R jest przechodnia w X x,y,zX(RR R)

podzielność w zbiorze liczb, rówieśnictwo w zbiorze ludzi

  • relacja R jest spójna w Xx,yX (xy  R  R)

mniejszość w zbiorze liczb <, starszeństwo w zbiorze osób, w których nie ma rówieśników

Ważniejsze rodzaje relacji


  • relacja identyczności IX = { : xX}

  • relacja pełna {: xX  yY}

  • relacja równoważności R: Relacja, która jest zwrotna, symetryczna i przechodnia w zbiorze X jest nazywana równoważnością (równością) w X.

np. rówieśnictwo w zbiorze ludzi, podobieństwo w zbiorze figur geometrycznych

Pojęcie relacji równoważności jest ściśle związane z pojęciem podziału: każda relacja równoważności R w danym zbiorze wyznacza podział tego zbioru na tzw. klasy abstrakcji, i odwrotnie.



Klasą abstrakcji relacji równoważnościowej R wyznaczoną przez elementy y zbioru X nazywamy zbiór tych elementów zbioru X, które pozostają w relacji R do y i oznaczamy ją symbolem [y]R, czyli

x[y]R R lub [y]R ={x: xX  R}

np. rówieśnictwo w gronie ludzi wyznacza podział na grupy rówieśnicze oraz

podział na grupy rówieśnicze jest rodziną klas abstrakcji relacji rówieśnictwa

Zbiór klas abstrakcji posiada własności:


  1. yX [y]=X

  2. R [x]=[y]

  3. [x] [y]  [x] [y]=

Oznacza to, że jeżeli na zbiorze X zdefiniowano relację równoważności R, to wyznacza ona podział tego zbioru na rozłączne podzbiory (klasy abstrakcji).

Zbiór, którego elementami są wszystkie klasy abstrakcji nazywamy zbiorem ilorazowym zbioru X względem relacji R i oznaczamy X/R.



  • relacja częściowo porządkująca: Relację, która jest zwrotna, przechodnia i antysymetryczna w zbiorze X, nazywamy relacją porządkującą zbiór.

np. relacja  ,  , relacja starszeństwa

  • relacja porządkująca jest relacją asymetryczną, przechodnią i spójną (porządek liniowy). np. > , < , relacja starszeństwa, gdzie brak rówieśników

    1. Relacje jednoznaczne czyli funkcje

Relację f nazywamy relacją jednoznaczną lub po prostu funkcją, jeśli każdemu przedmiotowi x odpowiada co najwyżej jeden przedmiot y taki, że f, czyli:

relacja f jest jednoznaczna w zbiorze X  x,y,zX(ff  y=z)

Niech X i Y będą dwoma dowolnymi zbiorami. Funkcją lub odwzorowaniem z X w Y nazywamy każdą relację binarną f  XY, która ma następującą własność: dla każdego przedmiotu xX istnieje co najwyżej jeden element yY, taki że f.

Piszemy najczęściej w przypadku funkcji:

(1) f(x)=y,

gdzie x nazywany argumentem funkcji, y natomiast wartością funkcji f dla argumentu x.

W celu podkreślenia, że funkcja jest relacją odwzorowującą, piszemy:

(2) f: X  Y,

Notacja (1) oznacza pewien element zbioru Y, natomiast notacja (2) oznacza relację f, czyli zbiór par f.

Zbiór X jest dziedziną funkcji dom(f), zaś zbiór Y jest przeciwdziedziną funkcji ran(f) czyli zbiorem jej wartości.



Przykład 2.4

X={Agata, Anna}, Y={Piotr, Mateusz} jest_żoną: XY

jest żoną(Agata)=Piotr, jest_żoną(Anna)=Mateusz

Jeśli f: XY i UX, to możemy zdefiniować funkcję odwzorowującą zbiór U w zbiór Y, rozważając tylko te wartości f, które odnoszą się do zbioru U. Mówimy wtedy, że funkcja f jest zredukowana do zbioru U i oznaczamy:

fU: U  Y, stąd fU(u)= f(u)Y.

Jeżeli istnieje taki zbiór X\dom(f), który nie jest pusty, wówczas istnieją pewne elementy w zbiorze X, którym nie przypisano żadnych elementów w zbiorze Y. Wówczas funkcja f jest funkcją częściową, nieokreśloną dla elementów ze zbioru X\dom(f).

W przypadku, gdy funkcja ma n argumentów (n0), wówczas dziedziną tej funkcji jest odpowiedni produkt kartezjański i piszemy:

f: X1 ... Xn Y

Wartością y tej funkcji n-argumentowej jest f(x1,...,xn)=y, czyli 1,...,xn>f

Przykład 2.5

Bool ={0,1}, and: (Bool  Bool)  Bool, f={f(x): x{1,1}f(x)=1  f(x)=0}

W przypadku, gdy n=0 funkcję f nazywamy stałą:

f: Y


Własności funkcji:

  • funkcję f: X  Y nazywamy różnowartościową (injekcją), jeśli różnym elementom zbioru X przypisane są różne elementy zbioru Y, czyli

X  x,y,zX(ff  x=z) lub

f jest różnowartościowa  x,zX( f(x)=f(z)  x=z)

Funkcjami różnowartościowymi są funkcje: silnia, jest_żoną, nie jast nią and.


  • funkcję f: X  Y nazywamy funkcją ”na” (surjekcją), jeśli każdemu elementowi zbioru Y odpowiada co najmniej jeden element zbioru X.

  • funkcja jest wzajemnie jednoznaczna (bijekcja), jeżeli jest różnowartościowa i „na”.

Niech X i Y są zbiorami:



  1. Jeśli f: X  Y jest funkcją różnowartościową, to możemy zdefiniować funkcję „na” g taką, że dla wszystkich xX, g(f(x))=x. Tak więc funkcja g odwraca działanie funkcji f.

  2. Jeśli g: Y  X jest funkcją „na”, to możemy zdefiniować taką funkcję różnowartościową f, że dla wszystkich xX, g(f(x))=x

Stąd funkcja g jest funkcją odwrotną, jeśli dla dowolnego xX i yY zachodzi:

g(f(x))=x i f(g(y))=y.

Funkcje jako relacje jednoznaczne można składać.

Dane są dwie funkcje: f: X  Y oraz g: Y  Z. Złożeniem (iloczynem względnym lub superpozycją) tych funkcji jest funkcja fg: X  Z, której wartość jest równa (fg)(x) = g(f(x)).

Podzbiór W produktu XY, zwany wykresem funkcji f: X  Y można określić następująco:


(2,2)











(0,3)


(0,4)


(0,5)

W = {:  XY  f(x)=y}
P
X=Y=N, funkcja silnia  f: NN

silnia(n)=1*2*3*...*n.

W={<1,1>, <2,2>, <3,6>,...}

rzykład 2.6







(1,1)


(3,6)


(0,6)


(0,2)


(0,1)


(1,0)


(2,0)


(3,0)


silnia




Zofia Kruczkiewicz, Języki programowania 1, materiały do wykładu 2




©snauka.pl 2016
wyślij wiadomość