FC2ブログ
--.--
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

12.18
Wed
冬休みーがはじまりました

やっほーい!1月に3日くらい学校行く日あるんですけどね...


さて、命題論理のコンパクト性定理を証明してみたいと思います.

論理学をつくるを参考に読んでいたのですが、若干理解が微妙なところがあったので

めもめもしてみます。

まず命題論理のコンパクト性定理とは、

論理式の集合 が有限充足可能 が充足可能

であることをいいます

ここで有限充足可能とは の任意の有限部分集合が充足可能であることとします。

そして、つくる本ではを部分集合とする都合の良い集合を作り

そこからを充足する真理値割り当て関数が簡単に作れるという事を示す方針でした

ここまではおkなのです。


以下にもう少し噛み砕いて私なりにわかりやすくしたものを書いてみます

まず命題論理式の定義と意味論を簡単に定義します

論理式の定義

1. 命題変数 は論理式である
2. を任意の論理式とするときは論理式である

他の結合子を導入してもいいのですが証明が長くなるのでやめます;)

論理式の解釈の定義

を命題変数の集合として写像 を解釈とする.

を論理式の集合として、命題の真偽はある解釈の元での真偽関数により定まる

1. のとき  命題変数の真偽は解釈で与えられるということ

2. のときそれ以外のとき

3. のとき それ以外のとき


証明は以下のような性質をもつ都合のいい集合が作れたというところからやります

のもつ性質

1.

2. 任意の論理式についてであるかの何れか

3. は有限充足可能

で、ある解釈関数を定義します

定義1
任意の命題変数について

つまりに属す命題変数のみを真とするような解釈関数です。これを考えると以下が証明できます

つまりそのような解釈のもとでに属す論理式を充足します.そのようながあるということです


では証明します.


1. が命題変数のとき

   を仮定します

   は命題変数であるから論理式の解釈の定義より仮定はといえる.

   よって定義1より


   を仮定します

   定義1によりこれはです

   さらに論理式の解釈の定義より、は命題変数であるからです


2. が複合論理式である場合

   が論理結合子を個もつような式であるとして

   個未満の論理結合子をもつような論理式については

   であると仮定します(帰納法の仮定です)

   ①. という形であった場合
     
    つまりを仮定します。

    であるための必要十分条件は

    帰納法の仮定の逆の対偶を考えると(双条件なのでおk)

    よってとなり、の持つ性質2よりつまり

    
    つまりを仮定します

    の持つ性質2よりであるから帰納法の仮定より
    
    論理式の解釈の定義よりよって


   ②.という形であった場合

    を仮定します.論理式の解釈の定義より

    帰納法の仮定より、

    ここでとするとの性質よりとなるが

    部分集合は充足不能であるから、が有限充足可能であることに反する

    よって
    
    
    を仮定します

    まずこの仮定のもとでであることをいいます

    としてみるととなるが部分集合は充足不能であるため

    の性質に反する。よってとなる。またとなることも全く同様

    であるので帰納法の仮定により

    よって論理式の解釈の定義により



よってであるのでを充足するような真偽関数です
スポンサーサイト

comment 0 trackback 0
トラックバックURL
http://telracsmoratori.blog.fc2.com/tb.php/180-fcc7239b
トラックバック
コメント
管理者にだけ表示を許可する
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。