Роздрукувати сторінку
Главная \ Методичні вказівки \ Методичні вказівки \ 2884 Контрольна робота з навчальної дисципліни Дискретна математика, НАУ

Контрольна робота з навчальної дисципліни Дискретна математика, НАУ

« Назад

2884 Контрольна робота з навчальної дисципліни Дискретна математика, НАУ

НАЦІОНАЛЬНИЙ АВІАЦІЙНИЙ УНІВЕРСИТЕТ

Навчально-науковий інститут Комп’ютерних інформаційних технологій

Інститут заочного та дистанційного навчання

Кафедра прикладної інформатики 

 

Контрольна робота з навчальної дисципліни Дискретна математика

  

Галузь знань: 0501 «Інформатика та обчислювальна техніка»

Напрям підготовки: 6.050101 «Комп’ютерні науки»

  

Київ-2015

ТЕОРЕТИЧНА ЧАСТИНА 

  1. Логіка висловлювань.

  2. Основні логічні операції.

  3. Основні  тотожності математичної логіки.

  4. Тотожні перетворення логічних виразів.

  5. Логічні функції.

  6. Двоїстість.

  7. Нормальні і досконалі форми.

  8. Методи мінімізації логічних функцій.

  9. Логіка предикатів.

  10. Множини. Поняття, приклади.

  11. Операції над множинами.

  12. Що таке кола Ейлера?

  13. Що таке універсум?

  14. Що таке підмножина? Наведіть приклади.

  15. Основні  тотожності теорії множин.

  16. Сформулюйте комутативні закони алгебри множин.

  17. Сформулюйте асоціативні закони алгебри множин.

  18. Сформулюйте дистрибутивні закони алгебри множин.

  19. Сформулюйте закони самопоглинання алгебри множин.

  20. Сформулюйте закони поглинання алгебри множин.

  21. Сформулюйте теореми де Моргана алгебри множин.

  22. Відповідності і відношення.

  23. Функціональні відношення.

  24. Відношення еквівалентності.

  25. Відношення порядку.

  26. Потужність множин.

  27. Теорія Кантора.

  1. Що називається об’єднанням відношень? Навести приклади.

  2. Що називається перерізом відношень? Навести приклади.

  3. Що називається різницею відношень? Навести приклади.

  4. Що називається диз’юнктивною сумою відношень? Навести приклади.

  5. Що називається доповненням відношення? Навести приклади.

  6. Що називається відношенням, симетричним до даного відношення?

  7. Що називається композицією двох відношень?

  8. Яке відношення називається рефлексивним? Навести приклади.

  9. Яке відношення називається антирефлексивним? Навести приклади.

  10. Яке відношення називається симетричним? Навести приклади.

  11. Яке відношення називається асиметричним? Навести приклади.

  12. Яке відношення називається антисиметричним? Навести приклади.

  13. Яке відношення називається транзитивним? Навести приклади.

  14. Що називається відображенням?

  15. Яке відображення називається сюр’єктивним?

  16. Яке відображення називається ін’єктивним?

  17. Яке відображення називається бієктивним?

  18. Що називається композицією відображень?

 

ПРАКТИЧНА ЧАСТИНА 

Логіка висловлювань

1. Для функцій, що реалізовані формулами побудувати таблиці істинності (зробити по 2 завд.):

2. Визначити значення функції, яка реалізована формулою , на наборах (0, 0, 1), (1, 1, 0), (1, 1, 1) (зробити по 2 завд.):

3. Представити у вигляді ДДНФ і ДКНФ функції та зробити їх спрощення(зробити по 2 завд.):

4. Для спрощеної функції побудувати комутаційну схему. 

Множини

Завдання 1. (зробити по 3 завд.). Дані множини А, В, С. Знайти: I) АÇ(ВÈС); II)АÈ(ВÇС); III)(АÈВ)ÇС; IV)(АÇС)È(АÇВ); V) (АÈС)ÇВ; VI) (АÇВ)ÈС, якщо:

