LOGIKA I MATEMATYKA DYSKRETNA

LISTA ZADA‹ NR 3

1. Udowodnij indukcyjnie:
a) 1

2

+ 2

2

+ 3

2

+ ... + n

2

=

1
6

n(n + 1)(2n + 1)

dla n ∈ N

b) 2

0

+ 2

1

+ 2

2

+ ... + 2

n

= 2

n+1

− 1

dla n ∈ N

c) 10

n

− 1

dzieli si¦ bez reszty przez 9 dla n ∈ N

2. Okre±l wªasno±ci (zwrotno±¢, symetryczno±¢, itp.) poni»szych relacji:

a) xRy gdy x · y = 0; x, y ∈ R

b) mRn gdy m + n = 5; m, n ∈ {0, 1, 2, 3, 4, 5}

c) mRn gdy m − n jest parzyste; m, n ∈ {0, 1, 2, 3}

3. Narysuj diagram Hassego poni»szych relacji:

a) (x

1

, x

2

) ¹ (y

1

, y

2

)

gdy x

2

1

+ x

2

2

≤ y

2

1

+ y

2

2

, gdzie x

1

, x

2

, y

1

, y

2

∈ {0, 1, 2}

b) x ¹ y gdy x < y − 1 lub x = y, gdzie x, y ∈ {0, 1, 2, 3, 4}

Grzegorz Kondrat