Logika. Zadania z tematu 6.

  

Relacje równoważności. Relacje porządku

 

 
 

1

. W zbiorze słów 

{

,

,

,

,

}

X

kos kot kosz tak takt

=

 

wprowadzono relację R:  

xRy

⇔  x 

należy umieścić w słowniku przed y.  

Naszkicować diagram tej relacji. 

 
2. W zbiorze 

{ , , , }

X

a b c d

=

 

określono relacje R i S:  

{( , ), ( , ), ( , ), ( , ) }

R

a a

a b

c d

d b

=

, 

{( , ), ( , ), ( , ), ( , ) }

S

a a

b b

c d

d a

=

. 

Wyznaczyć 

1

,

,

\ ,

R

S R

S R S R

−

∪

∩

. 

 
3. W zbiorze 

{0, 1, 2, 3, 4}

X

=

 

określono relacje R , S i T wzorami:  

3

xRy

x

y

⇔ + = , 

2 (

)

xSy

x

y

⇔

−

,  

xTy

x

y

⇔ < . 

Jakie własności mają te relacje? 

 
4

. Która z podanych relacji jest relacją równoważności?  

W przypadku pozytywnej odpowiedzi opisać klasy abstrakcji tej relacji: 

a) W zbiorze prostych na płaszczyźnie  kRl ⇔  prosta k jest równoległa do prostej l. 

b) W zbiorze prostych na płaszczyźnie  kRl ⇔  prosta k jest prostopadła do prostej l. 
c) W zbiorze ludzi  xRy

⇔  x ma tego samego rodzica co y. 

d) W zbiorze ludzi 

xRy

⇔  x 

ma tę samą matkę co y. 

e) W zbiorze trójkątów na płaszczyźnie 

1

2

1

2

przystaje do

t Rt

t

t

⇔

. 

 
5. W zbiorze  X

N

N

= ×  

określono relacje R  i S wzorami:  

( , ) ( , )

m n R p q

m

q

n

p

⇔ + = + ,  ( , ) ( , )

m n S p q

mq

np

⇔

=

. 

Wykazać, że obie relacje są  relacjami równoważności. Opisać klasy abstrakcji tych relacji. 

 
6. W zbiorze 

{( , );

,

1, 2,3}

X

a b

a b

=

=

 

wprowadzamy relację (tzw. porządku leksykograficznego):  

( , )

( , )

(

)

L

a b

c d

a

c

a

c

b

d

≤

⇔ < ∨

= ∧ ≤

. 

Naszkicować diagram Hassego tej relacji. Wskazać elementy minimalne, maksymalne, największe 
i najmniejsze. 

 
7. W zbiorze X 

wprowadzona jest relacja porządku leksykograficznego. Naszkicować diagram  

Hassego relacji. Wskazać elementy minimalne, maksymalne, największe i najmniejsze. 
a) 

{(2,5), (6,1), (2,1), (0, 0)}

X

=

,   b) 

{(8,9), (1,1), (7,3), (3, 4), (8,5)}

X

=

. 

 
8. W zbiorze 

{( , );

,

1, 2,3}

X

a b

a b

=

=

 

wprowadzamy relację (tzw. porządku produktywnego):  

( , )

( , )

P

a b

c d

a

c

b

d

≤

⇔ ≤ ∧ ≤ . 

Naszkicować diagram Hassego tej relacji. Wskazać elementy minimalne, maksymalne, największe 
i najmniejsze. 

 
9. W zbiorze X 

wprowadzona jest relacja porządku produktywnego. Naszkicować diagram Hassego  

relacji. Wskazać elementy minimalne, maksymalne, największe i najmniejsze. 
a) 

{(2,5), (6,1), (2,1), (0, 0)}

X

=

,   b) 

{(8,9), (1,1), (7,3), (3, 4), (8,5)}

X

=

. 

 
 
 
 
 

 

2 

Odpowiedzi 

Zadanie 1. 
 
 
 
 
 
 
 
Zadanie 3. 
Relacja R jest przeciwzwrotna, symetryczna, nieprzechodnia, niespójna. 
Relacja S jest zwrotna, symetryczna, przechodnia, niespójna. 
Relacja T jest przeciwzwrotna, przeciwsymetryczna, przechodnia, niespójna. 
 
Zadanie 4. 
a)  Relacja R jest relacj

ą równoważności. Proste należące do tej samej klasy abstrakcji mają 

jednakowy kierunek. 

b)  Relacja R  

nie jest relacją równoważności. Nie jest zwrotna i nie jest przechodnia. 

c)  Relacja R 

nie jest relacją równoważności. Nie jest przechodnia. 

d)  Relacja R jest relac

ją równoważności. Osoby należące do tej samej klasy abstrakcji, to osoby 

mające tę samą matkę. 

e)  Relacja R 

jest relacją równoważności. Trójkąty należące do tej samej klasy abstrakcji, to trójkąty 

przystające. 

 
Zadanie 5. 
Dowolna klasa abstrakcji relacji R sk

łada się z par (m,n), które leżą na tej samej prostej równoległej do 

prostej y = x. 
Dowolna klasa abstrakcji relacji S 

składa się z par (m,n), które leżą na tej samej prostej przechodzącej 

przez początek układu współrzędnych. 
Zadanie 6. 

 

 

 

 

 

Zadanie 7. 

 

(3,3) 

 

(3,2) 

 

(3,1) 

 

(2,3) 

 

(2,2) 

 

(2,1) 

 

(1,3) 

 

(1,2) 

 

(1,1) 

 
Zadanie 8. 

 

 

 

 

 

 

 

 

 

 

 

Zadanie 9. 

kos 

kosz 

kot 

tak 

takt 

Zadanie 2. 

{( , ), ( , ), ( , ), ( , ), ( , ), ( , ) }

R

S

a a

a b

c d

d b

b b

d a

∪ =

 

{( , ), ( , )}

R

S

a a

c d

∩ =

 

\

{( , ), ( , ) }

R S

a b

d b

=

 

1

{( , ), ( , ), ( , ), ( , ) }

R

a a

b a

d c

b d

−

=

 

Element minimalny: para (1,1) 
Element najmniejszy: para (1,1) 
Element maksymalny: para (3,3) 

Element największy: para (3,3). 
 

Element minimalny: para (0,0) 
Element najmniejszy: para (0,0) 
Element maksymalny: para (6,1) 

Element największy: para (6,1).

 

(6,1) 

(2,5) 

(2,1) 

(0,0) 

(8,9) 

(8,5) 

(7,3) 

(3,4) 

(1,1) 

Element minimalny: para (1,1) 
Element najmniejszy: para (1,1) 
Element maksymalny: para (8,9 

Element największy: para (8,9).

 

(3,3 

(2,3) 

(2,1) 

(1,2) 

(1,3) 

(1,1) 

(2,2) 

(3,1) 

(3,2) 

Element minimalny: para (1,1) 
Element najmniejszy: para (1,1) 
Element maksymalny: para (3,3) 

Element największy: para (3,3). 
 

(2,5) 

(6,1) 

(2,1) 

(0,0) 

Element minimalny: para (0,0) 
Element najmniejszy: para (0,0) 
Elementy maksymalne: pary (6,1), (2,5) 

Element największy: brak

 

(3,4) 

(7,3) 

(1,1) 

(8,9) 

(8,5) 

Element minimalny: para (1,1) 
Element najmniejszy: para (1,1) 
Element maksymalny: para (8,9 

Element największy: para (8,9).