№ вар.

Множини А, В, С

№ вар.

Множини А, В, С

1

А={2; 3; 8; 9}, В={16; 18; 20}, C=N

11

A=N, B=Z, C={-1; 0; 1}

2

A=N, B={-2; -1; 0; 1; 2}, C={3; 5; 7}

12

A={1; 3; 5; …}, B={2; 4; 6; …}, C=N

3

A={3; 4; 5; …}, B=N, C={-1; 0; 1; 2}

13

A=Z, B=N, C={3; 6; 9; …}

4

A={21; 22; …; 26}, B={3; 5}, C=N

14

A={1; 3; 5;…}, B={2; 4; 6;…}, C= N

5

A=Z, B={2; 4; 6}, C=N

15

A=[2; 3], B=(0; 4], C={1; 2; 3; 4}

6

A={20}, B={2; 3; 4; 5}, C={5; 6; …; 10}

16

A=(2; 5), B=(0; 6], C=[-1; 3)

7

A=N, B={-1; 0; 1; 2}, C={15; 16; …; 20};

17

А=(0;2], В=[-1; 3], С=(-3; 6)

8

A=Z, B=N, C=Q

18

А=(-3; 6), В=[0; 4), С=[2; 7]

9

А={-1; 0; 1; 2}, В={2; 3; 4}, C= N

19

А=[0; 3), В=[-2; 4]; С=(-1; 1);

10

А={2; 3; 4}, B={3; 6}, C=N

20

А=[2; ¥), В=(-3; 4], С=(0; 6)

 

Завдання 2. (зробити по 3 завд.).  Дані множини А, В, С. Зобразити за допомогою кругів  Ейлера наступні множини, якщо АÍU, BÍU, CÍU, АÇВÇС¹Æ.

№ вар.

Множини А, В, С

№ вар.

Множини А, В, С

1

АÇВÇС

11

 

2

(АÇВ)ÇС

12

 

3

(АÈВ)ÇС

13

 

4

АÈВÈС

14

 

5

(АÇВ)È(АÇС)

15

 

6

АÈ(ВÇС)

16

 

7

(АÇС)ÈВ

17

 

8

 

18

 

9

 

19

(АÇВ)\С

10

 

20

(А\C) ÈB

 

Завдання 3. (зробити по 3 завд.). Знайти різницю А\В та В\А множин А і В, якщо:

№ вар.

Множини А, В

№

вар

Множини А, В

1

А={1; 2; 3; …; 10}, B={5; 6; …; 12}

11

A=(-2; 1), B=[0; 3)

2

A={x|xÎR, 2£x£6}, B={ x|xÎR, 3£x£7}

12

A=N, B=[0; 4]

3

A={x|xÎR, 1<x£4}, B={ x|xÎR, 2<x£8}

13

A=(0; 2), B=N

4

A={x|xÎR, 0<x<2}, B={ x|xÎR, 1<x£3}

14

A=No, B=[0; 5)

5

A={x|xÎR, -2<x<3}, B={ x|xÎR, 0<x<5}

15

А=N, B={2; 4; 6; …2n; …}

6

A={x|xÎR, -¥<x£2}, B={ x|xÎR, 1£x<5}

16

A=Z, B=N

7

A={x|xÎR, -¥<x<5}, B={ x|xÎR, 0<x£6}

17

A={x|xÎR, -¥<x<5}, B={ x|xÎR, 1£x£2}

8

A=[3; 5], B=[4; 8];

18

A=(-¥; ¥), B=(-2; ¥)

9

A=(3; 6), B=(4; 8]

19

A=No, B=N

10

A=(3; 8), B=(2; 9];

20

А=Q, B=

 

Завдання 4. (зробити по 3 завд.).  Знайти декартовий добуток множин А та В і зобразити їх елементи на координатній площині, якщо:

№ вар.

Множини А, В

№ вар

Множини А, В

1

A={1; 2; 3}; B={3; 4}

11

A=(-3; 2], B=[-1; 4]

