ВУЗ: Национальная металлургическая академия Украины
Категория: Учебное пособие
Дисциплина: Маркетинг
Добавлен: 06.02.2019
Просмотров: 2072
Скачиваний: 7
16
8. Скільки слів довжини 8 можна скласти з а і б, таких, що кількість букв а
у цих словах не перевищує три?
Розв’язок. Такими словами будуть всі слова, які не мають ні однієї
букви а, всі слова, які мають лише одну букву а, всі слова, які мають дві бу-
кви а, і, нарешті, всі слова, які мають три букви а, тобто загальна кількість
слів становить
93
56
28
8
1
5
3
8
6
2
8
7
1
8
8
0
8
5
3
6
2
7
1
8
0
8
8
8
8
=
+
+
+
=
=
+
+
+
=
+
+
+
!
!
!
!
!
!
!
!
!
!
!
!
)
,
(
)
,
(
)
,
(
)
,
(
С
С
С
С
9. У групі студентів кожний студент або блондин, або брюнет. Серед сту-
дентів 10 блондинів, решта – брюнети. 12 студентів люблять читати де-
тективи. Серед 12-ти студентів, які люблять читати детективи, 5 блонди-
нів і сім брюнетів. Скільки чоловік налічує вся група, якщо два брюнети
не люблять читати детективи?
Розв’язок. Нехай А означає множину блондинів: |А| = 10; В – множи-
ну брюнетів: |В| = 9; С – множину любителів читати детективи: |С| = 12. Тоді
А
∩
В =
∅
, оскільки множини блондинів і брюнетів не можуть мати спіль-
них елементів; А
∩
С – множина блондинів, які люблять читати детективи:
|А
∩
С| = 5; В
∩
С – множина брюнетів, які люблять читати детективи: |В
∩
С| = 7. Множина А
∩
В
∩
С =
∅
. Отже,
|A
∪
B
∪
C| =|A| + |B| + |C| – |A
∩
B| – |A
∪
C|– |B
∩
C| + |A
∩
B
∩
C| =
= 10 + 9 + 12 – 0 – 5 – 7 +0 = 19.
З
АДАЧІ ТА ВПРАВИ ДО ТЕМИ
Е
ЛЕМЕНТИ КОМБІНАТОРНОГО АНАЛІЗУ
1. Група студентів налічує 25 чоловік. Із них 15 люблять математику, 10 –
фізику, 8 – не люблять ні математики ні фізики. Скільки студентів люб-
лять і математику і фізику?
2. На зборах студентів-відмінників були як студенти першого так студенти
і третього курсу. Всі вони або любителі прози, або любителі поезії. Сту-
дентів-хлопців було 16, а любителів прози – 24. Студентів-дівчат буде
17
рівно стільки, скільки хлопців любителів прози. Скільки студентів було
на зборах?
3. У групі з 100 студентів англійською мовою володіють 28 чоловік, німець-
кою – 30, французькою 42, англійською і німецькою – 8, англійською і
французькою – 10, німецькою і французькою – 5, а всіма трьома мовами
володіють 3 студенти. Скільки студентів не знають жодної з заданих мов?
4. На кафедрі математики працює сім викладачів. Скількома способами
можна скласти комісію з трьох чоловік для прийому “хвостів”?
5. В шаховому турнірі брали участь 30 чоловік, і кожні два шахісти зіграли
між собою лише один раз. Скільки партій було зіграно в турнірі?
6. Скільки існує п’ятизначних чисел, в яких кожна наступна цифра
a) менша за попередню;
b) більша за попередню.
7. На площині проведено 10 ліній так, що ніякі дві з них не паралельні між
собою і неякі три з них не перетинаються в одній точці. Знайти:
a) число точок перетину цих прямих;
b) число трикутників які утворюють ці прямі;
c) на скільки частин ділять площину ці прямі.
8. Скільки прямих можна провести через n точок, якщо ніякі три з них не
лежать на одній прямій?
9. У корзині знаходиться р білих і х чорних м’ячів. Скількома способами
можна викласти ці м’ячі в ряд так, щоб ніякі два чорних м’ячі не були
поряд?
10. Скількома способами можна:
a) упорядкувати множину {1, 2, …, 2n} так, щоб кожне парне число мало
парний номер?
b) розмістити 8 тур на шахівниці так, щоб вони не били одне одну?
11. В змаганнях по метанню списа беруть участь чотири спортсмени (A, B,
C, D). Скількома способами їх можна розмістити в списку виходів у сек-
тор для метання, якщо спортсмен В не може виходити раніше спортсме-
на А?
18
12. Скільки слів із п’яти букв можна скласти, якщо Х = {a, b, c, d}і буква а
зустрічається у слові не більше двох разів, буква b – не більше одного ра-
зу і буква с – не більше трьох разів?
13. Нехай Х = {a, b, c, d} – алфавіт. Слово р = x y z …u v в алфавіті Х назива-
ється паліндромом, якщо слово p
′
= v u … z y x дорівнює р. Скільки палі-
ндромів в алфавіті Х існує серед слів із п’яти букв?
14. Скільки різних слів можна скласти перестановкою букв у слові “чачача”?
19
Т
ЕМА
3
Е
ЛЕМЕНТИ АЛГЕБРИ ЛОГІКИ
О
СНОВНІ ВИЗНАЧЕННЯ ТА ПРИКЛАДИ ВИРІШЕННЯ ЗАДАЧ З РОЗДІЛУ
Н
ЕСУПЕРЕЧНІСТЬ І ПОВНОТА ЧИСЛЕННЯ ВИСЛОВЛЕНЬ
Основні визначення
Застосування союзу і при побудові висловлень зветься
кон`юнкцією.
Форма запису таблиці істинності кон`юнкції:
1. p = 1 і q = 1, то (p і q) = 1;
2. p = 1 і q = 0, то (p і q) = 0;
3. p = 0 і q = 1, то (p і q) = 0;
4. p = 0 і q = 0, то (p і q) = 0.
Якщо істині висловлення, які складають, кон`юнкцію, то кон`юнкція
істина, і навпаки, якщо кон`юнкція істина, то істина кожна її складова.
Кон`юнкція помилкова якщо помилкова хоча б одна її складова.
Імплікативними силогізмами є теореми, які подібні логічним схе-
мам, називаним силогізмами. В імплікаціях обидва посилання, як і висно-
вок, мають однаково визначений вид.
Форма запису таблиці істинності імплікації:
1. р = 1 і q = 1 то (p →q) = 1;
2. р = 1 і q = 0 то (p →q) = 0;
3. р = 0 і q = 1 то (p →q) = 1;
4. р = 0 і q = 0 то (p →q) = 1.
Коли обидві посилки вірні, то висновок вірний. Якщо одна з посилок
зрадлива, то і весь алгоритм зрадливий.
Диз'юнкція завжди є комунікативною. Вона характерна спілкою або.
Форма запису таблиці істинності диз'юнкції:
1. якщо p = 1 і q = 1 то (p або q) = 1;
2. якщо p = 1 і q = 0 то (p або q) = 1;
3. якщо p = 0 і q = 1 то (p або q) = 1;
4. якщо p = 0 і q = 0 то (p або q) = 0.
Диз'юнкція істина тоді, коли один з її членів є істинним.
p
q
p
∧
q
1
1
1
1
0
0
0
1
0
0
0
0
р
q
p
→
q
1
1
1
0
1
1
1
0
0
0
0
1
p
q
p
∨
q
1
1
1
0
1
1
1
0
1
0
0
0
20
Закон, що характеризує еквівалентність
Форма таблиці істинності еквівалентності:
1. якщо р = 1 і q = 1, то (p ↔ q) = 1;
2. якщо р = 1 і q = 0, то (p ↔ q) = 0;
3. якщо р = 0 і q = 1, то (p ↔ q) = 0;
4. якщо р = 0 і q = 0, то (p ↔ q) = 1;
Еквівалентність істинна коли обидва її члена одночасно або істинні,
або помилкові.
Закони де-Моргана
1. [Не (р або q)] тоді і тільки тоді, коли [(не р) і (не q)].
2. [Не (q і не p)] тоді і тільки тоді, коли [(не p або не q)].
Обидва закони мають численні застосування, у першу чергу при під-
становках.
Лема. Нехай А – формула, а В
1
, В
2
, …, В
к
– пропозиційні змінні, що
входять до формули А, і нехай задана деяка інтерпретація h. Покладемо В
і
′
рівним В
і
, якщо h(B
i
) = 1, і рівним ¬В
і
, якщо h(B
i
) = 0, і, нарешті, А
′
рівним
А, коли h(А) = 1, і рівним ¬А, коли h(А) = 0.
В
ИЗНАЧЕННЯ
. Літерою називається атом або заперечення атома.
Диз’юнктом називається диз’юнкція літер. Одиничним диз’юнктом нази-
вається однолітерний диз’юнкт. Якщо диз’юнкт не має жодної літери, то
він називається пустим диз’юнктом і позначається 0. Літери L i ¬L нази-
ваються контрарними.
Правило тавтології (ДП1). Викреслити всі тавтологічні диз’юнкти
із S. Множина диз’юнктів S
|
, що залишились, суперечна тоді і тільки тоді,
коли S суперечна.
Правило однолітерних диз’юнктів (ДП2). Якщо існує одиничний
диз’юнкт L в S, то S
|
одержано з S шляхом викреслення з S тих диз’юнктів,
які містять L. Якщо S
|
пустий, то S істина. В протилежному випадку буду-
p
q
p
↔
q
1
1
1
0
1
0
1
0
0
0
0
1