サーキットというグラフの計算量 その２

前回とは一転、またまた長く間が相手しまい申し訳ありません。どうしてこうなのでしょうか。亀の呪いでもかかっているかのようです。扱っているいる問題がむずかしすぎですよね、まったく。しかし、千里の道も一歩から。少しずつがんばっていきたいと思います。

さて前回の復習ですが、パリティを定義して

　Parity(x1,x2,…,xn)=(x1+x2+…+xn) mod 2

   (※a mod bはaをbで割ったときの剰余）

としました。前回言及しなかったのですが、このとき、パリティはブール関数として表されることから、このパリティの否定も定義でき、次のようにすることにします

　￢Parity(x1,x2,…,xn)=1-Parity(x1,x2,…,xn)

また、x1,x2,…,xnのk番目のthreshold関数を（このブログでは)Th(k,n)(x1,x2,…,xn)と表すことにすると、

　Th(k,n)(x1,x2,…,xn)=1　　iff 　x1+x2+…+xn ≧k

    (※iffは if and only if の省略形で同値を意味する）

と定義し、最後にブール関数のモノトーン(monotone)もしくは日本語でいう単調をで定義して、ブール関数fにモノトーンであるとは、すなわち、

　　x≦y　　ならば　f(x)≦f(y)

　　　

　ただし、x=(x1,x2,…,xn),y=(y1,y2,…,yn)で、

　　　　　　x≦yはx1≦y1∧x2≦y2∧…∧xn≦yn

　　　　　　を意味します

　

が成り立つこととしました。

今回は、単調なブール関数f(x1,x2,…,xn)のmintermとmaxtermという言葉を定義したあと、min(f),Max(f)という集合の表記について説明します。以下、繰り返しになりますが、単調なブール関数f(x1,x2,…,xn)において成り立つと考えてください。

まず、mintermから。あるブール代数の集合｛xi1,xi2,…,xik｝(※変数の最後の添え字がkであることに注意。すなわち1≦i≦ｎで1≦k≦n）が単調なブール関数fのmintermという場合、xi1=1,xi2=1,…,xik=1のときのみf=1がなりたつこと。言い方をもっと数学らしくすると、xi1=1,xi2=1,…,xik=1のときのみf=1であり、これらの変数のどんな真部分集合を取ってきてその値をすべて1にしてもf=1とはならない、と定義します。

つぎに、maxterm。あるブール代数の集合｛xi1,xi2,…,xik｝が単調なブール関数fのmaxtermという場合、xi1=0,xi2=,0…,xik=0のときのみf=0であり、これらの変数のどんな真部分集合を取ってきてその値をすべて0にしてもf=0とはならない、と定義します。

こうしておいて、関数fのすべてのmintermの集合をmin(f)、すべてのmaxtermの集合をMax(f)とします。

こうしたときに、次のことが成り立ちます。すなわち、p∈min(f),q∈Max(f)のとき

　　

　　　p∩q≠Φ

テキストでは自明のごとく書いてありますが、これは一般に、mintermが成立するとは、ブール関数fの一部がxi1∧xi2∧…∧xik=1を含むことと同等と考えることが可能で、maxtermが成立するとは、ブール関数fが一部がxi1∨xi2∨…∨xik=0を含むことと同等だと考えると一見成立しないように思われますが、mintemがxi1のみmaxtemもxi1のみと言う場合も当然あるために上の式は成立するということだと思われます。

さて、最後に単調な論理式について少しふれておこうと思います。論理式Fに否定のリラテルすなわち、￢xのような形のブール変数を含まないような論理式を単調な論理式といいます。単調な論理式Fから表せるブール関数fは単調になり、また逆に単調なブール関数は単調な論理式によって表すことができます。

とりあえず、今回はここまでにしておきます。かなりヤヤコシイのですが、あとは、どうか誰か読んでくださいますように、お祈りするのみです。