Тема 2. Елементи комбінаторики
1. Поняття комбінаторної задачі.
2. Правило суми. Принцип включення і виключення.
3. Правило добутку.
Приклад.
Скільки існує
-значних
чисел в десятковій системі числення?
4. Перестановки без повторень: означення, обчислення, приклади.
Приклад
1.
Скласти
всі можливі числа з цифр
,
де
-
число букв, що входять в Ваше ім’я.
Приклад
2.
Скількома
способами можна розташувати на полиці
різних книг, якщо 2 певні книги не мають
стояти одна біля одної?
5. Розміщення без повторень: означення, обчислення, приклади.
Приклад 1. Скласти всі можливі розміщення з різних букв Вашого імені.
Приклад
2.
На
вершину гори ведуть
стежинок. Скількома способами турист
може піднятися в гору і потім спуститися
з неї при умові, що підйом і спускання
мають відбуватися по різних стежинках?
6. Комбінації без повторень: означення, обчислення, приклади. Властивості числа комбінацій.
Приклад 1. Скласти всі можливі комбінації з різних букв Вашого імені.
Приклад
2.
На колі вибрані
точок. Скільки існує трикутників з
вершинами в цих точках?
7. Перестановки з повтореннями: означення, обчислення, приклади.
Приклад.
Скількома
способами можна поселити
студентів у трьох кімнатах гуртожитку:
одномісній, двомісній, тримісній?
8. Розміщення з повтореннями: означення, обчислення, приклади.
Приклад.
Скільки трицифрових чисел можна скласти
з
цифр
,
де
-
число букв, що входять в Ваше ім’я?
9. Число елементів булеана скінченної множини.
Приклад.
В приміщенні
лампочок. Скількома різними способами
можна освітити приміщення?
10. Комбінації з повтореннями: означення, обчислення, приклади.
Приклад.
Скількома способами можна розсадити
гостей, які тільки що прийшли, серед
гостей, які вже сидять за круглим столом?
Розділ 2 Елементи теорії булевих функцій
Тема 3. Елементи теорії булевих функцій
1.
Поняття булевої функції. Способи завдання
булевих функцій. Число
булевих функцій
аргументів.
2. Елементарні булеві функції та їх властивості.
Виписати у вигляді таблиці елементарні булеві функції одного і двох аргументів.
3. Реалізація булевих функцій формулами.
4. Рівносильність та тотожність формул. Принцип двоїстості.
5. Диз’юнктивна та кон’юнктивна нормальні форми.
6. Зображення булевих функцій досконалими диз’юнктивними нормальними формами.
7. Зображення булевих функцій досконалими кон’юнктивними нормальними формами.
Приклад.
Для булевої функції
,
заданої формулою:
1) скласти таблицю істинності;
2) знайти ДДНФ і ДКНФ двома способами:
а) за допомогою таблиці,
б) за допомогою рівносильних перетворень.
-
№ варіанта
Булева функція
1
2
3
4
5
∣
6
7
∣
8
∣
9
∣
10
∣
8. Повні системи булевих функцій.
9. Мінімізація булевих функції в класі досконалих диз’юнктивних нормальних форм.
10. Реалізація булевих функції схемами з функціональних елементів.
11. Аналіз і функціонування схеми з функціональних елементів.
12. Структурній синтез схем з функціональних елементів.
Приклад.
Булеву функцію
,
задану переліком десяткових еквівалентів
наборів, на яких вона дорівнює одиниці
-
мінімізувати в класі ДНФ методом Квайна-МакКласкі;
-
реалізувати схемою з функціональних елементів.
-
№ варі-анта
1
3, 6, 7, 9, 10, 11, 15
2
2, 3, 5, 7, 11, 14, 15
3
0, 1, 4, 10, 11, 12, 15
4
2, 3, 6, 8, 9, 13, 14
5
2, 3, 5, 7, 10, 11, 15
6
0, 3, 5, 7, 10, 14, 15
7
0, 2, 5, 8, 13, 14, 15
8
0, 3, 5, 7, 8, 11, 12
9
1, 2, 3, 7, 11, 12, 15
10
0, 1, 2, 3, 6, 8, 15