Petr Hliněný, FI MU Brno 1 FI: IB000: Důkazové postupy
10 Důkazové postupy pro algoritmy10 Důkazové postupy pro algoritmy
Nyní si ukážeme, jak formální deklarativní jazyk z Lekce 9 využít k formálně přesným
induktivním důkazům vybraných algoritmů. Dá se říci, že tato lekce je ,,vrcholem v
naší snaze o matematické dokazování algoritmů v informatice.
2
Stručný přehled lekce
* Důkaz indukcí s ,,fixací parametrů .
* Důkaz indukcí vzhledem k součtu parametrů.
* Důkaz indukcí se ,,zesílením tvrzení .
Petr Hliněný, FI MU Brno 2 FI: IB000: Důkazové postupy
10.1 Technika ,,fixace parametru10.1 Technika ,,fixace parametru
Příklad 10.1. Uvažme deklaraci  obsahující pouze rovnici
g(x, y) = if x then y + g(x - 1, y) else 0 fi .
Věta. Pro každé m, n   platí g(m, n) 
z, kde z  m  n.2
Důkaz: Budiž n   libovolné ale pro další úvahy pevné. Dokážeme, že pro každé
m   platí g(m, n) 
z, kde z  m  n, indukcí vzhledem k m.2
* Báze m = 0. Platí g(0, n)  if 0 then n + g(0 - 1, n) else 0 fi  0.2
* Indukční krok. Nechť m + 1  k. Pak
g(k, n)  if k then n + g(k - 1, n) else 0 fi  n+g(k-1, n)  n+g(w, n) ,
kde je w  m. Podle I.P. platí g(w, n) 
u pro u  m  n. Dále
n + g(w, n) 
n + u  v, kde v  n + (m  n) = (m + 1)  n = k  n, a tím
jsme dohromady hotovi s důkazem g(k, n) 
v.
2
Petr Hliněný, FI MU Brno 3 FI: IB000: Důkazové postupy
10.2 Technika ,,indukce k součtu parametrů10.2 Technika ,,indukce k součtu parametrů
Příklad 10.2. Uvažme deklaraci  obsahující pouze rovnici
g(x, y) = if x then (if y then g(x - 1, y) + g(x, y - 1) else 0 fi) else 0 fi .
Věta. Pro každé m, n   platí g(m, n) 
0.2
Tvrzení této věty přímo nelze dokázat indukcí vzhledem k m, ani indukcí vzhledem
k n, neboť u žádného z m, n nemáme zaručeno, že se vždy zmenší. 2Důkaz lze ovšem
postavit na faktu, že se vždy zmenší alespoň jeden z m, n, neboli se vždy zmenší součet
m a n. To znamená, že výše uvedené tvrzení nejprve přeformulujeme do následující
(matematicky ekvivalentní) podoby:
Věta. Pro každé i   platí, že jestliže i = m + n pro kterákoliv m, n  ,
pak g(m, n) 
0. 2
Důkaz indukcí vzhledem k i: Báze i = 0 znamená, že 0 = m + n pro m, n  , neboli
m = n = 0. Dokazujeme tedy, že g(0, 0) 
0. Platí
g(0, 0)  if 0 then (if 0 then g(0 - 1, 0) + g(0, 0 - 1) else 0 fi) else 0 fi  0 .
Petr Hliněný, FI MU Brno 4 FI: IB000: Důkazové postupy
Indukční krok. Nechť i+1 = m+n, kde m, n  . Nyní rozlišíme tři možnosti (z nichž
první dvě jsou svým způsobem jen rozšířeními předchozí báze indukce):
* Pro m = 0 platí
g(0, n)  if 0 then (if n then g(0 - 1, n) + g(0, n - 1) else 0 fi) else 0 fi  0 .2
* Pro m > 0, n = 0 platí
g(m, 0)  if m then (if 0 then g(m - 1, 0) + g(m, 0 - 1) else 0 fi) else 0 fi 
 if 0 then g(m - 1, 0) + g(m, 0 - 1) else 0 fi  0 .2
* Pro m > 0, n > 0 platí
g(m, n)  if m then (if n then g(m - 1, n) + g(m, n - 1) else 0 fi) else 0 fi 
 if n then g(m - 1, n) + g(m, n - 1) else 0 fi  g(m-1, n)+g(m, n-1) .2
