Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Дискретная математика - методичка

.pdf
Скачиваний:
30
Добавлен:
02.02.2015
Размер:
718.13 Кб
Скачать

П Е Р Е Д М О В А

Кожна математична теорія стає більш зрозумілою та доступною, якщо її вдається застосувати для розв’язання практичних задач. Цей посібник дозволить кожному студенту придбати навички використання теоретичних знань на практиці. Він може бути використаний студентами як денної, так і заочної форми навчання різних спеціальностей, до навчальної програми яких входить вивчення “ Дискретної математики”.

В посібнику коротко викладається необхідний теоретичний матеріал та наводяться формули, які потрібні для розв’язання задач. Кожна задача має 31 варіант. В якості еталонного розв’язаний нульовий варіант. Всі задачі різних варіантів однотипні. Числові дані наведені в таблицях і знаходяться за номером варіанта. При вивченні курсу студент розв’язує свій варіант з набору задач.

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

1

І. Елементи теорії множин

Основні поняття

Множини є неозначене математичне поняття. Проілюструвати множину можна на прикладах.

1)Множина книжок в бібліотеці.

2)Множина непарних чисел.

3)Множина функцій неперервних на певному відрізку, тощо. Множини позначаються великими літерами латинського алфавіту А, В,

С, …, N , …, а елементи множин маленькими літерамиа, b, c, …, n, … Якщо елемента належить множиніА, то пишутьа А, в протилежному випадкуа А (елемент а не належить множиніА).

Кількість елементів скінченої множини А має назвупотужності А і позначається|. Множина, яка не містить жодного елемента називаєтьсяпорожньою та позначається .

Способи опису множин

1.Перерахування всіх елементів.

Наприклад, А={0;1;2;3;4;5;6;7;8;9}.

2.Показ характеристичної властивості елементів даної множини.

Наприклад, якщо F – множина коренів рівнянняsin 2x =0 , яка належить

інтервалу [0;2π], то пишуть: F ={ x : sin x =0, x [0;2π]} .

2

Порівняння множин

Якщо кожен елемент множини А є також елементом множинВ, тоА має назвупідмножини (або частини) множиниВ. ПозначаєтьсяА В.

Множини А таВ рівні, якщо одночасно виконуються умовиА В таВ А. ПозначаєтьсяА=В.

Діаграми Ейлера-Венна

Множина, яка об'єднує всі однотипні множини, має назву універсальної множини, абоуніверсума. Позначається І.

Наприклад, універсумом зоології є множина всіх тварин. Універсумом математики є множина чисел.

Множини і операції над множинами для наочності зображають на площині в вигляді кругів Ейлера. Універсум І зображають у вигляді області прямокутника, а його підмножини – в вигляді кругів, еліпсів, тощо.

2

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

1. Заперечення (доповнення) множини.

Означення: Запереченням множиниА називають множинуA (неА), елементами якої є всі елементи універсума, за виключенням елементів мно-

жини А. З означення виходить, що A =А

A заштриховано

2. Переріз множин.

Означення: Перерізом множинА таВ називають множинуА∩В (А×В), яка складається з усіх елементів, що належатьА таВ одночасно

A I B заштриховано

3. Об'єднання множин.

Означення: Об'єднанням множин А та В називається множинаАUВ (А+В), яка складається з усіх елементів, що належать хоча б одній з цих множин

АUВ заштриховано

Примітка 1. Операції перерізу та об'єднання можна узагальнити наn

n

n

множин (n>2) А12U…U Аn=U Ai ; А1∩А2∩…

∩Аn=I Ai .

i=1

i=1

Примітка 2. Якщо в виразі немає дужок, то спочатку виконується заперечення (доповнення), потім переріз, потім об'єднання.

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

1.Комутативність АUВ=ВUА; А∩В=В∩А.

2.Асоціативність АUВUС=(АUВ)UС=АU(ВUС)

А∩В∩С=(А∩В)∩С=А∩(В∩С).

3

3.Дистрибутивність

3.1.А∩(ВUС)=(А∩В)U(А∩С)

3.2.АU(В∩С)=(АUВ)∩(АUС).

4.АUА=А; А∩А=А

5.АU A =І; АU A =

6.АUІ=І; А∩І=А

7.АU =А; А∩ =

8.Правило де Моргана A I B = A I B ;A I B = A U B .

9.Поглинання A U (A I B) =A

A I (AU B) = A

Примітка 3. Правило де Моргана можна узагальнити на випадокn

множин (n>2): A1 È A2 È ...È An = A1 Ç A2 Ç ...Ç An

A1 ÇA2 Ç...ÇAn =A1 ÈA2 È... ÈAn .

