Основи дискретної математики

МЕТОДИЧНІ ВКАЗІВКИ

до виконання практичних робіт

для студентів за фахом 5.05010101

«Обслуговування програмних систем і комплексів»

Краматорськ 2009

Розробив О.В. Сігова викладач першої професійної категорії

Розглянуто та схвалено на засіданні
циклової комісії «Програмування»
протокол № від 2009р.

Голова О. В. Олійник

Методична розробка призначена для студентів денної форми навчання за фахом 5.05010101«Обслуговування програмних систем і комплексів»

Включає програму предмета (блоки ї модулі), перелік літератури, що рекомендована, питання для самоконтролю. Складені індивідуальні завдання, приведен приклад виконання практичних робіт, а також правила оформлення.

ВВЕДЕННЯ

Метою даної фундаментальної дисципліни є: ознайомлення студентів з максимально широким колом понять дискретної математики, придбати навички у створенні та програмуванні дискретних об’єктів при рішенні практичних завдань. А також навчити студентів розумінню у вирішенні проблем, пов’язаних з автоматизацією процесів обробки дискретної інформації; привити навички у використанні методів дискретної математики для синтезу обчислювальної техніки та програмного забезпечення.

Основні способи подачі інформації - дискретні (дискретний (лат. diskretus) - розділений, переривчастий): це слова й конструкції мов і граматик, табличні масиви реальних даних у технічних системах і науково - природних спостереженнях; дані господарської, соціальної, демографічної, історичної статистики.

Для кількісного аналізу й обчислювальних перетворень безперервних процесів доводиться їх представляти як дискретні. Математичні методи обробки, аналізу й перетворення дискретної інформації необхідні у всіх галузях науковій, господарській і соціальній сферах.

Часто для аналізу конкретних систем з безперервними конструктивними елементами будують моделі дискретної математики. Наприклад, класична транспортна або інформаційна мережа трактується як граф із заданою пропускною здатністю або вагою гілок, а геометрична форма гілок між двома пунктами - вузлами мережі не має значення.

Даний матеріал безпосередньо пов'язан з такими дисциплінами: «Основи програмування і алгоритмічні мови», «Структури даних», Комп’ютерна схемотехніка, «Комп’ютерні мережі».

ПРОГРАМА ПРЕДМЕТА І МЕТОДИЧНІ ВКАЗІВКИ ПО ВИВЧЕННЮ НАВЧАЛЬНОГО МАТЕРІАЛУ

1 ОСНОВИ ТЕОРІЇ МНОЖИН

1. Поняття множини й способи її завдання;

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

3. Прямий добуток множин;

4. Ланцюжок, алфавіт.

Поняття множини. Універсальна множина і її підмножини. Способи завдання множин. Операції над множинами. Властивості дій над множинами. Визначення числа елементів множин. Прямий добуток множин. Вектор. Порожній ланцюжок. Дії з ланцюжками. Конкатенація. Піднесення ланцюжків у ступінь. Алфавіт. Ітерація алфавіту. Усічена ітерація.[1], [2], [3], [4].

Питання для самоконтролю

1. Дискретна математика: фундаментальні поняття, основні розділи.

2. Множини, підмножини, способи завдання множин; операції над множинами. Діаграми Венна для цих операцій.

3. Поняття кінцевої універсальної множини, операції різниця множин, доповнення множини. Діаграми Венна для цих операцій.

4. Алфавіт як множина. Ітерація, усічена ітерація алфавіту, алфавіт у ступені 0. Ланцюжок, елементи ланцюжка, порожній ланцюжок, ступінь ланцюжка, зчеплення ланцюжків.

5. Число елементів (потужність) множини. Висновок формули для визначення потужності (кількості елементів) об'єднання двох множин. Формула для визначення потужності об'єднання трьох множин.

6. Поняття "вектор" у теорії множин. Відмінність вектора від множини. Прямий добуток множин. Ступеня множини.

2 ОСНОВИ ТЕОРІЇ ВІДНОСИН

1. Поняття відносини;

2. Властивості бінарних відносин;

3. Операції з бінарними відносинами;

4. Замикання відносин.

Відносини. Способи завдання відносин. Матриця суміжності. Орієнтований граф. Властивості бінарних відносин. Рефлексивність. Симетричність. Транзитивність. Операції з бінарними відносинами. Піднесення відносин у другий і третій ступінь. Добуток бінарних відносин. Транзитивне замикання відносини. Транзитивно - рефлекснвне замикання відносини..[1], [2]

Питання для самоконтролю

1. Відношення;

2. Способи завдання відносин;

3. Бінарні відносини, Універсальна множина для бінарних відносин. Поняття зворотного відношення; приклад його побудови;

4. Властивості бінарних відносин (рефлексивність, симетричність, транзитивність);

5. Визначення властивостей бінарних відносин за ознаками;

6. Добуток двох відносин, ступеня відносини;

7. Транзитивне й транзитивно-рефлексивне замикання відносини.

3 ЕЛЕМЕНТИ АЛГЕБРИ ЛОГІКИ

1. Логічні зв'язування;

2. Таблиці істинності для складених висловлень;

3. Таблиця основних конъюнкций;

4. Аргументи.

Прості висловлення, логічні зв'язки. Таблиці істинності для логічних зв'язок. Складені висловлення. Таблиці істинності для складених висловлень. Побудова заданих складених висловлень. Перехід від складеного висловлення до формул множин. Спрощення формул і зворотний перехід. Відношення між висловленнями. Аргументи, [1], [2], [3], [4].

Питання для самоконтролю

1. Основні поняття алгебри висловлень.

2. Таблиці істинності для основних логічних зв'язок.

3. Побудова таблиць істинності для складних висловлень. Логічні закони.

4. Зв'язування як логічна функція. Множина логічних функцій для двох висловлень.

5. Побудова висловлень із заданою таблицею істинності. Таблиця основних кон'юнкцій для двох висловлень, СДНФ. Приклади, еквівалентність двох складних висловлень.

6. Логічні відносини між висловленнями.

7. Прості відносини, 2-відносини. Алгоритм перевірки відносин для двох складних висловлень.

8. Аргументи і їхні елементи. Поняття правильності аргументу й істинності висновку. Процедура перевірки правильності аргументу.

9. Побудова правильного аргументу по заданим посилкам.

10. Перемикальні схеми як прикладне застосування теорії складених висловлень. Побудова найпростіших перемикальних схем для висловлень, що містять кон'юнкцію, диз'юнкцію й заперечення.

11. Побудова перемикальних схем із заданими властивостями з використанням діаграм Венна.

4 ОСНОВИ ТЕОРІЇ ГРАФІВ

1. Загальне поняття графа;

2. Способи завдання графів;

3. Елементи графів;

4. Операції із частинами графів;

5. Діаметр, радіус і центр графа;

6. Діаметр, радіус і центр довжини графа.

Загальне поняття графа. Граф, як математичний об'єкт. Поняття інцидентності. Способи завдання графів. Дерево, як різновид графа. Визначення цикломатического числа графа. Завдання відносини інцидентності. Елементи графів. Частина графа. Суграф. Подграф. Зоряний граф. Операції із частинами графів. Эйлеров граф. Відстань. Довжина, Діаметр, радіус і центр графа. Діаметр, радіус і центр довжини графа..[1], [2], [3], [4].

ЗАГАЛЬНІ МЕТОДИЧНІ ВКАЗІВКИ ПО ВИКОНАННЮ ПРАКТИЧНИХ РОБІТ

Матеріал курсу «Основи дискретної математики»для виконання практичних робіт розподілен на наступні частини:

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

2. Основи теорії відношень;

3. Елементи алгебри логіки;

4. Основи теорії графів;

5. Теорія кінцевих автоматів.

Перш ніж почати виконання завдань практичних робіт, необхідно проробити відповідні розділи курсу лекцій. Відповісти на контрольні питання. Правильно виконану практичну роботу студент повинен захистити (продемонструвати роботу програм, відповісти на питання що до виконання роботи, контрольні питання).

ПОРЯДОК РІШЕННЯ ЗАДАЧ ПРАКТИЧНИХ РОБІТ

1. Вивчити теоретичні матеріал до відповідного розділу.

2. Розібрати приведений приклад, якщо у завданні необхідно створити програму, (набрати і запустити програму на виконання, поексперементувати з даними, виводом, результатом).

3. Ознайомитись з власним варіантом задач, виконати теоретичну частину робіт, при необхідності согласувати з викладачєм.

4. Скласти і відладити Паскаль - програму, яка реалізує практичну частину задачі (при необхідності).

5. Оформити рішення задачі у вигляді звіту.

ЗВІТ ПОВИНЕН МІСТИТИ

• назву задачі;

• ціль роботи;

• короткі теоретичні відомості по темі розв'язуваної задачі;

• індивідуальне завдання з конкретними значеннями параметрів для виконуваного варіанта;

• рішення задачі з докладними поясненнями;

• короткі висновки за результатами рішення задачі.

• для задач, у яких передбачена реалізація у вигляді Паскаль-программы (додатково до перерахованого вище):

Ø листинг програми;

Ø роздруківку результатів роботи програми.

ПРАКТИЧНА РОБОТА №1

Тема: Універсальна множина, її підмножини. Визначення числа елементів підмножин

Ціль: - придбання навичок побудови діаграм Венна, визначення кількості елементів довільної підмножини.

Завдання

Для заданої універсальної множини М и його під множин: А= {а Є М| а = р k }; В = {b Є M|b=q k }; C = {c Є М | с =r k } (k=1,2,3,...) одержати за допомогою діаграм Венна множину Ф и обчислити кількість елементів цієї множини. Скласти Паскаль - програму для визначення кількості елементів будь-якої підмножини універсальної множини М.

Методичні вказівки.

1. Побудувати діаграму Венна (аналітично) для множини Ф, зобразивши підмножини А, В и С із урахуванням значень р, q,r.

2. Для кожної зв'язної області діаграми Венна визначити кількість елементів і вказати їх у кожній області у вигляді числа.

3. Визначити кількість елементів множини Ф,

4. Скласти Паскаль - программу для визначення кількості елементів множини Ф та зрівняти результати.

Таблиця 1

Продовження таблиці 2

Приклад рішення задачі:

Для заданої універсальної множини М и її підмножин: А = {а Є М | а = 3k}; В = {b Є M | b = 6k}; С = {с Є М | с = 9k} (k= 1,2,3,...) одержати за допомогою діаграм Венна множину Ф и обчислити кількість елементів цієї множини. Скласти Паскаль-программу для визначення кількості елементів будь-якої підмножини універсальної множини М={ 1,2,3...79,80}.

____ _

Ф = (А\(ВUС))U((В ∩ А)\С)

Рішення

1. Побудуємо вручну діаграму Венна для множини Ф, зобразивши підмножини А, В и С із урахуванням значень р, q, r.

_____ __

Ф = (А\(ВUС))U((В ∩ А)\С)

3 1 7 4 6

_____

ВUС ВUС

_____

A\(BUC) В ∩ А

_ _

C (В ∩ А)\C

Ф

2. Для кожної зв'язної області діаграми Венна визначимо кількість елементів, указавши їх у кожній області у вигляді числа.

В ∩ С

НОК(6,9)= 18

80/18=4

В

80/6= 13

13-4=9

С

80/9= 8

8-4=4

A: 80/3= 26

26-9-4-4=9

80-9-9-4-4=54

3 Визначимо кількість елементів множини Ф.

n(Ф)= 9+4+4= 17

4 Складемо Паскаль-программу для визначення кількості елементів множини Ф та зрівняємо результати.

Листинг - програми.

Program Mn;

(* Для заданої універсальної множини U={ 1,2,3...79,80} і

її підмножин:

А= {а Є U | а=3n}; В = {b Є U | b=6n}; С = {с Є U | с=9n)

(n=1,2,3,...) визначити кількість елементів підмножини

універсальної множини U:

_____ __

(А \ (В U С)) U ((В ∩ А) \ С) *)

Uses Crt;

