II-206B− 三値論理による素項展開の考察 殿 政

II-206B−
三 値論 理 に よ る素項 展 開 の考 察
L
司
殿
政
男
ACon日iderationofPrimeImplicantExpansionbyM6ansof
B・ternaryLlogic
MasaoMUKAIDONO
Abstract
One・fth・m・
」・・p・ ・blem・
f・・皿 ・1…Th・
…al・Rp・
・ac旧
・{・wit・hingth…yi・h・wt・
・・th・
・imp晦
・impl輌ficati・ ・p・
・w鼓 ・hingfun・ti・n…
・blemi…1ve・
.1・gical
・bt・i・i・gth・p・im・implica・t
expansion・sumofallprimeimplicants-.
Inthep∫esCntpaper
,NYeconsiderthe.primeimplicantexpansionofswitchingfUncti砧through
出etheoryofB・ternarylogic.EspeciallybymeansofthetheoryofB・ternary'logic
m・th・dk・
・w…N・1…'・alg・
,wedescribe
・ithmgi・i・gth・p加eimplicant・xp・n・i…f・nygivenl・wit・h▲
・g
functions.
{.ま
らは,clause・columetable.を
え が き
用 い る こ と に よ り,」.R.
Slagleら の 手 順 を 改 良 して い る 。:一:
一 方 ,従 来 の 二 値 論 理 の 真 理 値0,1に,あ
論 理 式(switchingfor㎡ulas,Booleanexpressions),
また は 論 理 関 数(switching・fuhctions,Booleanfunctions・truthfunctions)の
簡 単 化 と い う問 題 は
チ ン グ理 論 の 主 題 で あ り .こ
い まい で
あ る こ と を 意 味 す る 真 理 値 乃 を 加 え る と、 あ る程 度 の あ
,ス
イ ッ
れ ま で 数 多 くの 研 究 が 行 な
い まい さ を 取 り扱 か う こ との で き る 三 値 論 理 −B−
三値
論 理 一一
が 得 られ る こ とが 既 に 知 られ て い る1b)』B⊥ 三 値
わ れ て い る1)一'14)。
そ こ で 用 い られ て る 手 法 の ほ と ん ど
論 理 は,従
は ・ まず 与 え ら れ た 論 理 式 の 葉 裏(主
体 系 で,二 値 論 理 を 含 む よ うに 拡 張 され て い る の で,よ
cant)展
項
開 を求め るのが 第一 ス テ ップで
,primeimpli,次
に,素
り高 い立 場 か ら二 値 論 理 を 眺 め る こ とが で き る と い う特
項 の
中 か ら無 冗 長 な 組 み 合 せ を 見 い 出 す も の で あ る 。 素 顔 展
徴 を 有 して い る。 ・
開 を 求 め る 古 くか ら 知 ら れ て い る 代 表 的 な 手 法 に ,
Harvardi) ,M.Karnaugh2)お
る 図 を 用 い る も の,お
Quinet)お
よ びE.W,Veitch3)に
よ び 計 算 機 に 適
よ びE.∫.McCluskey5)の
これ らの 手 法 は
準 形(特
N・1…
に つ い て 考 察 し,素 項 展 開 の い くつ か の 性 質 に つ い て述
し た 。W.V.
小 項 表 示)に
べ る。 特 に,R.」.Nelsonの
よ びT.H
.Mott7)に
,Nelsoh8),9)の
2.諸
よ るconsensusを
変 数Xi,ま
,W.V.
とる手
三 値論理 の理
∴;
。 こ の 手 法 は 、 最 近,J.R.Slagleso)ら
早 い 手 順 に 改 良 さ れ て い ・る
.更
義
た は そ の 否 定 ∼xi.を 文 字 と い い,riと
∼
が 同 時 に 存 在 しな い よ うな い くつ か の 文 字 のAND(.・)
の 手法 は
の であ る
定
泊 と は 互 に 補 元 で あ る と い う』 あ る文 字 と そ の 補 元 と
手 法 な ど が あ る 。R.J.
.乗 法 標 準 形(噸
形 式,、 。nj。。。ti。
。
f・rm)を カ‖法 標 準 形(積
和形 式
,di,j。n,、i。ef。,m)O。,
また は逆 に 加 法 標 準 形 を 乗 法 標 準 形 に
用
.:簡 単 な 省 略 算 を
い な が ら分 配 法 則 に よ 喉 聞 し て 瀬
展 搬
求 め る も
頓知
手 法 を,'B−
論 を 用 い て 導 い て い る。'・
。
展 開す る必要 が
あ る。 主 加 法 標 準 形 に 展 聞 し な い で よ い 方 法 に は
法 ・ お よ びR.」
三 値論理 を用 い て論理 式の 素項展開
、 与 え られ た 論 理 式 を い っ た ん主 加 法 標
殊 加 法 標 準 形 .最
Quine6)お
本 論 文 で は,B−
ょ
もの な どが あ る
来 の 二 値 論 理 を 最 も 自然 に 拡 張 した 三 値 論 理
に よ り
を積 項.'OR(V)を
和 項 と呼 ぶ ご 加 法 標 準 形 と は,、い く
つ か の 積 項 のORで
構 成 され る論 理 式 を い い ∴ 乗 法 標 準
形 とは.い
くつ か の和 項 のANDで
v、う。
・
・'・"・:.'14、
〔定 義1〕
・積(和)項
(97)
『
、'
α た 存 在 す る す べ て の文 字 が,t積
(和)項 βに'も存 在 す る と き,aFβ1と
に,s.R.D、S・)
構 成 され る論 理 式 を
記 す 。 この と きひ,
49.10.20受
理
明 治 大学 工 学 部 研 究 報 告No.29
α は β を 含 む,ま
た は,β
上 の 関 係 ← は,明
積(和)項
は α に 含 まれ る と い う。
存 在 す る す べ て のY2を0ま
る γ2η〒{0,1}nの
らカ、た 半 順 序 関 係 を な す 。 α,β を.
と す る と 、 αト β の と き,β
F(α*)で,変
は α ・β'(α〉 β')と
置 き 換 え て 得 られ
元 か ら な る 集 合 をa*で
〔定 義5〕
(吸 収 法 興り)α 〉 α ●β'=α
(α ・(α∨ β')=α)
]・
元a-(の,_,ai,_,an)と
α に 文 字Xiが
・$
吸 収 法 則 が 適 用 さ れ て い る 加(乗)法
積 項 α と は,次 の
存 在 す る=ai'":1
α に 文 字 ∼ 酷 が 存 在 す る'一
・r-一"ai=O
標準
、
な わ ち,他
の 積(和)項
在 しな い よ な 加(乗)法
に 含 まれ る積(和)項
αに 変 数 右 が 存 在 しな い=α
が存
標 準 形 を 既 約 な 加(乗)法
〔定義6〕
標準 形
す べ て の 論 理 式 φ は,あ
る 二 値 論 理 関 数(本
数 と す る)f:V2n-V2(た
を 表 現 し て い る 。 あ る積(和)項
論 理 関 数 の1'L:setを
上 の対 応 は,明
だ し、V2-{0,1D
α*={a∈
碇 義・)とは四 ら旅 呼 で肪 ・
γ・
π げ(a)=1}。
合K(f)一
の集
〔定 義.4〕K(f)内
義1)の
に 知 ら れ て い る!s)B'一 三 値 論 理 関 数 のV・ くつ か の性
で の,積(和)項
項 か ら な る 加(乗)法
質 に つ い て 述 べ て お こ う。
〔定 理1〕
の 集 合 と い う。
極 大 元 をfの
にお け る半 順 序 関 係
す べ ての 事
ほ)α
標 準 形 を ∫ の 加(乗)法
形 式 の索 項
{2}aE-b-一,F(a)←
亨
排}自
省)。1
三 値 論 理 関 数 な らぽ,
一'F(a*)ニ{O,1};,'
{2}F(α)-1-→F(α*)一{1},
(3}F(α)-0-→F(a*)・={0}(証
∼X=1-X
〔系2〕
と し て 三 値(0,Y2,1)ま
で 拡 張 定 義 し た 論 理 体 系 で,二
値 論 理 で 成 立 す る ほ と ん ど の 等 式 がB−
明 略)。
論 理 式 φ を 加(乗)法
す るB−
三 値 論 理 関 数 をFと
標 準 形 と す る 。 φ 力壌 現
す る と,
F(a)-0津F(α*)=・{o},
三 値 論 理 で も成
立 す る15)が,t-'...'
(F(α)=1≡=二F(α*)={1})(証
(相 補 法 則)∼X・X-o,ノ)XVXr1
〔定 義7〕B−
が 成 立 しな い の が 特 徴 的 で あ る 。 ま た,B−
値(O,弱,1)を
三値論理関
と る 変 数Xl,_、Xnと,上
述 べ た 三 値 ま で 拡 張 され た 論 理 演 算 ・,V,∼
で
意 の 論 理 式 は,二
も,ま
値 論理 関 数 と して も 見 る こ と が で き
る 。Br・ 三 値 論 理 で は,分
意 のBr三
配 法 則,べ
〔3}F(α)ニ ー;〇二==ご'F(α*)={0},.
を 満 す と き,FをP形
値論理関数 とし て
真 理 値O,1を
釈 す れ ば,定
き等 法 則 が 成 立 す
論 理 関 数 と い う。
確 定 し た 情 報,%を
理1は,入
あ い ま い な 情 報 と解
力 の 情 報 が 確 定 す れ ばB−
論 理 関 数 の 値 も確 定 し,入
三値
力 の あ い ま い さ が 減 ら な けホ
ぽ 関 数 の 値 の あ い ま い さ も 減 ら な い こ と を 意 味 してい
値 論 理 関 数 を加 法形 式 お よび 乗 法
形 式 に 展 開 す る こ と が で き る が,`相
三 値 論 理 関 数Fが,
{2}F(α)二1;===三F(a*)r-'〔1},'
との有 限
い う 。 よ っ て,任
明 略)。
U)∬(a)=Y2F=ltF(α*)一{O,1},
回 の 結 合 で 構 成 さ れ る論 理 式 が 表 現 す る 三 値 論 理 関 数 を
か1う1あ
γ2,
」,1『
、(b)(証
{1}F(a)=Y2←
X・y='niin'(X,y),寸X>y=max(X,y),,
る か ら,任
三 値 論 理 関 数 で あ るた
∈V2n-・F(α)∈
〔系1〕FがB−
・
値 論 理 で定 義 され て い る論 理 演
算AND,OR,NOT(∼)を.
た,B-:-r三
三 値 論 理 関 数FがB−
め の必 要 十 分 条 件は
素 項 と い い,fの
展 開 と い う。
'
iB− 三 値 論 理 と は,二
数 と は,三
三 値 論 理 に よ る素 項 展 開 の考 察,
'既
α*})
を,∫ が 生 成 す る積(和)項
F(定
3.B−
関 して,積(和)項
〔
α1ご*⊂ プL1(1)}
(K(∫)二{α1∫-1(1)⊂
成 立 して い る。 また,積
項 の 間 の 半 順 序 関 係 ← と γ♂ の 元 の 間 の半 順序 関 係 ←
α*で 表 わ す こ と に す る 。 す な わ
あ る 二 値 論 理 関 数fに
らか に 一 対 一 対 応 で,積 項 αに対 応す
る元 を α とす れ ば,α*=α*が
αが 表 現 して い る二 値
が 表 現 す る二 値 論 理 関 数 を ア とす る と き,
〔定 義3〕
元 α,bに 対 応 す るそ れ ぞ れ の 積 項 をa,β と
す る。
論文 では
ち,α
ε=乃
す る と き,α1一β な る と き,お よび そ の 時 に 限 りaFbと
と 呼 ぶ 。・
〔}ば'≡ 卜'、 ・
す べ てn変
と
と き 互 に 対 応 し て い う。
が成 立 して βは 省 略 で き る。
形,す
表 わ し,
数 が α*の 元 の す べ て を と っ た と きFが
る値 の 集 合 を表 わ す もの とす る。
表 わ せ る か ら,
〔
定 義2〕
た は1で
る 。 系1は,あ
補 法 則 が 成 立 しな い
る 変 数 に つ い て 肯 定 ・J否定 が 同 時 に 存 在 す る よ
い ま い さ を 含 む 入 力 が 確 定 し た と 仮定 し
た 時 に 取 り得 る 関 数 の 値 が{o,1}な
う な 項 が あ り得 る 。、こ の よ う な 項 を そ れ ぞ れ 相 補 積 項,
す る 関 数 値 は%で
相 補 和 項 と い う。 あ るBL三
が 確 定 て い れ ば そ の 入 力 の 取 り得 るす べ て の 確 定 し擁
定 義 域V3n・={o;・va,1}.n:の
値 論 理 関 数 をFと
し,Fの
に 対 し で,関
あ る 元 を'α'と す る と き,q,に
(98)
あ り"・ま た`あ
ら ば 、,そ の 入 力 幽
る入 力 に対 す る関鍵
数 値 は 同 じ 確 定 し た 値 を.と る こ と を 韻 ・
B− 三 値 論理 に よ る素 項 展 開 の考 察
し,逆 は 必 ず し も成 立 し な い こ と を 意 味 して い る 。 と こ
た,φ
ろが,系2に
以 外 に 存 在 しえ な い 。 よ っ て,定
よ り,加
標準 形 な ら ば1に
法 標 準 形 な らば0に
対 して,乗
対 して 逆 が 成 立 す る 。 系1で
しな い と い うこ と は,一
般 にB−
三 値 論 理 で は あ る程 度
〔
補 題1〕
定 理2に
論
、^
論 理 式 φ を 加(乗)法
φ が表 現 す るB−
加(乗)法
す る と
て い る 論 理 式 が 乗(加)法
ギ ・x=0(∼x∨x=1)
.Xr.・-xαW-x),・,
き等 法 則)
は系1よ
り明 ら か 。 逆 を 示 そ う。 φ・
が 表 現 す る二 値 論 理
胸(吸
収 法 則)α
つ い でF(a*)≡`{1}と
す
、
る。 こ の と き,1
咋F-1(1)nV・n==f-'(1),・
一
元 をbと
理1②
蹴
〔
綱
り・ β← ・・'β*⊂f`i(1)柄
鞭
も 有 り鵡)『
す る と 明 ら か にF(旬
よ り,'F(a>=1が
α*で あ っ
解
βが φ に
剖 計
る
三 値 論 理 関 数 はP形
ち,￠
三 値 論 理 関 数 、Fは,系2よ
り
、
り
を 満 す 。 φ をB7三
論 理 関 数 であ
法 則 が 成 立 し な い と.して,省
値 論 理 の 式 と し て,す
なわ ち
算(i)を 施 こLて
,..1川
い る)を
F(α)=1#F(α*)・
・{1}『
Setに は 影 響 を 与 え な い か ら,{1}式
F(α)〒Y2?・=iF(α*)・
・{o ,1}
義7よ
り.i;はP形
が 保 た れ る 。 一 方,ψ'は
論 理 関 数 で あ る。
明 終)
よ り'
〔
定理 ・
〕 論理式 … 力藤 蹄 式 の素議 開で あ せ
めの必要十分条 件は,φ が既 約な加 〈
乗 〉法標 準形 で あ
り・表現するB− 三値論理関数 がP形 論理歯数で あ るこ
三 値 論 理 関 数 をF'
値 論 理 関 数 の1よ り
.
加 法 標 準 形 で あ る か ら,系2
,`t'.、
・.
F'(a)==O=iF'(a*)={0}
が 成 式 し,φ'は
既 約 は 加 法 標 準 形 で,F'.はP形
数 と な り,定 理2か
論理関
ら φ'は 素 項 展 開 と い う こ と に な る 。
φ が 加 法 標 準 形 で 与 え られ て い る場 合 も 同 様 で あ る 。 φ'
.'￨It、
醐)腰
細 ・
は淀 裁 抽 よび系 ・より鵬 か∴逆
を示そう・φが糊 する二麟 関数をf ,B≒
値言
融
関数をFと す る。 い ま,φ を既 約 な加 法 標 準 形 でFがP
形論理 関数 で あ る とす る。 ヒ め と きニゾ め 素 項 ぽ す べ て
が 表 現 す る 二 値 論 理 関 数 は 明 ら か に ∫ に 等 しい か ら,∫
の 素 顔 展 開 が 上 述 の 手 法 で 得 られ る こ と に な る 。
〔
系4〕
φに存在する二なぱ 堅
もしアのある雲脚
迦
なか・たとずる已 α剛 障 る元を鱒5と
頁④
‡1・しかレ ・がfの 瀬 嫡 恒(鱒
言固.・である
か らζれ はFがP形
なわち☆省略
F'(a)=1ごF'(α*)==一{1}1
:(証
。T
般 に相補積
約 な加 法標 準 形 に な って
φtと レ、φ'が 表 現 す るB−
と す る 。、揮 栢 積 項 の 除 去 は 、B-r三
然 的 に1"
が 導 か れ る か ら ,定
得 ら れ る 式(既
相 補
略 算{ii),㈹ を 用 い て 分 配 法
項 が 生 ず る 。 こ の 相 補 積 項 を 除 去 し て,す
lE
F(の=0"=・iF(a*)={0}
・,・i'
L,,(1)・
、!i岨 路)
開 と恒 巴,
則 に よ り加 法 形 式 に 展 開 す る 。 こ の と き,一
2お よ び 補 題1よ
る
を 乗 法 標 準 形 で 与 克 られ た 論 理 式 と すiる。 φが 表
・F(a)=1=㌧F(α*)二{1)
証明)φ が 表 現 す るB− 三 値 論 理 関 数 をFと す る ど,系
あ
論 理 に よ っ て も示 す こ と が で ぎ る 。.す な わ
現 す るB−
る。.'.=.・}
と で
形 式 ￠)莱項
展 開で ある。
ら,B-;値
・=1。b← α で あ る か ら定
る・ 、
一..‥
儲 娯 φを加 ㊥ 法形式 の業繋
が 示 さ れ,必
標準形 に展開
こ の 手 法 は. .既に 記 号 論 理 の 言 葉 を 用 い てR.J、
Nelson8}19) ,に よ り得 られ て い る も の で あ る がsl定 理2か
導 か れ る 。・
乗 法 形 式 の 場 合 も伺
φが 表 現 し て い るB−
配 法 則 を 用 い て 加(乗)法
す る 。 こ う し て 得 ら れ た 式 は ・ ∫ の 加(乗)法
ポ ・
示 され る ↓ ψ は 素 項 展 開Lc"あ る か
一 ・ とい う吐
・β∨ α・
・α
、
よ り,α に 対 応 す る 積 項 を α と す る と.ば ㌔
仕
.,
・((α〉 β),α 一 α)
を 用 い な が ら,分
.,`i,,,・
ら礒3・
、
標 準 形 で 与 え られ て い る と す
補 法 則)∼
働(べ
存在 括(β
の よ う
る二 値 論 理 関 数 五を 表 現 し
(i)(相
法 形 式 に つ い て 示 す 。F(a)-1-・F(a*)一{1}
た か ら,a*⊂f'i(1)が
三値論
論 理 関 数 で あ る よ うな 既 約 な
る。 こ の 式 を 省 略 算
・〔0})。
す る 。 あ る 元aに
明 終)
標 準 形 を 求 め る 問 題 に 帰 着 さ せ られ,次
証Jl)加
関 数 をfと
に は ∫の 素 項
りφは 素 項 展 開
項 展 開 を 求 め る 問 題 は,B−
索 痕 展 開 を 求 め る 手 法;あ
、F(α)・
・1=±F(α*)一{1L・
(F(α)=o=F(α*)こ
義4よ
な 素項 展 開 を 求 め る手 法 が 得 られ る 。
形 式 の 素 項 展 開 と し,
三 値 論 理 関 数 をFと
よ り,素
理 関 数 と して 見 た と きP形
三 値 論 理 関 数 とい うこ と
が言 え る 。.'㌧
は 既 約 は 加 法 標 準 形 で あ る か ら,ψ
で あ る 。 φ が 乗 法 標 準 形 の 場 合 に も 同 様 。(証
逆が成立
の情 報 が 失 な わ れ て い る こ と を 意 味 し て い る がJ`P形
理 関 数 は,,情 報 損 失 の な いB−
法
省 略 算 伺,㈹
(積)項
証 明)相
(・g9)
は カll(乗)法
も成 立 す る 。 ハ:・:.
φを
補 法 則 が成 立
標 準 形 に 展 開 し た と き ,相
が 生 じな い な ら ば,φ
開 で あ る。逆
標 準形 とす る
の み を 用 い て,・す な わ ち,相
し な い と し て 乗(加)法
論 理 関 数 で あ る こ とに矛 盾 ず る
6rま
論 理 式 φ を 既 約 な 加(乗)法
補和
形 式 の 素項 展
,.,,
補 法 則 が 成 立 し な い と い う こ と{お
ψ をB−
三
明 治 大 学 工 学 部 研 究報 告'No.29
値 論 理 の 式 と し て 見 て 展 開 した こ と に な る。 こ れ が 表 現
す るB−
4.む
す
び
三 値 論 理 関 数 を'F−とす る 。 加 法 標 準 形 で 与 え ら
B− 三 値 論 理 を 用 い て,二 値 論 理 関 数 の 素 項 展 開 のい
れ れ ば,
F(α)-0〒=≧F(α*)一{0}。
くつ か の 性 質 を 明 らか に した 。
一
一 方 ,乗
法 形 式 に展 開 して 相 補 和 項 が 生 じな い とい うこ
とは,乗
法 標 準 形 に な って い る訳 で あ るか ら
草 稿16)に修 正 加 筆 した もの で,熱 心 に ご検 討 下 さ った研
究 会 の 方 々に 感 謝 致 し ます 。 最 後 に,日
F(a):=一・1Fi!F(a*)E{1}。
よ っ て,FはP形
本 論 文 は,電 子 通 信 学 会 オ ーマ トソ ト研 究 会 にお け る
論 理 関 数 で あ る か ら,定
理2よ
り φは
加法 形 式 の 素 項 展 開 で あ る。乗 法 形 式 の 場 合 も 同 様 で あ
る。(証
た だ く本 学 後 藤 以紀 教授,電
電 子 デ ィバ イ ス 部 長,長
〔系5〕
既 約 な 加(乗)法
標 準 形 φ に お い て,す
子 技 術総 合 研 究 所 駒 宮 安 男
田正 情 報 制 御 研 究 室 長 に 感 謝致
します 。
明 終)
数 に つ い て 補 元 が 存 在 し な け れ ば,φ
ごろ,御 指導 い
べての変
は 加(乗)法
文.一
形式の
献
1)HarvardCoinpusationLab.:c`Synthesisofe・
素 項 展 開 で あ る。
lectronic.cornputingandcontrolcircuitS,',Ann.
証 明)す
べ て の 変 数 に つ い て 補 元 が 存 在 し な い な らば,
φ をB−
三 値 論 理 の 式 と し て 乗(加)法
き.相
補 和(積)項
theComputationLaboratory,HarvardUpiversity
形 式 に 展 開 した と
は 生 じ な い か ら 系4よ
Press,Cambridge,VoL27(1951).
りφは 素項 展 開
で あ る。(証
2)E.W.Veitch="Achartmethodfotsimplifying
truthfunctions",Ptoc.AsS..Comput.Mach.confe∫.
明 終)
ence,PittsburghJp.127(May.1952).
〔定 理3〕
論 理 式 φ1,￠2を
そ れ ぞ れ 加(乗)法
.
形式の素
3)M.Karnaugh:"Themapmethodforsynthesis
項 展 開 と す る 。 φi・ ￠2(φ1>φ2)を
い て 加(乗)法
省 略 算(i),㈹,㈹
を用
ofco
標 準 形 に 展 開 し て 得 られ る式 は,加(乗)
,rnbinationalIogiccircuits",Trans・AIEE・Com・
mun:Electron.,Vol.72,p.593(NoV.1953).
4)W、V.Quine':"ThePr6blemofsimplifyingtruth
法 形 式 の 素項 展 開 で あ る。
functions",Amer,Math.Mon.,,VoL59,p.521(Oct.
証 明)φi,φ2お
よ び ￠1・ φ2が 表 現 す るB−
数 を そ れ ぞ れFl,F2お
よ びF3←Fl・
￠2は 素 項 展 開 で あ る か ら系3よ
三 値論理関
1952).
・F2)とす る 。 φ1,
りFl,F2'は
5)E.J.McCluskey:"MinimizationofBooleanfunc'
そ れぞれ
tions",BellSyst.Tech.」.,VoL35,p.1414(Nov.
1956).-'"
瓦(α)三li!Fi(a*)={1},・i=ゴ,2。
6)W.V.9uine:"Awaytosimplifytruthfunc・
よ っ て'・
F3(α)'畦
、
一 ・F,(α
が 得 られ る 。 φ11φ2を
1955).
省 略 算(i),(ii),㈹ に 従 っ て 加 法 標
準 形 に 展 開 して 得 ら れ る 式 が 表 現 す るB−
をF3'と
tion・",Ame・.Math.Mon.,y?L62,p.627(N・Y.
・)一 〔1}』(2)
7)T.H.Mott:"Determizationofthe'irredunda皿t
normalformsofatruthfunctionbyiteratedcon・
三値論理関数
す る 。 上 述 した 素 項 展 開 を 求 め る 手 法 のB−
sensusoftheprimeimplicants",Trans.IRE,
三
ElcectronlcComputers,Vo1.EC-9,p.245(June
値 論 理 に よ る 説 明 と 同 様 に,相
論 理 関 数 の1-Setに
補 積 項 の 除 去 はB−
三 値
1960).
影 響 を お よ ぼ さ な い か ら,
8)R.J.Nelson:"Simplest'riormaltmthfunctions",
(2)式 よ り
」.SymbolicLogic,VoL20,p.105(June1955).
9)R.J.Ne}son:"Weaksimplestnormalttuth
F3'(a)-i;=tF3'(a*)一{1}
furctions",J.SymbolicLogic,VoL20,p.232(Sep・
が 保 持 され る 。 一・
方,'.得 られ た 式 は 既 約 な 加 法 標 準 形 に
な っ て い る か ら,系2よ
1955).
り,
10)J.R.Sl・gl・,C.L.Ch・
F3'(α)■O≠F3'(α*)一{0}。
よ っ て,F3'はP形
・g・ndR.C・T・L・e・"A
爬walgorithmforgeneratingprinieimplicant'
論 理 関 数 で あ る か ら,定
理2よ
Trans.IEEE,Comput.,Vo1.C-19,P.304(Ap「
り加
ロ
・
1970).
法 形 式 の 索 莫 展 開 が 得 られ る 。乗 法 標 準形 の 場 合 も 同
様 。,.(証
〔
系6〕
(積)項
11)S.R.D・
明 終)
論 理 式 φ を 加(乗)法
形 式 の 素 項 展 開,aを
・andN'.S.Kh・b・a・"Cl・u・e・ca1・mt・ble
。pP,。achf・rg・n・
・titi・g・llth・p・i㎡
・implicant・
・1
。wit。hi。gfun、ti。n、tt,T,an・..IEEE,C・mp・t,,V・1・
和
C-21,.p.1239(Nov.1972).,
と す る 。 Φ ・α(φ∨ α)を 省 略(i),(ii)、 ㈹ 算 を 用 い
12)M.J.Gazale:"IrredundantdiSjunctiveandcon'
て 加 ・(乗)法 標 準 形 に 展 開 して 得 ら れ る 式 は.加(乗)法
junctiveforrpsofaB601eanfunction'㌔IBMJ・
形 式 の 素 項 展 開 で あ る6
証 明)和(積)項
る か ら,定
理3よ
は す べ て 加(乗)法
Vo!.1,p.171(April1957).
形 式 の素 項 展 開 で あ
り導 か れ る 。・"tt(証
13)wiv.:Q。i・
t,uthf。n,ti。
明終ン
(100)
…d・'・dfe・ahdp・im・im・li…t・
。、・,Am,,:M・th.M・f・
・l
、,V・1.66,P・755
B− 三 値 論 理 に よ る素 項 展開 の考 察
(Nov.1959).
会 論 文 誌D,55-D,6,P.335(1972-6).
16)内 殿 政 男:"B−
三 値 論理 関数 に よ る 素項 展開 の 求
14)S.R.Das=`℃ommentsonarewalgorithmfor
generatingprimeimplicant",Trans,IEEE,Compt.
め 方",電
(Corresp.),Vol.C-20,p.1614(Dec.1971).
88(1971-3).
15)南
殿 政
男:"B−
三 値 論 理 関 数 に つ い て",電
子 通 信
(101)
子 通 信 学 会 オ ー トマ トン 研 究 会 資 料 ,A70-