Операції заперечення, перерізу та об'єднання називають базисними операціями. Через ці операції можна виразити інші операції теорії множин, наприклад різницю множин, симетричну різницю.

4. Різниця множин.

Означення: Різницею множинА іВ називається множинаА\В, що складається з усіх елементівА, які не належатьВ А\В={х: х A, х B}

А\В заштриховано

Легко побачити, що А \ А= , А \ A =А; A \ А= A ; А \ І= ; І \ А = A ,

А \ =А; \ А = .

Різницю множин можна записати формулою: А \ В = А ∩B . Різниця множин не комутативна та не асоціативна.

5. Симетрична різниця (диз’юнктивна сума)

Означення: Симетричною різницею множинА іВ називається множинаАÅВ, яка складається з елементів множиниА або множиниВ, за виключенням елементів, які належатьА іВ одночасно

АÅВ={х: х A або х B та х А∩B}

Симетрична різниця комутативна і асоціативна крім того АÅА= ;

АÅ A =І; АÅІ= A; АÅ =А

АÅВ заштриховано

4

За допомогою діаграми Ейлера-Венналегко показати, що

АÅВ=(АUВ)\(А∩В), АÅВ=(А\В)U(В\А)=(A I B)U (B I A).

ІІ. Відповідності та відношення

Прямий (декартовий) добуток множин

Нехай маємо дві множини: A={a1,a2,….,a n}таВ={b1,b2,….,b m}.

 

Означення. Прямим

(декартовим) добутком множин А таВ (познача-

ється

А×В)

називається

множина

усіх

упорядкованих

пар

(ai,bj),

i =

 

 

j =

 

 

таких, що перший елемент належить множині А, а другий –

1,n,

1,m

множині В.

 

 

 

 

 

 

 

 

 

 

Відповідно, декартовим добутком

трьох множин

А,

В, С

(С={с12,…., ср})

називається множина усіх упорядкованих трійок (ai,bj,ck),

i =

 

 

j =

 

,

k =

 

, де ai А, bj В,

ck С, позначаєтьсяА×В×С, тощо.

1,n,

1,m

1, p

Відповідності. Відношення.

Відповідністю називається будь який зв'язок між елементами одній множини або елементами різних множин.

Поняття відповідності – найбільш загальне поняття, на якому базуються поняття функції, відображення, тощо.

Для того, щоб задати відповідність G між елементами множин X таY необхідно вказати, які елементиy Y відповідають елементамх Х, тобто вказати пари(х, у).

Відношення є частинним випадком відповідності, але заданої не на різних множинах, а на одній множиниХ. Між елементами цієї множини можуть існувати певні логічні зв'язки, тобто елементи знаходяться в певних відношеннях один з одним. Той факт, що елементихi Х знаходиться у відношенніR з елементомхj Х записується так:хiR хj, або (хi, хj)R .

Таке відношення називається бінарним. Таким чином, бінарне відношення, яке задано на множині Х є підмножина декартового добуткуХ×Х. R Х×Х.

Способи завдання відношень

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

Приклад 1. Відношення R – " бути менше", яке задано на множині

А={1,3,4,8,9}.

Його можна задати:

1. Перерахуванням пар: R={(1,3),(1,4),(1,8),(1,9),(3,4),(3,8),(3,9),(4,8),(4,9),(8,9)}

5

2. Таблицею: якщо пара (аi, аj)R, то на перетиніі-горядка таj-гостовпця стоїть одиниця, якщо (аi, аj)R – то 0.

В нашому прикладі маємо:

R

1

3

4

8

9

 

 

 

 

 

 

1

0

1

1

1

1

 

 

 

 

 

 

3

0

0

1

1

1

4

0

0

0

1

1

8

0

0

0

0

1

9

0

0

0

0

0

 

 

 

 

 

 

 

0

1

1

1

1

 

 

0

0

1

1

1

 

або R =

0

0

0

1

1

.

 

0

0

0

0

1

 

 

 

0

0

0

0

0

3. Граф. Елементи позначаються точками (вершинами), а зв'язок між ними – дугами (ребрами), причому дуга має напрямок – від першого елемента пари до другого.

1

3

9

8 4

Операції над відношеннями

Оскільки відношення є множина, то над відношеннями виконуються всі ті операції, що й над множинами: об’єднання, переріз, різниця, симетрична різниця, доповнення (до Х×Х). Крім того існують операції інверсія та композиція.

1. Інверсія – будується на основі поняттяінверсії пари, тобто інверсія пари (хi, хj) є пара (хj, хi). Інверсія відношенняR є відношенняR-1,яке утворене інверсією пар.R-1 ще називаютьоберненим відношенням доR. Для відношенняR (приклад 1)R-1 є:

R-1={(3,1),(4,1),(8,1),(9,1),(4,3),(8,3),(9,3),(8,4),(9,4),(9,8)}.

2. Нехай на множині Х задано відношенняR таР. Нехай (аi, аj)R, а (аjк) Р.Композицією цих двох пар є пара (аi, ак). Композицією відношеньR таР називається відношенняQ=R○P, яке утворено композицією пар. Наприклад, нехай на множиніА={1,3,4,8,9} задано відношенняR – " бути менше" (приклад 1) таР – " ділитись без залишку", тобто

6

Р={(9,1),(8,1),(4,1),(3,1),(9,3),(8,4)(1,1),(3,3),(4,4),(8,8),(9,9)}.

Тоді R○P=Q={(1,1), (1,3), (1,4), (1,8), (1,9), (3,1), (3,4), (3,8), (3,3), (3,9),

(4,1), (4,4), (4,8), (4,3), (4,9), (8,1), (8,3), (8,9)}.

Властивості відношень

1. Рефлексивність.

Означення. ВідношенняR називається рефлексивним, якщо кожен елемент множиниА, на якому задано відношення, знаходиться в цьому відношенні сам з собою, тобтоai A; (ai,ai) R. Граф рефлексивного відношення при кожній вершині має петлю.

2. Антирефлексивність.

Означення. ВідношенняR називається антирефлексивним, якщо жоден з елементів множиниА, на якому задано відношення, не знаходиться в цьому відношенні сам з собою, тобтоai A; (ai,ai) R. У графа антирефлексивного відношення аніяка вершина не має петель.

3. Симетричність.

Означення. ВідношенняR називається симетричним, якщо для будь якої пари(ai, aj) R, ai, aj A одночасно виконується умова(aj,ai) R. Граф симетричного відношення має тільки подвійні ребра різного напрямку, а петлі можуть бути, або не бути.

4. Антисиметричність.

Означення. ВідношенняR називається антисиметричним, якщо для жодної пари різних елементівai, aj A, таких, що(ai, aj) R, одночасно не виконується умова(aj,ai) R. Граф антисиметричного відношення містить тільки одинарні ребра, а петлі можуть бути, або не бути.

5. Транзитивність.

Означення. ВідношенняR називається транзитивним, якщо з того, що одночасно виконуються умови(ai, aj) R, та (aj, aк) R випливає умова

(ai,aк) R.

На графі транзитивного відношення якщо є два послідовних ребра одного напрямку, то обов’язково повинно бути ребро, яке йде з початку першого ребра до кінця другого.

Види відношень

1. Еквівалентність.

Еквівалентністю називається відношення R, яке задовольняє властивостям рефлексивності, симетричності та транзитивності.

2. Частковий порядок.

Означення. Частковим порядком називається відношенняR, яке задовольняє властивостям рефлексивності, антисиметричності та транзитивності.

7

3. Суворий порядок.

Означення. Суворим порядком називається відношенняR, яке задовольняє властивостям антирефлексивності, антисиметричності та транзитивності.

Ш. Елементи математичної логіки.

Логіка (logos – слово, думка, мова, розум – з грецької) це сукупність наук про закони та форми мислення. Можна казати про традиційну логіку, яка є початковою сходинкою логіки та вивчає загальні форми висновків та способи зв'язку висловлювань в висновках. (Аристотель IV століття до н.е.).

Криза традиційної логіки підштовхнула дослідників до розроблення інших підходів щодо формалізації висновків.(Джордж Буль, Огюст де Морган – середина ХІХ ст.) В наслідок цього виникла математична логіка (теоретична логіка, символічна логіка) та закладено основи алгебри логік – булевої алгебри.

Булева алгебра

Логічними (булевими) змінними називають змінні, які приймають значення 0 або 1.

Логічною називають функцію f(x1,x2,…,x n), завдану на множині логічних змінних{x1,x2,…,x n} і яка приймає значення 0 або 1. З комбінаторним відомо, що дляn – містної функції кількість різних наборів змінних дорівнює2n. Логічні функції можна задати формулами або таблицями, які мають назву таблиць істинності. Область визначення логічної функції – це множина наборів, на яких вона є визначеною.

 

x1

x2

x3

f(x1,x2,x3)

 

 

 

 

 

 

0

0

0

1

Приклад.

0

0

1

1

 

0

1

0

-

Область визначеності –

1

0

0

0

набори (0,0,0), (0,0,1),

0

1

1

0

(1,0,0), (0,1,1), (1,1,1)

 

 

 

 

 

1

0

1

-

 

1

1

0

-

 

1

1

1

1

 

 

 

 

 

