Питання до іспиту з дискретної математики

1. Поняття множини; способи задання множин; підмножина; включення та рівність множин. Основні операції на множинах. Закони алгебри множин. Покриття і розбиття множини. Булеан множини.

Способи задання множин:

1. 
   Явний – множина задаэться переликом елементив A={0,1,2,9}
   

2. 
   Неявний – за допомогою характеристичнойи властывости B = {x|P(x)}, P(x) – характеристична властивисть.
   

Пидмножына:







Властивости пидмножыны:



Строге включення:



Булеан – множина всих пидмножын. B(A)





Булеан.

Булеан мистыть 2 в степени n елементив. (якщо множина мистыть 4 елеметив, булеан складаэться з 2^4=16.

Операцийи над множинами.

1. 
   Обьеднання множин.
   

2. 
   Перетин
   

3. 
   Ризныця
   

4. 
   Сыметрычна ризныця
   

5. 
   Универсальна множина
   

6. 
   Доповнення
   

Властивости операций:

1. 
   комутатывный закон, властывисть комутатывности
   

2. 
   закон асоциатывности, властывисть асоциатывности
   

3. 
   закон дыстрибьютывности, властывисть дыстрибутывности
   

4. 
   
   

Властывости порожньойи множыны и универзальнойи множыны

5. 
   Закон подвийного доповнення
   
6. 
   Иденпотентнисть
   
7. 
   Закони деморгана
   
8. 
   Закон поглинання
   
9. 
   
   

10. 
    
    

2. Декартів добуток множин. Поняття відношення; способи їх задання; теоретико-множинні операції на відношеннях; добуток відношень; відношення, обернене до даного; основні властивості відношень (рефлексивне, …).

Впорядкована пара елементив множини А – це объект де a,b э A, а – перший объект, б – другий объект.

Невпорядковани пары: (a,b) =(b,a)

Декартив добуток множин А и B – нова множина впорядкованих пар

A x B={|x э A, y э B}





Покриття множини А називается довильна сукупнисть НЕпорожних пидмножин множини А A1,…,An, таких що

Розбыття множини А називается таке йийи покрыття, що

Видношення.



Прыклады

Способы задання бинарных видношень:

1. 
   Видношення R задане як множина(явно)(графиком).
   

A={с,т,и,л}

xRy в слови «стил» литера х знаходиться литеры y (вербальний спосиб задання)

R={<с,т>,<с,и>,<с,л>,<т,и>,<т,л>,<и,л>}

2. 
   Координатне задання.
   

R={|x^2+y^2<4}



Приклад 2.

A={1,2,3}; B={a,b}; ; R={<1,a>,,<2,a>,<3,b>}

3. 
   Стрилкови диаграмы.
   
4. 
   Матричний спосиб.
   

5. 
   Граф ориентований (на одний множини)
   

Операцийи над множинами.

1. 
   Объеднання
   

2. Перетин
3. Ризныця

4. доповнення R1

Для бинарных

5. 
   Обернене видношення(инверсне)
   

5. 
   Добуток (суперпозиция aбо композыция) R1*R2
   

Добутком двох бинарных видношень R1 та R2 называется бинарне видношення R1*R2 = {| (иснуэ) z э B: э R1, э R2}

Властивости:

1)R1 * R2 не комутатывный (R1 * R2 != R2 * R1)

2)R1 * R2 – асоциатывна
Специальни властывости бинарных видношень заданих на множини А

1. 
   Бинарне видношення задане на множини A називается диагональю, якщо ; пара виду називается диагональною парою.
   

iA =R

2. 
   Бинарне видношення задане на множини A називается рефлексивним, якщо воно мистыть диагональ:
   

3. 
   Бинарне видношення R называется иррефлексывным(антирефлексивний) якщо (немаэ жоднойи диагональнойи пары)
   
4. 
   Бинарне видношення R называется сыметрычным якщо x R y
   
5. 
   Бинарне видношення R называется антысыметрычным якщо x R y, y R x
   
6. 
   Бинарне видношення R называется транзытывным якщо x R y, y R z x R z
   

3. Відношення еквівалентності та його властивості; теорема про розбиття множини та відношення еквівалентності на цій множині. Мінімальний (максимальний), найменший (найбільший) елемент відносно ЧП. Лінійний порядок.
Бинарне видношення задане на множини A называется видношенням эквивалентости якщо,

R – рефлексивне, симетричне, транзитивне

