wstep121211.pdf

Zadanie1Udowodnij, »e funkcjaf:X!Yjest ró»nowarto±cio-

wa dokładnie wtedy, gdy dla dowolnych podzbiorówA;BX

zachodzi implikacja

A$B)f(A)$f(B):

Zadanie2Udowodnij, »e funkcjaf:X!Yjest ró»nowarto±cio-

wa wtedy i tylko wtedy, gdy dla dowolnego zbioruZi dowolnych

funkcjig 1 ;g 2 :Z!X,

je±lifg 1 =fg 2 ; tog 1 =g 2 :

Zadanie3Udowodnij, »e funkcjaf:X!Yjest „na” wtedy i

tylko wtedy, gdy dla dowolnego zbioruZi dowolnych funkcji

g 1 ;g 2 :Y!Z,

je±lig 1 f=g 2 f; tog 1 =g 2 :

Relacje

Relacj¡n-argumentow¡ nazywamy podzbiór%X 1 X 2 :::X n .

Je±li%XYjest relacj¡ dwuargumentow¡ (binarn¡), to za-

miast(x;y)2%piszemyx%y.

Relacj¡ binarn¡ okre±lon¡ w zbiorzeXnazywamy podzbiór%

XX.

Funkcjejakorelacje.Funkcj¡ nazywamy relacj¦ binarn¡%

XYtak¡, »e dla ka»dego elementux2Xjest jeden i tylko

jeden elementy2Yspełniaj¡cy warunek(x;y)2%:

8 x2X 9! y2Y (x;y)2%:

Rozwa»my relacj¦ binarn¡%okre±lon¡ w zbiorzeX:%XX.

Mówimy, »e relacja%jest:

–zwrotna,je±li 8 x2X x%x,

–przeciwzwrotna,je±li 8 x2X x%x,

–symetryczna,je±li 8 x;y2X x%y)y%x,

–asymetryczna(antysymetryczna), je±li 8 x;y2X x%y)y%x,

–słaboantysymetryczna,je±li 8 x;y2X x%y^y%x)x=y,

–spójna,je±li 8 x;y2X x%y_y%x_x=y,

–przechodnia,je±li 8 x;y;z2X x%y^y%z)x%z.

Rozwa»my nast¦puj¡ce relacje binarne w zbiorzeR:

„x<y”,

„x 6 y”,

„jxj=jyj”

oraz nast¦puj¡ce relacje binarne w zbiorzeN 1 :

„xiys¡ tej samej parzysto±ci”,

„y=x 2 ”,

„xjy”.