Контрольні запитання з дискретної математики PDF

1 КОНТРОЛЬНІ ЗАПИТАННЯ ЗА МАТЕРІАЛАМИ КУРСУ «ДИСКРЕТНА МАТЕМАТИКА» ТЕОРІЯ МНОЖИН 1. Що таке множина ? 2. Яку множину називають універсумом або універсальною множиною ? 3. Що таке булеан множини А ? 4. Що таке потужність скінченної...

1 КОНТРОЛЬНІ ЗАПИТАННЯ ЗА МАТЕРІАЛАМИ КУРСУ «ДИСКРЕТНА МАТЕМАТИКА» ТЕОРІЯ МНОЖИН 1. Що таке множина ? 2. Яку множину називають універсумом або універсальною множиною ? 3. Що таке булеан множини А ? 4. Що таке потужність скінченної множини ? 5. Яку множину називають об’єднанням двох множин ? 6. Яку множину називають перетином (перерізом) двох множин ? 7. Яку множину називають різницею множин А та В ? 8. Що таке доповнення множини В до множини А ? 9. Яку множину називають доповненням множини А ? 10. Яку множину називають симетричною різницею двох множин ? 11. Закони алгебри множин. 12. Що таке відповідність ? 12. Що таке упорядкована пара предметів ? 13. Яку множину називають декартовим добутком двох множин ? 14. Що таке бінарне (або двомісне) відношення ? 15. Які множини називають першою та другою проекціями відношення ? 16. Що таке переріз бінарного відношення R за підмножиною С першої базисної множини А ? 17. Який переріз називають перерізом бінарного відношення за елементом а ? 18. Що таке фактор-множина множини В за відношенням R ? 19. Операції над відношеннями.  2 19. Яке відношення називають рефлексивним ? Яка особливість матриці такого відношення ? 20. Яке відношення називають антирефлексивним ? Яка особливість матриці такого відношення ?. 21. Яке відношення називають симетричним ? Яка особливість матриці такого відношення ? 22. Яке відношення називають транзитивним ? 23. Яке бінарне відношення називають еквівалентним ? 24. Яке бінарне відношення називають відношенням порядку (порядком) на множині А ? 25. Операції над відношеннями. 26. Яке відношення називають оберненим відношенням до даного відношення ? 27. Що таке композиція відношень R та S ? 28. Яке бінарне відношення f називають функціональним ? 29. Яке функціональне відношення f, визначене на множинах А та В, називають функцією (відображенням) із А у В ? 30. Яку функцію називають цілком визначеною (тотальною) ? 31. Яку функцію називають сюр’єктивною ? 32. Яку функцію називають ін’єктивною ? 33. Яку функцію називають бієктивною ? КОМБІНАТОРНИЙ АНАЛІЗ 1. Правило суми. 2. Правило добутку. 3. Що таке вибірка? 4. Означення перестановки без повторень. Формула обчислення їх кількості.  3 5. Означення розміщення з n елементів по m. Формула обчислення їх кількості. 6. Означення комбінацій з n елементів по m. Формула обчислення їх кількості. 7. Основний алгоритм обчислення кількості перестановок, розміщень та комбінацій без повторень. ТЕОРІЯ ГРАФІВ 1. Що таке граф ? 2. Які вершини називають суміжними вершинами ? 3. Які ребра називають суміжними ? 4. Який граф називають орієнтованим графом або орграфом ? 5. Який граф називають неорієнтованим або н-графом ? 6. Яке ребро графа називають петлею ? 7. Які ребра в графі називають кратними ? 8. Який граф називають повним ? 9. Який граф називають мультиграфом ? 10. Який граф називають псевдографом ? 11. Який граф називають порожнім графом ? 12. Який граф називають доповненням даного графа ? 13. Що таке степінь вершини ? 14. Яку вершину називають ізольованою ? 15. Сформулюйте лему про рукостискання. 16. Чи вірне твердження: У будь-якому графі кількість вершин непарного степеня парна ? 17. Який граф називають підграфом заданого графа ? 18. Який граф називають кістяком (каркасом) заданого графа ? 19. Які графи називають рівними ?  4 20. Які графи називають ізоморфними ? 21. Що таке маршрут (шлях) у графі ? 22. Що таке довжина маршруту ? 23. Який маршрут називають ланцюгом ? 24. Який ланцюг називають простим ? 25. Який маршрут називають циклічним ? 26. Як називають циклічний маршрут, який є ланцюгом ? 27. Який циклічний маршрут називають простим циклом ? 28. Коли дві вершини графа називають зв’язаними ? 29. Який граф називають зв’язним ? 30. Яку вершину графа називають точкою зчленування(з’єднання) ? 31. Яке ребро графа називають мостом ? 32. Що таке шлях або орієнтований маршрут ? 33. Чому дорівнює довжина орієнтованого маршруту ? 34. Який шлях (маршрут) називають орієнтованим ланцюгом ? 35. Який шлях в орієнтованому графі називають простим ланцюгом ? 36. Який шлях в орієнтованому графі називають контуром ? 37. Який контур називають циклом ? 38. Який контур називають простим циклом ? 39. Який граф називають співвіднесеним графом орієнтованого графа ? 40. Який орієнтований граф називають зв’язним ? 41. Який орієнтований граф називають сильно зв’язним ? 41. У чому полягає операція вилучення вершини з графа ? 42. У чому полягає операція вилучення ребра з графа ? 43. Який граф називають об’єднанням двох графів ? 44. Який граф називають кільцевою сумою двох графів ? 45. Назвіть способи задання графів ?  5 46. Який граф називають двочастковим (біграфом) ? 47. Який граф називають повним біграфом ? 48. Що таке дерево ? 49. Що таке кістякове (каркасне) дерево ? 50. Що таке мінімальне кістякове дерево ? 51. Який граф називають зваженим ? 52. Який граф називають зваженим орієнтованим графом ? 53. Який шлях у графі називають ейлеровим шляхом ? 54. Який цикл у графі називають ейлеровим циклом ? 55. Який граф називають ейлеровим ? 56. Який граф називають напівейлеровим ? 57. За якої умови граф має ейлеровий цикл ? 58. За якої умови граф має ейлеровий шлях ? 59. За якої умови орієнтований слабко зв’язний мультиграф має ейлеровий цикл ? 60. Який шлях називають гамільтоновим шляхом ? 61. Який цикл називають гамільтоновим циклом ? 62. Який граф називають гамільтоновим графом ? 63. За якої умови граф має гамільтоновий цикл ? (Теорема Дірака) 64. Який граф називають лісом ? 65. Яке дерево називають кореневим ? 66. Яку вершину дерева називають листком ? 67. Яку вершину дерева називають внутрішньою ? 68. Що таке рівень вершини у кореневому дереві ? 69. Чому дорівнює висота орієнтованого дерева ? 70. Яке кореневе дерево називають упорядкованим ? 71. Яке кореневе дерево називають m-арним ? 72. Яке кореневе дерево називають повним m-арним ?  6 73. Яке кореневе дерево називають завершеним ? 74. Що таке потік ? 75. Що таке пропускна спроможність дуги ? 76. Які умови накладають на потік по дузі ? 77. Що таке потік на транспортній мережі ? 78. Яку дугу називають насиченою ? 79. Яку дугу називають ненасиченою ? 80. Який потік називають повним ? 81. Що таке розріз ( X , X ) ? 82. Чому дорівнює потік через розріз ( X , X ) ? 83. У чому суть задачі про максимальний потік ? 84. Яка теорема є основою розв’язку задачі про максимальний потік ? 85. Що називають околом вершини ? 86. Що називають неоколом вершини ? 87. Що таке граф досяжності ? МАТЕМАТИЧНА ЛОГІКА 1. Що таке логіка ? 2. Що таке висловлення ? 3. Яку множину називають областю істинності висловлення ? 4. Яке висловлення називають тотожно істинним ? 5. Яке висловлення називають тотожно хибним ? 6. Що таке заперечення (інверсія) висловлення х ? 7. Що таке диз’юнкція (логічне додавання) висловлювань x і y ? 8. Що таке кон'юнкція (логічне множення) висловлювань x і y ?  7 9. Що таке імплікація (наслідок) висловлювань x і y ? 10. Що таке еквівалентність (подвійна імплікація) висловлювань x і y ? 11. Що таке операція Жегалкіна (нерівнозначністю) ? 12. Що таке штрих Шеффера ? 13. Що таке стрілка Пірса ? 14. Що таке логічна формула ? 15. У чому полягає задача (проблема) розв’язності логічної формули ? 16. З яких елементів складається найпростіша булева алгебра ? 17. Що таке булева функція ? 18. Що таке елементарна кон’юнкція ? 19. Чому дорівнює ранг елементарної кон’юнкції ? 20. Що таке диз’юнктивна нормальна форма булевої функції ? 21. Яку функцію називають конституентою одиниці (мінтермом, імплікантою)? 22. Що таке досконала диз’юнктивна нормальна форма (ДДНФ) булевої функції? 23. Що таке елементарна диз’юнкція ? 24. Чому дорівнює ранг елементарної диз’юнкції ? 25. Що таке кон’юнктивна нормальна форма булевої функції ? 26. Яку функцію називають конституентою нуля (макстермом) ? 27. Що таке досконала кон’юнктивна нормальна форма (ДКНФ) булевої функції? 28. Що таке мінімальна ДНФ (МДНФ) булевої функції ? 29. Що таке проста імпліканта булевої функції ? 30. Що таке скорочена ДНФ (СДНФ) ? 31. Що таке тупикова ДНФ ?