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).