БУЛЕВІ ФУНКЦІЇ ТА ТЕОРІЯ МНОЖИН

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.Представте дане число у двійковій системі числення:

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

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

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

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

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

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

1.101010101010112 x4	2.111010101110102 x8
3.101010111010102 x8	4.101110101110112 x16
5.101010101010112 x16	6.101011101011102 x4
7.101111101010102 x4	8.101010111011112 x8
9.101110111010112 x8	10.101110101011102 x16
11.101110101010102 x16	12.111010101010112 x4
13.101011101010112 x4	14.111010101110102 x8
15.101111101010102 x8	16.111011101010112 x16
17.101011101010112 x16	18.101110101010102 x4
19.101010101110102 x4	20.111010101010112 x8

ГРАФИ

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.визначте, чи є в графі цикли, прості цикли (наведіть приклади).

• ⇐ Назад
• 12