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.