Національний технічний університет України

“Київський політехнічний інститут”

ФІОТ

АУТС

Контрольная работа №1

з курсу «Основи дискретної математики»

Виконав студент групи

Київ 2009

Тема 1.1

Вправа 1. Нехай маємо універсальну множину U = {a,b,c,d,e,f,g,h}. Необхідно задати об’єднання, перетин, різницю множин S та T, доповнення множини S до множини U, доповнення множини S  T до множини U.

Варіанти задання множин S та T:

1. S = {a,b,c}; T = {b,c,f}; 6) S = {g,d,f,a};T = {b,c,e};

2. S = {d,f,g}; T = {d,g,h}; 7) S = {a};T = {a,b,f,h};

3. S = {a,b,c,d};T = {d,e,f,g}; 8) S = {a,b,e,f};T = ;

4. S = {h,g,d};T = {a,b,d,g}; 9) S = U;T = {a,b,e,h};

5. S = {g,d,b,c};T = {b,c,d}; 10) S = U;T = .

Розв’язок:

S = {h,g,d};T = {a,b,d,g}

ST = {h,g,d,a,b}

SÇT = {g,d}

S \ T = {h}

S’ = {a,b,c,e,f}

(SÇT)’ = {a,b,c,e,f,h}

Вправа 2. Навести множину всіх підмножин множини S із вправи 1.

Розв’язок:

S = { h,g,d } {,{h},{g},{d},{h,g},{g,d},{h,d},{ h,g,d }}

Вправа 3. Нехай S та T - множини із вправи 1. Необхідно задати:

1. Функцію із множини S в множину T: а) довільну; б) ін’єктивну; в) сюр’єктивну; г) бієктивну.

Розв’язок:

S = { h,g,d };T = {a,b,d,g}

а) S  T : F₁ = {(h,a),(g,a),(d,b)}

б) S  T : F₂ ={(h,a),(g,b),(d,d)}

в) S  T : F₃ –не існує.

г) S  T : F₄ –не існує.

2. Довільну функцію із множини T в множину S.

Розв’язок:

S = {h,g,d};T = {a,b,d,g};

T  S : P₁ {(a,h),(b,g),(d,g),(g,d)}

3. Ліву та праву композиції функції із множини T в множину S та функції із множини S в множину T.

Розв’язок:

P₁ ◦ F₁ - не існує лівої композиції.

P₁ ◊ F₁={(h,g),(g,g),(d,g)} - ліва композиція;

4. Функцію із множини S в множину S.

Розв’язок:

S = {h,g,d};

S  S : K₁ = {(h,g),(g,d),(d,h)}

5. Тотожні функції 1_S та 1_T.

Розв’язок:

S = {h,g,d};T = {a,b,d,g};

1_S={(h,h),(g,g),(d,d)}

1_T={(a,a),(b,b),(d,d),(g,g)}

6. Обернену зправа та зліва для бієктивної функції із множини S в множину T.

Розв’язок:

S = {a,b,c,d};T = {d,e,f,g}

F₅ = {(a,d),(b,c),(c,f),(d,g)}

F₅ - бієктивна функція із множини S в множину T.

F’₅= {(d,a), (c,b), (f,c), (g,d)} – обернена зліва для функції F₅ ;

F’’₅= {(d,a), (e,b), (f,c), (g,d)} - обернена зправа для функції F₅ .

7. Обернену зправа та зліва для ін’єктивної, але не сюр’єктивної функції із множини S в множину T.

Розв’язок:

S = {h,g,d};T = {a,b,d,g}

F₆ = {(h,a),(g,b),(d,d)}

F₆ - ін’єктивна, але не сюр’єктивна функція із множини S в множину T.

F’₆= {(a,h), (b,g), (d,d)} – обернена зліва для функції F₆ ;

F’’₆ – оберненої зправа не існує.

8. Обернену зправа та зліва для сюр’єктивної, але не ін’єктивної функції із множини S в множину T.

Розв’язок:

