Математика \ Специальные главы математики

Решение 15 заданий с множествами и подмножествами (Вариант 17), страница 2

Значит, $x: y=f(x) Þ xÎAÈB Þ xÎA либо xÎB Þ y=f(x)Îf(A) È f(B)

Ü Пусть yÎf(A)Èf(B)

yÎf(A) либо yÎf(B)

$x: y=f(x)

xÎA либо xÎB Þ xÎAÈB

y = f(x) Î f(AÈB)

b) f(AÇB) Í f(A) Í f(B)

Þ Пусть yÎf(AÇB) Þ $x: y=f(x) Þ xÎAÇB Þ xÎA, xÎB Þ f(x)Îf(A) и f(x)Îf(B) Þ yÎf(A)Çf(B)

Следовательно, f(AÇB) Í f(A)Çf(B)

c) f(A)\f(B) Í f(A\B)

Пусть yÎf(A) \ f(B) Þ yÎf(A), yÏf(B)

$x: y=f(x), xÎA, xÏB Þ xÎ(A\B) Þ f(x)Îf(A\B) Þ yÎf(A\B)

Следовательно, f(A) \ f(B) Í f(A\B)

Задание №9

Пусть A – множество прямых на плоскости. Являются ли эквивалентностями следующие отношения:

а) Параллельность прямых

R = {(x,y) | x,yÎA и x параллельна y}

Рефлексивность: нет, т.к. прямая не параллельна сама себе Þ R не является эквивалентностью ? (спорный вопрос)

Ответ: ?

b) Перпендикулярность прямых

R = {(x,y) | x,yÎA и x перпендикулярна y}

Рефлексивность: нет, т.к. прямая не перпендикулярна сама себе

Следовательно, R не является эквивалентностью

Ответ: нет

Задание №10

Найти dR, rR, R-1, R◦R, R◦R-1, R-1◦R

а) R = {(x,y) | x,yÎN и x делит y}

Решение:

1◦ dR=N

Þ по определению

Ü Пусть xÎN, тогда $y: для xÎN (x,y)ÎR, т.е. x=ky, kÎN, значит, NÍdR

2◦ rR=N

Þ по заданию R yÎN и y=(1/k)*x, kÎN, т.е. yÎN Þ rRÍN

Ü Пусть yÎN, значит, $ такой x (x=ky, kÎN), что (x,y)ÎR

Значит, NÍrR

3◦ R-1 = {(y,x) | x,yÎN и y делит x}

4◦ R◦R = {(x,y) | x,yÎN и y делит x}

т.к. (x,y)ÎR◦R Û $z: z делит x и y делит z, т.е. x=kz, kÎN и z=my, mÎN Þ x=kmy, k,mÎN, значит, y делит x

5◦ R◦R-1 = {(x,y) | x,yÎN}

т.к. (x,y)ÎR◦R-1 Û $z: z делит x и z делит y, тогда достаточно взять z=1

6◦ R-1◦R = {(x,y) | x,yÎN}

(x,y)ÎR-1◦R Û $z: x делит z и y делит z, тогда достаточно взять z=xy

b) R = {(x,y) | x,yÎD и x+y<=0}

Решение:

1◦ dR = D

2◦ rR = D

3◦ R-1 = {(y,x) | x,yÎD и y+x<=0}

R-1 = R, так как

#1) R-1Ì R

пусть aÎR-1 Þ a=(y,x), x,yÎD и y+x<=0 Þ aÎR

#2) RÌ R-1

пусть aÎR Þ a=(x,y), x,yÎD и x+y<=0 Þ aÎR-1

4◦ R◦R = R◦R-1=R-1◦R = {(x,y) | x,yÎD}

(x,y)ÎR◦R Û $z такое, что x+z<=0 и z+y<=0. Тогда достаточно взять z=min(-|x|,-|y|). Действительно, если z=-|x|, то x-|x| = 0, если x>=0 ; -2x, если x<0, а -|x|+y<=0, т.к. |x|>y

Если z=-|y|, то x-|y|<=0, т.к. |x|<|y| и -|y|+y = 0, если y>=0; -2y, если y<0

Задание №11

Доказать, что если отношения R1 и R2 рефлексивны, то рефлексивны и отношения R1ÈR2, R1ÇR2, R1-1, R1◦R2

a) Докажем, что R1ÈR2 рефлексивно, т.е. (x,x)ÎR1ÈR2  для любого xÎA

Пусть (k,l)ÎR1ÈR2. Тогда (k,l)ÎR1, либо (k,l)ÎR2. Но т.к. R1 и R2 рефлексивны, то (k,k)ÎR1, либо (k,k)ÎR2, т.е. (k,k)ÎR1ÈR2. Значит, R1ÈR2 рефлексивно.

б) Докажем, что R1ÇR2 рефлексивно

Пусть (k,l)ÎR1ÇR2. Тогда (k,l)ÎR1 и (k,l)ÎR2. Но, т.к. R1 и R2 рефлексивны, то (k,k)ÎR1 и (k,k)ÎR2, т.е. (k,k)ÎR1ÇR2. Значит, R1ÇR2 рефлексивно.

в) Докажем, что R1-1 рефлексивно

Пусть (a,b)ÎR1 и (b,a)ÎR1-1. По свойству рефлексивности, (a,a)ÎR1. Тогда (a,a)ÎR1-1 и R1-1 рефлексивно.

г) Докажем, что R1°R2 рефлексивно

Доказательство (от противного):

Предположим, что R1°R2 нерефлексивно.

Пусть (a,b)ÎR1°R2, т.е. $z: (a,z)ÎR1 и (z,b)ÎR2. Мы положим, что R1°R2 нерефлексивно, т.е. (a,a)ÏR1°R2. Но тогда нет таких z, что (a,z)ÎR1 и (z,a)ÎR2. Из рефлексивности R1 и R2 получаем: $z: (a,z)ÎR1 и (z,z)ÎR2, но нет z: (a,z)ÎR1 и (z,z)ÎR2. Мы получим противоречие, значит начальное предположение неверно и R1°R2 рефлексивно

Задание №12

Построить бинарное отношение:

рефлексивное, симметричное, не транзитивное

Таким, например, является отношение R = {(x,y) | x,yÎD, |x-y| <=1}

Рефлексивность соблюдается, т.к. (x-x)=0<=1

Симметричность соблюдается, т.к. |x-y| = |y-x| <=1

Транзитивность не соблюдается, т.к. из того, что |x-y|<=1 и |y-z|<=1 вовсе не следует, что |x-z|<=1

Задание №13

Доказать, что множество всех подмножеств данного множества частично упорядочено отношением включения Í

Доказательство:

Частичным порядком на множестве A называется отношение R такое, что:

1)  R транзитивно

2)  R рефлексивно

R = {(x,y) | x,yÎA и x Í y}

Имеется множество A, элементами которого являются его же подмножества.

Проверяем:

Транзитивность: да. Т.к. если xÍy и yÍz, то xÍz

Рефлексивность: да. Т.к. xÍx по определению. Каждое множество содержит само себя.

Задание №14

Сколькими способами можно разложить n = n1+…+nk различных шаров по m урнам так, чтобы в первую урну попало n1 шаров, во вторую n2 и т.д. в k-ую nk шаров?

Первые n1 шаров мы выбираем из n. Т.е. число сочетаний из n по n1:

n2 шаров мы выбираем из оставшихся n-n1 шаров и т.д. до конца

Применяем правило произведения.

Задание №15

а)

b)

Скачать файл