問題タブ [proofs]

Oracle データベースで BITOR() を実行する方法を探していたところ、代わりに BITAND() を使用し、BITOR(a,b) を a + b - BITAND(a,b) に置き換えるという提案に出会いました。

私はそれを数回手でテストし、考えられるすべての2進数で機能するように見えることを確認しましたが、なぜこれが正しいのかを簡単に数学的に証明することはできません.
誰かが私を啓発できますか？

n! であることをどのように証明できますか? 任意の定数自然数 p に対して O(n^p) に含まれていませんか? また、(nk)(n choose k) は O(n^p) で、すべての k に対して?

そこで私はカスタムのエラーモナドを作成し、そのモナド則をどのように証明するかを考えていました。誰かが私を助けるために時間を割いてくれるなら、それは大歓迎です。ありがとう！

そして、ここに私のコードがあります:

こんにちは、big-theta を理解するために最善を尽くしました。今では、Big-Oh と Big-Omega の証明の主な概念を理解していますが、演習に近い例を見つけることができませんでした。その証拠：

証人を示すことによって、4n^2 + 4n = Big-Theta(2n^2 + 32n) であることを証明します。

Big-Theta を証明するには、Big-Oh と Big-Omega について証明する必要があることはわかっていますが、どのように始めればよいかわかりません。つまり、右辺の方程式は私を混乱させます。

簡単な質問: Z3 の証明 (例: 4.3.2) では、「仮説」規則によって局所的な仮定が導入され、最終的に「補題」規則によって解放されます。「仮説」と「補題」の規則は常にきれいにネストされていますか?つまり、Z3 証明をネストされた証明ブロックを持つ言語にマッピングできるか、シーケンスを持つことができますか?

? ありがとう。

Matousek と Nesetril による本「Invitation to Discrete Mathematics」でこの質問に出くわしました。私はこれらの種類の問題に慣れていません。私はこの問題に次のように取り組みました。501 の数字の中から選択された 2 つの数字は、除数と被除数で構成されています。500 を超える数値は除数にはなりません。したがって、1 から 500 までの範囲の数値が少なくとも 1 つ必要です。1000 個の数字から 501 個の数字を選択する必要があるという事実を考慮すると、実際にはその範囲内の数字が得られます。

501 番号の選択を次のケースに分けました。

ケース 1 - 501 から 1000 までのすべての数字と 1 から 500 までの任意の数字を選択します。この場合、1 から 500 までのすべての数値が 501 から 1000 の範囲で少なくとも 1 つの被除数を持ち、その範囲全体が選択されるため、ステートメントは簡単に証明できます。ケース 2 - 1 から 500 までのすべての数字と、501 から 1000 までのいずれかの数字を選択します。この場合も、1 から 500 の範囲に互いに除数と被除数として機能する多くのペアがあるため、ステートメントは簡単に証明できます。ケース 3- 1 ～ 500 の範囲の数字と 501 ～ 1000 の範囲の数字を選択します。1 から 500 の範囲の数値について、選択した数値に配当があることを証明するのに苦労しています。

Big O、omega、theta 表記の意味と、関数がそれらの 1 つであるかどうかを証明する方法をよく理解していると思います。問題のように、それらの組み合わせを証明する方法がわかりません。誰かが私にこれを説明してもらえますか?

Θ(n) + O(n^3) = O(n^3)

編集：タイプミス、もともと等しくないと言っていました