logika 2termin

Egzamin ze wstępu do logiki

Imię i Nazwisko:. Nr grupy:..........

1.    Zapisz wyrażenie Vx: (Vyp(x,y) v q(x)) w sposób równoważny za pomocą jedynie kwantyfikatora szczegółowego 3, negacji i implikacji.

2.    Udowodnij korzystając wyłącznie z reguł wnioskowania:

(P => (<l =>'■))=> ((/> =>?) => (P => r)).

3.    Niech f:X-»Y i {Bi:teT}będzie dowolną rodziną podzbiorów Y.

Czy /■'[P|Ą] = p|/^_l[B,]? Odpowiedź uzasadnij.

4.    Niecił f,g:X-*Y będą iniektywnymi odwzorowaniami. Udowodnij: f'^l=g=> f=g.

5.    W zbiorze liczb zespolonych C-{0} określamy relację R: zRwoz w elR. Wykaż, że jest to relacja równoważności.

6.    W zbiorze X określona jest relacja R przeciwzwrotna (tzn. VxeX ~xRx), przechodnia i spójna. Sprawdź, czy relacja X-R jest relacją częściowego porządku.

7.    Czy jest możliwe, aby w zbiorze częściowo uporządkowanym każdy element był minimalny i nie było w nim elementu maksymalnego? Odpowiedź uzasadnij.

8.    Podaj przykład zbioru co najmniej trójelementowego, który jest dobrze uporządkowany relacją inkluzji.

10. Uzasadnij, że zbiór {a+b'42 :	s Q a b e Z a n i } jest przeliczalny.
Reguły wnioskowania:
R0. p, p=>q -> q	R9. p»q -> p=>q
Rl.p-»~~p	RIO. p»q -» q=>p
R2. ~(p=>q) -* pA~q	RU. ~(poq) -> (pA~q)v(~pAq)
R3. pvq, ~p -» q	R12. Vx:p(x) -» p(x|a)
R4. pvq, ~q p	RI3, 3x:p(x) p(a), a-nowa
R5. ~(pvq) -» ~pA~q	R14. ~Vx:p(x) -> 3x:~p(x)
R6, pAq -> p R7. pAq -» q R8. ~(pAq) -» ~pv~q	R15. ~3x;p(x) -» Vx:~p(x)

9.    Udowodnij, że jeżeli f:X-*X jest iniekcją i f[X]cYcX, to X~Y.