Булеві функції та теорія множин

 

19. (2.2.1) З’ясуйте взаємне розміщення множин , якщо – довільні підмножини універсальної множини .

20. (2.2.2) Перевірте, що для довільних множин з виконання включення випливає виконання включення .

21. (2.2.3) Для довільних множин перевірте, чи є виконання включення необхідною і достатньою умовою виконання рівності .

22. (2.2.4) З’ясуйте, чи вірна рівність для довільних .

23. (2.3.2) Дано булеві функції .

1. З’ясуйте питання про рівносильність ДНФ зведенням їх до ДДНФ.

2. Отримайте ДДНФ функції , використовуючи метод розщеплення .

3. Перетворіть за допомогою дистрибутивних законів у КНФ, спростіть отриманий вираз.

24. (2.3.3) Булеву функцію задано векторно.

1. Знайдіть двома способами її поліном Жегалкіна.

2. Знайдіть ДДНФ.

3. Знайдіть ДКНФ.

 

МІНІМІЗАЦІЯ НОРМАЛЬНИХ ФОРМ

ВСЮДИ ВИЗНАЧЕНИХ БУЛЕВИХ ФУНКЦІЙ

 

25. (2.5.1) Дано булеву функцію .

1. Запишіть її ДДНФ та ДКНФ.

2. Методом Квайна знайдіть скорочену ДНФ.

3. Для скороченої ДНФ побудуйте матрицю Квайна, укажіть ядрові імпліканти.

4. За допомогою матриці Квайна знайдіть мінімальну ДНФ, укажіть її складність.

5. Знайдіть мінімальну ДНФ даної функції за допомогою карт Карно, порівняйте з результатом, отриманим у п. 4.

 

ПРЕДИКАТИ

 

26. (4.1.1) Побудуйте предикати змінних на множині такі, що виконується умова ( – множина всіх людей).

27. (4.1.2) Укажіть область визначення, кількість змінних і тип предиката, кожний аргумент якого приймає значення з множини .

28. (4.1.3) Знайдіть значення висловлювання , отриманого з предикати 3-х змінних, визначеного на множині .

29. (4.1.4) Предикати та визначені на множині .

1. Знайдіть предикат, рівносильний предикату та такий, що не містить кванторів.

2. З’ясуйте, чи може предикат бути виконуваним, але не тотожньо істинним.

 

КОМБІНАТОРИКА

 

30. (5.1.1) Скількома способами з колоди карт у 36 листів можна вибрати неупорядкований набір з 5 карт так, що б у цьому наборі було б точно:

31. (5.1.2) Скільки різних слів можна утворити перестановкою букв слова ?

32. (5.2.1) Знайдіть найбільший член розкладу бінома .

33. (5.2.2) З даної пропорції знайдіть та .

34. (5.2.3) Обчисліть задані суми.

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

36. (5.3.1) Скільки натуральних чисел від 1 до 1000 не ділиться ні на , ні на , ні на , ні на ?

37. (5.3.2) Підрахуйте кількість різних перестановок цифр даного числа , при яких жодні однакових цифр не ідуть одна за одною.

38. (5.3.3) Скільки існує перестановок різних предметів, при яких на своїх початкових місцях опиняться рівно або рівно предметів?

39. (5.4.1) Скількома різними способами можна розподілити різних листівок у

1. різних;

2. нерозрізнених конвертів, якщо:

а) все конверти непусті;

б) допускаються пусті конверти (розглянути 4 випадки).

40. (5.5.1) Наносяться цифр на різних шарів (на кожний шар пишемо рівно одну цифру), після чого шари вкладаємо у мішок. З мішка на удачу виймаємо шар, записуємо число, зображене на ньому, та повертаємо шар у мішок. Ця процедура повторюється разів. Скільки існує різних випадків, при яких сума виписаних чисел дорівнювала б ?

41. (5.5.2) Гральна кістка кидається разів. У скільки разів число способів набора суми у очок перевищує число способів набору суми у очок?

 

РЕКУРЕНТНІ СПІВВІДНОШЕННЯ

 

42. (5.6.1) Знайдіть загальний розв’язок рекурентного співвідношення 5-ого порядку .

