Juk_Ilyenko_Moklyachuk_Orlovskiy_DM_praktikum

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

пр1 = { | : ( , ) }

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

пр2 = { | : ( , ) }

Образ множини

( ) = { |( , ) та }

Прообраз множини

−1( ) =

{

( , )

та

}

|

Iнверсiя графiка

−1 = {( , )|( , ) }

Композицiя графiкiв та

=

{( , )| :

( , )

та ( , ) }

Основнi типи спiввiдношень

Скрiзь визначене

пр1 =

Сюр’єктивне

пр2 =

Функц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, 2, . . . , , то

загальне число способiв здiйснити

дiї буде 1 · 2 . . . ·

Впорядкована множина

множина, елементи якої розм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ном ньютона

( + ) =

−

=0

∑

Комбiнацiї з повтореннями iз

групи, якi мiстять по елементiв,

по

причому кожен елемент належить

одному з типiв

Кiлькiсть комбiнацiй з повто-

реннями iз по

~

=

+ −1

Перестановки з повторення-

перестановки,

якi мiстять еле-

ми

ментiв,

причому

кожен

елемент

належить одному з типiв ( 1

елементiв першого типу, 2 еле-

ментiв другого типу, . . ., еле-

ментiв -го типу

Кiлькiсть перестановок з по-

втореннями

( 1, 2, . . . , ) =

!

1! 2! . . . !

чень

+

∑

∑

+

Формула включень та виклю-

|

=1 |

=

−

<

| ∩

∩

|

∑

1

|

2

∩

|−

. . .

+( 1) −1

|

∩

. . .

∩

|

−

Операцiя

Результуюча послiдовнiсть

( ) + ( )

( + ), ≥ 0

( )

( − ), ≥ 0, ≥ 0

( )

( ), ≥ 0

′( )

(( + 1) ), ≥ 0

′( )

(( ) ), ≥ 0

(

=0 − ) , ≥ 0

∫ ( ) · ( )

0 ( )

( −1

/ ), ≥

1

( ( ) + (

))/2

∑0 0 2 0 4 0

−

{

,

, , , , , . . .

}

( ( ) − (− ))/2

{0, 1, 0, 3, 0, 5, . . .}

Таблиця деяких генератрис

Послiдовнiсть

Ряд

Генератриса

= 1, = 0, ̸=

∞

1

∑

−

= 1

=0

1

Послiдовнiсть

Ряд

Генератриса

(1, 2, 3, 4, . . .)

∞

1

∑

−

( + 1)

=0

(1

)2

(1, , 2, 3, . . .)

∞

1

∑

−

1

=0

( 0

, 1

, 2 , 3

, . . .)

∞

∑

(1 + )

=0

(1,

,

, . . .)

+1

+2

∞

1

−

∑

+ −1

(1 ) +1

=0

(0, 1, 1/2, 1/3, . . .)

∞ 1

1

∑

ln

1 +

=1

(0, 1, −1/2, 1/3, . . .)

∞ (−1) +1

ln(1 + )

∑

=1

Лiнiйне однорiдне рекурентне

( + ) = 1 · ( + − 1)+

спiввiдношення (ЛОРС) -го

+ 2 · ( + − 2) + . . . + · ( )

порядку

Характеристичне рiвняння

= 1 −1 + 2 −2 + . . . +

ЛОРС -го порядку

Розв’язок характеристичного

Вiдповiдний

загальний

многочлена

розв’язок

- дiйсний корiнь кратностi 1

·

- дiйсний корiнь кратностi

( 1 + 2 + . . . + )

- комплексний корiнь кр. 1; | | =

| | ( 1 cos( )+ + 2 sin( ))

, arg( ) =

- комплексний корiнь кр. ; | | =

| | (cos( )( 1

+ 2 + . . . +

, arg( ) =

+ ) + sin( )( 1 + 2+

+ . . . + ))

Символи змiнних висловлювань

, , , . . . , , ,

Символи логiчних операцiй

¬, , , →,

Допомiжнi символи

(, ), /

Тавтологiя

≡ 1

Протирiччя

≡ 0.

Рiвносильнiсть

≡ .

Пiдформула формули

частина формули, котра сама є

формулою.

Будь яку пiдформулу можна замiнити на рiвносильну

Формула з тiсними заперече-

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

ннями

до змiнних.

Взаємно двоїстi символи

* ≡

* ≡

1* ≡ 0

0* ≡ 1

Взаємно двоїста до формули

формула *, в якiй всi логiчнi сим-

воли замiненi на двоїстi

Принцип двоїстостi

≡ * ≡ *

Булева функцiя

: → , = {0, 1}

Таблична булева функцiя

булева функцiя, що задається

скiнченним числом змiнних

Тотожний 0

0( ) ≡ 0

Тотожна 1

1( ) ≡ 1

Заперечення

2( ) ≡

Кон’юнкцiя

3( 1, 2) ≡ 1

2

Диз’юнкцiя

4( 1, 2) ≡ 1

2

Iмплiкацiя

5( 1, 2) ≡ 1

→ 2

Заперечення

6

( 1, 2) ≡ 1

9 2

Еквiваленцiя

7

( 1, 2) ≡ 1

2

Пряма сума

8

( 1, 2) ≡ 1

2

Штрих Шефера

9

( 1, 2) ≡ 1| 2

Стрiлка Пiрса

10( 1, 2) ≡ 1 ↓ 2

Iстотна змiнна

( 1, . . . , −1, 0, +1, . . . , ) ̸= ̸=

( 1, . . . , −1, 1, +1, . . . , )

Фiктивна змiнна

( 1, . . . , −1, 0, +1, . . . , ) ≡ ≡

( 1, . . . , −1, 1, +1, . . . , )

Векторне задання

булевої

вектор-стовпчик результатiв буле-

функцiї

вої функцiї

Змiнна висловлювання

, = 0

=

, = 1

Елементарна кон’юнкцiя

кон’юнкцiя змiнних або їх запере-

чень: = 11 22 . . .

Елементарна диз’юнкцiя

диз’юнкцiя змiнних або їх запере-

чень: = 11 22 . . .

Диз’юнктивна

нормальна

диз’юнкцiя елементарних кон’юн-

форма

кцiй: 1 2 . . .

Кон’юнктивна

нормальна

кон’юнкцiя елементарних диз’юн-

форма

кцiй: 1 2 . . .

Алгоритм побудови нормальної форми

1. Замiнити формулу на рiвно-

≡ (

) (

);

→

сильну 1 з логiчними символами

≡

, , ¬

2. Замiнити 1 на рiвносильну 2

≡

;

≡

( )

( )

з тiсними запереченнями

3. Розкрити дужки в формулi 2

ДНФ: ( ) ≡ ( ) ( )

за дистрибутивними законами

КНФ: ( ) ≡ ( ) ( )

3. Спростити отриману формулу

( ) ≡ ; ( ) ≡ ;

за законами поглинання та iдем-

≡ ; ≡

потентностi

Допомiжний полiном

замiна “або” на додавання та “i” на

множення: → +; → ×

Двоїстiсть нормальних форм

(ДНФ( *))* ≡ КНФ( )

Досконала нормальна форма

нормальна форма, кожна еле-

(завершена, довершена)

ментарна кон’юнкцiя (диз’юнкцiя)

якої мiстить всi змiннi формули

або їх заперечення

2. Виключити повторення змiнних

ДДНФ: ≡ ;

≡ 0 ДКНФ:

за законами iдемпотентностi, ви-

≡ ;

≡ 1

ключення третього та протирiччя

3. Додати до елементарних кон’-

ДДНФ: = ( ) (

)

юнкцiй (диз’юнкцiй) змiннi, яких

ДКНФ: = ( ) (

)

не вистачає

4. Вилучити елементарнi кон’юн-

≡ ; ≡

кцiї (диз’юнкцiї), якi повторюю-

ться за законами iдемпотентностi