Podle I.P. platí g(m - 1, n) 
0 a současně g(m, n - 1) 
0, proto
g(m - 1, n) + g(m, n - 1) 
0 + g(m, n - 1) 
0 + 0  0 .
Tím jsme s důkazem matematickou indukcí hotovi. 2
Petr Hliněný, FI MU Brno 5 FI: IB000: Důkazové postupy
Zajímavější verze
Příklad 10.3. Uvažme deklaraci  obsahující pouze rovnici
g(x, y) = if x then (if y then g(x - 1, y) + g(x, y - 1) else 1 fi) else 1 fi .2
Věta. Pro každé m, n   platí g(m, n) 
k, kde k = m+n
m (kombinační
číslo).
Toto tvrzení opět budeme dokazovat indukcí vzhledem k i = m + n.2
Vzpoměňte si nejprve na známý Pascalův trojúhelník kombinačních čísel, který je definovaný
rekurentním vztahem
a + 1
b + 1
=
a
b + 1
+
a
b
.
Nepřipomíná to trochu naši deklaraci? Je však třeba správně ,,nastavit význam parametrů
a, b. 2
Důkaz indukcí vzhledem k i: Báze i = 0 znamená, že 0 = m + n pro m, n  , neboli
m = n = 0. Dokazujeme tedy, že g(0, 0) 
1. Platí
g(0, 0)  if 0 then (if 0 then g(0 - 1, 0) + g(0, 0 - 1) else 1 fi) else 1 fi  1 .
Petr Hliněný, FI MU Brno 6 FI: IB000: Důkazové postupy
Indukční krok. Nechť i+1 = m+n, kde m, n  . Opět rozlišíme stejné tři možnosti:
* Pro m = 0 platí
g(0, n)  if 0 then (if n then g(0 - 1, n) + g(0, n - 1) else 1 fi) else 1 fi  1 .2
* Pro m > 0, n = 0 platí
g(m, 0)  if m then (if 0 then g(m - 1, 0) + g(m, 0 - 1) else 1 fi) else 1 fi 
 if 0 then g(m - 1, 0) + g(m, 0 - 1) else 1 fi  1 .2
* Pro m > 0, n > 0 platí
g(m, n)  if m then (if n then g(m - 1, n) + g(m, n - 1) else 1 fi) else 1 fi 
 if n then g(m - 1, n) + g(m, n - 1) else 1 fi  g(m-1, n)+g(m, n-1) .2
Podle I.P. platí g(m - 1, n) 
k1, kde k1  m-1+n
m-1 , a současně
g(m, n - 1) 
k2, kde k2  m+n-1
m . 2Přitom z Pascalova trojúhelníka plyne
m + n - 1
m - 1
+
m + n - 1
m
=
m + n - 1 + 1
m
=
m + n
m
,
a proto
g(m - 1, n) + g(m, n - 1) 
k1 + k2 
k 
m + n
m
.
2
Petr Hliněný, FI MU Brno 7 FI: IB000: Důkazové postupy
10.3 Technika ,,zesílení dokazovaného tvrzení10.3 Technika ,,zesílení dokazovaného tvrzení
Příklad 10.4. Uvažme deklaraci  obsahující tyto rovnice:
f(x) = if x then h(x) else 1 fi
h(x) = if x then f(x - 1) + h(x - 1) else 1 fi
Věta. Pro každé n   platí f(n) 
m, kde m = 2n
.
Požadované tvrzení bohužel nelze přímo dokázat indukcí podle n. 2Řešením je přeformulování
dokazovaného tvrzení do silnější podoby, kterou již indukcí dokázat lze:
Věta. Pro každé n   platí f(n) 
m a h(n) 
m, kde m = 2n
. 2
Důkaz, již poměrně snadno indukcí vzhledem k n:
* Báze n = 0. Platí
f(0)  if 0 then h(0) else 1 fi  1,
h(0)  if 0 then f(0 - 1) + h(0 - 1) else 1 fi  1.
Petr Hliněný, FI MU Brno 8 FI: IB000: Důkazové postupy
* Indukční krok: Nechť n + 1  k, pak platí
f(k)  if k then h(k) else 1 fi  h(k) 
 if k then f(k - 1) + h(k - 1) else 1 fi  f(k-1)+h(k-1)  f(w)+h(k-1) ,
kde w  k - 1 = n. Podle I.P. platí f(w) 
m, kde m = 2n
. 2Zároveň také
(naše ,,zesílení ) platí i h(w) 
m, a proto
f(w) + h(k - 1) 
m + h(k - 1) 
m + h(w) 
m + m  q ,
kde q = m + m = 2m = 2  2n
= 2n+1
= 2k
. Proto tranzitivně f(k)  q a
první část našeho tvrzení platí i pro n + 1  k. 2
Podobně je třeba ještě dokončit druhou část tvrzení.
h(k)  if k then f(k - 1) + h(k - 1) else 1 fi 
f(k - 1) + h(k - 1) 
f(w) + h(k - 1) ,
kde w  k - 1 = n. Podle I.P. platí f(w) 
m, kde m = 2n
, a také
h(w) 
m, tudíž opět
f(w) + h(k - 1) 
m + h(k - 1) 
m + h(w) 
m + m  q ,
kde q = m + m = 2  2n
= 2n+1
= 2k
. Proto h(k)  q a i druhá část našeho
tvrzení platí pro n + 1  k.
2
Petr Hliněný, FI MU Brno 9 FI: IB000: Důkazové postupy
10.4 Dva dobře známé školní algoritmy10.4 Dva dobře známé školní algoritmy
Číslice dekadického zápisu
Příklad 10.5. Mějme přirozené číslo m. Jednotlivé číslice i-tého řádu jeho dekadického
zápisu získáme deklarací
c(m, i) = if i then c(m ÷ 10, i - 1) else m - 10  (m ÷ 10) fi . 2
Dokažte:
Věta. Pro každá m, i   platí c(m, i) 
s, kde s je číslice řádu i (počítáno od
nultého zprava) v dekadickém zápise čísla m, nebo s  0 v případě, že dekadický
zápis čísla m má méně než i + 1 číslic. 2
Důkaz: Použijeme techniku fixace parametru m při indukci podle i.
* Báze i = 0. Platí
c(m, 0) 
m - 10  (m ÷ 10) 
t, kde t = m mod 10 .
V tomto výsledku mod znamená známou funkci modulo definovanou vztahem
x = x/y  y + (x mod y). Tudíž t je poslední číslicí dekadického zápisu m.
Petr Hliněný, FI MU Brno 10 FI: IB000: Důkazové postupy
* Indukční krok: Nechť i + 1  j, pak platí
c(m, j)  if j then c(m ÷ 10, j - 1) else m - 10  (m ÷ 10) fi 
 c(m ÷ 10, j - 1) 
c(p, w),
kde p  m/10 a w  j - 1 = i. 2Podle I.P. platí c(p, w) 
t a t je číslice
i-tého řádu dekadického zápisu čísla p. Jelikož m = 10p + (m mod 10) a násobení
deseti v dekadické soustavě znamená posun číslic v zápise ,,o jedno doleva , je t
zároveň číslice i + 1 = j-tého řádu dekadického zápisu čísla m. To je přesně co
bylo třeba dokázat.
2
Petr Hliněný, FI MU Brno 11 FI: IB000: Důkazové postupy
Euklidův algoritmus
Vˇeta 10.6. Uvažme deklaraci  obsahující pouze rovnici
g(x, y) = if x - y then g(x - y, y) else (if y - x then g(x, y - x) else x fi) fi .
Pak pro každé nenulové m, n   platí g(m, n)  z, kde z je největší
společný dělitel čísel m, n.2
Důkaz indukcí k i = m + n.
(Tj. dokazujeme následující tvrzení: Pro každé i  2 platí, že jestliže i  m+n,
kde m, n  , m, n > 0, pak z je největší společný dělitel čísel m, n.) 2
V bázi pro i = 2 je m, n = 1 a platí
g(1, 1)  if 1 - 1 then g(1 - 1, 1) else (if 1 - 1 then g(1, 1 - 1) else 1 fi) fi 
 if 0 then g(1 - 1, 1) else (if 1 - 1 then g(1, 1 - 1) else 1 fi) fi 
 if 1 - 1 then g(1, 1 - 1) else 1 fi  if 0 then g(1, 1 - 1) else 1 fi  1 .
Petr Hliněný, FI MU Brno 12 FI: IB000: Důkazové postupy
Indukční krok. Nechť i + 1 = m + n kde m, n  . Probereme tři možnosti:
* m = n. Pak
g(m, n)  if m - n then g(m - n, n) else (if n - m then g(m, n - m) else m fi) fi 
if 0 then g(m - n, n) else (if n - m then g(m, n - m) else m fi) fi 
if n - m then g(m, n - m) else m fi  if 0 then g(m, n - m) else m fi  m .2
* m < n. Pak
g(m, n)  if m - n then g(m - n, n) else (if n - m then g(m, n - m) else m fi) fi 
if 0 then g(m - n, n) else (if n - m then g(m, n - m) else m fi) fi 
if n - m then g(m, n - m) else m fi  if z then g(m, n - m) else m fi 
g(m, n - m)  g(m, k) ,
kde k  n-m. 2Platí m+k = m+(n-m) = n  i, takže podle I.P. také
platí g(m, k)  z, kde z je největší společný dělitel čísel m a n - m.
Ověříme, že z je největší společný dělitel čísel m a n.
 Jelikož číslo z dělí čísla m a n-m, dělí i jejich součet (n-m)+m = n.
Celkem z je společným dělitelem m a n.2
 Buď d nějaký společný dělitel čísel m a n. Pak d dělí také rozdíl n - m.
Tedy d je společný dělitel čísel m a n-m. Jelikož z je největší společný
dělitel čísel m a n - m, nutně d dělí z a závěr platí.
Petr Hliněný, FI MU Brno 13 FI: IB000: Důkazové postupy
* m > n. Pak
g(m, n)  g(m - n, n)  g(k, n) ,
kde k  m - n. Podle I.P. platí g(k, n)  z, kde z je největší společný
dělitel čísel m - n a n. Podobně jako výše ověříme, že z je také největší
společný dělitel čísel m a n.
2
2
Pozn´amka: Jak byste výše uvedený zápis Euklidova algoritmu vylepšili, aby správně
,,počítal největšího společného dělitele i v případech, že m = 0 nebo n = 0?
Co v takových případech selže při současném zápise?