Класом елементу а называется множина Kа = {x: x э А, а R x} a

1. 
   a R b;
   
2. 
   Ka = Kb (або [a]=[b])
   
3. 
   
   

1. 
   R = R^-1
   
2. 
   R * R = R (або R^2 = R)
   

,,,,}

ЧП задаэться за допомогою диаграм Хаасе.



Означення. Елемент а називается минимальним видносно ЧП R, якщо (для всих)

яки поривнюються з а видносно R выконуется э R (a <= x)

Означення. Елемент а називается найменьшим видносно ЧП R, якщо выконуэться э R

Линийний порядок. Видношення ЧП, заданого на А називается линийним порядком, якщо будь яки 2 елементи поривнюються за цим порядком.

Лексикографичний порядок. Задано алфавит А. S1 = k1, k2, … , kn, де ki э A, k =



Лексиграфичный порядок:



4. Відображення. Відображення множини на інші множини; Сюр’єкція та ін’єкція, взаємно однозначне відображення (бієкція). Операції.
Повнистью вызначене видношення.

Видношення R називается повнистью вызначеным, якщо (для будь якого х из множини А иснуэ у з множини B такий що пара х у належить нашому видношенню.)

Видношення R називается функциональным якщо (для будь якого х из множини А иснуэ не бильше одного елементу у из множини B таких що х у належить R)

Видображення називается повнистью вызначенне и функциональне видношення

f = {<1,a>,<3,d>,<2,a>}

Видображення називается частковим якщо F не повнистью вызначене и функциональне видношення.

F: A → B – видображення.

Повним прообразом елемента у э В называется множина F^-1(y) = {x: F(x) = y} або э F.

Область визначення:

Область значень видображення f:

Класификация видображень:

1. 
   Видображення f називается сюръектывным (або сюръекциею) якщо (для будь якого у из множини B F^-1(y) != порожний множини).
   
2. 
   Видображення f називается инъектывным якщо (ризным елементам видповидають ризни образы)
   
3. 
   Взаэмно-однозначне видображення або биэктывне видображення(биэкция) называется сюръектывне та инъектывне видображення.
   

Узагальнення видображення f: A → B

f^n: A1 x A2 x … x An → B

Типи:

1) Операция n-арна: F: A^n → A

2) Функция: f: A^n → B

3) Предикат P: A^n → {0,1}

Универсальна алгебра(алгебрайична структура). Алгеброю называется впорядкована пара

G = (A, W), де A != (порожня) множина. W називается сигнатурую алгебры. W - множина операций А. А – носий алгебры.

А = (Z, {f, x}) – алгебра (f(x) = 2x)
5. Поняття висловлювання, формули; інтерпретації. Операції над висловлюваннями. Властивості операцій (закони). Тавтологія, суперечність. Еквівалентні формули. Нормальні форми (КНФ, ДНФ), алгоритм нормалізації. Сумісність висловлювань. Логічне слідування; способи їх встановлення.
Висловлюванням А называется розповидне речення, яке може буты истынным або хыбным. Истыностни значення:

истына 1, T(True), И(Истина)

хибнисть 0, F(False), Л(Ложь)

Операцийи над высловлюваннямы:

1. 
   Заперечення ,
   
2. 
   Конъюкция - логичне множення, сполучник и.
   
3. 
   Дизъюнкция - логичне додавання, сполучник або.
   
4. 
   Импликация A → B – якщо …, то
   
5. 
   Еквивалентнисть
   

Прости высловлювання в логици называются атомамы або пропозыцийнымы зминнымы.

Формули в логици высловлювань (рекурсывне):

1. 
   Атом э формулою
   
2. 
   Якщо F – формула то (заперечення F) – формула.
   
3. 
   Якщо F1, F2 – формулы, то ,
   
4. 
   Инших формул немаэ.
   

Порядок выконання. Спочатку в дужках, заперечення , конъюкция , дызъюнкция , импликация , еквивалентнисть .

Властывости операций. F1, F2, F3, F – формулы.

1. , - комукатывнисть.

2. - асоциатывнисть.

3. - дистрибъютывнисть.



4. ;

5. закон выключення третього. - закон суперечности.

6.

Означення. Булевою алгеброю (двохелементною) называется G = ({0,1}, ) +закони

G = ({0,1}, ) – алгебра логикы. Якщо формула записана за допомогою операций то це булева формула.

Таблици истынности. F = (A B) →



