2. LOGIKA I TEORIA MNOGO´SCI.

1

2

Logika i teoria mnogo´sci.

2.1

Rachunek zda´

n. Funkcja zdaniowa. Kwanty…katory.

Zad. 1

Udowodni´c nast ¾

epuj ¾

ace prawa rachunku zda´n (tautologie):

a)

p _ (s q) ;

b)

p , s (s p) ;

c)

( p ) q ) , ( s q ) s p ) ;

d)

[ (p ) q) ^ (q ) r) ] ) ( p ) r ) ;

e)

[ p ^ (( p ) q ))] ) q;

f )

p _ (q ^ r) , (p _ q) ^ (p _ r) :

Zad. 2

Sprawdzi´c, czy nast ¾

epuj ¾

ace schematy zda´n s ¾

a tautologiami:

a)

[(p _ q) ^ (p ) q)] ) (q ) p) ;

b)

p ) [( q ^ q) ) r ] ;

c)

[( p ) q ) ^ p] ) q ;

d)

[ (p ) q) ^ (q ) p) ] ) ( p _ q ) ;

e)

[ (p ^ q) ) r] ) (p ) r) ^ (q ) r) ;

f )

(p ) q) , [(p ^ q) , p] ;

g)

(p _ q _ r) ) f

p ) [(q _ r) ^

p]g ;

h)

[p ^ (q _ r)] , [(p ^ q) _ (p ^ r)] ;

i)

[

(p ) q)] , (p ^

q) ;

j)

[(p ^ q) ) p] _ q;

k)

[

(p ^ q)] , [ p _

q] ;

l)

(p ^ q) ) (p _ q) ;

m)

[p , (q _ r)] ) r;

n)

f[(p _ r) , q] ^ rg ) ( p _ q) ;

o)

[(p ) q) ) p] ) q:

Zad. 3

Wyznaczy´c wykres funkcji zdaniowej ', której zakresem zmienno´sci jest zbiór X, okre´slonej w

nast ¾

epuj ¾

acy sposób:

a)

' (x)

,, log x

0";

X = R

+

;

b)

' (x)

,, jx

1j < 2 ^ 2

x

> 0";

X = R;

c)

' (x)

,, sin x 6= 0";

X = R;

d)

' (x)

,,x

2

< 3 ) x > 1";

X = R;

e)

' (x)

,,x

2

= 5";

X = N;

f )

' (x)

,,e

x 1

>

1";

X = R;

g)

' (x)

,, jxj = 4";

X = C;

h)

' ((a

n

))

,,ci ¾

ag (a

n

) jest monotoniczny i ograniczony";

X =zbiór ci ¾

agów liczbowych rzeczywistych;

i)

' ((a

n

))

,, lim

n!1

a

n

= 1 ^

P

a

n

jest zbie·

zny";

X =zbiór ci ¾

agów liczbowych rzeczywistych;

j)

' ((f ))

,,f

0

(x) > 0 dla x 2 [0; 1]";

X =zbiór funkcji okre´slonych na przedziale [0; 1]:

2006

EM

2. LOGIKA I TEORIA MNOGO´SCI.

2

Zad. 4

Które spo´sród podanych formu÷s ¾

a zdaniami (okre´sli´c ich warto´s´c logiczn ¾

a), a które funkcjami

zdaniowymi:

a)

V

x2R

p

x

2

+ 6x + 9 = x + 3 _

W

x2R

p

x

2

= x ;

b)

V

x2R

x

2

> log (0; 5)

)

W

y2R

y

2

= 10

!

;

c)

V

x2R

+

log x > 0

!

) cos

3
4

=

p

2

2

;

d)

ln x

0;

e)

W

x2R

sin

2

x

2;

f )

V

x2R

sin

2

x + cos

2

x = 1;

g)

W

x2R

sin

2

x + cos

2

x = 1;

h)

x

2

+ y

2

= 4;

i)

W

x2N

W

y2N

x

2

+ y

2

= 4;

j)

V

x2R

W

y2N

x

2

+ y

2

= 4;

k)

W

y2R

V

x2R

x

2

+ y

2

= 4;

l)

V

x2R

x

2

+ y

2

= 4;

m)

V

x2N

W

y2N

y

x = 2;

