Wrocław, 27 paz
dziernika 2015
Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków
Zadania  lista 4
1. 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).
2. Niech f: R��R będzie funkcją określoną wzorem f(x) = -2x+4. Znalez
ć funkcję odwrotną do tej
funkcji.
3. 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}.
4. 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.
5. Udowodnić, że w zbiorze [0,2] (jest to zbiór wszystkich liczb rzeczywistych nie mniejszych niż 0
i nie wię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].
6. Funkcja f jest zgodna z relacją R wtt f �� R. Dla X =df {a, b, c, d} niech będzie 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?
7. Jakie sygnatury mają funkcje reprezentujące:
a) operację całki nieoznaczonej,
b) całki oznaczonej,
a) permutację zbioru {1, 2,..., n} dla n>0.
8. Pokazać, że złożenie funkcji różnowartościowych jest funkcją różnowartościową. Czy złożenie
permutacji jest permutacją?
9. 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?
10. 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.