Document Outline

3 / 45

Informacje

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

Informacje

Ocena z ´cwicze ´

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

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 ˛

pół oceny w gór ˛e pod warunkiem uzyskania jakiegokolwiek zaliczenia.

Edward Szczypka

5 / 45

Matematyka dyskretna

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

Definicja
Działania
Własno´sci działa ´n
Moc

6 / 45

Matematyka dyskretna

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

spis

Edward Szczypka

8 / 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.

nazywamy zbiór wszystkich

elementów z uniwersum, które nie nale˙z ˛

a do zbioru A

mo˙zna to zapisa´c jako

= {

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 ´

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

= ∅

A ∪ A

X ,

∅

X ,

(

)

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 ˛

zbioru A.

Natomiast wszystkie mo˙zliwe podzbiory zbioru A przez

P(A)

lub

definiujemy jako

= {

X : X ⊆ A}

je´sli A ⊆ B to wtedy kAk ¬ kBk oraz k2

k ¬ k2

kA ∩ Bk ¬ min{kAk, kB}},

k∅k = 0,

k{∅}k = 1.

{a,b}

= {∅, {

a}, {b}, {a, b}}

Przykład:
Jaki jest rozmiar zbioru 2

, 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

, . . . ,

je´sli s ˛

a one parami

rozł ˛

aczne tzn. A

∩ A

= ∅

dla dowolnych ró˙znych i i j. to wtedy

∪ A

∪ . . . ∪ A

k = kA

k + kA

k + . . . + kA

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

, . . . ,

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

Podstawy
Tautologie
Zbiory a logika
Bramki Logiczne
Posta´c Normalna

Edward Szczypka

19 / 45

Podstawowe spójniki logiczne

negacja

nie

NOT

koniunkcja

AND

∧

alternatywa

lub

∨

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

Edward Szczypka

23 / 45

koniunkcja

p ∧ q

implikacja

p → q

alternatywa

p ∨ q

równowa ˙zno´s´c
p

p ↔ q

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 ˛

p → q

¬p ¬p ∨ q (p → q) ↔ (¬p ∨ q)

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 ˛

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?

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:

zwany równie˙z jako XOR mo˙zna zdefiniowa´c jako

pXORq ↔ (p ∨ q) ∧ ¬(p ∧ q)

zwany jako NOR mo˙zna zdefiniowa´c jako

pNORq ↔ ¬(p ∨ q)

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:

i=1

∧ l

∧ . . . ∧ l

gdzie;

- s ˛

a zdaniami prostymi, tzn zmienne albo negacje, zwane

literałami

alternatywy literałów, czyli zdania l

∧ l

∧ . . . ∧ l

, zwanej

klauzul ˛

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 ˛

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

Iloczyn Kartezja ´nski
słowa
Zliczanie

spis

Edward Szczypka

36 / 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 ˛

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

, tzn.

A × A × . . . × A

}

i nazywamy n-t ˛

a pot ˛eg ˛

a zbioru A.

Przykład

- oznacza płaszczyzn ˛e,

- oznacza przestrze ´n trójwymiarow ˛

- oznacza przestrze ´n n wymiarow ˛

- 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

∪ . . .

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

× . . . A

k = kA

k ∗ . . . ∗ kA

W szczególno´sci

k = kAk

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:

∪ A

∪ . . . ∪ A

k = 1 + kAk + kAk

+ . . . + k

Oznaczaj ˛

ac powy˙zsz ˛

a sum ˛e przez s, a rozmiar A przez q dostaniemy:

1 + q + q

+ . . . +

1 + q ∗ (1 + q + . . . + q

) −

n+1

1 + q ∗ s − q

n+1

Z tej równo´sci łatwo dostaniemy znany wzór na s

s =

n+1

− 1

q − 1

Edward Szczypka