n)

x : x

2

4 < 0 = (0; 2) ;

o)

P

1

n=1

f

n

(x) jest zbie·

zny;

p)

lim

n!1

1

1

n

n

= e;

q)

V

x2R

(sin x)

0

> 0;

r)

W

x2R

(sin x)

0

< 0;

s)

V

a;b2R

a

2

< b

2

, a < b ;

t)

W

a2R

W

b2R

a

2

= b

2

, a = b :

Zad. 5

Napisa´c zaprzeczenie podanego zdania i okre´sli´c jego warto´s´c logiczn ¾

a:

a)

V

x2R

(x > 0 ) x > 1) ;

b)

W

x2R

x

2

< 0

_

V

x2R

x

2

< 0 ;

c)

V

x2R

log

2

(jxj + 1) > 0 _ x

3

1 ;

d)

W

x2R

2

x

<

p

2 ^ x

4

0 ;

e)

V

n2N

n

2

> 4 ) 2

n

> 4 ;

f )

V

x2R

V

y2R

(xy > 0 _ jxj + y

0) ;

g)

V

x2R

W

y2R

(x

2

+ y

2

1 ) y = x);

h)

V

x2R

W

n2N

(n > x _ 3

n

< x) ;

i)

V

x2R

W

y2R

(y = sin x _ x = sin y) ;

j)

V

x2R

p

x

2

= x ) x

4

> 0 ;

k)

V

x>0

W

y<0

log

2

x < y

2

^ jxj = 2

y

;

l)

W

y 1

W

x> 1

x

2

+ y

2

= 1:

Zad. 6

Wyznaczy´c zbiór fx 2 R : ' (x)g, gdzie funkcja zdaniowa ' okre´slona jest w nast ¾

epuj ¾

acy sposób:

a)

' (x)

,,

W

y

2R

3x

y = 0 ";

b)

' (x)

,,

W

y

2R

y = sin x ";

2006

EM

2. LOGIKA I TEORIA MNOGO´SCI.

3

c)

' (x)

,,

V

y2R

y

2

+ xy + 1 < 0 ";

d)

' (x)

,,

V

y2R

3x

xy = 0 ";

e)

' (x)

,,

V

y2R

y sin x = 0 ";

f )

' (x)

,, arcsin (x + 1) = 0":

Zad. 7

Wyznaczy´c zbiór

(x; y) 2 R

2

:

(x; y) , gdzie funkca zdaniowa

okre´slona jest w nast ¾

epuj ¾

acy

sposób:

a)

(x; y)

,,x

2y + 1 = 0 ";

b)

(x; y)

,,xy

0 ";

c)

(x; y)

,,xy = 1 ";

d)

(x; y)

,,x

2

+ y

2

9 ";

e)

(x; y)

,, jx

yj = 4 ";

f )

(x; y)

,, jxj + jyj

1 ";

g)

(x; y)

,,y > x + 1 ^ y < 1

x ";

h)

(x; y)

,,y > x + 1 ) y < 1

x ":

Zad. 8

Zapisa´c u·

zywaj ¾

ac symboli kwanty…katorów nast ¾

epuj ¾

ace zdania:

a)

Ka·

zda liczba naturalna jest ca÷

kowita.

b)

Iloraz liczb naturalnych nie musi by´c liczb ¾

a naturaln ¾

a.

c)

Iloraz liczb naturalnych mo·

ze by´c liczb ¾

a naturaln ¾

a.

d)

Dla ka·

zdej liczby wymiernej mo·

zna dobra´c liczb ¾

e ca÷

kowit ¾

a tak ¾

a, ·

ze ich iloczyn jest liczb ¾

a ca÷

kowit ¾

a.

e)

Dla ka·

zdego " > 0 istnieje liczba naturalna K taka, ·

ze dla ka·

zdego n > K wyrazy ci ¾

agu a

n

s ¾

a wi ¾

eksze

od ".

f )

Suma dwóch ci ¾

agów zbie·

znych jest ci ¾

agiem zbie·

znym.

2.2

Rachunek zbiorów.

Zad. 9

Wyznaczy´c A; B; A [ B; A \ B; A n B; B n A; A

0

; B

0

; je´sli

a)

A = N;

B = [ 1; 3];

