Множества. Операции над множествами

Министерство  образования и науки РФ

Пензенский  государственный университет

 

Кафедра дискретной математики

 

 

 

 

 

ОТЧЕТ

по выполнению лабораторной работы №1

«Множества. операции над множествами»

 

 

 

 

 

Выполнили: студенты гр. 11ВЭ1

ЛитвиноваА.Р.

Войлочникова О.Ю.

Проверил: доцент,

к.т.н. Л.Н. Бондаренко

 

 

 

 

 

 

Пенза 2012 г.

Цель работы: изучение представлений множеств в ЭВМ и исследование основных операций над множествами с использованием математического пакета аналитических вычислений Maple.

2 Теоретическое задание  

2.1 Доказать, что число всех k-элементных подмножеств n-элементного множества X равно числу сочетаний из n по k

.

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

Данная нам формула  совпадает с формулой для числа сочетаний, которую можно получить из формулы для числа размещений. Если составить сначала все k-сочетания из n элементов, а потом переставить входящие в каждое сочетание элементы всеми возможными способами. При этом получатся все k-размещения из n элементов, причем каждое только по одному разу. Но из каждого k-сочетания можно сделать k! перестановок, а число этих сочетаний равно .  Значит, справедлива формула k! =

Из этой формулы находим, что = =

 

Поскольку выведенная формула совпадает с формулой для числа перестановок из k элементов одного типа и (n-k) элементов второго типа:  , то число сочетаний из n элементов по k можно найти по формуле  .

 

2.2 Доказать, что биномиальные коэффициенты удовлетворяют следующему рекуррентному соотношению

,

где  – символ Кронекера.

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

 

2.3 Доказать, что биномиальные коэффициенты описываются производящей функцией (биномом Ньютона)

.

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

Запишем (1+t)ⁿ в виде произведения  (1+t)ⁿ=(1+t) × (1+t) × …× (1+t).  Расписав правую часть этого равенства можно увидеть, что членов,  в которые входит k и (n–k) букв t ровно Р(k, n–k)= . Отсюда вытекает формула .

2.4  Составить таблицу чисел при , а .

n	k=0	k=1	k=2	k=3	k=4	k=5	k=6	k=7	k=8	k=9	k=10
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1
7	1	7	21	35	35	21	7	1
8	1	8	28	56	70	56	28	8	1
9	1	9	36	84	126	126	84	36	9	1
10	1	10	45	120	200	252	200	120	45	10	1

 

2.5 Для конечного множества X доказать равенство .

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

Доказательство проведем методом математической индукции.

База. Если n=0, т. е. множество пусто, то у него только одно подмножество — оно само, и интересующее нас число равно 2⁰=1.

Индукционный шаг. Пусть утверждение справедливо для некоторого n и пусть X — множество с кардинальным числом n+1. Зафиксировав некоторый элемент a₀ ϵ X, разделим подмножества множества X на два типа:

1. X₁, содержащее a₀,
2. X₂, не содержащее a₀, то есть являющиеся подмножествами множества X-{ a₀}.

Подмножеств типа (2) по предположению индукции  . Но подмножеств типа (1) ровно столько же, так как подмножество типа (1) получается из некоторого и притом единственного подмножества типа (2) добавлением элемента   и, следовательно, из каждого подмножества типа (2) получается этим способом одно и только одно подмножество типа (1).

Следовательно имеем 2X=X1 U X2 и X1∩ X2 = O. По индукционному предположению | X1| = 2n и |X2| = 2n . Получаем |2X| = | X1|  + |X2| = 2n + 2n =2n+1 =2|x|  .

2.6 Доказать дистрибутивные законы

,

,

,

ассоциативный закон

и законы де Моргана для множеств и

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

1. дистрибутивных законов

μx	μy	μz	1)μx˄(μy˅μz)	(μx˄μy) ˅ (μx˄μz)	2) μx ˅ (μy˄μz)	(μx˅μy) ˄ (μz˅μz)	3)μx˄ (μy μz)	(μx˄μy) (μx˄μz)
0	0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0
0	1	1	0	0	1	1	0	0
1	0	0	0	0	1	1	0	0
1	0	1	1	1	1	1	1	1
1	1	0	1	1	1	1	1	1
1	1	1	1	1	1	1	0	0

 

2. ассоциативного закона

 

μx	μy	μz	μx (μy z)	(μx μy) μz
0	0	0	0	0
0	0	1	1	1
0	1	0	1	1
0	1	1	0	0
1	0	0	1	1
1	0	1	0	0
1	1	0	0	0
1	1	1	1	1

 

3. законов де Моргана для множеств и

μx	μy	1) ¬(μx˄ μy)	¬μx˅¬ μy	2)¬(μx˅ μy)	¬μx˄¬ μy
0	0	1	1	1	1
0	1	1	1	0	0
1	0	1	1	0	0
1	1	0	0	0	0

 

  2.7 Доказать тождества

.

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

Распишем левую часть: = X Y X Z = X (Y Z)

Распишем правую часть: = X ( Y Z)

Правая и левая части равны.

 

Распишем левую часть: = (X Y) (X Z) \ (X Z) =

