EULER T: Graf, który ma cykl Eulera, musi mieć wszystkie wierzchołki stopnia parzystego.
W: Skończony graf spójny, w którym każdy wierzchołek ma stopień parzysty, ma cykl Eulera.
T: Graf G mający drogę Eulera ma albo dwa wierzchołki stopnia nieparzystego, albo nie ma w ogóle wierzchołków stopnia nieparzystego. W: Skończony graf spójny, mający dokładnie dwa wierzchołki stopnia nieparzystego, ma drogę Eulera.
KOMBINAROTYKA PERMUTACJE: P = n! Ilość możliwych ustawień
WARIACJE BEZ POWTÓRZEŃ: V= n!/(n-k)! k-elementowe wariacje ze zbioru n-elementowego istotna kolejność
WARIACJE Z POWTÓRZENIAMI: W= n^k k-elementowe wariacje ze zbioru n-elementowego istotna kolejność
KOMBINACJE: Ck/n= (n/k) = n!/k!(n-k)! k-elementowe kombinacje ze zbioru n-elementowego nie istotna kolejność
SCHEMAT BERMULIEGO: P(k) = (n/k)·p^(k)·q^(n-k) Pewne doświadczenie wykonujesz n razy nie zależnie od siebie (p = const) i chcesz osiągnąć k razy sukces. P(k=1) + p(k=2) + p(k=...) = 1 - p(k=0) P(AÇB) = P(A) · P(B) – wtedy są niezależne
P(Bn/A) =
KOMBINAROTYKA-INFO jeśli n = k Þ permutacje, jeśli n > k Þ ?ważna kolejność Þ warjacje,
jeśli n > k Þ ?kolejność nie ważna Þ kombinacje, jeśli zaczynam y za każdym razem od początku n razy Þ sch. Bermuliego
W - zb wszystkich możliwych zdarzeń =W - ich ilość A - zb zdarzeń sprzyjających =A - ich ilość P(A) = =A/=W
LOGIKA p Ù q –koniunkcja (i) 001 p Ú q –alternatywa (lub) 0111 pÞq – implikacja (jeśli p, to q) 1101
pÛq – równoważność (Û) 1001 pÄq – ex-or (albo) 0110
RAHUNEK ZDAŃ Ø(Ø(p)) Û p – prawo podwójnego zaprzeczenia (p Ù q) Ù r Û p Ù (q Ù r) – prawo łączności koniunkcji
(p Ú q) Ú r Û p Ú (q Ú r) – prawo łączności alternatywy Ø(pÞq) Û [p Ù(Øq)] – prawo zaprzeczenia implikacji
Ø(p Ùq) Û [Øp Ú (Øq)] – p.de Morgana: zaprzeczenia koniunkcji Ø(p Ú q) Û [Øp Ù (Øq)] – p.de Morgana: zaprzeczenia alternat.
[(p Þ q) Ù (q Þ r)] Þ (p Þ r) – prawo przechodniośi implikacji
PRAWA RACHUNKU ZBIORÓW: ØA={xÎU: xÏA} wszystko za wyjątkiem A AÈB={xÎU: xÎA lubÚ xÎB} suma
AÇB={xÎU: xÎA orazÙ xÎB} część wspólna A\B={xÎU: xÎA orazÙ xÏB} tylko A bez B
AÅB=(AÈB)\(AÇB)=(A\B)È(A\B) A i B bez części wspólnej (różnica symetryczna) (AÈB )ÈC = AÈ(CÈB) - łączność sumy
AÈA=A - idempotentność sumy AÇA=A - idempotentność iloczynu Ø (ØA)=A - podwójne dopełnienie
(AÇB)ÇC=AÇ(CÇB) - łączność iloczynu AÈB=BÈA - przemienność sumy AÇB=BÇA - przemienność iloczynu
(AÈB)ÇC=(AÇC)È(BÇC) - rozdzielność il. względem sumy (AÇB)ÈC=(AÈC)Ç(BÈC) - rozdzielność iloczynu względem sumy
A£B AÌBÛA£BÙA¹B - zawieranie się zbiorów; każdy elem. z A należy do B A=B A£BÙB£A - równość zbiorów
AÈ(ØB) ¹A\B AÈÆ=A AÇÆ=Æ A \ A=Æ A \ Æ=Æ AÈW =W AÇW=A AÈA’ =W AÇA’=Æ
Ø (AÈB)= Ø(A)Ç Ø(B) - całe U bez zbiorów A i B Ø (AÈB)= Ø(A)È Ø(B) - całe U bez części wspólnych zbiorów A i B
ILOCZYN KARTEZJAŃSKI: A´B - oznacza każdy element ze zbioru A w parze z elementem ze zbioru B, np. A = { 1, 2 }; B = { 3, 4 }; A ´ B = {(1; 3), (1; 4), (2; 3), (2; 4)}
KWANTYFIKATORY RACHUNEK KWANTYFIKATORÓW $$ - zd. Prawdziwe $" - zd. Nieprawdziwe
"$ - zd. Prawdziwe "xÎZ: x + y = 3 - zd. nieprawdziwe (bo nie mamy danego y)
NEGACJA KWANTYF. Ø( $x P(x))Û"x Ø (P(x)) Ø("x P(x))Û Ø $x P(x) Ø" = $Ø Ø$ = "Ø Ø"Ø = $ Ø$Ø = "
RELACJE Dom(r) - dziedzina relacji Cod(r) - przeciw dziedzina relacji
ZWROTNA Û "xÎA: (x, x) Îr Û (idA £ r) Û "x: xPx
PRZECIWSTAWNA (ANTYZWROTNA) Û "xÎA: (x, x) Ïr Û (idA = Æ) Û "x: (Ø (xPx))
SYMETRYCZNA Û "x,yÎA: (x, y) Îr Û (y, x) Îr Û r = r-1 Û "x("y(xPyÞyPx))
ASYMETRYCZNA Û "x,yÎA: (x, y) Îr Û (y, x) Ïr Û r Ç r-1 = Æ
ANTYSYMETRYCZNA Û "x,yÎA: ((x, y) Îr Ù (y, x) Îr) Û y = x Û r Ç r-1 = Æ Û "...
webss