問題タブ [proof-of-correctness]

これは宿題ですが、正式な証明を書くことでこのビジネス全体を理解することはできません。誰かがこれを解読して、この fnc の事後条件の正式な証明を書くことができますか?

文字列 REPLACE_BY (文字列 s、文字 c、文字 d)

事後条件 返される値は、出現するすべての c を d で置き換えることによって s から形成された文字列です (それ以外の場合は s を変更しません)。

私はラムダ計算が初めてで、次のことを証明するのに苦労しています。

SKK と II はベータ版に相当します。

どこ

S = ラムダ xyz.xz(yz) K = ラムダ xy.x I = ラムダ xx

SKKを開いてベータ削減しようとしましたが、どこにも行きませんでした。S、Kを拡張せずにSKKをさらに削減できるとは思わないでください.

誰かがこの質問に答えるのを手伝ってくれるかどうか疑問に思っていました. これは以前の試験用紙からのものであり、今年の試験の準備ができている答えを知っていればできることです。

この質問は非常に単純に思えて、完全に道に迷ってしまいます。正確には何を求めているのでしょうか?

整数変数を含むコードの次のセクションを検討してください。

適切な出力条件を記述し、コード片の正確性を検証することにより、実行後に m が i と j の最小値に等しいことを証明します。

私は投稿条件を次のように持っています: {m = i ∧ i < j ∨ m = j ∧ j < i}

これは正しいです？そして、これをどのように確認しますか？

リスト x,y をパラメーターとして取り、x と y の結合で z 番目に小さい要素を返す次のアルゴリズム min を考えてみましょう。前提条件: X と Y は昇順で並べ替えられた int のリストであり、互いに素です。

疑似コードであるため、インデックス付けは 0 ではなく 1 で始まることに注意してください。

z が 2 ずつ減少し続け、最終的に基本ケースの 1 つに到達するため、終了することを証明できますが、部分的な正確性を証明することはできません。

こんにちは、これらのコンビネータ SK = KI の証明に問題があります

括弧 [] で囲まれた手順は、私が行っている手順を示しているだけです。たとえば、[λxy.x / x] in λyz.xz(yz) は、式 λyz.xz(yz) のすべての x を (λxy.x) に置き換えようとしていることを意味します。

私がこれまでに試したことはSKを減らすことであり、これを得ました：

そしてKIを減らすと、これが得られました：

2 つの答えは、私 (λyz.zz) と λy に等しくないように見えますが。λx.x 誰か私が何を間違えたのか説明してくれませんか? ありがとうございました。

プログラムにバグがあることを証明できるという事実について考えていました。テストして、多かれ少なかれバグ耐性があるかどうかを評価できます。

しかし、プログラムにバグがないことを (理論的にも) 証明する方法はありますか?

「Hello World」などの単純なプログラムの場合は、できるはずです。しかし、より大きなプログラムはどうでしょうか?

帰納法による証明のこの変種が正しいかどうか疑問に思っています

帰納法による標準的な証明では、方程式/アルゴリズムが n に対して機能し、それが n+1 に対して機能することを証明できる場合、n 以上のすべての整数に対して機能すると仮定できると述べています。

さて、2 つの基本ケース (例: 2 と 3) があり、それが n+2 で機能することを証明する必要がある場合、2 より大きいすべての整数で機能すると言えますか?

n+2 に対して正しいことを証明できると仮定すると、

など、2より大きいすべての整数をカバーします

助けてくれてありがとう^^

(また、+2 バージョンが正しい場合、つまり、m 連続する基本ケースと、それが n+m で機能するという証明がある場合、n より大きいすべての整数で機能することを意味します)

ツリーの直径を見つけるには、ツリーから任意のノードを取得し、BFS を実行してそのノードから最も離れたノードを見つけ、そのノードで BFS を実行します。2 番目の BFS からの最大距離が直径になります。

私はこれを証明する方法がわかりませんか？ノード数の誘導を使用してみましたが、あまりにも多くの場合があります。

どんなアイデアでも大歓迎です...