Wrocław, 24 października 2012
Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków
Zadania – lista 3
1. Sprawdzić, czy przechodnie są wszystkie relacje binarne R
X
2
określone na zbiorze X spełnia-
jącym warunek:
a) card(X) = 1
b) card(X) = 2
c) card(X) = 3
2. Niech f będzie funkcją przekształcającą zbiór R wszystkich liczb rzeczywistych w rodzinę
wszystkich podzbiorów zbioru R (tj. zbiór 2
R
) określoną następującym wzorem:
f(t) = {x | x
R i x
t
} dla każdego t
R.
Oblicz f(-1), f(0), f(t
2
+1).
3. Niech f: R
R będzie funkcją określoną wzorem f(x) = -2x+4. Znaleźć funkcję odwrotną do tej
funkcji.
4. Ile jest funkcji ze zbioru {1,2,3} na siebie i takich, że f(1)=3? Uogólnić ten wynik dla zbioru
{1,2,..,n} i takich funkcji f, że f(x
i
)=y
i
, i=1,2,...,k; k
n, x
i
,y
i
{1,2.,,.n}.
5. Udowodnić, że jeśli A jest zbiorem k-elementowym zaś B jest zbiorem n-elementowym, k
n, to
istnieje n(n-1)...(n-k+1) funkcji różnowartościowych z A w B.
6. Udowodnić, że w zbiorze [0,2] (jest to zbiór wszystkich liczb rzeczywistych nie mniejszych niż 0
i niewiększych niż 2) nie istnieje taka relacja równoważności, której klasami abstrakcji byłyby
zbiory: [0,1], [1,4/3] i [1,2].
7. Funkcja f jest zgodna z relacją R wtt f
R. Dla X =
df
{a, b, c, d} niech będzie zdefiniowana
zdefiniowana relacja binarna na X:
R = {<a,b>, <a,d>, <c,c>, <b,b>, <b,d>, <c,c>, <d,b>, <c,d>, <d,c>, <d,a>, <d,d>}.
Zdefiniować wszystkie funkcje f zgodne z relacją R takie, że:
a) dom(f) = dom(R)
b) ran(f) = ran(R)
Które spośród tych funkcji mają funkcje odwrotne?
8. Jakie sygnatury mają funkcje reprezentujące:
a) operację całki nieoznaczonej,
b) całki oznaczonej,
a) permutację zbioru {1, 2,..., n} dla n>0.
9. Pokazać, że złożenie funkcji różnowartościowych jest funkcją różnowartościową. Czy złożenie
permutacji jest permutacją?
10. Niech będzie dany pewien graf G = (V, A), gdzie A
V
2
. Jaką interpretację można przypisać
złożeniu relacji A? Co oznaczają A
2
, ..., A
n
? W jaki sposób można zbadać, czy graf posiada pętle
oraz cykle?
