3 not problem
私が3notの話を最初に聞いたのは, 1960年代の始め頃, サバティカルで東大に滞在していたイリノイ大学のDavid Muller先生からだ. 研究室のお茶の時間に「アメリカの計算機科学科でよく話題になる問題」の1つとして紹介された. この話が記述されているのはあまり見た記憶がないが MITのHakmemには出ている. item 19の2-NOTs problemがそれである. x,y,zの3入力, x',y',z'の3出力を持つブラックボックスがある. 入出力の関係は x'=not x y'=not y z'=not z である. ブラックボックスには, andとorは好きなだけ使われているが, notは2つしかないことが分かっている. 内部はどうなっているか. Muller先生からこの話を聞いたわれわれは, その日は他の仕事がまったく手につかなかった. 解けてみるとなるほどと目から鱗
論理とはなにか？ (4:完) -- 論理から圏へ - 檜山正幸のキマイラ飼育記 (はてなBlog)
ワーイ、完結だ。シリーズがちゃんと完結するなんて、滅多にないよ、僕は。 前回の最後（一部省略・短縮）： 論理の定義として閉包作用素を使う定義があります。これについて説明するかも知れません。ストラスバーガーの意図としては、論理をプレ順序と考えるのは中間ステップであり、論理を圏として捉えるのが目的なので、「論理は圏だよ」という結論にたどり着かないと心残りかも知れません。 閉包作用素による論理の定義は、単品メニューとして出せる話題なので今回は省略して、「論理は圏だよ」という話をして、ストラスバーガー論文の紹介を締めくくりたいと思います。 内容： 今までの復習 状況証拠を確認 プレ順序集合から圏へ 太った圏も認めよう 圏としての論理 「証明とは何か？」とは何か？ 第1回と目次 今までの復習 まず、次の大きな前提を置きました。 どんな論理（論理的システム）でも、命題（正確には論理文）の集合Sを確定で
論理とはなにか？ (3) - 檜山正幸のキマイラ飼育記 (はてなBlog)
ストラスバーガーの論文を紹介、その第3回。 前回の最後で： あと1回は書く予定。証明可能性‘|-’ではなくて、定理集合や閉包演算子により論理的システムを定義する方法もあるので、それらの流儀でもやっぱりプレ順序集合が作れることは確認したいので。 と書いたので、そこらへんの話題です。 内容： 前置き 定理集合またはセオリー セオリーからプレ順序 演繹定理 まだ続くのかな 第1回と目次 前置き ストラスバーガーの原論文は解説的なものですが、一般向けの記事ではないので、少ない予備知識で紹介しようとすると文章の量が増えますね。もとの一文が一段落に、もとの一段落が一記事に、という感じ。でも、僕は翻訳ではなくて噛み砕いた説明を提供したいので、いたしかたないでしょう。 さて、以下、記号「⇒」、「⇔」は“地の文”で内容的に使います。つまり、「…ならば…」、「…と…は同値」という日本語表現の略記に過ぎません。
古典論理は可換環論なんだよ - 檜山正幸のキマイラ飼育記 (はてなBlog)
酒井さんのコメントに対して、 {true, false}と{0, 1}の対応でも、ほとんどの場合trueを1にしますが、trueを0にしたほうが計算がスムーズな状況もあります。 なんて応えたわけですが、これでフト思い出したことがあります。 以前、「イデアルと論理」つうネタでいくつかのエントリーを書いたことがあるのですが（「はてなブックマーク - ideal+logicに関するm-hiyama-taxonのブックマーク」参照）、中途半端にうっちゃってあるなー、ダハハハ。 未完（永久にか? ^^;）の「イデアルと論理」シリーズの最初のほうでは、普通の（つまり、可換環の）イデアルを紹介してますが、最終的には論理の（つまり、ブール代数の）イデアルに結びつけようと思っていたわけです。で、「どうやって結びつけるのか」という筋書きは今日説明しようかな、っと。（とはいえ、基本的に自分の備忘用ですけど。）
論理とはなにか？ (2) - 檜山正幸のキマイラ飼育記 (はてなBlog)
「論理とはなにか？」の続き。論理それ自体の知識をできるだけ仮定しないで、論理の一般論のエッセンスを解説しましょう（そう試みてはみるよ）。 内容： 前置き フツーっぽい命題証明系 「仮定なし」と「複数の仮定」への対処 一次方程式の証明系 一般的な手法としての有限ベキ構成 今回のまとめと次の話題 第1回と目次 前置き ストラスバーガーは、「論理とはプレ順序集合だ」と言っているわけですが、この主張が、既存の様々な論理的システムにうまく適用できるかどうかを調べたいと思います。とはいえ、既存の様々な論理システムに関する博物学的な知識が要求されるのではたまらないので、命題論理（に相当する日常論理）、中学レベルの連立方程式を素材にします。 記号列、記号的図形の集合を外から眺める、という発想は必要かも知れません。このへんのことは、「論理を身に付けるには」の前半を参照してください。 フツーっぽい命題証明系
論理とはなにか？ - 檜山正幸のキマイラ飼育記 (はてなBlog)
たまたま、"What is a logic, and what is a proof?" (April 8, 2005) by Lutz Strassburgerという論文を見つけて、読んでみました。比較的短い（印刷して12P）解説的な論文です。表題のとおり、 論理とはなにか？ 証明とはなにか？ という2つのテーマを扱ってます。後半1/3程をしめる「証明とはなにか？」が僕はよくわからんかったのだけど、前半は、「論理（a logic）は圏だよ」という主張をとても上手に説明しています。で、まー、この前半部分を紹介しようかと。 ただし、以前に書いたエントリーを参照しながら私見を交える（私見のほうが多いかな）ので、上記論文の忠実な紹介にはなってません。気になる方は原文を読んでくださいね。 第1回（このエントリー） 第2回 第3回 第4回(完) 今回の内容： プレ順序集合 論理とはプレ順序集合なり
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
