Лабораторна робота №2
Тема роботи:Множина.
Мета роботи: Перевірка основних співвідношень алгебри множин. Декартове множення.
Теоретичні відомості
Декартове множення
Нехай множина А складається з р елементів, а множина В – з н елементів. Декартовим множенням А×В є множина, що складається з усіх впорядкованих пар елементів (а,в), де а є А і в є В. Множина А×В має в своєму складі р·н елементів.
x
A × B 
Задачі на теорію множин
Задача 1:Генерація всіх підмножин даної n-елементної множини {0,.., n-1}.
Рішення:
Уведемо масив B[0..n] з (n+1) елементами. B[і]=0, якщо i-ий елемент у підмножину не входить, і B[i]=1 інакше. Таким чином бачимо зв'язок підмножини з двійковим представленням числа.
Алгоритм: будемо генерувати числа від 0 до 2n-1, знаходити їх двійкове представлення, і формувати підмножину з елементів з індексами бітів, рівних 1 у цьому представленні. Якщо число 2n-1 може не поміститися в розрядну сітку машини - генерацію будемо проводити, використовуючи масив B. Спочатку B[i]=0 для всіх i, що відповідає порожній підмножині. Будемо розглядати масив B як запис двійкового числа B[N]...B[1]B[0], і моделювати операцію додавання цього числа з одиницею. При додаванні будемо переглядати число з кінця замінюючи одиничні біти нулями доти, поки не знайдемо нульовий біт, у який занесемо 1.
Генерація підмножин закінчується, як тільки B[N]=1.
Приклад реалізації на мові Паскаль:
while B[N]<>0 do
begin
і:=0; { індекс біта двійкового числа }
while (B[і]=1) do
begin
B[і]:=0; { моделюємо перенос у наступний розряд, }
і:=і+1 { виникаючий при додаванні }
end;
B[і]:=1;
{ Роздруковуємо індекси одиничних елементів масиву B
-нова сгенерована підмножина }
For і:=0 to N-1 do
if B[і]=1 then write(і);
writeln; { перехід на новий рядок при печаті }
end;
Розробити програму на мові С і протестувати на символах зі свого ім’я.
====================================================================
Задача 2. Довести:
Рішення:
Нехай
====================================================================
Задача 3.Спростити вираз:
Рішення:
====================================================================
Задача 4.Довести
Рішення:
Нехай
====================================================================
Задача 5.Довести:
Рішення:
====================================================================
Задача 6.Довести:
A ∆ (B ∆ C) = (A ∆ B) ∆ C
Рішення:
Нехай
/
*
- всі елементи в А, яких нема в В*/
=>
/*
- правило де Моргана/
( A*
)
*
+ (( B *
)
+ (C *
)
*
)=>( A*(
)
*
+ ( B *
)
+ (C *
)
*
/*
- правило де Моргана/
0 0
0 0
====================================================================
Задача 7.Доведіть рахунковість множини усіх цілих чисел.
Нехай А и В – множини. Взаємно однозначною відповідністю (ВОВ) А на В називається усяка функція f: А->У, що задовольняє умовам:
f визначена на всій множині А
множина її значень збігається з У
f ін’єктивна, тобто a1,a2 A[a1a2 f(a1)f(a2)]
Множини А и В називають еквівалентними (А~В), якщо існує ВОВ f:А->В, а А рахунковою, якщо А~N, де N – усі натуральні числа. Рахунковість множини А означає, що всі її елементи можна занумерувати (без повторювань) натуральними числами.
Множина Z усіх цілих чисел рахункова таким засобом:
…,-2,-1,0,1,2,…
…,а4,а2,а0,а1,а2,…
====================================================================
Задача 8.Доведіть: усяка нескінченна множина містить рахункову підмножину.
Доказ: Множина А нескінченна, і тому очевидно не порожня. a0A. Але, будучи , А не вичерпується підмножиною {a0}A. Значить a1A-{a0}. Але, у силу А, воно не вичерпується підмножиною {a0,a1}A. Значить a2A-{a0,a1} і т.д. Таким чином, можемо перерахувати а -> підмножина {a0,a1,a2,…}А міститься в А и є рахунковим.
====================================================================
Задача 9. Доведіть, якщо А і В рахункові, то рахункова і множина АВ.
Доведемо рахунковість множини АВ:
Через рахунковість множин А и В маємо:
А={a0, a1, a2,…}
В={b0, b1, b2,…}
Покладемо cn=ak, якщо n=2k і cn=bk, якщо n=2k+1.
Тоді АВ={cnnN}, причому всі елементи цієї множини занумеровані натуральними числами, чим і доведена його рахунковість.