2

A={3}, B=(2; 5)

12

A=Z, B=[2; 5]

3

A={1; 2; 3}, B=Z

13

A=[-1; 1], B=(-2; 3)

4

A=Z, B=N

14

A=[-3; 1), B=(-2; 2)

5

A=N, B=(3; 4]

15

A=(-1; 3], B=R

6

A=[-1; 3],B=[2; 4]

16

A=(-1; 1), B=(1; 3]

7

A=Z, B=(2; 5)

17

A=R, B=[-2; 1)

8

A=Z, B=[-2; 2]

18

A=(-1; 1), B=(1;2)

9

A=[-1; 1), B=[-2; 3];

19

A=R, B=(-2; 2)

10

A=[2; 4], B={4}

20

A=[-3; 1), B={1; 2}

 

Відношення та відображення 

Завдання 1.(зробити всі завд.) На рис.1 зображені приклади бінарних відношень. Чи є вони відображеннями? Якщо так, опишіть їхній тип.

Завдання 2. (зробити по 3 завд.).  Вказати, які з властивостей – рефлексивність, симетричність, антисиметричність, транзитивність – має відношення R на множині A, де:

  1. A={1, 2, 3, 4}, R={(1,1), (2,2), (3,3), (4,4), (1,2), (2,3), (2,1), (3,2), (1,3), (3,1)};

  2. A={1, 2, 3, 4}, R={(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (3,4), (4,3)};

  3. A={1, 2, 3, 4}, R={(1,1), (2,2), (3,3), (4,4), (2,3), (2,4), (3,2), (4,2), (3,4), (4,3)};

  4. A={1, 2, 3, 4}, R={(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (1,4)};

  5. A={1, 2, 3, 4}, R={(1,1), (2,2), (3,3), (4,4), (1,2)};

  6. A={1, 2, 3, 4}, R={(1,1), (2,2), (3,3), (4,4), (1,2), (2,3), (4,1), (1,4)};

  7. A={1, 2, 3, 4}, R={(1,1), (2,2), (3,3), (1,2), (2,1), (1,3)};

  8. A={1, 2, 3, 4}, R={(1,1), (2,2), (3,3), (1,2), (2,3), (3,1)};

  9. A={1, 2, 3, 4}, R={(1,1), (2,2), (3,3), (1,2), (2,3), (1,3), (3,2)};

  10. A={1, 2, 3}, R={(1,1), (2,2), (3,3), (1,2), (2,1)};

  11. A={1, 2, 3}, R={(1,1), (2,2), (3,3), (1,2), (2,3), (1,3)};

  12. A={1, 2, 3}, R={(1,1), (2,2), (3,3), (1,3), (3,1)};

  13. A={1, 2, 3}, R={(1,1), (2,2), (3,3), (1,3), (3,2)};

  14. A={1, 2, 3}, R={(1,1), (2,2), (3,3)};

  15. A={1, 2, 3}, R={(1,1), (2,2), (3,3), (1,2)};

  16. A={1, 2, 3}, R={(1,1), (2,2), (1,2), (2,1)};

  17. A={1, 2, 3}, R={(1,1), (3,3), (1,2), (2,3)};

  18. A={1, 2, 3}, R={(1,1), (2,2), (3,3), (1,2), (2,1), (2,3)};

  19. A={1, 2, 3, 4, 5}, R={(1,2), (1,3), (1,4), (2,5), (3,5), (4,5)};

  20. A={1, 2, 3, 4, 5, 6}, R={(1,2), (1,3), (3,4), (3,5), (4,6), (5,6)};

  

Завдання 3. Задане відображення, яке здійснює функція. На яких множинах вона буде повністю визначена і на яких – частково визначена?

Завдання 4.  Які з відношень

{(6,3),(2,1),(0,3),(4,5)};

{(2,3),(4,7),(0,1),(6,5)};

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

{(6,1),(0,3),(4,1),(0,7)(2,5)},

заданих на множинах  і  , є функціями і якого типу? (Рис.2).

Завдання 5.  При відображенні  задані відношення: 

Чи є серед них функції і якого вони типу?

 

Завдання 6. При відображенні  задані відношення: 

 Чи є серед них функції і якого вони типу?

 

Потужність множини 

1. У групі з 10 туристів шість вміють визначати напрямок на північ, п’ять розуміють карту і четверо вміють і те і інше. Скільки людей мають шанс заблукати навіть із картою (тобто не вміють нічого)? 

2. |А|=10, |В|= 15, |АΔВ|=4

|А∩В|=?  |АUВ|=? 

3. На контрольній присутні 40 студентів. Їм запропоновано розв’язати одну задачу з математичного аналізу, одно з аналітичної геометрії, та одне диференціальне рівняння. Результати були наступні: Задачу з математичного аналізу розв’язали 20 чоловік (), Задачу з аналітичної геометрії розв’язали 18 чоловік (), Диференціальне рівняння розв’язали 18 чоловік ().При цьому: Задачі з математичного аналізу та аналітичної геометрії розв’язали 7 чоловік (); Задачу з математичного аналізу та диференціальне рівняння розв’язали 8 чоловік (); Задачу аналітичної геометрії та диференціальне рівняння розв’язали 9 людей (). Відомо, що жодної задачі не розв’язали троє. а)Скільки студентів розв’язали всі три задачі ?

б) Скільки студентів розв’язало рівно по дві задачі? 

