Теория множеств.

{x, x ϵ N, x²<100}

{1, 2, …, 9}

{x, x ϵ Z, x²<100}

-9, …, 0, …, 9

• Описать множества при помощи характеристического свойства.

x = {3, 6, 9, 12, 15, 18, 21, 24} положительные числа кратные 3

x = {a, b, c, d, e, f, g, h, I, j} буквы латинского алфавита

x = {1, 4, 9, 16, 25, … } квадраты положительных чисел

• Перечислить подмножества множеств.

{a} : {a}, Ø

{a, b} : {a, b}, {a}, {b}, Ø

{a, b, c} : {a, b, c}, {a, b}, {b, c}, {a, c}, {a}, {b}, {c}, Ø

{a, b, c, d} : {a, b, c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a}, {b}, {c}, {d}, Ø

• 2ⁿ – количество подмножеств множества из n элементов

1. n=0 2⁰=1

2. n=k

2^k {ᴓ, 1, 2, 3, 4, …,k}

3. 2^k+1=2^k2

{1, 2, 3, …, k}u{k+1}={1, 2, 3, …, k+1}

2^k+2^k=2*2^k=2^k+1

• Определить верность.

{2}ϵ{1, 2, 3, 4, 5} 0

{2}≤{1, 2, 3, 4, 5} 1

Ø ={ Ø } 0

{1, 2, 3}ϵ{1, 2, 3, {1, 2, 3}} 1

{1, 2, 3}≤{1, 2, 3, {1, 2, 3}} 1

• Определить количество элементов.

{ Ø, { Ø }} 2

{{ Ø, { Ø }}} 1

{1, 2, 3, {1, 2, 3}} 4

{ Ø, { Ø }, a, b, {a, b}, {a, b}, {a, b, {a, b}}} 6

{ Ø, { Ø }, { Ø, { Ø }}} 3

• Определить, что будет результатом выполнения представленной программы и доказать почему

алг. «решение»

команда 1

команда 2

конец

алг. «команда 1»

если справо свободно

то вправо

иначе

вверх

«команда 1»

вправо

все

конец

алг. «команда 2»

если слева стена

то закрась

иначе

влево вниз

«команда 2»

вправо закрась

все

конец

Доказательство «команда 1».

1)

2)

3)

n=0

n=k

n=k+1

n=k

n=k

n=k+1

Доказательство «команда 2».

1)				2)						3)
n=1
				n=k						n=k
										n=k+1

• Пусть есть массив x(n) содержащий n элементов. Определить результат следующей функции.

функция «решение(i)»

если i > n

то выход 0

иначе

i=i+1

выход x(i - 1) + «решение(i)»

все

конец

Данная функция складывает i элементов массива.

• Используя диаграммы венна закрасить те части, которые изображают множества.

А'

В

А

А ∩ В

В

А

(А u В) \ (А ∩ В)

В

А

А \ В

• С посощью диаграмм венна составьте множества.

C

B

A

(A \ C)U(B \ C)U(A∩B∩C)

C

B

A

(A∩C)u(A∩B)U(B∩C)

C

B

A

(A∩C)U(A∩B)U(B∩C) \ (A∩B∩C)

• Доказать.

(AUB)=A∩B

B

A

(aUb)

A B

AU(B∩C)=(AUB)∩(AUC)

C

B

A

au(b∩c)

C

B

A

C

B

A

aub auc

Симетрическая разность — ассоциативность.

(AΔB)ΔC

(((A\B)U(B\A))\C)U(C\((A\B)U(B\A)))

(((A\B)U(B\A))\C) (C\((A\B)U(B\A)))

(((A\B)U(B\A))\C)U(C\((A\B)U(B\A)))

(A\(BΔC))U((BΔC)\a)

(A\(BΔC)) ((BΔC)\a)

(A\(BΔC))U((BΔC)\a)