*{) Strukturální indukce Nyní se naplno ponoříme do hlubin induktivních definic a strukturální indukce, látky sice velmi abstraktní, ale pro informatiky potřebné. Stručný přehled lekce * Problematika jednoznačnosti induktivních definic množin. * Induktivní definice funkcí, použití strukturální indukce. * Nazpět k matematické logice: sémantika výrokové logiky a formální prevod do normálního tvaru. Petr Hliněný, Fl MU Brno, 2024 1/19 Fl: IB000: Strukturální indukce Zopakování na začátek Definice 6.0. Induktivní definice množiny. Jedná se obecně o popis (nějaké) množiny M v následujícím tvaru: • Je dáno několik pevných bazických prvků ai, 0,2,..., G M. • Je dán soubor induktivních pravidel typu Jsou-li (libovolné prvky) xi,... ,xt G M, pak také y G M. V tomto případě je y typicky funkcí y = • • • (v pravidle číslo i).c Pak naše induktivně definovaná množina M je určena jako nejmenší (inkluzí) množina vyhovující všem těmto pravidlům. Petr Hliněný, Fl MU Brno, 2024 2/19 Fl: IB000: Strukturální indukce 6.1 Jednoznačnost induktivních definic Definice: Řekneme, že daná induktivní definice množiny M je jednoznačná, právě když každý prvek M lze odvodit z bázických prvků pomocí induktivních pravidel právě jedním způsobem. • Induktivní definice množiny přirozených čísel N je jasně jednoznačná. • Podobně je jednoznačná následující definice množiny M C N; - 2,11 G M - Jestliže x G M, pak také x + 2 G M. □ Avšak jednoznačná už není tato induktivní definice množiny PCN; - 2,11 G P - Jestliže x E P, pak také x + 3 G P. Proč? iTo proto, že například prvek 11 G P lze získat jednou jako bázický prvek definice a podruhé z bázického prvku 2 G P trojí iterací pravidla 'x + 3 G P' (a je mnoho jiných prvků majících více odvození v P). • V čem tedy spočívá důležitost jednoznačných induktivních definic množin? Je to především v dalším možném využití induktivní definice množiny jako „základny" pro odvozené vyšší definice, viz následující. Petr Hliněný, Fl MU Brno, 2024 3/19 Fl: IB000: Strukturální indukce Příklad 6.1. Jednoznačnost induktivní definice 01-řetězců. Nad binární abecedou E = {0,1} induktivně definujeme speciální množinu řetězců následujícím předpisem: • '0', 'Olľ G B (bázické prvky). □ • Jestliže x G B a řetězec x končí znakem 0, pak také x + 'Oľ G B. • Jestliže x G B a řetězec x končí znakem 1, pak také x + '00' G 5. □ Dokažte, že uvedená definice množiny B je jednoznačná. Zde je přirozené pro důkaz aplikovat matematickou indukci. Avšak na rozdíl od dříve probíraných příkladů zde nevidíme žádný celočíselný „parametr n", a proto musíme nejprve za něj definovat vhodnou náhradu, • konkrétně „indukci podle délky odvození prvku x G B11, • kterážto délka je definována jako počet aplikací induktivních pravidel potřebných k odvození x G B. • Přesně řečeno, naši indukci povedeme podle struktury odvození prvků naší induktivní množiny a budeme tudíž mluvit o strukturální indukci. Petr Hliněný, Fl MU Brno, 2024 4/19 Fl: IB000: Strukturální indukce ■r □ * '0','Oil' G B (bazické prvky). * Jestliže x G B a řetězec x končí znakem 0, pak také x + '01' G B. * Jestliže x G B a řetězec x končí znakem 1, pak také x + '00' G 5. Důkaz: Nejprve musíme ověřit jednoznačnost definice množiny B pro její bazické prvky, tj. je třeba zkontrolovat, že žádný z bazických prvků případně nelze odvodit i některým(i) z pravidel. Pro řetězec '0' G B je to jasné z jeho minimální délky, ale řetězec 'Olľ G B by případně mohl být odvozený z předchozího z hlediska své délky. nAvšak žádné pravidlo nedává řetězec končící znaky 11. Báze indukci je tak hotova. V indukčním kroku předpokládáme, že tvrzení platí pro všechny dříve odvozené prvky množiny B a nahlédneme na prvek y G B dále odvozený jedním z daných pravidel. Nechť y končí znakem 0; pak y G B určitě musel být odvozen použitím „x + '00' G B" jako posledního pravidla. nJe tedy jednoznačně y = # + '00' a zároveň podle indukčního předp. byl řetězec x G B odvozen jednoznačně. [ ] Tudíž y G B je odvozen jednoznačně^ Obdobně postupujeme, pokud y končí znakem 1; pak y G B určitě musel být odvozen použitím „x + '01' G 5" jako posledního pravidla. nJe tedy jednoznačně y = x + 'Oľ a zase podle indukčního předpokladu byl řetězec x G B odvozen jednoznačně. Tudíž y e B je odvozen jednoznačně i v tomto případě. n Petr Hliněný, Fl MU Brno, 2024 5/19 Fl: IB000: Strukturální indukce 6.2 Induktivní definice funkcí Induktivně definovaná množina povětšinou nemá valný význam sama o sobě, avšak poskytuje definiční obor pro následnou induktivně definovanou funkci. Pro ilustraci z informatického světa si vezměte, že induktivní definice množiny mnohdy definuje prostě jen syntaxi, tedy správný způsob zápisu nějaké instrukce či programu, □ale k tomu je nutno také podat definici sémantiky, tedy významu toho správně zapsaného - co se má vlasně provést nebo vykonat. □ Definice 6.2. Induktivní definice funkce z induktivní množiny. Nechť množina M je dána jednoznačnou induktivní definicí. Pak říkáme, že funkce T : M X je definována induktivně (vzhledem k induktivní definici M), pokud je řečeno: • Pro každý z bázických prvků ai, 0,2,..., G M je určeno F{ai) = C{. • Pro každé induktivní pravidlo typu "Jsou-li (libovolné prvky) xi,..., X£ G M, pak také /(xi,..., x i) G M" je definováno ^( /(^í? • • • 5 xl)) na základě hodnot T(x\),..., T(x£). Petr Hliněný, Fl MU Brno, 2024 6/19 Fl: IB000: Strukturální indukce Ilustrační příklady Ilustrujme si induktivní definici funkce dětskou hrou na „tichou poštu". Definičním oborem je řada sedících hráčů, kde ten první je bazickým prvkem a každý následující (mimo posledního) odvozuje hráče sedícího hned za ním (nebo vedle) jako další prvek hry. □ Hodnotou bázického prvku je první (vymyšlené) posílané slovo. Induktivní pravidlo pak následujícímu hráči přiřazuje slovo, které je odvozeno („zkomolením") ze slova předchozího hráče. Výsledkem hry pak je hodnota-slovo posledního hráče. Petr Hliněný, Fl MU Brno, 2024 7/19 Fl: IB000: Strukturální indukce ■r Pro další příklad se podívejme třeba do manuálu unixového příkazu test No, problematická je otázka jednoznačnosti této definice - jednoznačnost není vynucena (jen umožněna) syntaktickými pravidly, jinak je pak dána nepsanými konvencemi implementace příkazu. To je pochopitelně z matematického hlediska špatně, ale přesto jde o pěknou ukázku z praktického života informatika. EXPRESSION: EXPRESSION is true or false ( EXPRESSION ) ! EXPRESSION EXPRESSI0N1 -a EXPRESSI0N2 EXPRESSI0N1 -o EXPRESSI0N2 [-n] STRING STRING1 = STRING2 and sets exit status. It is one of: EXPRESSION is true EXPRESSION is false both EXPRESSI0N1 and EXPRESSI0N2 are true either EXPRESSI0N1 or EXPRESSI0N2 is true the length of STRING is nonzero the strings are equal □ Petr Hliněný, Fl MU Brno, 2024 8/19 Fl: IB000: Strukturální indukce 6.3 Použití strukturální indukce Strukturální indukce je matematickou indukcí jako každá předchozí indukce. Hned je však vidět na první pohled zásadní rozdíl, nemáme zde žádný „parametr rí\ podle kterého bychom indukci přirozeně vedli. Místo explicitního parametru problému indukci pak vedeme podle délky odvození (počtu použitých induktivních pravidel) prvku induktivní množiny. Definice: Mějme induktivně definovanou množinu M a na jejích prvcích formulované tvrzení T(m), kde m G M. iTvrzení T (m) dokazujeme strukturální indukcí podle množiny M takto: • Dokážeme platnost T(mn) pro každý bázický prvek mn G M. • Pro každý nebázický prvek m G M vybereme induktivní pravidlo odvozující m G M z prvků mi,..., G M a předpokládáme platnost tvrzení T {mi) pro všechna i = 1,..., k. Z těchto předpokladů pak dokážeme platnost tvrzení T(m). □ Poznámka: Někdy může nastat (ale ne v jednoznačných definicích), že prvek m G M vyplývá z více induktivních pravidel určujících množinu M. Nemusíte dokazovat indukční krok pro každé pravidlo vedoucí k m G M, nýbrž vám stačí si vybrat jedno. Petr Hliněný, Fl MU Brno, 2024 9/19 Fl: IB000: Strukturální indukce Příklad 6.3. Induktivní definice na přirozených číslech následníkem. Vzpomeňte si z Oddílu 5.3, že přirozená čísla lze definovat induktivně bazickým prvkem 0 G N a pravidlem nGN^ succ(n) G N. Pišme zkráceně s(n) místo succ(n). Na množině N definujme funkci /(n) takto • /(O) = 0, □ • pokud n G N, tak f(s(n)) = s(s(f(n))). □ Dokažte, že /(n) = 2n pro každé n G N. Důkaz: V bázi skutečně platí /(O) = 0 = 2 • 0. □ Pro jakékoliv n G N pak můžeme (viz induktivní pravidlo) předpokládat, že f(n) = 2n platí. Z tohoto předpokladu pak přímočaře odvozujeme hodnotu f(s(n)) takton /(s(n)) = s(s(/(n))) = s(s(2n)) = s(2n + 1) = 2n + 2 = 2(n + 1). □ A jelikož přirozeně f(s(n)) = /(n + 1), tvrzení /(n + 1) = 2(n + 1) platí a jsme s důkazem hotovi. n Petr Hliněný, Fl MU Brno, 2024 10/19 Fl: IB000: Strukturální indukce Příklad 6.4. Jednoduché aritmetické výrazy a jejich význam. Nechť je dána abeceda E = {0,1, 2, 3,4, 5, 6, 7,8,9, 0, 0, (,)}. Definujme množinu jednoduchých výrazů SExp C E* induktivně takto: * Dekadický zápis každého přirozeného čísla n je prvkem SExp (bázické prvky). * Jestliže x,y £ SExp, pak také (x) 0 (y) a (x) 0 (y) jsou prvky SExp. * Jak snadno nahlédneme, díky nucenému závorkování je tato induktivní definice jednoduchých výrazů SExp jednoznačná. Tímto jsme aritmetickým výrazům přiřadili jejich „formu", tedy syntaxi. Pro přiřazení „významu", tj. sémantiky aritmetického výrazu, následně definujme funkci vyhodnocení Val: SExp —> N induktivně takto: * Pro bázické prvky: Va/(n) = n, kde n je dekadický zápis přirozeného čísla n. * První induktivní pravidlo: Val((x) 0 (y)) = Val(x) + Val(y). * Druhé induktivní pravidlo: Val((x) 0 (y)) = Val(x) • Val(y). Co je pak „správným významem" (hodnotou) uvedených aritmetických výrazů? □ Petr Hliněný, Fl MU Brno, 2024 11/19 Fl: IB000: Strukturální indukce Příklad 6.5. Důkaz správnosti přiřazeného „významu" Val: SExp —)► N. Věta. Pro každý výraz ,C,...} je množina výrokových proměnných. Množina ^výrokových formulí je dána těmito pravidly induktivní definice: * Bázickými prvky T jsou proměnné V, tj. X G J- pro každé X G V. * {negace) Je-li (p G J7, pak také je prvkem .F.c * (implikace) Je-li 92,^ G J7, pak také (^) je prvkem .F.c Zároveň platí, že závorky okolo (p lze vynechat pouze pokud (f G V nebo <^ bylo vytvořeno induktivním pravidlem negace. To stejné platí pro vynechávání závorek okolo ^. Poznámka: Již nad rámec předchozí definice patří dříve uvedené syntaktické zkratky * ((/?) V (ip) (disjunkce/„nebo") je jiný zápis formule -|(<£>) (ip), * (if) A (ip) (konjunkce/„a") je jiný zápis formule -,(-,(<£>) V * ((/?) (ip) (ekvivalence) je jiný zápis formule ((cp) =^> (ip)) A ((ip) =^> (<£>))■ Petr Hliněný, Fl MU Brno, 2024 13/19 Fl: IB000: Strukturální indukce ■r Sémantika výrokové logiky Na základě jednoznačné induktivní definice množiny J7 výrokových formulí nyní můžeme podat přesnou induktivní definici funkce vyhodnocení (logické hodnoty formulí). Nechť valuace (ohodnocení) je funkce v : V —>> {0,1}. Definice 6.6. Sémantika (význam) výrokové logiky. Pro každou valuaci v definujeme funkci sv\ .F->{0,1}, zvanou vyhodnocení formule a vzhledek k u, ninduktivně takto: • s„(X) := v(X) pro každé IeP. q í í w 1 jestliže su(ip) = 0; 0 jestliže su((p) = 1 a su(tfj) = 0; Petr Hliněný, Fl MU Brno, 2024 14/19 Fl: IB000: Strukturální indukce Převod formulí do normálního tvaru V dalším se vrátíme k logickým formulím v normálním tvaru (viz Oddíl 2.2), tedy k formulím, ve kterých se negace vztahuje pouze k výrokovým proměnným. Tvrzení 6.7. Každou výrokovou formuli lze převést do normálního tvaru, pokud k povolíme i užívání odvozených spojek A a V. • Pro ilustraci, k formuli ~^(A =^> B) je ekvivalentní normální tvar A A • k formuli -.(C A (-^4 B)) je ekvivalentní -.C V (-^4 A -.B), □ • k formuli -.((A => B) C) je ekvivalentní (A B) A -iC. Petr Hliněný, Fl MU Brno, 2024 15/19 Fl: IB000: Strukturální indukce ■r Metoda 6.8. Převod formule p do normálního tvaru ÍF{p)-Používáme T{X) jako „je pravda, že X" a Q{X) jako „nenípravda, že X". F(Ä) = A g (Ä) = j-(-v) = g{p) g(^) = g{^)yg{ip) j"(vvv) = j^vjw a(^v^) = g() T(p &ip) = T(p) ^ J"(» g(ip &tp) = F(p) ^ G{ip)n Pro predikátové formule toto rozšíříme ještě o pravidla: j-~(\/x. (p) = \/x. g (yx. (A =>■ ->{B V ->(C => ->A))). Užitím uvedeného postupu získáme: F(-,(A =>->(B V->(C =>-.A)))) = Q (A => ->(B V -i(C => ->A))) =□ ÍF(Ä) A g(^(B V -i(C => ~^A))) = A A F(B V -i(C => -<Á)) =□ AA(J(B)VJ(n(C^nil))) = AA(Bvg(C=>->A)) =□ A A (B V (^(C) A = i A (B V (C A T (A))) =□ AA(BV(CAi)) Petr Hliněný, Fl MU Brno, 2024 16/19 Fl: IB000: Strukturální indukce Důkaz pro normální tvar formule Na závěr následuje další ilustrativní ukázka důkazu strukturální indukcí. Věta 6.9. Pro libovolnou výrokovou formuli p platí (viz Metoda 6.8), že a) J~(p) je formule v normálním tvaru ekvivalentní k p b) a G (p) je formule v normálním tvaru ekvivalentní negaci -op. Důkaz povedeme indukcí ke struktuře formule, neboli indukci povedeme podle „délky" i - počtu aplikací induktivních pravidel při sestavování formule p. • Báze indukce (í — 0): Pro všechny atomy, tj. výrokové proměnné, zřejmě platí, že T{Ä) — A je ekvivalentní A a G(A) = -^A je ekvivalentní ->A • V indukčním kroku předpokládejme, že a) i b) platí pro všechny formule p délky nejvýše £. Vezmeme si formuli i/; délky £ + 1, která je utvořená jedním z následujících způsobů: Petr Hliněný, Fl MU Brno, 2024 17/19 Fl: IB000: Strukturální indukce ý = -.<£. Podle výše uvedeného induktivního předpisu je J7^) = J7^^) — G() je ekvivalentní negaci formule tpi (^2, což jsme zde měli dokázat. Petr Hliněný, Fl MU Brno, 2024 18/19 Fl: IB000: Strukturální indukce * ý = {ifi V ip2). Zde si musíme opět uvědomit, že spojka V je pro nás jen zkratka (ale nelze ji v důkaze opomenout, neboť Metoda 6.8 ji používá ve svých induktivních pravidlech), a přepsat ^ = (-^pi ^2)- Potom podle předchozích dokázaných případů víme, že J7^) = F^tpi ^2) = ^("■^í) =^ ^(^2) je ekvivalentní formuli (-^1 ^2) = V7- c°ž bylo třeba dokázat. Stejně tak G(ip) = G(~^