43. (5.6.2) Знайдіть загальний розв’язок рекурентного співвідношення 5-ого порядку .

44. (5.6.3) Зайдіть загальний вигляд розв’язку рекурентного співвідношення 4-ого порядку , якщо .

45. (5.6.4) Знайдіть загальний розв’язок рекурентного співвідношення 5-ого порядку із заданими початковими умовами .

 

СИСТЕМНІ ЧИСЛА

 

46. Представте дане число у двійковій системі числення:

1.131	2.161	3.147	4.135
5.142	6.132	7.168	8.149
9.151	10.153	11.133	12.157
13.132	14.143	15.167	16.134
17.144	18.157	19.159	20.145

 

47. Знайдіть значення суми, різниці та добутку даного числа та числа 346₈:

1.76548	2.72128	3.75468	4.67548
5.75438	6.54378	7.27658	8.72178
9.54678	10.54178	11.51778	12.77658
13.27458	14.32778	15.73748	16.73768
17.54768	18.35468	19.47568	20.53568

Виконайте перевірку, представивши кожне число у десятковій системі числення.

 

48. Дане число переведіть у 16 – річну систему числення:

1.(10)504(11)12	2.5(10)(11)4612	3.504(11)(10)12	4.2(10)9(11)812
5.12(10)7(11)12	6.(10)801(11)12	7.9(10)23(11)12	8.89(10)2(11)12
9.(10)756(11)12	10.2(10)4(11)912	11.29(10)4(11)12	12.789(10)(11)12
13.40(10)2(11)12	14.3(10)2(11)812	15.261(10)(11)12	16.(10)2(11)1112
17.2(10)87(11)12	18.(10)34(11)912	19.56(10)(11)212	20.9(10)9(11)012

 

49. Виконайте ділення даного числа на 23₄ та перевірте отриманий результат множенням:

1.2101014	2.2231104	3.2310024	4.2323234
5.2213304	6.3001124	7.2333314	8.2232224
9.2302304	10.2323004	11.3003104	12.2302234
13.2301124	14.2303134	15.2213014	16.2302014
17.2111034	18.2121114	19.2201214	20.2220134

 

50. Виконайте ділення та перевірте отриманий результат множенням:

1.83(14)2(10)0816 на 2816	2.(13)997(10)3416 на 3216
3.(11)2(14)850316 на 2916	4.1007(15)3(10)(14)16 на 3116
5.7(15)5(14)(14)(14)816 на 2616	6.812464(11)16 на 2716
7.(13)1562(14)(14)16 на 2916	8.(13)53(13)9(12)(14)16 на 3116
9.(12)(15)0(11)(15)(15)(13)16 на 2716	10.(13)6(15)0(15)(11)(10)16 на 2916
11.(14)4(14)(10)(11)9116 на 3316	12.1065210(10)16 на 3216
13.(11)54(15)76(10)16 на 2916	14.85811(15)416 на 3316
15.(13)5999(14)416 на 2716	16.(13)6(15)176(10)16 на 2916
17.(12)(15)52(12)6(10)16 на 3116	18.(14)785(11)5116 на 3316
19.(13)8(11)660416 на 2716	20.(10)(14)1(15)77(14)16 на 2916

 

51. Переведіть з однієї системи числення в іншу:

1.101010101010112 x 4	2.111010101110102 x 8
3.101010111010102 x 8	4.101110101110112 x 16
5.101010101010112 x 16	6.101011101011102 x 4
7.101111101010102 x 4	8.101010111011112 x 8
9.101110111010112 x 8	10.101110101011102 x 16
11.101110101010102 x 16	12.111010101010112 x 4
13.101011101010112 x 4	14.111010101110102 x 8
15.101111101010102 x 8	16.111011101010112 x 16
17.101011101010112 x 16	18.101110101010102 x 4
19.101010101110102 x 4	20.111010101010112 x 8

 

ГРАФИ

 

52. Дано неорієнтовані графи та , причому , .

1. Побудуйте граф – доповняльний до графа .

2. Побудуйте об’єднання графів .

3. Побудуйте перетин графів .

4. Побудуйте декартовий добуток графів

