問題タブ [proof]

idは type の唯一の関数であり、 typea -> aの fst唯一の関数です(a,b) -> a。これらの単純なケースでは、これは非常に簡単にわかります。しかし、一般的に、これをどのように証明しますか? 同じタイプの可能な関数が複数ある場合はどうなりますか?

あるいは、関数の型が与えられた場合、その型の一意の (これが真である場合) 関数をどのように導出しますか?

編集:型に制約を追加し始めたときに何が起こるかに特に興味があります。

私は何かがNPであることを証明する方法を学んでいます。Thomas Cormenのアルゴリズムの本の紹介で、彼は、ある問題の解決策が与えられれば、何かがNPであると述べています。これは、多項式時間で正しいことを確認できます。

問題が2x+9 = 55であり、正しいx値を見つけるのにどれくらいの時間がかかるかわからないふりをしましょう。しかし、問題を解くアルゴリズムが解23を返しました。それからそれがNPであることを示すために、 23を方程式に戻すだけで、それが多項式の時間を要して55を与えたかどうかを確認できますか？ありがとう。

Omegaを使ってCoqで証明しようとしています。私はそれに多くの時間を費やしましたが、何も思い浮かびませんでした。私は Coq を初めて使用するので、この種の言語には慣れておらず、あまり経験がありません。しかし、私はそれに取り組んでいます。

これが私が証明しなければならないコードです：

この証明を行うには、最初にこの補題を帰納法で証明すると役立つと思いました。

次に、これは、 omega と div2_eq を使用して:

しかし、私はそれ以上進むことができませんでした。

誰も何をすべきか知っていますか？

いくつかの不変条件と組み合わせた誘導を使用して、アルゴリズムの正当性を証明する方法を理解するのに苦労しています。つまり、不変量はどのように検出され、帰納的仮説はいつ使用されますか？特に二分探索の場合はどうでしょうか？私はまだ直感的な反応を見つけることができなかったので、誰かがここでこのトピックに光を当てることができることを望んでいました。

ここで、S-1 は、S の右端の 1 ビットを 0 に変更し、その右側のすべての 0 ビットを 1 に変更したビット列です。

なぜこれが正しいのか理解できたので、大まかな説明を書きました。

すべての反復の後、S の右端の 1 ビットとその右側のすべてのビットが 0 に等しく設定されます。文字列全体が 0 であり、1 の数に等しいカウントでループが中断されます。

この種の答えはどの数学コミュニティにも通用しないことを知っているので、正式な証明を書きたいと思っていましたが、それを行う方法がわかりません。私の証明スキルは特にお粗末なので、関連するテクニックの説明をいただければ幸いです。

私は学校で Coq を学んでいて、家でやるべき課題があります。証明すべきレンマがあります。リストの要素にゼロが含まれている場合、その要素の積は 0 です。コードを開始しましたが、先に進む方法がわからない点で立ち往生しています。Coq からのすべてのコマンドを知っているわけではありません。多くの調査を行いましたが、Proof の最後までたどり着くことができません。ここに私のコードがあります: Import List ZArith が必要です。

それで、リストにゼロが含まれているかどうかをチェックする関数と、その要素の積を計算する別の関数を作成するのは良い考えだと思いました。また、(幸運にも) 2 つの数字があり、そのうちの 1 つが 0 ではなく、その積が 0 である場合、必然的にもう 1 つの数字が 0 であることを証明する補題をオンラインで見つけました (それが役立つと思いました)。 . 帰納法で証明しようと思ったのですが、うまくいきませんでした。何か案は？私は、ここが誰かに私の仕事を依頼する場所ではないことを知っています。

S x = S y目標を からに変更したいx = y。のようなものinversionですが、仮説ではなく目標のためです。

このような戦術は正当に思えます。なぜなら、x = yがあれば、単純に and を使用rewriteしreflexivityて目的を証明できるからです。

現在、私は常に新しいサブゴールを導入するために使用していることに気づきますが、複雑な表現である場合をassert (x = y)記述するのは面倒です。xy

DOM、ThreeJS、そして現在canvasにはすべて、メソッドチェーンを提供するために書かれたライブラリがあります (おそらく jQuery で最もよく知られています)。連鎖はコア C ライブラリでも使用されています。

これらの流暢なインターフェースは、関心のあるオブジェクトの不必要な繰り返しを回避します。比較：

に：

以前の「伝統的な」スタイルは冗長であり、DRYに違反していると主張することができます。

変数の繰り返しを避けるために、一部の言語ではステートメントcxを使用して一連の呼び出しを表現できます。with

JavaScript のwithステートメントはタイプミスがあると危険ですが、Scala のより制限的withなステートメントは安全に使用できます。また、Haxe はそのusingキーワードを介してローカル スコープへの関数のインポートも提供します。残念ながら、Java と C にはそのような近道がないため、従来のコードとチェーンのどちらかを選択する必要があります。

言語の作成者は安全withなステートメントをメソッドチェーンの代替として検討する必要がありますか?それともそれを避ける十分な理由がありますか? そのような機能が望ましいとすれば、それはどのような形をとるべきでしょうか?

メソッドの連鎖に関して私が懸念していることの 1 つは、連鎖内の後続の呼び出しの主題に関するあいまいさが、 の繰り返し使用が明示的であったコードをコンパイルするときに以前に利用可能だった最適化を妨げる可能性があることです。cxたとえば、cxのメソッドへの呼び出しがオーバーラップしない場合、それらは並列化できますが、チェーンされた例では、コンパイラがこれを確認するのが難しい場合があります。

もう 1 つの欠点は、rambo が以下で指摘しているように、連鎖用に設計されたメソッドが他の値を返すことができないことです。これはかなり無駄に思えます。

私は最近、Codeforces で問題を解決しようとしましたが、解決策は正しくありましたが、現在それを証明しようとしています。アルゴリズムは次のようなものです。

最小の割引を最も高価なものに適用し、2 つの連続するより安価なものを無料で使用します。その後、アイテムがなくなるまで続けます。

私はちょっと証明に行き詰まっています。誰かが私に矛盾による正式な証明を与えてくれれば素晴らしいことです.

問題！