ホーン式とXOR-MDNF式との関係について

摘要

単調DNF式に基づく排他的論理和展開式（(direct +)MDNF式）と呼ばれるブール式のクラスとホーンDNF式のクラスとの関係について調べる．((direct +)MDNF式とは，単調DNF式f{sub}1＞…＞f{sub}dを用いてf＝f{sub}1 ((direct +)…((direct +) f{sub}dのように表されるブール式である．ただし，同じ項は2回以上現れない．ホーンDNF式とは，各項に否定的なリテラルを高々1つしか含まないDNF式である．本稿では，fとその否定fがどちらもホーンDNF式で表せる関数（ダブルホーン関数）と，各DNF式f{sub}iがちょうど1つの項からなる((direct +)MDNF式のクラスが一致することを示す．また，与えられたホーンDNF式を((direct +)MDNF式に変換する逐次多項式時間アルゴリズムを与える．