S = {g,d,b,c};T = {b,c,d}

F₇ = {(g,b),(d,c),(b,d)}

F₇ - сюр’єктивна, але не ін’єктивна функція із множини S в множину T.

F’’₇= {(b,g), (c,d), (d,b)} – обернена справа для функції F₇ ;

F’₇ – оберненої зліва не існує.

Вправа 4. Чи для всіх пар множин S та Т із вправи 1 можливо задати бієктивну функцію із множини S в множину T?

Розв’язок:

Можна для : 1),2),3),9).

Не можна для : 4),5),6),7),8),10).

Вправа 5. Чи існують обернена зліва та справа функції для функції, яка не є ні ін’єктивною, ні бієктивною?

Розв’язок:

Як ми побачили у вправі 3(8), якщо при цьому функція є сюр’єктивною, то для неї існує лише обернена справа функція.

Якщо функція не ін’єктивна не бієктивна і не сюр’єктивна, розглянемо приклад:

S={a,b,c}, T={d,e,f}

F₈={(a,d),(b,d),(c,e)} – не ін’єктивна і не сюр’єктивна функція із множини S в множину T.

F’₈= {(d,a), (d,b), (e,c)} – обернена зліва для функції F₈ ;

F’’₈ – оберненої справа не існує.

Вправа 6. На довільних множинах задати функції такі, щоб серед них була сюр’єктивна, ін’єктивна, бієктивна.

Розв’язок:

A = {a,b,c,d}

B = {e,f,g,h}

Ін’єктивна : C = {(a,h),(b,e),(c,f),(d,g)}

Сюр’єктивна : C = {(a,f),(b,g),(c,h),(d,e)}

Бієктивна : C = {(a,e),(b,f),(c,g),(d,h)}

Вправа 7. Нехай Z - множина цілих чисел, z  Z . Встановити властивості функцій, які задані такими відображеннями:

a) z  z ² ; б) z  - z ; в) z  2 z ; г) z  z+1 ; д) z  |z| .

Розв’язок:

z  z ² - не ін’єктивна, не сюр’єктивна, не бієктивна;

z  - z - ін’єктивна, сюр’єктивна, бієктивна;

z  2 z - ін’єктивна, не сюр’єктивна, не бієктивна;

z  z+1 - ін’єктивна, сюр’єктивна, бієктивна;

z  |z| - не ін’єктивна, не сюр’єктивна, не бієктивна.

Вправа 8. Необхідно задати чи установити відсутність обернених зліва та зправа функцій для таких функцій, які задані на множині цілих чисел (х,у  Z):

1) y = x²; 2) y = x; 3) y = x³; 4) y = 2x;

5) y = x +1; 6) y = x² + x; 7) y = x⁴; 8) y = |x|.

Розв’язок:

y = f₀(y) = 2x . Ця функція ін’єктивна, не сюр’єктивна ( наприклад, число 3 не може бути значенням функції для жодного аргументу) і не бієктивна.

Ліву обернену функцію x= f₁(y); f₁: Z  Z для функції f₀ знаходимо з рівняння f₁ ◦ f₀ = 1_Z . Аналізуємо рівняння. Кожному цілому числу функція f₀ ставить у відповідність число в четвертому степені. Права частина рівняння вимагає відобразити цей степінь в вихідне число. Очевидно, це може забезпечити функція x= f₁(y) =y/2. Дійсно, підставляючи функцію f₁(y) у рівняння, впевнимося у тому, що воно обертається на тотожність.

Праву обернену функцію x= f₂(y) знаходимо, розв’язуючи рівняння f₀ ◦ f₂ = 1_Z . Природно, що функція x = y/2 претендує й на місце правої оберненої функції. Дійсно, підставляючи функцію f₂(y) у рівняння, впевнимося у тому, що воно обертається на тотожність.

Вправа 9. Нехай S та T - множини із вправи 1. Необхідно задати довільне бінарне відношення між множинами S та Т за допомогою: а) графіка; б) матриці.

