Големина на текста:
Множество-определя се от
принадлежащите му елементи. Означава
се А={a,b,c,} като a,b,c са елементи. a
?A, a?A. под мощност на крайно
множество се разбира броя на
елементите в него |A|=3. две множества
са равни А=В ако са образувани от едни
и същи елементи. ако всеки елем. на
А?В ще казваме че А е подмножество
на В или А се съдържа в В: А?В. Ако
А?В и А?В, то а А е същинско
подмножество на В: А?В. Под
обединение (сума) на 2 множества А и
В ще разбираме множеството което се
състои от всички елементи
принадлежащи на поне едно от
множествата А или В. А?В. Св-ва
А?А=А- идемпотентност; А?В=В?А-
комутативност; А??С)=(А?В) ?С-
асоциативност; А?А?В. Сечение е
множеството което се състои от
елементите принадлежащи
едновременно на А и В: А?В. Св-ва:
А?А=А; А?В= В?А; А??С)=
?В) ?С; А? А?В. Диаграма на
Вен- множеството се представя като
част от равнината заградена от
несамопресичаща се затворена линия.
Обединението и сечението имат
свойството дистрибутивност:
А??С)=(А?В)??С);
А??С)=(А?В)??С). Празно
множ. –накоето не принадлежи нито
един елемент: ?. Св-ва: ??А; А??=А;
А??=?. Разлика на множествата А и В
е множество от всички елементи на А
които на принадлежат на В: AB.
AB?A; (AB)?A=A; (AB)?A=AB;
(AB)?B=A?B; (AB)?B=?
Списък – обект подобен на
множеството но в него даден елемент
може да присъства няколко пъти. Ако
редът на елементите в списъка не е
фиксиран той е неподреден
?=(а
1
2
....а
n
), ако редът е фиксиран
списъкът е подреден ?=<а
1
2
....а
n
>.
подреденият списък се нарича редица.
Елементът а
i
в i
-тата
позиция се нарича i
-
та
компонента на списъка. Броя на
елементите се нарича дължина на
списъка.
Под декартово произведение на
множествата А и В ще разбираме
множеството АхВ което се състои от
всички двойки <a
i
, b
i
>, a
i
?А b
i
?В.
Декартово произведение на множествата
А
1
2
....А
n
е множеството А
1
хА
2
х...хА
n
,
< а
i1
i2
....а
in
>, a
ij
?A
j
, j=1,2,…n
T1:
1
хА
2
х...хА
n
|=|А
1
|.|А
2
|…….|А
n
|
Д-во:
Т2: Броя на l- орките които можем да
образуваме от n елемента е n
l
.
Д-во: |A
l
|=|AxAxA….xA|=|A|.|A|…..|A| =
n.n……n =n
l
Вариации. Нека е дадено А={a
1
,a
2
,
….a
n
}. Под вариация от к-ти клас ще
разбираме всяка к- орка от елементите
на А. Ако елементите са различни
вариацията е без повторение. Ако
елементите се повтарят, вариацията е с
повторение. При вариация без
повторение к<=n. V
n
k
. V
n
k
=n!(n-k)! .
rV
n
k
=n
k
. Случая к=n се нарича
пермутация Pn=V
n
n
=n! . Комбинация
на елементите от множеството А от к-ти
клас се нарича всяко подмножество на А
с к- елемента. C
n
k
=n!k!.(n-k)! . При
комбинация с повторения всеки елемент
може да се повтаря по повече от 1 път
rCnk=C
n
k
+k-1
Двоични функции. Дадено е множ.
В={0,1} B
n
=BxBx….xB. Броят на
всички n- орки е 2
n
. Тези n- орки ще
наричаме двоични.
Опр: Под двоична ф-ция f: B
n
->B щя
разбираме функция с област B
n
и
кообласт В
Т: Броят на всички двоични ф-ции на n
променливи е
2
2
n
Опр: Ще казваме че променливата x
i
е
фиктивна за функцията fако е изпълнено
f(x
1
,x
2
…x
i-1
,0,x
i+1
…x
n
)= f(x
1
,x
2
…x
i-
1
,1,x
i+1
…x
n
). Функцията не се променя
ако x
i
е различно.
За n=2 броя функции е
2
2
2
=16, броя n-
орки 2
2
=4
Таблица!
То – f
0
, f
1
, f
2
, f
3
, f
4
, f
5
, f
6
, f
7
T
1
– f
1
, f
3
, f
5
, f
7
, f
9
, f
11
, f
13
, f
15
S – f
3
, f
5
, f
10
, f
12
f
0
– константа 0; f
1
- x
1
.x
2
конюнкция; f
2
-
забрана по x
2
; f
3
- тъждествена на x
1
; f
4
-
забрана пo x
1
; f
5
- тъжд. на x
2
; f
6
- x
1
+x
2
,
сума по модул 2; f
7
- x
1
?x
2
, дизюнкция; f
8
-
стрелка на Пиърс x
1
?x
2
; f
9
- логическа
еднозначност; f
10
- не x
2
; f
11
- импликация
от x
2
към x
1
, x
2
->x
1
; f
12
- не x
1
; f
13
- x
1
->x
2
;
f
14
- черта на Шефер, x
1
|x
2
; f
15
- константа
1. Св-ва на ф-циите: 1) x
1
.x
1
=x
1
,
x
1
?x
1
=x
1
, x
1
+x
1
=0; 2) x
1
.x
2
=x
2
.x
1
,
x
1
?x
2
=x
2
?x
1
, x
1
+x
2
=x
2
+x
1
; 3) x
1
.
(x
2
.x
3
)=(x
1
.x
2
).x
3
, x
1
?(x
2
?x
3
)=(x
1
?x
2
)?x
3
, x
1
+
(x
2
+x
3
)=(x
1
+x
2
)+x
3
; 4) x
1
.
(x
2
?x
3
)=x
1
.x
2
?x
1
.x
3
, x
1
?x
2
.x
3
=(x
1
?x
2
).(x
1
?x
3
),
x
1
.(x
2
+x
3
)=x
1
.x
2
+x
1
.x
3
; 5) x
1
.0=0, x
1
?0=x
1
,
x
1
+0=x
1
; 6)x
1
.1=x
1
, x
1
?1=1, x1+1=
1x
; 7)
01.1 =xx
,
111 =?xx
,
111 =+xx
; 8)
212.1xxxx?=
,
2.121xxxx =?
,
212.1xxxx?=
,
2.121xxxx =?
Съществуват правилата : изразите се
пресмятат отляво надясно; пресмятат се
първо скобите; отрицание; конюнкция;
дизюнкции и сума по модул 2; вси1ки
останали ф-ции.
Формули и суперпозиции. Нека е
дадено множ. F={f
1
(x
1
,x
2
….x
n
),f
2
(x
1
,x
2
x
n
),…}. Под формула над F ще
разбираме: 1) всяка ф-ция от F, 2) всеки
израз от вида : f
i
(
1
,
2
,…
ni
), f
i
?F, a
j
,
j=1,2…n
i
, е формула над F или буква на
променлива.
Пример: f= {f1(x1,x2)=x1.x2,f2(x1,x2)=x1?x2}.
Формули над F са: f
1
(x
1
,x
2
)=x
1
.x
2
,
f
1
(x
2
,x
3
)=x
2
.x
3
, f
2
(x
2
,x
3
)=x
2
?x
3
,
f
1
(x
1
,f
2
(x
2
,x
3
))=x
1
.(x
2
?x
3
)
Опр: Ако 1 ф-ция f се реализира с
формула над F, ще казваме че f е
суперпозиция над F
Опр: Множеството от всички
суперпозиции над F ще наричаме
затворена обвивка или само обвивка на
F. Означава се [F]. Обвивката на F се
състои от всички ф-ции които можем да
реализираме с формули над F.
P
2
– означава се множеството от всички
двоични функции.
Опр: Ще казваме че множеството от
двоични ф-ции ще е равно ако [F]=P
2
.
Т.е. всяка двоична ф-ция се реализира с
формула над F.
Теорема на Буул: Множеството от
двоични функции F={x
1
,x
1
?x
2
,x
1
.x
2
} е
пълно.
Д-во:
Теоремата дава начина за преход от
табличен към аналитичен запис. Това
става: 1) отбелязваме всички n- орки за
които стойността на ф-цията е 1; 2) за
всяка от тях построяваме конюнкция по
следния начин: всяка нула в набора се
замества с отрицанието на съответния
аргумент, а всяка единица с аргумента.
Т2: Нека е дадено множ. F={f
1
(x
1
,x
2
x
n1
),f2(x
1
,x
2
…x
n2
),…} и множ.
G={g
1
(x
1
,x
2
…x
m1
),g2(x
1
,x
2
…x
m2
)…}. Нека
F е пълно множество. НДУ множ. G да е
пълно е ф-циите f
1
,f
2
… да са
суперпозиции над G.
Т на Жегалки: Всяка двоична ф-ция се
реализира с 1 полином на Жегалки.
Базиса е: {x
1
+x
2
,x
1
.x
2
,1}
Множество-определя се от
принадлежащите му елементи. Означава
се А={a,b,c,} като a,b,c са елементи. a
?A, a?A. под мощност на крайно
множество се разбира броя на
елементите в него |A|=3. две множества
са равни А=В ако са образувани от едни
и същи елементи. ако всеки елем. на
А?В ще казваме че А е подмножество
на В или А се съдържа в В: А?В. Ако
А?В и А?В, то а А е същинско
подмножество на В: А?В. Под
обединение (сума) на 2 множества А и
В ще разбираме множеството което се
състои от всички елементи
принадлежащи на поне едно от
множествата А или В. А?В. Св-ва
А?А=А- идемпотентност; А?В=В?А-
комутативност; А??С)=(А?В) ?С-
асоциативност; А?А?В. Сечение е
множеството което се състои от
елементите принадлежащи
едновременно на А и В: А?В. Св-ва:
А?А=А; А?В= В?А; А??С)=
?В) ?С; А? А?В. Диаграма на
Вен- множеството се представя като
част от равнината заградена от
несамопресичаща се затворена линия.
Обединението и сечението имат
свойството дистрибутивност:
А??С)=(А?В)??С);
А??С)=(А?В)??С). Празно
множ. –накоето не принадлежи нито
един елемент: ?. Св-ва: ??А; А??=А;
А??=?. Разлика на множествата А и В
е множество от всички елементи на А
които на принадлежат на В: AB.
AB?A; (AB)?A=A; (AB)?A=AB;
(AB)?B=A?B; (AB)?B=?
Списък – обект подобен на
множеството но в него даден елемент
може да присъства няколко пъти. Ако
редът на елементите в списъка не е
фиксиран той е неподреден
?=(а
1
2
....а
n
), ако редът е фиксиран
списъкът е подреден ?=<а
1
2
....а
n
>.
подреденият списък се нарича редица.
Елементът а
i
в i
-тата
позиция се нарича i
-
та
компонента на списъка. Броя на
елементите се нарича дължина на
списъка.
Под декартово произведение на
множествата А и В ще разбираме
множеството АхВ което се състои от
всички двойки <a
i
, b
i
>, a
i
?А b
i
?В.
Декартово произведение на множествата
А
1
2
....А
n
е множеството А
1
хА
2
х...хА
n
,
< а
i1
i2
....а
in
>, a
ij
?A
j
, j=1,2,…n
T1:
1
хА
2
х...хА
n
|=|А
1
|.|А
2
|…….|А
n
|
Д-во:
Т2: Броя на l- орките които можем да
образуваме от n елемента е n
l
.
Д-во: |A
l
|=|AxAxA….xA|=|A|.|A|…..|A| =
n.n……n =n
l
Вариации. Нека е дадено А={a
1
,a
2
,
….a
n
}. Под вариация от к-ти клас ще
разбираме всяка к- орка от елементите
на А. Ако елементите са различни
вариацията е без повторение. Ако
елементите се повтарят, вариацията е с
повторение. При вариация без
повторение к<=n. V
n
k
. V
n
k
=n!(n-k)! .
rV
n
k
=n
k
. Случая к=n се нарича
пермутация Pn=V
n
n
=n! . Комбинация
на елементите от множеството А от к-ти
клас се нарича всяко подмножество на А
с к- елемента. C
n
k
=n!k!.(n-k)! . При
комбинация с повторения всеки елемент
може да се повтаря по повече от 1 път
rCnk=C
n
k
+k-1
Двоични функции. Дадено е множ.
В={0,1} B
n
=BxBx….xB. Броят на
всички n- орки е 2
n
. Тези n- орки ще
наричаме двоични.
Опр: Под двоична ф-ция f: B
n
->B щя
разбираме функция с област B
n
и
кообласт В
Т: Броят на всички двоични ф-ции на n
променливи е
2
2
n
Опр: Ще казваме че променливата x
i
е
фиктивна за функцията fако е изпълнено
f(x
1
,x
2
…x
i-1
,0,x
i+1
…x
n
)= f(x
1
,x
2
…x
i-
1
,1,x
i+1
…x
n
). Функцията не се променя
ако x
i
е различно.
За n=2 броя функции е
2
2
2
=16, броя n-
орки 2
2
=4
Таблица!
То – f
0
, f
1
, f
2
, f
3
, f
4
, f
5
, f
6
, f
7
T
1
– f
1
, f
3
, f
5
, f
7
, f
9
, f
11
, f
13
, f
15
S – f
3
, f
5
, f
10
, f
12
f
0
– константа 0; f
1
- x
1
.x
2
конюнкция; f
2
-
забрана по x
2
; f
3
- тъждествена на x
1
; f
4
-
забрана пo x
1
; f
5
- тъжд. на x
2
; f
6
- x
1
+x
2
,
сума по модул 2; f
7
- x
1
?x
2
, дизюнкция; f
8
-
стрелка на Пиърс x
1
?x
2
; f
9
- логическа
еднозначност; f
10
- не x
2
; f
11
- импликация
от x
2
към x
1
, x
2
->x
1
; f
12
- не x
1
; f
13
- x
1
->x
2
;
f
14
- черта на Шефер, x
1
|x
2
; f
15
- константа
1. Св-ва на ф-циите: 1) x
1
.x
1
=x
1
,
x
1
?x
1
=x
1
, x
1
+x
1
=0; 2) x
1
.x
2
=x
2
.x
1
,
x
1
?x
2
=x
2
?x
1
, x
1
+x
2
=x
2
+x
1
; 3) x
1
.
(x
2
.x
3
)=(x
1
.x
2
).x
3
, x
1
?(x
2
?x
3
)=(x
1
?x
2
)?x
3
, x
1
+
(x
2
+x
3
)=(x
1
+x
2
)+x
3
; 4) x
1
.(x
2
?x
3
)=x
1
.x
2
?x
1
.x
3
,
x
1
?x
2
.x
3
=(x
1
?x
2
).(x
1
?x
3
), x
1
.
(x
2
+x
3
)=x
1
.x
2
+x
1
.x
3
; 5) x
1
.0=0, x
1
?0=x
1
,
x
1
+0=x
1
; 6)x
1
.1=x
1
, x
1
?1=1, x1+1=
1x
; 7)
01.1 =xx
,
111 =?xx
,
111 =+xx
; 8)
212.1xxxx?=
,
2.121xxxx =?
,
212.1xxxx?=
,
2.121xxxx =?
Съществуват правилата : изразите се
пресмятат отляво надясно; пресмятат се
първо скобите; отрицание; конюнкция;
дизюнкции и сума по модул 2; вси1ки
останали ф-ции.
Формули и суперпозиции. Нека е
дадено множ. F={f
1
(x
1
,x
2
….x
n
),f
2
(x
1
,x
2
x
n
),…}. Под формула над F ще
разбираме: 1) всяка ф-ция от F, 2) всеки
израз от вида : f
i
(
1
,
2
,…
ni
), f
i
?F, a
j
,
j=1,2…n
i
, е формула над F или буква на
променлива.
Пример: f= {f1(x1,x2)=x1.x2,f2(x1,x2)=x1?x2}.
Формули над F са: f
1
(x
1
,x
2
)=x
1
.x
2
,
f
1
(x
2
,x
3
)=x
2
.x
3
, f
2
(x
2
,x
3
)=x
2
?x
3
,
f
1
(x
1
,f
2
(x
2
,x
3
))=x
1
.(x
2
?x
3
)
Опр: Ако 1 ф-ция f се реализира с
формула над F, ще казваме че f е
суперпозиция над F
Опр: Множеството от всички
суперпозиции над F ще наричаме
затворена обвивка или само обвивка на
F. Означава се [F]. Обвивката на F се
състои от всички ф-ции които можем да
реализираме с формули над F.
P
2
– означава се множеството от всички
двоични функции.
Опр: Ще казваме че множеството от
двоични ф-ции ще е равно ако [F]=P
2
.
Т.е. всяка двоична ф-ция се реализира с
формула над F.
Теорема на Буул: Множеството от
двоични функции F={x
1
,x
1
?x
2
,x
1
.x
2
} е
пълно.
Д-во:
Теоремата дава начина за преход от
табличен към аналитичен запис. Това
става: 1) отбелязваме всички n- орки за
които стойността на ф-цията е 1; 2) за
всяка от тях построяваме конюнкция по
следния начин: всяка нула в набора се
замества с отрицанието на съответния
аргумент, а всяка единица с аргумента.
Т2: Нека е дадено множ. F={f
1
(x
1
,x
2
x
n1
),f2(x
1
,x
2
…x
n2
),…} и множ.
G={g
1
(x
1
,x
2
…x
m1
),g2(x
1
,x
2
…x
m2
)…}. Нека
F е пълно множество. НДУ множ. G да е
пълно е ф-циите f
1
,f
2
… да са
суперпозиции над G.
Т на Жегалки: Всяка двоична ф-ция се
реализира с 1 полином на Жегалки.
Базиса е: {x
1
+x
2
,x
1
.x
2
,1}
Релации – под n членна релация в
редицата R <D
1
,D
2
,….D
n
>, където D
1
,D
2
,
….D
n
са множества, ще разбираме
подмножество на декартовото
произведение D
1
хD
2
х….хD
n
– n доменна
релация. Множеството D
i
ще наричаме
i
-ти
домен на релацията. Видове
релации: 1) ако aRa е в сила за всяко а
релацията е рефлексивна; 2) ако от аRb
=> bRa релацията е симетрична; 3) ако
аRb, bRс => аRc релацията е
транзитивна. Ако за дадена релация е
изпълнено 1,2,3 тя е релация на
еквивалентност. 4) ако са дадени а,b
които принадлежат на множеството се
изпълнява aRb или bRa . Релации за
които е изпълнено 1,2,3,4 се наричат
релации на подреждане. Релация която
изпълнява само 1,2,3 е релация на
частично подреждане.
Функции. Нека имаме релация R с
първи домейн А и втори В. Нека за
всяко х?А съществува едно y?B, за
които се изпълнява релацията R: xRy
или (x,y)?R. Релации с това свойство се
наричат функции на А в В, y=F(x).
A=D(F) се нарича дефиниционна област
или област на функцията F. B=R(F) e
област на стойностите или кообласт на
F. Елементът y=F(x) се нарича образ на
х, а х се нарича първообраз на y.
Всеки елемент от
областта А има 1 образ в
кообластта В, но не
всеки елемент от В има
първообраз в А или само
1 първообраз в А.
Опр: ф-ции при които за x
1
?x
2
се
изпълнява F(x
1
)?F(x
2
), т.е. различните
елементи имат различни образи се
наричат еднозначни ф-ции (инекции)
x=F(y). функция при която на всеки
елемент на F(A) можем да съпоставим
елемент x(A) се нарича обратна
y=F(x)=F(F
-1
(y)) x=F
-1
(y)=F
-1
(F(x))
Опр: ако F(A)=B, ф-цията F се нарича
изображение на А върху В или
сюрекция. В този случай всеки елемент
от В има първообраз в А.
Опр: когато 1 ф-ция е сюрекция и
инекция на А в В тя се нарича
еднозначно обратимо съответствие или
биекция.
Т: Нека А и В са крайни множества.
Броят на функциите с област А и
кообласт В е n
l
=|B|
|A|
Графи. Под граф Г ще разбираме
двойката <V,R>, където V={a
1
,a
2
…..a
n
}e
множество, а R е неподреден списък на
двойки елементи на V. Елементите на V
се наричат върхове на графа, а
елементите на R се наричат ребра на
графа. Ако ребрата са наредени двойки,
графът е ориентиран, ако не са
подредени е неориентиран.
Геометрично изображение на граф се
съставя по следния начин: - избират се
толкова точки колкото върхове има
графа; - върховете се съединяват с линия
ако графа е неориентиран и със стрелки
ако е ориентиран. Пример: F=<V,R> ,
V={1,2,3,4,5}, R=((1,2),(2,3),(3,4),(4,5),
(5,1),(1,3),(3,1))
Опр: Под път в ориентиран граф ще
разбираме редицата
<a
i1
,a
i2
>,<a
i2
,a
i3
>…..<a
il-1
,a
il
> от тези
ребра. Ще казваме че пътя води от а
i1
до
а
il
и има дължина (l-1) ребра
Опр: Път със съвпадащи краища се
нарича цикъл
Т: НДУ 1 краен ориентиран граф да
съдържа път с дължина на по-малка от
броя на върховете му n е да има цикъл в
него.
Д-во: построили сме път
<a
i1
,a
i2
>,<a
i2
,a
i3
>…..<a
in
,a
in+1
>. n- ребра =>
n+1 върха . Нашия граф има n- върха, то
поне 1 връх се повтаря следователно
нашия граф е цикъл.
Матрица на съседство. Нека е даден
граф с n върха. Опр: Матрицата А=||C
ij
||
nxn
се нарича матрица на съседство, ако
C
ij
е равно на броя на ребрата които
водят от върха a
i
до върха a
j
.
T: Нека А=||C
ij
||
nxn
e матрица на
съседство на графа Г . Тогава елементът
C
ij
(l)
, на l
- тата
степен на матрицата А е
равен на броя на пътищата с дължина l
които водя от a
i
до a
j
Следствия: 1) НДУ в графа Г да има
цикъл е A
n
?0 т.е. не всички елементи са
нула; 2) НДУ за да има цикъл в е да има
Затворени класове. Класове То и Т
1
.
Опр: множ. С се нарича затворено или
затворен клас ако С=[C]
T: множеството С е затворен клас ако:
1) тъжд. ф-ция fi(x
1
,x
2
….x
n
)=x
i
, i=1,2…n
принадлежи на С; 2) суперпозиции на ф-
ции от С също принадлежат на С
Опр: Ще казваме че ф-цията f(x
1
,x
2
…x
n
)
запазва нулата ако f(0,0....0)=0.
Множеството на всички двоични ф-ции
запазващи нулата ще означим с То. Броя
им е
2
2
n
-1
Опр: Ще казваме че f(x
1
,x
2
…x
n
) запазва
единицата ако f(1,1….1)=1. Множ. от
всички двоични ф-ции запазващи 1 ща
означим с Т
1
.
Т: Множествата То и Т
1
са затворени
класове. Д-во: 1) f
i
(x
1
,x
2
….x
n
)=x
i
; 2) нека
имаме f, g
1
, g
2
…g
n
?To f(g
1
,g
2
g
n
)=f(g1(0,0…0),g
2
(0,0…0),
….g
n
(0,0….0)=0
T: f
0
?To и f
1
?T
1
; F={f
0
,f
1
}. Тогава с
формули над F можем да построим …
константа 0 и 1 и отрицанието не x
1
(x
1
)
{f(x
1
,x
2
..x
n
)=0,f(x
1
,x
2
..x
n
)=1}?[{f
0
,f
1
}]
{x
1
}=[{f
0
,f
1
}]
Д-во: g
0
(x
1
)=f
0
(x
1
,x
1
…x
1
) n- пъти
g
0
(0)=f
0
(0,0…0)=1 , g
0
(1)=f0(1,1…)=0
или g
0
(1)=1
1сл. g
0
(1)=0, g
0
(0)=1 =>g
0
(x
1
)=не x
1
2сл. g
0
(1)=1, g
0
(0)=1 => g
0
(x
1
)=1
g
1
(1)=f
1
(1,1…1)=0, g
1
(0)=0 или g
1
(0)=1
1 сл. g
1
(1)=0, g
1
(0)=0 => g
1
(x
1
)=0
2 сл. g
1
(1)=0, g
1
(0)=1 => g
1
(x
1
)=не x
1
От 4-те случая получаваме 4 множ. {не
x
1
,0};{не x
1
};{1,0};{1,не x
1
} => {не
x
1
,0}?[{f
0
,f
1
}]; {x
1
}?[{f
0
,f
1
}];
{1,0}?[{f
0
,f
1
}]; {1, не x
1
}?[{f
0
,f
1
}]
Двойственост. Самодвойствени ф-
ции. Затворен клас S. ..
Опр: Ф-цията f(x
1
,x
2
…x
n
) ще наричаме
двойствена на f и ще я означаваме
f*(x1,x2…xn) или (f(x1,x2…xn))*
T: Двойствената ф-ция на сложна ф-ция
е сложна ф-ция на двойствените и
компоненти.
Д-во:
Опр: Ще казваме че f(x
1
,x
2
…x
n
) e
самодвойнствена ако f*(x
1
,x
2
x
n
)=f(x
1
,x
2
…x
n
)
Множеството на самодвойствените ф-
ции ще означим с S. Броят на всички
самодвойствени ф-ции е
2
2
n-1
T: Множеството S е затворен клас
F, g
1
…g
n
?S, (f(g
1
,g
2
…g
n
))*=f*(g
1
*,g
2
*…
g
n
*)= f*(g
1
,g
2
…g
n
)=f(g
1
,g
2
…g
n
)
T: Константите 0 и 1 са суперпозиции
над {f
0
,f
1
,f
s
}
{0,1,не x}?[{f
0
,f
1
,f
s
}] , f
0
?To, f
1
?T
1
,
fs?S .. ..
x1 x
a
{x, a=0 0
a
=a
x, a=1 1
a
=a.. .. ..
fs?S => f(a
1
,a
2
…a
n
)=f(a
1
,a
2
…a
n
)
g
s
(x
1
)=f(x
1
a1
,x
1
a2
…x
1
an
).. .. ..
g
s
(0)=f(0
a1
,0
a2
…0
an
)=f(a
1
,a
2
…a
n
)= f(a
1
,a
2
a
n
)=f(1
a1
,1
a2
…1
an
)=g
s
(1)
Дърветата са специален вид
ориентирани графи. Всяко дърво има
връх наречен корен и върхове наречени
листа. От листата не излизат ребра.
Дървото е граф без цикъл.
Нека Т е дърво с к-1 върха, корен r и
листа l
1
,l
2
….l
n
. избираме връх b не
принадлежащ на дървото. Прекарваме
ребро от някои връх а на Т до b.
Получихме ново дърво с корен r и к-
върха. Ако а не е лист на Т, то листата
на новото дърво са l
1
,l
2
….l
n
и b. Ако а е
лист на Т той се заменя с листа b.
T: Дърво с n – върха има n-1 ребра .
Дължината на пътя от корена до най-
далечния лист се нарича височина на
дървото . Дървото има точно 1 път от
корена до който и да е връх.
Релации – под n членна релация в
редицата R <D
1
,D
2
,….D
n
>, където D
1
,D
2
,
….D
n
са множества, ще разбираме
подмножество на декартовото
произведение D
1
хD
2
х….хD
n
– n доменна
релация. Множеството D
i
ще наричаме
i
-ти
домен на релацията. Видове
релации: 1) ако aRa е в сила за всяко а
релацията е рефлексивна; 2) ако от аRb
=> bRa релацията е симетрична; 3) ако
аRb, bRс => аRc релацията е
транзитивна. Ако за дадена релация е
изпълнено 1,2,3 тя е релация на
еквивалентност. 4) ако са дадени а,b
които принадлежат на множеството се
изпълнява aRb или bRa . Релации за
които е изпълнено 1,2,3,4 се наричат
релации на подреждане. Релация която
изпълнява само 1,2,3 е релация на
частично подреждане.
Функции. Нека имаме релация R с
първи домейн А и втори В. Нека за
всяко х?А съществува едно y?B, за
които се изпълнява релацията R: xRy
или (x,y)?R. Релации с това свойство се
наричат функции на А в В, y=F(x).
A=D(F) се нарича дефиниционна област
или област на функцията F. B=R(F) e
област на стойностите или кообласт на
F. Елементът y=F(x) се нарича образ на
х, а х се нарича първообраз на y.
Всеки елемент от
областта А има 1 образ в
кообластта В, но не
всеки елемент от В има
първообраз в А или само
1 първообраз в А.
Опр: ф-ции при които за x
1
?x
2
се
изпълнява F(x
1
)?F(x
2
), т.е. различните
елементи имат различни образи се
наричат еднозначни ф-ции (инекции)
x=F(y). функция при която на всеки
елемент на F(A) можем да съпоставим
елемент x(A) се нарича обратна
y=F(x)=F(F
-1
(y)) x=F
-1
(y)=F
-1
(F(x))
Опр: ако F(A)=B, ф-цията F се нарича
изображение на А върху В или
сюрекция. В този случай всеки елемент
от В има първообраз в А.
Опр: когато 1 ф-ция е сюрекция и
инекция на А в В тя се нарича
еднозначно обратимо съответствие или
биекция.
Т: Нека А и В са крайни множества.
Броят на функциите с област А и
кообласт В е n
l
=|B|
|A|
Графи. Под граф Г ще разбираме
двойката <V,R>, където V={a
1
,a
2
…..a
n
}e
множество, а R е неподреден списък на
двойки елементи на V. Елементите на V
се наричат върхове на графа, а
елементите на R се наричат ребра на
графа. Ако ребрата са наредени двойки,
графът е ориентиран, ако не са
подредени е неориентиран.
Геометрично изображение на граф се
съставя по следния начин: - избират се
толкова точки колкото върхове има
графа; - върховете се съединяват с линия
ако графа е неориентиран и със стрелки
ако е ориентиран. Пример: F=<V,R> ,
V={1,2,3,4,5}, R=((1,2),(2,3),(3,4),(4,5),
(5,1),(1,3),(3,1))
Опр: Под път в ориентиран граф ще
разбираме редицата
<a
i1
,a
i2
>,<a
i2
,a
i3
>…..<a
il-1
,a
il
> от тези
ребра. Ще казваме че пътя води от а
i1
до
а
il
и има дължина (l-1) ребра
Опр: Път със съвпадащи краища се
нарича цикъл
Т: НДУ 1 краен ориентиран граф да
съдържа път с дължина на по-малка от
броя на върховете му n е да има цикъл в
него.
Д-во: построили сме път
<a
i1
,a
i2
>,<a
i2
,a
i3
>…..<a
in
,a
in+1
>. n- ребра =>
n+1 върха . Нашия граф има n- върха, то
поне 1 връх се повтаря следователно
нашия граф е цикъл.
Матрица на съседство. Нека е даден
граф с n върха. Опр: Матрицата А=||C
ij
||
nxn
се нарича матрица на съседство, ако
C
ij
е равно на броя на ребрата които
водят от върха a
i
до върха a
j
.
T: Нека А=||C
ij
||
nxn
e матрица на
съседство на графа Г . Тогава елементът
C
ij
(l)
, на l
- тата
степен на матрицата А е
равен на броя на пътищата с дължина l
които водя от a
i
до a
j
Следствия: 1) НДУ в графа Г да има
цикъл е A
n
?0 т.е. не всички елементи са
нула; 2) НДУ за да има цикъл в е да има
Затворени класове. Класове То и Т
1
.
Опр: множ. С се нарича затворено или
затворен клас ако С=[C]
T: множеството С е затворен клас ако: 1)
тъжд. ф-ция fi(x
1
,x
2
….x
n
)=x
i
, i=1,2…n
принадлежи на С; 2) суперпозиции на ф-
ции от С също принадлежат на С
Опр: Ще казваме че ф-цията f(x
1
,x
2
…x
n
)
запазва нулата ако f(0,0....0)=0.
Множеството на всички двоични ф-ции
запазващи нулата ще означим с То. Броя
им е
2
2
n
-1
Опр: Ще казваме че f(x
1
,x
2
…x
n
) запазва
единицата ако f(1,1….1)=1. Множ. от
всички двоични ф-ции запазващи 1 ща
означим с Т
1
.
Т: Множествата То и Т
1
са затворени
класове. Д-во: 1) f
i
(x
1
,x
2
….x
n
)=x
i
; 2) нека
имаме f, g
1
, g
2
…g
n
?To f(g
1
,g
2
g
n
)=f(g1(0,0…0),g
2
(0,0…0),
….g
n
(0,0….0)=0
T: f
0
?To и f
1
?T
1
; F={f
0
,f
1
}. Тогава с
формули над F можем да построим …
константа 0 и 1 и отрицанието не x
1
(x
1
)
{f(x
1
,x
2
..x
n
)=0,f(x
1
,x
2
..x
n
)=1}?[{f
0
,f
1
}]
{x
1
}=[{f
0
,f
1
}]
Д-во: g
0
(x
1
)=f
0
(x
1
,x
1
…x
1
) n- пъти
g
0
(0)=f
0
(0,0…0)=1 , g
0
(1)=f0(1,1…)=0
или g
0
(1)=1
1сл. g
0
(1)=0, g
0
(0)=1 =>g
0
(x
1
)=не x
1
2сл. g
0
(1)=1, g
0
(0)=1 => g
0
(x
1
)=1
g
1
(1)=f
1
(1,1…1)=0, g
1
(0)=0 или g
1
(0)=1
1 сл. g
1
(1)=0, g
1
(0)=0 => g
1
(x
1
)=0
2 сл. g
1
(1)=0, g
1
(0)=1 => g
1
(x
1
)=не x
1
От 4-те случая получаваме 4 множ. {не
x
1
,0};{не x
1
};{1,0};{1,не x
1
} => {не
x
1
,0}?[{f
0
,f
1
}]; {x
1
}?[{f
0
,f
1
}];
{1,0}?[{f
0
,f
1
}]; {1, не x
1
}?[{f
0
,f
1
}]
Двойственост. Самодвойствени ф-ции.
Затворен клас S. ..
Опр: Ф-цията f(x
1
,x
2
…x
n
) ще наричаме
двойствена на f и ще я означаваме
f*(x1,x2…xn) или (f(x1,x2…xn))*
T: Двойствената ф-ция на сложна ф-ция
е сложна ф-ция на двойствените и
компоненти.
Д-во:
Опр: Ще казваме че f(x
1
,x
2
…x
n
) e
самодвойнствена ако f*(x
1
,x
2
x
n
)=f(x
1
,x
2
…x
n
)
Множеството на самодвойствените ф-
ции ще означим с S. Броят на всички
самодвойствени ф-ции е
2
2
n-1
T: Множеството S е затворен клас
F, g
1
…g
n
?S, (f(g
1
,g
2
…g
n
))*=f*(g
1
*,g
2
*…
g
n
*)= f*(g
1
,g
2
…g
n
)=f(g
1
,g
2
…g
n
)
T: Константите 0 и 1 са суперпозиции
над {f
0
,f
1
,f
s
}
{0,1,не x}?[{f
0
,f
1
,f
s
}] , f
0
?To, f
1
?T
1
, fs?S
.. ..
x1 x
a
{x, a=0 0
a
=a
x, a=1 1
a
=a.. .. ..
fs?S => f(a
1
,a
2
…a
n
)=f(a
1
,a
2
…a
n
)
g
s
(x
1
)=f(x
1
a1
,x
1
a2
…x
1
an
).. .. ..
g
s
(0)=f(0
a1
,0
a2
…0
an
)=f(a
1
,a
2
…a
n
)= f(a
1
,a
2
a
n
)=f(1
a1
,1
a2
…1
an
)=g
s
(1)
Дърветата са специален вид
ориентирани графи. Всяко дърво има
връх наречен корен и върхове наречени
листа. От листата не излизат ребра.
Дървото е граф без цикъл.
Нека Т е дърво с к-1 върха, корен r и
листа l
1
,l
2
….l
n
. избираме връх b не
принадлежащ на дървото. Прекарваме
ребро от някои връх а на Т до b.
Получихме ново дърво с корен r и к-
върха. Ако а не е лист на Т, то листата
на новото дърво са l
1
,l
2
….l
n
и b. Ако а е
лист на Т той се заменя с листа b.
T: Дърво с n – върха има n-1 ребра .
Дължината на пътя от корена до най-
далечния лист се нарича височина на
дървото . Дървото има точно 1 път от
корена до който и да е връх.
път с дължина n път с дължина n

Това е само предварителен преглед

За да разгледате всички страници от този документ натиснете тук.
Последно свалили материала:
ДАТА ИНФОРМАЦИЯ ЗА ПОТРЕБИТЕЛЯ
12 фев 2020 в 22:09 студент на 20 години от Пловдив - ПУ "Паисий Хилендарски", факулетет - Факултет по математика и информатика, специалност - Софтуерни технологии, випуск 2020
16 яну 2020 в 09:24 студент на 27 години от Шумен - Шуменски университет "Епископ Константин Преславски", факулетет - Факултет по технически науки, специалност - Компютърни и информационни системи, випуск 2021
15 яну 2020 в 10:20 родител
07 мар 2019 в 14:06 ученик на 28 години от Пловдив - ОБУ "Свети Иван Рилски", випуск 2011
27 яну 2019 в 18:43 студент на 21 години от Велико Търново - ВТУ, факулетет - Философски, специалност - Психология, випуск 2021
 
 

Пищови по дискретни структури

Материал № 733068, от 18 окт 2011
Свален: 163 пъти
Прегледан: 221 пъти
Предмет: Компютърни системи за управление
Тип: Пищов
Брой страници: 3
Брой думи: 3,261
Брой символи: 15,664

Потърси помощ за своята домашна:

Имаш домашна за "Пищови по дискретни структури"?
Намери бързо решение, с помощтта на потребители на Pomagalo.com:

Намери частен учител

Нина Урумова
преподава по Компютърни системи за управление
в град Варна
с опит от  15 години
289 78

виж още преподаватели...
Последно видяха материала