| 講演名 | 2005-03-18 単一2負項を加えたホーン関数 川村 直輝, 岩田 茂樹, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ホーン関数は高々1個の負リテラルを含む主項を持つブール関数である. ホーン関数に2個の負リテラルを含む項を1個(論理和で)加えたブール関数のクラスを考える. このクラスに属す関数は3個の負リテラルを持つ主項を含まないことを示す. また, ホーン関数に2個の負リテラルを含む項を2個加えたブール関数は3個の負リテラルを含む主項を数多く持つ場合があることを示す. 積和標準形で与えられたこのクラスに属す関数のトートロジー問題がP完全であることを示す. |
| 抄録(英) | A Horn function is a Boolean function where each of its prime implicants contains at most one negative literal. A class of Boolean functions is considered where a single term containing two negative literals is added (logically or-ed) to a Horn function. We show that the function does not contain any prime implicant having three negative literals. We also show that if two terms having two negative literals are added to a Horn function then it may have many prime implicants containing three negative literals. We show that the tautology problem for the considered class of Boolean functions given in disjunctive normal form is P-complete. |
| キーワード(和) | ブール関数 / ホーン関数 / 主項 / P完全 |
| キーワード(英) | Boolean functions / Horn functions / prime implicants / P-complete |
| 資料番号 | COMP2004-77 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2005/3/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 単一2負項を加えたホーン関数 |
| サブタイトル（和） | |
| タイトル（英） | Horn Functions with Single Two-negated Term |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ブール関数 / Boolean functions |
| キーワード(2)（和/英） | ホーン関数 / Horn functions |
| キーワード(3)（和/英） | 主項 / prime implicants |
| キーワード(4)（和/英） | P完全 / P-complete |
| 第 1 著者 氏名（和/英） | 川村 直輝 / Naoki KAWAMURA |
| 第 1 著者 所属（和/英） | 電気通信大学大学院電気通信学研究科情報工学専攻 Department of Comuputer Science, The University of Electro-Communications |
| 第 2 著者 氏名（和/英） | 岩田 茂樹 / Shigeki IWATA |
| 第 2 著者 所属（和/英） | 電気通信大学大学院電気通信学研究科情報工学専攻 Department of Comuputer Science, The University of Electro-Communications |
| 発表年月日 | 2005-03-18 |
| 資料番号 | COMP2004-77 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 743 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |