Matematyka Dyskretna

Władysław Skarbek

Państwowa Wyższa Szkoła Informatyki i Zarządzania

Październik 2004 – Styczeń 2005

Spis treści

Zbiory

1.1 Zbiory a typy danych . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Elementy i podzbiory . . . . . . . . . . . . . . . . . . . . . . . . .

1.3 Deﬁniowanie zbioru – notacja . . . . . . . . . . . . . . . . . . . .

1.4 Paradoks Russela . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.5 Operacje mnogościowe . . . . . . . . . . . . . . . . . . . . . . . .

1.6 Arytmetyczne typy danych . . . . . . . . . . . . . . . . . . . . .

1.7 Zbiór potęgowy a kombinacje i permutacje . . . . . . . . . . . . .

1.8 Produkt kartezjański . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.9 Relacje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.10 Funkcje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.11 Złożony typ danych a produkt kartezjański . . . . . . . . . . . . 15
1.12 Generalizacja typów danych . . . . . . . . . . . . . . . . . . . . . 16
1.13 Atrybuty i cechy . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.14 Tabela relacyjna . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.15 Ciągi i macierze . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.16 Diagramy relacyjne w UML . . . . . . . . . . . . . . . . . . . . . 20

Algebry

2.1 Intuicje informacyjne algebry . . . . . . . . . . . . . . . . . . . . 22
2.2 Deﬁnicja algebry ogólnej . . . . . . . . . . . . . . . . . . . . . . . 22

2.2.1 Algebry a klasy obiektów . . . . . . . . . . . . . . . . . . 23
2.2.2 Diagramy klas w UML . . . . . . . . . . . . . . . . . . . . 23

2.3 Algebra Boole’a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Układy zupełne funkcji Boole’a . . . . . . . . . . . . . . . . . . . 27
2.5 Własności algebry Boole’a . . . . . . . . . . . . . . . . . . . . . . 29
2.6 Mapa Karnaugh . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.7 Rachunek zdań . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.7.1 Spójniki logiczne . . . . . . . . . . . . . . . . . . . . . . . 31
2.7.2 Wyrażenia logiczne . . . . . . . . . . . . . . . . . . . . . . 32
2.7.3 Wyrażenia logiczne a zbiory . . . . . . . . . . . . . . . . . 34

2.7.4 Łamigłówka króla . . . . . . . . . . . . . . . . . . . . . . . 35

2.8 Rachunek predykatów i kwantyﬁkatorów . . . . . . . . . . . . . . 36

2.8.1 Predykaty . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.8.2 Kwantyﬁkatory . . . . . . . . . . . . . . . . . . . . . . . . 38

2.9 Homomorﬁzm algebr . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.10 Rachunek reszt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.11 Arytmetyka cyfrowa w stałym przecinku . . . . . . . . . . . . . . 45
2.12 Arytmetyka cyfrowa w zmiennym przecinku . . . . . . . . . . . . 46

2.12.1 Wzorce bitowe w IEEE 754 . . . . . . . . . . . . . . . . . 50

Schematy rekurencyjne

3.1 Wieże Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2 Konwersja wyrażenia arytmetycznego na ONP . . . . . . . . . . 55
3.3 Generowanie kodu maszynowego wyrażenia arytmetycznego . . . 58
3.4 Klasyczna indukcja matematyczna . . . . . . . . . . . . . . . . . 60

3.4.1 Indukcja matematyczna – wybrane przykłady . . . . . . . 61
3.4.2 Obliczanie sum metodą różnic . . . . . . . . . . . . . . . . 65

3.5 Równania rekurencyjne . . . . . . . . . . . . . . . . . . . . . . . 66
3.6 Zliczanie obiektów kombinatorycznych . . . . . . . . . . . . . . . 72

3.6.1 Współczynniki dwumienne . . . . . . . . . . . . . . . . . 72
3.6.2 Własności liczbowe zbiorów i funkcji . . . . . . . . . . . . 75
3.6.3 Zasada włączania i wyłączania . . . . . . . . . . . . . . . 75
3.6.4 Podziały . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.6.5 Zbiory z powtórzeniami . . . . . . . . . . . . . . . . . . . 77
3.6.6 Zliczanie drzew binarnych . . . . . . . . . . . . . . . . . . 78

Kongruencje

4.1 Podzielność liczb całkowitych . . . . . . . . . . . . . . . . . . . . 81

4.2 Algebra reszt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

4.2.1 Równania w resztach . . . . . . . . . . . . . . . . . . . . . 98
4.2.2 Chińskie twierdzenie o resztach . . . . . . . . . . . . . . . 99
4.2.3 Twierdzenia Fermata o resztach . . . . . . . . . . . . . . 101
4.2.4 Funkcja Eulera . . . . . . . . . . . . . . . . . . . . . . . . 102
4.2.5 Twierdzenie Eulera o resztach . . . . . . . . . . . . . . . . 103
4.2.6 Szyfrowanie – algorytm RSA . . . . . . . . . . . . . . . . 104

Przedmowa

Matematyka dyskretna w ujęciu tego wykładu ma na celu wprowadzenie koncep-
cji matematycznych leżących u podstaw takich obszarów wiedzy informatycznej
jak języki i techniki programowania, układy logiczne i arytmetyczne maszyn
cyfrowych oraz algorytmy szyfrowania danych.
Zaczynamy od pojęcia zbioru i szeregu pochodnych pojęć mnogościowych, które
ściśle wiążą się z koncepcję typu danych, atrybutu obiektu w systemie informa-
cyjnym, tabeli w relacyjnej bazie danych oraz instancji obiektu danego typu.
Kolejnym prezentowanym obszarem są algebry i ich związek z projektowaniem
jednostek arytmetycznych i logicznych w maszynach cyfrowych, z koncepcją
klasy obiektów i algebraicznym modelem programu komputerowego.
Rozdział poświęcony schematom rekurencyjnym omawia indukcyjne techniki
deﬁniowania obiektów matematycznych. Obejmuje on szereg przykładów za-
stosowania koncepcji rekursji w przyrostowym deﬁniowaniu złożonych struktur
danych i algorytmów działających na nich.
Wykład zamyka dyskusja zastosowań rachunku reszt w kryptograﬁi. Przedsta-
wiono wybrane algorytmy szyfrowania danych wraz z ich teoretycznymi podsta-
wami.

Zbiory

• Zbiór jest pojęciem pierwotnym

⇒

”ten typ tak ma”

• Przykład zbioru: księgozbiór Polskiej Biblioteki Narodowej

• Intuicje zbioru:

–

Zbiór to kolekcja, zestaw elementów

–

Specyﬁczna własność wyróżnia elementy

–

Elementy należą do pewnego uniwersum

–

Zbiór jest podzbiorem pewnego uniwersum

1.1

Zbiory a typy danych

• Intuicje informatyczne:

–

Książka to złożony typ danych

–

Konkretny egzemplarz Pana Tadeusza w księgozbiorze to instancja
typu Książka

–

Ten konkretny egzemplarz należy do zbioru wszystkich instancji typu
Książka

–

Księgozbiór to specyﬁczna Kolekcja

–

Księgozbiór Biblioteki Narodowej to instancja typu Księgozbiór

• Wnioski:

–

Typ danych nie jest zbiorem

–

Typ danych T określa własność instancja danych jest typu T

–

Własność instancja danych jest typu T deﬁniuje zbiór wszystkich
instancji typu T

Ćwiczenia

1. Podaj przykładowe atrybuty obiektu typu Książka.

2. Typ Kolekcja jest generalizacją typu Księgozbiór. Jakich atrybutów typu

Księgozbiór nie posiada Kolekcja ?

3. Określ typ danych, którego zbiór wszystkich instancji jest zbiorem wszyst-

kich danych osobowych studentów PWSIiP.

1.2

Elementy i podzbiory

•

∈ – przynależność, np.:

–

∈ X – x jest elementem zbioru X

–

y /

∈ X – y nie jest elementem zbioru X

•

⊂, ⊃ – podzbiór, nadzbiór, np.:

–

⊂ B – A jest podzbiorem zbioru B

–

⊃ A – B jest nadzbiorem zbioru A

• (, ) – podzbiór, nadzbiór właściwy, np.:

–

A ( B – A jest podzbiorem właściwym zbioru B

–

B ) A – B jest nadzbiorem właściwym zbioru A

• = – równość,

6= – różność np.:

–

A = B – zbiory A i B są identyczne

–

6= B – zbiory A i B są różne

⇒

Skrót: wtt – wtedy i tylko wtedy

Ćwiczenia
Uzasadnij następujące własności inkluzji:

1. A ⊂ B wtt A ( B lub A = B.

2. Jeśli A ( B, to A 6= B.

3. A ⊂ A.

4. Jeśli A ⊂ B i B ⊂ C, to A ⊂ C.

1.3

Deﬁniowanie zbioru – notacja

•

∅ – zbiór pusty

•

{·, . . . , ·} – wyliczenie elementów zbioru, np.:

–

A =

{1, 2, 3, 4, 5, 6} – zbiór składa się z liczb całkowitych od 1 do 6

–

B =

{1, 2, . . . , 12} – zbiór liczb naturalnych od 1 do 12

– N

, {1, 2, 3, . . . } – zbiór liczb naturalnych

– Z

, {0, ±1, ±2, ±3, . . .} – zbiór liczb całkowitych

•

{x : W (x)} – zbiór tych x, które spełniają warunek W (x), np.:

– ZP

, {x : x ∈ Z, 2 dzieli x} – zbiór liczb całkowitych parzystych

–

, {x : x =

p
q

gdzie q ∈ N, p ∈ Z} – zbiór liczb wymiernych

– R

= {x : x ∈ Q lub jest granicą ciągu liczb wymiernych } – zbiór

liczb rzeczywistych

Ćwiczenia

1. Zapisz własność deﬁnicyjną zbioru liczb pierwszych.

2. Czy każda liczba rzeczywista o skończonym dziesiętnym zapisie pozycyj-

nym jest liczbą wymierną ?

3. Podaj przykład liczby wymiernej, której nie można zapisać skończoną licz-

bą cyfr dziesiętnych.

Zadania

1. Podaj przykład liczby wymiernej, która w zapisie dziesiętnym ma skoń-

czoną liczbę cyfr, a w zapisie dwójkowym nie ma skończonego zapisu.

2. Dla liczby rzeczywistej x = 0, b

, b

, . . . podaj ciąg liczb wymiernych zbież-

ny do x.

1.4

Paradoks Russela

• Niech U będzie zbiorem wszystkich zbiorów

• Własność: U jest własnym elementem

• Rozważmy zbiór S, który jest zbiorem wszystkich zbiorów nie będących

własnym elementem:

, {Z : Z /∈ Z}

• Pytania:

1. Czy S ∈ S ?
2. Czy S /

∈ S ?

• Paradoks:

1. Jeśli S ∈ S, to S /∈ S
2. Jeśli S /

∈ S, to S ∈ S

• Własność deﬁnicyjna zbioru S jest sprzeczna

• Paradoks fryzjera:

W pewnej jednostce wojskowej jest fryzjer, który goli wszystkich tych
mężczyzn w jednostce, którzy się sami nie golą. Czy on się sam goli ?

• Paradoks kłamcy:

Pewien osobnik zawsze kłamie. Pewnego dnia wygłosił on sentencję Ja
zawsze kłamię. Czy tym razem skłamał ?

Ćwiczenie
Niech S będzie zbiorem określonym w paradoksie Russela.

• Dlaczego z tego, że S

∈ S wynika S /

∈ S ?

• Dlaczego z tego, że S /

∈ S wynika S ∈ S ?

Zadania

• Wyjaśnij na czym polega paradoks fryzjera

• Wyjaśnij na czym polega paradoks kłamcy

1.5

Operacje mnogościowe

•

∪, ∩, − operacje sumy, iloczynu i różnicy dwóch zbiorów, np.:

–

∪ B – suma zbiorów A i B

–

∩ B – iloczyn zbiorów A i B

–

− B – różnica zbiorów A i B

•

| · | – liczność zbioru, np.:

–

|A| = n – zbiór A ma n elementów

–

|A ∪ B| – liczność sumy zbiorów A i B

• suma n zbiorów:

[

i=1

, A

∪ · · · ∪ A

• iloczyn n zbiorów:

i=1

, A

∩ · · · ∩ A

Zadania
Niech A , U − A. Uzasadnij następujące własności operacji mnogościowych:

1. przemienność: A ∪ B = B ∪ A, A ∩ B = B ∩ A

2. łączność: (A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C)

3. rozdzielczość: (A∪B)∩C = (A∩C)∪(B∩C), (A∩B)∪C = (A∪C)∩(B∪C)

4. prawa de’Morgana: A ∪ B = A ∩ B, A ∩ B = A ∪ B

1.6

Arytmetyczne typy danych

• Typ arytmetyczny w języku programowania określa liczbowy zbiór możli-

wych wartości (instancji) zmiennych deﬁniowanych w programie

• Przykład z języka C: deklaracja

int k;

mówi,że zmienna k ma wartości typu całkowitego

• Uwagi:

–

Zmienna całkowita w realizacji komputerowej ma skończony zbiór
wartości

–

Kodowanie wartości całkowitej ustalone jest przez model jednostki
arytmetyczno-logicznej ALU (ang. Arithmetic-Logic Unit) – zwykle
jest to kod uzupełniający do dwóch (ang. 2’s complement)

• Zapis x

∈ Z w matematyce oznacza, że x może przyjąć dowolną całkowitą

wartość liczbową

• Deklaracja int k; w języku C oznacza, że w programie komputerowym k

może przyjmować wartości z podzbioru liczb całkowitych I

kodowanego

na 32 bitach, gdzie

, {i ∈ Z : −2

−1

≤ i < 2

−1

}

• unsigned int k; ogranicza wartości zmiennej k do podzbioru liczb na-

turalnych I

kodowanego na 32 bitach, gdzie

, {i ∈ Z : 0 ≤ i < 2

}

• Deklaracje

float f; double d;

mówią, że zmienne f,d mają wartości typu rzeczywistego

• Uwagi:

–

Zmienna rzeczywista w realizacji komputerowej ma skończony zbiór
wartości

–

Kodowanie wartości rzeczywistej odbywa się w reprezentacji o zmien-
nym przecinku z pojedynczą precyzją (deklaracja float) lub podwój-
ną precyzją (deklaracja double) zwykle zgodnie ze standardem ”IE-
EE 774 Floating Point Numbers”

• float f; ogranicza wartości zmiennej f do podzbioru liczb rzeczywistych

32,8

kodowanego na 32 bitach z cechą na 8 bitach, gdzie zgodnie ze stan-

dardem ”IEEE 774 Floating Point Numbers”

32,8

≈

−10

38,53

−10

−44,85

∪ {0} ∪

−44,85

, 10

38,53

• double d; ogranicza wartości zmiennej d do podzbioru liczb rzeczywistych

64,11

kodowanego na 64 bitach z cechą na 11 bitach, gdzie zgodnie ze

standardem ”IEEE 774 Floating Point Numbers”

64,11

≈

−10

308.3

−10

−323.3

∪ {0} ∪

−323.3

, 10

308.3

Ćwiczenia
Uzasadnij dla n ∈ N następujące własności:

1. I

(

n+1

2. I

(

n+1

3. I

(

n+1

Zadania
Pokaż dla dowolnego k ∈ N :

1. Z =

∞

n=k

2. N = {0} ∪

∞

n=k

Problem
Uzasadnij, że każda liczba rzeczywista x 6= 0 da się zapisać jednoznacznie w

notacji naukowej:

x = (

−1)

s(x)

m(x)2

c(x)

gdzie s(x) ∈ {0, 1} – bit znaku, m(x) ∈

1
2

, 1

– mantysa, c(x) ∈ Z – cecha

liczby x.

1.7

Zbiór potęgowy a kombinacje i permutacje

Niech U będzie skończonym uniwersum, n , |U|. Wtedy

• Zbiór 2

, {Z : Z ⊂ U} nazywamy zbiorem potęgowym

• Liczność zbioru potęgowego:

| = 2

|U|

• Jeśli k

∈ {0} ∪ N i 0 ≤ k ≤ n, to k-elementowy podzbiór Z ⊂ U nazy-

wamy k-elementową kombinacją elementów z U. Zbiór takich kombinacji
oznaczamy przez U

, a jego liczność prze c

k,n

• Własności:

–

= {∅}, c

0,n

, |U

| = 1

–

Jeśli k 6= k

′

, to U

∩ U

′

= ∅

–

n
k=0

oraz

n
k=0

k,n

= 2

–

Dla 0 < k ≤ n : c

k,n+1

= c

k,n

+ c

−1,n

• Dowolne uporządkowanie zbioru U nazywamy permutacją tego zbioru

• Własności:

–

Zbiór n-elementowy ma n! różnych permutacji, gdzie n! jest iloczy-
nem liczb od 1 do n :

, 1 · · · · · n

–

Liczba c

k,n

kombinacji k-elementowych ze zbioru n-elementowego dla

k > 0 wynosi

k,n

k!(n

− k)!

Ćwiczenia
Oblicz liczność zbioru potęgowego 2

dla:

1. U = {0, 1}

2. U = {1, 2, 3}

3. U = {1, 2, . . . , n}

Zadania

1. Narysuj trójkąt Pascala dla n = 5.

2. Sprawdź prawdziwość wzoru

k,n

k!(n

− k)!

Problem
Niech U = {1, 2, . . . , n}, n > 2

1. Ile permutacji zbioru U ma jedynkę na pozycji 2 ?

2. Ile permutacji zbioru U ma jedynkę położoną na prawo od dwójki ?

1.8

Produkt kartezjański

Niech A

, A

, . . . , A

będą dowolnymi zbiorami. Wtedy

• (a

, a

) oznacza uporządkowaną parę elementów gdzie a

∈ A

jest pierw-

szą składową pary, zaś a

∈ A

jej drugą składową

• A

× A

, {(a

, a

) : a

∈ A

, a

∈ A

} – produkt kartezjański zbioru A

i zbioru A

• (a

, . . . , a

) oznacza uporządkowaną krotkę elementów gdzie a

∈ A

jest

i-tą składową tej krotki, i = 1, . . . , n

• A

× · · · × A

, {(a

, . . . , a

) : a

∈ A

, . . . a

∈ A

} – produkt kartezjań-

ski zbiorów A

, . . . , A

• Jeśli A

= · · · = A

= A, to produkt kartezjański A × · · · × A oznaczamy

przez A

Ćwiczenia
Niech A = {0, 1}, B = {2, 3}. Wyznacz:

1. C = A × A

2. D = B × B

3. A × B

4. B × A

5. C × D

Zadania
Niech A = [0, 1], B = [1/4, 3/4]

1. Podaj interpretację zbiorów A

oraz A

2. Wyznacz pole zbioru A

− B

3. Wyznacz objętość zbioru A

− B

Problemy

1. Pokaż, że dla dowolnych a, a

′

∈ A, b, b

′

∈ B :

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

′

, b

′

}} wtt a = a

′

oraz b = b

′

Wniosek: Zbiór {a, {a, b}} może być traktowany jako zbiór deﬁnicyjny dla

pary elementów (a, b).

2. Niech A, B, C, D ⊂ U. Podaj warunek dostateczny i konieczny na to by

(A × B) ∪ (C × D) = (A ∪ C) × (B × D)

1.9

Relacje

• Intuicja: Relacja modeluje współwystępowanie dwóch lub więcej elemen-

tów w związkach o dowolnym charakterze

• Przykłady relacji:

–

, {(x, y) : x jest ojcem y}

–

, {(x, y, z) : punkty x, y, z są współliniowe }

–

, {(x, k, p, s) : ocena x z kolokwium k

na przedmiocie p otrzymana przez studenta s}

• Deﬁnicja relacji między elementami zbiorów A

, A

, . . . , A

Zbiór R ⊂ A

× · · · × A

modeluje relację n-argumentową

• Jeśli n = 2, to relacja jest nazywana relacją binarną. Wtedy zamiast

, a

) ∈ R piszemy a

• Relacja binarna może być reprezentowana graﬁcznie:

jeśli a

, to z wierzchołka o etykiecie a

prowadzimy gałąź do wierz-

chołka o etykiecie a

i z grotem wskazującym na niego.

• Relacja odwrotna R

−1

do relacji binarnej R ⊂ A

× A

−1

, {(a

, a

) : (a

, a

) ∈ R}

• Dziedzina relacji binarnej R

⊂ A

× A

, {a

∈ A

: a

dla pewnego a

∈ A

}

• Przeciw-dziedzina relacji binarnej R

⊂ A

× A

−1

, {a

∈ A

: a

dla pewnego a

∈ A

}

• Własność: D

−1

= D

−1

• Deﬁnicje:

–

Relacja binarna jest zwrotna wtt aRa dla wszystkich a ∈ D

–

Relacja binarna jest symetryczna wtt (aRb wtt bRa)

–

Relacja binarna jest przechodnia wtt aRb i bRc implikuje aRc

–

Relacja binarna zwrotna, symetryczna i przechodnia nazywa się re-
lację równoważności

• Niech [x]

, {y ∈ A : xRy} będzie tzw. klasą równoważności relacji

równoważności R o dziedzinie A. Wtedy

–

xRy wtt [x]

= [y]

–

dla dowolnych x, y ∈ A : [x]

= [y]

lub [x]

∪ [y]

= ∅

• Zbiór wszystkich klas równoważności relacji R w zbiorze A oznaczamy

przez A/R.

Ćwiczenia

1. Określ zbiory A, B, C, D, w produktach kartezjańskich których określono

następujące relacje:

(a) A × B ⊃ R

, {(x, y) : x jest synem y}

(b) A × B × C ⊃ R

, {(x, y, z) : punkty x, y, z nie są współliniowe }

, {(x, a, p, s) : ocena x wystawiona przez asystenta a

na przedmiocie p studentowi s}

2. Podaj po cztery przykłady relacji

(a) międzyludzkich występujących w grupie pracowniczej

(b) między dwoma dowolnymi kołami na płaszczyźnie

3. Narysuj graf następujących relacji binarnych:

(a) R

, {(A, B), (B, C), (C, D), (D, A)}

(b) R

, {(A, B), (A, C), (A, D), (A, A)}

, {(B, A), (C, A), (D, A), (A, A)}

(d) R

, {(B, A), (C, A), (D, A), (D, C), (C, B), (B, D)}

4. Wyznacz relacje R

−1

, i = 1, . . . , 7, tj. relacje odwrotne do relacji R

, . . . , R

zdeﬁniowanych w powyższych ćwiczeniach.

Zadania

1. Kiedy dziedzina relacji jest pusta ?

2. Kiedy przeciw-dziedzina relacji jest pusta ?

3. Niech a, b ∈ Z, aRb wtedy i tylko wtedy gdy a i b są parzyste. Czy relacja

R jest relacją równoważności ?

4. Ile różnych klas równoważności ma następująca relacja liczb całkowitych

przy ustalonym m ∈ Z :

xRy wtt m dzieli x

− y

Problemy

1. Udowodnij: D

−1

= D

−1

2. Określamy relację R w zbiorze A instancji typu int w C następująco: xRy

wtt instancje x i y reprezentują tę samą liczbę całkowitą. Pokaż, że R jest
relacją równoważności, dla której A/R = I

1.10

Funkcje

Niech R ⊂ A

× A

będzie relacją.

• Deﬁnicje:

–

Obraz elementu a

∈ A

R(a

) , {a

∈ A

: a

}

–

Przeciw-obraz elementu a

∈ A

−1

) , {a

∈ A

: a

}

• Binarna relacja R nazywa się funkcją częściową wtt

|R(a

)| = 1 dla wszyst-

kich a

∈ D

• Funkcję częściową f identyﬁkujemy symbolami: f : A

→ A

• Funkcja częściowa f : A

→ A

nazywa się funkcją jeśli D

= A

• Funkcję f identyﬁkujemy symbolami: f : A

→ A

• Dla funkcji zapis relacyjny a

f a

zastępujemy przez a

= f(a

) lub a

7→

• Szczególne rodzaje funkcji:

–

f : A

→ A

jest jednoznaczną funkcją ”w” A

wtt |f

−1

)| = 1 dla

wszystkich a

∈ D

−1

–

Własność: Relacja odwrotna do funkcji jednoznacznej ”w” jest funk-
cją częściową

–

f jest jednoznacznym odwzorowaniem A

”na” A

wtt |f

−1

)| = 1

dla wszystkich a

∈ D

−1

oraz D

−1

= A

–

Własność: Relacja odwrotna do funkcji jednoznacznej ”na” jest funk-
cją jednoznaczną ”na”

Ćwiczenia

1. Czy relacja x jest ojcem y jest funkcją w zbiorze wszystkich mężczyzn?

2. Czy relacja x jest synem y jest funkcją w zbiorze wszystkich mężczyzn?

3. Czy relacja x jest synem y jest funkcją częściową w zbiorze wszystkich

mężczyzn?

4. Czy relacja osoba x ma żyjącego ojca y jest funkcją częściową?

5. Niech f(x) = |x| dla x ∈ [−1, 1]. Wyznacz dla f

(a) Przeciw-obraz zera

(b) Przeciw-obraz y ∈ (0, 1]

Zadania

1. Dlaczego funkcja f(x) = 1/x jest funkcją częściową w R ?

2. Ile istnieje różnych funkcji postaci f : {0, 1} → {0, 1}

Problemy

1. Pokaż, że graf relacji binarnej będącej funkcją f : X → X na skończonym

zbiorze X zawiera co najmniej jeden cykl.

2. Pokaż, że funkcja jest jednoznaczna ”na” wtedy i tylko wtedy gdy jej graf

jako relacji binarnej składa się z rozłącznych cykli.

3. Sprawdź, że liczba funkcji binarnych na zbiorze n-elementowym równa się

liczbie podzbiorów tego zbioru.

1.11

Złożony typ danych a produkt kartezjański

Niech A

, A

, . . . , A

będą zbiorami instancji typów T

, . . . , T

. Wtedy

• W językach programowania składowe instancji złożonego typu zamiast

numeru pozycji mają swoje nazwy

• W języku C typ złożony jest nazywany strukturą i ma on ogólną postać:

typedef struct

{T1 nazwa1;...,Tn nazwan} T;

z deklaracją zmiennej x typu T w postaci T x;
lub
struct T

{T1 nazwa1;...,Tn nazwan};

z deklaracją zmiennej x typu T w postaci:
struct T x;

• Przykład struktury numerycznej:

typedef struct

{double re; double im} Complex;

• Przykład struktury biznesowej:

typedef struct

{int seria, int numer, float cena, String opis} Produkt;

• Typ T złożony z typów T

, . . . , T

ma instancje w postaci krotek o skła-

dowych, które są instancjami kolejno typów T

, . . . , T

• Wniosek: Produkt kartezjański zbiorów instancji typów T

, . . . , T

jest

zbiorem instancji typu złożonego T

• Jeśli A jest zbiorem instancji typu danych T i R jest relacją równoważności

w A, to zbiór A/R nazywamy modelem M

typu danych T względem

relacji R.

• Własność: Jeśli typ T jest złożony z typów T

, . . . , T

i M

, . . . , M

są

modelami tych typów, to M

jest modelem typy T względem relacji R

określonej następująco w zbiorze instancji typu T :

, . . . , x

)R(y

, . . . , y

) wtt x

, i = 1, . . . , n

Co więcej, model typu złożonego jest produktem kartezjańskim modeli
składowych:

= M

× · · · × M

Ćwiczenia

1. Opisz zbiór instancji typu danych złożonego

(a) z dwóch składowych typu int:

typedef struct

{int m; int n;} T;

(b) z trzech składowych typu double:

typedef struct

{double a; double b; double c;} T;

2. Podaj trzy dowolne instancje typu:

(a) Complex

(b) Product

Zadania
Model typu danych Ti ma n

elementów, i = 1, 2. Ile elementów ma model typu

1. typedef struct{T1 a; T2 b;} T3;

2. typedef struct{T1 a; T2 b; T1 c;} T4;

3. typedef struct{T1 a; T2 b; T1 c; T2 d;} T5;

1.12

Generalizacja typów danych

• Przyrostowe tworzenie krotki:

, a

) jest równoważne ((a

, a

), a

)

• Przyrostowe tworzenie produktu kartezjańskiego:

× A

= (A

× A

) × A

• Kontekst koncepcji generalizacji typów danych:

–

Najpierw programujemy własności ogólne obiektu (np. ruch ﬁgury),
a następnie jego specyﬁczne atrybuty (np. wizualizacja koła)

–

Rozszerzenie projektu o nowe funkcjonalności wymaga dodania no-
wych atrybutów – mechanizmy dziedziczenia w programowaniu obiek-
towym pozwalają je realizować bez aktualizacji istniejących już mo-
dułów oprogramowania

• Przykłady:

–

Do przemieszczenia ﬁgury symetrycznej względem jej środka wystar-
czy jego przemieszczenie. Natomiast narysowanie takiej ﬁgury, np.
pierścienia i koła wymaga znajomości innych parametrów. Dołącze-
nie tych parametrów do informacji o środku jest przykładem rozsze-
rzania typów danych lub dziedziczenia typów danych.

–

W języku Java dodanie do typu T1 atrybutu nowyAtrybut symboli-
zuje konstrukcja extends tworząc nowy typ danych
T2

:class T2 extends T1 {int nowyAtrybut;...}

Ćwiczenia
Niech T1 będzie typem danych złożonym z dwóch składowych typu int:
typedef struct

{int m; int n;} T1;

1. Opisz zbiór instancji typu danych, który specjalizuje T1 (operacja odwrot-

na do generalizacji):

(a) class T2 extends T1 {double a; double b;}

(b) class T3 extends T1 {int k; int l;}

2. Podaj trzy dowolne instancje typu

(a) T2

(b) T3

Zadania
Model typu danych Ti ma n

elementów, i = 1, 2. Ile elementów ma model typu

1. class T3 extends T1 {T2 pole;}

2. class T4 extends T2 {T1 pole;}

1.13

Atrybuty i cechy

• Przykłady stosowania pojęć atrybut, cecha:

–

Jan ma 175 cm wzrostu – obiekt: konkretny Jan; atrybut: wzrost;
cecha: 175 cm

–

Kolor dominujący w tym obrazie jest czerwony – obiekt: konkretny
obraz; atrybut: kolor dominujący; cecha: kolor czerwony

–

Toyota Corolla z silnikiem 2, 5 litra kosztuje 20 tysięcy Euro – obiekt:
konkretny model samochodu; atrybut 1: pojemność silnika; cecha 1:
2,5 litra; atrybut 2: cena; cecha 2: 20 tysięcy Euro

• Cecha c

∈ C przysługuje obiektowi o ∈ O w kontekście danego atrybutu

a :

7→ c, c = a(o)

• Atrybut a jest funkcją określoną na zbiorze obiektów

O o wartościach w

zbiorze cech C

a :

O → C

Ćwiczenia

1. Określ obiekt, atrybut i cechę w zdaniu

(a) Słoń ma dwie tony wagi.

(b) Temperatura barwowa tego obrazu wynosi 3000

◦

Kelvina

◦

gorączki

(d) Subaru Impreza ma moc 200 KM

2. Określ zbiór obiektów, atrybut i zbiór cech dla

(a) wagi słoni w ZOO warszawskim

(b) temperatur barwowych obrazów w Muzeum Narodowym

(d) mocy samochodów produkowanych w Europie w roku 2003

Zadania

1. Podaj przykład atrybutu, którego cechy są trójkami liczb całkowitych z

przedziału [0, 255].

2. Ile różnych atrybutów binarnych można określić na zbiorze trzech obiek-

tów.

1.14

Tabela relacyjna

• Kontekst tabeli relacyjnej: bazy danych takie jak baza Access, Oracle,

Postgress, MySQL to kolekcje tabel relacyjnych

• Tabela relacyjna to dwuwymiarowy zestaw danych, w którym:

–

wiersz tabeli odpowiada obiektowi danych

–

kolumna tabeli reprezentuje atrybut

–

element c

leżący na przecięciu wiersza obiektu o

i kolumny atry-

butu a

jest cechą tego obiektu

= a

) ∈ C

• Zwykle cecha w tabeli relacyjnej jest liczbą, łańcuchem znaków (ang.

String), lub jest instancją specjalnego typu, np. typu data, czas (ang.
Date, Time)

• Dlaczego termin tabela relacyjna ? Jest kilka powodów:

–

Tabela relacyjna z atrybutami a

, . . . , a

reprezentuje następującą

szczególną relację:

, {(a

(o), . . . , a

(o)) : o ∈ O} ⊂ C

× · · · × C

–

Krotka (a

(o), . . . , a

(o)) to wiersz tabeli opisujący obiekt o

–

Dowolną relację R

między kolekcjami obiektów O

można opisać

tzw. asocjacyjną tabelą relacyjną z jednym atrybutem złożonym a

a :

× O

→ N × N,

który przypisuje parze obiektów (o

, o

) parę ich identyﬁkatorów (id(o

), id(o

))

Ćwiczenia

1. Określ obiekty, atrybuty, cechy i ich typy w następującej tabeli relacyjnej

Nazwisko

Imię

Waga [kg]

Wzrost [cm]

Abacki

Karol

55,4

155

Babacki

Jan

47,6

134

2. Zaprojektuj tabelę relacyjną reprezentującą listę ocen z Matematyki Dys-

kretnej dla dwóch kolokwiów i egzaminu pisemnego. Zapełnij jeden wiersz
tej tabeli oczekiwanymi przez siebie danymi

Zadania

1. Czy tabela relacyjna może zawierać dwa różne wiersze o tej samej zawar-

tości ?

2. Tabele w bazach danych mogą mieć niektóre pozycje typu brak danych.

Jak zmodyﬁkować deﬁnicję atrybutu, by obejmowała przypadki pozycji
nie zdeﬁniowanych ?

1.15

Ciągi i macierze

Niech I ⊂ Z będzie zbiorem indeksów całkowitych.

• Ciąg c = (c

)

∈I

elementów ze zbioru Z indeksowany przez I jest funkcją

postaci

c : I

→ Z, c(i) , c

∈ Z, i ∈ I

• Przykłady:

–

Jeśli I = N oraz Z = R, to ciąg c jest ciągiem liczb rzeczywistych

–

Jeśli I = [1, n], to c jest wektorem długości n, c ∈ Z

–

Jeśli I = [0, 9] oraz Z jest zbiorem instancji typu int w języku C,
to c jest instancją macierzy jednowymiarowej deklarowanej jako int
c[10];

Niech I

⊂ Z będzie j-tym zbiorem indeksów całkowitych, j = 1, . . . , k.

• Niech i = (i

, . . . , i

) ∈ I , I

× . . . I

będzie wielo-indeksem

• Macierz elementów c = (c

)

∈I

ze zbioru Z indeksowany przez I jest funk-

cją postaci

c : I

→ Z, c(i) , c

, i

∈ I

• Przykłady:

–

Jeśli I

= I

= N oraz Z = R, to ciąg c jest nieskończoną macierzą

liczb rzeczywistych

–

Jeśli I

= [1, m], I

= [1, n] to c jest macierzą o m wierszach i n

kolumnach. Zbiór takich macierzy oznaczamy przez Z

×n

–

Jeśli I

= [0, 9], I

= [0, 19] oraz Z jest zbiorem instancji typu float

w języku C, to c jest instancją macierzy deklarowanej jako double
c[10][20];

Ćwiczenia

1. Określ zbiór indeksów dla

(a) wektora wierszowego [c

−2

, c

−1

, c

]

(b) wektora kolumnowego

, c

]













0,0

0,1

1,0

1,1

(d) macierzy prostokątnej

1,1

1,2

1,3

2,1

2,2

2,3

2. Ile elementów zawiera macierz o zbiorze indeksów I = [0, 5]

Zadania

1. Dlaczego wektor jest szczególnym przypadkiem macierzy dowolnego wy-

miaru ?

2. Ile elementów zawiera macierz o zbiorze indeksów I = I

× I

, gdzie

| = n

, i = 1, 2, 3 ?

1.16

Diagramy relacyjne w UML

Ćwiczenia
Narysuj diagram relacyjny dla:

1. roli Nauczyciel uczy matematykę jeśli nauczyciel jest typu Pracownik, a

matematyka jest typu Przedmiot nauczania

2. generalizacji typu Koło, Prostokąt i elipsa do typu Kształt

3. kompozycji typów Środek koła i Promień koła do typu Koło

4. kolekcji obiektów typu Kształt

«datatype»

Pracownik Umysłowy

«datatype»

Kampania Reklamowa

szef

0..*

kieruje

«datatype»

Reklama

«datatype»

Reklama TV

«datatype»

Reklama prasowa

«datatype»

Komponent

1..*

Generalization

Composition

Aggregation

Rysunek 1: Relacje w UML: composition – kompozycja obiektów, aggregation
– kolekcje obiektów, generalization – generalizacja (opozycja dziedziczenia)

Algebry

• Pojęcie algebry:

1. Dziedzina D algebry, np. zbiór liczb rzeczywistych, t.j. D = R
2. Operacje O algebry, np. dodawanie, odejmowanie, mnożenie i dziele-

nie w zbiorze liczb rzeczywistych, t.j. O = {+, −, ∗, /}

3. Operacja ma ustaloną liczbę argumentów, np. dodawanie ma dwa

argumenty

4. Operacje mogą być funkcjami częściowymi, np. dzielenie

• Przykłady algebr:

1. Zbiór liczb całkowitych Z z dodawaniem + i odejmowaniem −: (Z; +, −)
2. Zbiór liczb rzeczywistych R z dodawaniem +, odejmowaniem −, mno-

żeniem ∗ i dzieleniem / : (R; +, −, ∗, /)

3. Zbiór izometrii I przestrzeni z operacją ◦ składania funkcji: (I; ◦)

–

np. obrót na płaszczyźnie o kąt φ wokół punktu O(x

, y

) :

′

= x

+ x cos(φ) + y sin(φ)

′

= y

− x sin(φ) + y cos(φ)

–

np. symetria osiowa względem osi x :

′

= x

′

= −y

Ćwiczenia

1. Dlaczego operacja dzielenia w R jest funkcją częściową?

2. Jaka operacja określona jest w algebrze obrotów płaszczyzny w siebie?

3. Jaka operacja określona jest w algebrze izometrii płaszczyzny w siebie?

4. Jakie przekształcenie określone jest przez złożenie dwóch symetrii osio-

wych względem tej samej osi ?

Zadania

1. Uzasadnij, że złożenie dwóch obrotów jest obrotem

2. Uzasadnij, że złożenie dwóch izometrii jest izometrią

2.1

Intuicje informacyjne algebry

• Jednostka arytmetyczno-logiczna (ALU) w komputerze (część jednostki

centralnej CPU) realizuje operacje arytmetyczne i bitowe na liczbach ze
zbioru I

• Każde zdanie programu C określa funkcję na pamięci komputera

• Każde zdanie programu C określa funkcję na globalnym stanie programu

• Wynik programu jest złożeniem funkcji – złożenie jest tu operacją w zbio-

rze funkcji realizowanych przez kolejne zdania programu C

• Wynik programu jest złożeniem elementarnych operacji arytmetyczno-

logicznych

• Algebra Boole’a stanowi podstawę projektowania układów logicznych

2.2

Deﬁnicja algebry ogólnej

• Formalna deﬁnicja algebry ogólnej:

A , (X, K; f

: X

→ X, i = 1, . . . , K)

gdzie

• X jest dziedziną algebry

• f

jest i-tą operacją algebry (funkcja częściowa!)

• n

jest liczbą argumentów i-tej operacji

2.2.1

Algebry a klasy obiektów

• Algebra

A łączy w logiczną całość zbiór X i operacje f

na tym zbiorze

• Klasa

K w programowaniu obiektowym określa zbiór instancji (obiektów)

tej klasy i jednocześnie operacje na tych instancjach i opcjonalnie na in-
stancjach innych klas.

• Wartość operacji klasy

K może być instancją klasy K

′

6= K, np.: class X

{int x; improve(); Y produce(double a);}

• Biorąc produkt kartezjański zbiorów instancji rodziny klas, które są uży-

wane w danej aplikacji możemy traktować każdą operację w klasie jako
operację w takim zbiorze. Otrzymujemy więc algebrę.

2.2.2

Diagramy klas w UML

• UML pozwala na reprezentację graﬁczną klasy (rys.2)

• Z diagramu klasy można generować deﬁnicję klasy w różnych językach,

np. w Javie lub C++

2.3

Algebra Boole’a

• Operacja NOT :

{0, 1} → {0, 1}

, NOT(x) , 1 − x, x ∈ {0, 1}

• Operacja AND :

{0, 1} × {0, 1} → {0, 1}

AND(x, y) , x&y , x · y, x, y ∈ {0, 1}

• Operacja OR :

{0, 1} × {0, 1} → {0, 1}

OR(x, y) , x|y , x + y − xy, x, y ∈ {0, 1}

• Prawa de’Morgana w algebrze Boole’a:

–

NOT OR:

|y = x&y

Rysunek 2: Diagram klas w UML: klasa Shape jest generalizacją klas Circle,
Rectangle

–

NOT AND:

x&y = x

• Funkcja Boole’a, inaczej funkcja bitowa n argumentowa to każda funkcja

f taka, że:

f :

{0, 1}

→ {0, 1}

Ćwiczenia

1. Czemu służą operacje logiczne w CPU?

2. Niech funkcja bitowa NAND będzie określona wzorem:

NAND(x, y) , x&y , x&y

Sprawdź, że x = x&x.

3. Niech funkcja bitowa NOR będzie określona wzorem:

NOR(x, y) , | , x|y

Sprawdź, że x = x|x.

4. Czym się różni operacja składania funkcji mnożących liczby całkowite od

operacji mnożenia liczb całkowitych?

Zadania
Pokaż, że funkcja f da się wyrazić przez funkcję g, gdzie

1. f = NOT, g = NAND

2. f = AND, g = NAND

3. f = OR, g = NAND

4. f = NOT, g = NOR

5. f = OR, g = NOR

6. f = AND, g = NOR

Problemy

1. Pokaż,że następujące funkcje bitowe mają wartość 1 tylko w jednym ele-

mencie dziedziny, a w pozostałych wartość 0.

x&y&z = 1 wtt

x = 1, y = 1, z = 1

x&y&z = 1 wtt

x = 0, y = 1, z = 1

x&y&z = 1 wtt

x = 0, y = 0, z = 1

x&y&z = 1 wtt

x = 0, y = 0, z = 0

2. Jaka jest postać wyrażenia Boole’a złożonego tylko z funkcji NOT oraz

AND, która przyjmuje 1 tylko w następującym elemencie dziedziny:

(a) x = 0, y = 1, z = 0

(b) x = 1, y = 0, z = 0

(d) x = 1, y = 1, z = 0

3. Oznaczmy funkcję bitową przyjmującą wartość 1 tylko w elemencie (a, b, c)

przez f

a,b,c

. Pokaż, że funkcja g przyjmuje wartość 1 tylko w elementach

ze zbioru A, gdzie:

(a) g(x, y, z) = f

0,0,0

(x, y, z)|f

1,1,1

(x, y, z), A = {(0, 0, 0), (1, 1, 1)}

(b) g(x, y, z) = f

1,0,0

(x, y, z)|f

0,1,0

(x, y, z)|f

0,0,1

(x, y, z),

A =

{(1, 0, 0), (0, 1, 0), (0, 0, 1)}

4. Pokaż, że każda funkcja bitowa f o trzech argumentach da się przedsta-

wić jako złożenie funkcji NOT, AND, OR w tzw. dyzjunkcyjnej postaci
normalnej:

f (x, y, z) = OR

(a,b,c):f (a,b,c)=1

a,b,c

(x, y, z)

gdzie OR

W (i) oznacza wyrażenie łączące operacją OR wartości wyraże-

nia W (i) otrzymane dla każdego i ∈ I.

5. Zapisz i uzasadnij uogólnienie dyzjunkcyjnej postaci normalnej dla dowol-

nej funkcji bitowej o n argumentach, n > 1

6. Zapisz postać dyzjunkcyjną normalną dla funkcji Boole’a f zadanej tabelą:

f(x,y,z)

7. Pokaż,że następujące funkcje bitowe mają wartość 0 tylko w jednym ele-

mencie dziedziny, a w pozostałych wartość 1.

|y|z = 0 wtt x = 0, y = 0, z = 0

|y|z = 0 wtt x = 1, y = 0, z = 0

|y|z = 0 wtt x = 1, y = 1, z = 0

|y|z = 0 wtt x = 1, y = 1, z = 1

8. Jaka jest postać wyrażenia Boole’a złożonego tylko z funkcji NOT oraz

OR, która przyjmuje 0 tylko w następującym elemencie dziedziny:

(a) x = 0, y = 0, z = 1

(b) x = 0, y = 1, z = 0

(d) x = 1, y = 0, z = 1

9. Oznaczmy funkcję bitową przyjmującą wartość 0 tylko w elemencie (a, b, c)

przez f

a,b,c

. Pokaż, że funkcja g przyjmuje wartość 0 tylko w elementach

ze zbioru A, gdzie:

(a) g(x, y, z) = f

0,0,0

(x, y, z)&f

1,1,1

(x, y, z), A = {(0, 0, 0), (1, 1, 1)}

(b) g(x, y, z) = f

1,0,0

(x, y, z)&f

0,1,0

(x, y, z)&f

0,0,1

(x, y, z),

A =

{(1, 0, 0), (0, 1, 0), (0, 0, 1)}

10. Pokaż, że każda funkcja bitowa f o trzech argumentach da się przedsta-

wić jako złożenie funkcji NOT, OR i AND w tzw. koniunkcyjnej postaci
normalnej:

f (x, y, z) = AND

(a,b,c):f (a,b,c)=1

a,b,c

(x, y, z)

gdzie AND

W (i) oznacza wyrażenie łączące operacją AND wartości wy-

rażenia W (i) otrzymane dla każdego i ∈ I.

11. Zapisz i uzasadnij uogólnienie koniunkcyjnej postaci normalnej dla dowol-

nej funkcji bitowej o n argumentach, n > 1

12. Zapisz postać koniunkcyjną normalną dla funkcji Boole’a f zadaną po-

wyższą tabelą.

2.4

Układy zupełne funkcji Boole’a

•

S – zbiór funkcji selekcji, t.j. funkcji postaci:

f (x

, x

, . . . , x

) = x

dla pewnego i ∈ [1, n]

•

C – zbiór funkcji stałych, t.j. funkcji postaci:

f (x

, x

, . . . , x

) = const

• Zbiór funkcji Boole’a

F nazywa się układem zupełnym wtt dowolna funkcja

Boole’a da się przedstawić jako złożenie funkcji z F ∪ S ∪ C

• Zbiór funkcji

{|, &, ·} jest układem zupełnym

• Zbiór funkcji

{&, ·} jest układem zupełnym

• Zbiór funkcji

{|, ·} jest układem zupełnym

• Zbiór funkcji

{|} jest układem zupełnym

• Zbiór funkcji

{&} jest układem zupełnym

• Fakt: Jeśli funkcje układu zupełnego A możemy otrzymać przez złożenie

z funkcji układu B, to układ B jest zupełny

• Funkcja Boole’a f :

{0, 1}

→ {0, 1} jest monotoniczna wtt

≤ x

′

, i = 1, . . . , n

−→ f(x

, . . . , x

) ≤ f(x

′

, . . . , x

′

)

• Fakt: Złożenie funkcji monotonicznych jest funkcją monotoniczną

• Wniosek: Układ zupełny zawiera co najmniej jedną funkcję, która nie jest

monotoniczna

• Funkcja Boole’a f :

{0, 1}

→ {0, 1} jest samosprzężona wtt

f (x

, . . . , x

) = f(x

, . . . , x

)

• Fakt: Złożenie funkcji samosprzężonych jest funkcją samosprzężoną

• Wniosek: Układ zupełny zawiera co najmniej jedną funkcję, która nie jest

samosprzężona

• Dla funkcji n argumentowej f, która nie jest samosprzężona istnieje krotka

, . . . , a

) ∈ {0, 1}

, na której f nie jest sprzężona, t.j.:

f (a

, . . . , a

) = f(a

, . . . , a

)

• W klasie funkcji Boole’a, które nie są samosprzężone wyróżniamy funkcje

f które są sprzężone w zerze, t.j.

f (0, . . . , 0) = f (1, . . . , 1)

f (a

, . . . , a

) = f(a

, . . . , a

)

dla pewnego (a

, . . . , a

)

Twierdzenie 2.1

O warunkach na zupełność układu

Jeśli układ funkcji Boole’a zawiera funkcję f

niemonotoniczną i funkcję f

sprzężoną w zerze, która nie jest samosprzężona, to układ ten jest zupełny. ⊳

Dowód:

Pokażemy najpierw, że z funkcji f

, . . . , x

) możemy skonstruować funkcję N OT . Miano-

wicie brak monotoniczności oznacza istnienie takich dwóch elementów w dziedzinie f

, że po

uporządkowaniu zmiennych według rosnących wartości mamy:

(0, . . . , 0, 1, . . . , 1, 1, . . . , 1) = 0

(0, . . . , 0, 0, . . . , 0, 1, . . . , 1) = 1

Podstawiając x = 0, 1 sprawdzamy, że funkcja

g(x)

, f

(0, . . . , 0, x, . . . , x, 1, . . . , 1) = x

Następnie pokażemy, że z funkcji f

możemy przez właściwe podstawienie zmiennych x, y jako

argumentów funkcji otrzymamy jedną z funkcji AND, NOR, OR lub NAND.
Mianowicie x podstawiamy w miejsce jedynek sekwencji (a

, . . . , a

), dla której nie jest speł-

niony warunek sprzężenia:

, . . . , a

) = f

, . . . , a

)

Zmienną y podstawiamy w miejsce zer tej sekwencji. Obydwa podstawienia się możliwe gdyż
sekwencja ta nie może składać się z samych zer lub samych jedynek – konsekwencja warunku

sprzężenia w zerze. Porządkując argumenty według rosnących wartości mamy:

(0, . . . , 0, 1, . . . , 1) = f

(1, . . . , 1, 0, . . . , 0)

h(x, y)

, f

(y, . . . , y, x, . . . , x)

h(0, 1) = h(1, 0)

Ponieważ h(0, 0) = f

(0, . . . , 0) = f

(1, . . . , 1) = h(1, 1). Rozważając dwie możliwe wartości

dla h(0, 0) i również dwie możliwości dla h(0, 1) otrzymujemy następujące cztery możliwości na
funkcję h :

h(x,y)

Widzimy więc, że możemy z funkcji f

otrzymać:

• AND dla h(0, 0) = 0, h(0, 1) = 0 – wtedy otrzymane AND wraz z NOT (otrzymanym z

) jest układem zupełnym

• NOR dla h(0, 0) = 1, h(0, 1) = 0 – wtedy otrzymane NOR tworzy układ zupełny

• OR dla h(0, 0) = 0, h(0, 1) = 1 – wtedy otrzymane OR wraz z NOT (otrzymanym z

)jest układem zupełnym

• NAND dla h(0, 0) = 1, h(0, 1) = 1 – wtedy otrzymane NAND tworzy układ zupełny

Stąd f

oraz f

tworzą układ zupełny, bo z nich możemy otrzymać układ zupełny.

⊳

Ćwiczenia:
Stosując twierdzenie o układach zupełnych sprawdź zupełność układu:

1. AND i NOT

2. OR i NOT

3. AND, OR i NOT

4. NAND

5. NOR

2.5

Własności algebry Boole’a

• Przemienność:

|y = y|x, x&y = y&x

• Łączność:

|(y|z) = (x|y)|z, x&(y&z) = (x&y)&z

• Rozdzielność koniunkcji względem alternatywy:

x&(y

|z) = (x&y)|(x&z)

• Rozdzielność alternatywy względem koniunkcji:

|(y&z) = (x|y)&(x|z)

• Własności negacji:

x = x, x

|y = x&y, x&y = x|y

• Pełność negacji:

|x = 1, x&x = 0

• Własności zera:

|0 = x, x&0 = 0

• Własności jedynki:

x&1 = x, x

|1 = 1

Ćwiczenia
Uzasadnij równości funkcji Boole’a:

1. x&y&z = z|x|y

2. x|y|z = z&x&y
3. x&(x|y)&y = 0

4. x|(x&y)|y = 1

2.6

Mapa Karnaugh

• Eliminacja zmiennej i jej negacji w alternatywie koniunkcji:

x&w

|x&w = w

x&w

|x&w = (x|x)&w = 1&w = w

gdzie w jest dowolnym wyrażeniem boolowskim

• Eliminacja zmiennej i jej negacji w koniunkcji alternatyw:

(x|w)&(x|w) = w

(x|w)&(x|w) = (x&x)|w = 0|w = w

gdzie w jest dowolnym wyrażeniem boolowskim

• Eliminacja dwóch zmiennych w koniunkcji alternatyw:

(x|y|w)&(x|y|w)&(x|y|w)&(x|y|w) = w

Eliminacja dwóch zmiennych w alternatywie koniunkcji:

x&y&w

|x&y&w|x&y&w|x&y&w = w

x&y&w

|x&y&w|x&y&w|x&y&w = (x&y&w|x&y&w)|(x&y&w|x&y&w) =

= y&w|y&w = w

Ćwiczenia:
Uprość wyrażenia boolowskie do wyrażenia o:

1. jednej zmiennej: x&y|y&x
2. dwóch zmiennych: x&y&z|x&z&y

3. jednej zmiennej: x&y&z|y&x&z|x&y&z|x&z&y

4. jednej zmiennej: (x|y)&(y|x)

5. dwóch zmiennych: (x|y|z)&(x|z|y)

6. jednej zmiennej: (x|y|z)&(y|x|z)&(x|y|z)&(x|z|y)

2.7

Rachunek zdań

• Przykłady zdań o wartości logicznej prawda (1):

–

1000 = 1000

–

5 < 55

–

17 = 7 + 10

–

sześć jest liczbą parzystą

–

1024 jest całkowitą potęgą dwójki

• Przykłady zdań o wartości logicznej fałsz (0):

–

1000 = 2000

–

5 > 15

–

17 = 2 + 51

–

sześć jest liczbą nieparzystą

–

1024 jest całkowitą potęgą trójki

• Następującym zdaniom nie można przypisać wartości logicznej:

–

x = 2000

–

x > y

–

x = y + z

2.7.1

Spójniki logiczne

Spójnik

Nazwa

Spójnik w C

Funkcja Boole’a

Funkcja w C

negacja

∨

alternatywa

∧

koniunkcja

↔

równoważność

→

implikacja
alt. wyłączna

⊕

2.7.2

Wyrażenia logiczne

• Budowa wyrażeń logicznych:

–

Stałe logiczne: T F

–

Zmienne logiczne:

a b c . . . x y z

–

Wyrażenia atomowe: stałe logiczne lub zmienne logiczne

–

Negacja atomów:

¬a ¬b ¬c . . . ¬x ¬y ¬z ¬T ¬F

–

Wyrażenia złożone z wyrażeń prostszych w

, w

¬(w

)

) ∨ (w

)

) ∧ (w

)

) → (w

)

Jeśli wyrażenie w

lub w

jest atomem lub jego negacją, to pomijamy

nawiasy.

• Przykłady wyrażeń logicznych:

¬a, x → y, (¬a ∨ b) → (a ∧ b)

• Wyrażenie logiczne w reprezentuje funkcję Boole’a f

• Niech wyrażenia logiczne w

i w

będą zbudowane z tego samego zestawu

zmiennych logicznych. Mówimy, że

–

i w

są logicznie równoważne, w

⇐⇒ w

, wtt określają tą samą

funkcję Boole’a:

⇐⇒ w

wtt f

= f

–

implikuje w

, w

=⇒ w

, wtt jedynki f

są jedynkami f

=⇒ w

wtt f

≤ f

wttf

(a, b, . . . ) = 1 → f

(a, b, . . . ) = 1

• Jeśli f

nie przyjmuje wartości zero, to wyrażenie w nazywa się tautologią

• Równoważna deﬁnicja wyrażeń równoważnych:

⇐⇒ w

wtt (w

) ↔ (w

) jest tautologią

• Równoważna deﬁnicja implikacji logicznej:

=⇒ w

wtt (w

) → (w

) jest tautologią

• Ważne tautologie:

∨ ¬a

¬¬a ↔ a

(a ∨ b) ∨ (¬a ∧ ¬b)

(a ∨ b) ∧ ¬b → a

(a → b) ↔ (¬a ∨ b)

kontrapozycja: (a → b) ↔ (¬b → ¬a)

modus ponens: (a ∧ (a → b)) → b

modus tollens: (a ∧ (¬b → ¬a)) → b

zaprzeczenie: (¬p → F ) → p

przechodniość implikacji:[(a → b) ∧ (b → c)] → (a → c)

Zadania:

1. Wiemy, że zdanie ¬a ∧ b jest prawdziwe. Co można powiedzieć o prawdzi-

wości zdania:

[a ∨ ¬b ∨ (a ∨ b)] ∨ [(¬(a ∨ b)) ∨ (¬a ∧ b)]

2. Co możesz powiedzieć o prawdziwości zdań a , x ∈ A, b , y ∈ B, c , y ∈

A jeśli następujące implikacje są prawdziwe:

Jeśli x ∈ A oraz y ∈ B, to y ∈ A

Jeśli x 6∈ A oraz y ∈ A, to y 6∈ B

3. Sprawdź czy następujące wyrażenia logiczne są tautologiami:

(a) (a → b) ∧ (a → c) ↔ (a → (b ∧ c))

(b) (a → c) ∧ (b → c) ↔ ((a ∨ b) → c)

(d) (a → (b → c)) → ((a → b) → c)

(e) (a ↔ b) → (a ∧ b)

(f) (a ↔ b) ↔ (a ∧ b) ∨ (¬a ∧ ¬b)

(g) (a → b) ↔ ((a ∧ ¬b) → b)

(h) (a → b) ↔ ((a ∧ ¬b) → (c ∧ ¬c))

(i) ((a → b) → c) → (b → (a → c))

Problemy:

1. W pewnej wiosce ludzie dzielą się na dwie grupy K i P. W grupie K są

ci, którzy zawsze kłamią, a w grupie P ci, którzy zawsze mówią prawdę.

Określ przynależność osób do tych grup, jeśli:

(a) spotykają się osoby A, B i A powiada do B ”przynajmniej jeden z

nas jest kłamcą”

(b) spotykają się osoby A, B i A powiada ”ja jestem kłamcą lub B nie

jest kłamcą”

mi”, zaś B na to ”tylko jeden z nas nie kłamie”

(d) spotykają się osoby A, B, C i A powiada ”panowie należycie do tej

samej grupy” – co powie C jeśli ktoś go zapyta ”czy A i B są w tej
samej grupie?”

2. W pewnej wiosce w Transylwanii mieszkają osobnicy, których można zali-

czyć do jednej z czterech kategorii: (1) ludzie zdrowi, którzy zawsze mówią
prawdę; (2) ludzie chorzy, którzy zawsze kłamią; (3) wampiry zdrowe, któ-
re zawsze kłamią; (4) wampiry chore, które zawsze mówią prawdę.

(a) Pewien mieszkaniec tej wioski powiada ”jestem albo człowiekiem albo

jestem zdrowy.” Do jakiej kategorii należy ta osoba?

(b) Inny mieszkaniec powiada ”nie jestem zdrowym człowiekiem”. Kim

on jest?

do tej samej kategorii co poprzednik?

(d) Tubylec na zadane przez turystę pytanie ”czy jesteś chorym wampi-

rem?” odpowiedział ”tak lub nie.” Kim był ten tubylec?

Przykład dowodu przez zaprzeczenie
Twierdzenie 2.2

O pierwiastku z dwóch

√

2 jest liczbą niewymierną. ⊳

Dowód:

Niech zdanie p ma postać:

√

2 jest liczbą niewymierną.

Wtedy

¬p oznacza, że dla pewnych liczb m, n ∈ N względnie pierwszych mamy:

√

2 =

, m

= 2n

Stąd m jest podzielne przez dwa, a więc m

jest podzielne przez cztery i stąd n jest też podzielne

przez dwa. Co przeczy temu, że m i n są względnie pierwsze.

⊳

2.7.3

Wyrażenia logiczne a zbiory

wyrażenie logiczne

własność

zbiory

∨ a ↔ a ∧ a ↔ a

idempotentność

∪ A = A ∩ A = A

(a ∨ b) ∨ c ↔ a ∨ (b ∨ c)

łączność

(A ∪ B) ∪ C = A ∪ (B ∪ C)

(a ∨ b) ∧ c ↔ a ∧ (b ∧ c)

(A ∩ B) ∩ C = A ∩ (B ∩ C)

∨ b ↔ b ∨ a

przemienność

∪ B = B ∪ A

∧ b ↔ b ∧ a

∩ B = B ∩ A

∧ (b ∨ c) ↔ (a ∧ b) ∨ (a ∧ c)

rozdzielczość

∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

∨ (b ∧ c) ↔ (a ∨ b) ∧ (a ∨ c)

∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

¬¬a ↔ a

inwolucja

= A

¬(a ∨ b) ↔ ¬a ∧ ¬b

prawa

∪ B = A ∩ B

¬(a ∧ b) ↔ ¬a ∨ ¬b

de’Morgana

∩ B = A ∪ B

∨ F ↔ a

∧ F ↔ F

identyczność

∪ ∅ = A

∩ ∅ = ∅

∧ T ↔ a

∨ T ↔ T

∩ U = A

∪ U = U

∨ (a ∧ b) ↔ a

absorpcja

∪ (A ∩ B) = A

∧ (a ∨ b) ↔ a

∩ (A ∪ B) = A

2.7.4

Łamigłówka króla

Królewicz poślubi tę z trzech panien, która pierwsza rozwiąże zadanie opraco-
wane przez króla. Król powiedział pannom, że w sąsiedniej ciemnej komnacie
nałoży kolejno każdej z nich kapelusz koloru czerwonego lub zielonego. Gdy to
uczynił poinstruował je, że mają podnieść rękę gdy zobaczą przynajmniej jeden
kapelusz koloru czerwonego, a następnie pomyśleć i odgadnąć jaki kapelusz ma-
ją na głowie. Wygra ta z panien, która pierwsza da poprawną odpowiedź. Po
wprowadzeniu panien zgromadzeni zobaczyli, że król założył wszystkim pannom
kapelusze koloru czerwonego. Po dłuższej chwili milczenia jedna z panien ogłosiła
z pewnością siebie, że nosi kapelusz czerwony. Skąd to wiedziała?
Rozwiązanie logiczne

• Niech symbole A, B, C reprezentują trzy panny

• Załóżmy, że zagadkę rozwiązała panna A

• Określamy zdania logiczne:

1. a

, Panna A ma kapelusz czerwony.

2. a

, Panna A podniosła rękę.

3. a

, Panna A określiła kolor swojego kapelusza

4. Analogicznie określamy zdania b

, b

dla panny B oraz c

, c

dla panny C

• Gdy ”wszystkie panny podniosły rękę”, w ocenie sytuacji przez pannę A

następujące zdania są prawdziwe i ich prawdziwość może być sprawdzona
przez panny B i C:

1. ¬a

∧ b

∧ c

→ ¬a

∧ b

∧ c

2. ¬a

∧ b

∧ c

→ b

∨ c

3. ¬(b

∧ c

) → ¬(¬a

∧ b

∧ c

)

4. ¬(b

∨ c

) → a

∨ ¬b

∨ ¬c

5. b

↔ T

6. c

↔ T

7. ¬(b

∨ c

) → a

∨ F ∨ F ↔ a

8. ¬b

∧ ¬c

→ a

2.8

Rachunek predykatów i kwantyﬁkatorów

1. Formy zdaniowe

2. Kwantyﬁkatory

2.8.1

Predykaty

• Forma zdaniowa (predykat) jednej zmiennej to wyrażenie P (x), które po

podstawieniu dowolnego a ∈ D

staje się zdaniem logicznym

• Zbiór D

nazywamy dziedziną zmiennej x

• Jeśli P (a) jest zdaniem prawdziwym, to mówimy, że a spełnia P

• Zbiór tych wszystkich a

∈ D

, które spełniają P oznaczamy przez T (P ) i

nazywamy zbiorem spełniania predykatu P

• Forma zdaniowa (predykat) wielu zmiennych P (x, y, . . . ) ma określone

dziedziny D

, D

, . . . dla każdego parametru, a zbiór T (P ) spełniania P

jest relacją zawartą w D

× D

× · · · :

T (P )

, {(a, b, . . . ) : a ∈ D

, b

∈ D

, . . . P (a, b, . . . ) jest spełniony

}

T (P )

⊂ D , D

× D

× . . .

• Produkt kartezjański D

, D

× D

× . . . nazywamy dziedziną predykatu

• Przykłady:

–

P (x)

, x jest liczbą parzystą, D

, N, T (P ) to zbiór liczb parzystych

–

Q(x, y)

, x

+ y

= 25, D

= D

, N, T (Q) = {(3, 4), (4, 3)}

–

′

(x, y) , P (x) ∧ Q(x, y), D

= D

, N, T (Q

′

) = {(4, 3)}

–

, . . . , x

) , |x

| + . . . |x

| ≤ 1, D

= · · · = D

= R, T (P

) =

kula w normie pierwszej w R

–

, . . . , x

) , x

+ . . . x

≤ 1, D

= · · · = D

= R, T (P

) =

kula w R

–

∞

, . . . , x

) , max

| ≤ 1, D

= · · · = D

= R, T (P

∞

) =

kula w normie Czebyszewa w R

• Jeśli predykaty P i Q mają tę samą dziedzinę, to:

T (

¬(P )) = T (P )

T (P

∨ Q) = T (P ) ∪ T (Q)

T (P

∧ Q) = T (P ) ∩ T (Q)

T (P

→ Q) = T (P ) ∪ T (Q)

T (P

↔ Q) = (T (P ) ∩ T (Q)) ∪ (T (P ) ∩ T (Q))

• Mówimy, że z predykatu P wynika predykat Q wtt T

⊂ T

. Oznaczamy

ten fakt przez P ⇒ Q

• Mówimy, że predykat P jest równoważny predykatowi Q wtt T

= T

Oznaczamy ten fakt przez P ⇔ Q

Ćwiczenia:

1. Zapisz predykat P, dla którego zbiór spełniania T (P ) jest:

(a) kulą o promieniu 5 i o środku w punkcie (5, −5, 55)

(b) kołem o promieniu 10 i o środku w (1, 11)

o środku w (5, 5)

(d) kwadratem obróconym o 45 stopni względem środka poprzednio okre-

ślonego kwadratu

(e) zbiorem wszystkich punktów na płaszczyźnie o współrzędnych całko-

witych, które są względnie pierwsze

2. Znajdź zbiór spełniania T (P ) dla następującego predykatu P (x) :

• x

+ x + 1 < 30

• 1

≤ 3

≤ 27

• 0 < x < 40 oraz x

+ 7 jest całkowitą potęgą dwójki

Zadania:

1. Wyraź P (x) , ”x jest wielokrotnością 4” przy pomocy predykatu Q(x) ,

”x jest liczbą parzystą”

2. Niech A ⊂ D

będzie dowolnym zbiorem w dziedzinie D

. Zdeﬁniuj pre-

dykat P (x) taki, że T (P ) = A

3. Niech A , {x ∈ N : x ≤ 18}, B , {x ∈ N : x ≤ 25, 2|x}.

(a) Wypisz elementy zbiorów A − B oraz B − A

(b) Określ predykaty deﬁniujące zbiory A − B oraz B − A

4. Przypuśćmy, że mamy logiczną implikację P ⇒ Q dla predykatów P i

Q określonych w dziedzinie D. Co można powiedzieć o zbiorze spełniania
T ((P )

→ (Q))?

Problemy:
Jakie relacje muszą zachodzić między zbiorami spełniania T (P ) oraz T (Q) by
prawdą były następujące implikacje:

1. (P (x) → Q(x)) ⇒ P (x)
2. (P (x) → Q(x)) ⇒ Q(x)
3. (P (x) ∨ Q(x)) ⇒ (P (x) ∧ Q(x))
4. (P (x) → Q(x)) ⇒ (P (x) ∨ Q(x))

2.8.2

Kwantyﬁkatory

• Kwantyﬁkator ogólny

∀x (czytaj ”dla każdego x”) dotyczy predykatu jed-

nej zmiennej P (x) lub wielu zmiennych P (x, y, . . . )

–

Zmienna kwantyﬁkatora przyjmuje wartości z dziedziny D

lub z jej

podzbioru Z ⊂ D

–

Predykat P (x) jednej zmiennej – otrzymujemy zdanie logiczne q :

, ∀x ∈ Z, P (x)

Zdanie q jest prawdziwe wtt Z ⊂ T (P )

–

Jeśli Z = ∅, to zdanie ∀x ∈ Z, P (x) jest zawsze prawdziwe

–

Przykłady:

∀x ∈ N, x

> x

− 1

∀x ∈ Z − {0}, x

> x

− 1

∀x ∈ R, x

≥ 2x − 1

–

Predykat P (x, y) dwóch zmiennych – otrzymujemy predykat Q(y) :

Q(y)

, ∀x ∈ Z, P (x, y)

Zdanie Q(b) dla x = b jest prawdziwe wtt

⊂ {x ∈ D

: P (x, b)}

–

Przykłady:

∀x ∈ R, x

+ y ≥ 2x − 1

∀x ∈ R, sin(x · y) ≤ 1

• Kwantyﬁkator egzystencjalny

∃x (czytaj ”istnieje x”) dotyczy predykatu

jednej zmiennej P (x) lub wielu zmiennych P (x, y, . . . )

–

Zmienna kwantyﬁkatora przyjmuje wartości z dziedziny D

lub z jej

podzbioru Z ⊂ D

–

Predykat P (x) jednej zmiennej – otrzymujemy zdanie logiczne q :

, ∃x ∈ Z, P (x)

Zdanie q jest prawdziwe wtt Z ∩ T (P ) 6= ∅

–

Przykłady:

∃x ∈ N, 2

> 10

10000

∃x ∈ R, x

≤ 2x − 1

–

Predykat P (x, y) dwóch zmiennych – otrzymujemy predykat Q(y) :

Q(y)

, ∃x ∈ Z, P (x, y)

Zdanie Q(b) dla x = b jest prawdziwe wtt

∩ {x ∈ D

: P (x, b)} 6= ∅

–

Przykłady:

∃x ∈ R, x

+ y ≤ 2x − 1

∃x ∈ R, sin(x · y) >

√

2/2

• Negacja

∀ :

¬[∀x ∈ Z, P (x)] ↔ ∃x ∈ Z, ¬P (x)
¬[∀x ∈ Z, ¬P (x)] ↔ ∃x ∈ Z, P (x)

¬[∀x ∈ Z, P (x, y)] ↔ ∃x ∈ Z, ¬P (x, y)
¬[∀x ∈ Z, ¬P (x, y)] ↔ ∃x ∈ Z, P (x, y)

• Negacja

∃ :

¬[∃x ∈ Z, P (x)] ↔ ∀x ∈ Z, ¬P (x)
¬[∃x ∈ Z, ¬P (x)] ↔ ∀x ∈ Z, P (x)

¬[∃x ∈ Z, P (x, y)] ↔ ∀x ∈ Z, ¬P (x, y)
¬[∃x ∈ Z, ¬P (x, y)] ↔ ∀x ∈ Z, P (x, y)

• Przykład – deﬁnicja ciągłości funkcji w punkcie x

P (x, x

) , ∀ǫ > 0∃δ > 0, |x − x

| < δ → |f(x) − f(x

)| < ǫ

¬P (x, x

) ↔ ∃ǫ > 0∀δ > 0, |x − x

| < δ ∧ |f(x) − f(x

)| ≥ ǫ

• Przemienność

∀ :

∀x ∈ Z

∀y ∈ Z

, P (x, y)

↔ ∀y ∈ Z

∀x ∈ Z

, P (x, y)

∀x ∈ Z

∀y ∈ Z

, P (x, y, z)

↔ ∀y ∈ Z

∀x ∈ Z

, P (x, y, z)

• Przemienność

∃ :

∃x ∈ Z

∃y ∈ Z

, P (x, y)

↔ ∃y ∈ Z

∃x ∈ Z

, P (x, y)

∃x ∈ Z

∃y ∈ Z

, P (x, y, z)

↔ ∃y ∈ Z

∃x ∈ Z

, P (x, y, z)

• Specjalizacja dla Z

6= ∅ :

∀x ∈ Z, P (x) → ∃x ∈ Z, P (x)

∀x ∈ Z, P (x, y) → ∃x ∈ Z, P (x, y)

Ćwiczenia:

1. Zapisz w postaci kwantyﬁkatorowej następujące zdania:

(a) Istnieją wysocy mężczyźni

(b) Tylko pobożni zasługują na zbawienie

(d) Są rzeczy na ziemi i w niebie, które nie śnią się nawet ﬁlozofom

(e) Żadne prosię nie lata

2. Określ prawdziwość zdań:

(a) ∀x ∈ N, x

+ x < 10

10000

(b) ∃x ∈ N, (x

= 2x) ∨ (x

= 100)

Zadania:

1. Uzasadnij prawdziwość implikacji:

[∃x, (P (x) ∧ Q(x))] → [∃x, P (x)] ∧ [∃x, Q(x)]

2. Podaj przykład predykatów P (x), Q(x), dla których następujące implika-

cje są fałszywe:

[∀x, (P (x) ∨ Q(x))] → [∀x, P (x)] ∨ [∀x, Q(x)]

∀x∃y, P (x, y) → ∃y∀x, P (x, y)

∀x∃y, P (x, y) → ∃x∀y, ¬P (x, y)

Problemy:

1. Niech D

= {a, b, c.} Wyeliminuj kwantyﬁkatory z następujących zdań:

•

∀x ∈ D, P (x)

• [

∀x ∈ D, R(x)] ∧ [∃x ∈ D, S(x)]

2. Zapisz w postaci kwantyﬁkatorowej następujące zdania:

• Istnieją co najmniej dwa elementy x

∈ D, spełniające predykat P (x)

• Istnieją co najwyżej dwa elementy x

∈ D, spełniające predykat P (x)

• Istnieją dokładnie dwa elementy x

∈ D, spełniające predykat P (x)

• Można upiec szarlotkę na więcej niż dwa sposoby

• Własność P (n) jest prawdziwa dla wszystkich n

∈ N za wyjątkiem

skończonej liczby przypadków

2.9

Homomorﬁzm algebr

• Homomorﬁzm to odwzorowanie dziedziny jednej algebry w dziedzinę dru-

giej algebry zachowujące działania tych algebr

• Formalna deﬁnicja homomorﬁzmu:

–

Algebra oryginalna:

A , (X, K; f

: X

→ X, i = 1, . . . , K)

–

Algebra homomorﬁczna:

B , (Y, K; f

′

: Y

→ Y, i = 1, . . . , K)

–

Homomorﬁzm to odwzorowanie h : X → Y spełniające warunki:

h(f

, . . . , x

)) = f

′

(h(x

), . . . , h(x

))

dla dowolnych (x

, . . . , x

) ∈ D(f

), i = 1, . . . , K.

–

W algebrze homomorﬁcznej B (przy homomorﬁźmie h : X → Y )

dziedziny operacji są nadzbiorami obrazów dziedzin odpowiednich
operacji w algebrze A :

h(D(f

)) ⊂ D(f

′

), i = 1, . . . , K

–

Jeśli homomorﬁzm h : X → Y jest odwzorowaniem różnowartościo-

wym i ”na”, to h

−1

nie musi być homomorﬁzmem. Jeśli h

−1

jest

homomorﬁzmem, to h nazywamy izomorﬁzmem algebr A oraz B.

–

Jeśli h jest homomorﬁzmem różnowartościowym i ”na”, to h

−1

: Y →

X jest homomorﬁzmem wtt gdy dziedziny operacji w algebrze B są
obrazem dziedzin odpowiednich operacji w algebrze A :

D(f

′

) = h(D(f

)), i = 1, . . . , K

–

Jeśli h jest homomorﬁzmem różnowartościowym ”na” oraz dla pew-
nej operacji f

w algebrze A istnieje element (y

, . . . , y

) ∈ D(f

′

), bę-

dący obrazem elementu spoza dziedziny operacji f

, t.j. x

= h

−1

), i =

1, . . . , K oraz

, . . . , y

) ∈ D(f

′

), (x

, . . . , x

)) 6∈ D(f

to rozszerzenie operacji f

−1

na element (x

, . . . , x

)

, . . . , x

) , h

−1

′

, . . . , y

))

określa rozszerzenie algebry A izomorﬁczne z algebrą B.

• Przykład:

–

A , (Z, 2; +, ·) – algebra liczb całkowitych z operacjami dodawania

i mnożenia

–

B , ({0, 1}, 1; ⊕, &) – algebra binarna z operacjami XOR i AND

–

Odwzorowanie h : Z → {0, 1} określone następująco: h(x) = 0 wtt x

jest liczbą parzystą (x ∈ P)

–

Odwzorowanie h jest homomorﬁzmem algebry A w algebrę B, t.j.:

∀x, y ∈ Z, h(x + y) = h(x) ⊕ h(y)

∀x, y ∈ Z, h(x · y) = h(x)&h(y)

Dowód

homomorﬁzmu w powyższym przykładzie

Rozważmy cztery następujące przypadki dla operacji dodawania:

∈ P, y ∈ P → (x + y) ∈ P

∈ P, y ∈ P → h(x) = 0, h(y) = 0, h(x + y) = 0 = 0 ⊕ 0 = h(x) ⊕ h(y)

∈ P, y 6∈ P → (x + y) 6∈ P

∈ P, y 6∈ P → h(x) = 0, h(y) = 1, h(x + y) = 1 = 0 ⊕ 1 = h(x) ⊕ h(y)

6∈ P, y ∈ P → (x + y) 6∈ P

6∈ P, y ∈ P → h(x) = 1, h(y) = 0, h(x + y) = 1 = 1 ⊕ 0 = h(x) ⊕ h(y)

6∈ P, y 6∈ P → (x + y) ∈ P

6∈ P, y 6∈ P → h(x) = 1, h(y) = 1, h(x + y) = 0 = 1 ⊕ 1 = h(x) ⊕ h(y)

Rozważmy te same przypadki tym razem dla operacji mnożenia:

∈ P, y ∈ P → (x · y) ∈ P

∈ P, y ∈ P → h(x) = 0, h(y) = 0, h(x · y) = 0 = 0&0 = h(x)&h(y)

∈ P, y 6∈ P → (x · y) ∈ P

∈ P, y 6∈ P → h(x) = 0, h(y) = 1, h(x · y) = 0 = 0&1 = h(x)&h(y)

6∈ P, y ∈ P → (x · y) ∈ P

6∈ P, y ∈ P → h(x) = 1, h(y) = 0, h(x · y) = 0 = 1&0 = h(x)&h(y)

6∈ P, y 6∈ P → (x · y) 6∈ P

6∈ P, y 6∈ P → h(x) = 1, h(y) = 1, h(x + y) = 1 = 1&1 = h(x) ⊕ h(y)

⊳

Zadanie:
Pokaż, że rozszerzenie w powyższym przykładzie algebry A o operację odejmo-

wania liczb całkowitych −, a algebrę B o operację odejmowania modulo dwa ⊖,

to odwzorowanie h jest też homomorﬁzmem algebry A w algebrę B.

2.10

Rachunek reszt

• Iloraz q z dzielenia n

∈ Z przez p ∈ N oraz reszta r z tego dzielenia

spełniają warunki:

n = q

· p + r, 0 ≤ r < p

• Powyższy rozkład jest jednoznaczny, tzn. istnieje dokładnie jedna taka

para (q, r) spełniająca te warunki.
Dowód:

Jeśli n = q

· p + r

= q

· p + r

, to

|(q

− q

)

| · p = |r

− r

Ponieważ p dzieli

− r

|, a |r

− r

| < p, to r

= r

Stąd

· p = q

· p ⇒ q

= q

I dlatego (q

, r

) = (q

, r

⊳

• Określamy funkcję mod

: Z → Z

, {0, 1, . . . , p − 1}

(czytaj: modulo p), p ∈ N:

∀n ∈ Z mod

(n) , reszta z dzielenia n przez p

• Podstawowy związek resztowy, p > 0:

n =

· p + mod

(n)

• Operacje modulo +

−

∗

: Z

× Z

→ Z

x +

, mod

(x + y), x −

, mod

(x − y), x ∗

, mod

(x · y),

gdzie +, · to dodawanie i mnożenie liczb całkowitych

• Jednoargumentowa operacja negacji modulo

−

: Z

→ Z

−

, 0 −

x = p

− x, x ∈ Z

• Odejmowanie modulo przez dodawanie modulo i negację modulo:

−

y = x +

(−

• Własności mod

dla dowolnych x, y ∈ Z :

mod

(x + y) = mod

(mod

(x) + mod

(y))

mod

(x + y) = mod

(x) +

mod

(y)

mod

(−x)

= mod

(− mod

(x)) = mod

(p − mod

(x))

mod

(−x)

= −

mod

(x)

mod

(x − y) = mod

(mod

(x) − mod

(y))

mod

(x − y) = mod

(x) −

mod

(y)

mod

(x · y)

= mod

(mod

(x) · mod

(y))

mod

(x · y)

= mod

(x) ∗

mod

(y)

• Twierdzenie: Funkcja mod

określa homomorﬁzm algebry (Z, 3; +, −, ·) w

algebrę (Z

, 3; +

−

∗

)

• Jeśli p jest liczbą pierwszą to dla dowolnego a

∈ Z

−{0}, równanie a∗

x =

1 ma dokładnie jedno rozwiązanie w zbiorze Z

. Oznaczamy je jako a

−1

Dowód

twierdzenia o elemencie odwrotnym w Z

Niech f (x)

, a ∗

x, x

∈ Z

będzie funkcją argumentu x. Zauważmy, że f : Z

→ Z

i f jest

funkcją różnowartościową bo:

∗

x = a

∗

⇒ p|a(x − y) ⇒ p|a ∨ p|(x − y)

Ponieważ 0 < a < p, to p

6 |a, a więc p|(x−y). Możemy założyć, że x ≥ y. Wtedy 0 ≤ (x−y) < p

i p

|(x − y) tylko wtedy gdy x − y = 0, t.j. gdy x = y.

Skoro funkcja f jest określona na skończonym zbiorze i jest różnowartościowa, więc jest też
odwzorowaniem Z

na Z

Dlatego f

−1

(1) jest zbiorem jednoelementowym, t.j. istnieje dokładnie jeden element x

∈ Z

dla którego f (x) = 1, t.j. a

∗

x = 1.

⊳

Twierdzenie 2.3

o arytmetyce w I

Niech I

, {n ∈ Z : −2

−1

≤ n < 2

−1

} ⊂ Z, p , 2

. Wtedy

• Na zbiorze I

operacje arytmetyczne +, −, · stają się funkcjami częścio-

wymi

• Odwzorowanie mod

ograniczone do zbioru I

jest różnowartościowe i

ma postać dla x ∈ I

mod

(x) =

gdy 0 ≤ x ≤ (p/2) − 1

x + p gdy

− p/2 ≤ x ≤ −1

• Odwzorowanie odwrotne mod

−1

: Z

→ I

ma postać dla dowolnego

∈ Z

mod

−1

(y) =

gdy 0 ≤ y ≤ (p/2) − 1

− p gdy (p/2) ≤ y ≤ p − 1

⊳

Twierdzenie 2.4

o homomorﬁźmie algebr

Odwzorowanie mod

jest homomorﬁzmem różnowartościowym ”na” algebry A

, 3; +,

−, ·) na algebrę B

, (Z

, 3; +

−

∗

), t.j. dla dowolnych x, y ∈ I

z dziedziny operacji po lewej stronie mamy:

mod

(x + y) = mod

(x) +

mod

(y)

mod

(x − y) = mod

(x) −

mod

(y)

mod

(x · y) = mod

(x) ∗

mod

(y)

⊳

Wniosek 2.1

o homomorﬁcznym rozszerzeniu

Określamy homomorﬁczne rozszerzenie arytmetycznych operacji +, −, · na I

x ˜

+y , mod

−1

(mod

(x) +

mod

(y))

x ˜

−y , mod

−1

(mod

(x) −

mod

(y))

x˜

·y , mod

−1

(mod

(x) ∗

mod

(y))

Wtedy mod

jest izomorﬁzmem algebry B

i rozszerzonej algebry A

. ⊳

2.11

Arytmetyka cyfrowa w stałym przecinku

• N – długość rejestru w ALU (w praktyce N = 8, 16, 32, 64)

• Arytmetyka cyfrowa liczb całkowitych standardowo dotyczy działań +,

−, ·

na zbiorze I

• Działania te są wykonywane poprzez arytmetykę modulo +

−

∗

w Z

• Funkcja mod

określa różnowartościowy homomorﬁzm obu algebr

• Liczba n ze zbioru I

jest kodowana na dokładnie N bitach z użyciem

odwzorowania mod

, p = 2

u(n)

N bitów

{

mod

(n)

u(n) nazywa się kodem uzupełnieniowym do dwóch (ang. 2’s complement
to two)

Przykłady dla N = 8: I

= [−128, 127], p = 2

= 256

u(100) =

8 bitów

{

mod

256

(100)=

8 bitów

z}|{

100 = 01100100

−100) =

8 bitów

{

mod

256

(−100)=

8 bitów

{

−100 + 256=

8 bitów

z}|{

156 = 10011100

−128) =

8 bitów

{

mod

256

(−128)=

8 bitów

{

−128 + 256=

8 bitów

z}|{

128 = 10000000

−1) =

8 bitów

{

mod

256

(−1)=

8 bitów

{

−1 + 256=

8 bitów

z}|{

255 = 11111111

• Ustawianie domyślnego stałego przecinka na cyfrze s = 0, . . . , N

− 1 :

–

Dziedzina liczbowa przecinka na cyfrze s :

, I

· 2

−s

, {x ∈ Q : ∃n ∈ I

, x = n

· 2

−s

}

–

Homomorﬁzm algebry A

= (I

, 3; +,

−, ·) z algebrą B

= (Z

, 3; +

−

∗

)

określa następujące odwzorowanie mod

mod

(x) , mod

(x · 2

), x ∈ I

Nazwa kodu u(n) wynika z charakteru odejmowania manualnego od 2

liczby

z przedziału [1, 2

−1

] w systemie dwójkowym, np. dla N = 8, n = −100 mamy:

256 = 1 0 0 0 0 0 0 0 0
256 = 0 1 1 1 1 1 2 0 0

−100 =

0 1 1 0 0 1 0 0

−100) =

1 0 0 1 1 1 0 0

Reguły manualne dla u(n): W zapisie dwójkowym liczby n na N bitach nie
zmieniaj zer na najmłodszych pozycjach i nie zmieniaj najmłodszej jedynki.
Pozostałe cyfry zmień na przeciwne.

2.12

Arytmetyka cyfrowa w zmiennym przecinku

• Arytmetyka w zmiennym przecinku stosuje reprezentację opartą na kon-

cepcji cechy c(x), mantysy m(x) i znaku liczby s(x) dla x ∈ R.

• W standardzie ”IEEE 754 Floating Point Numbers” (w skrócie IEEE 754)

żąda się by mantysa była w przedziale [1, 2) :

x = (

−1)

s(x)

m(x)2

c(x)

, s(x)

∈ {0, 1}, m(x) ∈ [1, 2), c(x) ∈ Z

• Jeśli x

6= 0, to powyższa reprezentacja zmiennoprzecinkowa jest jedno-

znaczna, bo R − {0} można podzielić na przeskalowane przez ±2

, k

∈ Z,

wersje przedziału [1, 2) :

− {0} = (−∞, −1] ∪ (−1, 0) ∪ (0, 1) ∪ [1, ∞)

(−∞, −1] = · · · ∪ (−8, −4] ∪ (−4, −2] ∪ (−2, −1] =

∞

k=0

(−2

k+1

−2

]

(−1, −0) =

−1, −

1
2

∪

−

1
2

−

1
4

∪ · · · =

−∞

−1

(−2

k+1

−2

]

(0, 1) = · · · ∪

1
2

∪

, 1

−∞

−1

, 2

k+1

)

[1, ∞) = [1, 2) ∪ [2, 4) ∪ [4, 8) ∪ · · · =

∞

k=0

, 2

k+1

)

• Jeśli x

∈ [2

, 2

k+1

), k ∈ Z, to s(x) = 0, c(x) = k, m(x) = x/2

• Jeśli x

∈ (−2

k+1

−2

], k ∈ Z, to s(x) = 1, c(x) = k, m(x) = −x/2

• W praktyce mamy ograniczoną liczbę bitów n

na pole cechy i n

bitów

na pole mantysy

• W IEEE 754 cechę c(x) kodujemy jako liczbę c(x) + b, gdzie b jest stałym

przesunięciem dla cechy

• W IEEE 754 struktura słowa zmiennoprzecinkowego ma postać:

precyzja

s(x)

c(x) + b

m(x)

ﬂoat

1 [31]

8 [30-23]

23 [22-00]

127

double

1 [63]

11 [62-52]

52 [51-00]

1023

gdzie pole bitowe opisano w postaci: długość [zakres pozycji bitowych] i tak
dla precyzji pojedynczej (ﬂoat) mamy n

= 8, n

= 23, a dla podwójnej

(double) n

= 11, n

= 52

• W IEEE 754 wiodącą jedynkę mantysy pomija się

• W IEEE 754 dopuszczalny kod cechy c + b

∈ [1, 2

− 2], t.j. kody złożone

z samych zer i z samych jedynek zarezerwowano dla innych celów. Stąd
zakres dopuszczalnych cech wynosi:

∈ [1 − b, 2

− 2 − b]

• W IEEE 754 wartość zapisu liczby x w przypadku mantysy znormalizo-

wanej wynosi:

x = (

−1)

· m · 2

, m

∈ [1, 2 − 2

−n

], c ∈ [1 − b, 2

− 2 − b]

∈ [−2

−2−b

(2 − 2

−n

), −2

−b+1

] ∪ [2

−b+1

, 2

−2−b

(2 − 2

−n

)]

dla n

= 8, n

= 23, b = 127,

∈ [−2

127

(2 − 2

−23

), −2

−126

] ∪ [2

−126

, 2

127

(2 − 2

−23

)]

dla n

= 11, n

= 52, b = 1023,

∈ [−2

1023

(2 − 2

−52

), −2

−1022

] ∪ [2

−1022

, 2

1023

(2 − 2

−52

)]

• W IEEE 754 oprócz mantysy znormalizowanej dopuszczono dla wyróżnio-

nej wartości cechy nie znormalizowany zapis ułamka m w miejscu manty-
sy, z wagą jeden dla najstarszej pozycji (bez domyślnej jedynki), t.j. dla
c + b = 0 wartość zapisu liczby x wynosi:

x = (

−1)

· m · 2

−b

, m

∈ [2

−n

, 2

− 2

−n

]

∈ [−2

−b+1

(1 − 2

−n

), −2

−b−n

] ∪ [2

−b−n

, 2

−b+1

(1 − 2

−n

)]

dla n

= 23, b = 127,

∈ [−2

−126

(1 − 2

−23

), −2

−149

] ∪ [2

−149

, 2

−126

(1 − 2

−23

)]

dla n

= 52, b = 1023,

∈ [−2

−1022

(1 − 2

−52

), −2

−1074

] ∪ [2

−1074

, 2

−1022

(1 − 2

−52

)]

• Reprezentacja zera: pole cechy i mantysy wypełnione zerami, pole znaku

dowolne

• Liczby rzeczywiste R(N, n

) = R(1+n

, n

) reprezentowane w zmien-

nym przecinku w IEEE 754 są postaci zdeﬁniowanej powyżej dla mantysy
znormalizowanej i nie znormalizowanej:

R(N, n

)

, R

(N, n

) ∪ R

(N, n

) ∪ {0},

N = 1 + n

+ n

, b = 2

−1

− 1

(N, n

) , {x : ∃s, k, c ∈ N, x = (−1)

· m · 2

, s

∈ {0, 1},

∈ [1, 2 − 2

−n

], m = 1 + k2

−n

∈ [1 − b, 2

− 2 − b]}

(N, n

) , {x : ∃s, k ∈ N, x = (−1)

· m · 2

−b

, s

∈ {0, 1},

∈ [2

−n

, 2

− 2

−n

], m = k2

−n

}

• Zakresy dla float:

R(32, 8)

, R

(32, 8) ∪ R

(32, 8) ∪ {0},

= 8, n

= 23, b = 127

(32, 8) , {x : ∃s, k, c ∈ N, x = (−1)

· m · 2

, s

∈ {0, 1},

∈ [1, 2 − 2

−23

], m = 1 + k2

−23

, c

∈ [−126, 127]}

(32, 8) , {x : ∃s, k ∈ N, x = (−1)

· m · 2

−b

, s

∈ {0, 1},

∈ [2

−22

, 2

− 2

−22

], m = k2

−22

}

• Zakresy dla double:

R(64, 11)

, R

(64, 11) ∪ R

(64, 11) ∪ {0},

= 52, n

= 11, b = 1023

(64, 11) , {x : ∃s, k, c ∈ N, x = (−1)

· m · 2

, s

∈ {0, 1},

∈ [1, 2 − 2

−52

], m = 1 + k2

−52

, c

∈ [−1022, 1023]}

(64, 11) , {x : ∃s, k ∈ N, x = (−1)

· m · 2

−b

, s

∈ {0, 1},

∈ [2

−51

, 2

− 2

−51

], m = k2

−51

}

• Reprezentacja nieskończoności: same jedynki w polu cechy, same zera w

polu mantysy, pole znaku równe zero dla +∞ i równe jeden dla −∞

• Kategoria NaN (ang. Not a Number)

–

Kategoria QNaN (ang. Quiet Not a Number) – obsługuje argumenty
nie zdeﬁniowane i jest kodowana w polu cechy przez same jedynki, a
w polu mantysy ma jedynkę na pozycji najbardziej znaczącej

–

Kategoria SNaN (ang. Signalling Not a Number) – obsługuje argu-
menty nieprawidłowe i jest kodowana w polu cechy przez same je-
dynki, a w polu mantysy ma zero na pozycji najbardziej znaczącej i
przynajmniej jedną jedynkę na pozostałych pozycjach

• Operacje na argumentach specjalnych:

–

operacja z argumentem NaN ma wynik NaN

–

operacje z argumentem ∞ :

operacja

wynik

± ∞

±∞ · ±∞

±∞

6= 0 → ±x/0

±∞

∞ + ∞

∞

operacja

wynik

±0/ ± 0

NaN

∞ − ∞

NaN

±∞/ ± ∞

NaN

±∞ · 0

NaN

2.12.1

Wzorce bitowe w IEEE 754

kod

(c)

kod

(m)

0 . . . 0

0 . . . 01

1 . . . 1

+bez norm.

0, f · 2

−

b+1

0 . . . 01

1 . . . 10

X . . . X

+z norm.

1, f · 2

−

1 . . . 1

0 . . . 0

+∞

1 . . . 1

0 . . . 01

01 . . . 1

SN aN

1 . . . 1

10 . . . 0

1 . . . 1

QN aN

kod

(c)

kod

(m)

0 . . . 0

−

0 . . . 0

0 . . . 01

1 . . . 1

−

bez norm.

−

0, f · 2

−

b+1

0 . . . 01

1 . . . 10

X . . . X

−

z norm.

−

1, f · 2

−

1 . . . 1

0 . . . 0

−∞

1 . . . 1

0 . . . 01

01 . . . 1

SN aN

1 . . . 1

10 . . . 0

1 . . . 1

QN aN

Schematy rekurencyjne

• Pojęcie schematu rekurencyjnego, t.j. rekursji:

–

Rekursja to specyﬁczny schemat konstrukcji zbiorów typu rekuren-
cyjnego

–

Rekursja składa się z dwóch kroków:

1. krok bazowy: określa obiekty bazowe
2. krok rekurencyjny: konstruuje elementy złożone z elementów prost-

szych

• Przykłady rekursji:

–

rekurencyjne ciągi liczb, np. ciąg Fibonacciego:

= 1, c

n+1

, c

+ c

−1

, n

∈ N

–

rekurencyjne ciągi zbiorów, np. obrazy fraktalne takie jak trójkąt
Sierpińskiego, czy zbiór Cantora C :

C = lim

→∞

= [0, 1], C

n+1

= f

) ∪ f

)

(x) , x/3, f

(x) , (x + 2)/3

–

poprawne wyrażenia języka programowania ze zbioru W, np.

a, b, c, . . . , x, y, z

∈ W – bazowe wyrażenia

∈ W → (w) ∈ W – wyrażenie nawiasowe

, w

∈ W → w

+ w

∈ W, w

− w

∈ W, . . . inne operacje

• drzewa matematyczne:

–

Pojedynczy węzeł w tworzy drzewo T

–

Jeśli T

, . . . , T

są drzewami, a r jest węzłem, to struktura złożona z

węzła r jako korzenia z referencjami na drzewa T

, . . . , T

jest nowym

drzewem T

• Użyteczność rekursji:

–

Funkcje języka programowania mogą realizować rekursje, t.j. proce-
dury rekurencyjne, np. n! oblicza następująca funkcja języka C:
int silnia(int n) { if (n == 0) return 1; else return n∗silnia(n − 1); }

–

Jeśli zbiór Z jest budowany rekurencyjnie ze zbioru bazowego Z

, to

prawdziwość zdania typu ∀x ∈ Z, P (x) dowodzi się techniką ogólnej

indukcji matematycznej złożoną z dwóch kroków:

1. podstawa indukcji:

dowodzimy prawdziwości P (x) dla wszystkich x ∈ Z

2. krok indukcyjny: jeśli element x jest zbudowany rekurencyjnie z

elementów x

, . . . , x

, to dowodzimy prawdziwości implikacji

[P (x

) ∧ · · · ∧ P (x

)] → P (x)

Przykład 3.1

Palindromy

Rozważmy palindromy nad alfabetem Σ, t.j. słowa, które czytane od lewej i od
prawej mają tą samą postać. Niech słowo puste E i pojedynczy symbol będą też
palindromem. Pokażemy, że zbiór P

wszystkich palindromów można zbudować

następującym schematem rekurencyjnym:

1. krok bazowy:

∈ P, ∀σ ∈ Σ, σ ∈ P

2. krok rekurencyjny:

∀σ ∈ Σ, x ∈ P → σxσ ∈ P

Zauważmy, że elementy bazowe ze zbioru są palindromami z deﬁnicji. Jeśli x jest
palindromem, to konstrukcja σxσ daje również palindrom. Stąd mamy P ⊂ P

Jeśli wyrażenie x jest palindromem, t.j. x ∈ P

, to można je zbudować z E lub

z symbolu środkowego (przypadki parzystej lub nieparzystej długości) stosując
krok rekurencyjny. Stąd również zachodzi przeciwna inkluzja P

⊂ P.

⊳

Przykład 3.2

Zbalansowane wyrażenia nawiasowe

Zbalansowane wyrażenia nawiasowe ze zbioru B budujemy tylko z symboli na-

wiasów ’(’ oraz ’)’ stosując następujący schemat rekurencyjny:

1. krok bazowy: E ∈ B – symbol pusty jest wyrażeniem nawiasowym
2. krok rekurencyjny 1: x ∈ B → (x) ∈ B
3. krok rekurencyjny 2: x, y ∈ B → xy ∈ B

Niech w ∈ B, w = w

. . . w

, w

∈ {(, )}. Określamy ciąg liczb L

) jako liczbę

lewych (prawych) nawiasów na pozycjach 1, . . . , i.
W praktyce często wykorzystujemy następującą własność zbalansowanych wy-
rażeń nawiasowych:

≥ P

, i = 1, . . . n

− 1, L

= P

(1)

Oznaczmy przez B

zbiór wyrażeń nawiasowych spełniających powyższą wła-

sność.
Pokażemy najpierw, że B ⊂ B

. W kroku rekurencyjnym pierwszym w wyrażeniu

(x) mamy na pozycji i-tej, 2 ≤ i ≤ n − 1 :

= 1 + L

−1

(x) ≥ 1 + P

−1

(x) = 1 + P

> P

gdzie L

(x) (P

(x)) dotyczy wartości analizowanych tylko dla części x.

Dla i = 1 : L

= 1 > P

= 0. Zaś dla i = n :

= 1 + L

−1

(x) = 1 + P

−1

(x) = P

Pokazaliśmy więc, że (x) spełnia warunek (1), t.j. (x) ∈ B

Podobnie pokazujemy, że jeśli x, y ∈ B spełniają warunek (1), to wyrażenie xy

również spełnia warunek (1). Dlatego B ⊂ B

Przypuśćmy teraz, że jakieś wyrażenie w ∈ B

, t.j. spełnia warunek (1). Musimy

pokazać, że da się ono zbudować stosując kroki rekurencyjne 1 oraz 2.
Wiemy, że jest to prawda dla najkrótszego wyrażenia x = (), bo budujemy je z
E stosując krok 1. Przypuśćmy, że

|x| > 2 i że wyrażenia x

′

∈ B

krótsze od x,

t.j. |x

′

| < |x| pokazaliśmy konstrukcję opartą na krokach rekurencyjnych 1 i 2,

t.j. x

′

∈ B. Wtedy x mamy dwa przypadki:

1. x jest postaci x = (x

′

), x

′

∈ B

i wtedy możemy zastosować krok 1 do

′

∈ B,

2. możemy x podzielić na części x = x

. . . x

, z których każda spełnia

warunek (1), t.j. x

∈ B

. Punkty podziału dostajemy tam gdzie L

= P

Wtedy każda z tych części (jako krótsza od x) należy do B i stosując

rekurencyjny krok 2 k − 1 razy wnioskujemy, że również x ∈ B.

Pokazaliśmy więc inkluzję przeciwną B

⊂ B. W efekcie B = B

. ⊳

3.1

Wieże Hanoi

Problem Wieże Hanoi:
Zabawa w wieże Hanoi wymaga pewnej liczby n pierścieni o różnych promieniach
zewnętrznych R

· · · > R

, i stałym promieniu wewnętrznym r

= · · · = r

r < R

, dużo mniejszym niż rozmiar każdego pierścienia, ale na tyle dużym

by pierścienie mogły być nałożone przez swoje wewnętrzne otwory na szkielet
wieży złożonej z pionowego pręta i nieruchomej podstawy. Dysponujemy trzema
takimi szkieletami o numerach 1, 2, 3. Początkowo wszystkie pierścienie tworzą
wieżę numer 1 w ten sposób, że największy leży na podstawie szkieletu 1 i kolejne
mniejsze pierścienie spoczywają na większych. Zadanie polega na przeniesieniu
wszystkich pierścieni, jeden po drugim, z wieży numer 1 na wieżę numer 3 z
wykorzystaniem wieży 2 w ten sposób by nigdy większy pierścień nie był położony
na pierścieniu mniejszym.
Oznaczmy polecenie przeniesienia krążka z wieży i na wieżę j przez i → j;

Wtedy rozwiązanie dla n = 1 ma trywialną postać: 1 → 3;

Dla n = 2 wykorzystamy wieżę 2 : 1 → 2; 1 → 3; 2 → 3;

Dla n = 3 mamy 7 poleceń:

1 → 3; 1 → 2; 3 → 2; 1 → 3; 2 → 1; 2 → 3; 1 → 3;

Schemat rekurencyjny HanoiT owers(i, j, n) jest procedurą, która ma wygene-
rować sekwencję poleceń przenosząca n pierścieni z wieży i na wieżę j.

1. krok bazowy dla n = 1:

(a) i → j;

(b) zakończenie;

2. krok rekurencyjny dla n > 1:

(a) niech k będzie numerem trzeciej wieży różnej od i oraz j

(b) HanoiT owers(i, k, n − 1);

(d) HanoiT owers(k, j, n − 1);

(e) zakończenie;

Ślad procedury uwzględnia następujące fakty:

• Każde wykonanie procedury oznacza utworzenie nowej kopii parametrów

procedury (tu dla i, j, n) i zmiennych pomocniczych (tu tylko dla k)

• W kopii parametrów wpisujemy wartości argumentów aktualnego wywo-

łania procedury, a w kopii lokalnych zmiennych wartości aktualne dla tego
wykonania procedury

• Zakończenie procedury skutkuje usunięciem kopii parametrów i lokalnych

zmiennych

• Podobne zarządzanie pamięcią dotyczy aktualnego kroku jaki jest wyko-

nywany w ramach łańcucha wywołań procedur

• Zmienna pomocnicza t oznacza długość aktywnego łańcucha wywołań pro-

cedur jeszcze nie zakończonych

• Zawsze mamy w pamięci t kopii parametrów i zmiennych lokalnych (u nas

, j

, n

, k

; . . . ; i

, j

, n

, k

)

• Aktualnie wykonywana procedura korzysta jako ostatnia w łańcuchu wy-

wołań procedur z t-tej kopii parametrów i zmiennych lokalnych

Poniższa tabela opisuje ślad wywołania HonoiT owers(1, 3, 2)

aktualnekroki t

, j

, n

, k

; . . . ; i

, j

, n

, k

polecenie

2.(a)

1 1, 3, 2, 2

2.(b); 1.(a)

2 1, 3, 2, 2; 1, 2, 1, −

1 → 2

2.(b); 1.(b)

1 1, 3, 2, 2

2.(c)

1 1, 3, 2, 2

1 → 3

2.(d); 1.(a)

2 1, 3, 2, 2; 2, 3, 1, −

2 → 3

2.(d); 1.(b)

1 1, 3, 2, 1

2.(e)

Zadanie: Zapisz procedurę rekurencyjną silnia(n) i utwórz tabelę śladu wyko-
nania silnia(4).
Kolejna tabela opisuje ślad wywołania HonoiT owers(1, 3, 3)

kroki

, j

, n

, k

; . . . ; i

, j

, n

, k

polecenie

2.(a)

1 1, 3, 3, 2

2.(b); 2.(a)

2 1, 3, 3, 2; 1, 2, 2, 3

2.(b); 2.(b); 1.(a)

3 1, 3, 3, 2; 1, 2, 2, 3; 1, 3, 1, −

1 → 3

2.(b); 2.(b); 1.(b)

2 1, 3, 3, 2; 1, 2, 2, 3

2.(b); 2.(c)

2 1, 3, 3, 2; 1, 2, 2, 3

1 → 2

2.(b); 2.(d); 1.(a) 3 1, 3, 3, 2; 1, 2, 2, 3; 3, 2, 1, −

3 → 2

2.(b); 2.(d); 1.(b)

2 1, 3, 3, 2; 1, 2, 2, 3;

2.(b); 2.(e)

1 1, 3, 3, 2

2.(c)

1 1, 3, 3, 2

1 → 3

2.(d); 2.(a)

2 1, 3, 3, 2; 2, 3, 2, 1

2.(d); 2.(b); 1.(a) 3 1, 3, 3, 2; 2, 3, 2, 1; 2, 1, 1, −

2 → 1

2.(d); 2.(b); 1.(b)

2 1, 3, 3, 2; 2, 3, 2, 1

2.(d); 2.(c)

2 1, 3, 3, 2; 2, 3, 2, 1

2 → 3

2.(d); 2.(d); 1.(a) 3 1, 3, 3, 2; 2, 3, 2, 1; 1, 3, 1, −

1 → 3

2.(d); 2.(d); 1.(b) 2 1, 3, 3, 2; 2, 3, 2, 1
2.(d); 2.(e)

1 1, 3, 3, 2

2.(e)

Własność 3.1

O liczbie poleceń w problemie Wieże Hanoi

Niech p(n) będzie liczbą poleceń generowanych przez procedurę HanoiT owers(i, j, n).
Wtedy

1. p(1) = 1

2. p(n) = p(n − 1) + 1 + p(n − 1)
3. p(n) = 2

− 1

⊳

Zadanie: Sprawdź słuszność powyższych własności funkcji p(n).

3.2

Konwersja wyrażenia arytmetycznego na ONP

• Notacja arytmetyczna (NA), np.: a + b, a + b

∗ c, (a + b) ∗ c

• Notacja Polska (NP), np.: +ab, +a

∗ bc, ∗ + abc

• Odwrotna Notacja Polska (ONP), np.: ab+, abc

∗ +, ab + c∗

• Przykłady równoważnych wyrażeń:

ONP

a/b

/ab

ab/

a + b

− c

− + abc

ab + c

−

a/b

∗ c

∗/abc

ab/c

∗

∗ b/c

∗ abc

∗ c/

− b/c

−a/bc

abc/

−

(a − b)/c

− abc

− c/

a + b

∗ (c − d/a)

+a ∗ b − c/da

abcda/

− ∗+

(c/d + a) ∗ (b − d/a) ∗ + /cda − b/da cd/a + bda/ − ∗

Obserwacje:

• Kolejność występowania zmiennych w NA, NP i ONP jest taka sama

• Kolejność wykonywania operacji w NA uwzględnia położenie nawiasów,

priorytety i reguły łączenia operacji o jednakowych priorytetach

• Kolejność występowania operacji w ONP jest taka sama jak kolejność wy-

konywania operacji w NA

• Tabela priorytetów i reguł łączenia:

poziom operacje reguły łączenia

∗ /

od prawej

+ −

od lewej

• Symbol operacji w NA mają poziom zagnieżdżenia określony przez liczbę

−

− P

−

, gdzie L

−

) jest liczbą lewych (prawych) nawiasów wystę-

pujących przed daną operacją, np. w wyrażeniu (c/d + a) ∗ (b − (d + c)/a)

kolejne operacje / + ∗ − +/ mają poziomy zagnieżdżenia równe odpowied-

nio 1, 1, 0, 1, 2, 1

Przesłanki do algorytmu NA → ONP :

• Zakładamy sekwencyjny przegląd symboli wyrażenia w typu NA, kolejno

od lewej do prawej

• Pojawienie się symbolu zmiennej oznacza jej kopiowanie na wyjście u

• Zmiana porządku symbolu operacji o i jej drugiego argumentu wymaga

zapamiętania o w jakiejś strukturze danych s, np. dla w postaci a/(b+a∗c),

operacja / zapamiętywana jest w s

• Drugi argument operacji o może być też złożonym wyrażeniem i dlatego do

s mogą być dopisywane kolejne operacje, które będą usuwane z s wcześniej
niż symbol o

• Struktura danych ma własność stosu, który działa według zasady ostatni

zapisany – pierwszy skasowany (ang. LIFO – Last In First Out)

• Ponieważ nawiasy, priorytety i zasady łączności ustalają kolejność opera-

cji, to powinniśmy dołączyć dodatkowe reguły obsługi stosu s :

1. Pojawienie się prawego nawiasu ) oznacza wycofanie z s na wyjście

u wszystkich operacji z tego poziomu zagnieżdżenia

2. Pojawienie się lewego nawiasu ( oznacza jego automatyczne zapa-

miętanie w s, co pozwoli na łatwą identyﬁkację wszystkich symboli
operacji zapisanych w s z aktualnego poziomu zagnieżdżenia

3. Pojawienie się operacji o

next

o niższym priorytecie niż ostatnia ope-

racja o

top

na stosie s oznacza wycofanie o

top

z s na wyjście u

4. Pojawienie się operacji o

next

o tym samym priorytecie co ostatnia

operacja o

top

na stosie s, ale o regule łączenia od lewej oznacza wy-

cofanie o

top

z s na wyjście u

Algorytm 3.1

konwersji NA → ONP

• Wejście: poprawne wyrażenie typu NA

x = x

. . . x

, x

∈ {a, . . . , z, (, ), +, −, ∗, /}

Dla uproszczenia zapisu algorytmu zakładamy, że x

′

(

′

, x

′

)

′

• Wyjście: wyrażenie typu ONP

y = y

. . . y

, y

∈ {a, . . . , z, +, −, ∗, /}

• Metoda:

1. Przygotuj wskaźniki bieżącej pozycji:

–

i – dla wejścia w

–

← 0 – dla wyjścia u

–

← 0 – dla stosu s

2. Dla i = 1, . . . , n :

(a) Przypadek x

∈ {a, . . . , z} : j ← j + 1; y

← x

;

(b) Przypadek x

′

(

′

: t ← t + 1; s

← x

′

)

′

i. póki s

′

(

′

wykonuj: j ← j + 1; y

← s

; t ← t − 1;

ii. t ← t − 1

(d) Przypadek x

∈ {+, −, ∗, /}

i. póki s

∈ {+, −, ∗, /} oraz (prty(s

) > prty(x

) lub prty(s

) =

prty(x

) i obowiązuje reguła łączenia od lewej dla operacji s

i x

) wykonuj:

← j + 1; y

← s

; t ← t − 1;

ii. Wprowadź x

na stos: t ← t + 1; s

← x

⊳

Ślad algorytmu NA → ONP na wyrażeniu ((c/d + a) ∗ (b − d + c)/d)

krok

. . . s

(

2.(b)

1 (

(

2.(b)

2 ((

2.(a)

2.(d)ii.

3 ((/

2.(a)

+ 2.(d)i − ii. 3 ((+

2.(a)

)

2.(c)i − ii. 1 (

∗

2.(d)ii.

2 (∗

10 (

2.(b)

3 (∗(

11 b

2.(a)

12 − 2.(d)ii.

4 (∗(−

13 d

2.(a)

14 + 2.(d)i − ii. 4 (∗(+

−

15 c

2.(a)

16 )

2.(c)i − ii. 2 (∗

17 /

2.(d)ii.

3 (∗/

18 d

2.(a)

19 )

2.(c)i − ii. 0

12 − 13 /∗

Wynik konwersji ((c/d + a) ∗ (b − d + c)/d) na ONP:

. . . y

= cd/a + bd − c + d/∗

3.3

Generowanie kodu maszynowego wyrażenia arytme-
tycznego

• Prosty model maszyny (PMM):

–

pamięć MEM złożona z N słów maszynowych o adresach 0, 1, 2, . . . , N−

1, np. N = 2

M EM [0], M EM [1], . . . , M EM [N

− 1]

–

akumulator R

, tj. wyróżniony rejestr, w którym przed wykonaniem

operacji arytmetycznej znajduje się pierwszy argument, a po jej wy-
konaniu wynik operacji

–

rejestr wierzchołka (ang. top) stosu programu R

–

jednostka centralna z repertuarem instrukcji:

∗ Instrukcje z adresowaniem bezpośrednim

instrukcja

efekt działania

LOAD X

← MEM[@X]

SAVE X

M EM [@X]

← R

ADD X

← R

+ MEM[@X]

SUB X

← R

− MEM[@X]

MUL X

← R

∗ MEM[@X]

DIV X

← R

/M EM [@X]

gdzie @X oznacza adres zmiennej X.

∗ Instrukcje stosowe

instrukcja

efekt działania

PUSH

M EM [R

] ← R

; R

← R

+ 1

POP

← R

− 1; R

← MEM[R

]

POP2

← R

− 1; R

← MEM[R

− 1];

M EM [R

− 1] ← MEM[R

]

ADD *T

← R

− 1; R

← R

+ MEM[R

]

SUB *T

← R

− 1; R

← R

− MEM[R

]

MUL *T

← R

− 1; R

← R

∗ MEM[R

]

DIV *T

← R

− 1; R

← R

/M EM [R

]

–

Przykład kodu dla PMM umieszczającego na stosie programu wartość
wyrażenia (A + B) ∗ C − D :

kod

wyniki ONP

LOAD A

A w R

ADD B

AB+ w R

MUL C

AB+C* w R

SUB D

AB+C*D- w R

PUSH

AB+C*D- na stosie

–

Przykład o bardziej złożonej interakcji ze stosem:
NA – A ∗ C/(B − C + D), ONP – ACBC − D + /∗

kod

wyniki ONP

LOAD B

B w R

SUB C

BC- w R

ADD D

BC-D+ w R

PUSH

BC-D+ na stosie

LOAD C

C w R

DIV *T

CBC-D+/ w R

PUSH

CBC-D+/ na stosie

LOAD A

A w R

MUL *T

ACBC-D+/* w R

PUSH

ACBC-D+/* na stosie

Algorytm 3.2

ON P

→ CODE

• s – stos zmiennych aktualizowany z ONP y = y

. . . y

• $ – dodatkowy symbolem oznaczający aktualny wierzchołek stosu

1. Przygotuj wskaźniki bieżącej pozycji:

–

j – dla ONP

–

← 0 – dla stosu s

2. Dla j = 1, . . . , J :

(a) Przypadek y

jest symbolem zmiennej: t ← t + 1; s

← y

(b) Przypadek y

jest symbolem operacji:

← s

−1

; v

← s

; t ← t − 1; s

←

′

;

i. Przypadek v

, v

zawierają symbole zmiennych: generuj kod

LOAD v

; y

; PUSH;

gdzie v

jest symbolem zapisanym w v

, i = 1, 2, a y

jest

tekstem ADD gdy y

′

, SUB gdy y

′

−

′

, MUL gdy

′

∗

′

, DIV gdy y

′

ii. Przypadek v

jest symbolem zmiennej, v

′

: generuj kod

LOAD v

; y

∗ T ; PUSH;

iii. Przypadek v

jest symbolem zmiennej, v

′

generuj kod

POP ; y

; PUSH;

iv. Przypadek v

′

, v

′

: generuj kod

POP2 ; y

∗ T ; PUSH;

3. W kodzie usuń wszystkie pary kolejnych instrukcji postaci ”PUSH;

POP;”

4. W kodzie usuń wszystkie pary kolejnych INSTRUKCJI postaci ”PUSH

; POP2;” o ile kolejna instrukcji jest postaci ”ADD *T” lub postaci
”MUL *T”

⊳

Ślad algorytmu ONP → CODE na wyrażeniu CD/A + BD − C + D/∗

krok

. . . s

generowany kod

2.(a)

1 C

2.(a)

2 CD

2.(b)i.

1 $

LOAD C; DIV D; PUSH;

2.(a)

2 $A

+ 2.(b)iii. 1 $

POP ; ADD A; PUSH;

2.(a)

2 $B

2.(a)

3 $BD

− 2.(b)i.

2 $$

LOAD B; SUB D; PUSH;

2.(a)

2 $$C

10 + 2.(b)iii. 2 $$

POP ; ADD C; PUSH;

11 D 2.(a)

3 $$D

12 /

2.(b)iii. 2 $$

POP ; DIV D; PUSH;

13 ∗

2.(b)iv. 1 $

POP2 ; MUL *T; PUSH;

Po kroku 3 usuwającym pary ”PUSH; POP” oraz kroku 4 usuwającym pary
”PUSH; POP2” (przed ”MUL”) wygenerowany kod ma postać:

LOAD C
DIV D
ADD A
PUSH
LOAD B
SUB D
ADD C
DIV D
MUL *T
PUSH

Zauważmy, że w tym przykładzie automatycznie wygenerowany kod jest opty-
malny w sensie ilości instrukcji.

3.4

Klasyczna indukcja matematyczna

• Ogólny schemat indukcji matematycznej:

Jeśli zbiór Z jest budowany rekurencyjnie ze zbioru bazowego Z

, to praw-

dziwość zdania typu ∀x ∈ Z, P (x) dowodzi się techniką ogólnej indukcji

matematycznej złożoną z dwóch kroków:

1. podstawa indukcji:

dowodzimy prawdziwości P (x) dla wszystkich x ∈ Z

2. krok indukcyjny: jeśli element x jest zbudowany rekurencyjnie z ele-

mentów x

, . . . , x

, to dowodzimy prawdziwości implikacji

[P (x

) ∧ · · · ∧ P (x

)] → P (x)

• Klasyczna indukcja matematyczna przyjmuje następujące założenia:

–

Z = N

∪ {0}, Z

= {0}

–

n > 0

→ n = (n−1)+1 – zasada budowy większych liczb z mniejszych

pozwala na konstrukcję:

n = 0 + 1 +

· · · + 1

–

Prawdziwość zdania ∀n ≥ n

, P (n) uzasadniamy dowodząc prawdzi-

wości:

1. podstawy indukcji dla n

∈ Z : P (n

) jest zdaniem prawdziwym

2. kroku indukcyjnego dla n > n

w postaci ogólnej:

[∀n

≤ k < n, P (k)] → P (n)

3. lub kroku indukcyjnego dla n > n

w postaci szczególnej:

P (n

− 1) → P (n)

3.4.1

Indukcja matematyczna – wybrane przykłady

Przykład 3.3

Wzór na sumę kwadratów liczb parzystych

Dowodzimy prawdziwości równości:

k=1

(2k)

2
3

n(n + 1)(2n + 1)

Niech L(n) – lewa strona równości, P(n) – prawa strona równości, predykat
P (n) :

P (n)

, L(n) = P(n)

Podstawa indukcji n

= 1 :

L(1) = (2 · 1)

= 2

= 4, P(1) =

2
3

1 · 2 · 3 = 4, → L(1) = P(1) → P (1)

Krok indukcyjny dla n > 1.
Załóżmy P (n − 1), t.j. L(n − 1) = P(n − 1). Wtedy

L(n) = L(n − 1) + (2n)

= P(n − 1) + (2n)

2
3

(n − 1)n(2n − 1) + 4n

2
3

n[(n

− 1)(2n − 1) + 6n] =

2
3

n(n + 1)(2n + 1) =

P(n)

W takim razie z założenia P (n − 1) wynika L(n) = P(n), t.j. P (n). Zauważmy

przy okazji, że w kroku indukcyjnym wnioskujemy z pierwszej linii mamy:

n(n + 1)(2n + 1) =

3
2 L

(n) = (n − 1)n(2n − 1) + 6n

A to jest krok indukcyjny do dowodu tego, że każdy wyraz ciągu n(n+1)(2n+1)
jest podzielny przez 6. ⊳

Zadania:
Pokaż metodą indukcji matematycznej prawdziwość następujących równości cząst-
kowych sum szeregów liczbowych:

n
k=1

(3k − 2) = n(3n − 1)/2

n
k=1

k(k + 1) = n(n + 1)(n + 2)/3

n
k=1

k(k

− 1) = (n − 1)n(n + 1)/3

n
k=1

= n(n + 1)(2n + 1)/6

n
k=1

(−1)

= (−1)

n(n + 1)/2

n
k=1

k(k + 1)(k + 2) = n(n + 1)(n + 2)(n + 3)/4

n
k=1

k(k

− 1)(k − 2) = (n − 2)(n − 1)n(n + 1)/4

n
k=1

2/(k + 2)k = 3/2 − (2n + 3)/(n + 1)(n + 2)

n
k=1

1/(2k − 1)(2k + 1) = n/(2n + 1)

10.

n
k=1

1/(3k − 2)(3k + 1) = n/(3n + 1)

11.

−1

k=0

1/(n + k)(n + k + 1) = 1/2n

12.

−1

k=0

1/(n − 2k)(n − 2k + 2) = n/(4 − n

) dla nieparzystych n > 0

Zadania:
Pokaż metodą indukcji matematycznej prawdziwość następujących własności:

1. Ogólne prawo de Morgana:

[

k=1

2. 2

> n

dla n > 4

n
k=1

√

k >

√

n dla n > 1

4. 4|(3

+ 1) dla nieparzystych n > 0

5. 5|(2 · 4

+ 3 · 9

) dla n ≥ 0

6. 7|(2

n+2

+ 3

2n+1

) dla n ≥ 0

7. 13|(4

2n+1

+ 3

n+2

) dla n ≥ 0

8. Jeśli c

= c

= 1, c

= 3 oraz dla n > 2 c

= 3c

−1

− 3c

−2

+ c

−3

, to

= n

− n + 1 dla n ≥ 0

Przykład 3.4

Istnienie łańcucha zwycięstw w turnieju

Rozważmy turnieje sportowe , w których każdy gracz spotyka się z każdym i
każda gra dwóch przeciwników kończy się zwycięstwem jednego z nich. Łańcuch
zwycięstw długości k, dotyczy k graczy G

, . . . , G

i ma miejsce gdy gracz G

pokonał gracza G

, G

wygrał z G

, . . . , G

−1

okazał się lepszy od G

. Pokaże-

my, że w każdym takim turnieju z n uczestnikami można zawsze zidentyﬁkować
łańcuch zwycięstw długości n.
Baza indukcji dla n

= 3. Niech gracze A, B, C uczestniczą w turnieju. Jeśli

A wygrał z B to zapisujemy ten fakt jako A

→ B. Po jego zakończeniu mamy

dwie możliwości:

1. Jeden z graczy pokonał pozostałych. Np. A → B, A → C i wtedy gdy

→ C, to łańcuch zwycięstw ma postać A → B → C, w przeciwnym

razie A → C → B.

2. Każdy z graczy ma po jednym zwycięstwie i jednej porażce. Np. B → A i

→ C i wtedy łańcuch zwycięstw to B → A → C.

Krok indukcyjny dla n > 3. Po zakończeniu turnieju wybierzmy dowolnego gra-
cza X, który ma przynajmniej jedno zwycięstwo i przynajmniej jedną porażkę.
Taki gracz istnieje, bo jego brak oznaczałoby, że w turnieju są tylko dwie ka-
tegorie graczy – ci, którzy wygrali wszystkie spotkania oraz ci, którzy odnieśli
same porażki. Ale w każdej z tych kategorii może znaleźć się co najwyżej jeden
gracz. Wtedy liczba wszystkich graczy n musiałaby wynosić co najwyżej dwóch
graczy, wbrew założeniu, że n > 3.
Gracz X określa dwie kategorie graczy:

1. W zbiorze W znajdują się gracze, z którymi X wygrał

2. W zbiorze P są ci przeciwnicy, z którymi X przegrał

Ponieważ liczność n

= |P| jest mniejsza niż n, to z założenia indukcyjnego

istnieje w zbiorze P łańcuch zwycięstw:

→ . . . → P

Podobnie możemy znaleźć łańcuch zwycięstw w zbiorze W :

→ . . . → W

gdzie n

= n − 1 − n

Budowa łańcucha zwycięstw dla wszystkich graczy jest teraz prosta. Ma on
bowiem następującą postać:

→ . . . → P

→ X → W

→ . . . → W

⊳

Przykład 3.5

Liczba obszarów określonych przez n prostych na płaszczyźnie

Mówimy, że proste p

, . . . , p

są w położeniu ogólnym, gdy każda para p

, p

ma punkt przecięcia, ale żadna trójka prostych nie przecina się w jednym punk-
cie. Pokażemy, że liczba obszarów L(n), na które dzieli płaszczyznę zestaw n
prostych będących w położeniu ogólnym wynosi:

L(n) = 1 +

n(n + 1)

Baza indukcji dla n

= 2. Ponieważ prosta p

dzieli na dwie części każdą z

półpłaszczyzn określonych przez prostą p

, to dwie prostą dzielą płaszczyznę na

cztery obszary i wzór na L(n) jest prawdziwy dla n = 2, bo L(2) = 1 + 3 = 4.
Krok indukcyjny dla n > 2.
Załóżmy, że proste p

, . . . , p

−1

dzielą płaszczyznę na L(n−1) obszarów. Dodat-

kowa prosta p

przecina proste p

, . . . , p

−1

w pewnych n−1 różnych punktach.

Punkty te możemy uporządkować według kolejności występowania na prostej
p

. Wtedy kolejne punkty przecięcia X

, . . . , X

−1

leżą na granicach n obszarów

, R

, . . . , R

−1

, z których każdy jest dzielony na dwie części przez prostą p

leży na granicy między R

−1

a R

, i = 1, . . . , n

− 1.

W ten sposób zamiast n starych obszarów pojawia się 2n nowych, tzn. liczba
obszarów wzrasta o n. Stąd

L(n) = L(n

− 1) + n = 1 +

(n − 1)n

+ n = 1 +

n(n + 1)

i wzór na L(n) ma żądaną postać. ⊳

Problemy:

1. Mówimy, że zbiór płaszczyzn znajduje się w położeniu ogólnym, gdy każ-

de dwie się przecinają, a przecięcie dowolnych trzech nie tworzy prostej.
Pokaż, że n płaszczyzn w przestrzeni trójwymiarowej, które znajdują się
w położeniu ogólnym dzieli przestrzeń na 2 + (n − 1)n obszarów.

2. Pokaż, że w wielokącie wypukłym o n wierzchołkach suma kątów mię-

dzy kolejnymi bokami wynosi (n − 2)180

◦

. Uwaga: Figura jest wypukła

gdy każdy odcinek łączący jej dwa dowolne punkty całkowicie się w niej
zawiera.

3. Małżeństwo, pan X i pani Y, zaprosiło na przyjęcie n par małżeńskich.

Po początkowych powitaniach polegających na wzajemnym podaniu rąk,
pan X zapytał pozostałe 2n + 1 osób z iloma osobami wymieniły uścisk
dłoni. Ku swojemu zdziwieniu otrzymał 2n + 1 różnych odpowiedzi, t.j.
każda osoba przywitała się z inną liczbą osób. Wiadomo, że małżonkowie
nie podawały sobie rąk. Pokaż przez indukcję, że pani Y (małżonka pana
X) przywitała się z dokładnie n osobami?
Wskazówka: Rozważ małżeństwo, w którym jeden z partnerów przywitał
się z maksymalną liczbą osób, t.j. z 2n osobami. Z iloma osobami przywitał
się partner tej osoby? Jak wpływa na liczbę różnych odpowiedzi usunięcie
tej pary z obliczeń?

1. Budujemy przykładowy graf płaski na mapie powiatów polskich. Krawędź

takiego grafu jest wyznaczona przez wspólną granicę dwóch powiatów lub
przez granicę powiatu i granicę Polski. Koniec takiej wspólnej granicy na-
zywamy wierzchołkiem grafu. Zauważmy, że za wyjątkiem wierzchołków
znajdujących się na granicy państwa, wierzchołki grafu znajdują na gra-
nicy przynajmniej trzech powiatów.
W terminologii grafów powiat jest regionem wyznaczonym na płaszczyź-
nie przez krawędzie grafu. Graf powiatów jest płaskim grafem spójnym bo
istnieje droga wzdłuż jego krawędzi między dwoma dowolnymi wierzchoł-
kami. W naszym przykładzie regionem też jest obszar znajdujący się poza
obszarem państwa polskiego.
Na mapie Unii Europejskiej obszar poza Unią składałby się z więcej niż
jednego regionu, a jednym z nich byłaby Szwajcaria. Regiony w takim
podejściu łączą się tylko na granicach i pokrywają całą płaszczyznę.
Niech r będzie liczbą regionów w płaskim graﬁe spójnym o k krawędziach
i n wierzchołkach. Pokaż metodą indukcji ogólnej, że obowiązuje następu-
jący związek Eulera:

− k + r = 2

Wskazówka: Jak wpływa na wyrażenie n − k + r usunięcie dowolnej kra-

wędzi z grafu?

3.4.2

Obliczanie sum metodą różnic

Lemat 3.1
Jeśli a

jest ciągiem arytmetycznym o różnicy r, to dla m ≤ n :

k=m

k+1

1
r

−

n+1

⊳

Dowód:

Zauważmy, że:

1
r

−

Dlatego

1
r

−

1
r

−

· · · +

−1

−

1
r

−

· · · +

−1

−

1
r

−

⊳

Przykład 3.6

Pokażemy, że suma

k=1

n(n + 1)

n + 1

Ponieważ a

= n jest ciągiem arytmetycznym o różnicy r = 1, to z powyższego

lematu mamy:

k=1

n(n + 1)

1
r

−

n+1

1
1

1 −

n + 1

⊳

Zadania:
Pokaż metodą różnic:

n
k=1

1/(2k − 1)(2k + 1) = n/(2n + 1)

n
k=1

1/(3k − 2)(3k + 1) = n/(3n + 1)

−1

k=0

1/(n + k)(n + k + 1) = 1/2n

−1

k=0

1/(n − 2k)(n − 2k + 2) = n/(4 − n

) dla nieparzystych n > 0

3.5

Równania rekurencyjne

• Przykład równania rekurencyjnego deﬁniującego ciąg Fibonacciego:

, 0, F

, 1, ∀n ≥ 2, F

, F

−1

+ F

−2

• Szukamy rozwiązania F

w postaci jawnej, np. jako liniowej kombinacji

funkcji postaci r

, gdzie r

∈ R znajdujemy z równania:

= r

−1

+ r

−2

, 1 = r + r

Rozwiązanie równania r

+ r − 1 = 0 :

= −

1 −

√

, r

= −

1 +

√

• Szukamy współczynników c

, c

, takich, że F

, c

+ c

spełnia wa-

runki początkowe F

= 0, F

= 1 :

+ c

= 0, c

+ c

= 1

Stąd c

= −c

, c

= 1/(r

− r

) = −1

√

5/5 i

√

−1 +

√

−

−1 −

√

Własność 3.2

Ciąg Fibonacciego

1. F

n+1

−1

− F

= (−1)

, n

≥ 1.

Dowód: Niech c

, F

n+1

−1

− F

. Dla n = 1, c

= −1. Dla n + 1,

wyrażenie ma postać:

n+1

= F

n+2

− F

n+1

= (F

n+1

+ F

− F

n+1

= F

n+1

− F

n+1

) + F

= −(F

n+1

−1

− F

) = −c

To jest kolejny wyraz tego ciągu jest negacją poprzedniego, a ponieważ
pierwszy wyraz wynosi −1, więc c

= (−1)

2. F

n+1

oraz F

są liczbami względnie pierwszymi.

Dowód: Jeśli p|F

oraz p|F

n+1

, to p

n+1

−1

− F

= (−1)

. Stąd p = 1

co dowodzi naszej tezy.

3. F

= F

−m+1

+ F

−1

−m

dla n ≥ m ≥ 1.

Dowód: Zauważmy, że z tego, że F

= 0, równanie jest spełnione dla do-

wolnego m = n oraz dla m = 1, a w szczególności dla n = 2.
Pokażemy teraz prawdziwość równości dla n + 1 jeśli jest ona prawdziwa
dla n

′

≤ n. Mamy bowiem dla m ≥ 2 i m ≤ n :

n+1

= F

+ F

−1

= (F

−m+1

+ F

−1

−m

) + (F

−1

−1)−(m−1)+1

+ F

−2

−1)−(m−1)

) =

= F

−m+1

+ F

−1

−m

+ F

−1

−m+1

+ F

−2

−m

= (F

+ F

−1

−m+1

+ (F

−1

+ F

−2

−m

= F

m+1

(n+1)

−(m+1)+1

+ F

(n+1)

−(m+1)

Niech k = m + 1. Pokazaliśmy więc prawdziwość tej relacji dla n + 1 oraz
n + 1

≥ k ≥ 3 :

n+1

= F

(n+1)

−k+1

+ F

−1

(n+1)

−k

Dla k = 2 mamy:

n+1

−2+1

+ F

n+1

−2

= F

+ F

−1

= F

+ F

−1

= F

n+1

co uzupełnia dowód kroku indukcyjnego.

4. Jeśli m|n, m > 0, n ≥ 0, to F

Dowód: Załóżmy, że n = mk. Jeśli k = 1, to m = n, F

= F

. Jeśli

k = 2, to n

− m = 2m − m = m i z powyższej równości mamy:

= F

−m+1

+ F

−1

−m

= F

−m+1

+ F

−1

= F

−m+1

+ F

−1

)

Stąd dla k = 2, F

W kroku indukcyjnym pokażemy, że twierdzenie jest prawdziwe dla n =
(k+1)m jeśli jest ono prawdziwe dla k. Mianowicie wtedy F

= fF

, f

∈

i dlatego

= F

−m+1

+ F

−1

−m

= F

−m+1

+ F

−1

(k+1)m

−m

= F

−m+1

+ F

−1

= F

−m+1

+ F

−1

f )

co dowodzi prawdziwości kroku indukcyjnego.

5. F

N W P (m,n)

|NW P (F

, F

Dowód: Z poprzedniego twierdzenia wiemy, że jeśli k|m i k|n, to F

oraz F

, a stąd F

|NW P (F

, F

). W szczególności jako k możemy

wziąć NW P (m, n). Stąd F

N W P (m,n)

|NW P (F

, F

⊳

• Inny zapis równania Fibonacciego:

∀n ≥ 0, F

n+2

− F

n+1

− F

= 0

• Liniowe równanie rekurencyjne rzędu k o stałych współczynnikach

, d

, . . . , d

∈ R :

n+k

+ d

−1

n+k

−1

+ · · · + d

n+1

+ d

= v

(2)

• W przypadku równania Fibonacciego:

k = 2, d

= 1, d

= −1, d

= −1, ∀n ≥ 0, v

= 0

• Jeśli v

= 0 dla każdego n ≥ 0, to równanie to nazywa się jednorodnym

• Równanie charakterystyczne równania różnicowego (2):

+ d

−1

+ · · · + d

r + d

= 0

(3)

Twierdzenie 3.1

O rozwiązaniach jednorodnych liniowych równań rekurencyj-

nych
Niech r

, r

, . . . r

∈ C będą wszystkimi pierwiastkami równania charaktery-

stycznego (3) (z ewentualnymi powtórzeniami dla tzw. pierwiastków wielokrot-
nych).

1. Jeśli wszystkie pierwiastki r

są jednokrotne, to rozwiązanie równania

jednorodnego ma postać:

= c

+ c

+ · · · + c

(4)

Współczynniki c

, . . . , c

wyznaczamy z k warunków początkowych.

2. Jeśli pierwiastek r

= ma krotność n

, to w powyższym rozwiązaniu (4)

j-te wystąpienie wyrażenia r

zastępujemy wyrażeniem n

−1

, dla j =

1, . . . , n

j=1

i,j

−1

(5)

Współczynniki c

i,j

wyznaczamy z k warunków początkowych.

⊳

Przykład 3.7

Pierwiastki jednokrotne

Szukamy rozwiązania równania rekurencyjnego:

n+2

= a

n+1

+ 2a

, n

≥ 0, a

= 2, a

= 1

Postać jednorodna:

n+2

− a

n+1

− 2a

= 0

Równanie charakterystyczne:

− r − 2 = 0

Pierwiastki równania: r

= −1, r

= 2. Ogólne rozwiązanie:

= c

(−1)

+ c

Wyznaczenie współczynników c

, c

z warunków początkowych:

+ c

= 2, −c

+ 2c

= 1

Stąd c

= c

= 1 i rozwiązanie a

ma postać:

= (−1)

+ 2

⊳

Przykład 3.8

Pierwiastki wielokrotne

Szukamy rozwiązania równania rekurencyjnego:

n+2

= 4a

n+1

− 4a

, n

≥ 0, a

= 1, a

= 4

Postać jednorodna:

n+2

− 4a

n+1

+ 4a

= 0

Równanie charakterystyczne:

− 4r + 4 = 0

Pierwiastki równania: r

= r

= 2. Ogólne rozwiązanie:

= c

+ c

= (c

+ c

n)2

Wyznaczenie współczynników c

, c

z warunków początkowych:

= 1, (c

+ c

)2 = 4

Stąd c

= c

= 1 i rozwiązanie a

ma postać:

= (n + 1)2

⊳

Zadania:
Znajdź rozwiązania następujących równań rekurencyjnych:

1. Równanie Fibonacciego z warunkami: a

= a

= 1

2. Równanie Fibonacciego z warunkami: a

= 1, a

= 3

3. a

n+2

= 2a

n+1

− 2a

, a

= a

= 2

4. a

n+2

− a

n+1

− 6a

, a

= 0, a

= 1

5. a

n+2

− a

n+1

− 6a

, a

= 2, a

= 1

6. a

n+2

= −a

, a

= a

= 2

7. a

n+3

− 4a

n+2

+ 5a

n+1

− 2a

= 0, a

= 4, a

= 7, a

= 17

Problemy:

1. Pokaż, że iloraz kolejnych wyrazów ciągu Finonacciego zbiega do złotej

średniej, t.j.:

lim

→∞

n+1

1 +

√

2. Niech a

będzie liczbą wszystkich słów długości n złożonych z cyfr 0, 1 nie

zawierających kolejnych dwóch jedynek 11. Pokaż, że:

= 1, a

= 2, a

= 5, a

= a

−1

+ a

−2

, dla n

≥ 3

3. Znajdź związek rekurencyjny dla ciągu

(a) a

, ⌊n/2⌋

(b) b

, ⌊n/3⌋

, a

+ b

Sprawdź przez indukcję słuszność zaproponowanych związków rekurencyj-
nych.

• Równania niejednorodne szczególnej postaci:

n+k

+ d

−1

n+k

−1

+ · · · + d

n+1

+ d

= r

v(n)

(6)

gdzie r ∈ R, oraz v jest wielomianem

• Obserwacja: jeśli b

jest rozwiązaniem szczególnym niejednorodnego linio-

wego równania rekurencyjnego, to dowolne rozwiązanie c

tego równania

jest postaci:

= b

+ a

, n

≥ 0,

gdzie a

jest rozwiązaniem równania jednorodnego o tych samych współ-

czynnikach.

Twierdzenie 3.2

O rozwiązaniach niejednorodnych liniowych równań rekuren-

cyjnych
Szczególne rozwiązanie niejednorodnego równania rekurencyjnego (6) o począt-
kowych wartościach a

, . . . , a

−1

jest rozwiązaniem równania jednorodnego o

wielomianie charakterystycznym

p(x)(x

− r)

e+1

gdzie e jest stopniem wielomianu v, p(x) jest wielomianem charakterystycznym
równania oryginalnego:

p(x)

, d

+ d

−1

+ · · · + d

x + d

a brakujące e + 1 współczynnik c

k+1

, . . . , c

k+e+1

szukamy z dodatkowych wa-

runków otrzymanych na elementy a

, a

k+1

, . . . , a

k+e

. ⊳

Przykład 3.9

Rekurencyjne równanie niejednorodne

Szukamy rozwiązań równania rekurencyjnego:

n+2

− a

n+1

− 2a

= 2, a

= 3, a

= −2

Wielomian charakterystyczny p(x) = x

− x− 2 = (x+ 1)(x− 2), a prawa strona

v(n) = 1

· 2. Stąd r = 1 oraz e = 0. Dlatego wielomian charakterystycznego

nowego równania jednorodnego ma postać:

p(x)(x

− 1)

0+1

= (x + 1)(x − 2)(x − 1)

z dodatkowym warunkiem początkowym: a

= a

+ 2a

+ 2 = 6.

Rozwiązanie ogólne równania rekurencyjnego o wielomianie charakterystycznym
(x + 1)(x − 2)(x − 1) ma postać:

= c

(−1)

+ c

Podstawienie do warunków początkowych otrzymujemy c

= 3, c

= 1, c

= −1

i szczególne rozwiązanie naszego równania ma postać:

= 3(−1)

+ 2

− 1

⊳

Zadania:
Znajdź rozwiązania następujących równań rekurencyjnych:

1. a

n+2

= 3a

n+1

− 2a

+ 2 · 3

, a

= 1, a

= 2

2. a

n+3

− 6a

n+2

+ 11a

n+1

− 6a

= 12n3

, a

= 2, a

= −25, a

= −140

3. a

n+2

− 5a

n+1

+ 6a

= 4n

− 2n − 3, a

= 6, a

= 14

3.6

Zliczanie obiektów kombinatorycznych

1. Współczynniki dwumienne

2. Własności liczbowe zbiorów i funkcji

3. Zasada włączania i wyłączania

4. Podziały

5. Zbiory z powtórzeniami

6. Zliczanie drzew binarnych

3.6.1

Współczynniki dwumienne

• Współczynnik dwumienny

a
k

jest współczynnikiem przy potędze x

rozwinięciu w szereg Taylora funkcji (1 + x)

, k

∈ {0} ∪ N, a ∈ R :

(1 + x)

∞

k=0

• Wzór na współczynnik szeregu Taylora:

f (x) =

∞

k=0

→ c

(k)

(0)

• Wzór na k-tą pochodną funkcji (1 + x)

(1 + x)

= a(a − 1) . . . (a − k + 1)(1 + x)

−k

• Wzór na współczynnik dwumienny:

(1 + x)

x=0

/k! =

a(a

− 1) . . . (a − k + 1)

• Związek z liczbą kombinacji k-elementowych ze zbioru n-elementowego:

k,n

Dowód:

Jeśli ponumerujemy elementy uniwersum U =

, . . . , u

}, to każdy podzbiór Z ⊂ U możemy

reprezentować przez ciąg binarny b

, . . . , b

gdy u

∈ Z,

gdy u

6∈ Z

oraz przez jednomian q

(x) :

(x)

, x

. . . x

= x

+···+b

= x

|Z|

Zauważmy, że: q

∅

(x) = 1, q

(x) = x

, q

(x) = x

wtt

|Z| = k. Widzimy, że istnieje dokładnie

k,n

podzbiorów reprezentowanych przez jednomian x

. Rozważmy wielomian p(x) będący sumą

jednomianów reprezentujących wszystkie podzbiory U :

p(x)

∈2

(x) =

|Z|=k

k,n

Z drugiej strony:

p(x) =

∈2

· · ·

−1

. . . x

−1

]

· · ·

−1

. . . x

−1

](1 + x)

· · ·

−2

. . . x

−2

](1 + x)

(1 + x)

−1

= (1 + x)

Z jednoznaczności reprezentacji funkcji wielomianowych mamy więc

k,n

n
k

⊳

Własność 3.3

Dwumian

• Związek rekurencyjny (trójkąt Pascala):

n − 1

− 1

n − 1

• Własność przekątnej trójkąta Pascala:

n + 1

− 1

n − 1

− 1

n − 1

− 2

n − 1

− 1

n − 2

− 2

+ · · · +

n − k

j=0

n − j

− j

⊳

Zadania: Uzasadnij bez indukcji matematycznej:

n
k=0

n
k

= 2

n
k=0

(−1)

k n

= 0

n
k=0

= 2

−1

n
k=0

2k+1

= 2

−1

n
k=0

n
k

= n2

−1

n
k=0

k n

= 3

7. (x + y)

n
k=0

n
k

−k

3.6.2

Własności liczbowe zbiorów i funkcji

• Dla dowolnych zbiorów skończonych A, B, A

⊂ U, i = 1, . . . , n :

|A ∪ B| = |A| + |B| − |A ∩ B|

∩ B = ∅ → |A ∪ B| = |A| + |B|

|U − A| = |U| − |A|

|A × B| = |A||B|

× · · · × A

| = |A

| · · · · · |A

| = 2

|U|

k,n

• Oznaczmy zbiór wszystkich funkcji postaci f : X

→ Y przez Y

, wtedy:

= |Y |

|X|

• Liczba funkcji różnowartościowych w X

(permutacji zbioru X) wynosi

|X|!

• Liczba funkcji różnowartościowych w Y

, gdy

|Y | = |X| wynosi |X|!

• Liczba funkcji różnowartościowych w Y

(iniekcji zbioru X w zbiór Y ),

|Y | ≥ |X|, wynosi:

|Y | · (|Y | − 1) . . . (|Y | − |X| + 1)

3.6.3

Zasada włączania i wyłączania

• Zasada włączania i wyłączania – przypadek dwóch zbiorów:

∪ A

| = |A

| + |A

| − |A

∩ A

• Zasada włączania i wyłączania – przypadek trzech zbiorów:

∪A

| = |A

|+|A

|−|A

∩A

|−|A

∩A

|−|A

∩A

|+|A

∩A

• Zasada włączania i wyłączania – przypadek ogólny:

niech I = {1, . . . , n} będzie zbiorem indeksów, wtedy

[

i=1

| =

∅6=J⊂I

(−1)

|J|+1

∈J

Dowód kroku indukcyjnego:

∪ · · · ∪ A

∪ A

n+1

| = |A

∪ · · · ∪ A

| + |A

n+1

| − |(A

∩ A

n+1

) ∪ · · · ∪ (A

∩ A

n+1

∅6=J⊂I

(−1)

|J|+1

∈J

+ |A

n+1

| +

∅6=J⊂I

(−1)

|J|+2

n+1

∈J

∅6=J⊂(I∩{n+1}

(−1)

|J|+1

∈J

• Zastosowanie: Liczba S(k, n) równa liczbie wszystkich funkcji typu ”na”

, (suriekcji zbioru X na zbiór Y )

|X| = k ≥ n = |Y | wynosi:

S(k, n) =

j=0

(−1)

(n − j)

Dowód

formuły S(k, n)

Niech

∅ 6= Z ( Y. Oznaczmy przez A

⊂ Y

zbiór tych funkcji, które nie przyjmują wartości

w zbiorze Z, t.j. A

, (Y − Z)

. Liczność zbioru A

wynosi więc (n

− |Z|)

Poszukiwany zbiór B, funkcji postaci f : X

→ Y otrzymujemy przez odjęcie od zbioru Y

sumy

zbiorów A

{y}

dla wszystkich y

∈ Y ;

B = Y

−

∈Y

{y}

Dlatego

|B| = n

−

∈Y

{y}

Zauważmy, że j-elementowe przecięcie zbiorów typu A

}

, p = 1, . . . , j daje zbiór postaci A

gdzie Z =

, . . . , y

} jest dowolną kombinacją j-elementową zbioru Y.

Stosujemy zasadę włączania i wyłączania:

∈Y

{y}

∅6=Z⊂Y

(

−1)

|Z|+1

∈Z

{y}

∅6=Z⊂Y

(

−1)

|Z|+1

−1

⊂Y,|Z|=j

(

−1)

− j)

−1

(

−1)

− j)

Ostatecznie

|B| = n

−

−1

(

−1)

− j)

(

−1)

− j)

⊳

3.6.4

Podziały

• Podział zbioru U na n podzbiorów jest dowolnym zestawem zbiorów Z

, . . . , Z

⊂

U takim, że:

U =

i=1

, Z

∩ Z

= ∅, i 6= j

• Liczba P (k, n) wszystkich podziałów zbioru k-elementowego U na n roz-

łącznych podzbiorów wynosi:

P (k, n) =

j=0

(−1)

(n − j)

Dowód

Formuły P (k, n)

Niech I będzie zbiorem indeksów 1, . . . , n. Dowolny podział na n podzbiorów określony przez

funkcję f : U

→ I : zbioru U na zbiór I :

f (u) = i wtt u

∈ Z

Dowolna zmiana numeracji, t.j. permutacja g zbioru I zmienia funkcję f, ale nie zmienia po-
działu:

f (u) = g(i) wtt u

∈ Z

W takim razie jednemu podziałowi odpowiada n! numeracji. Ponieważ liczba suriekcji ze zbioru

wynosi S(k, n), to P (k, n) = S(k, n)/n!.

⊳

3.6.5

Zbiory z powtórzeniami

• Przykład: [a, a, a, b, b] jest podzbiorem z powtórzeniami, np. dla uniwersum

U =

{a, b, c}

• Koncepcja zbioru z powtórzeniami (wielozbioru) pasuje do koncepcji ko-

lekcji danych, gdzie instancje tej samej danej mogą się powtarzać

• Matematycznie wielozbiór W możemy reprezentować przez funkcję f

→ N ∪ {0}

• Przykład: wielozbiór W = [a, a, a, b, b] reprezentowany jest przez funkcję

(a) = 3, f

(b) = 2, f

• Mówimy, że wielozbiór W jest k elementowy gdy:

∈U

(u) = k

• Niech s(k, n) będzie liczbą różnych k-elementowych wielozbiorów określo-

nych w zbiorze n-elementowym. Wtedy:

s(k, n + 1) = s(k, n) + s(k

− 1, n) + · · · + s(1, n) + s(0, n)

Dowód: Ten rekurencyjny związek wynika z faktu, że element n + 1 albo
nie wystepuje w wielozbiorze i mamy wtedy s(k, n) takich wielozbiorów w
zbiorze n-elementowym, albo występuje z krotnością j > i wtedy krotność
k

− j daje s(k − j, n) wielozbiorów.

• s(k, n) spełnia prostszą relację rekurencyjną:

s(k, n + 1) = s(k

− 1, n + 1) + s(k, n)

• Wniosek: Tablica wartości s(k, n) jest obróconą tablicą wartości

n
k

, a

dokładniej:

s(k, n) =

n + k − 1

3.6.6

Zliczanie drzew binarnych

• Rekurencyjny schemat deﬁnicji zbioru drzew

T : Niech s symbolizuje do-

wolną zawartość węzła drzewa, a E jest symbolem drzewa pustego.

1. krok bazowy:

(a) E ∈ T – puste drzewo binarne

(b) (E, s, E) ∈ T – binarne drzewo o jednym węźle

2. krok indukcyjny:

, T

∈ T → T , (T

, s, T

) ∈ T

Drzewo T

nazywamy lewym poddrzewem drzewa T, a T

jego pra-

wym poddrzewem. Mówimy, że zawartość s znajduje się w korzeniu
drzewa T. Jeśli T

6= E, to mówimy, że korzeń T

jest lewym synem

korzenia drzewa T. Jeśli natomiast T

6= E, to korzeń T

jest prawym

synem korzenia drzewa T.

• Formalnie drzewo T

∈ T jest napisem nad alfabetem {s, E, (, )} popraw-

nie zdeﬁniowanym według powyższego schematu o liczbie węzłów równej
liczbie wystąpień symbolu s

• W praktyce programowania w konstrukcji (T

, s, T

), s jest zastępowane

często złożoną strukturą danych, a T

referencją na być może puste pod-

drzewo

• Mówimy, że dwa drzewa są różne jeśli T

6= T

w sensie napisów, które je

reprezentują

• Poziom zagnieżdżenia węzła minus jeden określa głębokość tego węzła.

Maksymalna głębokość określa wysokość drzewa.

• Przykłady drzew:

–

Napis ((E, s, E), s, (E, s, E)) reprezentuje drzewo o trzech węzłach.
Drzewo to ma dwa poddrzewa, każde po jednym węźle.Wysokość tego
drzewa wynosi 1.

–

Napis ((((E, s, E), s, E), s, E), s, E) reprezentuje drzewo o czterech
węzłach. Drzewo to ma jedno poddrzewo niepuste, które z kolei też
ma tylko lewe poddrzewo niepuste o dwóch węzłach. Wysokość tego
drzewa wynosi trzy.

• Niech

oznacza zbiór wszystkich drzew binarnych o n węzłach, a t(n) ,

• Własności:

1. t(0) = 1 – bo E ∈ T
2. t(1) = 1 – bo (E, s, E) ∈ T
3. Jeśli T ∈ T

, T = (T

, s, T

) oraz T

∈ T

, 0

≤ k ≤ (n − 1), to

∈ T

−k−1

4. Rekurencyjny związek dla t(n) :

t(n) = t(0)t(n

− 1) + t(1)t(n − 2) + · · · + t(n − 2)t(1) + t(n − 1)t(0)

5. Jawna postać funkcji dla t(n) :

t(n) =

n + 1

, n

∈ N ∪ {0}

(7)

Dowód

Wyprowadzenie wzoru (7)

• Deﬁniujemy funkcję tworzącą;

F (x)

∞

f (n)x

• Obliczamy wyrażenie xF

(x) :

(x) = x

∞

f (i)x

∞

f (j)x

= x

∞

+j=k

f (i)f (j)

= x

∞

f (k + 1)x

∞

f (k + 1)x

= F (x)

− f (0) = F (x) − 1

• Rozwiązujemy równanie kwadratowe xF

(x)

− F (x) + 1 = 0 względem F (x) :

F (x) =

√

− 4x

⊳

• Znajdujemy szereg Taylora w postaci dwumiennej dla G(x) =

√

− 4x :

G(x) =

∞

1/2

(

−4x)

∞

1/2

(

−4)

• Zmieniamy postać n-tego współczynnika rozwinięcia Taylora:

1/2

(

−4)

1
2

−1

−3

· · · · ·

−(2n−3)

(

−4)

−

· 1 · 3 · · · · · (2n − 3)2

−n

−

· 3 · · · · · (2n − 3)2

− 1)!

n!(n

− 1)!

−

· 3 · · · · · (2n − 3) · 2 · 4 · · · · · (2n − 2) · 2

n!(n

− 1)!

−

· 2 · 3 · · · · · (2n − 3) · (2n − 2) · 2

n!(n

− 1)!

−

(2n

− 2)!

− 1)!(n − 1)!

−

− 2

− 1

• Wyliczamy szereg Taylora dla (1

− G(x))/2x :

F (x) =

∞

− 2

− 1

−1

∞

n + 1

• Wniosek: f (n) =

⊳

Kongruencje

• Podzielność liczb całkowitych

• Algebra reszt

• Szyfrowanie

4.1

Podzielność liczb całkowitych

• Pojęcie ilorazu i reszty z dzielenia liczb całkowitych

Jeśli a, b ∈ Z, 6= 0, to iloraz całkowity q ∈ Z liczby a przez liczbę b oraz

reszta r ∈ Z z dzielenia a przez b spełniają następujący związki:

a = qb + r, 0

≤ r ≤ |b| − 1

(8)

• Przykłady:

–

Dla a = 15, b = −4 : q = −3, r = 3

–

Dla a = 15, b = 4 : q = 3, r = 3

–

Dla a = −15, b = −4 : q = 4, r = 1

–

Dla a = −15, b = 4 : q = −4, r = 1

• Dla dowolnych a, b

∈ Z, b 6= 0 istnieje dokładnie jedna para liczb całkowi-

tych (q, r) spełniająca związki (8)

• Dowód jednoznaczności ilorazu i reszty:

Jeśli a = q

b + r

= q

b + r

, 0

≤ r

, r

≤ |b| − 1, to

− q

| · |b| = |r

− r

| < |b|

Stąd |q

− q

| < 1, a dla liczb całkowitych jest to możliwe gdy q

= q

= q.

W efekcie r

= a − qb = r

• Dowód istnienia ilorazu i reszty dla a

≥ 0 (przez indukcję):

–

Baza indukcji dla a = 0, . . . , |b| − 1 :

q = 0, r = a bo a = 0

· b + a, 0 ≤ a ≤ |b| − 1

–

Krok indukcyjny dla a ≥ (|b| − 1) :

a = qb + r, 0

≤ r ≤ |b| − 1 → a + 1 = q

′

b + r

′

, 0

≤ r

′

≤ |b| − 1

Możliwe są dwa przypadki:(1)r + 1 < |b|; (2) r + 1 = |b|.

W pierwszym przypadku q

′

= q, r

′

= r + 1, bo:

a + 1 = (qb + r) + 1 = qb + (r + 1) = q

′

b + r

′

, 0

≤ r

′

≤ |b| − 1

W drugim przypadku dla b > 0 mamy q

′

= q + 1, r

′

= 0, bo:

a + 1 = (qb + r) + 1 = (q + 1)b + (r + 1

− b) = q

′

b + r

′

, r

′

= 0

Natomiast gdy r + 1 = −b dla b < 0 mamy q

′

= q − 1, r

′

= 0,

a + 1 = (qb + r) + 1 = (q

− 1)b + (r + 1 + b) = q

′

b + r

′

, r

′

= 0

• Dowód istnienia ilorazu i reszty dla a < 0 (przez negację):

Budujemy iloraz q

′

i resztę r

′

z ilorazu q i reszty r dla −a > 0. Jeśli r = 0,

to q

′

= −q, r

′

= 0, bo:

a =

−(−a) = −(qb + r) = (−q)b + 0

Jeśli r > 0 i b > 0, to q

′

= −q − 1, r

′

= b − r, bo:

−a = −(−a) = −(qb + r) = (−q − 1)b + (b − r) = q

′

b + r

′

, 0

≤ r

′

≤ |b| − 1

Natomiast gdy r > 0 i b < 0, q

′

= −q + 1, r

′

= |b| − r, bo:

−a = −(−a) = −(qb + r) = (−q + 1)b + (|b| − r) = q

′

b + r

′

, 0

≤ r

′

≤ |b| − 1

• Funkcje ilorazu q = a

÷ b, i reszty r = mod

(a) :

a = (a

÷ b)b + mod

(a)

• Związek ilorazu całkowitego z ilorazem rzeczywistym

–

Dolna część całkowita liczby rzeczywistej ⌊x⌋ :

⌊x⌋ = max{k ∈ Z : k ≤ x}

–

Górna część całkowita liczby rzeczywistej ⌈x⌉ :

⌈x⌉ = min{k ∈ Z : k ≥ x}

–

Podstawowe własności ⌊x⌋ i ⌈x⌉, x ∈ R :

⌊x⌋ ≤ x < ⌊x⌋ + 1

∀n ∈ N,

⌊x⌋

j x

⌈−x⌉ = −⌊x⌋

–

Jeśli b > 0, to iloraz całkowity otrzymujemy jako dolną część całko-
witą ilorazu rzeczywistego:

÷ b =

j a

Mianowicie:

j a

≤

j a

+ 1

j a

· b ≤ a <

j a

· b + b

0 ≤ a −

j a

· b < b

Biorąc więc q = ⌊a/b⌋, r = a − qb otrzymujemy własność deﬁnicyjną

dla ilorazu i reszty z dzielenia całkowitego a przez b :

a = qb + r, 0

≤ r ≤ b − 1

–

Jeśli b < 0, to iloraz całkowity otrzymujemy jako górną część całko-
witą ilorazu rzeczywistego:

÷ b =

l a

Mianowicie:

−a

≤

−a

+ 1

−a

· (−b) ≤ a <

−a

· (−b) + |b|

l a

· b ≤ a <

l a

· b + |b|

0 ≤ a −

l a

· b < |b|

Biorąc więc q = ⌈a/b⌉, r = a − qb otrzymujemy własność deﬁnicyjną

dla ilorazu i reszty z dzielenia całkowitego a przez b :

a = qb + r, 0

≤ r ≤ |b| − 1

Ćwiczenia:

1. Oblicz a ÷ b, mod

(a), ⌊a/b⌋ oraz ⌈a/b⌉ gdy:

(a) a = 25, b = 3

(b) a = 25, b = −3

(d) a = −25, b = −3

2. Sprawdź własność ∀n ∈ N, ∀x ∈ R, ⌊⌊x⌋/n⌋ = ⌊x/n⌋ gdy:

(a) x = 25, 333 n = 7

(b) x = −25, 333 n = 7

Zadania:

1. Oblicz a ÷ b oraz mod

(a) gdy:

(a) a = −2b − 1, a, b ∈ Z, b > 0

(b) a = −2b − 1, a, b ∈ Z, b < 0

2. Udowodnij własność: ∀n ∈ N, ∀x ∈ R, ⌊⌊x⌋/n⌋ = ⌊x/n⌋

4.1.1

Kombinacje liniowe dwóch liczb całkowitych

• Kombinacja liniowa liczb a, b

∈ Z o współczynnikach x, y ∈ Z to wyrażenie

postaci:

· a + y · b

• Zbiór wszystkich kombinacji liczb a, b oznaczamy przez

L(a, b) :

L(a, b) , {xa + yb : x, y ∈ Z}

• Niech

(a, b) zawiera tylko dodatnie elementy L(a, b), a L

−

(a, b) tylko

ujemne. Wtedy:

−

(a, b) = −L

(a, b)

L(a, b) = L

−

(a, b) ∪ {0} ∪ L

(a, b)

gdzie negacja −Z zbioru Z oznacza zbiór negacji wszystkich elementów Z

• Największy wspólny podzielnik N W P (a, b) określamy następująco:

N W P (a, b)

, max{c ∈ Z : c|a, c|b}

• Najmniejszą wspólną wielokrotność N W W (a, b) określamy następująco:

N W W (a, b)

, min{c ∈ N : a|c, b|c}

• Deﬁnicja funkcji NWP jest poprawna o ile

|a| + |b| > 0

• Największy wspólny podzielnik jest zawsze dodatni

• Największy wspólny podzielnik nie zmienia sie przy zmianie znaku:

N W P (a, b) = N W P (

−a, b) = NW P (a, −b)

= NW P (−a, −b) = NW P (|a|, |b|)

Twierdzenie 4.1

O liniowej reprezentacji funkcji NWP

Niech dla a, b ∈ Z, |a| + |b| > 0, m

a,b

oznacza najmniejszy element zbioru

(a, b). Wtedy:

1. m

a,b

dzieli każdy element L

(a, b)

2. m

a,b

dzieli każdy element L

−

(a, b)

3. m

a,b

dzieli każdy element L(a, b)

4. m

a,b

dzieli zarówno a jak i b

5. Jeśli c dzieli a i b, to dzieli każdy element zbioru L(a, b)

6. Jeśli c dzieli a i b, to dzieli m

a,b

7. m

a,b

jest największym wspólnym podzielnikiem a i b

8. Największy wspólny podzielnik a i b jest kombinacją liniową a i b, t.j.

istnieją takie liczby x, y ∈ Z, że:

N W P (a, b) = x

· a + y · b

⊳

Dowód:

W kolejności faktów do pokazania mamy:

1. Niech m

a,b

= x

a+y

b. Wtedy gdyby dla pewnego xa+yb

∈ L

(a, b) reszta r z dzielenia

xa + yb przez m

a,b

była większa od zera, to

r = xa + yb

− qm

a,b

, r = (x

− qx

)a + (y

− qy

Znaleźliśmy więc r mniejsze od m

a,b

i należące do

, co przeczy wyborowi m

a,b

2. Bo dla xa + yb

∈ L

−

(a, b), to m

a,b

|(−x)a + (−y)b ∈ L

(a, b). W takim razie m

a,b

|xa +

∈ L

−

(a, b)

3. m

a,b

dzieli zero, a więc z powyższych dwóch punktów dzieli każdy element zbioru

L(a, b)

4. Skoro a = 1

· a + 0 · b, zaś b = 0 · a + 1 · b, to a, b ∈ L(a, b) i z poprzedniego punktu dzielą

się przez m

a,b

5. Wspólny podzielnik a i b dzieli również każdą kombinację liczb a i b, a więc każdy element

zbioru

L(a, b)

6. Ponieważ m

a,b

jest elementem

L(a, b), to z poprzedniego punktu musi dzielić się przez

każdy wspólny podzielnik a i b

7. m

a,b

jako wielokrotność każdego wspólnego podzielnika liczb a oraz b, będąc jednocześnie

wspólnym podzielnikiem a i b (punkt 4) musi być największym wspólnym podzielnikiem
a i b

8. Skoro m

a,b

= N W P (a, b) i m

a,b

∈ L(a, b), to teza tego punktu jest oczywista

⊳

4.1.2

Algorytm Euklidesa dla NWP

Twierdzenie 4.2

Poprawność algorytmu Euklidesa dla NWP

Niech a, b ∈ Z, b > 0, r

, a, r

, b. Wtedy

1. NW P (a, b) = NW P (b, mod

(a))

2. Dla i > 0, gdy r

> 0 algorytm Euklidesa deﬁniuje kolejne wyrazu ciągu

i+1

, mod

−1

). Gdy r

= 0, element r

i+1

nie jest określony. Ciąg ten

ma następujące własności:

(a) NW P (r

, r

) = NW P (a, b)

(b) r

i+1

< r

dla i > 0

, r

i+1

) = NW P (r

−1

, r

) dla i > 0

(d) NW P (r

, r

i+1

) = NW P (a, b)

(e) Jeśli r

i+1

= 0, to r

= NW P (a, b)

(f) Dla pewnego i ≤ b + 1 : r

= 0

⊳

Zadanie:
Sprawdź na przykładach, że następująca funkcja C poprawnie realizuje algorytm
Euklidesa:

int NWP(int a, int b)
{ int r;

while (r = a%b)

{

a = b; b = r;

}
return b;

}

Ćwiczenia:

1. Oblicz NW P (a, b) gdy:

(a) a = 81, b = 27

(b) a = −81, b = 27

2. Wyznacz ślad wywołania funkcji NWP(a,b) gdy

(a) a = 1024, b = 10024

(b) a = 10024, b = 1024

Zadania:

1. Niech q = a ÷ b, r = mod

(a). Pokaż, że NW P (a, b) = NW P (q, r).

2. Udowodnij twierdzenie 4.2.

4.1.3

Rozszerzony algorytm Euklidesa dla NWP

Twierdzenie 4.3

Poprawność rozszerzonego algorytmu Euklidesa dla NWP

Niech również a, b ∈ Z, b > 0, r

, a, r

, b i dodatkowo x

= 1, y

= 0, x

0, y

= 1. Wtedy

1. Dla i > 0, gdy r

> 0 rozszerzony algorytm Euklidesa deﬁniuje kolejne

wyrazu ciągu r

i+1

, mod

−1

) i dodatkowo współczynniki kombinacji

liniowej x

i+1

, y

i+1

−1

, r

−1

÷ r

, x

i+1

, x

−1

− q

−1

, y

i+1

, y

−1

− q

−1

Gdy r

= 0, elementy r

i+1

, x

i+1

, y

i+1

nie są określone. Ciągi r

, x

, y

gene-

rowane przez rozszerzony algorytm Euklidesa mają następujące własności:

(a) r

= x

a + y

b, r

= x

a + y

(b) Jeśli dla i > 0, r

> 0, r

−1

= x

−1

a + y

−1

b oraz r

= x

a + y

b, to

i+1

= x

i+1

a + y

i+1

= 0, to NW P (a, b) = r

= x

a + y

⊳

Zadanie: Sprawdź na przykładach, że następująca funkcja nwpxy poprawnie
realizuje w języku C rozszerzony algorytm Euklidesa, tj. po wywołaniu z =
nwpxy(u,v,&x,&y)

mamy: z = NW P (u, v), z = x · u + y · v.

int nwpxy(int a, int b, int* px1, int* py1)
{ int q, r, x0=1, y0=0, x1=0, y1=1, x2, y2;

while (q=a/b, r=a%b)

{

a = b; b = r;
x2 = x0-q*x1; y2 = y0-q*y1;
x0 = x1; x1 = x2; y0 = y1; y1 = y2;

}
*px1 = x1; *py1 = y1;
return b;

}

Ćwiczenia:

1. Oblicz x, y ∈ Z takie, że NW P (a, b) = xa + yb gdy:

(a) a = 81, b = 27

(b) a = −81, b = 27

2. Wyznacz ślad wywołania funkcji nwpxy(a,b) gdy

(a) a = 1024, b = 10024

(b) a = 10024, b = 1024

Problem:
Udowodnij twierdzenie 4.3.

4.1.4

Przykład – rozlewanie płynów

Problem odmierzania płynu
Z rezerwuaru R o bardzo dużej pojemności należy odmierzyć c jednostek płynu
dysponując miarką A o pojemności a jednostek oraz miarką B o pojemności b.
W przypadku

• gdy c

≤ max(a, b) – c jednostek płynu ma znaleźć się w jednym z naczyń

A lub B

• gdy c > max(a, b) – c jednostek płynu ma znaleźć się w dodatkowym na-

czyniu C o nieznanej pojemności większej lub równej c

Zakładamy, że a, b, c są liczbami naturalnymi. Dopuszczalna operacja w jednym
kroku procesu rozlewania płynów polega albo na wypełnieniu do pełna lub na
całkowitym opróżnieniu jednej z miarek A lub B.

Rozlewanie płynów – przypadki specjalne

• Niech X

→Y oznacza przelanie płynu z X do Y

• Przypadek a

|c lub b|c jest trywialny

• Przypadek c > a oraz c > b rozwiązujemy następująco:

1. niech k ← c ÷ a
2. wykonaj k razy: R→A, A→C
3. pozostałe r = c − k · a < a jednostek uzyskaj stosując rozwiązanie

opisane poniżej dla przypadku c < a. W rozwiązaniu tym c jedno-
stek traﬁa na końcu do naczynia A. W tym przypadku c = r i tyle
jednostek przelewamy do naczynia C.

Rozlewanie płynów – kombinacje liniowe
Zakładamy teraz, że c < a, nie ma naczynia C, a c jednostek znajdzie się na
końcu w miarce A.

Twierdzenie 4.4

O stanach miarek A i B

Po każdym kroku X→Y w miarce A (B) znajduje się liczba jednostek x

a + y

b dla B) płynu gdzie x

, y

, x

, y

∈ Z. ⊳

Dowód

Dowód prowadzimy przez indukcję

Na początku miarki są puste więc x

= x

= y

= 0.

1. Dla kroku R

→A (R→B) mamy x

= 1, y

= 0 (x

= 0, y

= 1), bo czerpiąc z

rezerwuaru R dolewamy do A (B) płyn do pełna

2. Dla kroku A

→R (B→R) mamy x

= 0, y

= 0 (x

= 0, y

= 0), bo wylewając

zawartość A (B) do rezerwuaru R opróżniamy całkowicie miarkę

3. Dla kroku A

→B mamy zmianę współczynników zależną od bieżącej zawartości obu mia-

rek:

(a) x

a + y

≥ b − (x

a + y

b) :

′
A

= x

+ x

, y

′
A

= y

+ y

− 1, x

′
B

= 0, y

′
B

= 1

(b) x

a + y

b < b

− (x

a + y

b) :

′
A

= 0, y

′
A

= 0, x

′
B

= x

+ x

, y

′
B

= y

+ y

4. Dla kroku B

→A mamy warunki i wzory symetryczne:

(a) x

a + y

≥ a − (x

a + y

b) :

′
B

= x

+ x

− 1, y

′
B

= y

+ y

, x

′
A

= 0, y

′
A

= 1

(b) x

a + y

b < a

− (x

a + y

b) :

′
B

= 0, y

′
B

= 0, x

′
A

= x

+ x

, y

′
A

= y

+ y

Powyższe kroki wyczerpują wszystkie możliwości kroku indukcyjnego, w którym pokazaliśmy,

że jeśli stan płynów w miarkach przed danym krokiem jest kombinacją liniową xa + yb, to po

jej wykonaniu stan ich też jest postaci x

′

a + y

′

⊳

Wniosek: Na końcu procesu rozlewania musimy mieć c = xa + yb, z własności
zbioru L

(a, b) mamy NW P (a, b)|c. To jest warunkiem koniecznym na istnie-

nie rozwiązania problemu dla przypadku c < a i symetrycznie dla c < b jest:
N W P (a, b)

|c.

Rozlewanie płynów – konstrukcja rozwiązania dla

c < a

Warunek NW P (a, b)|c jest też warunkiem dostatecznym dla przypadku c < a

(symetrycznie również dla c < b), potraﬁmy bowiem skonstruować rozwiązanie
następująco biorąc reprezentację c = xa + yb, x, −y ∈ N :
Algorytm 4.1

Rozlewanie w przypadku c < a

Krok 0:

← 0; [x, y] → nwpxy(a, b); //c = xa + yb, x, −y ∈ N

Krok 1: Wykonaj

x razy:

Krok 1.1: R

→A; A→B;

Krok 1.2: Wykonaj

Krok 1.2.1: jeśli miarka B jest pełna, to

→R; k ← k + 1;

jeśli

k =

−y, to zakończ (wynik w A)

Krok 1.2.2: jeśli miarka A jest pusta, to

wyjdź z pętli 1.2 (do kroku 1.1);

w przeciwnym razie

→B i kontynuuj pętlę 1.2 ⊳

Powyższy algorytm korzysta ze specjalnej kombinacji c = xa + yb, w której x
jest dodatnie, a y ujemne.
Lemat 4.1

Jeśli a, b, c ∈ N oraz NW P (a, b)|c, to istnieje reprezentacja c = xa + yb, dla

której x, −y ∈ N. ⊳

Dowód:

Z własności zbioru

(a, b) wiemy, że c = xa + yb, dla pewnych x, y

∈ Z. Musimy

pokazać, że możemy zawsze dobrać dodatnie x w takiej reprezentacji. Zauważmy, że dwie różne

reprezentacje c = x

a + y

b = x

a + y

b spełniają następujący warunek:

− x

)a = (y

− y

Na przykład dla współczynników (x

, y

) nowe współczynniki (x

, y

) zdeﬁniowane wzorami

= x

+ b/N W P (a, b), y

= y

− a/NW P (a, b)

spełniają powyższy warunek. Zauważmy, że w nowej parze współczynnik x się zwiększył, a

współczynnik y zmniejszył. Gdyby w reprezentacji c = xa + yb współczynnik x był ujemny,

to stosując powyższe przejścia z (x

, y

) na (x

, y

) co najmniej

⌈(−x) · NW P (a, b)/b⌉ razy

otrzymamy x dodatnie, a y ujemne.

⊳

Ćwiczenia:

1. Znajdź x, y ∈ Z takie, że x ≥ 0, −y ≥ 0, NW P (a, b) = xa + yb gdy:

(a) a = 1024, b = 10024

(b) a = 10024, b = 1024

2. Uzyskaj 32 litry stosując tylko menzurki A i B odpowiednio o pojemno-

ściach 64 i 48 litrów.

3. Uzyskaj 96 litrów w naczyniu C o pojemności 1000 litrów stosując men-

zurki A i B odpowiednio o pojemnościach 64 i 48 litrów.

Zadania:

1. Uzyskaj 36 litrów stosując tylko menzurki o pojemności 64 i 48 litrów.

2. Uzyskaj 108 litrów w naczyniu C o pojemności 1000 litrów stosując men-

zurki A i B o pojemności 64 i 48 litrów.

4.1.5

Liczby pierwsze – wprowadzenie

• Deﬁnicja: Liczby a, b

∈ Z są względnie pierwsze wtt NW P (a, b) = 1

• Przykłady liczb względnie pierwszych: N W P (4, 15) = 1, N W P (3, 7) =

1, NW P (121, 120) = 1

• Lemat: Jeśli liczby a

. . . . , a

∈ Z są pierwsze względem b ∈ Z, liczba

, a

· · · · · a

jest pierwsza względem b.

Dowód:

Ponieważ N W P (a

, b) = 1, to istnieje kombinacja x

+ y

b = 1. Stąd:

1 =

+ y

b] =

+ yb =

+ yb = xa + yb

gdzie x = x

· · · · · x

, a y = (1

− xa)/b. Dlatego NW P (a, b) = 1.

⊳

• Niech d(n) będzie liczbą dodatnich dzielników liczby n

∈ Z

• Obserwacje:

–

d(1) = 1, d(

−1) = 1

–

Jeśli n ∈ Z, |n| 6= 1, to d(n) ≥ 2

–

Deﬁnicja: Liczba p ∈ N, p > 1 jest liczbą pierwszą wtt d(n) = 2

–

Przykłady liczb pierwszych: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

• Lemat: Jeśli p jest liczbą pierwszą, to dla dowolnej liczby n

∈ Z albo p, n

są względnie pierwsze lub p dzieli n.
Dowód:

Podzielniki p to 1 oraz p, a więc N W P (p, n) = 1 lub N W P (p, n) = p. W

pierwszym przypadku p, n są względnie pierwsze, a w drugim p

|n.

⊳

• Lemat: Jeśli p jest liczbą pierwszą i p

|ab, dla pewnych a, b ∈ Z, to albo

|a lub p|b.

Dowód

przez zaprzeczenie

Gdyby p

6 |a oraz p 6 |b, to a, b są pierwsze względem

p. Z lematu powyżej wiemy, że wtedy p i ab są względnie pierwsze, a to przeczy p

|ab.

⊳

• Wniosek: Jeśli p jest liczbą pierwszą i p

· · · · · a

, to dla pewnego i, p

• Wniosek: Jeśli p, q

, . . . , q

są liczbami pierwszymi i p|q

· · · · · q

, to dla

pewnego i, p = q

Ćwiczenia:

1. Wybierz wszystkie pary liczb względnie pierwszych występujące w prze-

dziale [4, 24] ⊂ N

2. Sprawdź, że najmniejsza liczba pierwsza p < n, która dzieli n jest nie

większa niż ⌊

√

⌋, gdy n = 63, 255, 333.

Zadania:

1. Udowodnij wniosek: Jeśli p jest liczbą pierwszą i p|a

· · · · · a

, to dla

pewnego i, p|a

2. Udowodnij wniosek: Jeśli p, q

, . . . , q

są liczbami pierwszymi i p|q

·· · ··q

to dla pewnego i, p = q

4.1.6

Faktoryzacja na liczby pierwsze

Twierdzenie 4.5

O rozkładzie na czynniki pierwsze Dla dowolnej liczby na-

turalnej n ≥ 2 istnieje dokładnie jeden rozkład na czynniki pierwsze, t.j. istnieje

jedyne r i istnieje jedyny zestaw liczb pierwszych p

≤ · · · ≤ p

taki, że

n = p

· · · · · p

⊳

Dowód

przez indukcję

Jeśli n jest liczbą pierwszą, to r = 1, p

= n. Jeśli dla m < n

twierdzenie jest prawdziwe i n nie jest liczbą pierwszą, to istnieją liczby a < n, b < n takie, że

n = ab. Z założenia indukcyjnego mamy

a = p

· · · · · p

, b = q

· · · · · q

, p

≤ · · · ≤ p

, q

≤ · · · ≤ q

Łączymy i sortujemy oba ciągi liczb pierwszych otrzymując ciąg p

′
1

≤ · · · ≤ p

′
r

, r = r

+ r

n = ab = p

′
1

· · · · · p

′
r

Mamy więc prawdziwość wniosku indukcyjnego dla n.

Przypuśćmy teraz, że mamy dwa rozkłady na czynniki pierwsze:

n = p

· · · · · p

= q

· · · · · q

Wtedy p

= q

dla pewnego i, bo p

. . . q

. Dzielimy obie strony powyższej równości przez

i stosujemy to samo rozumowanie dla p

. Po r

krokach otrzymamy po lewej stronie wartość

1. Prawa strona też musi być jeden, a więc nie może być żadnego q

, które nie uległo skróceniu.

To jest oba zestawy są identyczne.

⊳

• Przykłady rozkładów na czynniki pierwsze:

30 = 2 · 3 · 5, 37 = 37, 40 = 2 · 2 · 2 · 5

• Wnioski

1. Jeśli w rozkładzie na czynniki pierwsze liczby n, liczba pierwsza p

występuje e(p) razy, e(p) ≥ 0, to

n =

p liczba pierwsza

e(p)

2. Jeśli a =

e(p)

, b =

f (p)

są rozkładami na czynniki pierwsze

liczb a i liczb b, to

N W P (a, b) =

p liczba pierwsza

min(e(p),f (p))

N W W (a, b) =

p liczba pierwsza

max(e(p),f (p))

Ćwiczenia:

1. Znajdź rozkład na czynniki pierwsze dla n = 33, 55, 333, 555

2. Znajdź rozkład na czynniki pierwsze dla n = 33 · 55, 333 · 555
3. Znajdź na podstawie rozkładu na czynniki pierwsze wartość NW P (256, 96)

Problem: Udowodnij wniosek: Jeśli a =

e(p)

, b =

f (p)

są rozkładami na

czynniki pierwsze liczb a i liczb b, to

N W P (a, b) =

p liczba pierwsza

min(e(p),f (p))

N W W (a, b) =

p liczba pierwsza

max(e(p),f (p))

4.1.7

Liczby pierwsze – sito Eratostenesa

Lemat 4.2

J eśli n nie jest liczbą pierwszą, to istnieje liczba pierwsza p ≤

√

taka, że p|n ⊳

Dowód:

Jeśli n = ab, a, b

∈ N, a ≥ b > 1, to n = ab ≥ b

. Stąd b

≤

√

n i każda liczba

pierwsza p dzieląca b spełnia:

≤

√

n, p

⊳

Twierdzenie 4.6
Istnieje nieskończenie wiele liczb pierwszych. ⊳
Dowód

przez zaprzeczenie

Gdyby zbiór liczb pierwszych był skończony, t.j. gdyby istniało tylko n liczb pierwszych p

, . . . , p

to liczba q = p

· · · · · p

+ 1 daje przy dzieleniu przez p

resztę 1, i = 1, . . . , n. Dlatego q nie

dzieli się przez żadną liczbę pierwszą, a więc samo q musi być liczbą pierwszą większą od wszyst-

kich liczb pierwszych. Stąd q > q. Otrzymana sprzeczność dowodzi nieskończoności zbioru liczb

pierwszych.

⊳

Algorytm 4.2

Sito Eratostenesa

1. Wejście: n – szukamy liczb pierwszych w przedziale [1, n

]

2. Wyjście: tablica liczb całkowitych p[1..n

] taka, że |p[i]| = i, p[i] = i,

gdy i jest liczbą pierwszą oraz p[i] = −i, gdy i nie jest liczbą pierwszą,
i = 1, . . . , n

3. Metoda:

Krok 0: Utwórz tablicę

p[1..n

];

Krok 1: Dla

i = 1, . . . , n

: p[i] ← i;

Krok 2:

p[1]

← −1; k ← 2;

Krok 3:

← najmniejsze j ∈ [k, n] takie, że p[j] > 0 (jeśli istnieje)

Krok 4: Jeśli takie

j nie istnieje, to zwróć tablicę p[];

Krok 5: Dla

j = 2k, 3k, . . . , mk, mk

≤ n

: p[j] = −j;

Krok 6: Kontynuuj od kroku 3;

⊳

Ćwiczenie: Znajdź techniką sita Eratostenesa wszystkie liczby pierwsze z prze-
działu [1, 111].

4.1.8

Liczby Mersena

• Liczba Mersena jest liczbą pierwszą postaci 2

− 1

• Przykłady liczb Mersena: 3 = 2

− 1, 7 = 2

− 1, 31 = 2

− 1, 127 = 2

− 1

• Obserwacja: dla a, b

∈ N, a, b > 1, mamy:

1 + 2

+ (2

)

+ · · · + (2

)

−1

)

− 1

• Wniosek: 2

− 1 nie jest liczbą pierwszą bo

− 1 = (2

− 1) 1 + 2

+ (2

)

+ · · · + (2

)

−1

• Wniosek: Jeśli 2

− 1 jest liczbą pierwszą, to p jest liczbą pierwszą

Ćwiczenie: Czy liczba 2

1024

− 1 jest liczbą pierwszą?

4.1.9

Liczby Fermata

• Liczba Fermata jest liczbą pierwszą postaci 2

+ 1

• Przykłady liczb Fermata: 5 = 2

+ 1, 17 = 2

+ 1, 257 = 2

+ 1

• Obserwacje:

1. 2

+ 1 dzieli 2

− 1, bo

− 1 = 2

·2

− 1 =

− 1 = (2

− 1)(2

+ 1)

2. 2

+ 1 dzieli 2

·1

+ 1

3. Jeśli 2

+ 1 dzieli 2

·a

+ 1, to 2

+ 1 dzieli 2

·(a+2)

+ 1,

Dowód:

·(a+2)

+ 1

· 2

·a

+ 1

· 2

·a

+ 1

− 2

+ 1

· 2

·a

+ 1

−

− 1

+ 1

⊳

• Wniosek: 2

+ 1 dzieli 2

·a

+ 1 dla dowolnego r ∈ N oraz a nieparzystego

• Wniosek: Jeśli 2

+ 1, n ∈ N jest liczbą pierwszą, to istnieje r ∈ N takie,

że n = 2

Dowód:

Dowolna liczba naturalna n = 2

a dla pewnego r

∈ N ∪ {0} oraz a niepa-

rzystego. Jeśli a > 1, to na podstawie poprzedniego wniosku 2

+ 1 = 2

·a

+ 1 nie jest

liczbą pierwszą. Skoro 2

+ 1 jest liczbą pierwszą, to a = 1 i n = 2

⊳

Ćwiczenie: Czy liczba 2

1023

+ 1 jest liczbą pierwszą?

4.2

Algebra reszt

• Niech a, b, m

∈ Z, m 6= 0. Mówimy, że a przystaje do b modulo m i zapisu-

jemy a ≡ b (mod m) wtt a − b jest wielokrotnością m

• Relacja przystawania modulo m jest relacją równoważności

• Relacja przystawania modulo m nazywa się też relacją kongruencji

• Klasa równoważności [x]

nazywa się też klasą kongruencji elementu x ∈ Z

• Dla dowolnego m

∈ Z, m 6= 0, istnieje dokładnie |m| różnych klas kongru-

encji

• Zbiór

, . . . , r

−1

} ⊂ Z nazywa się pełnym zbiorem reszt modulo m wtt

= [r

]

∪ · · · ∪ [r

−1

]

• Jeśli x

≡ y

(mod m) oraz x

≡ y

(mod m), to

± x

≡ y

± y

(mod m)

≡ y

(mod m)

• Jeśli x

≡ y (mod m), k ∈ N, to

≡ y

(mod m)

≡ ky (mod m), −kx ≡ −ky (mod m)

• Jeśli x

≡ y (mod m), d|m, to x ≡ y (mod d)

• Jeśli x

≡ y (mod m), d|m, d|x, d|y, to

x
d

≡

y
d

(mod m/d)

• Reguła skracania: Jeśli m

∈ N, x, y, k ∈ Z oraz

≡ ky (mod m)

≡ y (mod m/NW P (k, m))

Dowód:

Niech d = N W P (k, m), m = dm

′

, k = dk

′

. Wtedy N W P (k

′

, m

′

) = 1 i dla

pewnej αm

′

+ βk

′

= 1. Stąd

′

|dk

′

− y) → m

′

− y) → m

′

|(x − y) →

|(x − y)

⊳

Dowód

inny dowód

Ponieważ d = N W P (k, m) dzieli kx, ky, oraz m, to

k
d

≡

k
d

(mod m/d)

Ale k/d oraz m/d są względnie pierwsze i m/d dzieląc (k/d)(x

− y) musi dzielić x − y.

⊳

• Jeśli x

≡ y (mod m

) oraz x ≡ y (mod m

), to

≡ y (mod NW W (m

, m

))

• Jeśli x

≡ y (mod m

), i = 1, . . . , n, to

≡ y (mod NW W (m

, . . . , m

))

1. Jeśli n =

k
i=0

jest rozwinięciem dziesiętnym liczby n ∈ N, 0 ≤ c

10, to

≡

i=0

(mod 9)

(9)

≡

i=0

(mod 3)

(10)

≡

i=0

(−1)

(mod 11)

(11)

2. Jeśli n =

k
i=0

jest rozwinięciem przy podstawie b > 1 liczby n ∈ N,

0 ≤ c

< b, to

≡

i=0

(mod b − 1)

≡

i=0

(−1)

(mod b + 1)

Ćwiczenia:

1. Pokaż, że własności z punktu jeden wynikają z własności punktu dwa.

2. Dlaczego kongruencja (10) wynika z kongruencji (9).

Zadania:

1. Udowodnij prawdziwość kongruencji (2).

2. Udowodnij prawdziwość kongruencji (2).

Przykład 4.1

rachunku reszt

• Znajdujemy resztę z dzielenia 2

1023

przez 7.

Ponieważ 2

= 8 ≡ 1 (mod 7) i 1023 = 3 · 341, to

1023

= (2

)

341

≡ 1

341

≡ 1 (mod 7)

• Obliczamy klasę kongruencji modulo 11 dla 3

1111

Ponieważ 3

≡ 1 (mod 11) oraz 1111 = 5 · 222 + 1, to

1111

= (3

)

222

· 3

≡ 1

222

· 3 ≡ 3 (mod 11)

• Jaką resztę z dzielenia przez 23 daje liczba x, jeśli 3x

≡ 15 (mod 23)?

Ponieważ 3x ≡ 3 · 5 (mod 23) oraz NW P (3, 23) = 1, to z własności skra-

cania x ≡ 5 (mod 23). W takim razie ta reszta wynosi 5

• Jaką resztę z dzielenia przez 8 daje liczba x, jeśli 3x

≡ 15 (mod 24)?

Ponieważ 3x ≡ 3 · 5 (mod 24) oraz NW P (3, 24) = 3, to z własności skra-

cania x ≡ 5 (mod 24/3). W takim razie x ≡ 5 (mod 8) i ta reszta wynosi

• Czy liczba 1234567890 dzieli się przez przez 9 ?

Tak, bo

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 0 = 45 ≡ 0 (mod 9)

• Czy liczba 1234567890 dzieli się przez przez 11 ?

Nie, bo

−1 + 2 − 3 + 4 − 5 + 6 − 7 + 8 − 9 + 0 = −5 ≡ 6 (mod 11)

⊳

Zadania:

1. Oblicz resztę z dzielenia 3

1023

przez 7

2. Oblicz resztę z dzielenia 2

1023

przez 11

3. Pokaż metodą reszt, że 7|(8

− 1) dla dowolnego k ∈ N

4. Jaką resztę z dzielenia przez 27 daje liczba x, jeśli 7x ≡ 21 (mod 27)?

5. Jaką resztę z dzielenia przez 9 daje liczba x, jeśli 3x ≡ 15 (mod 27)?

6. Czy liczba 9876543210 dzieli się przez przez 3 ?

7. Czy liczba 9876543215 dzieli się przez przez 11 ?

8. Rozwiąż równanie w resztach 14x − 2 ≡ 12 (mod 42)

9. Rozwiąż równanie w resztach 14x − 12 ≡ 2 (mod 120).

Problem:
W międzynarodowym systemie numeracji książek (ISBN) dziewięć pierwszych

cyfr dziesiętnych x

, i = 1, . . . , 9, tworzy numer, a dziesiąty symbol jest symbo-

lem kontrolnym obliczanym następująco:

i=1

(mod 11)

Jeśli x

= 10, to zapisywany jest symbol X.

Pokaż, że taki symbol kontrolny pozwala wykrywać błędne zapisy na jednej
pozycji i błędy polegające na zamianie dwóch symboli.

4.2.1

Równania w resztach

• Liniowe równanie w resztach ma postać:

≡ b (mod m)

gdzie m ∈ N, a, b ∈ Z

• Jeśli istnieje rozwiązanie równania ax

≡ b (mod m), to NW P (a, m)|b.

Dowód:

Jeśli ax

≡ b (mod m), to m|(ax − b), t.j. istnieje k ∈ Z takie, że

− b = km, b = ax − km

Skoro b jest kombinacją liniową liczb a oraz m, to b jest wielokrotnością N W P (a, m).

⊳

• Przykład: a = 10, b = 15, m = 25.

Warunek konieczny jest spełniony bo NW P (a, m) = NW P (10, 25) =
5|15 = b. Równanie ax ≡ b (mod m) jest spełnione np. dla x = 9.

• Jeśli N W P (a, m)

|b, to istnieje rozwiązanie równania ax ≡ b (mod m).

Dowód:

Z warunku N W P (a, m)

|b wynika istnienie kombinacji liniowej a i m dającej

wartość b. Mianowicie rozszerzony algorytm Euklidesa daje k

′

, l

′

∈ Z takie, że:

′

a + l

′

m = N W P (a, m)

′

N W P (a, m)

+ l

′

N W P (a, m)

= N W P (a, m)

N W P (a, m)

= b

Stąd dla k = k

′

b/N W P (a, m), l = l

′

b/N W P (a, m) : ka + lm = b. Dlatego m

|(ka − b) i

x = k = k

′

b/N W P (a, m) jest rozwiązaniem równania ax

≡ b (mod m).

⊳

• Przykład: a = 10, b = 15, m = 25.

Ponieważ NW P (a, m) = 5 oraz 3 · 10 + (−1) · 25 = 5, to

x = k

′

b/N W P (a, m) = 3

· 15/5 = 9

jest rozwiązaniem równania 10x ≡ 15 (mod 25).

• Jeśli x

′

> x, x

′

, x

∈ Z

są rozwiązaniami równania ax ≡ b (mod m), to

istnieje i ∈ [0, NW P (a, m)) takie, że:

′

≡ x + i

N W P (a, m)

(mod m)

Dowód:

Z tego, że ax

≡ b (mod m) i ax

′

≡ b (mod m) mamy

a(x

′

− x) ≡ 0 (mod m)

Jeśli a = N W P (a, m)a

′

, m = N W P (a, m)m

′

, to dla pewnego i

′

− x) = i

′

, x

′

− x =

′

, x

′

= x +

′

= x + im

′

gdzie i = i

′

. Ponieważ x, x

′

∈ Z, to 0 ≤ x

′

− x < m. Dlatego im

′

< m oraz

i < m/m

′

= N W P (a, m).

⊳

• Przykład: a = 10, b = 15, m = 25.

Obliczamy NW P (a, m) = NW P (10, 25) = 10, m

′

= m/NW P (a, m) =

25/5 = 5. Na podstawie rozwiązania x = 9 otrzymujemy inne rozwiązania
w Z

≡ x + im

′

(mod m)

= x = 9, x

= 9 + 1 · 5 = 14, x

= x

+ 5 = 19, x

= x

+ 5 = 24,

≡ 24 + 5 = 29 ≡ 4 (mod 25).

Zadania:
Znajdź wszystkie rozwiązania równania ax ≡ b (mod m), gdy:

1. a = 6, b = 18, m = 24

2. a = 12, b = 18, m = 24

3. a = 26, b = 39, m = 65

4. a = 26, b = 39, m = 78

5. a = 127, b = 51, m = 111

4.2.2

Chińskie twierdzenie o resztach

Twierdzenie 4.7

Chińskie twierdzenie o resztach

Niech m

, . . . , m

∈ N są wzajemnie względnie pierwsze, t.j.

N W P (m

, m

) = 1, i, j = 1, . . . , n, i 6= j

Określamy M = m

· · · · · m

. Niech też r

∈ N, r

∈ [0, m

) będzie dowolną

resztą modulo m

, i = 1, . . . , n. Wtedy istnieje dokładnie jedna liczba całkowita

∈ [0, M), która przystaje do r

modulo m

, i = 1, . . . , n. ⊳

Dowód:

Niech M

, M/m

oraz c

będzie rozwiązaniem równania M

≡ 1 (mod m

Rozwiązanie istnieje bo N W P (m

, M

) = 1. Niech teraz

′

, c

· · · + c

Zauważmy, że

≡ r

, i = 1, . . . , n

≡ 0 (mod m

), gdy i

6= j

′

= c

· · · + c

≡ r

, i = 1, . . . , n

Weźmy x

, mod

′

)

∈ [0, M). Sprawdzamy, że x ≡ r

, i = 1, . . . , n. Istnieje więc liczba x

spełniająca tezę twierdzenia.
Dla dowodu jednoznaczności x w [0, M ), przypuśćmy, że istnieją liczby x

≥ x

∈ [0, M) takie,

że

≡ r

(mod m

), x

≡ r

(mod m

), i = 1, . . . , n

Wtedy dla pewnych k

≥ 0, k

∈ Z, i = 1, . . . , n

− x

, . . . , m

− x

Ponieważ liczby m

, . . . , m

są względnie pierwsze, to M

− x

. Ponieważ x

− x

< M, to

warunek ten jest możliwy tylko gdy x

= x

⊳

Przykład 4.2

Szukamy wszystkie liczby x ∈ Z, które przystają do 1 modulo

2, do 3 modulo 5 i do 5 modulo 7.
Stosujemy chińskie twierdzenie o resztach dla parametrów:

= 1, m

= 2, r

= 3, m

= 5, r

= 5, m

= 7

M = m

= 70, M

= M/m

= 35, M

= M/m

= 14, M

= M/m

= 10

Rozwiązujemy równania M

≡ 1 (mod m

), i = 1, 2, 3 :

35c

≡ 1 (mod 2), 14c

≡ 1 (mod 5), 10c

≡ 1 (mod 7)

Wystarczy znaleźć po jednym rozwiązaniu tych równań, np.:

= 1, c

= 4, c

= 5

Wtedy zgodnie z dowodem chińskiego twierdzenia o resztach

′

= M

+ M

= 35 · 1 · 1 + 14 · 4 · 3 + 10 · 5 · 5 = 453

jest jednym z rozwiązań. Rozwiązanie bazowe dostajemy jako x = mod

(453) =

33. Pełny zbiór rozwiązań to klasa kongruencji liczby 33 modulo 70. ⊳

Zadania:
Znajdź wszystkie liczby x ∈ Z, które przystają do r

modulo m

, do r

mo-

dulo m

(w przykładach nieparzystych) oraz do r

modulo m

(w przykładach

parzystych) gdzie:

1. r

= 0, m

= 2, r

= 4, m

= 5

100

2. r

= 0, m

= 2, r

= 4, m

= 5, r

= 3, m

= 7

3. r

= 3, m

= 4, r

= 2, m

= 3

4. r

= 3, m

= 4, r

= 2, m

= 3, r

= 4, m

= 5

5. r

= 3, m

= 4, r

= 2, m

= 6

6. r

= 3, m

= 4, r

= 2, m

= 6, r

= 4, m

= 5

4.2.3

Twierdzenia Fermata o resztach

Twierdzenie 4.8

Twierdzenie Fermata o resztach

Jeśli p jest liczbą pierwszą i a ∈ Z, p 6 |a, to

−1

≡ 1 (mod p)

⊳

Dowód:

Rozważamy dwa iloczyny:

, 1 · 2 · 3 · · · · · (p − 1), y , (1 · a)(2 · a)(3 · a) . . . ((p − 1) · a) = a

−1

Zauważmy, że jeśli ia

≡ ja (mod p), j ≥ i, j, i = 1, . . . , p − 1, to p|(j − i)a. A ponieważ liczba

pierwsza p

6 |a, to p|(j − i). Ale j − i < p. Stąd j = i.

Stąd każdy czynnik y przystaje modulo p do dokładnie jednego czynnika liczby x. Tzn. liczba

y przystaje do liczby x modulo p :

≡ x

(mod p), a

−1

≡ x

(mod p)

Stosując regułę skracania kolejno dla 2, . . . , p

− 1 otrzymujemy

−1

≡ 1

(mod p)

⊳

Ćwiczenia:
Pokaż, że:

1. 7 dzieli 128

− 1

2. 7 dzieli 64

+ 41

3. 11 dzieli 128

− 1

4. 11 dzieli 64

+ 54

5. 5 dzieli 1281

− 1

6. 5 dzieli 641

+ 54

101

4.2.4

Funkcja Eulera

• Funkcja Eulera ϕ(n), n

∈ N określa ile liczb naturalnych z przedziału [1, n]

jest względnie pierwszych z n :

ϕ(n)

, |{k ∈ N : k ∈ [1, n], NW P (k, n) = 1}|

• Przykłady:ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2, ϕ(5) = 4

• Jeśli p jest liczbą pierwszą, to ϕ(p) = p

− 1

• Jeśli p jest liczbą pierwszą, to w przedziale [1, p

− 1], tylko liczby 1 · p, 2 ·

p, . . . , p

· p nie są względnie pierwsze z p

• Wniosek: ϕ(p

) = p

− p

• Wniosek: ϕ(p

) = p

− p

−1

• Twierdzenie: Jeśli m oraz n są względnie pierwsze, to

ϕ(mn) = ϕ(m)ϕ(n)

• Przykład:

ϕ(300) = ϕ(12

· 25) = ϕ(2

· 3 · 5

)

= ϕ(2

)ϕ(3)ϕ(5

) = (2

− 2)(3 − 1)(5

− 5) = 80

Dowód

równości ϕ(mn) = ϕ(m)ϕ(n)

Z chińskiego twierdzenia o resztach wiemy, że dla m

′

∈ [0, m) oraz n

′

∈ [0, n) istnieje dokładnie

jedno k

∈ [0, mn) o własności:

≡ m

′

(mod m), k

≡ n

′

(mod n),

To oznacza, że przekształcenie f

′

: [0, mn)

→ [0, m) × [0, n) określone następująco:

′

)

, (mod

′

), mod

′

))

jest odwzorowaniem różnowartościowym.

Modyﬁkujemy teraz funkcję modulo mod

(x), a

∈ N, x ∈ Z następująco:

mod

(x)

jeśli a

mod

(x)

w przeciwnym razie

Wtedy przekształcenie f : [1, mn]

→ [1, m] × [1, n] określone jako:

f (x)

, (mod

(x), mod

(x))

jest również odwzorowaniem różnowartościowym, bo f jest złożeniem różnowartościowego f

′

różnowartościowym mapowaniem (g

(u), g

(v)), gdzie

(u)

jeśli u = 0,

w przeciwnym razie

102

Ponieważ liczby m, n są względnie pierwsze, to własność N W P (k, mn) = 1 jest równoważna
koniunkcji własności N W P (k, m) = 1, N W P (k, n) = 1. Wiemy z analizy algorytmu Euklidesa,
że N W P (k, m) = N W P (mod

(k), m) = N W P (mod

(k), m).

Dlatego N W P (k, mn) = 1 jest równoważne koniunkcji własności N W P (mod

(k), m) = 1,

N W P (mod

(k), n) = 1. Stąd widzimy, że różnowartościowe przekształcenie f przekształca

wszystkie liczby pierwsze względem mn na wszystkie kombinacje liczb pierwszych względem m

i n odpowiednio. Stąd liczba ϕ(mn) = ϕ(m)ϕ(n).

⊳

4.2.5

Twierdzenie Eulera o resztach

Twierdzenie 4.9

Twierdzenie Eulera o resztach

Jeśli m ∈ N oraz a ∈ Z jest liczbą pierwszą względem m, to

ϕ(m)

≡ 1 (mod m)

⊳

Dowód:

Niech n

, ϕ(m). Rozważamy dwa iloczyny:

, b

· b

· · · · · b

, y

, (b

· a)(b

· a) . . . (b

· a) = a

gdzie liczba b

∈ [1, m] jest liczbą pierwszą względem m, i = 1, . . . , n.

Zauważmy, że jeśli b

≡ b

a (mod m), to reguła skracania daje b

≡ b

(mod m), t.j. j = i.

Stąd każdy czynnik y przystaje modulo m do dokładnie jednego czynnika liczby x. Tzn. liczba
y przystaje do liczby x modulo m :

≡ x

(mod m), a

≡ x

(mod m)

Stosując regułę skracania kolejno dla b

, . . . , b

otrzymujemy

(m)

≡ 1 (mod m)

⊳

• Inne rozwiązanie równania liniowego w resztach ax

≡ b (mod m) :

a = N W P (a, m)a

′

, b = N W P (a, m)b

′

−→ a

′

≡ b

′

(mod m)

Stąd

′

)

ϕ(m)

−1

′

≡ (a

′

)

ϕ(m)

−1

′

(mod m)

′

)

ϕ(m)

≡ (a

′

)

ϕ(m)

−1

′

(mod m)

≡ (a

′

)

ϕ(m)

−1

′

(mod m)

• Przykłady zastosowań twierdzenia Eulera o resztach:

–

Wyznaczamy resztę z dzielenia 2

126

przez 75 :

ϕ(75) = ϕ(3

· 5

) = 2 · 20 = 40, 126 = 3 · 40 + 6

≡ 1 (mod 75), 2

126

= 2

)

≡ 64 (mod 75)

103

–

Rozwiązujemy równanie 6x ≡ 5 (mod 13) :

φ(13) = 12, x

≡ 6

−1

5 (mod 13), x ≡ 6

5 (mod 13)

Ale

11 ≡ 6

· 11 ≡ 6

· 66 · 11 ≡ 6

(mod 13)

Stąd

≡ 11 · 5 (mod 13), x ≡ 3 (mod 13)

Ćwiczenia:

1. Wyznacz wartość funkcji Eulera ϕ(n), gdy:

(a) n = 127

(b) n = 210

2. Sprawdź, że:

(a) 127 dzieli liczbę 10

126

− 1

(b) 210 dzieli liczbę 11

− 1

Zadania:

1. Wyznacz resztę z dzielenia 2

125

przez 75

2. Rozwiąż równanie 7x ≡ 6 (mod 11) stosując twierdzenie Eulera o resztach

3. Pokaż, że twierdzenie Fermata jest szczególnym przypadkiem twierdzenia

Eulera o resztach.

4.2.6

Szyfrowanie – algorytm RSA

• Odkrywcy algorytmu RSA – Rivest, Shamir i Adelson

• Klucze w algorytmie RSA:

–

elementy prywatne:

1. czynnik p – duża liczba pierwsza, np. p > 2

500

2. czynnik q – duża liczba pierwsza q 6= p,

–

elementy publiczne:

1. dzielnik m – liczba złożona postaci m = p · q
2. wykładniki e, f – elementy nawzajem odwrotne modulo:

≡ 1 (mod (p − 1)(q − 1))

104

• Komunikat a podlegający zaszyfrowaniu: dowolna liczba a

∈ N, a < m

pierwsza względem dzielnika m

• Zaszyfrowanie:

, mod

)

• Odszyfrowanie:

a = mod

)

• Poprawność szyfrowania:

≡ a

(mod m)

∃k ∈ N, ef = 1 + k(p − 1)(q − 1)

= a · a

k(p

−1)(q−1)

= a · a

kϕ(pq)

= a · (a

ϕ(m)

)

· (a

ϕ(m)

)

≡ a · 1

≡ a (mod m)

Przykład 4.3

szyfrowania RSA

1. Ustalamy parametry algorytmu RSA: klucze prywatne – p = 17, q = 19;

klucze publiczne m = pq = 323, e = 131.

2. Poszukujemy wykładnika f odwrotnego do e = 131 modulo (p−1)(q−1) =

288, tj. ef ≡ 1 (mod 288). Ponieważ NW P (131, 288) = 1, to istnieją
f, g

∈ Z, takie,że

131f + 288g = 1, 131f + (131 · 2 + 26)g = 1, 131f

′

+ 26g = 1

gdzie f

′

= f + 2g. Bez stosowania rozszerzonego algorytmu Euklidesa

widzimy bezpośrednio, że f

′

= 1, g = −5 spełniają ostatnią z równości.

Stąd f = f

′

− 2g = 11.

3. Wybieramy komunikat do zaszyfrowania a < 323 taki, że NW P (a, 323) =

1, np. a = 7.

4. Zaszyfrowanie:

, mod

323

131

Ale stosując działania modulo 323 mamy:

131

= 7

· 7

1 ≡ 121 · (201)

1 ≡ 121 · 197 ≡ 258

Zaszyfrowane a = 7 wynosi r = 258.

5. Odszyfrowanie:

a = mod

) = mod

323

258

Ale

258

= 258 · 258

· 258

≡ 258 · 26 · 26

≡ 258 · 26 · 30

≡ 258 · 26 · 254 ≡ 7

Otrzymujemy więc prawidłowe odszyfrowanie komunikatu a = 7.

105

⊳

Zadanie: Zaszyfruj i odszyfruj komunikat a w schemacie RSA o parametrach:

1. a = 2, p = 3, q = 5, m =?, e = 5, f =?

2. a = 7, p = 3, q =?, m = 15, e = 5, f =?

3. a = 11, p = 17, q = 19, m = 323, e = 131, f = 11

Typowy scenariusz stosowania algorytmu RSA z kluczem N-bitowym, m ∈ I

bitowym (np. N = 512)

• Kroki nadawcy:

1. Wybierz losowo a < m względnie pierwsze z m i przedstaw a na N

bitach

2. Wyślij szyfr RSA r = mod

) dla a

3. Dla kolejnej N-bitowej porcji d danych szyfrowanych wyślij kod d

′

a XOR d, gdzie operacja XOR realizowana jest bit po bicie

• Kroki odbiorcy:

1. Odbierz r
2. Odszyfruj a = mod

)

3. Dla kolejnej odebranej N-bitowej porcji d

′

zdekoduj d = a XOR d

′

• Poprawność dekodowania:

a XOR d

′

= a XOR (a XOR d) = (a XOR a) XOR d = 0 XOR d = d

106

Document Outline

Zbiory
Algebry
Schematy rekurencyjne
Kongruencje
- Podzielnosc liczb calkowitych
- Algebra reszt

Matematyka dyskretna W adys aw Skarbek

Document Outline