補題:32bit符号なし整数変数間の算術和演算をブール関数で表す その3
初期seedから日時を求める無謀な挑戦 - Plus Le Toolのための補題。
以下で使う記号の定義については[id:plusletool:20130427:p2]を参照。
また、以下では独自に定義した関数 を使うが、これについては[id:plusletool:20130612:p1]を参照。
補題:32bit符号なし整数変数間の算術和演算をブール関数で表す - Plus Le Toolの続き。
上記記事の(*20)の直前の「この式から何とかして を消去したい。」の続きから始める。
補題:32bit符号なし整数変数間の算術和演算をブール関数で表す その2
初期seedから日時を求める無謀な挑戦 - Plus Le Toolのための補題。
以下で使う記号の定義については[id:plusletool:20130427:p2]を参照。
また、以下では独自に定義した関数 を使うが、これについては[id:plusletool:20130612:p1]を参照。
補題:32bit符号なし整数変数間の算術和演算をブール関数で表す - Plus Le Toolの続き。
自力では絶対無理だと思ってたけど、あることに気づいたらあっさり解けちゃった……
前回の漸化式の強引な解法(※失敗談)
このブール代数の漸化式を誰か解いてください! - Plus Le Toolの漸化式を数学的な方法で解くのは(少なくとも自力では)無理っぽいので、別の強引な方法で無理矢理解くことにした。
なお、以下で使う記号の定義については[id:plusletool:20130427:p2]を参照。
また、以下では独自に定義した関数 を使うが、これについては[id:plusletool:20130612:p1]を参照。
このブール代数の漸化式を誰か解いてください!
初期seedから日時を求める無謀な挑戦 - Plus Le Toolのために必要で、だけど自力ではどうしても解けそうにない問題があるので、それを解いていただきたい。
なお、以下で使う記号の定義については[id:plusletool:20130427:p2]を参照。
また、以下では独自に定義した関数 を使うが、これについては[id:plusletool:20130612:p1]を参照。
続きを読む【!】この問題は解決しました。【!】
この問題は[id:plusletool:20130713:p1]の方法で解決しました。
皆様にご協力いただき、ありがとうございました。
補題:32bit符号なし整数変数間の算術和演算をブール関数で表す
初期seedから日時を求める無謀な挑戦 - Plus Le Toolのための補題。
使う記号の定義は[id:plusletool:20130427:p2]参照。
補題:32bit符号なし整数変数間の演算をブール関数で表す - Plus Le Toolの続きみたいなもの。
今回の内容はうまく説明できないものが多いから、証明や計算過程はほとんど省略しちゃった(・ω<)テヘペロ
少し考えれば分かると思うので各自考えてね(投げやり
補題:新しい関数“Cr(Ω)”を定義する 定理(*C)の証明
補題:新しい関数“Cr(Ω)”を定義する - Plus Le Toolの定理(*C)の証明。
今まで証明がなかったものをさきさんが証明してくれました。ありがとうございます!
この記事ではさきさんの証明を参考にしつつ、しかし同じこと書いても2番煎じなので別路線で証明してみた。
補題:新しい関数“Cr(Ω)”を定義する
初期seedから日時を求める無謀な挑戦 - Plus Le Toolのための補題。
使う記号の定義は[id:plusletool:20130427:p2]参照。
ここでは関数 を定義する。
なぜ定義するのか、何に使うのか、どんな意味なのか、……etcは次回の記事で分かるはずなので、今回は細かいことは置いておいてとりあえず定義だけしておく。
【追記】
やっぱりここでちゃんと書いておく。
は、ブール代数における 次の基本対称式を表している。
普通の代数においては任意の対称式は基本対称式の和と差と積の組み合わせで一意に表せるが、ブール代数においても同様の性質があって、任意の対称式は基本対称式の排他的論理和と論理積の組み合わせで一意に表せる。
また 対称式でなくても、対象構造を多く含む式なら部分的に基本対称式で表すことでより簡単に記述できることが多い。
そこで基本対称式を で表し、これを使って式を簡略化しようというのがこの関数の目的である。ちなみに基本対称式は慣例的には でなく (文献によっては )を使って のように表すらしい。
この追記の時点ではじめて知った……(手遅れ)
ああそうそう、今回の記事にはちゃんと証明できなかった定理が多数あるので気に入らない人は読まない方が精神衛生上いいと思うの。
続きを読む