4.1 2分探索 検索・挿入・削除がO(logn)時間で実行される。 4.2 2分探索木 右の子 検索・挿入・削除は木の高さに比例する。 最悪の場合木の高さはn-1になる。 ランダムに要素を挿入すると… データの割り当てられている点の個数をn個として、これを内点と呼び…

1.意味論的同値が同値関係であることを証明せよ 反射的であるのは定義から自明 対称的であるのは定義から自明 推移的であるのは定義から自明 よって意味論的同値は同値関係である。 2.AとBが意味論的同値であってもα等価でない例を挙げよ。 解答例）AとA∨A（…

4.5 意味論的同値 どんな解釈の仕方をしてもAとBは真偽が同じ 定義：すべての付値について 意味論的同値は同値関係である 復習：同値関係 反射的 対称的 ならば 推移的 かつならば 補題4.5.6 変数の名前替えをしたもの同士は意味論的に同値である。 命題4.5.…