1

論理関数とその表現法について学ぶØ 論理関数Ø 真理値表Ø 論理式（和積標準形，積和標準形）
Ø カルノー図Ø 論理回路Ø 二分決定木Ø 二分決定グラフ（BDD）
2

3

説明変数による分類を木状に繰り返すことで事象を説明する。

機械学習にも利用される。

発生形態
卵生

胎生

Ø データ（正例と負例）
から決定木を作成

哺乳類

呼吸方法
肺呼吸

えら呼吸

魚類

体温
恒温

変温

鳥類

爬虫類
4

真理値表から二分決定木は簡単に作成できる。
xyzf00000010010001111000101111011111xx=0x=1yyz0z00z
1

0 1 1z15

二分決定木は簡約化できることがある

xx=0x=1y0z0x=0

簡約化yz0z10 1 1xyyzz
1x=100z
10 116

決定木は木構造を保つ必要がある
Ø 下記の 2 つは左右ともに木ではない

xx=0x=1yyz

0x=0y0x=1yzz
1x1017

3変数 AND 関数，OR 関数の二分決定木を作成し，簡約化せよ
Ø 真理値表は下記
OR関数

AND関数
𝑥𝑦𝑧𝑥∧𝑦∧𝑧𝑥𝑦𝑧𝑥∨𝑦∨𝑧

00000000010001011000

1001111111118AND 関数

xxyz0z0

簡約化

y0z00 0 0yzz
100019OR 関数

xxyz0z1簡約化

y1z1

1 1 1yzz
101111011下記の真理値表を x, y, z の順に値を確認する決定木
xyz

f00010010010101101001101011011111xyyz
1z01z01 0 1z112

簡約化するxxyyz
1z01z0

1 0 1

簡約化

yzzz
11010113

同じ真理値表を z、y、x の順に値を確認する決定木
xyz

f00010010010101101001101011011111zyyx1x11x10 0 0x114簡約化する

zzyyx1x11x10 0 0y

簡約化

xx1100115

同じ関数を表す決定木だが、サイズが異なる

xzyy1xzz0101100116

前述の例のように変数を読む順序によって決定木は変わる
Ø 出来るだけコンパクトな決定木を構成ことは重要
ü メモリの節約
Ø コンパクトな決定木を構成することは簡単ではない
ü 最適な変数順序をどう決める？？

17

下記は論理関数 f を表す真理値表である。
f を表す出来るだけコンパクトな二分決定木を求めよ。
xyz

f0001001101000111100110111100111118y, z, x の順に変数の値を確認する決定木を作成する。
xyz

f00010011010001111001101111001111yzzx1x11x10 0 1x119作成した決定木を簡約化する。

yyzz

簡約化

zx
1x11x10 0 1x11012021

二分決定木とは異なり、「有向非巡回グラフ」で表現

xxyyz00yzz
10 1

二分決定木

y110BDD22

BDD は下記を満たす
Ø 定数節点（0,1）と変数節点から構成される
Ø 有向非巡回グラフである
Ø 定数節点から出る枝はないØ 変数節点からは、0-枝と1-枝のちょうど 2 本の枝が出るØ 変数節点のうち 1 つは、次数が 0 の根節点である
Ø BDD のサイズは、節点の数で定義される

23

多くの実用的な論理関数を「コンパクト」に表現可能
変数順序が定まると表現が「一意」に定まる
BDD に対する効率な演算がある [Bryant 1986]
部分グラフが、もとの論理関数の部分論理関数を表す
近年、さまざまな分野に応用されている

24

部分グラフが、もとの論理関数の部分論理関数を表す

xy𝑥̅ 𝑦𝑧 ∨ 𝑥 𝑦𝑧& ∨𝑦= 𝑥𝑓
̅ 0, 𝑦, 𝑧 ∨ 𝑥𝑓(1, 𝑦, 𝑧)
yxz

0

1

𝑓 0, 𝑦, 𝑧𝑓 1, 𝑦, 𝑧25

変数順序：全順序関係に従って、変数が出現
Orderedxyxyyz0zz

1

Ordered でない

0y1

Ordered はサイズが大きくなる傾向にあるが、扱いやすい

26

BDD に 2 つの簡約化規則を適用
冗長な接点の削除

x

等価な接点の削除

xxx

講義では，ROBDD を扱う（単に BDD と呼ぶ）

27

