Juk_Ilyenko_Moklyachuk_Orlovskiy_DM_praktikum

Iмплiканта булевої функцiї

→ ≡ 1

Проста iмплiканта булевої

при видаленi будь-якої букви з

функцiї

вона перестає бути iмплiкантою

Скорочена ДНФ булевої фун-

складається з простих iмплiкант

кцiї

функцiї

Ядрова iмплiканта булевої

при видаленi iмплiканти з ДНФ

функцiї

отримуємо ДНФ, не рiвносильну

Мiнiмальна ДНФ булевої фун-

має найменшу кiлькiсть символiв

кцiї

з усiх з ДНФ функцiї

Глуха ДНФ булевої функцiї

ДНФ iз простих iмплiкант, вида-

лення з якої будь-якої кон’юнкцiї

порушує рiвносильнiсть цiєї ДНФ

булевiй функцiї

Складнiсть ДНФ

Кiлькiсть символiв змiнних у

ДНФ

Формула неповного склею-

( ) (

) ≡

вання

( ) (

)

Граф

= ( , ) - геометрична конфi-

гурацiя, що складається з вершин,

сполучених ребрами

Множина вершин

= { 1, . . . , }

Множина ребер

= { 1, . . . , }

Порядок графу

кiлькiсть вершин графу | |

Сумiжнi вершини

вершини, сполученi ребром: =

( , )

Повний граф

граф, у якого кожнi двi вершини

сумiжнi

Шлях

послiдовнiсть ребер 1, 2, . . . ,

така, що та +1 мають спiльну

вершину

Цикл

шлях, початкова вершина якого

спiвпадає з кiнцевою

Ейлерiв шлях (цикл)

шлях (цикл), коже ребро якого

з’являється лише один раз

Iнцидентнi вершина та ребро

вершина , сполучена з ре-

бром

( : = ( , ))

Степiнь вершини

кiлькiсть ребер, iнцидентних вер-

шинi

Матриця сумiжностi

= || , ||; , – кiлькiсть ребер,

iнцидентних одночасно та

Матриця iнцидентностi

= || , ||; , коли -та вершина

iнцидентна -му ребру, та , = 0,

якщо нi

Iзоморфнi графи та

графи, мiж

множинами

вершин

яких можна

встановити

бiєкцiю,

яка зберiгає сумiжнiсть вершин

Iзольована вершина

вершина, не сполучена з жодною

iншою

Зв’язний граф

будь-якимi двi вершини графа

з’єднує ланцюг

Ейлерiв граф

в графi iснує ейлерiв цикл

Напiвйлерiв граф

в графi iснує незамкнений ейлерiв

ланцюг

Зв’язний граф Ейлерiв кожна його вершина має парну степiнь

Орiєнтований граф (орграф)

граф, ребрам якого (дугам) при-

своєно напрямок

Петля орграфу

дуга, що починається i закiнчує-

ться в тiй самiй вершинi

Матриця сумiжностi

= || , ||; , – кiлькiсть ребер,

що починаються з та закiнчую-

ться в

Матриця iнцидентностi ор-

= || , ||; , = −1 коли -та вер-

графу

шина – початок -ї дуги; , = −1,

якщо кiнець; , = 2, якщо -a ду-

га є петлею

Турнiр

повний орграф

Дерево

зв’язний граф, який не мiстить ци-

клiв

Основнi властивостi дерев

1.

дерево не має циклiв та мiстить | | − 1 ребер;

2.

видалення будь-якого ребра порушить зв’язнiсть;

3.

додавання будь-якого ребра породить цикл;

4.

будь-якi двi вершини пов’язанi рiвно одним шляхом.

Реберний пiдграф ( ′, ′)

пiдграф графа ( , ) такий, що

′ , ′ , причому ′ скла-

дається з кiнцевих вершин ребер

′

Остовне дерево графа ( , )

пiдграф ′( , ′) графа ( , ),

який є деревом

Бiнарна операцiя

математичний об’єкт, що складає-

ться з двох величин i певної дiї над

ними

Нейтральний елемент

елемент , для якого * =

= * = для будь-якого

Обернений елемент до

елемент −1, для якого * −1 =

= −1 * = для будь-якого

Замкнутiсть вiдносно опе-

, : *

рацiї *

Магма

базова алгебраїчна структура, що

складається з множини та замкну-

тої бiнарної операцiєї

Напiвгрупа

асоцiативна магма

Моноїд

напiвгрупа з нейтральним елемен-

том

Група

моноїд з оберненим елементом

Iзоморфiзм груп та

бiєкцiя : → , для якої

, : ( ) * ( ) = ( * )

Пiдгрупа

пiдмножина групи , що є гру-

пою вiдносно операцiї, яка задає

Лiвий (правий) сумiжний

= { : } ( = { :

клас по пiдгрупi групи

})

Циклiчна група

група, породжена своїм елементом

Порядок елемента

найменше додатнє число ( ) =

таке, що =

1

2

3

4

5

a

b

→

( ) → ( → )

1

1

1

1

1

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

2

3

4

5

→

1

1

0

1

1

1

0

0

0

0

0

1

1

1

1

0

0

1

1

1

1

2

3

4

5

6

7

8

→

→

1

1

0

0

1

0

0

0

1

0

0

1

0

1

1

0

0

1

1

0

1

0

0

1

0

0

1

1

1

0

0

0

1.

( → ) ( → ( ));

4.

(( ) → ) → ( → );

2.

→ (

)) → ( );

5.

( → ( )) → (( → ) →

(

3.

( ( → )) →

;

( → ));

6.

→ ) ).

( (

)) ((