MATEMATYKA DYSKRETNA

2013/2014

 

Zakres:

1. Rachunek zdań ; Rachunek zbiorów
 
2. Rachunek predykatów ; Schematy wnioskowania
 
3. Funkcje całkowitoliczbowe ; Kombinatoryka
 
4. Rekurencje ; Postać zwarta schematu rekurencyjnego
 
5. Schemat Hornera ; Kongruencje
 
6. Grafy – definicje, klasyfikacje, reprezentacje, właściwości
 
7. Grafy – algorytmy na grafach

 

Literatura:

http://wazniak.mimuw.edu.pl/index.php?title=Strona_g%C5%82%C3%B3wna

Sysło M.M.: Algorytmy, WSiP, Warszawa 1997.
Ross K.A., Wright C.R.B.: Matematyka dyskretna, PWN, Warszawa 1996.
Ziembiński Z., Logika praktyczna, PWN, Warszawa 2000.
Lipski W.: Kombinatoryka dla programistów, WNT, Warszawa 1982.
Wilson R.J.: Wprowadzenie do teorii grafów, Warszawa 1998.
Bryant V.: Aspekty kombinatoryki, WNT, Warszawa 1997.

 

MATEMATYKA DYSKRETNA

Wymiar: 2 2 0 0 0

Wymagania: matematyka na poziomie szkoły średniej

Zaliczenie przedmiotu: MAX{Pozytywna cena z ćwiczeń audytoryjnych wystawiona na
podstawie trzech testów i aktywności ,Pozytywna ocena z egzaminu „zerowego”}

Założenia programowe: Zapoznanie z podstawowymi obiektami i strukturami matematyki
dyskretnej, przydatnymi do treści pozostałych przedmiotów poświęconych m.in. projektowaniu i
analizie algorytmów wspomagania decyzji, a także systemom komputerowo zintegrowanego
zarządzania.

Wykład:

1. Podstawy logiki i teorii mnogości. – Elementy teorii zbiorów – zbiory, alfabety, rachunek
zbiorów, funkcje. Zastosowania – maszyna Turinga. Funkcje całkowitoliczbowe: powała i podłoga.
Zastosowanie – szacowanie długości słowa maszynowego.

2. Podstawy logiki i teorii mnogości. – Logika pierwszego rzędu. Rachunek zdań. Reguły
wnioskowania (modus ponens, zasada rezolucji). Zastosowania w strukturach systemów
ekspertowych.

3. Podstawy logiki i teorii mnogości. – Dowody formalne, pojęcia poprawności i pełności
systemu logicznego. Teorie formalne.

4. Asymptotyka funkcji liczbowych. – Zastosowania – szacowanie złożoności obliczeniowej.
Problemy decyzyjne i optymalizacyjne. Problemy łatwe i trudne. Zastosowania - zasada dziel i
zwyciężaj.

2

5. Elementy teorii liczb – Podzielność liczb naturalnych – algorytm Euklidesa.
NWD, NWW. Operator modulo. Liczby pierwsze i rozkład liczb na czynniki pierwsze.
Zastosowania – kryptografia. Liczby doskonałe. Równanie diofantyczne.

6. Elementy kombinatoryki – Zasada gołębnika. Zasada włączania i wyłączania.
Generowanie obiektów kombinatorycznych. Permutacje, kombinacje, wariacje.
Zastosowania – szacowanie złożoność obliczeniowej.

7. Elementy kombinatoryki – Definicje, algorytmy i zależności rekurencyjne.
Rozwiązywanie zależności rekurencyjnych – przez podstawianie i za pomocą
równania charakterystycznego. Zastosowania - symbol Newtona, trójkąt Newtona.

8. Elementy kombinatoryki – Kongruencje. Zastosowania – na jaka cyfrę kończy
się liczba 5

100

? Systemy liczbowe. Schemat Hornera. Zastosowania – szybkie

potęgowanie.

9. Elementy teorii grafów – Relacje i ich reprezentacje. Grafy symetryczne i
skierowane. Charakterystyki - drogi, cykle, pętle, itd. Właściwości i klasyfikacje
grafów: drzewa, grafy dwudzielne, grafy pełne, grafy planarne, itp.

10. Elementy teorii grafów – Badanie właściwości grafów. Grafy Eulera i
Hamiltona. Izomorfizm grafów. Zastosowania – wybrane ilustracje problemów
łatwych i trudnych. Strategie zachłanne.

11 Elementy teorii grafów. Macierzowe reprezentacje grafów – macierz
incydencji, macierz stowarzyszona. Zastosowania – badanie właściwości grafów.

3

12 Elementy teorii grafów. Algorytmy na grafach – drzewa rozpinające. Przykłady zastosowań –
wyznaczanie
sieci instalacji elektrycznej.

13 Elementy teorii grafów. Algorytmy na grafach – zadania najkrótszych dróg. Przykłady
zastosowań –
wyznaczanie najkrótszej drogi (metoda podziałów i ograniczeń).

14. Elementy teorii grafów –Grafy AND/OR. Przykłady zastosowań – planowanie działań (np.
montażu).

Ćwiczenia
Ćwiczenia polegają na rozwiązywaniu zadań opracowanych do poszczególnych partii materiału z
wykładu.
Są to głównie ćwiczenia rachunkowe, ale w wielu przypadkach sprowadzają się do „giełdy” pomysłów
nowych (niestandardowych) rozwiązań oraz skojarzeń i pomysłów związanych z praktycznym
wykorzystaniem
zdobytych umiejętności.

Literatura:

Ross K.A., Wright C.R.B., Matematyka dyskretna, PWN, Warszawa 1996.

Sysło M.M., Algorytmy, WSziP, Warszawa, 1997

Lipski W., Kombinatoryka dla programistów, WNT, Warszawa, 1982

Wilson R.J., Wprowadzenie do teorii grafów, PWN, Warszawa, 1998.

Ziembiński Z., Logika praktyczna, PWN, Warszawa 2000.

4

Zaliczenie:

•MAX{„Z”, ”0”} , gdzie:

Ind.Akt.Studenta

• IF((#1 + #2 + #3)/3  3) THEN („Z” = 3 + Bonus); Bonus = * 0.5
(MAX Akt. Grupy)/4

Test (przykład)

1. Uprość wyrażenie: (p  p)  (p  p)  ?

2. Oblicz wartość formuły: (q  p)  ? , dla q = p = 1

3. Wyznacz

pierwszych

pięć

elementów

zbioru:

{5/n

|

nN}

=

{ , , , , }

4. Czy prawdą jest, że: (A \ B) \ C = A \ (B \ C)

5. Czy prawdą jest, że z faktów a i b wynika fakt g?

R1: IF b THEN h
R2: IF b i h THEN f
R3: IF a i b THEN c
R4: IF c i h THEN g

Zakład Informatyki Gospodarczej

https://sites.google.com/a/apps.wz.pw.edu.pl/zig-wz-pw

profesor Zbigniew Banaszak

[e-mail]

5

Wykład 1

1.Elementy teorii zbiorów

•rachunek zdań,

•sprzeczności i tautologie, reguły wnioskowania (reguła modus ponens),

•zastosowania w strukturach systemów ekspertowych,

•zbiory i działania na zbiorach,

•rachunek predykatów, zasada rezolucji,

Rachunek zdań

ZDANIA, SPÓJNIKI, FORMUŁY

Poniższe napisy nie są formułami

p   q


Ten napis na pewno nie jest formułą,

(p  q))

Poniższe napisy są formułami

p  (r  q)
q
p  q

p  p  p
(p  p)  p  p  (p  p)

6

Oznaczenia

N – zbiór liczb naturalnych (bez zera)

N

0

– zbiór liczb naturalnych z zerem

Z – zbiór liczb całkowitych

Z

+

– zbiór liczb całkowitych dodatnich

Q – zbiór liczb wymiernych

R – zbiór liczb rzeczywistych

x  A – x należy do zbioru A (x jest elementem zbioru A)

x  A – x nie należy do zbioru A

A  B – zbiór A jest podzbiorem zbioru B (zbiór A zawiera się w zbiorze B)

A  B - zbiór A nie jest podzbiorem zbioru B

A  B – iloczyn mnogościowy zbiorów

A  B – suma mnogościowa zbiorów

A \ B – różnica mnogościowa zbiorów

7

A  B – różnica symetryczna zbiorów

Ø = { } – zbiór pusty

|A| – moc zbioru A (liczba elementów zbioru A)

 - znak sumy

 – znak iloczynu

x – dla każdego x

x – istnieje x

! x – istnieje jedno x

 – ...nieprawda, że... (negacja)

 – ...lub... (alternatywa)

 – ...i... (koniunkcja)

 – ...jeżeli, to... (implikacja)

 – ...wtedy i tylko wtedy... (równoważność)

A  – A jest zdefiniowane jako...

 x  – największa liczba całkowita niewiększa niż x

 x  – najmniejsza liczba całkowita niemniejsza niż x

8

The symbol n!, called factorial n, was introduced in

1808 by Christian Kramp of Strassbourg, who chose

it so as to circumvent printing difficulties incurred by

the previously used symbol thus illustrated on the

right.

9

In its primitive form the per cent sign is found in the 15th century

manuscripts on commercial arithmetic, where it appears as this

symbol after the word "per" or after the letter "p" as a contraction for

"per cento." The use of the per cent symbol can be seen in this

extract from an anonymous Italian manuscript of 1684
The percent sign, %, has probably evolved from a symbol introduced

in an anonymous Italian manuscript of 1425. Instead of "per 100," "P

cento," which were common at that time, this author used the symbol

shown.

10

The earliest Hindu symbol for zero was the heavy dot that appears in
the Bakhshali manuscript, whose contents may date back to the third
or fourth century A.D. The zero appeared in India as early as the 9th
century, and probably some time before that, and was very likely a
Hindu invention.

Since the earliest form of the Hindu symbol was commonly used in
inscriptions and manuscripts in order to mark a blank, it was called
sunya, meaning “void” or “empty.”
This word passed over into the Arabic as sifr, meaning “vacant.”
This was transliterated in about 1200 into Latin with the sound but
not the sense being kept, resulting in zephirum or zephyrum.
Various progressive changes of these forms, including zeuero,
zepiro, zero, cifra, and cifre, led to the development of our words
“zero” and “cipher.”

11

The symbols of elementary
arithmetic are almost wholly
algebraic, most of them being
transferred to the numerical field
only in the 19th century, partly to aid
the printer in setting up a page and
partly because of the educational
fashion then dominant of demanding
a written analysis for every problem.

There is some symbolism in Egyptian
algebra. In the Rhind papyrus we find
symbols for plus and minus.
The first of these symbols represents a pair
of legs walking from right to left, the normal
direction for Egyptian writing, and the other
a pair of legs walking from left to right,
opposite to the direction for Egyptian
writing.

12

SPÓJNIKI ZDANIOWE

Zapis

Nazwa

Symbol

..nieprawda, że..

negacja



...lub...

alternatywa



...i...

koniunkcja



...jeżeli...to...

implikacja



...wtedy i tylko wtedy gdy… równoważność



HIERARCHIA
SPÓJNIKÓW

 ;  ;  ;  ; 

13

p



p

0

1

1

0



0

1

0

0

1

1

1

1



0

1

0

0

0

1

0

1



0

1

0

1

1

1

0

1

a  b  a  b

14

Sprawdź które z następujących formuł są
tautologiami

Sprawdź:

(a  b)  (b  c)  (c  a)  b , ((p  q)  p)  (p 

q)

((p  q)  p)  (p  q

)

P R A W A

Przemienności

p  q  q  p ,

p  q  q p

Łączności

p  (q  r)  (p  q)  r

, p  (q  r)  (p q)  r

Rozdzielności mnożenia względem dodawania

(p  q)  r  p  r  q  r

Rozdzielności dodawania względem mnożenia

(p  q)  r  (p  r)  (q

 r)

De Morgana

 (p  q)  p  q

, (p  q)  p  q

Powtórzeń

p  p  p … p  p ,

p  p  p … p  p

15

PRAWA (TAUTOLOGIE, SPRZECZNOŚCI)

Zdania złożone, które są zawsze prawdziwe, niezależnie od
wartości logicznych
zmiennych zdaniowych p, q nazywamy tautologiami.

p  p  1 ; ((p  p)  q)  q

Zdaniem sprzecznym (sprzecznością) jest zdanie, które jest
zawsze fałszywe.

p  p  0 ; (p  p)  0

(p  p)  p

 p  (p p)

( p  p)  p p  ( p  p)




1
p

p  1

0 p

 p  1





p

1

p (p  p)(A  p)  (p  A)

A

0 1 0 0 1
1 1 1 1 1

16

(((a  b)  (a  d))  (b  d))  a  b

 d

(((a  (b  d))  (b  d))

p  p p … p  p

((a  (b  d))  (b  d))

,

a  b  a  b

((a  (b  d))  (b  d))

,

(p  r)  p  q

((a  b  d)  ( (b  d)  (b  d)) ,

(a  b  d)

,

x  x 

1

(p  q)  r  (p  r)  (q  r)

(p  q ) 
r

17

Schematy logiczne funkcji dla postaci uproszczonej b)

i postaci normalnej zupełnej sumy a)

a)

b)













x

3

x

2

x

2

x

3

x

2

x

1

x

3

x

2

x

2

x

3

x

2

x

1

x

3

x

2

x

1

y









x

3

x

1

x

2

x

1

x

3

y

Dana jest funkcja trzech zmiennych:

y = f(x

3

,x

2

,x

1

) = x

3

 (x

2

 x

1

)  x

3

 x

1

y = x

3

x

2

x

1

 x

3

x

2

x

1

 x

3

x

2

x

1

 x

3

x

2

x

1

 x

3

x

2

x

1

18

Przykład
Dane są trzy zbiorniki wyposażone w trzy sygnalizatory
dwupołożeniowe podające informacje o poziomach cieczy. Należy
zasygnalizować dwa przypadki:

•Gdy wszystkie zbiorniki osiągną określony poziom

•Gdy co najmniej dwa zbiorniki osiągną ten poziom
Notując odpowiednie informacje przez a, b, c warunki te można
zapisać:

•abc

•ab ; ac ; bc

Odpowiednia funkcja przełączająca ma postać:

y = abc  ab  ac  bc

 
Rozszerzając to wyrażenie do postaci elementarnych iloczynów
zupełnych:

y = abc  ab1  a1c  1bc = abc 
ab(cc)

 a(bb)

 c  (aa)

bc = abc 

abc

 ab c  a bc

i przeprowadzając jej minimalizacje

y = ab  ac

 b c = c(a  b)  ab

otrzymujemy schemat logiczny układu

19

c
b
a









y

20

1. Podaj przykład wartościowania zmiennych tak aby poniższe formuły były

wartościowane na 0

p  (q  r)
(p  q)  r
(p  q)

2. Podaj przykład wartościowania zmiennych tak, aby poniższe formuły były

wartościowane na 1

(p  q)
(p  q)
(q  q)  (p  q)

3. Udowodnij następujące równoważności

21

ZBIORY

Zbiór liczb naturalnych: 1, 2, 3 , 4 , 5 , ...

- N = {1, 2, 3 , 4 , 5 , ...}

Zbiór liczb wymiernych: 1/2, 2/3 , 4/4 , 5/6 , ... -

W = {1/2, 2/3 , 4/4,

5/6 , ...}

Zbiór liczb niewymiernych: 2, , e ,... -  W

Zbiór liczb rzeczywistych

-

R

Zbiór liczb całkowitych

-

C

N  C  W  R ;

 W  C

;

 W  R

Suma mnogościowa

A  B = C ;

C = {c  A  c  B}

Iloczyn mnogościowy A  B = C ;

C = {c  A  c  B}

Różnica mnogościowa A \ B = C ;

C = {c  A  c  B}

Różnica symetryczna
A  B = C

; C = { c  A  B  c  A  B } = { c  A \ B  c  B \

A }

Zbiór pusty

A =    a [a  A ]

Inkluzja dwóch zbiorów

( A  B )  a [ a  A  a  B ]

22

Zbiory liczbowe
N - zbiór liczb naturalnych N ={1,2,3,4,}
Z - zbiór liczb całkowitych Z
={0,±1,±2,±3,±4,}
Q - zbiór liczb wymiernych Q=


: m Z, n Z, n 0
n
m
R – zbiór liczb rzeczywistych
Rys. 1.1 Relacje midzy zbiorami N, Z, Q, R
N Ì Z Ì Q Ì R

23



– alfabet;

{a, b, c}



*

– język – zbiór słów zbudowanych z elementów alfabetu

{a, aa, aaa, b, bb, bbb, ab, ba,….}

|{a, aa, aaa, b, bb, bbb, ab, ba,….}| = 

0

Zbiór wszystkich języków



*

jakie można zbudować na

skończonym

alfabecie



jest mocy

2

o

24

M

– automat (maszyna Turinga)

L(M)

– język akceptowany przez

M

z danego stanu początkowego

osiągany (akceptowany) jest wybrany stan z zadanego zbioru stanów

końcowych

np.: {a, aa, aaa, b, bb, bbb, ab, ba,….}

Zatem, skoro



0

< 2

o

więc nie dla każdego języka istnieje automat

M

go „rozumiejący”, a zatem nie na wszystkie pytania można

odpowiedzieć, a w konsekwencji nie każdy problem rozwiązać.

25

W dowolnym języku programowania istnieje przeliczalnie wiele
programów.

każdy program to tylko słowo, a słów (nad ustalonym alfabetem  ) jest przeliczalnie wiele

W dowolnym alfabecie można utworzyć przeliczalną liczbę języków.

języki to zbiory słów, czyli wszystkich możliwych języków (nad
ustalonym alfabetem  ) jest

2

o

> 

0

Każda maszyna Turinga (program komputerowy) akceptuje jeden
określony język.

Oznacza to, że maszyn Turinga (programów komputerowych) jest
mniej niż potencjalnych pytań (problemów)

Problem jest nierozstrzygalny, jeżeli nie istnieje algorytm, który
po skończonej (przeliczalnej) liczbie kroków jednoznacznie odpowie
TAK lub NIE dla dowolnych danych wejściowych.

26

Pamiętajmy – założyliśmy, że powyższy ciąg zawiera wszystkie
liczby rzeczywiste z przedziału

Skonstruujemy teraz liczbę rzeczywistą, która jednak w

powyższym ciągu na pewno nie wystąpi. Mianowicie, nasza

liczba ma na k-tym miejscu po przecinku cyfrę o 1 większą niż

ma na k-tym miejscu liczba stojąca w powyższym ciągu na

miejscu k-tym, lub 0 jeżeli tą cyfrą była 9.

W naszym przykładzie wyglądałaby ona tak: 0,3802334...
Ponieważ założyliśmy, że zbiór zawiera wszystkie liczby
rzeczywiste z przedziału

to znaczy, że nowo skonstruowana liczba musi być

równa którejś z liczb już tam występujący

ch.

Załóżmy, że jest równa n-tej liczbie - wtedy, w szczególności,

powinna mieć na n-tym miejscu po przecinku taką samą cyfrę -

dochodzimy, więc do sprzeczności, ponieważ skonstruowaliśmy

liczbę tak, że na n-tym miejscu ma inną cyfrę. Otrzymana

sprzeczność pokazuje, że zbiory liczb naturalnych i rzeczywistych z

przedziału [0,1] nie są równoliczne.

27

Można wykazać, że moc zbioru liczb rzeczywistych z przedziału

[0,1] jest większa od mocy zbioru liczb naturalnych. Oznacza to,

że liczb rzeczywistych jest więcej niż liczb naturalnych

|N|

 |R|



0

–

moc zbioru liczb naturalnych

N



0

= |N|

c = 2

o

moc continuum (moc zbioru liczb

rzeczywistych

R

)

c = 2

o

= |R|



0

< c

|R| = |P(N)| = 2

o

28

Metoda przekątniowa polega na skonstruowaniu elementu, o
którym wiemy, że nie należy do rozpatrywanego zbioru, dzięki
czemu można wykazać, że pewne założenie o elementach owego
zbioru jest nieprawdziwe: w przykładzie poniższym założeniem
jest możliwość ponumerowania liczb rzeczywistych z przedziału
[0,1].

Rozumowanie przebiega jak następuje: każda liczba rzeczywis

ta

ma swoje rozwinięcie dziesiętne, skończone lub nie. Jeśli jest ono
skończone, dopiszemy na jego końcu zera tak, by otrzymać
rozwinięcie formalnie nieskończone.

Załóżmy, że możemy ponumerować wszystkie liczby rzeczywiste

liczbami naturalnymi, a następnie ustawić je jedna za drugą, na
przykład w ten sposób

:

•0,267888928717743...

•0,271673820983098...

•0,219212212222222...

•0,342111334423422...

•0,213421113344234...

•0,954112122893457...

•0,739208396716263...

•...

29

Maszyna Turinga

Turing zauważył, że każdy w pełni mechaniczny proces obliczeń

składa się z następujących operacji:

•odczytywanie symboli,
•wymazywanie i zapisywanie symboli,
•zapamiętywanie i przenoszenie informacji.

Maszyna Turinga:
składa się z taśmy, głowicy pisząco-czytającej oraz urządzenia
sterującego.
Obustronnie nieskończona taśma podzielona jest na klatki, z których
każda zawiera najwyżej jeden symbol skończonego alfabetu,
zwanego alfabetem roboczym maszyny.

W dowolnym momencie prawie wszystkie klatki są puste – zawierają
element wyróżniony b (ang. blank – pusty). Głowica ma w polu
swojego działania zawsze dokładnie jedna klatkę. Urządzenie
sterujące pełni funkcje pamięcią; w każdym momencie znajduje się
ono w jednym ze skończonej liczby stanów.

30

Przykład:

Rozważmy maszynę obliczająca funkcję f(x) = x + 1 w układzie
dwójkowym.

Oznacza to, że jeśli w konfiguracji początkowej niepusta część taśmy

była zapisem dwójkowym liczby x, to po zatrzymaniu niepusta część

taśmy będzie zapisem x + 1.

START: Jeżeli odczytasz b, przesuń głowice w lewo i przejdź do

LEFT; w

przeciwnym razie przesuń głowicę w prawo i powtórz START

(szukanie

końca x).

LEFT: Jeżeli odczytasz 1, zastąp ją przez 0, przesuń głowicę w lewo i

powtórz LEFT, w przeciwnym razie symbol odczytany zastąp

jedynką i zatrzymaj się.

31

32

33

Sprawdź:

A  B  A  B

A  B  A  B

Niech A = {1,2,3,4,8,16}, B =

{2,4,6,8,10} , C = {1,3,7,15}.

Wyznacz:

A \ C

B  (C  B)

A  B

(B  A)  (A  C)

A  B

`

C \ (B \ A)

B  C

A  (B  C)

34

A \ B  A  B

A

1. A  B =


A \ B = A

, A  B = 

, A  

2. A 
B

A \ B =  , A  B = A

,   A

A \ B =

,



, A  B =

A

B

B

3. A  B  

A

35

B

36

A \ B = B \ A

xA  xB = xB  xA

xA  xB = xB  xA

a  b = b  a

a  b = a  b

A  B  A  B

xA  xB  xA  xB

a  b  a  b

(a  b)  a  b
a  b  a  b
a  a  bb

1  1  1

Można też sprawdzać metodą sprowadzania badanej formuły do dziedziny
rachunku zdań:

37

A \ B = B \ A

xA  xB  xB  xA

xA  xB  xB  xA

a  b  b  a

a  b  a  b

A  B  A  B

xA  xB  xA  xB

a  b  a  b

(a  b)  a  b
a  b  a  b
a  a  bb

1  1  1

38

Bądź też wreszcie wykazując jej fałszywość przez

wskazanie kontrprzykładu:

A \ (B \ C) = (A \ B) \ C)

A = {1,2,…11,12}; B = {7,8}; C = {9,10}

Lewa strona:

A \ (B \ C) = {1,2,…11,12} \ ({7,8}\{9,10}) = {1,2,…11,12} \

{7,8} =

= {1,2,3,4,5,6,9,10,11,12}

Prawa strona

(A \ B) \ C) = ({1,2,…11,12} \ {7,8}) \ {9,10} =

= {1,2,3,4,5,6,9,10,11,12}\ {9,10} =

{1,2,3,4,5,6,11,12}

Ostatecznie:

A \ (B \ C) = (A \ B) \ C)

{1,2,3,4,5,6,9,10,11,12} = {1,2,3,4,5,6,11,12}

39

A \ B = B \ A

xA  xB = xB  xA

xA  xB = xB  xA

a  b = b  a

a  b = a  b

A \ (B \ C) = (A \ B) \ C)

A = {1,2,…11,12}; B = {7,8}; C = {9,10}

A \ (B \ C) = {1,2,…11,12} \ ({7,8}\{9,10}) = {1,2,…11,12} \

{7,8} =

= {1,2,3,4,5,6,9,10,11,12}

(A \ B) \ C) = ({1,2,…11,12} \ {7,8}) \ {9,10} =

= {1,2,3,4,5,6,9,10,11,12}\ {9,10} = {1,2,3,4,5,6,11,12}

A \ (B \ C) = (A \ B) \ C)

{1,2,3,4,5,6,9,10,11,12} = {1,2,3,4,5,6,11,12}

A

A’

1

a  A’  a  1  a 

A

A’ = 1 \ A

N  W

; (W  N )

;

W  W = 

;

N \ W = 

Zbiór potęgowy

P(S) (zbioru S to zbiór wszystkich podzbiorów

zbioru S.

S={a,b} ; P(S) = { , {a}, {b} , {a,b}}

|S| = 2 ,

|P(S)| = 2

2

|P()| = ??? ,

|P({1})| = ???

Przestrzeń

(zbiór pełny) 1

Dopełnienie

A’ zbioru A przestrzeni 1

{

5n | n  N} = {5, 10, 15,…}

{4n + 3 | n N} = { , ,…., }

40

1.Wypisz po kilka elementów z następujących
zbiorów:

{nN: n jest podzielna przez 5}

{2

n

: n  N }

{1/n : n  {1,2,3,4}}

{ x  R : x = k/n i k  {1,2} i n  {1,2,4,8} }

2. Jaka jest liczba elementów podanych poniżej
zbiorów?

{n  N : n

2

= 2},

{x  Z: x

2

= 2}, {x  R: x

2

= 2}

{n  N: n jest liczbą pierwszą, niewiększą niż 10}

{n  N: n jest potęgą 2}

{x  Z: |x| <10}, {x  R: |x| <10}

{n  N : n jest liczbą parzystą i liczbą podzielną przez

3}

3. Niech U={n  N: n < 20} będzie ustalonym uniwersum i niech A i B

będą jego podzbiorami takimi, że A= {2n+1: n  N i n < 6},

B = {3n+2: n  N i n < 6}.

Wyznacz elementy zbiorów A  B, A  B, A \ B, B \ A,

Iloczyn kartezjański zbiorów

(produkt)

Dla dowolnych zbiorów A, B iloczynem kartezjańskim
nazywamy zbiór
wszystkich par uporządkowanych (a, b) takich, że a  A i b  B

A  B = {(a,b) : a  A  b  B

}

Produkt dowolnej, skończonej rodziny zbiorów

S

1

 S

2

 S

3

... S

n

= { (s

1

, s

2

, s

3

, ..., s

n

) : s

k

 S

k

dla k = 1, 2,

3, ..., n }

PRZYKŁAD

{a}  {b} = {(a,b)}

{3}  {a,b} = {(3,a), (3,b)}

{1,2}  {a,b} = {(1,a), (1,b), (2,a), (2,b)}

42

Wprowadzimy oznaczenia dla pewnych szczególnych
podzbiorów zbioru R, nazywanych przedziałami.

Dla a,b  R gdzie a < b, określamy:

{ x  R : a < x < b } = (a,b) – przedział otwarty

{ x  R : a  x  b } = [a,b] – przedział domknięty

{ x  R : a  x < b } = [a,b) – przedział prawostronnie

otwarty

{ x  R : a < x  b } = (a,b] – przedział prawostronnie

domknięty

43

Alfabet to skończony zbiór S , którego elementami są symbole
zwane literami
alfabetu S .

Słowem danego alfabetu S nazywamy dowolny skończony ciąg
liter tego zbioru S

Zbiór wszystkich słów zbudowanych z elementów zbioru S
oznaczamy S *.

S* jest zbiorem nieskończonym.

Dowolny podzbiór zbioru S* nazywamy językiem nad alfabetem S
.

Słowo puste -  (ciąg nie zawierający liter );

analogia do

zbioru pustego.

PRZYKŁAD

Jeżeli  = { a,b }, to S *= {, a, b, aa, bb, abb, aaa,

babb, ... }

Jeżeli  = { a }, to S *= {, a, aa, aaa, aaaa, ... }

Jeżeli  = { 0, 1, 2} , to *= {, 0, 1, 2, 00, 01, 02, 11, 12, 20,

21, 22, 000, ... }

Jeżeli  = { a,b } i dł(w) oznacza długość słowa w zbiorze *,

to

A = { w   *: dł(w) = 2 } = { aa, ab, bb, ba }

44

Wnioskowanie

Modus ponens

a  b

a, a  b

b

Zasada rezolucji

(a  b  b  c)  (a  c)

a  b, b  c

b  c

Objawy  Diagnoza  Terapia

Dowody

 Wyrok 

Kara

A i B przyprostokątne,

IF

A i B przyprostokątne

THEN

C

2

= A

2

+ B

2

p – dzisiaj jest niedziela
q – mam wolny dzień
r – jadę na ryby

Jeżeli prawdą jest, że

p  q ,

oraz

jeżeli prawdą jest, że q  r,

Zatem:

w każdą niedzielę p jestem na rybach r.

bo

p, p  q

q

q , q  r
r

C

2

= A

2

+ B

2

46

Fakty: a, b

Baza

wiedzy:

R1. a  c  d

R2. a  b  c

R3. b  d  g

R4. c  g  h

h?

g

d

R3

a

b

R2 c

h

R1

R4

Udowodnij że nie jesteś
wielbłądem!

R

1

: a  b  c  d

R

2

: d  c  f

R

3

: f  d  x  h

h?

47

Spójność:

(a,L)  (c,3)  (d,H) ,

(~(a,H))  (c,3)  (d,H)

Niesprzeczność: (a,L)  (c,3)  (d,H) , (a,L)  (c,3)  (d,L)

Pochłanianie:

(a,L)  (c,3)  (d,H) ,

(a,L)  (b,D)  (c,3) 

(d,H)

(c,3)  (d,H) ,

(a,L)  (c,3)  (d,H)

Zapętlenie: (a,L)  (c,5)  (d,H) , (d,H)  (f,2) , (f,2)  (g,4)  (c,5)

(a, L)

(d, H)

(f, 2)

(c, 5)

(g, 4)

48

49

Baza faktów: BF = {e,f}

Baza reguł: BR = {

}

e

f

d

b

a

c

R

3

R

1

R

5

R

2

50

Przykłady

P(Janek,Zosia) = [Janek jest bratem Zosi] , P(V,x,y,z) = [V

= x*y*z]

xR [x + 0 = x] , xN [x = x*x] , xN [x < 0] , xR [x <

0] ,

x  zbiór kotów [x pije mleko] , x  zbiór szpaków [x jest

ptakiem]

x  zbiór dzieci y  zbiór rodziców [x jest dzieckiem y]

Rachunek predykatów

 jeden talerz  student

,

 student  jeden talerz

Niech P(x) = [x = x*x] która z tez jest prawdziwa:

 x  R P(x)

,

 x  R P(x)

 x {0,1} [x  x  0]

,

x {0,1} [x  x  1]

Predykaty

P(x) , P(x) = [ x = 3] , P(x) = [Q(x) U(x)] , [pije mleko] ,

[jest zielone],

P(x

1

,x

2

,...,x

n

) , P(x,y,z) = [x + y = z] , P(x,y) = [x > y] , [jest

dzieckiem],

51

Bardziej formalnie:

Predykatem lub funkcją zdaniową nazywamy wyrażenie W(x), w którym
występuje zmienna x i które staje się zdaniem prawdziwym lub
fałszywym, gdy w miejsce x podstawimy wartość zmiennej x.

Rachunek predykatów został stworzony poprzez rozszerzenie rachunku
zdań o kwantyfikatory ogólny i szczególny: „dla każdego”  oraz
„istnieje takie, że” .

Rachunek predykatów przyjmuje założenie o monotoniczności logiki. Oznacza to,
że jeżeli po przyjęciu zbioru aksjomatów wykazywana hipoteza jest poprawna
(czyli jest twierdzeniem), to po dodaniu nowego

aksjomatu

wynik ten nie może

ulec zmianie.
Założenie to nie pozwala na uwzględnienie wyjątków powodujących, że zbiór
aksjomatów staje się zbiorem sprzecznym, co w niektórych przypadkach ogranicza
możliwość zastosowania omawianego rachunku.

Przykład

 x[jest_ptakiem(x)  potrafi_latac(x)]

jest_ptakiem(struś)

¬ potrafi_latac(struś)

Twierdzenie „dla wszystkich x, jeżeli x jest ptakiem, to x potrafi latać” jest nie do
końca poprawne ponieważ występują pewne odstępstwa od niego.
Otóż, struś jest ptakiem i nie potrafi latać. Bazę wiedzy należałoby uzupełnić o
nowy aksjomat:
¬ potrafi_latac(struś). Uwzględnianiem takich przypadków zajmuje się logika
niemonotoniczna.

52

Sprawdzanie prawdziwości

x P(x) - „jeden zaprzecza wszystkiemu“

x P(x) - „jeden wystarcza“

( x P(x))   x [P(x)]

Przykład

( x  R [x < x + 1]   x  R [x  x + 1]

( y Q(y))  y [Q(y)]

Przykład

( x  y [y > x])   x ( y [y > x])   x  y ( [y > x])   x 

y [y  x]

53

Niech U’ = {1,2,3} , U” = {4,5,6,7} sprawdź
prawdziwość:

 X  U’  y  U” [y > x]

 x  U’  y  U” [y > x]

 X  U’  y  U” [y > x]

 x  U’  y  U” [y > x]

! xR [x*6 = 0]

 x  R  y R ! z  R [x + y = z]

 x {1,2,3} P(x)  P(1)  P(2)  P(3) ,

(x P(x)  x P(x))  (x P(x)  x Q(x))

x P(x) x P(x) x Q(x) x P(x)  x P(x)

x P(x) 

x Q(x)

0

0

0

1

1

0

0

1

1

1

0

1

0

1

0

0

1

1

1

1

1

0

0

1

0

1

1

1

0

54

( x P(x)   x P(x))  ( x P(x)   x Q(x))

( A  A )

 ( B  C )

( A  A )

 (B  C )

1



?????

( x P(x)   x P(x))  ( x P(x)   x Q(x))

Sprawdź

Twierdzenie o dedukcji (zasada rezolucji)

Jeżeli formuły {A1, A2,…, An} nie są sprzeczne, to formuła B jest ich

konkluzją (tzn. wynika inferencyjnie z formuł A1, A2,…, An) wtedy i

tylko wtedy, gdy formuły { A1,A2,…,An, ¬B} są sprzeczne.

55

Każdy człowiek jest śmiertelny.

 x : Cz(x)  Śm(x)

Marek jest człowiekiem.

Cz(M)

Czy Marek jest śmiertelny?

Śm(M)?

 x : Cz(x)  Śm(x)

Cz(x)  Śm(x)

Cz(M)

Cz(M)

Śm(M)?

Śm(M)

Cz(x)  Śm(x) , Cz(M)

Śm(M)

Śm(M) , Śm(M)



Cz(x)  Śm(x)

, Cz(M)

Śm(M)

Śm(M)

x:=M



Zasada rezolucji

(a  b  b  c)  (a  c)a  b, b  c

a  c

56

Każdy człowiek jest śmiertelny.

 x : Cz(x)  Śm(x)

Marek nie jest człowiekiem.

Cz(M)

Czy Marek jest śmiertelny?

Śm(M)?

 x : Cz(x)  Śm(x)

Cz(x)  Śm(x)

Cz(M)

Cz(M)

Śm(M)?

Śm(M)

Cz(x)  Śm(x) ,  Cz(M)

Cz(M)  Śm(M) , Śm(M)

Cz(x)  Śm(x)

,  Cz(M)

x:=M

Cz(M)  Śm(M)

Cz(M)  Śm(M) Śm(M)

Cz(M)

Cz(M)

57

Według kodeksu cywilnego, jeżeli x jest mężem y ,to y jest żoną x.

Korzystając z tego faktu oraz przyjmując, że x to Linda, a y to Bil, należy

przekonać Bila, że Linda jest jednak jego żoną, czemu on gorąco

zaprzecza.

W zapisie predykatowym mamy zatem, że:

Żona(Linda, Bil)

¬Żona(x,y)  Mąż(y,x)

¬Mąż(Bil, Linda)

58

Rozważmy system ekspertowy, którego baza wiedzy zawiera m reguł,

a maksymalna liczba faktów wynosi n.

Przyjmijmy najgorszy przypadek, w którym baza wiedzy zawiera tylko

jeden fakt. Oznacza to, że należy wygenerować pozostałych n-1 faktów.
W przeszukiwaniu bazy reguł należy sprawdzać wszystkie kombinacje

faktów każdorazowo rozszerzonej bazy faktów.

Oznacza to, że każda z n reguł musi być „sprawdzona” kolejno dla

kombinacji 1 po 1, 2 po 1 i 2 po 2, 3 po 1 i 3 po 2 oraz 3 po 3, aż do

kombinacji z n-1 po 1, itd.

Tak więc sprawdzeniami objętych jest m2

1

+ m2

2

+…+m2

n-1

przypadków. Wykorzystywana jest tutaj zależność:

59

Niech m = 500 reguł oraz n = 101 faktów. Oznacza to konieczność

dokonania ok.

2

100

sprawdzeń.

Przyjmując, że rok ma 31 536 000, tzn. ok. 310

7

sekund i zakładając

wykorzystanie

komputera

umożliwiającego

wykonywanie

1000

sprawdzeń na jedną nanosekundę, a zatem posiadając możliwość

dokonywania rocznie

3 10

7

10

9 

10

3

= 3 10

19

sprawdzeń,

samo sprawdzanie (wyszukiwanie) postawionej hipotezy w najgorszym

przypadku trwałoby 10

30

/(3 10

19

) 

10

11

lat.

Zauważmy bowiem, że 2

100

 10

30

,

ponieważ 2

10

 10

3

,

więc 2

10

2

10

2

10

... 2

10

 10

3

10

3

10

3

... 10

3

= 10

310

 10

30

.

10

10

60

x{P(x)  {y[P(y)  P(f(x,y))]  ~y[Q(x,y)  P(y)}}

Krok 1 x{~P(x)  {y[~P(y)  P((f(x,y))]  ~y[~Q(x,y) 

P(y)]}}

Krok 2 x{~P(x)  {y[~P(y)  P((f(x,y))]  y[Q(x,y) 

~P(y)]}}

Krok 3

x{~P(x)  {y[~P(y)  P((f(x,y))]  z[Q(x,z) 

~P(z)]}}

Krok 4 x{~P(x)  {y[~P(y)  P((f(x,y))]  [Q(x,z) 

~P(z)]}}

Krok 5 x y{~P(x)  {[~P(y)  P((f(x,y))]  [Q(x,z) 

~P(z)]}}

Krok 6 i 7

[~P(x)  ~P(y)  P((f(x,y))]  [~P(x)  Q((f(x,g(x))]  [~P(x) 

~P(g(x))]

A  (B  C)  (D  E)  (A  B  C)  (A  D)  (A  E)

Krok 8

~P(x) ∨ ~P(y) ∨ P((f(x,y))
~P(x) ∨ Q((f(x,g(x))
~P(x)∨ ~P(g(x))

Krok 9

~P(x

1

) ∨ ~P(y

1

) ∨ P((f(x

1

,y

1

))

~P(x

2

)∨ Q((f(x

2

,g(x

2

))

~P(x

3

)∨ ~P(g(x

3

))

61

Dana jest formuła postaci:

 x[P(x) ( y[P(y)  P(f(x,y))]  ¬  y[Q(x,y)  P(y)])]

1. Podczas pierwszego kroku usuniemy symbol implikacji,

wykorzystując znane

przekształcenie A B  ( ¬ A)  B.

"x[ ¬ P(x)  ( y[ ¬ P(y)  P(f(x,y))]  ¬  y[ ¬ Q(x,y)  P(y)])]

2. W tym kroku przemieszczamy wszystkie zewnętrzne znaki negacji

do wewnątrz w celu przypisania ich wyłącznie formułom atomowym. W
przypadku kwantyfikatora ogólnego korzystamy z własności ¬  x[A]  
x[ ¬ A].

"x[ ¬ P(x)  ( y[ ¬ P(y)  P(f(x,y))]   y[ ¬ ( ¬ Q(x,y) 

P(y))])]

Korzystając z prawa de Morgana ¬ (A  B)  ( ¬ A)  ( ¬ B)

otrzymujemy

 x[ ¬ P(x)  ( y[ ¬ P(y)  P(f(x,y))]   y[Q(x,y)  ¬ P(y)])]

62

3. Eliminujemy kwantyfikator szczegółowy  poprzez wprowadzenie
odpowiednich stałych w miejsce zmiennych będących w zasięgu
kwantyfikatora.

 x[ ¬ P(x)  ( y[ ¬ P(y)  P(f(x,y))]  z[Q(x,z)  ¬ P(z)])]

Następnie usuwamy kwantyfikator szczegółowy . Powołując się na zasadę:

Jeżeli kwantyfikator szczegółowy jest w zasięgu kwantyfikatora ogólnego to

należy wprowadzić funkcję uzależnioną od zmiennej kwantyfikatora

ogólnego. wstawiamy funkcję

g(x)

w miejsce zmiennej

z

 x[ ¬ P(x)  ( y[ ¬ P(y)  P(f(x,y))]  (Q(x,g(x))  ¬ P(g(x)))]

4. W tym kroku przemieszczamy kwantyfikator ogólny  na zewnątrz formuły
złożonej.

 x y[ ¬ P(x)  (( ¬ P(y)  P(f(x,y)))  (Q(x,g(x))  ¬ P(g(x)))]

Korzystając z zasady:
Jeżeli wszystkie zmienne są w zasięgu kwantyfikatora to możemy z niego
zrezygnować pamiętając, że każda zmienna w formule została wyprowadzona
za pomocą kwantyfikatora ogólnego. pozbywamy się kwantyfikatorów
ogólnych

¬ P(x)  (( ¬ P(y)  P(f(x,y)))  (Q(x,g(x))  ¬ P(g(x)))

63

5. W tym miejscu należy tak przekształcić formułę, aby funktory
koniunkcji były zewnętrzne względem funktorów alternatywy.

Korzystamy z własności A  (B  C)  (A  B)  (A  C)

{ ¬ P(x)  ¬ P(y)  P(f(x,y))}  [{ ¬ P(x)  Q(x,g(x))}  { ¬ P(x)

 ¬ P(g(x)}]

6. Z ostatniego wyrażenia po usunięciu symbolu koniunkcji otrzymujemy
postać klauzulową

i) ¬ P(x)  ¬ P(y)  P(f(x,y))

ii) ¬ P(x)  Q(x,g(x))

iii) ¬ P(x)  ¬ P(g(x)

64

Wykład 2

Elementy teorii liczb

•funkcje całkowitoliczbowe: powała i podłoga,

•podzielność liczb – algorytm Euklidesa,

•równanie diofantyczne,

•NWD, NWW, operator modulo,

•liczby pierwsze i rozkład liczb na czynniki, liczby doskonałe,

Ciągi - funkcje zmiennej naturalnej

a

n

= n

;

a

1

= 1 , a

2

= 2 , a

3

= 3

,

. . .

a

n

= n

2

;

a

n

= 2

n

,

a

n

= n!

Funkcje całkowitoliczbowe

Podłoga

xR

, x = max{nC : n x}

 = 3;

- = -4

Powała

xR

, x = min{nC : n x}

 = 4;

- = -3

65

66

Funkcje całkowitoliczbowe

Podłoga

xR

, x = max{nC : n x}

 = 3;

- = -4

Powała

xR

, x = min{nC : n x}

 = 4;

- = -3

1 x = x  x = x  xC

;

x  x  x

2 x - x = 1  xR

3 - x = - x

;

x = - - x

4 x = n  n  x < n+1

5 x = n  x – 1 < n  x

6 x = n  n – 1 < x  n

7 x = n  x  n < x+1

67

Dane n  N

Ile potrzeba zarezerwować bitów pamięci dla zapisania n w komputerze?

(2002)

10

= 2 10

3

+ 0 10

2

+ 0 10

1

+ 2 10

0

(101001)

2

= 1 2

5

+ 0 2

4

+ 1 2

3

+ 0 2

2

+ 0 2

1

+ 1 2

0

32 8 1

2

5

= 32  41 < 64 = 2

6

Zatem liczba

n

zapisana na

m

bitach spełnia nierówność

2

m-1

 n < 2

m

2

m-1

 n < 2

m

/ log

2

x = n  n  x < n+1

m-1  log

2

n < m

log

2

n = m-1

a

zatem

m = log

2

n +1

Przykład

n = 7

;

log

2

7 = 2 (bo 2

2

= 4 a 2

3

= 8 ) zatem m = 2 + 1 =

3

Właściwość: 4 x = n  n  x <n+1

m-1  log

2

n < m

68

Algorytm Euklidesa

(por.: Sysło M.M., Algorytmy, WSiP, Warszawa, 1997, Sysło M.,

Piramidy, szyszki I inne konstrukcje algorytmiczne. WsiP, Warszawa, 1998.)

Liczba k jest największym wspólnym dzielnikiem m i n, tzn.

NWD(m,n), jeśli dzieli m oraz n i jest największą liczba o tej

właściwości.

Algorytm Euklidesa znajduje NWD(m,n).

NWD(n,m) = max{kN : k dzieli n  k dzieli m }

NWD(48,6) = 6 , NWD(26,15) = 1

NWD(n,m)

Niech n  m

n/m = q + r ; n = q m + r ; r = n - q m ; 0  r  m-1

NWD(n,m) = NWD(m,r)

NWD(24,12) ; 24 = 2 x 12 + 0 ; NWD(12,0)

NWD(37,35) ; 37 = 1 x 35 + 2 ; NWD(35,2) = NWD(2,1) ; NWD(2,1) =
NWD(1,0)

69

NWD(n,m)

Niech n  m

n/m = q + r ; n = q m + r ; r = n - q m ; 0  r  m-1

NWD(n,m) = NWD(m,r) ; NWD(37,35) ; 37 = 1 x 35 + 2

NWD(721,448)

n

= q x m + r

721 =

1 x 448 + 273

448 =

1 x 273 +

175

273 =

1 x 175 +

98

175 =

1 x 98 +

77

98 =

1 x 77 +

21

77 =

3 x 21 +

14

21 =

1 x 14 +

7

14 =

2 x 7

+ 0

NWD(721,448) = 7

NWD(35,2) ; 35 = 2 x 17 + 1 ;
NWD(17,1)

70

Równania diofantyczne

A

2

+ B

2

= C

2

3

2

+ 4

2

= 5

2

trójkąty pitagorejskie

A

n

+ B

n

= C

n

Przykład

Dane są naczynia o pojemności m i n. Czy korzystając z nich można

napełnić zbiornik o pojemności k ? Jeżeli tak to w jaki sposób?

Niech m, n  N ,

x, y  Z ;

k = x m + y n

5 x + 7 y = 3

;

15 = 4 x + 10 y ;

3 = 6 x + 18 y

NWD(7,5) = 1

NWD(10,4) = 2

NWD(18,6) =6

Rozwiązanie istnieje gdy k jest wielokrotnością NWD(m,n).

15 = 4 x + 10 y

nie ma rozwiązania, bo 2 = NWD(4,10),

3 = 5 x + 7 y

rozwiązanie istnieje, bo 1 = NWD(5,7).

71

Najmniejsza wspólna wielokrotność:

NWW(m,n)

NWW(m,n) = min{k: k jest podzielne przez m  k jest podzielne

przez m}

NWW(12,9) = 3 bo ;

12 = 3  3  2

;

9 = 3  3

m  n 12  9

NWW(12,9) = ---------------- =------ = 36
NWD(12,9)

3

Liczby pierwsze

nN jest liczbą pierwszą jeśli n jest podzielne tylko przez 1 i n.

Liczb pierwszych jest nieskończenie wiele.

Każdą liczbę naturalną można przedstawić w postaci

H = 2

l1

 3

l3

 5

l5

 7

l7

 11

l11

 13

l13

.........

l

1

, l

3

, l

5

, . .. – nieujemne liczby całkowite

72

Niech p

1

, p

2

, p

3

, ..., p

k

wszystkie liczby pierwsze

Euler

M = p

1

 p

2

 p

3

 ...  (p

k

+ 1) - liczba pierwsza

O

1

= 2

O

2

= 2 +1 = 3

O

3

= 2  3 +1 = 7

O

4

= 2  3  7 + 1 = 43

ale O

4

= 2  3  7  43 + 1 = 1807 = 13  139

2

k

Fermat

L

k

= 2 + 1

k = 1, 2 , 3 , 4 - liczba pierwsza

ale dla k = 5 nie jest liczbą pierwszą

73

n mod m , Mod(n,m) , MOD(n,m)

- reszta z

dzielenia n przez m

7 mod 3 = 1

;

1 mod 7 = 1

;

7 mod 7 = 0

n div m , Div(n,m) , DIV(n,m)

-

całkowita część

wyniku dzielenia

7 div 3 = 2 ;

1 div 7 = 0 ;

7 div 7 = 1

Liczba doskonała

Liczba doskonała jest liczbą naturalną gdy jest równa sumie

wszystkich swoich dzielników właściwych, tzn. takich które są

od niej mniejsze.

6 = 1 + 2 + 3

28 = 1 + 2 + 4 + 7 + 14

74

Wykład 3

Elementy kombinatoryki

• zasada gołębnika,

• zasada włączania i wyłączania,

• permutacje, kombinacje, podziały liczb,

• algorytmy generowania obiektów kombinatorycznych,

Zasada Gołębnika

(Zasada szufladkowa DIRICHLET’A)

Niech:

m obiektów oraz n pudełek

jeżeli n < m, to przynajmniej dwa obiekty są w jednym pudełku

Niech |A| - moc zbioru A ;

np. A = {a,b,c,d,e} ; |A| = 5

Jeżeli skończony zbiór S jest podzielony na k zbiorów, to co najmniej

jeden z tych zbiorów ma |S|/k lub więcej elementów.

Zastosowania:

W każdej grupie n osób są przynajmniej 2 osoby, które znają tę samą liczbę

osób.

75

Dany zbiór A = {

a

1

, a

2

,...,a

9

} taki, że suma jego elementów = 90.

a)  trzy takie elementy zbioru A, że ich suma  30.

b)  cztery takie elementy zbioru A, że ich suma  40.

a)

(a

1

+ a

2

+ a

3

)

+ (a

4

+ a

5

+ a

6

) + (a

7

+ a

8

+ a

9

) =

90

 < 30

 < 30

 > 30

 < 30

 = 30

 > 30

b

)

a

1

a

2

a

3

a

4

a

5

a

6

a

7

a

8

a

9

a

2

a

3

a

4

a

5

a

6

a

7

a

8

a

9

a

1

a

3

a

4

a

5

a

6

a

7

a

8

a

9

a

1

a

2

a

4

a

5

a

6

a

7

a

8

a

9

a

1

a

2

a

3

4 x 90 = 360 zatem 360/9 = 40

a

1

+ a

2

+ a

3

+ a

4

lub a

2

+ a

3

+ a

4

+ a

5

lub .......  40

76

Zasada włączania i wyłączania

Należy „włączyć” (dodać do siebie liczności poszczególnych zbiorów),

następnie „wyłączyć” (odjąć liczność przecięć po dwa zbiory), potem

„włączyć” (dodać liczności wszystkich przecięć po trzy zbiory), itd.

| A  B  C | = |A| + |B| + |C| - |A  B| - |A  C| - |B  C| + |A
 B  B|

Ilustracja

A = {a,b} ;

B = {1,2}

;

C = {x,y}

|A  B  C | = 6 = 2 + 2 + 2 – 0 – 0 – 0 + 0 = 6

A

B

C

77

Zastosowanie

Ile jest liczb między 1 a 999 nie podzielnych, ani przez 5, ani

przez 7?

/
7

/
5

1, 2, ... , 999

999 - „/5” - „/7” + „/5 7” = 999 -  999/5  -  999/7  + 
999/35  =

= 999 - 199 - 142 + 28 = 686

78

Ile liczb naturalnych ze zbioru S = {1,2,3,...,1000} dzieli się przez

3 lub

5 lub przez obie te liczby jednocześnie?

Niech D

3

= {nS : n dzieli się przez 3}

D

5

= {nS : n dzieli się przez 5}

D

3



D

5

= {nS : n dzieli się przez 15}

D

3

= {3mS : 1 m  333}

| D

3

|

=  1000/3  = 333

D

5

= {5mS : 1 m  200}

| D

5

|

=  1000/5  = 200

| D

3



D

5

| =  1000/15  = 66

Zatem

| D

3

 D

5

| = | D

3

| + | D

5

| - | D

3



D

5

| = 333 + 200 – 66 = 467

79

Permutacje

- funkcje na zbiorze liczb naturalnych {a

1

,a

2

, ...,a

n

}

Liczba permutacji

P

n

= n! = n  (n-1) (n-2)  ...  1 = 1  2  3 

...  n

0! = 1

{A , B , C}

A B
C

B C A C
A B
C B C A
B A

Urzędnik zapomniał hasła do swoje aktówki. Hasło jest liczbą 7 cyfrową złożoną z

cyfr od 1 do 7. Cyfry w haśle nie powtarzają się. (Ostatnie 3 cyfry wybierane są ze

zbioru {3,4,7}).

Ile możliwości w najgorszym przypadku trzeba sprawdzić aby otworzyć zamek?

{3,4,7} - (3,4,7) , (4,7,3) , (7,4,3) , (3,7,4) , (4,3,7) , (7,3,4)

80

Wariacje

- bez powtórzeń

Dany zbiór A = {a

1

,a

2

, ...,a

n

}.

Wariacja – k-elementowy ciąg nie powtarzających się obiektów zbioru A.

Liczba k-elementowych wariacji zbioru A, n = |A| .

V

n

k

= n  (n-1)  (n-2)  ... (n – k+1))

n!

n  (n-1)  (n-2) ...(n-k+1)  (n- k) (n-k-1)..2  1

V

n

k

=

=

(n-k)!

(n-k) (n-k-1)  ...  2  1

= n (n-1) ... (n-k+1)

A = {a,b,c}

; k = 2 ;

(a,b) , (a,c) , (b,c) , (b,a) , (c,a) ,

(c,b)

W urnie jest 10 kul ponumerowanych od 1 do 10. Losujemy kolejno i bez zwrotu 5

kul. Po każdym losowaniu zapisujemy jej numer. Ile jest wszystkich możliwych

wyników losowania?

V

n

k

= n (n-1) (n-2) ... (n – (k-1)) ; V

10

5

= 10 9 8 7 6

81

Wariacje

- z powtórzeniami

Rzucamy 10 razy monetą. Ile jest możliwych wyników tego

doświadczenia?

Liczba k- elementowych wariacji z powtórzeniami

W

n

k

= n  n  n  n  ...  n = n

k

k

{O,R} , {O,R},..., {O,R} ; 2

n

Na ile sposobów można rozmieścić 2 kule (czarna i białą) w 3

szufladach?

I

II

III

0

b

c

0

c

b

0

c-b 0

0

0

c-b

b

c

0

c

b

0

c-b 0

0

b

0

c

c

0

b

82

Kombinacje

Dany zbiór A = {a

1

,a

2

, ...,a

n

}.

Kombinacja – k-elementowy podzbiór zbioru A.

Liczba k-elementowych kombinacji ze zbioru A, n = |

A| .

n! n

C

n

k

= =

k! (n-k)! k

3 3!

= = 3 , {3,2,1}

, k = 2

; (1,2) , (1,3) ,

(2,3)
2 2!  1!

Łatwo zauważyć, że:

n!

V

n

k

= = k! C

n

k

(n-k)!

83

Na ile sposobów można wybrać 8 kart z talii 24 kart jeżeli kolejność nie

jest ważna?

Ile z tych układów 8- kartowych zawiera 2 asy.

C

20

6

 C

4

2

Na ile sposobów można rozmieścić 6 osób w 3 różnych pokojach 2 osobowych?

C

6

2

 C

4

2

 C

2

2

Własności kombinacji

a)

n

n

=

k

n - k

b)

n

n

=

0

n

c)

n

n

=

1

n - 1

84

Trójkat Pascal’a

1

1

1

1

2

1

1

3

3

1

1

4

6

4

1

Dwumian Newton’a

n

n

n

n

(a + b)

n

=

a

n

+ a

n-1

b + ... + a b

n-1

+ b

n

0

1

n-1

n

n

n

(a +b)

n

=  a

n-i

b

i

i=0

i

85

Ciąg Fibonacciego Leonardo Fibonacci (1175 - 1250)).

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,

2584, 4181,...

F

1

= 1

;

F

2

= 1 ;

F

n

= F

n-1

+ F

n-2

dla n > 2

Pary

1 1 2 3 5 8

Okresy 1 2 3 4 5
6

M

M

M

M

M

M

M

R

R

R

R

R

R

R
R

R

R

R

M

R

86

Złota

proporcja

2/1 = 2 ; 3/2 = 1.5 ; 5/3 = 1.667 ; 8/5 = 1.6 ; 13/8 = 1.625 21/13 =
1.615 ; 34/21 = 1.619:

; 55/34 = 1.618 . . .

≈ 1,618033989

współczynnik „złotych proporcji”

rozwiązanie równania:

a

x

a-x

a x

a

2

a

=

;

a

2

– a x = x

2

- - 1 = 0

x a – x

x

2

x

a
x

=

87

front Partenonu

F

n+1

5 + 1

 =

=

= 1,618033989.....

F

n

2

1 1 + 5

1 - 5

F

n

=

5 2

2

n

n

a

x

a –
x

88

Wykład 4

Elementy kombinatoryki

• algorytmy i zależności rekurencyjne,

• symbol Newtona, trójkąt Pascal’a

• rozwiązywanie zależności rekurencyjnych – przez podstawianie i za pomocą

równania charakterystycznego,

• kongruencje, schemat Hornera

(por.: Sysło M., Piramidy, szyszki i inne konstrukcje algorytmiczne. WSiP, Warszawa,

1998.

Ross K.A., Wright C.R.B., Matematyka dyskretna, PWN, Warszawa 1996.)

Algorytmy i zależności rekurencyjne

Wieża w Hanoi

Trzy kręgi

wymagają 7 przełożeń bo 2

3

– 1 = 7

Trzy kręgi wymagają 7 przełożeń bo 2

3

– 1 = 7

n okręgów wymaga 2

n

– 1 przełożeń

Jeden krąg - jedno przełożenie

2

1

- 1

Dwa kręgi - trzy przełożenia

2

2

- 1

90

Zależności rekurencyjne

1 , -3 , - 27 , -185 , …

S

n

= 6S

n-1

– 9S

n-2

, n  2 , S

o

= 1 , s

1

= -3

S

n

= 3

n

- 2n3

n

, n  N

0

Sprawdzenie:

n

S

n

= 6S

n-1

– 9S

n-2

S

n

= 3

n

- 2n3

n

0

1

3

0

- 2*0*3

0

=1

1

-3

3

1

- 2*1*3

1

= -3

2

6*(-3)– 9*1 = -27

3

2

- 2*2*3

2

= -27

3

6*(-27)– 9*(-3) = -185

3

3

- 2*3*3

3

= -185

4

. . .

. . .

91

Trójkat Pascal’a

n = 4

{a,b,c,d}

k = 0



1

k = 1

{a}, {b}, {c}, {d}

4

k = 2

{a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}

6

k = 3

{a,b,c}, {a,b,d},{a,c,d}, {b,c,d}

4

k = 4

{a,b,c,d}

1

n! n

C

n

k

= =

k!(n-k)! k

1

1

1

1

2

1

1

3

3

1

1

4

6

4

1

(symbol Newton’a)

92

1

1

1

1

2

1

1

3

3

1

1

4

6

4

1

n

n n n

(a – b)

n

=

a

n

+ a

n-1

b + . . . + a b

n-1

+ b

n

0

1 n-1 n

n n
(a – b)

n

=



a

n-i

b

i

i=0 i

Dwumian Newton’a

93

Liczby Fibonacciego

1 1

2 3 5 8 13 21 34 55 89 144 ...

F

1

= 1 ;

F

2

= 1 ;

F

n

= F

n-1

+ F

n-2

dla n > 2

n n

1 1 + 5 1 - 5

F

n

=

5

2 2

94

Na płaszczyźnie jest danych n okręgów.

Jaka jest maksymalna liczba obszarów, na które dzielą one

płaszczyznę?

Wyprowadź

rozwiązanie

w

postaci

odpowiedniej

zależności

rekurencyjnej.

1

2

1

2

4

3

1 = 2

0

1 + 1 = 2 = 2

1

1 + 2 + 1 = 4 = 2

2

1 + 3 + 3 + 1 = 8

= 2

3

95

n n
 =
2

n

i=0 i

a = b =
1

n

n

n

n

2

n

=

+ + ... +

+

0

1

n-1

n

1 + 4 + 6 + 4 + 1 = 16 = 2

4

4 n
 =
2

4

i=0 i

n

n

n

n n

2

n

=

+ + ... + + = (a +

b)

0

1

n-1

n

96

97

a

n

= 4a

n-1

+ 3

; a

0

= 3

;;

a

n

= 4

n+1

-1 ;; a

n

=

42

2n

-1

a

0

= 3, a

1

= 15, a

2

= 63, . . .

a

n

= 4a

n-1

+ 3

a

n

= 4(4a

n-2

+ 3) + 3 = 4

2

a

n-2

+ 4

1

3 + 4

0

3

a

n

= 4(4(4a

n-3

+ 3) + 3) + 3 = 4

3

a

n-3

+ 4

2

3 + 4

1

3

+ 4

0

3

……………………………………………

a

n

= 4

n

a

0

+ 4

n-1

3 + …+ 4

2

3 + 4

1

3 + 4

0

3

a

n

= 3(4

n

+ 4

n-1

+ …+ 4

2

+ 4

1

+ 4

0

) = 3(1-4

n+1

)/(1-4) =

4

n+1

-1

Zależności rekurencyjne

– wzory jawne

Metoda przez podstawianie

Przykład

a

1

, a

2

, a

3

,...,a

i

, a

i+1

,... ;

1 , 2 , 3 , 7 ,15 ,

31, . ...

a

1

=1 a

n

= 2 a

n-1

+ 1

n>1 ; a

n

= 2

n

– 1 ;

n>1

a

n

= 2 a

n-1

+ 1 = 2(2 a

n-2

+ 1) + 1 = 2

2

a

n-2

+ 2 + 1 =

= 2

2

(2 a

n-3

+ 1) + 2 + 1 = 2

3

a

n-3

+ 2

2

+ 2

1

+ 2

0

=

. . .

= 2

k

a

n-k

+ 2

k-1

+ 2

k-2

+ ... + 2

2

+ 2

1

+ 2

0

=

= 2

n-1

+ 2

n-2

+ ... + 2

2

+ 2

1

+ 2

0

= 2

n

– 1

98

Suma wyrazów postępu geometrycznego

a

1

, a

2

, a

3

,...,a

i

, a

i+1

,... ; .q = a

i+1

/a

i

1 - q

n

S = a

1

1 - q

2

n-1

+ 2

n-2

+ ... + 2

2

+ 2

1

+ 2

0

= 2

n

– 1

a

n

+ a

n-1

+ ...+ a

3

+a

2

+ a

1

Ponieważ

q = 2

i+1

/2

i

= 2

i

a

1

= 1

zatem

S

n

= (1-2

n

)/(1-2) = - (1-2

n

) = 2

n

-1

Sprawdzenie:

n

a

n

= 2 a

n-1

+ 1

a

n

= 2

n

- 1

1

1

1

2

2*1 + 1 = 3

2

2

– 1 = 3

3

2*3 + 1 = 7

2

3

– 1 = 7

4

2*7 + 1 = 15 2

4

– 1 = 15

5

2*15 + 1 = 31

2

5

– 1 = 31

99

Przykład

Dana jest zależność rekurencyjna

f(n) = f(n-1) + 3

n

;

n > 1 ; f(1) = 3

Wyznacz postać analityczną

f(n) = f(n-1) + 3

n

;

n > 1 ; f(1) = 3

f(n) = f(n-1) + 3

n

= (f(n-2) + 3

n-1

) + 3

n

=

= ((f(n-3) + 3

n-2

) + 3

n-1

) + 3

n

=

= . . .=

= 3

1

+ 3

2

+ 3

3

+ 3

4

+ . . . + 3

n-1

+ 3

n

Ponieważ kolejny wyraz f(n) jest sumą postępu arytmetycznego

1 - q

n

S =

 a

1

1 - q

100

q = f(i+1)/f(i) = 3

i+1

/3

i

= 3

, a

1

= 3

Zatem

f(n) = (1- 3

n

)/(1-3)*3 = 3/2(3

n

– 1)

Sprawdzenie

n

f(n) = f(n-1) + 3

n

f(n) = 3/2(3

n

– 1)

1

3

3

2

3 + 3

2

= 12

3/2(3

2

– 1) = 3/2(8) = 12

3

12 + 3

3

= 39

3/2(3

3

– 1) = 3/2(26) = 39

4

39 + 3

4

3/2(3

4

– 1)

101

Metoda równania charakterystycznego

Rozważmy ciągi postaci:

s

n

= a*s

n-1

+ b*s

n-2

. a , b - stałe

Przypadek a)

a = 0 lub b = 0

;

znane są wartości s

0

i s

1

Jeżeli b = 0 to s

n

= a*s

n-1

dla n  1.

Zatem s

1

= as

0

, s

2

= as

1

= a

2

s

o

,...

Ostatecznie

s

n

= a

n

s

o

Przykład

s

n

= 3s

n-1

, gdzie s

0

= 5

;

5, 15, 45, …

ponieważ a = 3 zatem ostatecznie s

n

= 3

n

5

;5, 15,

45, …

102

Metoda równania charakterystycznego

Rozważmy ciągi postaci:

s

n

= a*s

n-1

+ b*s

n-2

. a , b - stałe

Jeżeli a = 0 to s

n

= b*s

n-2

dla n  2.

Zatem s

2

= bs

0

, s

4

= bs

2

= b

2

s

o

,...

Ostatecznie

s

2n

= b

n

s

o

dla

n  N

Podobnie

s

3

= bs

1

, s

5

= bs

3

= b

2

s

1

,...

Ostatecznie

s

2n+1

= b

n

s

1

dla

n  N

Przykład

s

n

= 3s

n-2

,

gdzie s

0

= 5 i s

1

= 2 ,

Ostatecznie s

2n

= 3

n

5

i

s

2n+1

= 3

n

2

103

Przykład

s

n

= 3s

n-2

,

gdzie s

0

= 5 i s

1

= 2 ,

Ostatecznie s

2n

= 3

n

5

i

s

2n+1

= 3

n

2

Sprawdzenie:

n

s

n

= 3s

n-2

s

2n

= 3

n

5

, s

2n+1

= 3

n

2

0

5

5

2n = 0



n = 0

1

2

2

2n+1 = 1  n = 0

2

15 15

2n = 2



n = 1

3

6

6

2n+1 = 3  n = 1

4

45 45

2n = 4



n = 2

5

18

18

2n+1 = 5  n = 2

… … … …

… …

104

Przypadek b)

a  0 lub b 0

; znane są wartości s

0

i s

1

Znana jest zależność

s

n

= a*s

n-1

+ b*s

n-2

; a , b - stałe

Rozważmy równanie charakterystyczne

x

2

– a*x – b = 0

F

n

= F

n-1

+ F

n-2

równanie jednorodne

x

n

= x

n-1

+ x

n-2

równanie charakterystyczne

x

n

= x

n-1

+ x

n-2

/ x

n-2

x

2

= x+ 1

F

n

= A x

1

n

+ B x

2

n

ogólna postać rozwiązania

Rozważmy równanie charakterystyczne

x

2

– a*x – b = 0

105

W sytuacji gdy równanie to ma dwa różne rozwiązania r

1

i r

2

wówczas

s

n

= c

1

 r

1

n

+ c

2

 r

2

n

Gdy s

o

i s

1

są dane wówczas przez podstawienie n = 0 i n = 1 wyznaczyć

można c

1

i c

2

.

W sytuacji gdy równanie to ma tylko jedno rozwiązanie r

wówczas

s

n

= c

1

 r

n

+ c

2

 n  r

n

Gdy s

o

i s

1

są dane wówczas przez podstawienie n = 0 i n = 1 wyznaczyć

można c

1

i c

2

.

Rozważmy równanie charakterystyczne

x

2

– a  x – b = 0

106

Przykład

s

n

= s

n-1

+ 2 s

n-2

;

s

0

= s

1

= 3

równanie charakterystyczne ma postać x

2

– a*x – b = 0 zatem

x

2

–x – 2 = 0

 = b

2

– 4ac = 1 +8 = 9 ; x

1

= (-b + )/2a = (1 + 3)/2 = 2 . x

2

= -1

Postać poszukiwana:

s

n

= c

1

r

1

n

+ c

2

r

2

n

Zatem s

n

= c

1

2

n

+ c

2

(-1)

n

Wiadomo, że s

0

= s

1

= 3

Wyznaczane są: c

1

i c

2

Dla n = 0

s

n

= c

1

2

0

+ c

2

(-1)

0

= c

1

+ c

2

= 3

Dla n = 1

s

n

= c

1

2

1

+ c

2

(-1)

1

= 2c

1

- c

2

= 3

3c

1

= 6 ,

c

1

= 2 , c

2

= 1

Ostatecznie s

n

= 2*2

n

+ (-1)

n

107

Sprawdzenie

n

s

n

= s

n-1

+ 2 s

n-

2

s

n

= 2*2

n

+ (-1)

n

0

3

2*2

0

+ (-1)

0

= 3

1

3

2*2

1

+ (-1)

1

= 3

2

3 + 2*3

2*2

2

+ (-1)

2

= 9

3

9 + 2*3

2*2

3

+ (-1)

3

= 15

4

15 + 2*9

2*2

4

+ (-1)

4

Przykład

s

n

= 4s

n-1

– 4s

n-2

, n  2 ;

s

0

= 1 , s

1

= 8

równanie charakterystyczne ma postać x

2

– ax – b = 0 zatem

x

2

–4x + 4 = 0

 = b

2

– 4ac = 16 - 16 = 0 ; x

1

= x

2

= 4/2 = 2

Postać poszukiwana s

n

= c

1

r

n

+ c

2

nr

n

, a dokładniej

s

n

= c

1

2

n

+ c

2

n2

n

108

Wyznaczane są: c

1

i c

2

Dla n = 0

s

n

= c

1

2

0

+ c

2

*0*2

0

= c

1

= 1

Dla n = 1

s

n

= c

1

2

1

+ c

2

*1*2

1

= 2c

1

+ 2c

2

= 8

c

1

= 1 , c

2

= 3

Ostatecznie s

n

= 2

n

+ 3*n*2

n

Sprawdzenie

n

s

n

= 4s

n-1

– 4s

n-2

s

n

= 2

n

+ 3*n*2

n

0

1

2

0

+ 3*0*2

0

= 1

1

8

2

1

+ 3*1*2

1

= 8

2

4*8 - 4*1

2

2

+ 3*2*2

2

= 28

3

4*28 - 4*8

2

3

+ 3*3*2

3

109

Kongruencje

x  y (mod m)

kongruencja

;

m - moduł

6  1 (mod 5)

;

12  2 (mod 5) ;

14  4 (mod 5)

Kongruencje nie zmieniają swoich właściwości przy obustronnym

podnoszeniu do potęgi (pierwiastkowaniu) oraz przy mnożeniu i

dzieleniu przez inne kongruencje

6  1 (mod 5) / 6

36  6 (mod 5)  1 (mod 5)

6  1 (mod 5) / * (12  2 (mod 5))

72  2 (mod 5)

110

Zastosowania

Wyznacz największe x  3

15

podzielne przez

17

3

3

= 27  10 (mod 17)

27  10 (mod 17) / * 27  10 (mod 17)

3

6

 100 (mod 17)  15 (mod 17)

3

6

 15 (mod 17) / * 3

6

 15 (mod 17)

3

12

 225 (mod 17)  4 (mod 17)

3

12

 4 (mod 17) / *3

3

 10 (mod 17)

3

15

 40 (mod 17)  6 (mod 17)

Zatem

3

15

– 6  0 (mod 17) bo 0 (mod 17)  17 (mod 17)  34 (mod 17),

itd

x = 3

15

– 6

111

Na jaką cyfrę kończy się liczba 2

100

?

2

10

 4 (mod 10)

1024  4 (mod 10)

2

10

 4 (mod 10) /

2

2

20

 16 (mod 10)  6 (mod 10)

2

20

 6 (mod 10) /

2

2

40

 36 (mod 10)  6 (mod 10)

2

40

 6 (mod 10) /

2

2

80

 36 (mod 10)  6 (mod 10

2

80

 6 (mod 10) / (2

20

 6 (mod 10) )

2

100

 36 (mod 10)  6 (mod 10)

2

100

 6 (mod 10)

Zatem 2

100

kończy się cyfrą 6.

112

Schemat Hornera

Dana jest reprezentacja liczby M w systemie przy podstawie a.

Oblicz jej dziesiętną postać.

M = r

k

a

k

+ r

k-1

a

k-1

+ r

k-2

a

k-2

+ ...+ r

1

a

1

+ r

0

M = (r

k

a

k-1

+ r

k-1

a

k-2

+ r

k-2

a

k-1

+ ...+ r

1

)a

1

+ r

0

M = ((r

k

a

k-1

+ r

k-1

a

k-2

+ r

k-2

a

k-1

+ ...+ r

2

)a+ r

1

)a + r

0

M = (...((r

k

a+ r

k-1

)a

+ r

k-2

)a + ...+ r

1

)a + r

0

Przykład

M = (45)

10

= (101101)

2

= 1  2

5

+ 0  2

4

+ 1  2

3

+1  2

2

+ 0  2

1

+ 1

 2

0

1  2

5

+ 0  2

4

+ 1  2

3

+1  2

2

+ 0  2

1

+ 1  2

0

= 1  2

5

+ 1  2

3

+1 

2

2

+ 1  2

0

=

= 100000 + 1000 + 100 + 1 = 101101

(101101)

2

=

= ((((1  2

+ 0)  2

+ 1)  2

+1)  2 + 0)  2+

1 = ((((1  2

)2

+1)2

+1)2)2+

1 =

= (((5) 2 +1)2)2+1 =

= ((11)2)2+1 = 44 + 1 = 45

113

Zastosowanie

Najszybszy sposób obliczania potęgi x

n

. Niech n = 45.

Zatem x

45

= x

((((1*2 + 0)2 + 1)2 +1)2 + 0)2+ 1

= (((((x

2

)

2

x)

2

)x)

2

)

2

x

Bo x*x = x

2

;

x

2

x

2

= x

2+2

;

(x

2

)

3

= x

2*3

Sprawdzenie

x

((((1*2 + 0)2 + 1)2 +1)2 + 0)2+ 1

= (x

((((1*2 + 0)2 + 1)2 +1)2 + 0)2

)x =

= (x

(((1*2 + 0)2 + 1)2 +1)2

)

2

x =

= ((x

((1*2 + 0)2 + 1)2 +1

)

2

)

2

x =

= (((x

((1*2 + 0)2 + 1)2

)x)

2

)

2

x =

= (((((x

(1*2 + 0)2

)x)

2

)x)

2

)

2

x =

= (((((x

(1*2 + 0)

)

2

x)

2

)x)

2

)

2

x =

= (((((x

(1*2)

)

2

x)

2

)x)

2

)

2

x =

= (((((x

2

)

2

x)

2

)x)

2

)

2

x

114

Przykład

X

22

= X

16

X

4

X

2

bo 22 = 2

4

+ 2

2

+ 2

1

= 16 + 4 + 2

X

22

= (X

8

X

2

)

2

X

2

X

22

= ((X

2

)

4

X

2

)

2

X

2

115

W Y K Ł A D - 5

Elementy teorii grafów

• relacje,

• grafy (symetryczne i skierowane),

• drogi, cykle, rodzaje grafów: drzewa, dwudzielne, pełne,

• macierzowe reprezentacje grafów,

• grafy Eulera i Hamiltona, grafy płaskie

(Wilson R.J., Wprowadzenie do teorii grafów, PWN, Warszawa, 1998. Ross K.A., Wright C.R.B.,

Matematyka

dyskretna, PWN, Warszawa 1996. N. Deo, Teoria grafów i jej zastosowania w technice i

informatyce. PWN,

Warszawa 1980.)

Relacje

R

- relacja dwuargumentowa na zbiorze

S

x

T

R  S

x

T

Przykład
S = {1,2,3}, T = {a, b} , S x T = {(1,a), (1,b), (2,a), (2,b), (3,a),

(3,b)}

R = S x T = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}

1

2

3

a

b

116

1

2

3

Przykład

S = {1,2,3},

T = {1,2,3} ,

S x T = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3),(3,1),

(3,2), (3,3)}

117

R’ = {(1,2),(1,3),(2,3)}  S x T;

a R’ b  a < b

dla a S, bT

R” = {(1,1),(2,2),(3,3)}  S x T

;

a R” b  a = b dla a S, bT

R’’’ = { }  S x T

;

a R’’’ b  a mod 5 = b mod 5 = 4 mod 5

dla a S, bT

1

2

3

a

b

118

Niech R  S x S

(relacja R w zbiorze S )

Jest zwrotna

(x,x)  R

, x  S

Jest przeciwzwrotna

(x,x)  R

, x S

Jest symetryczna

(x,y)  R  (y,x)  R, x,y S

Jest antysymetryczna

(x,y)  R & (y,x)  R  x = y

Jest przechodnia

(x,y)  R & (y,z)  R  (x,z)  R

119

Przykład

R’ = {(1,2),(1,3),(2,3)}  S x T;

a R’ b  a < b

dla a S, bT

R” = {(1,1),(2,2),(3,3)}  S x T

;

a R” b  a = b dla a S, bT

Jeżeli R  S x T to R^  T x S jest relacja odwrotną

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R =

{(a,a), (b,b),

(c,c), (d,d), (a,b)}. Czy relacja ta jest zwrotna?

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,a),

(b,b),(c,c), (d,d)}. Czy relacja ta jest przechodnia?

Jeżeli dana relacja jest symetryczna, zwrotnia i przechodnia, to jest

relacją

równoważności, na której definiujemy klasy abstrakcji.

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,b),

(b,c),

(a,a)}. Czy relacja ta jest przeciwzwrotna?

Przykład

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,b),

(b,a),(c,c), (d,c), (c,d)}. Czy relacja ta jest symetryczna?

120

Przykład

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,b),

(b,c),

(c,d), (d,a)}. Czy relacja ta jest przeciwsymetryczna?

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,b), (a,c),

(b,a)}.

Czy relacja ta jest spójna?

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,b),

(b,a),(c,c)}. Czy relacja ta jest symetryczna?

Relacja jest spójna, jeżeli

x,y S, x ≠ y  (y,x)  R  (x,y)  R

Relacje < i ≤ są relacjami spójnymi w zbiorze liczb rzeczywistych

121

a

b

c

a

b

c

S = {a,b,c}

;

R’ = {(a,b),(c.b),(a,c)} ;

a

b

c

G R A F Y

Graf

G = (S, R)

Przykład

S = {a,b,c}

;

R = {(a,b),(b,a),(b,c),(c.b),(c,a),(a,c)}

G = (S, R’)

122

A

D

C

B

C

D

B

(1736) Leonard Euler Problem mostów królewieckich

Przejść przez każdy z mostów dokładnie jeden raz i powrócić do punktu
wyjściowego.

A

6

7

2

3

1 8

3 5

4

123

Problem sieci wodnej (W), gazowej (G) i elektrycznej (E). Są trzy domy H

1

,

H

2

i H

3

, z których każdy musi być podłączony przewodami do każdej z

trzech sieci. Czy jest możliwe dokonanie takich połączeń bez skrzyżowania

przewodów?

H

1

H

2

H

3

W

G

E

124

Krawędzie, łuki, wierzchołki, drogi, ścieżki, pętle, kontury, obwody,

cykle, drogi zamknięte.

Ścieżka (droga) elementarna

- nie przecina samej siebie.

Graf spójny

G -

jeżeli istnieje przynajmniej jedna ścieżka (droga)

miedzy

każdą para wierzchołków w G.

Podgraf

G’  G = (X,R) , G’ = (X’,R’); X’  X ; R’  R

Długość drogi – liczba krawędzi drogi.

Stopień wierzchołka

- liczba krawędzi z nim incydentnych.

Graf regularny

– wszystkie wierzchołki sa tego samego stopnia

125

Charakterystyki grafu

n - liczba wierzchołków

e - liczba krawędzi

k - liczba składowych (spójności)

e  n – k

r - rząd grafu

r = n – k

 - zerowość grafu

 = e – n + k

Przykład

Rząd grafu = liczba gałęzi w każdym dendrycie grafu

Zerowość grafu = liczba cięciw w grafie

rząd + zerowość = liczba krawędzi w grafie

126

Izomorfizm

Dwa grafy są izomorficzne jeśli zachodzi wzajemnie jednoznaczna

odpowiedniość między ich wierzchołkami oraz ich krawędziami przy

zachowaniu relacji incydencji.

Grafy izomorficzne muszą mieć:

• tę samą liczbę wierzchołków

• tę samą liczbę krawędzi

• równa liczbę wierzchołków o danym stopniu

Poszukiwane jest kryterium efektywnego obliczeniowo wykrywania
izomorfizmu!

127

I z o m o r f i z
m

N o m e n k l a t u
r a

Dwa grafy G

1

i G

2

są izomorficzne, jeżeli istnieje

wzajemna jednoznaczna odpowiedniość między

wierzchołkami grafu G

1

i wierzchołkami grafu G

2

,

taka że liczba krawędzi łącząca dwa dowolne

wierzchołki w G

1

jest równa liczbie krawędzi

łączących odpowiadające im wierzchołki w G

2

.

128

Grafy dwudzielne, grafy pełne, drzewa

Graf dwudzielny

Graf pełny

Drzewo

Graf dwudzielny

– wierzchołki którego można pokolorować dwoma barwami.

Graf pełny –

każdy wierzchołek którego jest połączony (krawędzią lub łukiem) z

pozostałymi wierzchołkami

Drzewo

– graf spójny bez obwodów (drzewo genealogiczne, rzeka, drzewo

decyzyjne,

itp.)

Właściwości drzewa:

•między każdą parą wierzchołków istnieje tylko jedna droga

•drzewo o n wierzchołkach ma n-1 krawędzi

129

Drzewo binarne

- dokładnie jeden wierzchołek jest stopnia drugiego a

pozostałe stopnia

trzeciego lub pierwszego.

poziom 0

poziom 1

poziom 3

poziom 4

Właściwości drzew binarnych:

- liczba wierzchołków n w drzewie binarnym jest zawsze

nieparzysta.

- liczba krawędzi w drzewie jest równa

p = (n+1)/2,

- p – liczba wierzchołków wiszących

1/2(p + 3(n-p-1)+2) = n-1

- liczba krawędzi w

drzewie

130

Własności drzew (dla grafu T mającego n-wierzchołków):

• T nie zawiera cykli, ilość krawędzi = n-1
• T jest grafem spójnym, każda krawędź jest mostem.
• Każde dwa wierzchołki T połączone są dokładnie jedną drogą.
• T nie zawiera cykli, ale po dodaniu dowolnej nowej krawędzi otrzymujemy graf

z dokładnie jednym cyklem.

Grafy platońskie

131

A

A

A

A

B

D

C

B

D

C

B

D

C

B

D

C

Drzewa o wierzchołkach zaetykietowanych

Liczba drzew zaetykietowanych o n wierzchołkach

(n2)

wynosi

n

n-2

.

A

A

B

D

C

B

D

C

C

A

B

D

132

Łatwo zauważyć, że liczba drzew niezaetykietowanych o czterech
wierzchołkach wynosi 2.

Dendrytem grafu spójnego G nazywamy drzewo będące jego
podgrafem i zawierającym wszystkie wierzchołki grafu G.

Graf niespójny o k składowych ma las dendrytów składający się z k
drzew.

Każdy graf spójny ma przynajmniej jeden dendryt.

Cięciwą nazywamy krawędź grafu G która nie należy do danego
dendrytu.

Przykład

133

REPREZENTACJE MACIERZOWE

Macierz sąsiedztwa A

(n x n)

,

Macierz incydencji M

(n x m)

grafu o n wierzchołkach i m krawędziach

a

i,j

- liczba krawędzi łączących wierzchołek „i” z wierzchołkiem „j”

m

i,j

= 1 jeśli i-ty wierzchołek jest incydenty z j-tą krawędzią

3 b
4

1 a
2

c d
e

m

i,j

= 0 w przeciwnym wypadku

1 2 3

4

1

0 1

1 0

2

1 0

1 1

A =

3

1 1 0 1

4

0 1 1 0

a b

c d e

1

1 0 1 0 0

2

1 0 0 1 1

M =

3

1 1 1 0 0

4

0 1 0 0 1

134

Grafy Eulera (przechodzenie przez krawędzie)

Grafem Eulera nazywamy graf składający się z drogi Eulera.

Drogą Eulera nazywamy drogę zamknięta przechodzącą dokładnie jeden raz
przez każdą krawędź z grafu G.

Graf jest grafem Eulera wtedy i tylko wtedy gdy wszystkie wierzchołki G są
stopnia parzystego.

A

D

C

B

Graf spójny mający dokładnie dwa wierzchołki
stopnia

nieparzystego, ma drogę Eulera

.

135

Obwód Hamiltona (przechodzenie przez wierzchołki)

Obwodem Hamiltona w grafie spójnym jest droga zamknięta. Która przechodzi

przez każdy wierzchołek grafu G dokładnie jeden raz.

Obwód Hamiltona w grafie o n wierzchołkach składa się z n
krawędzi.

Problem komiwojażera.

Całkowita liczba różnych obwodów

Hamiltona w grafie pełnym o n wierzchołkach:
(n-1)/2!

136

Grafy planarne

Graf planarny to graf który można narysować na płaszczyźnie bez przecięć – to

znaczy tak aby, żadne dwie krawędzie nie przecinały się na rysunku poza

wierzchołkiem z którym są incydentne.

Grafy

K

3,3

i

K

5

są nieplanarne.

Dany graf G jest planarny wtedy i tylko wtedy gdy nie zawiera

podgrafu homeomorficznego z grafem K

3,3

i K

5

.

137

Dany graf G jest planarny wtedy i tylko wtedy gdy jest ściągalny

do podgrafu K

3,3

lub do podgrafu K

5

.

Problem
kolorowania

Shell

Esso

Gulf

BP

Shell

lub

Gulf

Graf jest k - kolorowalny jeżeli każdemu wierzchołkowi można przypisać jeden z k

kolorów, w taki sposób że żadne dwa wierzchołki sąsiednie nie mają tego samego

koloru.

138

W Y K Ł A D - 6

Elementy teorii grafów

• przeszukiwanie grafów

• algorytmy na grafach (zadania najkrótszych dróg): algorytm Fleury’go,
algorytm Kruskala, algorytm
Prima, algorytm Dijkstry
(Ross K.A., Wright C.R.B., Matematyka dyskretna, PWN, Warszawa 1996.)

Problem wyznaczania najkrótszej trasy: znaleźć taka ścieżkę, prowadzącą od węzła i

do węzła j, by suma wartości przebywanych połączeń była jak najmniejsza. Wyznacz

najkrótsza ścieżkę łączącą węzły A i J.

PRZESZUKIWANIE GRAFÓW (metoda podziału i ograniczeń)

Dane są naczynia o pojemności odpowiednio 4 i 3 litra. Czy można z ich pomocą

odmierzyć pojemność 2 litrów? Wszystko to przy założeniu, że naczynia te nie są

cechowane, a możliwe działania obejmują nalewanie do pełna (bądź opróżnianie)

lub przelewanie z jednego naczynia do drugiego.

A

J

139

Algorytm Dijkstry

Jaka jest długość najkrótszej drogi łączącej dwa wierzchołki w danym

grafie skierowanym?

Jeśli graf skierowany ma wagi, to jaka jest waga minimalna lub

maksymalna takiej drogi?

Przykład

v

2

7

v

4

2

v

6

3 7 9

v

1

2 5 4

9

1 8

v

3

4 v

5

v

7

140

ALGORYTMY NA GRAFACH

Algorytm Fleury’go

(wyznaczanie drogi Eulera)

Niech ES – ciąg krawędzi drogi lub cyklu Eulera, VS – ciąg wierzchołków tej

drogi lub cyklu. Niech V(G) – zbiór wierzchołków, a E(G) – zbiór krawędzi

grafu G

1. Wybierz dowolny wierzchołek v nieparzystego stopnia, jeśli taki

istnieje. W przeciwnym przypadku wybierz dowolny wierzchołek v.

Niech VS = v i niech ES = .

2. Jeśli z wierzchołka v nie wychodzi już żadna krawędź, zatrzymaj się.

3. Jeśli pozostała dokładnie jedna krawędź wychodząca z wierzchołka v ,

powiedzmy krawędź e z wierzchołka v do w, to usuń e z E(G) oraz

v z V(G) i przejdź do kroku 5.

4. Jeśli została więcej niż jedna krawędź wychodząca z wierzchołka v ,

wybierz krawędź, powiedzmy e z v do w , po usunięciu której graf

pozostanie spójny, następnie usuń e z E(G).

5. Dołącz w na końcu ciągu VS, dołącz e na końcu ciągu ES, zastąp v

wierzchołkiem w i przejdź do kroku 2.

141

Algorytm Fleury’go (wyznaczanie drogi Eulera)

142

Algorytm Kruskala (minimalne drzewo spinające)

Dane: skończony graf spójny G z wagami, którego krawędzie są uporządkowane

według wzrastających wag.

Wyniki: zbiór E krawędzi minimalnego drzewa spinającego grafu G

Niech E:= .

Dla j = 1 do |E(G)|

Jeśli graf E  {e

j

} jest acykliczny, to dołącz e

j

do E.

Przykład

2

5

3

3

5

5

5

3

4

1

5

2

e

8

e

9

e

7

e

8

e

4

e

5

e

6

e

2

e

1

e

10

e

3

e

11

143

Wagi krawędzi W(e

i

) mają tworzyć ciąg niemalejący, tzn. W(e

i

) < W(e

j

) dla i <

j , zatem:

e

1

2

5

3

3

5

5

5

3

4

1

5

2

e

8

e

9

e

7

e

8

e

4

e

5

e

6

e

2

e

1

e

10

e

3

e

11

e

1

e

2

e

3

e

4

e

5

e

6

e

7

e

8

e

9

e

10

e

11

1 2 2 3 3 4 5 5 5 5 5

e

7

e

3

e

5

e

6

e

2

144

Algorytm Prima (minimalne drzewo spinające)

Dane: skończony graf spójny G z wagami (z krawędziami wypisanymi w

dowolnym porządku)

Wyniki: zbiór E krawędzi minimalnego drzewa spinającego grafu G

Niech E:= .

Wybierz w ze zbioru V(G) i niech V := {w}

Dopóki V  V(G), wykonuj

wybierz w zbiorze E(G) krawędź (u,v) o najmniejszej możliwej wadze, taką że

u  V i

v  V(G) \ V dołącz krawędź (u,v) do zbioru E i wierzchołek v do zbioru V.

2

b

3 1

d e

1

c

2

1

4

5

4

3

a

Algorytmy Prima i Kruskala są algorytmami zachłannymi, tzn.
algorytmami wybierającymi zawsze najmniejszą krawędź, która
należy dodać lub największą krawędź, którą należy odrzucić.

Przykład

145