【2分木】に関する知恵袋
【質問】
論理学の問題です。分木の知恵袋を理解したいのであれば、OCRのソフトのコストをいうと、定義１ Σをラベルの集合とする. Σ-２分木を次のように帰納的に定義する.(1) a ∈Σなら a はΣ-２分木である.(2) a ∈Σ, S , T がΣ-２分木であるとき、OCRのソフトのコストを理解したいのであれば、Node(a, S, T)はΣ-２分木である.上記の定義にもとづいて、分木の知恵袋を理解したいのであれば、以下の問いに答えよ.問題１(1)Σ-2分木Tの高さh(T)を定義せよ（ただし、a∈Σのとき、h(a) = 0 とおく.)(2)Σ-2分木Ｔの葉の個数c(t)を定義せよ.(3)任意のΣ-2分木Ｔについてc(T) <= 2^h(T)となることを示せ.問題２(1)Σ-２分木Ｔの部分木の集合Sub(T)を定義せよ.(2)Σ-２分木S,Tについて、S∈Sub(T)ならばL(Ｓ)⊆Ｌ（Ｔ）となることを示せ.上記の問題なのですが、問題１(1)ですでに何をどうすればいいのかさっぱり分かりません。考え方だけでも結構ですので、どなたか教えていただけないでしょうか？よろしくお願いします。
【解答】
問題1(1)・a∈Σ なら h(a) = 0．・a ∈Σ で S, T がΣ-2分木であるとき h(Node(a, S, T)) = max{ h(S), h(T) } + 1．(2)・a∈Σ なら c(a) = 1．・a ∈Σ で S, T がΣ-2分木であるとき c(Node(a, S, T)) = c(S) + c(T)．(3)帰納法で示す．まず，a∈Σ なら c(a) = 1 ≦ 1 = 2^0 = 2^h(a)．次に，Σ-2分木 S, T について c(S) ≦ 2^h(S)，c(T) ≦ 2^h(T)が成り立つと仮定すると，任意の a∈Σ に対してc(Node(a, S, T)) = c(S) + c(T) ≦ 2^h(S) + 2^h(T)≦ 2^(max{ h(S), h(T) }) + 2^(max{ h(S), h(T) })= 2・2^(max{ h(S), h(T) })= 2^(max{ h(S), h(T) } + 1)= 2^h(Node(a, S, T))より c(Node(a, S, T)) ≦ 2^h(Node(a, S, T)) が成り立つ．以上より，任意のΣ-2分木 T について c(T) ≦ 2^h(T) が成り立つ．問題2(1)・a∈Σ なら Sub(a) = { a }．・a ∈Σ で S, T がΣ-2分木であるとき Sub(Node(a, S, T)) = Sub(S)∪Sub(T)∪{ Node(a, S, T) }．(2)各Σ-2分木 T に対する L(T) を次のように定義する：・a∈Σ なら L(a) = { a }．・a∈Σ で S, T が Σ-2分木であるとき L(Node(a, S, T)) = L(S)∪L(T)∪{ a }．このとき，任意のΣ-2分木 S, T に対して，S∈Sub(T) ⇒ L(S)⊆L(T)が成り立つことを，T に関する帰納法によって示す．まず，a∈Σ のとき S∈Sub(a) = { a } とすると S = a だから，L(S) = L(a) ⊆ L(a)．次に，Σ-2分木 T1, T2 について S∈Sub(T1) ⇒ L(S)⊆L(T1) ・・・・・①S∈Sub(T2) ⇒ L(S)⊆L(T2) ・・・・・②が成り立つと仮定し，任意の a∈Σ をとって S∈Sub(Node(a, T1, T2)) ⇒ L(S)⊆L(Node(a, T1, T2))が成り立つことを示す．そのために S∈Sub(Node(a, T1, T2)) とすると，Sub(Node(a, T1, T2)) = Sub(T1)∪Sub(T2)∪{ Node(a, T1, T2) } より，(a) S∈Sub(T1) または (b) S∈Sub(T2) または (c) S = Node(a, T1, T2)が成り立つ．(a) S∈Sub(T1) の場合，帰納法の仮定①より L(S)⊆L(T1) であり，また，L の定義から L(T1)⊆L(Node(a, T1, T2)) であるから，L(S)⊆L(Node(a, T1, T2)) となる．(b) S∈Sub(T2) の場合，帰納法の仮定②より L(S)⊆L(T2) であり，また，L の定義から L(T2)⊆L(Node(a, T1, T2)) であるから，L(S)⊆L(Node(a, T1, T2)) となる．(c) S = Node(a, T1, T2) の場合，L(S) ⊆ L(S) = L(Node(a, T1, T2))．したがって，L(S)⊆L(Node(a, T1, T2)) が言えたので，S∈Sub(Node(a, T1, T2)) ⇒ L(S)⊆L(Node(a, T1, T2))が成り立つ．以上より，任意のΣ-2分木 S, T に対してS∈Sub(T) ⇒ L(S)⊆L(T) が成り立つことが示された．