4. Під час підготовки до іспиту 40 студентів використовували книги  і . При цьому книгою  користувалися 25 студентів, книгою  – 22 студенти, книгою  – також 22, книги  або  () – 33 студенти,  – 32 студенти,  – 31 студент,  – 10 студентів. а) Скільки студентів готувались до іспиту лише по книзі , лише по книзі , лише по книзі ?  б) Скільки студентів при підготовці до іспиту не використовували жодної з трьох книг? 

5. Кожен із студентів групи під час зимових канікул рівно 2 рази був в театрі. При цьому спектаклі  і  дивились відповідно 20, 10, 18 студентів. а) Скільки студентів в групі? б) Скільки з них бачили спектаклі  і ,   і ,  і ? 

6. З чотирьох завданнь перше зробили 5 студентів, друге  - 10, третє - 15, четверте – 6. Кожен студент зробив рівно три завдання. Скільки було студентів? 

7. Є 10 страв у меню ресторана. Скільки різних замовлень можна зробити (кожну страву можна замовити тільки 1 раз)? 

8. Є 10 співробітників і 20 обов’язків. Скільки існує впорядкованих пар типу
(співробітник; список_обов’язків), якщо кожен може виконувати будь-який набір обов’язків (у тому числі нуль)? 

 

Список рекомендованих джерел

Основні

1. Капітонова Ю.В.,Кривий С.Л.,Летичевський О.А., Луцький Г.М., Печурін М.К.,  Основи дискретної математики. Підручник. К.: Наукова думка. – 2002. – 256 с.

2. Балдачов Ю.М., Соколова Н.А., Ходаков В.Є. Дискретна математика. К.: Вища школа. – 2002. - 467 с.

3. Лекции по теории графов // Емеличев В.А., Мельников О.И., Савранов В.И., Тышкевич Р.И. М.: Наука. –1990. - 382 с.

4. Кук Д.,  Бейз Е.  Компьютерная математика. - М.: Наука. –1999.– 384 с.

Додаткові

5. Харари Ф. Теория графов.- М.: МИР.- 1993.- 290 с.

6. Емельянов В. В., Ясиновский С. И. Введение в интеллектуальное имитационное моделирование сложных дискретных систем и процессов. Язык РДО. — М.: АНВИК, 1998. - 427с.

7. Заболотский В. П., Оводенко А. А., Степанов А. Г. Математические модели в управлении: Учеб. пособие. - СПб.: СПбГУАП, 2001. - 196 с.

З повагою ІЦ "KURSOVIKS"!