Wrocław, 24 paz
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 �� X2 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 2R) 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(t2+1).
3. Niech f: R��R będzie funkcją określoną wzorem f(x) = -2x+4. Znalez
ć 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(xi)=yi, i=1,2,...,k; kŁ�n, xi,yi ��{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 = {, , , , , , , , , , }.
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 �� V2. Jaką interpretację można przypisać
złożeniu relacji A? Co oznaczają A2, ..., An? W jaki sposób można zbadać, czy graf posiada pętle
oraz cykle?
11. Pokazać w jaki sposób na podstawie definicji grafu w postaci G = (V, A) zbudować jego definicję
o postaci G = (V, G�), gdzie G� : V �� 2V jest funkcją wyznaczającą dla dowolnego wierzchołka
v��V zbiór wierzchołków następników G�(v), tj. wierzchołków do których prowadzą łuki z
wierzchołka v.