Еквивалентни формулы логикы высловлювання. M – множина формул.

Означення. Видображення h: М → {0,1}называется интерпретацию якщо формул F1 та F2 з множини M задовильняються таки умовы: h ( F) =





Якщо формула F мистыть n атомив, то формула f маэ 2^n интерпретаций.

Означення. Дви формулы F1, F2 логикы высловлювання называются еквивалентними(або ривносыльнымы)(позначаються F1 = F2), якщо воны прыймають однакови истыностни значення пры всих интерпретакциях.

Закони.

7. - F закон подвийного заперечення

8. - закон идемпотентности

9. F1; F1 – закон погринання.

10. - закони де-моргана.

11.

12.

Означення. Формула F логикы высловлення называется тавтологиэю, якщо вона истынна пры всих интерпрытациях.

Означення. Формула F называется суперечнистью, якщо вона хибна при всих интерпрытациях.

- контрарни литеры.

Означення. Якщо формула F не э тавтологиэю, и не э суперечнистью, то F называется нейтральною.



Нормальни формы в логици высловлювання.

- коньюктывна нормальна форма КНФ

- дызъюктывна нормальна форма ДНФ

Означення. Литерою называется формула выду А або , де А – атом.

Означення. Елементарною дызъюнкциэю называется дызъюнкция скинченнойи кильности литер (елементарна дызъюнкция называется дызъюнкт)

,

Означення. Коньюктывна нормальна форма называется формула, записана у выгляди конъюнкцийи скинченнойи килькости елементарных дызьюнкций.

КНФ це коньюкция елементарних дызъюнкций.

ДНФ це дызъюнкция скинченнойи килькости елементарных конъюкций.

Теорема. Будь-яку формулу логикы высловлювання можна податы у выгляди ДНФ (КНФ).

1. 
   ДНФ и КНФ запысуються не едыным чином.
   
2. 
   Перехид вид ДНФ до КНФ и навпакы видбуваэться за законом дыстрыбутывности.
   

Сумистнисть высловлювань. Высловлювання А1, А2, … , Аn называются сумиснымы якщо иснуэ така интерпрытация пры який вси высловлювання э истынымы.

Логичне слидування. Позначаэться высновок

Означення. Формула F называется логичным слидуванням(логичным высновком) з посылок F1, F2, … , Fn (позначаеэться F1, F2, … , Fn F), якщо для всих интерпрытаций на якых посылкы истыни Fi = 1 и высновок F = 1.

Теорема 1. F1, F2, … , Fn F

Теорема 2. F1, F2, … , Fn F

6. Булеві функції, способи їх задання, інтерпретації. Унарні, бінарні функції. Вироджені, не вироджені функції (фіктивні змінні). Формули, еквівалентні формули. Основні рівносильності (закони). Булева алгебра. Теорема про диз’юнктивний розклад БФ. Досконалі нормальні форми ( ДДНФ, ДКНФ), способи їх побудови.

Булеви функцийи.

Дж. Буль B = {0,1} – булевый алфавит.

Означення. Булевою функциэю называется видображення f^n: B^n → B.

Означення. Булевою функциэю называется f(x1, … , xn), де xi э В, , y э B.

Означення. Сукупнисть значень аргументив х1, … , хn (называють булевым словом, булевым набором, булевый кортеж, кортеж довжыны n, интерпретация)

Означення. Иснуэ булевых наборив довжыны n: 2^n шт.

Способи задання булевих функций:

1. 
   Вербальний (словесний). Пр.
   

1) Булева функция вид 3х зминных = 1 на наборах №3,4,5,7.

2) Булева функция вид 3х зминных функция голосування.

2. Аналитычне (за допомогою формулы)

3. Таблиця истыности (Табл. Кели)

Интерпретацийи розмищуються у лексикографичному порядку.

Означення. Нехай (сигма) – двийковый кортеж довжыны n.

(сигма) = (a1, a2, … , an) ai э {0,1}

Номером интерпрытацийи V называется число V(сигма) = a1*2^(n-1) + a2* 2^(n-2) + … +

an-1*2 + an.

n = 3

f (x1, x2, x3)

Елементарни булеви функцийи вид одниэйи зминойи: : 2^2^1 = 4 шт. n = 1.



Булеви функцийи вид двох зминых: ; n = 2; 2^2^2 = 16 шт.



Булеви функцийи вид трьох зминных 2^2^3 = 2^8 = 256

