Типові практичні завдання

1. Нехай множина перших 20 натуральних чисел - це універсум. Запишіть такі його підмножини: А – підмножина парних чисел; В – підмножина непарних чисел; С – підмножина квадратів чисел; D – підмножина простих чисел.

2. Чи рівні між собою множини А та В (якщо ні, то чому?): а) A={2, 5, 4}, B={5, 4, 2}; б) A={1, 2, 4, 2}, B={1, 2, 4}; в) A={2, 4, 5}, B={2, 4, 3}; г) A={1, {2, 5}, 6}, B={1, {5, 2}, 6}; д) A={1, {2, 5}, 6}, B={1, 2, 5, 6}?

3. Нехай , . Знайти , , .

4. Нехай - множина натуральних чисел, - множина натуральних чисел та 0. Знайти , , , , .

5. Які з наведених нижче співвідношень невірні и чому?

а) ; б) ; в) ; г) .

6. В яких відношеннях знаходяться між собою такі три множини: А={1, 3}; B – множина непарних додатних чисел; С - множина рішень рівняння ?

7. Нехай , . Знайти , .

8. Используя диаграммы Венна, покажите равенства двух множеств .

9. Для каждого из приведенных ниже множеств используйте диаграммы Венна для двух множеств и заштрихуйте те её части, которые изображают заданные множества: а) ; б) ; в) .

10. Визначити та навести зображення множин якщо множини задані як .

11. Дати оцінку справедливості рівняння. Відповідь підтвердити діаграмами Ейлера: .

12. Спростити вираз .

13. Нехай ={2, 3} и ={3, 4, 5, 6}. Визначити декартов добуток , відношення «бути дільником», відношення «рівність» (=), відношення , області визначення і значення відношення .

14. Нехай ; і

.

Знайти переріз відношення за елементами .

Знайти переріз відношення за підмножиною .

15. Нехай є два відношення

і .

Знайти композицію , переріз .

16. Нехай і нехай відношення є множина

Показати, що відношення є відношенням еквівалентності.

17. Нехай і нехай визначено у вигляді

. Чи є відношення відношенням еквівалентності?

18. Для відношення еквівалентності, яке задається класами еквівалентності ; ; , знайти матрицю еквівалентності.

19. Для відношення нестрогого порядку «бути дільником» на множині знайти матрицю відношень.

20. Знайти матрицю відношення строгого порядку «»на множині .

21. Визначте, які властивості мають відношення, що задаються на деякій множині людей. Нехай , якщо:

а) вище зростом, ніж ;

б) і народилися в один день;

в) є родичем ;

г) знайомий з .

22. В множині задані відношення:

а) {(1, 2), (2, 3), (2, 4), (3, 2), (5, 1)};

б) {(2, 1), (3, 4), (4, 4), (5, 3)};

в) {(1, 2), (2, 3), (3, 2), (4, 3), (5, 1)};

г) {(1, 2), (2, 3), (4, 1), (4, 5), (5, 5)};

д) {(1, 5), (2, 1), (3, 4), (4, 3), (5, 2)}.

Які з цих відношень є функціями, а які – відображеннями?

23. Які з наведених відношень в множині дійсних чисел є функціями?

а) { };

б) { };

в) { };

г) { }.

24. Нехай , . Визначити, чи є наведені відношення між елементами і всюди визначеними, сюр’єктивними, функціональними, ін’єктивними, взаємно однозначним:

а) ;

б) ;

в) .

25. Скільки способів існує для того, щоб вибрати три різних фарби з п’яти?

26. Скількома способами можна скласти трикольоровий смугастий стяг, як що є п’ять матеріалів різних кольорів?

27. Скільки словників треба видати, щоб можна було виконати безпосередній переклад з п’яти мов (російської, української, англійської, французької, німецької) на любу з п’яти мов.

28. У одного студента є 7 книг з математики, а у другого студента – 9 книг. Скількома способами вони можуть обміняти книгу одного на книгу другого?

29. Наукове товариство складається з 25 чоловік. Треба вибрати президента, вченого секретаря, скарбника. Скількома способами це можна зробити, якщо кожний член товариства посідає тільки один пост?

30. На диск секретного замка нанесено 12 літер. Секретне слово складається з 5 літер. Скільки невдалих спроб може бути зроблено людиною, яка не знає секретного слова?