b)

A = Z;

B = fx 2 R : x

2

= 5g;

c)

A = [0; 2];

B = fx 2 R : jx

1j

1g;

d)

A = (0; +1);

B = fx 2 R : log

1
2

x

1g:

2006

EM

2. LOGIKA I TEORIA MNOGO´SCI.

4

Zad. 10

Wyznaczy´c zbiór pot ¾

egowy 2

X

w przypadku, gdy

a)

X = ;;

b)

X = fa; b; cg;

c)

X = ff1g; f1; 2gg;

d)

X = f;; ag;

e)

X = (0; 1);

f )

X = N:

Wskaza´c zbiory, dla których zbiór 2

X

ma sko´nczon ¾

a ilo´s´c elementów.

Zad. 11

Wyznaczy´c moc nast ¾

epuj ¾

acych zbiorów:

a)

A = ;;

b)

B = f;g;

c)

C = fx 2 R : x

2

x = 1g;

d)

D = fx 2 R : x

2

4 > 0g;

e)

E = f2n + 1 : n 2 Ng;

f )

F = f0; 1g

f3; 4g;

g)

G = (0; 1)

(3; 4);

h)

H =zbiór liczb podzielnych przez 5;

i)

I =zbiór liczb ca÷

kowitych czterocyfrowych,

które mo·

zna utworzy´c z cyfr 0; 1; 2; 3; 4;

j)

G =zbiór przedzia÷

ów postaci (a; b), gdzie

a; b 2 Q:

Zad. 12

Wyznaczy´c i narysowa´c zbiór:

a)

f 1; 2; 4g

f2; 5g ;

b)

f 1; 3; 4g

(1; 1) ;

c)

N

R;

d)

(2; 5]

( 1; 1) ;

e)

[ 1; 4]

(2; 5] ;

f )

[ 2; 1]

[ 2; 4) ;

g)

(x; y) 2 R

2

: y > x ^ y < 2x ;

h)

(x; y) 2 R

2

: y

jxj _ x

2

+ y

2

< 1 ;

i)

(x; y) 2 R

2

: x

2

+ y

2

2x

2y

0 ) x >

1
2

;

j)

(x; y) 2 R

2

: y

jx

1j ^ y < jx + 1j ;

k)

(x; y) 2 R

2

: y > 2

x

_ x > 2

y

;

l)

(x; y) 2 R

2

: y > x

2

) y = jxj ;

m)

(x; y) 2 R

2

: x

y + 2 < 0 ) jxj + jyj

0 ;

n)

(x; y) 2 R

2

: y = log

2

(jxj + 1) ^ y

0 :

Zad. 13

Wyznaczy´c i narysowa´c zbiory A; B; A [ B; A \ B; A n B; B n A; A

0

; B

0

; gdzie:

a)

A = [ 1; 1]

[0; 1] ; B = R

1
2

; 4 ;

b)

A = (x; y) 2 R

2

: y > x ; B = (0; 1)

( 1; 2] :

Zad. 14

Udowodni´c, ·

ze dla dowolnych zbiorów A; B; C

X zachodz ¾

a równo´sci:

a)

A \ (B [ C) = (A \ B) [ (A \ C) ;

b)

A [ (B \ C) = (A [ B) \ (A [ C) ;

c)

(A \ B)

0

= A

0

[ B

0

;

d)

A n (B [ C) = (A n B) n C;

e)

(A [ A

0

)

0

= ;;

f )

(A n B) [ B = A;

2006

EM

2. LOGIKA I TEORIA MNOGO´SCI.

5

g)

A

(B [ C) = (A

B) [ (A

C) ;

h)

(B \ C)

A = (B

A) \ (C

A) :

Zad. 15

Czy dla dowolnych zbiorów A; B; C

X zachodz ¾

a poni·

zsze równo´sci? Uzasadni´c odpowied´z.

a)

A n (B \ C) = (A n B) \ (A n C) ;

b)

(A [ B)

0

= A

0

\ B

0

;

c)

A [ (B n C) = (A [ B) n (A \ C) ;

d)

A n B = (A

0

[ B)

0

;

e)

(A [ B) n B = A;

f )

(A n C)

B = (A

B) \ (C

B) ;

g)

(A n B) n C = A n (B n C) ;

h)

A \ (B n C) = (A \ B) n (A \ C) :

Zad. 16

Wyznaczy´c (narysowa´c) kilka zbiorów z podanej rodziny, a nast ¾

epnie wyznaczy´c

S

n2N

A

n

i

T

n2N

A

n

,

je´sli

a)