Властывости булевых функций фиктывни зминни.

Означення. Зминна xi булевойи функцийи f(x1, … , xn) называется фиктывною (несуттевою) якщо для всих можливих наборив значень зминных x1, … , xi-1, xi+1, … , xn виконуэться f(x1, … , xi-1, 0, xi+1, … , xn) = f (x1, … , xi-1, 1, xi+1, … , xn).

Якщо зминна не э фиктывною то вона называется суттевою.



Функция яка не мистыть фиктывных зминных называется не выродженою.

Якщо мистыть называется выродженою.

Розклад бульовойи функцийи.





Принцип суперпозыция для побудовы булевых функций з n >= 3 зминных.

Суперпозыциэю называется прыйом отрымання новых булевых функций шляхом пидстановкы значень одных функций замисть значень аргументив иншых функций.
7. Алгебра Жегалкіна. Поліном Жегалкіна, способи побудови. Лінійна булева функція. Функції, що зберігають 0 та 1. Двоїсті функції. Принцип двоїстості. Повнота системи булевих функцій. Монотонність БФ. Критерій Поста.
Алгебра: G ({0,1}, ,0,1)+закони – булева двохелемента алгебра.

G = ({0,1}, )+законы – алгебра логикы.

Означення. Формула называется булевою, якщо в ний выкорыстовуються



Зауваження: кожний формули видповидаэ булева функция едыным чином.

Булевий функцийи видповидаэ формула не единим чином.

f (x,y) =

Формулы называються еквивалентнымы(ривносыльнымы) якщо воны представляють одну и ту ж саму булеву функцию.

Алгоритм побудови ДДНФ за табличкою истыности.

1. 
   Видмичаэмо ти интерпретацийи на якых f (x1, … , xn) = 1
   
2. 
   Виписуэмо стилькы доданкив, скилькы видмичено интерпретаций, розставляэмо степени:
   
3. 
   Враховуючи, що , одержуемо ДДНФ.
   

Теорема. Будь-яку довильну БФ (крим f ==0) можна подати у вигляди ДДНФ ((f ≠1)ДКНФ), причому, це представленя едине ( з точнистю до перестановкы доданкив).

ДДНФ видносыться до каноничных форм.

Форма называется каноничною якщо:

1. 
   завжды иснуэ,
   
2. 
   вона едына ( з точнистю до порядку зминных)
   
3. 
   завжды иснуэ алгорытм зведення до каноничного виду.
   

ДНФ → ДДНФ (за допомогою формулою розщеплення)

ДКНФ.

Побудова ДКНФ.





Означення. Елементарна дызъюнкция яка мистыть вси зминни называется констытуентою нуля.

Означення. ДКНФ називается така КНФ, у який кожна елементарна дизъюнкция э констытуентою нуля.

Алгоритм побудови ДКНФ за табл. Истинности.

1. 
   Выдиляэмо ти интерпретацийи на якых f(x1, … , xn) = 0
   

2. 
   Выпысуэмо стилькы множникив скилькы э рядкив, де f = 0.
   
3. 
   Проставляэмо степени:
   
4. 
   Рахуэмо.
   

Алгебра Жегалкина.

Означення. Алгеброю Жегалкина называется , виконуються закони:

1. 
   Комутатывности. xy = yx;
   
2. 
   Асоциатывности.
   
3. 
   Дистрибутивнисть лдя конъюнкция видносно .
   

x(y z) = xy xz

4. 
   Иденпотентисть для
   
5. 
   Зведення подибных для
   
6. 
   Спиввидношення для констант
   

Формулы переходу вид алгебры буля до алгебры жегалкина

7. 
   
   
8. 
   
   

Формулы переходу вид алгебры жегалкина до алгебры буля

9. 
   
   

Полином Жегалкина (канонична форма булевых функий)

Означення. Елементарна конъюнкция называется монотонною, якщо вона не мистыть заперечень зминных.

Означення. Килькисть зминных яки входять в елементарну конъюнкцию называются рангом елементарнойи конъюнкцийи.

Означення. Полиномом жегалкина называется скинченна сума за модулем 2 попарно ризных елементарных конъюнкций над множиною зминных. {x1, … , xn}

Означення. Найбильный з рангив елементарнойи конъюнкцийи, що входить в полином называется степенем многочлена.


8. Мінімізація булевих функцій. Аналітичний метод, карти Карно, метод Квайна.
Ролдор

дэждж
скачати