5. Наведіть приклад шляху та простого шляху з вершини у вершину . В чому полягає різниця між ними?

6. Наведіть приклад цикла та простого цикла у графі . В чому полягає різниця між ними?

7. Чи існує у графі цикл Ейлера? Наведіть приклад. Відповідь обгрунтуйте.

8. Зобразіть граф , отриманий з графа ототожнюванням вершин і .

9. Виконайте розщеплення за вершиною .

10. Виконайте стягування графа по ребру .

11. Для графа побудуйте: а) частину графа; б) підграф;

в) суграф.

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.

 

53. На площині задано вершини неорієнтованого графа. В таблиці перелічено всі його ребра. Побудуйте граф на площині та:

1. складіть таблицю степенів вершин;

2. запишіть матрицю суміжності;

3. запишіть матрицю інцидентності;

4. запишіть таблицю ексцентриситетів у графі;

5. визначте вектор віддаленості;

6. знайдіть радіус та визначте центр графа;

7. знайдіть діаметр та визначте периферійні вершини графа.

1.	(1,2)	(2,3)	(3,4)	(4,2)	(4,3)	(2,1)	(2,3)	(5,2)
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.

 

54. Для орієнтованого графа:

1. побудуйте його на площині;

2. запишіть матрицю суміжності;

3. запишіть матрицю інцидентності;

4. визначте степені виходу та входу вершин графа;

5. визначте, чи є серед вершин джерела та стоки;

6. визначте, чи є маршрут з вершини у вершину ;

7. знайдіть всі шляхи довжини 2, що виходять з вершини ;

8. знайдіть всі шляхи довжини 3, що виходять з вершини ;

9. знайдіть всі шляхи довжини 4, що виходять з вершини ;

10. визначте, чи є в графі цикли, прості цикли (наведіть приклади).

1.

ребро

1 верш.

a

a

e

b

c

c

d

e

e

g

b

g

2 верш.

c

d

b

d

g

f

f

f

a

f

g

a

2.

ребро

1 верш.

a

a

b

b

c

c

d

e

e

g

b

g

2 верш.

b

d

e

d

d

f

f

f

g

f

f

a

3.

ребро

1 верш.

a

a

b

b

c

c

d

e

e

g

b

c

2 верш.

b

e

e

g

d

f

e

f

g

f

f

b

4.

ребро

1 верш.

a

a

f

b

c

c

e

e

a

g

b

g

2 верш.

c

b

b

c

e

f

a

f

g

f

f

c

5.

ребро

1 верш.

a

a

b

b

c

c

d

f

e

g

b

g

2 верш.

g

e

c

a

d

f

e

g

g

f

e

b

6.

ребро

1 верш.

a

a

b

e

c

c

d

e

e

g

b

g

2 верш.

g

b

c

c

d

a

e

f

g

f

f

a

7.

ребро

1 верш.

a

a

b

b

c

c

d

e

e

g

g

g

2 верш.

b

f

c

a

d

e

e

f

g

f

c

a

8.

ребро

1 верш.

c

a

b

b

d

f

d

e

e

g

d

g

2 верш.

a

e

c

d

c

c

e

f

g

f

b

a

9.

ребро

1 верш.

a

a

b

f

c

c

d

e

e

g

b

g

2 верш.

c

e

c

c

d

f

b

f

g

f

f

b

10.

ребро

1 верш.

a

a

b

b

c

c

d

e

e

g

b

g

2 верш.

b

d

d

c

a

f

e

f

g

f

e

a

11.

ребро

1 верш.

a

a

b

c

c

c

d

e

e

g

b

g

2 верш.

b

c

c

b

d

f

e

f

a

f

f

a

12.

ребро

1 верш.

a

g

b

f

c

c

d

e

e

g

d

g

2 верш.

b

b

c

c

d

f

e

f

g

f

f

a

13.

ребро

---

⇐ Предыдущая12

Поделиться с друзьями:

---

Дата добавления: 2016-12-05; Мы поможем в написании ваших работ!; просмотров: 1327 | Нарушение авторских прав

---

Лучшие изречения:

© 2015-2024 lektsii.org - Контакты - Последнее добавление