Logika dla informatyków, Kolokwium nr 1, listopad 2012 - przykład testu

1/4

Nazwisko: ............................

Imię: ....................................

Zadanie

A

B

C

D

1

2

3

4

5

6

7

8

9

10

Razem:

Uwaga: Test wielokrotnego wyboru (liczba poprawnych odpowiedzi w wierszu: od 0 do 4).
Odpowiedzi poprawne zaznaczyć następującymi skreśleniem:

Logika dla informatyków, Kolokwium nr 1, listopad 2012 - przykład testu

2/4

1. Wskazać, które z równości nie zachodzą dla dowolnych par zbiorów:
A) (A



B)



B = B

B) A = (A



B)



(A \ B)

C) (B \ A)



A = A



B

D) A = (A



B)



(B \ A)

2. Niech A =

def

{{a}, {<a, b>}, {a, b}}, B =

def

{{<a, a>, <a, b>}, {a, {b}}, {a}}. Prawdą

jest, że:

A) A



B ≠ {<a, b>}

B) A



B = {{a}, {<a, a>, <a, b>}, {a, {b}}}

C) B\ A



(A \ B) \ B

D) A



A\ B

3. Niech card(A) = 3 oraz card(B) = 4. Prawdą jest, że dla każdej pary zbiorów A i B:
A) card(A



B) = 7 – card(A



B)

B) card(A



B) + card(A



B) = 7

C) card(A



B) = card(B\A) + card(A\B)

D) card(A



B) = 4 + card(A\B)

4. Niech A =

def

{a, b}. Prawdą jest, że w zbiorze A

2

można zdefiniować:

A) relację zwrotną
B) dokładnie trzy relacje nieprzechodnie
C) co najmniej dwie relacje symetryczne
D) dokładnie cztery relacje równoważności

5. Niech dana będzie relacja binarna reprezentowana grafem:

1

3

2

Prawdą jest, że podana relacja:
A) jest zwrotna,
B) jest przechodnia,
C) jest symetryczna,
D) posiada własność



x



y (<x,y>



R



<y,y>



R)



<y,x>



R.

6. Wskazać, co jest prawdą:

A)

Niech X={a,b,c,d}, R



X



X i R = {<a,a>, <b,b>, <a,b>, <c,c>, <d,d>}. Relacja R jest

relacją symetryczną.

B)

Niech X={a,b,c,d}, R



X



X i R = {<a,b>, <b,a>, <c,a>, <a,c>, <d,a>, <d,a>}.

Relacja R nie jest relacją przechodnią.

C)

Niech dany będzie zbiór liczb naturalnych Z={1,2,3,4,5}. Dla dowolnego x



Z oraz

dowolnej liczby naturalnej w



0 symbol mod(x,w) oznacza resztę z dzielenia x przez

w. Niech dana będzie relacja R



Z



Z taka, że para <x,y>



R wtedy i tylko wtedy, gdy

mod(x,2)=mod(y,2). Relacja R jest relacją równoważności i generuje nieskończoną

Logika dla informatyków, Kolokwium nr 1, listopad 2012 - przykład testu

3/4

liczbę klas abstrakcji.

D)

Niech C oznacza zbiór liczb całkowitych, R



C



C i niech x



C, y



C. Przyjmujemy,

że <x,y>



R wtedy i tylko wtedy, gdy x-y



C. Relacja R jest relacją równoważności i

generuje skończenie wiele klas abstrakcji?

7. Niech dana będzie tabela:

U

Cena

Rok

Stan

n

1

wysoka

1966

dobry

n

2

niska

1971

dobry

n

3

średnia

1971

dobry

n

4

wysoka

1968

dobry

w której:

- ni, i=1,2,3,4 są obiektami,
- Cena, Rok i Stan są tzw. atrybutami (cechami obiektów),
- w komórkach wpisane są wartości atrybutów wymienionych w kolumnie dla obiektów

wymienionych w wierszach.

Mówimy, że obiekty x i y są nierozróżnialne ze względu na atrybut a



{ Cena, Rok, Stan }

wtedy i tylko wtedy, gdy wartości atrybutu a dla obiektów x i y są równe. (Symbolicznie x



a

y).

Wskazać, co jest prawdziwe:

A) Nie zachodzi n

3



Stan

n

4

.

B) Relacja nierozróżnialności



Rok

obiektów jest relacją równoważności nad zbiorem U.

C) Iloczyn relacji nierozróżnialności



Cena

i



Stan

jest relacją zwrotną nad zbiorem U.

D) Iloczyn relacji nierozróżnialności



Rok

i



Cena

nie jest relacją symetryczną nad zbiorem U.

8. Dana jest następująca definicja spójności relacji R: Relacja R



X



X jest relacją spójną

wtedy i tylko wtedy, gdy dla każdej pary obiektów <x,y>



X



X jeżeli x



y, to zachodzi

warunek <x,y>



R



<y,x>



R, gdzie spójnik



definiowany jest w następujący sposób:

p q

p



q

0 0

0

0 1

1

1 0

1

1 1

1

Dane są cztery relacje binarne przedstawione poniższymi grafami G1-G4.

G1

1

3

4

2

G2

1

3

4

2

Logika dla informatyków, Kolokwium nr 1, listopad 2012 - przykład testu

4/4

G3

1

3

4

2

G4

1

3

4

2

Zaznaczyć stwierdzenia prawdziwe:

A) Relacja G1 jest spójna.
B) Relacja G2 nie jest spójna.
C) Relacja G3 jest spójna.
D) Relacja G4 nie jest spójna.

itd.