Розв’язок:

S = {h,g,d};T = {a,b,d,g};

а) ST = {(h,a),(g,b),(d,d)}

h g d

a 1 0 0

б) ST = b 0 1 0

d 0 0 1

g 0 0 0

Вправа 10. Нехай задана множина Х. Необхідно задати за допомогою графіка відношення на Х: а) довільне; б) рефлексивне; в) симетричне; г) антисиметричне; д) транзитивне; е) таке, що мало б змістовну інтерпретацію.

Варіанти задання множини Х:

1) X = {1,2,3,4,5,6}; 2) X = {a,b,c,d,f};

3) X = {5,6,7,8,9,10}; 4) X = {000, 001, 010, 011, 100, 101, 110, 111}.

Розв’язок:

X = {000, 001, 010, 011, 100, 101, 110, 111}.

{(000,001),(001,010),(010,011),(011,100),(100,101)} - довільне

{(000,000),( 001,001),( 010,010),( 011,011)} - рефлексивне

{(000,001),(001,010),(001,000),(010,001)} - симетричне

{(000,000),(000,001),(001,001),(001,010),(001,011),(010,010),(011,011),(011,10 0),(010,100),(100,100),(100,101),(101,101)} - антисиметричне

{(000,001),(001,010),(010,011),(000,010),(000,011),(001,011)} - транзитивне

{(000,000), (000,001), (000,010), (000,011), (000,100), (000,101), (001,001), (001,011), (001,101), (010,010), (010,101), (011,011), (100,100), (101,101)}-це відношення можна задати, як відношення "x₁ ділить x₂ націло", де (x₁, x₂) - кожна пара з графіка відношення.

Вправа 13. Перевірити виконання властивостей а) комутативності, б) дистрибутивності, в) асоціативності, г) доповнення та д) подвійного доповнення операцій над множинами S та Т із вправи 1.

Розв’язок:

S = {h,g,d};T = {a,b,d,g};U = {a,b,c,d,e,f,g,h};R={b,g}

а) ST = TS

{h,g,d}{a,b,d,g}= {a,b,d,g}{h,g,d}

{a,b,d,g,h}={a,b,d,g,h}

SÇT = TÇS

{h,g,d}Ç{a,b,d,g} = {a,b,d,g}Ç{h,g,d}

{d,g}={d,g}

б) S(RÇT) = (SR)Ç(ST)

{h,g,d}({b,g}Ç{a,b,d,g}) = ({h,g,d}{b,g})Ç({h,g,d}{a,b,d,g})

{h,g,d}{b,g} = {h,g,d,b}Ç{h,g,d,b}

{h,g,d,b}= {h,g,d,b}

SÇ(RT) = (SÇR)(SÇT)

{h,g,d}Ç({b,g}{a,b,d,g}) = ({h,g,d}Ç{b,g})({h,g,d}Ç{a,b,d,g}

{h,g,d}Ç{b,g,a,d} = {g}{g,d}

{g,d} = {g,d}

в) S(RT) = (SR)T

{h,g,d}({b,g}{a,b,d,g}) = ({h,g,d}{b,g}){a,b,d,g}

{h,g,d}{a,b,d,g} = {h,g,d}{a,b,d,g}

{a,b,d,g,h} = { a,b,d,g,h }

SÇ(RÇT) = (SÇR)ÇT

{h,g,d}Ç({b,g}Ç{a,b,d,g}) = ({h,g,d}Ç{b,g})Ç{a,b,d,g}

{h,g,d}Ç{b,g} = {g}Ç{a,b,d,g}

{g} = {g}

г) SS’ = U

{h,g,d }{a,b,c,e,f,h} = {g,d,b,c,a,e,f,h}

SÇS’ = Ø

{h,g,d }Ç{ a,b,c,e,f,h} = Ø

д) (S’)’ = S

({h,g,d }’)’ = { a,b,c,e,f,h }’ = {h,g,d }