31. В цеху є 9 вільних робочих місць, 2 з яких можуть посідати тільки жінки, 3 – тільки чоловіки, а 4 чоловіки та жінки. Скількома способами можна розподілити 3-х жінок та 4-х чоловіків по робочих місцях?

32. Скількома способами можна впорядкувати множину так, щоб числа 1, 2, 3 стояли поруч і в порядку зростання?

33. На зборах мають виступати 4 особи А, В, С, Д. Скількома способами їх можна розташувати в списку ораторів, якщо В не може виступати до того часу, поки не виступить А?

34. Скількома способами можна розсадити дев’ять пасажирів у три вагони щоб: а) у кожний вагон сіло три пасажири; б) у пронумеровані вагони: у перший – чотири пасажири; у другий – три і в третій – два?

35. У ліфт семиповерхового будинку ввійшли три чоловіки. Скільки існує способів вийти: а) усім на однім поверсі; б) одночасно на будь-якому поверсі; в) усім на різних поверхах; с) усіляких комбінацій?

36. При ; ; ; знайти значення функцій: 1) ; 2) .

Скласти таблицю відповідності для формули .

37. Визначити, чи є наступні формули загальнозначущими, суперечливими та несуперечливими:

а) ;

б) ;

в) .

38. Скласти таблицю відповідності для формул і .

39. Перевірить за допомогою таблиць відповідності такі тотожності:

а) = ; б) .

40. Знайдіть ДДНФ формули .

41. За допомогою еквівалентних перетворювань привести до ДНФ такі формули: а) ; б) .

42. За допомогою співвідношень виду перетворити ДНФ у КНФ.

43. Перевірить за допомогою таблиць відповідності такі тотожності:

а) = ; б) ; в) = .

44. Визначити, які з даних речень є висловлюваннями: «Волга уливається в Чорне море», «Волга уливається в Каспійське море», «Який сьогодні день?», «Відстань від Землі до Сонця дорівнює 150000000 км».

45. Записати в символічній формі такі висловлювання:

а) У мене не сучасний комп’ютер або я закінчу проект вчасно.

б) Невірно, що я закінчу проект вчасно та складу іспит.

в) У мене не сучасний комп’ютер або я не закінчу проект вчасно та складу іспит.

46. Записати у вигляді формули логіки висловлювань та визначити істинне значення таких висловлювань:

а) «Для того що би , необхідно і достатньо, що би »;

б) « рівносильно тому, що ».

47. Записати у вигляді формули логіки висловлювань та визначити істинне значення таких висловлювань:

а) «6 ділиться на 3, і 10 більше ніж 5»;

б) «6 ділиться на 3, і 7 більше ніж 10».

48. Показати, що висловлювання є логічним слідством висловлювання .

49. Дано істинне висловлювання «Якщо ділиться на 9, то ділиться на 3». Нехай також звісно, що « ділиться на 9». Який висновок можна зробити з цих двох висловлювань?

50. Чи є наступні формули загальнозначущими, суперечливими та несуперечливими:

а)

б)

в)

г)

51. Побудуйте складні висловлювання з використанням тільки таких операцій: а) еквівалентність; б) імплікація і кон’юнкція; в) від’ємина, кон’юнкція та диз’юнкція.

52. Предметна область є множина дійсних чисел. Записати у вигляді виразу логіки предикатів математичне затвердження: «Для всіх вірно, що »; «Існує число, квадрат якого дорівнює 4».

53. Визначити, які змінні є зв’язними, а які – вільними в наведених формулах: а) ; б) ; в) .

54. Привести формулу к ВНФ.

55. Знайти степені кожної вершини графів (для орграфів вказати и ). Перевірити формулу розрахунку кількості ребер, використовуючи степені вершин графа. Запишіть матриці суміжності та інциденції.

3) 4)

8)

Знайти графи, які задаються такими матрицями суміжності та інциденції .

1.	2.	3.

5.	6.

56. Довести, що множина усіх ребер кінцевого зв’язного графа формує простий цикл тоді та тільки тоді, коли степені усіх вершин кратні 2.

57. Довести, що граф ейлерів тоді та тільки тоді, коли множину його ребер можна розбити на прості цикли (які попарно не перетинаються за ребрами).

58. Перелічить неізоморфні дерева з шістьома вершинами.

59. Перелічить кореневі дерева з п’ятьома деревами.

60. Яка кількість ребер остового дерева зв’язного графа з вершинами та ребрами.

61. Яка властивість є достатньою умовою для того, щоб довільний граф мав гамільтоновий цикл?