A

n

=

1

n

; 3 +

1

n

; n 2 N;

b)

A

n

= ( 1)

n 1

n

; n! ; n 2 N;

c)

A

n

=

1

n+1

;

1

n

i

; n 2 N;

d)

A

n

= [n; n + 1]; n 2 N;

e)

A

n

= [( 1)

n

; 1 +

1

2

n

]; n 2 N;

f )

A

n

= 0; 2

1

n

(0; n) ; n 2 N;

g)

A

n

= f1; 2; :::; ng

[0; n] ; n 2 N;

h)

A

n

=

1

n

;

1

n

R; n 2 N;

i)

A

n

= fx 2 R : cos

n

x = 1g ; n 2 N;

j)

A

n

= (x; y) 2 R

2

: x 2 [0; 1] ^ 0

y

x

n

:

Zad. 17

Wyznaczy´c (narysowa´c) kilka zbiorów z podanej rodziny, a nast ¾

epnie wyznaczy´c

S

A

t

i

T

A

t

, je´sli

a)

A

t

= (0;

1

t

); t 2 R

+

;

b)

A

t

= (0;

t

t+1

); t 2 R

+

;

c)

A

t

= fx 2 R : jxj < tg ; t 2 R

+

;

d)

A

t

= fx 2 R : xt

1g ; t 2 R;

e)

A

t

= fx 2 R : sin x = tg ; t 2 R;

f )

A

t

= [ 1; sin t] ; t 2 R;

g)

A

t

= (x; y) 2 R

2

: y

t jxj ; t 2 R

+

;

h)

A

t

= (x; y) 2 R

2

: y

jx

tj ; t 2 R;

i)

A

t

= (x; y) 2 R

2

: x

2

+ y

2

t

2

; t 2 R

+

;

j)

A

t

= (x; y) 2 R

2

: x

2

+ y

2

t

2

^ y

1
2

t ;

t 2 R

+

:

2.3

Relacje.

Zad. 18

Sprawdzi´c, które spo´sród poni·

zej zde…niowanych relacji s ¾

a funkcjami:

a)

1

= (x; y) 2 (0; +1)

( 1; 0) : x

2

= y

2

;

b)

2

= (x; y) 2 R

( 1; 0) : x

2

= y

2

;

c)

3

= (x; y) 2 ( 1; 0)

R : x

2

= y

2

;

d)

4

= ;;

e)

5

= [f1g

( 1; 0)] [ [f2g

(0; +1)];

f )

6

= f(x; y) 2 R

( 1; 0) : jyj = 2g ;

2006

EM

2. LOGIKA I TEORIA MNOGO´SCI.

6

g)

7

= (x; y) 2 R

( 1; 0] : y

2

+ y

0 ;

h)

8

= (x; y) 2 R

2

: y

2

+ y

0 :

Zad. 19

Sprawdzi´c, czy podzbiór f

A

B jest funkcj ¾

a odwzorowuj ¾

ac ¾

a zbiór A w zbiór B, je´sli:

a)

A = R; B = R n f0g oraz

V

x2R

V

y2Rnf0g

(x; y) 2 f , 2xy = 1;

b)

A = R; B = R oraz

V

x2R

V

y2R

(x; y) 2 f , x

2

y

2

= 1;

c)

A; B s ¾

a dowolnymi zbiorami, y

o

jest dowolnym elementem zbioru B oraz

V

x2A

V

y2B

(x; y) 2 f , y = y

o

:

Zad. 20

Zbada´c, czy funkcja f jest injekcj ¾

a, surjekcj ¾

a, bijekcj ¾

a; wyznaczy´c przeciwdziedzin ¾

e funkcji f i (o

ile istnieje) funkcj ¾

e odwrotn ¾

a f

1

.

a)

f : [2; +1) ! R;

f (x) =

x

2

+ 4x

3;

b)

f (x) =

x

x 1

;

c)

f (x) =