Вправа 14. Перевірити результати виконання операцій а) об’єднання та б) перетину множин S та Т вправи 1, коли в якості одного з операндів виступає множина U чи Ø.

Розв’язок:

S = {h,g,d};T = {a,b,d,g};U = {a,b,c,d,e,f,g,h};

а) SU = U

{h,g,d}{a,b,c,d,e,f,g,h} = {a,b,c,d,e,f,g,h}

SØ = S

{h,g,d}Ø = {h,g,d}

б) SÇU = S

{h,g,d}Ç{a,b,c,d,e,f,g,h} = {h,g,d}

SÇØ = Ø

{h,g,d}ÇØ = Ø

Вправа 15. Задати відношення часткового порядку на множині:

1) A = {a₁, a₂, a₃, a₄, a₅, a₆} ; 2) B = {b₁, b₂, b₃, b₄, b₅, b₆};

3) C = {c₁, c₂, c₃, c₄, c₅, c₆}; 4) D = {d₁, d₂, d₃, d₄, d₅, d₆};

5) E = {e₁, e₂, e₃, e₄, e₅, e₆}; 6) F = {f₁, f₂, f₃, f₄, f₅, f₆};

7) G = {g₁, g₂, g₃, g₄, g₅, g₆}; 8) H = {h₁, h₂, h₃, h₄, h₅, h₆};

9) I = {i₁, i₂, i₃, i₄, i₅, i₆}; 10) J = {j₁, j₂, j₃, j₄, j₅, j₆};

11) K = {k₁, k₂, k₃, k₄, k₅, k₆}; 12) L = {l₁, l₂, l₃, l₄, l₅, l₆};

13) M = {m₁, m₂, m₃, m₄, m₅, m₆};14) N = {n₁, n₂, n₃, n₄, n₅, n₆};

15) P = {p₁, p₂, p₃, p₄, p₅, p₆}; 16) R = {r₁, r₂, r₃, r₄, r₅, r₆}.

Розв’язок:

P = {d₁, d₂, d₃, d₄, d₅, d₆};

a₁={(d₁,d₁), (d₂,d₂), (d₃,d₃), (d₄,d₄), (d₅,d₅), (d₆,d₆), (d₁,d₂), (d₁,d₃), (d₁,d₄), (d₁,d₅), (d₁,d₆), (d₂,d₃), (d₂,d₄), (d₂,d₅), (d₂,d₆), (d₃,d₄), (d₃,d₅), (d₃,d₆), (d₄,d₅), (d₄,d₆), (d₅,d₆)}

a₁={(d₁,d₁), (d₂,d₂), (d₃,d₃), (d₄,d₄), (d₅,d₅), (d₆,d₆), (d₁,d₂), (d₁,d₃), (d₁,d₄), (d₁,d₅), (d₁,d₆), (d₂,d₄), (d₂,d₆), (d₃,d₅), (d₃,d₆), (d₄,d₆), (d₅,d₆)}

a₁={(d₁,d₁), (d₂,d₂), (d₃,d₃), (d₄,d₄), (d₅,d₅), (d₆,d₆), (d₁,d₂), (d₂,d₃), (d₁,d₃)}

a₁={(d₁,d₁), (d₂,d₂), (d₃,d₃), (d₄,d₄), (d₅,d₅), (d₆,d₆), (d₁,d₂), (d₂,d₃), (d₄,d₅), (d₄,d₆), (d₅,d₆)} є рефлексивними, антисеметричними, транзитивними; отже, ці відношення – відношення часткового порядку.

Вправа 25. Задати частковий порядок на множинах із вправи 15 та встановити межі та грані для підмножини, яка містить: а) перший, третій та п’ятий елементи; б) другий, третій та четвертий елементи.

Розв’язок:

P = {d₁, d₂, d₃, d₄, d₅, d₆};