Type Sets=Set of Byte;

Const p=3;q=6;r=9;n=80;

Var a, b, c, u: Sets; i: Byte; y Integer; {змінні а,b,с, u, i-множини чисел}

Procedure Foots;

{процедура, що виділяє: елементи підмножини А кратні р елементи підмножини В кратні q елементи підмножини С кратні r}

Begin

For i:=l To n Do

Begin

u:=u+[i];

If (i Mod p)=0 Then a:=a+[i]; If (i Mod q)=0 Then b:=b+[ij; If (i Mod r)=0 Then c:=c+[i];

End;

End;

Procedure Kolichestvo(Set0:Sets);

{процедура, що считує кол-во елементів підмножин}

j:=0;{обнуління кол-ва елементів}

For i:=1 To n Do

If i in Set0 Then {якщо число входить у дану підмножину} Begin

Write(i,''); {вивід елемента який входить в дану підмножину}

Inc(j); {збільшення кол-ва елементів на 1}

End;

WriteLn;

WriteLn('Кількість елементів:'j); {вивід кол-ва елементів}

End;

{основна програма:}

Begin {ClrScr;}

Foots;{виклик процедури, що виділяє елементи подмн-ва} {Позначення:

перетинання П -"*"

об'єднання U -"+"

доповнення А - (U-A)

різниця А \ В - (В)}

WriteLn(' _____');

WriteLn('МножинаCUB:');

Kolichestvo((u-(b+c)));

{виклик процедури, що считує кол-во елементів підмножин}

WriteLn(' ');

WriteLn('Множина А \ (С U В)');

Kolichestvo((a-(u-(c+b))));

writeln(' _');

writeln('Множина ((В П А) \ С)');

Kolichestvo((b*a)-(u-c));

WriteLn(' _____ __');

WriteLn('Множина ((A \ (C U B)) U ((В П A) \ C)');

Kolichestvo((a-(u-(c+b)))+((b*a)-(u-c)));

ReadKey;

End.

18 36 54 72

Кількість елементів:4

Множина ((A \ (C U B)) U ((В П А) \ С)

6 912 18 24 27 30 36 42 45 48 54 60 63 66 72 78

Кількість елементів: 17

Множина CUB:

1 2 3 4 5 7 8 10 11 13 14 15 16 17 19 20 21 22 23 25 26 28 29 31 32 33 34 35 37 38 39 40 41 43 44 46 47 49 50 51 52 53 55 56 57 58 59 61 62 64 65 67 68 69 70 71 73 74 75 76 77 79 80

Кількість елементів:63

Множина А \ (С U В)

6 912 18 24 27 30 36 42 45 48 54 60 63 66 72 78

Кількість елементів: 17

Множина (В П А) \ С

18 36 54 72

Кількість елементів:4

____ __

Множина ((А \ ((СUB)) U ((В П А) \ С)

6 9 12 18 24 27 30 36 42 45 48 54 60 63 66 72 78

Кількість елементів: 17

ПРАКТИЧНА РОБОТА № 2

Тема: Бінарні відносини між елементами множини

Ціль: - дослідження властивостей бінарних відносин.

Завдання

Для заданої множини М побудувати бінарні відносини Р и Q і досліджувати їхньої властивості. Відношення Q аналітично й графічно звести в ступені 2,3, а також побудувати транзитивне замикання Q⁺ і транзитивно - рефлексивне замикання Р*. Одержати аналітично і графічно відношення R = Р х Q, знайти для R зворотне відношення й доповнення відносини R.

Таблиця 3

Продовження таблиці 3

Приклад рішення задачі:

Для заданої множини М побудувати бінарні відносини Р и Q і досліджувати їхньої властивості. Відношення Q аналітично й графічно звести в ступені 2,3, а також побудувати транзитивне замикання Q⁺ і транзитивно-рефлексивне замикання Р*. Одержати аналітично й графічно відношення R = Р х Q, знайти для R зворотне відношення й доповнення відносини R.

P=”«с» або «d» тільки на першому місці”

Q=”«a» на будь-якому місці”

Рішення

P={ca, cb, cf, da, db, df}

1. Висловлення Р антирефлексивно, тому що на головної диаго­
налі матриці суміжності нулі.

2. Висловлення Р не симетрично, тому що матриця суміжності
не симетрична щодо головної діагоналі, а на самої діагоналі розташовані нулію

3.Висловлення Р транзитивно, тому що властивість транзитивності не порушено.

1. Висловлення Q не рефлексивно, тому що на головній діагоналі матриці суміжності перебувають нулі й одиниці.

2. Висловлення Q симетрично, тому що матриця суміжності симетрична щодо головної діагоналі.

3. Висловлення Q не транзитивно, тому що властивість транзитивності порушена.

2. Відношення Q аналітично й графічно зведемо в ступені

2,3.

Q = {аа, ab, ас, ad, af, ba, ca, da, fa}

Q² = {aa, ab, ac, ad, af,ba,..., ff}

Q² = {aa, ab, ac, ad, af, ba, bb, be, bd, bf, ca, cb, cc, cd, cf, da, ab, dc, dd, df, fa, fb, fc, fd, ff} Q³ = Q²

3, Одержимо аналітично й графічно відношення R = Р х Q,

R = Px Q

Р = {ca, cb, cd, cf, da, db, dc, df}

Q = {aa, ab, ac, ad, af, ba, ca, da, fa}

R = {ca, cb, cc, cd, cf, da, db, dc, dd, df}

4. Знайдемо для R зворотне відношення й доповнення відносини R.

R = {ca, cb, її, cd, cf, da, db, dc, dd, df}

R ^-1 = (ac, be, cc, dc, fc, ad, bd, cd, dd, fd}

_

R = {aa, ab, ac, ad, af, ba, bb, be, bd, bf, fa, ft, fc, fd. ff)

ПРАКТИЧНА РОБОТА №3

Тема: Елементи алгебри логіки (висловлення, складені висловлення, відносини).

Ціль - одержання складених висловлень із заданою таблицею істинності; автоматизація аналізу відносин між парами висловлень.

Завдання

Із трьох простих висловлень р, g, r скласти, використовуючи основні логічні зв'язки, три складові висловлення В, С, D із заданими таблицями істинності, спростити ці висловлення за допомогою еквівалентних перетворень. Установити вид відносин між можливими парами всіх висловлень (А, В, C,D).

Методичні вказівки

1. Побудувати таблицю істинності для висловлення А.

2. Використовуючи таблицю СДНФ, скласти з основних кон'юнкцій складові висловлення В, С, D й, по можливості, спростити їх, використовуючи діаграми Венна.

3. Встановити стосунки між всіма можливими парами складених висловлень (А? В; А? С... С? D)

Таблиця 4

Примітка:

Умовні позначки в таблиці:

~ - заперечення (логічне НІ);

Ú - диз'юнкція (логічне АБО);

Ù - кон'юнкция (логічне И);

® - імплікація (якщо..., то...).

Приклад рішення задачі:

Із трьох простих висловлень р, q, r скласти, використовуючи основні логічні зв'язки, три складові висловлення В, С, D із заданими таблицями істинності, спростити ці висловлення, за допомогою еквівалентних перетворень. Установити вид бінарних відносин між всіма можливими парами складених висловлень (А В, С, D). Для висловлення А побудувати перемикальну схему й пояснити її роботу. А = ~ (q Ú ~ r) Ù р® (q Ù~ r)

В = 7,3

С = 7,2,4

D = 7,6,5,2

Рішення

А = ~ (q Ú ~ r) Ù р® (q Ù~ r)

В = 7,3

С = 7,2,4

D = 7,6,5,2

1. Побудуємо таблицю істинності для висловлення А.

2. Спростимо висловлення А, що представимо у вигляді перемикальної схеми.

A = ~ (q Ú ~ r) Ù р® (q Ù ~ r)

A=~pÚqÚ~r

Представимо висловлення А в виді перемикальної схеми.

3 Використовуючи таблицю СДНФ, складемо з основних кон'юнкцій складові висловлення В, С, D й, по можливості, спростимо їх, використовуючи діаграми Венна.

В С

В = (~pÙ~qÙr) Ú (pÙ~qÙr) = r/q = r Ù~q

С = (~pÙ~qÙr) Ú (pÙqÙ~r) Ú (pÙ~qÙ~r) = (pÙ~r) Ú (~pÙ~qÙr)

D = (~pÙ~qÙr)Ú(~pÙ~qÙ~r)Ú(~pÙqÙr) Ú (pÙqÙ~r) = (qÙ~r) Ú (~pÙ r)

Побудуємо таблиці істинності для висловлень, В С і D.

4 Встановити вид бінарних відносин між всіма можливими парами складених висловлень (А? В; А? С... C?D).

Між вис-ми А и В установлене відношення "F несумісність".

Між вис-ми А и С установлене відношення"F-несумісність".

Між вис-ми А и D установлене відношення "з D випливає А".

Між вис-ми В и С установлене відношення "з В випливає С",

Між вис-ми В и D установлене відношення "Незалежні".

Між вис-ми С и D установлене відношення "Незалежні".

ЗАВДАННЯ № 4

Тема: Елементи теорії графів

Ціль: одержання навичок дослідження неорієнтованих графів.

Завдання

1 Зобразити граф G у відповідності зі своїм варіантом і вказати поруч із кожним ребром його вага. Побудова виконати так, щоб ребра графа не перетиналися один з одним.

2 Визначити цикломатичне число графа G.

3 Побудувати для графа G дерево з мінімальною вагою й визначити його.

4 Досліджувати граф G на мінімум (визначити радіус, діаметр і центр (центри) графа).

5 Досліджувати граф G на максимум (визначити діаметр довжини, центр (центри) довжини й радіус довжини графа G).

6 Побудувати для графа G приклади його частини, суграфа, подграфа, зоряного графа.

Таблиця 5.1

Таблиця 5.2

Приклад рішення задачі:

Зобразити граф G. Побудову виконати так, щоб ребра графа не перетиналися один з одним. Визначити цикломатичне число графа G, Побудувати для графа G дерево з мінімальною вагою й визначити його. Досліджувати граф G на мінімум (визначити радіус, діаметр і центр (центри) графа). Досліджувати граф G на максимум (визначити діаметр довжини, центр (центри) довжини й радіус довжини графа G). Побудувати для графа G приклади його частини, суграфа, подграфа, зоряного графа.

V = {а, b, с, d, e, f, k, m}

Е = { ab, be, bd, be, de, cd, df, fk, ek, em }

Вага ребер

Рішення.

1 Зобразимо граф G відповідно до умови, поруч із кожним ребром зазначена його вага.

2 Визначимо цикломатичне число графа G, обчисливши
його по формулі:

г = v +m - n, де

v - число зв'язних компонентів графа,

m - число ребер,

n - число вершин.

г = 1+10-8==3;

3 Побудуємо для графа G дерево з мінімальною вагою й
визначимо його.

Будуємо ребро графа з мінімальною вагою - CD-потім на кожному кроці добудовуємо ребра з мінімальною вагою доти, поки в графі не буде утворюватися циклів.

Крок 1 - ребро CD з вагою 2.

Крок 2 - ребро BE з вагою 3.

Крок 3 - ребро АВ з вагою 4.

Крок 4 - ребро DF з вагою 4.

Крок 5 - ребро BD з вагою 5.

Крок 6 - ребро FK з вагою 5.

Вага дерева:

L = 2+3+4+4+5+5=23.

4 Досліджуємо граф G на мінімум (визначимо радіус, Діаметр і центр (центри) графа). Для цього побудуємо матрицю

відстаней.

Центр вершина b

R(G)=10;

D(G)=18.

5 Досліджуємо граф G на максимум (визначимо діаметр довжини, центр (центри) довжини й радіус довжини графа G). Для цього побудуємо матрицю відстаней.

Центр довжини вершина b

R(G)=24;

D(G)==34.

6 Побудувати для графа G приклади його частини, суграфа, подграфа, зоряного графа.

Побудуємо граф, що є частиною графа G.

Побудуємо граф, що є суграфом графа G.

Побудуємо граф, що є подграфом графа G на множинівершинU(CBDE).

Побудуємо зоряний граф G(D).

СПИСОК РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ

1. Комп'ютерна дискретна математика:Підручник/М.Ф. Бондаренко, Н,В, Білоус, А.Г. Ругкас,- Харків: «Компанія СМИТ», 2004.- 480 с.

2. Новиков Ф.А. Дискретна математика для програмистів.-Спб.:Питер,2000.-304 с.:іл,

3. Іванов Б.Н. Дискретна математика.-М,: Лабораторія базових знань» 2002.-288 с.

4. Кузнєцов О. П., Адельсон-Вельский Г. М. Дискретна
математика для інженера.-М.: Енергоатомиздат, 1988,-480 с.

Питання по теорії до іспиту (заліку):

1. Предмет дискретної математики.

2. Множини, підмножини, способи завдання множин; операції над множинами. Діаграми Венна для цих операцій.

3. Поняття кінцевої універсальної множини. Діаграми Венна для операцій над множинами.

4 Алфавіт як множина. Ітерація, усічена ітерація алфавіту, алфавіт у ступені 0. Ланцюжок, елементи ланцюжка, порожній ланцюжок, ступінь ланцюжка, зчеплення ланцюжків.

5. Число елементів (потужність) множини. Висновок формули для визначення потужності (кількості елементів) об'єднання двох множин. Формула для визначення потужності об'єднання трьох множин,

6. Поняття "вектор" у теорії множин. Відмінність вектора від множини. Прямий добуток множин. Ступені множини.

7. Поняття відносини, побудованого на множині М Арність Відносини. Приклади побудови відносин.

8. Способи завдання відносин. Бінарні відносини, Універсальна множина для бінарних відносин. Поняття зворотного відношення; приклад його побудови.

9. Властивості бінарних відносин, визначення цих властивостей за ознаками.

10. Добуток двох відносин, ступеня відносини. Транзитивне й транзитивно-рефлексивное замикання відносини.

11. Основні поняття алгебри висловлень (висловлення, складене висловлення, основні зв'язування в складених висловленнях - конъюнкций, диз'юнкція, заперечення, імплікація, еквівалентність).

12. Таблиці істинності для основних логічних зв'язувань. Побудова таблиць істинності для складних висловлень, Логічні закони,

13. Зв'язування як логічна функція. Множина логічних функцій для двох висловлень.

14. Побудова висловлень із заданою таблицею істинності. Таблиця основних кон'юнкцій для двох висловлень, СДНФ.

15. Логічні відносини між висловленнями (відносини проходження, еквівалентності, протилежності, сумісностей).

16. Аргументи і їх елементи. Поняття правильності аргументу й істинності висновку. Процедура перевірки правильності аргументу.

17. Перемикальні схеми як прикладне застосування теорії складених висловлень. Побудова найпростіших перемикальних схем для висловлень, що містять кон'юнкцію, диз'юнкцію й заперечення.

18. Побудова перемикальних схем із заданими властивостями з використанням діаграм Венна.

19. Поняття графа; різновиду графів. Орієнтовані й неорієнтовані графи; їхнє завдання за допомогою матриць.

20. Частина графа, суграф, подграф, зоряний граф. Операції із частинами графа (доповнення, об'єднання, перетинання).

21. Поняття маршруту, ланцюга, простого ланцюга в графі. Зв'язність графа.

22. Довжина маршруту в графі; відстань між вершинами графа. Діаметр, радіус і центр (центри) графа, процедура їхнього пошуку.

23. Поняття довжини між вершинами графа. Діаметр довжини, радіус довжини й центр (центри) довжини графа, процедура їхнього пошуку.

24. Визначення кінцевого автомата (КА), призначення. Основні поняття, що задають параметри КА, діаграма станів, робота КА - розпізнавача.

25. Недосяжні й еквівалентні стани КА.

26. Недетермінований кінцевий автомат (НКА) - завдання, інтерпретація його роботи з розпізнання ланцюжків).