x

2

;

x

0;

log (x + 1) ; x > 0;

d)

f (x) = 2

jx + 2j ;

e)

f : Z ! Z;

f (k) = 2k + 1;

f )

f : R

2

! R;

f (x; y) = x + y;

g)

f : R

2

! R

2

;

f (x; y) = (x; xy) ;

h)

f : R

2

! R

2

;

f (x; y) = (x

y; x + 2y) ;

i)

f : C ! C;

f (z) = z + 1

2i;

j)

f : C ! C;

f (z) = iz:

Zad. 21

Zbada´c, czy

X

X jest relacj ¾

a równowa·

zno´sci. Je´sli tak, to wyznaczy´c (opisa´c, narysowa´c,

„policzy´c”„) klasy abstrakcji tej relacji.

a)

X = R f0g ;

x y , xy > 0;

b)

X = R;

x y , xy

0;

c)

X = R;

x y , x

y > 1;

d)

X = Z;

n m ,

W

k2Z

n

m = 3k;

e)

X = R;

x y , x

y 2 Z;

f )

X = R;

x y , x

2

= y

2

;

g)

X = 2

R

;

A B , A

B;

h)

X = 2

N

;

A B , A \ B = ;;

i)

X = R

2

;

(x

1

; y

1

) (x

2

; y

2

) , x

2

1

+ y

2

1

= x

2

2

+ y

2

2

;

j)

X = R

2

;

(x

1

; y

1

) (x

2

; y

2

) , x

1

= x

2

;

k)

X = R

2

;

(x

1

; y

1

) (x

2

; y

2

) , x

1

= y

2

;

2006

EM

2. LOGIKA I TEORIA MNOGO´SCI.

7

l)

X = R

+

R

+

;

(x

1

; y

1

) (x

2

; y

2

) ,

y

1

x

1

=

y

2

x

2

;

m)

X = C

2

;

z

1

z

2

, Im z

1

= Im z

2

;

n)

X = C

2

;

z

1

z

2

, arg z

1

= arg z

2

;

o)

X = zbiór ludzi,

x y , x jest ojcem y;

p)

X =zbiór prostych w R

2

;

l k , l ? k;

q)

X =zbiór prostych w R

2

;

l k , l q k;

r)

X =zbiór wektorów w R

2

;

x y

, x q y;

s)

X = zbiór studentów P×, x y , x i y ucz ¾

a si ¾

e na tym samym wydziale P×;

t)

X = zbiór punktów pewnej mapy,

P Q , h (P ) = h (Q) ; gdzie h (P ) = wysoko´s´c n.p.m. punktu P:

Jak nazywamy klasy abstrakcji relacji zde…niowanych w czterech ostatnich podpunktach?

Zad. 22

Zbada´c, czy

X

X jest relacj ¾

a porz ¾

adku (liniowego porz ¾

adku), je´sli

a)

X = N;

n m , n j m (n jest dzielnikiem m);

b)

X = 2

R

;

A B , A \ B = ;;

c)

X = R;

x y , x

y 2 Q;

d)

X = R;

x y , x

y:

Zad. 23

Wyznaczy´c elementy maksymalne, minimalne, najwi ¾

eksze i najmniejsze (o ile istniej ¾

a) w zbiorze

uporz ¾

adkowanym (X; ), je´sli

a)

X = f2; 4; 6; 8; 12; 16g;

n m , n j m;

b)

X =rodzina przedzia÷

ów postaci ( a; a), gdzie a jest dowoln ¾

a liczb ¾

a dodatni ¾

a,

A B , A

B;

c)

X = 2

R

;

A B , A

B;

d)

X =zbiór s÷

ów w danym j ¾

ezyku;

s

1

s

2

, s

1

wyst ¾

epuje w s÷

owniku przed s

2

;

e)

X = f1; 2; 3; 4; 5; 6g;

x y , x ! y wg schematu:

1 ! 2 ! 3

#

4 ! 5 ! 6

f )

X = f1; 2; 3; 4g;

x y , x ! y wg schematu:

1 ! 2
"

#

4 3

g)

X = fa; b; c; d; e; f; gg;

x y , x ! y wg schematu:

a ! b

f

#

#

"

c

! d ! e ! g

2006

EM