= (X Y) ((X Z) (X Z)) = (X Y) ((X X Z) (X Z Z)) =

= (X Y) (X Z) =

Правая часть равна левой.

 

8.  Непосредственно по определению подсчитать числа Стирлинга для и .

Определение:

 Число разбиений n элементного множества ровно на k блоков называется числом Стирлинга 2 рода.

Результат расчета чисел Стирлинга для и приведен в таблице 2.

N\k	0	1	2	3	4
0	1	0	0	0	0
1	0	1	0	0	0
2	0	1	1	0	0
3	0	1	3	1	0
4	0	1	7	6	1

Таблица 2 –  числа Стирлинга

Подробный расчет:

S_n,0 = 0

S_3,1 =1

S_3,2 = 3  {1} {2,3} ; {2} {1,3}; {3} {1,2}

S_3,3= 1  {1} {2} {3}

 

2.9 Доказать соотношение .

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

  Если задано множество  из n > 0 объектов, которое должно быть разбито на k непустых блоков, то мы либо помещаем последний объект в отдельный класс, а оставшиеся n – 1 объект разбиваем на k – 1 блок способами, либо помещаем его в любой из k блоков, на которые разбиты n – 1 объект. В последнем случае имеется возможных вариантов, поскольку каждый из способов распределения первых n – 1 объектов по k непустым блокам дает k подмножеств, с которыми можно объединить n -ый объект. Имеем рекуррентную формулу:

=

2.10 Методом математической индукции доказать правило получения двоично-отраженных кодов Грея.

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

G₍₁₎ =   - двоично – отраженный код Грея

Пусть G_(n) = - код Грея для n

G_(n+1) =   - двоично – отраженный код Грея , отличается в одном разряде, ч.т.д.

 

 

 

 

 

3 Практическое  задание

3.1 Используя команды "randomize" и "rand", написать программу на Maple для генерации множества, содержащего не более 20 случайных элементов в диапазоне от 1 до 30.

> restart:

> randomize(): r := rand(1..30):

> X := {seq(r(),k=1..20)};

 Y := {seq(r(),k=1..20)};

 Z := {seq(r(),k=1..20)};

 

3.2 С помощью программы сгенерировать три множества X, Y, Z и с помощью команды "nops" найти число элементов в этих множествах.

> X := {seq(r(),k=1..20)}; cardX := nops(X);

 Y := {seq(r(),k=1..20)}; cardY := nops(Y);

 Z := {seq(r(),k=1..20)}; cardZ := nops(Z);

 

3.3 Используя команды "union", "intersect", "minus", "symmdiff", найти объединение, пересечение, разность, симметрическую разность множеств X, Y. Определить число элементов в полученных множествах.

> a:=X union Y;

b:=X intersect Y;

c:=X minus Y;

d:=symmdiff(X,Y);

carda := nops(a);

cardb := nops(b);

cardc := nops(c);

cardd := nops(d);

 

3.4 Найти дополнение множеств X, Y в множестве и вычислить число элементов в полученных множествах.

> Q:={seq(i,i=1..30)};

Q minus X;

Q minus Y;

cardX := nops(Q minus X);

cardY := nops(Q minus Y);

 

3.5 Используя команды "union", "intersect", "minus", "symmdiff", найти объединение, пересечение, симметрическую разность множеств X, Y, Z и вычислить . Определить число элементов в полученных множествах. Проверить соотношения из п.п. 2.6 и 2.7.

> a1:=X union Y union Z;

b1:=X intersect Y intersect Z;

c1:=symmdiff(X,Y,Z);

d1:=X minus Y minus Z;

carda1 := nops(a1);

cardb1 := nops(b1);

cardc1 := nops(c1);

cardd1 := nops(d1);

 

 

3.6 С помощью команды "subset" проверить соотношения: ,    .

> (X union Y subset X union Y union Z);

 (X intersect Y intersect Z subset X intersect Y);

 

3.7 С помощью команды "setpartition" найти все разбиения множества на подмножества, состоящие из одинакового числа элементов k, а числа k найти с помощью команды "factorset".

> with(numtheory):

with(combinat,setpartition);

F1:=X intersect Y intersect Z;

F:=factorset(nops(F1));

if nops(F)<>0 then

for l from 1 to nops(F)do 

print (setpartition(F1,F[l]))

end do;

else print ("Пустое")

end if;

 

 

 

3.8 Используя команды "binomial", "sum" и "Sum", получить в аналитическом виде формулу для суммы всех биномиальных коэффициентов (чисел сочетаний) при фиксированном числе n.

> Sum(binomial(n,k),k=0..n) = sum(binomial(n,k),k=0..n);

 

3.9 Используя команду "stirling2" найти числа Стирлинга второго рода для множества X при .

> with(combinat, stirling2);

> [seq([k,stirling2(nops(X),k)],k=1..cardX)]; cardX;

3.10 Используя команды "graycode", "convert", "binary" найти коды Грея для .

> n:=5;

with(combinat, graycode);

g:=graycode(n);

> [seq([g[k],convert(g[k], binary)],k=1..nops(g))];

> n:=6;

with(combinat, graycode);

g:=graycode(n);

> [seq([g[k],convert(g[k], binary)],k=1..nops(g))];