Нехай P впорядкована за допомогою відношення {(d₁,d₁), (d₂,d₂), (d₃,d₃), (d₄,d₄), (d₅,d₅), (d₆,d₆), (d₁,d₂), (d₁,d₃), (d₁,d₄), (d₁,d₅), (d₁,d₆), (d₂,d₃), (d₂,d₄), (d₂,d₅), (d₂,d₆), (d₃,d₄), (d₃,d₅), (d₃,d₆), (d₄,d₅), (d₄,d₆), (d₅,d₆)}. Тоді для підмножини P_α = {d₁, d₃, d₅} верхні межі - d₅ , d₆, верхня грань - d₅, нижня межа та грань - d₁. А для підмножини P_б = {d₂, d₃, d₄} верхні межі - d₄, d₅, d₆, нижні - d₁, d₂, верхня грань - d₄, нижня - d₂.

Вправа 26. На кожній множині вправи 15 задати відношення часткового порядку, яке визначає решітку, але не перетворює множину у лінійно впорядковану.

Розв’язок:

P = {d₁, d₂, d₃, d₄, d₅, d₆};

{(d₁,d₁), (d₂,d₂), (d₃,d₃), (d₄,d₄), (d₅,d₅), (d₆,d₆), (d₁,d₂), (d₁,d₃), (d₁,d₄), (d₁,d₅), (d₁,d₆), (d₂,d₃), (d₂,d₄), (d₂,d₅), (d₂,d₆), (d₃,d₄), (d₃,d₅), (d₃,d₆), (d₄,d₅), (d₄,d₆), (d₅,d₆)}

Вправа 32. Частково впорядковані множини задані діаграмами Хассе. Необхідно встановити для кожної з частково впорядкованих множин, чи є вона решіткою. Якщо відповідь негативна, то обгрунтувати її. Варіанти діаграм Хассе:

Розв’язок:

6) Решітка – це частково впорядкована множина, кожні два элементи якої мають нижню і верхню грані.

Тому, в моєму випадку частково впорядкованих множина буде решіткою.

Вправа 36. Задати розбиття множин із вправи 15.

Розв’язок:

P = {d₁, d₂, d₃, d₄, d₅, d₆};

Розбиттям є множина підмножин P₁ = {d₁, d₂, d₃}, P₂ = {d₄, d₅, d₆}. Дійсно, виконуються умови P₁  P₂ = {d₁, d₂, d₃, d₄, d₅, d₆} = P, P₁ ∩ P₂ = Ø.

Вправа 37. Для відношень еквівалентності, заданих на множинах вправи 15, побудувати визначені ними розбиття.

Розв’язок:

P = {d₁, d₂, d₃, d₄, d₅, d₆};

Тоді відношення еквівалентності {(d₁,d₁),(d₂,d₂),(d₃,d₃),(d₁,d₂),(d₂,d₁),(d₁,d₃),(d₃,d₁),(d₂,d₃),(d₃,d₂),(d₄,d₄),(d₅,d₅),(d₆,d₆),(d₄,d₅), (d₅,d₄),(d₄,d₆),(d₆,d₄),(d₅,d₆),(d₆,d₅)}, задане на множині P, визначає розбиття {P₁, P₂}, де P₁ = {d₁, d₂, d₃}, P₂ = {d₄, d₅, d₆}. При формуванні підмножин розбиття включаємо в неї елементи p_i та p_j тоді і тільки тоді, коли в відношенні є пара (p_i, p_j).

Вправа 38. Для розбиттів, заданих на множинах вправи 15, побудувати відповідні відношення еквівалентності.

Розв’язок:

P₁ = {d₁, d₂, d₃}, P₂ = {d₄, d₅, d₆}

{(d₁,d₁),(d₂,d₂),(d₃,d₃),(d₁,d₂),(d₂,d₁),(d₁,d₃),(d₃,d₁),(d₂,d₃),(d₃,d₂),(d₄,d₄),(d₅,d₅),(d₆,d₆),(d₄,d₅),(d₅,d₄), (d₄,d₆),(d₆,d₄),(d₅,d₆),(d₆,d₅)} – відношення еквівалентності.