Основні елементарні логічні функції

1. Інверсія (Ні, заперечення, ¬, доповнення). Інверсіяf(x)= х - логічна функція однієї змінної, яка задається таблицею істинності:

8

х

 

 

Легко побачити, що

х

 

 

 

 

 

= х

 

 

 

 

х

 

 

 

01

10

2.Кон'юнкція (І, логічний добуток).

Кон'юнкція – це бінарна логічна функція, яка задається виразом:

f(x1, x2)= x1Ù x2º x1× x2= x1 x2=min{ x1, x2}

Таблиця істинності кон'юнкції має вигляд

x1

x2

x1Ù x2

 

 

 

 

x1 таx2 – логічні співмножники

0

0

0

0

1

0

 

1

0

0

 

1

1

1

 

 

 

 

 

3. Диз'юнкція (АБО, математичне додавання).

Диз'юнкція – це бінарна логічна функція, яка задається виразом:

f(x1, x2)= x1Ú x2=mах{ x1, x2}

Її таблиця істинності має вигляд:

x1

x2

x1Ú x2

 

 

 

 

x1 таx2 – логічні доданки

0

0

0

0

1

1

 

1

0

1

 

1

1

1

 

 

 

 

 

Примітка. Операції кон'юнкції та диз'юнкції можна узагальнити наn логічних співмножників та n логічних доданків.

Основні тотожності алгебри Буля

1. Диз'юнкція та кон'юнкція комутативні x1Ú x2 = x2Ú x1, x1Ù x2 = x2Ù x1.

2. Диз'юнкція та кон'юнкція асоціативні а) (x1Ú x2 )Ú x3 = x1Ú ( x2Ú x3)

б) (x1Ù x2 )Ù x3 = x1Ù ( x2Ù x3)

3. Диз'юнкція та кон'юнкція взаємно дистрибутивні а) x1Ú ( x2Ù x3)=(x1Ú x2 )Ù( x1Ú x3)= (x1Ú x2 )( x1Ú x3)

9

б) x1 ( x2 x3)= (x1 x2 ) ( x1 x3)=x1 x2 x1 x3

4.

 

Правила де Моргана (закони де Моргана)

а)

 

 

 

 

 

 

=

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x

х

х

х

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

2

1

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

=

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

б)

x

х

 

х

 

х

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

2

1

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

=

 

 

 

 

 

 

 

....

 

 

 

 

 

 

Взагалі x

 

х

 

... х

 

 

 

 

х

1

х

2

х

 

 

 

 

 

 

 

1 2

 

 

 

 

 

 

 

 

n

 

 

 

 

 

 

 

n

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

=

 

 

 

 

....

 

 

 

 

 

 

 

 

 

 

 

 

x

х ... х

 

 

 

 

 

 

 

 

 

 

х

х

х

 

 

 

 

 

 

 

1

2

 

 

 

 

 

 

n

1

 

2

 

 

 

 

n

5.

х х = х

 

 

 

 

х х = х

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

х

 

= 0

 

 

 

 

х

 

= 1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

х

 

 

 

х

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

х 0 = 0

 

 

 

 

х 0 = х

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

х 1 = х

 

 

 

 

х 1 = 1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6.

 

Закон поглинання

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x1 x2 x1 = x1, ( x1 x2) x1 = x1

 

 

 

 

 

 

7.

 

Закон склеювання

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x1x2x1

 

= x1, (x1 x2) (x1

 

 

)= x1

 

 

х

х

 

 

 

 

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

 

 

Довести тотожність можна за допомогою таблиць істинності.

Якщо в логічному виразі відсутні дужки, то спочатку виконуються операції заперечення, потім кон'юнкції, далі – диз'юнкції.

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

а) імплікація (логічне слідування)

f(x1, x2)= x1x2=

 

х2

(якщо x1, тоx2).

х

 

 

1

 

 

 

Таблиця істинності має вигляд:

 

 

 

 

 

 

x1

x2

x1x2

 

 

 

 

 

0

0

1

 

0

1

1

 

1

0

0

 

1

1

1

 

б) еквіваленція (функція рівнозначності)

f(x1, x2)= x1 x2=

 

 

 

 

x1х2

х

х

2

1

 

 

 

10

Калькулятор

Сервис бесплатной оценки стоимости работы

  1. Заполните заявку. Специалисты рассчитают стоимость вашей работы
  2. Расчет стоимости придет на почту и по СМС

Нажимая на кнопку, вы соглашаетесь с политикой конфиденциальности и на обработку персональных данных.

Номер вашей заявки

Прямо сейчас на почту придет автоматическое письмо-подтверждение с информацией о заявке.

Оформить еще одну заявку