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?

11. Pokazać w jaki sposób na podstawie definicji grafu w postaci G = (V, A) zbudować jego definicję

o postaci G = (V,



), gdzie



: V



2

V

jest funkcją wyznaczającą dla dowolnego wierzchołka

v



V zbiór wierzchołków następników



(v), tj. wierzchołków do których prowadzą łuki z

wierzchołka v.