Matematyka Dyskretna
(Zbiory, Logika)
Edward Szczypka
szczypka@tcs.uj.edu.pl
12 pa´zdziernika 2013
Edward Szczypka
1 / 45
Matematyka Dyskretna
(Zbiory, Logika)
Edward Szczypka
szczypka@tcs.uj.edu.pl
12 pa´zdziernika 2013
Edward Szczypka
1 / 45
spis
1
2
3
4
Edward Szczypka
2 / 45
Dzisiejszy wykład
administracja,
podstawowe zasady,
sylabus,
prerekwizyty,
Zbiory, Logika, Zliczanie.
Edward Szczypka
3 / 45
Kontakt i Zasoby
instruktor
Edward Szczypka,
Uniwersytet Jagiello ´nski
Wydział Matematyki i Informatyki,
Kraków, Łojasiewicza 6, pokój 3058,
Kontakt:
szczypka@tcs.uj.edu.pl,
suszi
zasoby
biblioteka,
internet,
Edward Szczypka
4 / 45
Ocena z ´cwicze ´
n
Do uzyskania punktów
kolokwium 4 zaj ˛ecia
100 pkt
kolokwium 8 zaj ˛ecia
100 pkt
Punkty ko ´ncowe =
50% * kolokwium
50% * kolokwium
Przeliczanie na oceny
Razem Punktów
Ocena
91-100
bdb
5.0
81-90
+db
4.5
71-80
db
4.0
61-70
+dst
3.5
51-60
dst
3.0
0-50
ndst
Uwaga!
Podczas ´cwicze ´n mo˙zna zdoby´c szereg plusów, trzy plusy oznaczaj ˛
a
pół oceny w gór ˛e pod warunkiem uzyskania jakiegokolwiek zaliczenia.
Edward Szczypka
5 / 45
Co to jest matematyka dyskretna
nieci ˛
agłe, dyskretne i sko ´nczone obiekty,
niektóre działy:
algebra liniowa,
logika matematyczna
kombinatoryka,
kryptografia,
programowanie liniowe,
teoria gier,
teoria grafów,
teoria informacji,
teoria liczb,
analiza numeryczna,
Edward Szczypka
6 / 45
Co to jest matematyka dyskretna (cd)
kombinatoryka (zło˙zono´s´c obliczeniowa)
enumeratywna
zliczanie obiektów,
szacowanie czasu działania procedur,
egzystencjalna
badanie istnienia i nieistnienia obiektów,
wnioskowanie o zatrzymaniu procedury,
konstruktywna
metody konstrukcji obiektów,
projektowanie algorytmów,
Edward Szczypka
7 / 45
Zbiór
pierwotne poj ˛ecie,
kolekcja niepowtarzaj ˛
acych si ˛e obiektów,
do zbioru nale˙z ˛
a elementy tego zbioru,
piszemy x ∈ X je´sli x jest elementem zbioru X ,
piszemy x /
∈ X je´sli x nie jest elementem zbioru X .
Zbiór opisywany jedynie przez rodzaj posiadanych obiektów.
Zbiory s ˛
a równe wtedy i tylko wtedy gdy maj ˛
a dokładnie takie
same elementy.
zbiory opisywane poprzez:
wymienienie wszystkich elementów {0, 1, 2, 3, 4, 5}
poprzez okre´slenie własno´sci, któr ˛
a spełniaj ˛
a te elementy, np.
nieujemne liczby całkowite nie wi ˛eksze ni˙z 5.
Edward Szczypka
9 / 45
Definicja (cd)
opis zbioru cz ˛esto skrótowy poprzez wykorzystanie wielokropka,
np {1, 3, 5, 7, 13, . . . , 17},
niebezpiecze ´nstwo pomyłek
A = {1, 3, 5, . . .} - czy podany zbiór opisuje liczby nieparzyste czy
liczby pierwsze?
B = {x : x /
∈ X } - sprzeczno´s´c je´sli zapytamy czy B ∈ B?
jakikolwiek element x nale˙zy lub nie nale˙zy do zbioru, element nie
mo˙ze nale˙ze´c tylko cz ˛e´sciowo.
uniwersum X wszystkie mo˙zliwe, wszystkie rozwa˙zane elementy,
zbiór pusty ∅, mo˙zna zdefiniowa´c jako {x : x 6= x },
Uwaga
Zbiór ∅ i zbiór {∅} to dwa ró˙zne zbiory, drugi zawiera zbiór pusty!
Podobnie ró˙znica mi ˛edzy kontem z zerowym stanem i brakiem konta.
Edward Szczypka
10 / 45
Działania na zbiorach
Zbiór A zawiera si ˛e w B lub A jest podzbiorem B, ozn.
A ⊆ B
,
je´sli ka˙zdy element nale˙z ˛
acy do A nale˙zy równocze´snie do B,
przykład {1, 2, 3} ⊆ {1, 2, 3, 4, 5},
Ró˙znica zbioru A i B, ozn.
A\B
to zbiór, który zawiera wszystkie elementy z A, które nie
wyst ˛epuj ˛
a w B,
przykład {1, 2, 3, 4, 5}\{2, 4, 6} = {1, 3, 5},
Suma zbiorów A i B ozn.
A ∪ B
to zbiór który zawiera wszystkie elementy ze zbioru A i B,
przykład {1, 2, 3, 4, 5} ∪ {2, 4, 6} = {1, 2, 3, 4, 5, 6},
Iloczyn zbiorów A i B ozn.
A ∩ B
to zbiór elementów wyst ˛epuj ˛
acych równocze´snie w zbiorze A i B„
przykład {1, 2, 3, 4, 5} ∩ {2, 4, 6} = {2, 4}
Edward Szczypka
11 / 45
Działania (cd)
Dopełnieniem zbioru A, ozn.
A
0
nazywamy zbiór wszystkich
elementów z uniwersum, które nie nale˙z ˛
a do zbioru A
mo˙zna to zapisa´c jako
A
0
= {
x ∈ X : x /
∈ A}
,
Ró˙znic ˛
a symetryczn ˛
a zbioru A i B, ozn.
A ÷ B
,
nazywamy zbiór elementów, które nale˙z do A i nie nale˙z ˛
a do B lub
nale˙z ˛
a do B i nie nale˙z ˛
a do A. czyli
A ÷ B = (A\B) ∪ (B\A)
.
Zbiory takie, ˙ze A ÷ B = ∅, równowa˙znie A ∩ B = ∅ nazywamy
rozł ˛
acznymi.
Edward Szczypka
12 / 45
Własno ´sci działa ´
n
Przykład
A ∪ A = A ∩ A = A ∪ ∅ = A,
A ∪ B = B ∪ A,
A ∪ (B ∪ C) = (A ∪ B) ∪ C = A ∪ B ∪ C,
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) = A ∩ B ∩ C,
A\(B ∪ C) = (A\B) ∩ (A\C),
A\(A\B) = A ∩ B,
(
A ∪ B)\(A ∩ B) = (A\B) ∪ (B\A)
Edward Szczypka
13 / 45
Własno ´sci działa ´
n (cd)
A ∩ A
0
= ∅
,
A ∪ A
0
=
X ,
∅
0
=
X ,
(
A
0
)
0
=
A,
A ÷ B = B ÷ A,
A ÷ (B ÷ C) = (A ÷ B) ÷ C,
Edward Szczypka
14 / 45
Wa˙zne zbiory
∅ - zbiór pusty,
N - zbiór liczb naturalnych (wraz z zerem),
Z - zbiór liczb całkowitych,
Q - zbiór liczb wymiernych,
R - zbiór liczb rzeczywistych
Inkluzja zbiorów
Dla tych zbiorów zachodzi N ( Z ( Q ( R.
Edward Szczypka
15 / 45
Moc
Ilo´s´c elementów w zbiorze A oznaczamy przez
kAk
i nazywamy moc ˛
a
zbioru A.
Natomiast wszystkie mo˙zliwe podzbiory zbioru A przez
P(A)
lub
2
A
co
definiujemy jako
2
A
= {
X : X ⊆ A}
,
je´sli A ⊆ B to wtedy kAk ¬ kBk oraz k2
A
k ¬ k2
B
k.
kA ∩ Bk ¬ min{kAk, kB}},
k∅k = 0,
k{∅}k = 1.
2
{a,b}
= {∅, {
a}, {b}, {a, b}}
Przykład:
Jaki jest rozmiar zbioru 2
A
, gdy A ma zero elementów?
Edward Szczypka
16 / 45
Moc (cd)
je´sli A jest rozł ˛
aczne z B to moc zbioru kA ∪ Bk wynosi kAk + kBk
dla wi ˛ekszej ilo´sci zbiorów A
1
,
A
2
, . . . ,
A
n
je´sli s ˛
a one parami
rozł ˛
aczne tzn. A
i
∩ A
j
= ∅
dla dowolnych ró˙znych i i j. to wtedy
kA
1
∪ A
2
∪ . . . ∪ A
n
k = kA
1
k + kA
2
k + . . . + kA
n
k
w ogólnym przypadku dla dowolnych A i B mamy wzór
kA ∪ Bk = kAk + kBk − kA ∩ Bk
prosz ˛e spróbowa´c wyprowadzi´c wzór na moc sumy zbiorów
A
1
,
A
2
, . . . ,
A
n
.
Sito
Sposób zliczania wymieniony w dwóch ostatnich punktach nosi nazw ˛e
sita.
Edward Szczypka
17 / 45
Moc (cd)
Teraz zastanówmy si ˛e nad moc ˛
a ró˙znicy dwóch zbiorów A i B
zbiór A mo˙zna przedstawi´c jako sum ˛e dwóch zbiorów (A ∩ B) i
(
A\B)
powy˙zsze zbiory s ˛
a rozł ˛
aczne (A ∩ B) ∩ (A\B) = ∅
korzystaj ˛
ac z poprzedniego slajdu kA\Bk = kAk − kA ∩ B|
Edward Szczypka
18 / 45
spis
1
2
3
Podstawy
Tautologie
Zbiory a logika
Bramki Logiczne
Posta´c Normalna
4
Edward Szczypka
19 / 45
Podstawowe spójniki logiczne
negacja
nie
NOT
¬
koniunkcja
i
AND
∧
alternatywa
lub
OR
∨
implikacja
je´sli . . . to . . .
IF . . . THEN . . .
→
równowa˙zno´s´c
wtedy i tylko wtedy
IF AND ONLY IF
↔
Powy˙zsze spójniki s ˛
a spójnikami
ekstensjonalnymi
ich prawdziwo´s´c
zale˙zy jedynie od prawdziwo´sci zda ´n składowych.
Edward Szczypka
20 / 45
Podstawowe spójniki logiczne (cd)
J ˛ezyk naturalny posiada jeszcze spójniki
intensjonalne
, gdzie
prawdziwo´s´c zdania zale˙zy równie˙z od innych czynników, np:
jest mo˙zliwe, ˙ze . . . ,
jestem przekonany, ˙ze . . . .
Uwaga
Na wykładzie b ˛edziemy zajmowa´c si ˛e jedynie spójnikami
ekstensjonalnymi.
Edward Szczypka
21 / 45
Zdanie logiczne
Wyra˙zenie:
które ma ´sci´sle okre´slon ˛
a warto´s´c
prawd ˛e albo fałsz,
warto´s´c
prawdy albo fałszu zale˙zy jedynie od prawdziwo´sci zda ´n
prostych
Przykłady:
Teraz pada deszcz. - jest zdaniem logicznym, mo˙zna mu
przypisa´c warto´s´c prawdy lub fałszu.
By´c mo˙ze jutro b ˛edzie pada´c. - nie jest zdaniem logicznym.
Edward Szczypka
22 / 45
Warto ´sciowanie
1 w tabelce interpretujemy jako prawd ˛e,
0 jako fałsz.
negacja
p
¬p
0
1
1
0
Edward Szczypka
23 / 45
koniunkcja
p
q
p ∧ q
0
0
0
0
1
0
1
0
0
1
1
1
implikacja
p
q
p → q
0
0
1
0
1
1
1
0
0
1
1
1
alternatywa
p
q
p ∨ q
0
0
0
0
1
1
1
0
1
1
1
1
równowa ˙zno´s´c
p
q
p ↔ q
0
0
1
0
1
0
1
0
0
1
1
1
Edward Szczypka
24 / 45
Tautologie
Tautologia to
zdanie zawsze prawdziwe bez wzgl ˛edu na kombinacje warto´sci
logicznych zda ´n składowych,
prawo rachunku zda ´n
Wyra˙zenie (p → q) ↔ (¬p ∨ q) jest
tautologi ˛
a
.
p
q
p → q
¬p ¬p ∨ q (p → q) ↔ (¬p ∨ q)
0
0
1
1
1
1
0
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
1
1
Edward Szczypka
25 / 45
Kilka praw
(
p ∨ q) ↔ (q ∨ p)
przemienno´s´c alternatywy,
(
p ∧ q) ↔ (q ∧ p)
przemienno´s´c koniunkcji,
((
p ∨ q) ∨ r ) ↔ (q ∨ (p ∨ r ))
ł ˛
aczno´s´c alternatywy,
((
p ∧ q) ∧ r ) ↔ (q ∧ (p ∧ r ))
ł ˛
aczno´s´c koniunkcji,
p ∨ ¬p
prawo wył ˛
aczonego ´srodka,
¬(¬p) ↔ p
prawo wył ˛
aczonego ´srodka,
(
q ∨ (p ∧ r )) ↔ (q ∨ p) ∧ (q ∨ r ))
rozdzielno´s´c koniunkcji
wzgl ˛edem alternatywy,
(
q ∧ (p ∨ r )) ↔ (q ∧ p) ∨ (q ∧ r ))
rozdzielno´s´c alternatywy
wzgl ˛edem koniunkcji,
Edward Szczypka
26 / 45
Kilka praw (cd)
¬(p ∨ q) ↔ (¬q ∧ ¬p)
prawa de Morgana,
¬(p ∧ q) ↔ (¬q ∨ ¬p)
(¬
p → p) → p
prawo sprowadzania
do absurdu,
¬(p → q) ↔ (p ∧ ¬q)
prawo przeczenia implikacji,
(
p → q) ↔ (¬p ∨ q)
prawo kontrapozycji
((
p → q) ∧ (q → r )) ↔ (p → r )
prawo sylogizmu
Edward Szczypka
27 / 45
Zbiory a własno ´sci
ka˙zdy zbiór wyznacza własno´s´c
X - zbiór,
x ∈ X - własno´s´c,
ka˙zda własno´s´c wyznacza zbiór
α(
x ) - własno´s´c,
{x : α(x)} -zbiór
Zwi ˛
azek rachunku zda ´n i rachunku zbiorów
Taki zwi ˛
azek pozwala sprawdzi´c prawa rachunku zbiorów poprzez
najpierw "przetłumaczenie" równo´sci zbiorów na wyra˙zenie
rachunku zda ´n
sprawdzenie czy otrzymane wyra˙zenie jest tautologi ˛
a
Edward Szczypka
28 / 45
Przykłady
A\(A\B) = A ∩ B, mo˙zna przetłumaczy´c na
(
x ∈ A ∧ ¬(x ∈ A ∧ ¬x ∈ B)) ↔ (x ∈ A ∧ x ∈ B)
lub po prostu (p ∧ ¬(p ∧ ¬q)) ↔ (p ∧ q)
okazuje si ˛e, ˙ze jest to tautologia czyli mamy równo´s´c tych zbiorów,
Sprawd´z czy je´sli A ⊆ B ∪ C, B ⊆ A ∪ C i C ⊆ A ∪ B to wtedy
zbiory A, B i C s ˛
a równe.
Po przetłumaczeniu dostajemy
[(
p → (q ∨ r )) ∧ (q → (p ∨ r )) ∧ (r → (p ∨ q))] → [(p ↔ q) ∧ (p ↔
r ) ∧ (q ↔ r )]
okazuje si ˛e, ˙ze to nie jest tautologia, np dla p = q = 1, r = 0
mamy fałsz. Daje to mo˙zliwo´s´c na prost ˛
a konstrukcje
kontrprzykładu np. A = B = {x }, C = ∅.
Edward Szczypka
29 / 45
Binarne spójniki logiczne
Pytanie ile jest binarnych spójników logicznych?
p
q
s
1
s
2
s
3
s
4
s
5
s
6
s
7
s
8
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
p
q
s
9
s
10
s
11
s
12
s
13
s
14
s
15
s
16
0
0
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
Edward Szczypka
30 / 45
Binarne spójniki logiczne (cd)
Dlaczego wybrano tylko ¬, ∨, ∧, →, ↔?
bo to wystarcza,
bo s ˛
a to w sumie najwa˙zniejsze z punktu widzenia logiki.
Przykłady:
s
7
zwany równie˙z jako XOR mo˙zna zdefiniowa´c jako
pXORq ↔ (p ∨ q) ∧ ¬(p ∧ q)
s
9
zwany jako NOR mo˙zna zdefiniowa´c jako
pNORq ↔ ¬(p ∨ q)
s
15
zwany jako NAND mo˙zna zdefiniowa´c jako
pNANDq ↔ ¬(p ∧ q)
Edward Szczypka
31 / 45
Binarne spójniki logiczne (cd)
Definiowalno´s´c za pomoc ˛
a NAND i NOR
Bramki NOR i NAND s ˛
a o tyle ciekawe, ˙ze za pomoc ˛
a ka˙zdej z nich z
osobna mo˙zna zdefiniowa´c ka˙zd ˛
a inn ˛
a bramk˛e.
Przykład:
¬p = (pNORp),
p ∨ q = (pNORq)NOR(pNORq),
p ∧ q = ¬(¬p ∨ ¬q).
Prosz ˛e spróbowa´c pokaza´c, ˙ze NAND równie˙z definiuje wszystkie
mo˙zliwe spójniki binarne.
Edward Szczypka
32 / 45
Koniunkcyjna posta ´c normalna
Dzi ˛eki wykorzystaniu
prawa de Morgana
rozdzielno´sci alternatywy wzgl ˛edem koniunkcji,
praw ł ˛
aczno´s´ci,
ka˙zdy spójnik logiczny mo˙zna sprowadzi´c do formy w której mamy
tylko koniunkcj ˛e wyra˙ze ´n zawieraj ˛
acych jedynie alternatyw ˛e
zmiennych lub ich przecze ´n. Taka forma spójnika logicznego nosi
nazw ˛e postaci
koniunkcyjno normalnej
.
Przykład:
(
p ↔ q) ∧ r
=
(
p ∧ q) ∨ (¬p ∧ ¬q) ∨ r
=
((
p ∨ (¬p ∧ ¬q)) ∧ (q ∨ (¬p ∧ ¬q))) ∨ r
. . . . . .
=
(¬
p ∨ q ∨ r ) ∧ (p ∨ ¬q ∨ r )
Edward Szczypka
33 / 45
Koniunkcyjna posta ´c normalna (cd)
Jak wida´c ka˙zd ˛
a bramk˛e logiczna mo˙zna sprowadzi´c do postaci
koniunkcyjno normalnej
co mo˙zna zapisa´c jako:
W
n
i=1
l
i
j
1
∧ l
i
j
2
∧ . . . ∧ l
i
j
i
gdzie;
l
i
j
- s ˛
a zdaniami prostymi, tzn zmienne albo negacje, zwane
literałami
,
alternatywy literałów, czyli zdania l
i
j
1
∧ l
i
j
2
∧ . . . ∧ l
i
j
i
, zwanej
klauzul ˛
a
,
całe wyra˙zenie jest ju˙z koniunkcj ˛
a takich
klauzul
,
1 mln $ nagrody
Za znalezienie szybkiego algorytmu sprawdzaj ˛
acego spełnialno´s´c
takich formuł.
Edward Szczypka
34 / 45
Wieloargumentowe spójniki logiczne
W j ˛ezyku potocznym brak jest niewiele wieloargumentowych spójników
logicznych, jednak w ró˙znego rodzaju zastosowaniach, np. przy
budowie arytmometru takie spójnik cz ˛esto mo˙zna spotka´c.
Przykładowo w praktyce programista cz ˛esto spotyka si ˛e z konstrukcj ˛
a
IF p THEN q ELSE r ,
co mo˙zna przetłumaczy´c na
(
p → q) ∧ (¬p → r )
Pytanie:
Ile jest ró˙znych spójników logicznych dla k zmiennych?
Edward Szczypka
35 / 45
Pary uporz ˛
adkowane
W zbiorze kolejno´s´c elementów nie ma znaczenia, np. zapis {a, b}
oznacza to samo co zapis {b, a}. Jednak cz ˛esto taka kolejno´s´c
odgrywa znaczenie, np. w przypadku gdy rozpatrujemy współrz ˛edne
jakiego´s punktu istotnym jest co ma by´c na pierwszym a co na drugim
miejscu, itd. Par ˛e uporz ˛
adkowan ˛
a oznaczamy przez
ha, bi
,
Własno´sci
ha, bi 6= hb, ai,
ha, bi = hc, d i wtedy i tylko wtedy gdy a = b i b = c,
{a, b} = {b, a},
ha, bi 6= {a, b},
ha, ai 6= hai, natomiast {a, a} = {a},
Edward Szczypka
37 / 45
Para uporz ˛
adkowana (cd)
Par ˛e uporz ˛
adkowan ˛
a mo˙zna zdefiniowa´c za pomoc ˛
a zbiorów
ha, bi := {a, {a, b}}.
Dzi ˛eki tak postawionej definicji mo˙zna udowodni´c własno´sci ha, bi z
poprzedniego slajdu.
Edward Szczypka
38 / 45
Ci ˛
agi uporz ˛
adkowane, słowa (cd)
Wykorzystuj ˛
ac powy˙zsz ˛
a definicj ˛e mo˙zna zdefiniowa´c uporz ˛
adkowan ˛
a
trójk˛e, czwórk˛e itd.
ha, b, ci := ha, hb, cii
ha, b, c, d i := ha, hc, b, d ii
Własno´sci
Podobne własno´sci jak dla pary uporz ˛
adkowanej zachodz ˛
a oczywi´scie
dla ci ˛
agów o dowolnej długo´sci.
Edward Szczypka
39 / 45
Iloczyn kartezja ´
nski
Jak widzieli´smy poprzednio w parze uporz ˛
adkowanej czy w ci ˛
agu
istotna jest kolejno´s´c elementów, mi ˛edzy innymi z tego powodu, ˙ze
ka˙zdy z elementów w takiej parze mo˙ze nale˙ze´c do innego zbioru.
Przykład:
ha, bi ∈ A × B - para uporz ˛
adkowana w której a ∈ A i b ∈ B,
A × B = {ha, bi : a ∈ A, b ∈ B},
{a, b} × {1, 2} = {ha, 1i, ha, 2i, hb, 1i, hb, 2i},
Edward Szczypka
40 / 45
Iloczyn kartezja ´
nski (cd)
Które z podanych równo´sci jest prawdziwa?
(
A ∪ B) × C = (A × C) ∪ (B × C), Prawda
(
A ∩ B) × C = (A × C) ∩ (B × C), Prawda
A\(B × C) = (A\B) × (A\C),
Fałsz
(
A ∪ B) × (C ∪ D) = (A × C) ∪ (B × D),
Fałsz
(
A ∪ B) × (C ∪ D) = (A × C) ∪ (A × D) ∪ (B × C) ∪ (B × D)), Prawda
Edward Szczypka
41 / 45
Iloczyn kartezja ´
nski (cd)
Cz ˛esto gdy rozwa˙zamy iloczyn kartezja ´nski tego samego zbioru to
piszemy A
n
, tzn.
A
n
:=
A × A × . . . × A
|
{z
}
n
i nazywamy n-t ˛
a pot ˛eg ˛
a zbioru A.
Przykład
R
2
- oznacza płaszczyzn ˛e,
R
3
- oznacza przestrze ´n trójwymiarow ˛
a,
R
n
- oznacza przestrze ´n n wymiarow ˛
a,
R
0
- oznacza przestrze ´n 0-wymiarow ˛
a, czyli jeden punkt
Edward Szczypka
42 / 45
(Bardziej) rzeczywisty obiekt
opisywany jako lista atrybutów
Piotrek: 21 lat, 178 cm, zarobki 100 tys rocznie
cz ˛esto atrybuty s ˛
a tego samego rodzaju, np słowa składaj ˛
a si ˛e z
ci ˛
agu liter np. abrakadabra.
cz ˛esto nie znamy długo´sci takiego opisu danego obiektu.
stosujemy wtedy notacj ˛e:
A
∗
=
A
0
∪ A
1
∪ A
2
∪ A
3
∪ . . .
Elementy A
∗
nazywamy
słowami
nad alfabetem A.
Edward Szczypka
43 / 45
Zliczanie ci ˛
agów, słów
Pytanie: Ile elementów mamy w zbiorze A × B?
Je´sli wybierzemy element a ∈ A to dokładnie kBk par ze zbioru B,
b ˛edzie miało pierwsz ˛
a współrz ˛edn ˛
a równ ˛
a x . Podobnie dla
nast ˛epnego elementu z A i nast ˛epnego i nast ˛epnego. Wszystkich
elementów zatem jest kAk ∗ kBk.
kA × Bk = kAk ∗ kBk
W bardzo prosty sposób mo˙zna powy˙zszy wzór rozszerzy´c na
dowolna ilo´s´c elementów
kA
1
× . . . A
n
k = kA
1
k ∗ . . . ∗ kA
n
k.
W szczególno´sci
kA
n
k = kAk
n
.
Edward Szczypka
44 / 45
Zliczanie ci ˛
agów, słów (cd)
Oczywi´scie je´sli zadamy takie samo pytanie co do ilo´sci słów, to słów
jest niesko ´nczenie wiele. Ograniczmy si ˛e tylko do słów o długo´sci
nieprzekraczaj ˛
acej n,wtedy:
kA
0
∪ A
1
∪ . . . ∪ A
n
k = 1 + kAk + kAk
2
+ . . . + k
Ak
n
.
Oznaczaj ˛
ac powy˙zsz ˛
a sum ˛e przez s, a rozmiar A przez q dostaniemy:
s
=
1 + q + q
2
+ . . . +
q
n
=
1 + q ∗ (1 + q + . . . + q
n
) −
q
n+1
=
1 + q ∗ s − q
n+1
.
Z tej równo´sci łatwo dostaniemy znany wzór na s
s =
q
n+1
− 1
q − 1
.
Edward Szczypka
45 / 45