次のそれぞれの関数を BDD であらわせ(1) 𝑥! ∧ 𝑥" ∧ 𝑥# ∧ 𝑥$
(2) 𝑥! ∨ 𝑥" ∨ 𝑥# ∨ 𝑥$(3) (𝑥! ∨ 𝑥" ) ∧ 𝑥#(4) 𝑥! ⊕ 𝑥" ⊕ 𝑥# ⊕ 𝑥$28

次のそれぞれの関数を BDD であらわせ(1) 𝑥! ∧ 𝑥" ∧ 𝑥# ∧ 𝑥$𝑥(𝑥)𝑥&𝑥'0129

次のそれぞれの関数を BDD であらわせ(2) 𝑥! ∨ 𝑥" ∨ 𝑥# ∨ 𝑥$𝑥(𝑥)𝑥&𝑥'0130次のそれぞれの関数を BDD であらわせ(3) (𝑥! ∨ 𝑥" ) ∧ 𝑥#𝑥(𝑥)𝑥&0131

次のそれぞれの関数を BDD であらわせ(4) 𝑥! ⊕ 𝑥" ⊕ 𝑥# ⊕ 𝑥$𝑥(𝑥)𝑥)𝑥&𝑥&𝑥'𝑥'

0132

33

決定木と同様に変数を読む順序によって BDD の形は変わる．

どんな論理関数も BDD でコンパクトに表現できる？
Ø 任意の変数順序でサイズが小さい → 嬉しい！
Ø どんな変数順序でも、サイズが大きい → 辛い…
Ø ある変数順序で、サイズが小さい。
ü よい変数順序を求めることが重要
ü 最適な変数順序を求める → NP完全 [Tani, et al 1993]34

次の表内の関数は変数順序を変えてもサイズは変わらない関数

BDD のサイズ

論理積（ AND ）O(n)論理和（ OR )O(n)排他的論理和（ EXOR ）

O(n)

多数決関数

O(n2)

対称論理関数O(n2)※ 対称論理関数とは，入力変数内の1の個数のみで出力がきまる関数．
35

どの変数順序でも BDD のサイズが大きくなる例がある
Ø 算術乗算 [Bryant 1991]：Ω(2n/5)
Ø 算術除算 [Horiyama, Yajima 1998]：Ω(2n/8)
Ø ランダムな関数36

例： 𝑥! 𝑦! ∨ 𝑥" 𝑦"
次の 2 つの変数順序を考える．
Ø 𝑥! , 𝑦! , 𝑥" , 𝑦"
Ø 𝑥! , 𝑥" , 𝑦! , 𝑦"37

例： 𝑥! 𝑦! ∨ 𝑥" 𝑦"Ø 𝑥! , 𝑦! , 𝑥" , 𝑦"𝑥(𝑦(𝑥)𝑦)0138

例： 𝑥! 𝑦! ∨ 𝑥" 𝑦"𝑥(Ø 𝑥! , 𝑥" , 𝑦! , 𝑦"𝑥)𝑥)𝑦(𝑦(𝑦)0139

例： 𝑥! 𝑦! ∨ 𝑥" 𝑦"
𝑥! , 𝑦! , 𝑥" , 𝑦"𝑥(𝑥(𝑦(𝑦(𝑦)0𝑥)𝑥)𝑥)𝑥! , 𝑥" , 𝑦! , 𝑦"𝑦(𝑦)10140例： 𝑥! 𝑦! ∨ 𝑥" 𝑦" ∨ ⋯ ∨ 𝑥% 𝑦%
次の 2 つの変数順序を考える．
Ø 𝑥! , 𝑦! , 𝑥" , 𝑦" , … , 𝑥% , 𝑦% → サイズ：O(n)Ø 𝑥! , 𝑥" , … , 𝑥% , 𝑦! , 𝑦" … , 𝑦% → サイズ：O(2n)なぜ，これほどサイズに差がでるのか自分で考えてみること．

41

2 bitの 2 進数 𝑎: 𝑎! 𝑎& と 𝑏: 𝑏! 𝑏& を考える。
𝑎 = 𝑏 の時に 1、それ以外は 0 を出力する
論理関数 𝑓(𝑎! , 𝑎& , 𝑏! , 𝑏& ) を表す BDD のうち、最小サイズの変数順序および最大サイズの変数順序を求めよ。

42

最小サイズ𝑎(𝑏(𝑏(𝑎)𝑏)0𝑏)
143最大サイズ𝑎(𝑎)𝑎)𝑏(𝑏(𝑏(𝑏(𝑏)𝑏)01
44

二分決定木と二分決定グラフ（ BDD ）Ø 変数の順序がサイズに大きく影響する場合があるØ サイズを最小化する変数順序を見つけることは難しい

45