単調なブール関数のCNFおよびDNF格子のメビウス値

$ phi $が$ langle kのすべての変数に依存するように、変数$ langle k rangle:=
{0、 ldots、k } $の単調なブール関数 rangle $(すなわち、すべての変数$ x in langle k
rangle $に対して、$ nu: langle k rangle setminus {x } から
{ top、 bot $ phi( nu cup x mapsto top) neq phi( nu
cup x mapsto bot)$などの

それぞれの節が含まれる変数の集合として見える$ phi $を表す(一意の)最小化されたCNFを$ F _ { text
{cnf}} = C_0 land ldots land C_n $とする。 $ mathbf {s}
subseteq langle n rangle $に対しては、$ d _ { mathbf {s}}を定義します:
bigcup limits_ {i in mathbf {s}} C_i $。 $ mathbf {s} neq
mathbf {s ‘} $には$ d_ mathbf {s} = d_ mathbf {s’}
$があることに注意してください。さらに、$ d_ emptyset = emptyset $に注目してください。

基底集合$ L_ text {cnf} = {d_ }を持つ格子として、 CNF lattice
$(L _ { text {cnf}}、 leq) $ leq $が逆になっている場合は、$ d_ mathbf {s}
mid mathbf {s} subseteq lang n rangle } $ iff $ d_
mathbf {s ‘} subseteq d_ mathbf {s} $)。その格子の一番上の要素$ hat {1}
$は$ emptyset $であり、その下の要素$ hat {0} $は$ langle k rangle
$です。

同様に、我々は$ F _ { text {cnf}} $の代わりに$ phi $の DNF
lattice
$(L _ { text {dnf}}、 leq) F_ { text {dnf}} = D_0
lor ldots lor D_m $は、 phi $を表す一意に最小化されたDNFです。頂点要素として$
emptyset $、底要素として$ langle k rangle $があることに注意してください。

$ mu text {cnf}:$ phiのCNF格子のメビウス関数であるL { text {cnf}}
times mathbb {Z} $(resp。、$ mu_ text {dnf}
$、そのDNF格子のメビウス関数)。その関数の定義については、たとえば列挙型結合子の3.7を参照してください。

Example: Let $phi$ be the monotone Boolean
function on variables $langle 4 rangle$ defined by the CNF
$F_text{cnf} = (3 lor 4) land (0 lor 4) land (0 lor 1 lor
2)$. You can check that its corresponding DNF is $F_text{dnf} = (0
land 3) lor (0 land 4) lor (2 land 4) lor (1 land 4)$. The
Hasse diagrams of the CNF and DNF lattices of $phi$, together with
the values $mu(e,hat{1})$ for each element $e$ of the lattices,
are drawn below (where, e.g., “034: 1” means that it is element
$e={0,3,4}$ and we have $mu(e,hat{1})=1$):

CNF lattice: CNF lattice DNF
lattice: DNF lattice

QUESTION: Is it always the case that
$mu_text{cnf}(hat{0},hat{1})=0$ if and only if
$mu_text{dnf}(hat{0},hat{1})=0$? I know a proof of this
conditionally to FP $neq$ #P (which is beyond our scope here), but
I would like to prove it unconditionally.

What I know:

  • 最初に、クロスカット定理
  • 第2に、格子上のメビウス(Möbius)逆変換式を使って、満足値$$ phi $の数を数えれば、$ # phi $が$
    mu_ hat {0}、 hat {1})$と$ mu_ text {dnf}( hat {0}、 hat
    {1})$は両方とも偶数なので、同じパリティ;
  • 第3に、すべての変数$ langle k rangle $、最大$ k = 5
    $に依存するすべての単調関数を生成するための少しのコードを作成しました。 。私は実際には常に$ | mu_ text
    {cnf}( hat {0}、 hat {1})を持っていたことを知りました。 = | mu_ text {dnf}(
    hat {0}、 hat {1})| $です。さらに、私は、記号が同じである場合と、反対の場合があります。
ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です