組 合 せ 計 算 の た め の代 数 処 理 言 語 の 開 発
杉 本 英 二
要 旨
有 限 代 数 上 の組 合 せ 計 算 の た め に,集 合 ・写 像 ・群 ・関 係 ・準 同 型 な ど の概 念 を 定 義 ・ 計 算 す るた め の言 語 と,そ の 処 理 系 をprolog言 語 で作 成 した。
0.は じめ に
1.代 数 系 の 特 徴 につ いて 2.代 数 処 理 用 言 語 3.処 理 系 と結 果 4.参 考 文献
0.は じ め に
PermutationGroupsandCombinatorialStructures〔1〕 の よ うな 組 合 せ 理 論 の 研 究 に有 限 世 界 で の群 ・体 が 利 用 され る。 この よ うな 分 野 の 研 究 と学 習 に お いて,手 計 算 が で き る範 囲 に お いて も具 体 的 な組 合 せ を調 べ る ことが 必 要 に な る ことが 多 駄・。 単 純 な話 で は,特 定 の 群 の 中で 特 定 の 条 件 を満 たす 部 分 群 や部 分 集 合 をす べ て 見 つ け 出す とか,有 限 幾 何 上 の 直 線 ・平 面 ・点 な どの 相 互 関 係 を具 体 例 で 調 べ る な どが あ る。
そ の手 計 算 を系 統 的 に簡 単 化 して みて も,か な りな 量 に な る。も と も と組 合 せ 問 題 の 計 算 量 は問 題 の サ イ ズ を直 接 反 映 し,2nオ ーダ ーに な るの で,手 計 算 が 可 能 な範 囲 は非 常 に 限 られ て い る。 この よ うな事 態 を 改善 す るた め に計 算 機 を 利 用 す る こ とに な る が,FortranやPasca1で は実 行 速 度 は速 い が,プ ロ グ ラ ミン グが め ん ど うで あ る。 関 連 す るプ ロ グ ラム を い くつ か作 って も,デ ー タの 一 貫性 に よ ほ ど注 意 しな い と,そ れ らを組 合せた複雑 な計算 がで きない。
〔61〕
62 商 学 討 究 第36巻 第4号
そ こで,代 数 的概 念 を人 間 に 近 い 言葉 で 計 算機 に 入 力 で き て,そ れ らの概 念 を組 合 せ て よ り高 い概 念 を形 成 で き,そ れ らの 計 算 も可能 とす る シス テ ム が 必 要 で あ る。 この シス テ ム の 開 発 は,代 数 処理 の ツー ル と して も必 要 で あ るが, 一 方 で 公 理 ・推 論 ・証 明 ・知 識 とい う点 で も興 味 が あ る。今回,代 数的 ツール
と して 短 期 間 の 開 発 途 中 で あ るが,代 数 処 理 用 言 語 と処 理 系 を 作 った の で 報 告 す る。
従 来 この よ う な分 野 と して は,数 式 処 理 の 研 究 が あ る。 その 成 果 と して,大 型 計 算 機 用 のREDUCEやMACSYMA,パ ソ コ ン用 のmuMATHな ど が あ
る 〔2〕。 これ らの シス テ ム に よ って,代 数 方 程 式,微 積 分 や三 角 関 数 の 計 算, 素 因 数 分 解 な どが 容 易 に計 算 で き る よ うに な り,工 学 的 ・物 理 的 計 算 に大 き く 寄 与 して い る。
しか し,こ れ らの シス テ ム は実 数 と整 数 上 の計 算 を行 な うが,,利 用 者 が 勝 手 に決 め た演 算 系 の計 算 が で き る訳 で は な い。 今 回 の代 数 処 理 用言 語 で は,集 合 ・ 写 像 ・関 係 ・商 集 合 ・準 同型 と準 同型 射 ・群 ・体 な ど を 自由 に定 義 で きて,定
義 され た様 々 の概 念 に特 定 の例 が満 足 して い るか の判 定 や,条 件 を 満 た す集 合 の 探索 列挙 も可 能 で あ る。
1.代 数 系 の 特 徴 につ いて
＼
少 な くと も どの よ うな 機 能 が 必 要 か を 考 え る。 代 数 系 を始 め るの に必 要 な基 本 的 機 能 か ら順 次 取 入 れ る こ ζ に して,当 面 以 下 の 概 念 を 考 慮 す る。
A.集 合 に つ い て
集 合 を 定 義 す る と は,次 の4つ の 場 合 が あ る。
(1)あ る記 号 を集 合 で あ る と定 義 す る場 合 。
(例)Rは 集 合 で あ る ①
(2)あ る記 号 が 集 合 で あ って,そ の 外 延 を具 体 的 に与 え る場 合 。
(例)8={α,b,嬬d}、 ②
(3)あ る記 号 が 集 合 で あ って,そ の 内包 的表 現 で集 合 の定 義 を与 え る場 合 (例)7=移iκ ∈.R,κ≧100}③
組合せ計算 のための代数処理 言語 の開発
(4》 あ る集 合 か ら,別 の 集 合 を 新 た に 作 り 出 す と い う メ タ 操 作 の 場 合 。 (例)P={列VはSの 部 分 集 合}.④
(例)ルf=S×7(直 積 を と る)⑤ B.写 像 に つ い て
63
集 合Aの 各 要素 に つ い て,集 合Bの 要素 を一 意 に定 め る対 応 づ け ∫が あ る と き,∫ を み か らBへ の写 像 とい い,
∫:A→B ⑥
で 表 わ す。
写像 の 中 で も,
甲:A×S→S
の 型 の 写像 は,AがSに 作 用す る と見 られ る。特 にAが8と 一 致 す る と き, gをSの2項 演 算 と呼 ぶ。作 用 あ るい は2項 演 算 を 具 体 的 に 定 義 す る方 法 と し て,外 延 的 定 義 と内 包 的 定 義 の 方 法 が あ る。
(例)*:8×s→8で,
具 体 的 に は,(α,α)→ α(α,の → わ(α,c)→c (わ,α)→ わ(わ,わ)→c(b,c)→ α (C,α)→C(C,わ)→ α(C,C)→ わ
と 与 え る 方 法 と,あ る い は
(κ,ッ)→
ッ(κ=α) κ(ン=α) α(κ ≒y) c(κ=b,ツ=わ)
わ0ε んθrὼSθ
⑦
⑧
とす る方 法 で あ る。
64'商 学 討 究 第36巻 第4号
C.8〃8兜 配 の 定 義 に つ い て
演 算 を 伴 な う集 合 をsッs̀θ 加 と呼 ぶ こ と に す る 。 そ うす る と,群 ・環 ・体 は sツs̀θmで あ る 。写 像*を,
(例)Sを 集 合 と す る 。
*=S×S→S⑨
な る2項 演 算 とす る。 この と き,(s,*)が 次 の 条 件 を 満 た す と き群 と よ5ミ。
(1)結 合 則yコ じ,ッ,2∈S((κ*y)*2=κ*(ッ*2))⑩ (2}単 位 元 の 存 在 πω ∈8協 ∈8(ω*3じ=κ*ω=κ)⑪
(3)逆 元 の 存 在 伽 ∈S夙 ッ ∈8(κ*y=y*炉 の ⑫
こ の よ う にSと*と の 組 を1つ の 砂s̀e配 とす る こ と が で き る が,Sを 別 の 演 算 と 組 に し て 別 のsys詑 配 を 作 る こ と も で き る。 又,こ のsッ8tθ 襯 の 中 に 部 分 砂sεe配 を 定 義 す る こ と も可 能 で あ る 。
(例)H⊂Sで,以 下 の2つ あ 条 件 を 満 た す もの を 部 分 群 と よぶ 。
11)演 算 に 閉 じて い る こ と=yκ,ッ ∈ ∬(κ*ッ ∈ ∬) (2)逆 元 の 存 在:残 ∈H匠 ッ ∈H(κ*y=ッ*コ σ=の
D.関 係 の 定 義 に つ い て
集 合 の 中 に 関 係 を 導 入 で き る 。
(例)Sを 群 と して α,わ ∈Sと す る と き,乏rκ ∈S(α 二 κ一1厩)
⑬ ⑭
な、る と き,α と わ は 共 役 で あ る と い う 。 これ を α〜bと 表 わ す こ と に す る 。 こ の こ と を,
α〜b⇔ πκ ∈s(α=ズlb3じ)⑮
と書 く。 こ の 関 孫 が,特 に 次 の3条 件 を 満 た す と き,同 値 関 係 と い う。
組 合せ計算のための代数処理言語の開発 65
(1)反 射 律=yκ ∈S(κ 〜 め ⑯
(2)対 称 律:y劣,ッ ∈8(コ じ〜 ッ今 ・ッ〜 κ)⑰
(3)推 移 律:yκ,y,2∈S(κ 〜 ッ απdッ 〜2今 κ〜2)⑱
同 値 関 係 が 定 義 で き る 集 合 は,そ の 関 係 に よ っ て 同 値 類 に 牙 割 さ れ る。 集 合 Sの 〜 に 関 す る そ れ ら の 同 値 類 全 体 か ら な る集 合 をS/〜 で 表 わ す 。 こ れ を 商 集 合 と よ ぶ 。s∈Sにsの 同 値 類 を 対 応 さ せ る 写 像p
ρ:3→8/〜 ⑲
を 標 準 的 全 射 と い う。
E.準 同 型 と 射 に つ い て
群0=(8,*)の 中 に 同 値 関 係 〜 が 定 義 さ れ て,Dの よ う に 商 集 合8'=8/〜 ・ が で き た とす る 。S'の 要 素 間 にGの 演 算*と 矛 盾 な く,新 し い 演 算 ∠
4:S'×S'→S' ⑳
が 定 義 で き て,G'=(S7,の が 群 に な る と き,Gと α は 準 同 型 と い う 。 こ こ で 矛 盾 な く と い う の は,
V鑑,ツ ∈S(ρ(κ*y)=P(κ)」P(ツ))⑳
が 成 立 す る こ と を 指 す 。 た だ し ρ は 標 準 的 全 射 で あ る と す る 。
Gと0'が 準 同 型 で あ る と き,Gか らG'へ の 写 像 を 準 同 型 射 と よ ん で,
ん:θ → α ⑫
と表 わす 。
Gが 定 義 されて い る集 合 上 の写 像 で 表 わ す と,
P=S→S/〜'
が ん に 相 当 し て い る が,pよ り も ん の 表 現 の 方 が 好 ま れ て い る。 多 く の 場 合,
66 商 学 討 究 第36巻 第4号
こ のpと ゐ は 同 一 の 記 号 で 表 わ さ れ,文 脈 上 で ど ち ら か 判 断 す る こ と に な って い る 。
F.8〃8勿 榔 の 直 積 に つ い て
8ッsεθ配 の 直 積 が 必 要 な の は ベ ク トル の 導 入 に お い て で あ る 。例 え ば,群G=
(8,*)の 要 素 を 係 数 と して,
(α1,α2,̲,砺),(わ ・,b2,̲,わ の
を 作 っ た と き に,ベ ク トル の 演 算 を*と して,
(α1,α2,̲,α 。)*(わ1,わ2,̲,わ 。)
=(α1*わ1 ,α2*わ2,̲,α 。*わ 。) ⑳
が 自然 に定 義 で きて い る と良 い。
小 さ いsッs̀θ配 を 構 成 要 素 とす る大 きなsッs陀mが,構 成 要素 の性 質 を 自然 に受 継 ぐこ とが 望 ま しい。 米 田信 夫 先 生 も この 点 を 指 摘 され て い る[3]。
2,代 数 処 理 用言 語
数 学 上 の 様 々 の概 念 定 義 は非 常 に短 い文 で 書 か れ,そ れ ら は主 に集 合 ・写 像 ・ 論 理式 で表 現 され て い る。 代 数 処 理 用 言 語 は,で き る だ け数 学 上 の記 法 に従 っ て 設計 す る こ とを基 本 方 針 に して 以 下 の よ うに定 義 した。
後 で,実 現 の都 合 上 の制 限 か ら,こ こで の定 義 ど お りに は実 現 され な い所 も あ るが,大 き な違 い は な い。
A.集 合 と写 像 に つ い て
集 合 と写 像 は代 数 で 中心 的役 割 を担 って い る ので,こ れ らを基 本 的 デ ー タ型 とす る。 そ れ らをsθε型 と 濡αp画πg型 とよぶ 。
そ うす る と,① を 次 の よ うに 表 わ そ う。
D⑳ πθsθ むR.
② はそ の ま まの 形 で 表 わ す 。
組 合せ計算 のため代数処理言語の開発 ,67
D⑳ πesθ̀S={α,わ,c,の.
① の よ う に,記 号Sを 集 合 型 の 変 数 と して 使 う場 合 と,② の よ う に集 合 の 具 体 的 実 体 を 指 定 す る場 合 が あ る。 集 合概 念 は,集 合 の 要 素 と して 利 用 で き る もの を あ ま り制 限 を しな いの で,計 算 機 処 理 で は工 夫 が い る。 集 合 の 要 素 と し て 使 わ れ る もの と して,数,記 号,部 分 集 合,写 像,sッs̀飢 な ど多 様 で あ る。
これ らの どれ が 要素 で あ って も,集 合 と して の 取 扱 いが 可 能 で な けれ ば な らな い。
集 合 が 条 件 で指 定 され て い る場 合 は, 、その条件を評価 し,条 件 を満 た してい る 要素 を集 めて 集 合 とす る機 能 が 必 要 で あ る。 集 合 ③ は その よ うな集 合 で あ る。
これ を次 の よ うに表 わす 。
Dの ηesθ̀7={κ ∈Rl誕 ≧100}.
この 文 は,条 件 を 表 わ す理 論式 の部 分,ど この集 合 の 要素 を取 出す か の 指定 の部 分,そ して 作 られ た集 合 の 名前 の部 分 か ら構 成 され て い る。sθ̀型 を 基本 的 デ ー タ とす る と き,sθ 亡型 に 所 属 す る実現 値(o(油rθ πcの を 生 成 す る操 作 は 基 本 的 操 作 と して 提 供 され な けれ ば な らな い。 例 え ば,巾 集 合 を 作 る(④), 直 積 を と る(⑤)な どで あ る。 そ れ らを 作 り出 す 基 本 関 数 を 次 の よ うに しよ う。
PS=Poω θπ一sθ̲̀o∫(S).
ル1=D̀recむ̲Pro伽è(8,7).
集 合 間 の 写 像(⑥)は,
Dげ̀π θ πLαρP加9∫:A→R
で,Aか らBへ の 写 像/を 定 義 す る 。 集 合AとBが,次 の よ う に 定 義 さ れ て い た と き に,写 像gを 具 体 的 に 定 義 す る に は 下 記 の よ う に す る 。
D￠ 伽 θsθ 古A={α,b}.
68商 学 .討 究 第36巻 第4号
Dげ επθs㏄B={c,d}.
1)⑳ πθ ηL￠ρρ̀η99=・4→ 旦 s%c尻 訪 ὰα 一考c,6→d.
こ の よ ケ に して 定 義 さ れ た 写 像gの 逆 写 像 επ叱gの 定 義 は 次 の よ う に で き る 。
D￠伽 θ1ηαPP̀㎎ 伽 一8三B→ ゑ sωoh訪 αε
・α・̀φzθs・・→ ツ,
び 翫 ∈ ム(9(β)=κ)ε んθηy:=9・
も っ と 高 級 的 に 書 くな ら8‑1と だ け で す む の 恭 望 ま しい 。 そ うす る と汎 関 数 的 な働 き 一1を 定 義 で き な け れ ば な らな い 。 今 回 は 対 象 外 と して お く。
次 に ⑦ を 次 の よ う に 表 わ す 。
D{ゾ 加θ 〃L￠ρPε九g*:ρ かθcかPrα加c̀(a8)→S, Sεκ ん 腕 αε
(α,α)→ α,(α,わ)→b,(α,c)→c, (b,α)→ わ,(b,わ)→c,(δ,c)→ α, (c,α)→c,(c,b)→ α,(c,e)→b.
⑧ の よ う に,定 義 中 に 判 断 と 計 算 力泌 要 な 場 合,マ ッ カ ー シ ー の 条 件 式 を 使 う の が 良 い で あ ろ う 。
D(沸 πemαPP㎏*;Dεrecε 一Prodωct(S,8)→S, 8㏄ ゐ 魏 ὰ
ひαr励Zθs(κ,ッ)→9, ザ κ=ὰhθ π2:=夕
θZsθ̲ガ ッ=α 伽 π2:=コ 〔
組 合 せ 計 算 の た め の 代 数 処 理 言 語 の 開 発
θεse̲εア κ≒ỳん θπ9:=α
eZs￠̲εノ κ=bα πdツ=bε んθη β:=c θεεθ2:=わ.
69
B.8那 惚鵬 の 定 義 に つ い て
集 合 と演 算 の 組 を εッs̀θ肌 と呼 び,そ れ に 名 前 を つ け る こ と が 必 要 だ か ら,
D4Zπ θsッsεθmΣ=・(S,*).
と で も表 わ せ た ら よ い 。 し か し,こ れ だ と 同 一 の 記 号*を 異 な る 演 算 の た め に 利 用 で き な く な る。 た と え ば,新 た に
1)⑳ πθ 釧s̀θηL1「=(望 「,*)..
と す る と*の 定 義 域 は8か7か 不 明 瞭 た な る 。 そ こ で1つ の 演 算 記 号 を 重 複 し て 使 っ て も ど の 演 算 か 一 意 的 に す る た め に,演 算 に 名 前 を つ け よ う 。 そ う す る と ⑦ は
D⑳ πθ 〃脚 画90P1,*:D̀Pθc̀‑Prodωc̀(S,.S)→S, sωの̲̀hὰ.̲
と 表 わ し,一 方
Dφ πθ 配 αPPε㎎OP2,*:Dか ㏄ ε一Prod厩(7,の →7, SωCん εんαε....
と す れ ば,先 ほ ど のsystε 配 の 定 義 は,
D{ゲ επθsッs古θ〃喜 Σ 二(S,OP1).
Dげ επθsッs̀θ〃Lr=σ 〜OP2).
と書 け て,Σ とrも 同 一 記 号 を 演 算 記 号 と して 利 用 で き る 。
70商 学 討 究 第36巻 第4号
C.関 係 と 同 値 類 に つ い て
集 合 の 中 に 共 役 関 係 〜 を 定 義 す る に は,
D⑳ πθrθzα古εoη〜oπa sωcん̀ん αε
レα,わ∈S(α 〜 わ ⇔ 翫 ∈S(α=ズ1bκ)).
と 書 け れ ば よ い 。 人 間 に と っ て は,特 に 式 の 中 で 指 定 が な くて も,群G=(a op1)の 範 囲 で 定 義 さ れ て い る こ と は 文 脈 上 理 解 で き るが,計 算 機 言 語 上,こ れ で は 不 十 分 で あ る の で,式 の 計 算 を 明 示 す る 。 ど の εys̀θπ}上 の 計 算 か を 明 示 す る た め に,
θひ配̲oη(式,sy蕊 θ配 名)
を 導 入 し よ う。 そ うす る と,上 の 鋤ch̲抗 αε 以 下 の 式 は 次 の よ う に 表 わ せ る 。
yα,わ ∈S(α 〜b⇔ 翫 ∈S(α=θ ひαZ̲oπ(ズ1わ κ,G))).
関 係 が 同 値 関 数 を 満 た して,そ の 商 集 合 を 取 出 す に は,
9ωo古εθ碗̲sθ̀(8/〜)＼
と 書 く こ と に す る 。 こ の 手 順 に 伴 な っ て,標 準 的 余 射 も作 られ,そ のmα ρ炉 πg をpの 名 前 で 利 用 し た い と き に は,
9θ̲̀7η αP伽9̲〇 五 α窃0̀̀θηε̲cZαSS(P:S→8/〜).
で 取 出 す こ と に す る 。 D.準 同 型 と 射 に つ い て
2つ のsッsε θmO1=(81,0p1),G2=(S2,0p2)の 準 同 型 射 ゐ を 定 義 す る に は,写 像pが 定 義 さ れ て い る と き,
Dσ 加 θmorp砺SπLh:G1→G2, μs弓7zgηzαρPLlzgP・
組 合 せ 計 算 の だ め の 代 数 処 理 言 語 の 開 発71
と す る。
も し,pが あ る 同 値 関 係 に よ っ て 商 集 合S2を 作 っ た と き の 標 準 的 全 射 な ら 容 易 に 準 同 型 射 が 定 義 で き る 。op2が ま だ 不 定 の 場 合 に は,準 同 型 の 性 質 と pを 使 って,op2の 具 体 化 を 可 能 とす る 手 段 が あ る と都 合 が よ い 。
E.8〃8惚 配 の 直 積 に つ い て
sッs̀θ酩G1,G2,...,G.の 直 積 と そ の 上 で の 演 算+を 次 の よ う に 定 義 す る 。
D〔伽 θ 倒36θ 鷹y=(0̀rθC̀ ̲Pr・d臨(01,0・,…,0・),嘔 πS).
D⑳ ηθ7η αρPε㎎ びp肱s,+=v×v→ 玖
鋤ch肋 α ε
ひαr励Zθ((κ1,κ2,̲,κ 。),(y1,y・,轡,ッ の)→(β1,92,̲,2・), 之1:;θ ひαZ‑0η(κ1*ツ1,α),
22:=θ ひαZ‑oπ(κ2*ッ2,G2),
zη:=θ びα3‑oπ(κ πr野y",σ")・
3.処 理 系 と 結 果
処 理 系 はprolog言 語 上 に 作 る。 こ の 言 語 を 採 用 し た 主 な 理 由 を ま と め る と, 次 の2項 に な る。
(1)代 数 処 理 用 言 語 と違 和 感 が 少 な い 高 レ ベ ル 言 語 で あ る こ と。
(2)手 近 な パ ソ コ ンに,シ ス テ ム の 開 発 環 境 が そ ろ っ た 高 速 のprologイ ン タ プ リ タprologKABA〔4〕 が あ る こ と。
処 理 系 の 開 発 を 短縮 す るた め に,prolo9が 代 数 処 理 言 語 の ソー ス プ ロ グ ラ ムの 各 文 をread命 令 で 読 込 め るよ うに,構 文 を 少 し変更 し たの で,こ の 点 に つ いて 主 な と こ ろを 補 足 的 に説 明 す る。 処 理 系 の 主 な と ころ は,宣 言 的 に定 義 され た代 数 処 理 言 語 の 各 文 を,prolog言 語 の プ ロ グ ラム に変 換(翻 訳)す る こ とで,中 で も論 理 式 の 評 価 法 と,集 合 と写像 を 実 現 す るデ ー タ構 造 の 設定 が 問 題 で あ る。
商 学 討 究 第36巻 第4号
Aで 論 理 式 の評 価 につ いて 述 べ,Bで 実 現 され た 構 文 と例 を 示 す。Cで は, 処 理 系 の 概 略 と実 行 結 果 を示 す 。
A.prolog言 語 に よ る 論 理 式 の 表 現 と 評 価
論 理 式 は す べ てprologの 項 と して 表 現 す る こ と に した 。 論 理 記 号 のand, or,notは 次 の 構 文 で あ る 。
(1)prologの 項 は 論 理 式 で あ る 。
(2)AとBが 論 理 式 な ら,AandBと,AorBは 論 理 式 で あ る 。 {3)Aが 論 理 式 な ら,not(A)も 論 理 式 で あ る 。
限 量 の た め に 次 の 述 語 を 用 意 し た 。 全 称 記 号:fof̲any̲element̲of(X,S,Wff) 存 在 記 号:for̲some̲element̲of(X,S,Wff)
Xは,限 量 を 受 け る 変 数,SはXが 所 属 す る集 合,Wffは 論 理 式 で あ る。 こ の2つ の 述 語 は 項 だ か ら,上 の 論 理 式 の 構 文 に よ っ て 論 理 式 と な る。 以 上 の 構 文 で す べ て の 論 理 式 を 表 現 で き る 。
集 合 と 群 の 公 理 に 関 す る 部 分 を 論 理 式 で 表 現 し て み よ う。 そ の た め に,ま ず 集 合 の 定 義 と デ ー タ 構 造 を 与 え る 。 代 数 処 理 の 定 義 文 は,prologの 項 とす る 。 集 合 の 定 義 ① と ② を 次 の よ う に 表 わ す 。
define(set,name̲is(setR)).
define(set,name̲is(setS),[a,b,c,d]).
集 合 名 をsetR,setSと した の は,prologの 項 の 構 文 を 受 け る の で,大 文 字 で 始 ま る 名 前 は 変 数 に な る か らで あ る 。 だ か ら,名 前 は す べ て 小 文 字 で 始 ま る よ
う に す る 。
上 記 のsetSは,prologで 次 の よ う に 翻 訳 さ れ て い る。
組合せ計算 のための代数処理言語 の開発
setS([set,a,b,c,d]).1,
集 合 の 要 素 か ど う か を 判 定 す る た め に 次 の 述 語 を 用 意 し た 。
is̲aしelement̲of(E,S)
こ れ は,EがSの 要 素 で あ る と き 真 に な る 。
systemは 集 合 と 演 算 の 組 で あ る が,systemXか ら集 合 を 取 出 す 関 数set (X)を 用 意 し た 。
以 上 の 用 意 を す る と,Gを 演 算*を 持 つsystemと す る と き,群 の 公 理 は 次 の よ う に 書 け る 。
(結 合 側)(⑩)2,
for ̲any̲eleme血t̲of(X,set(G), for ̲any̲element̲of(Y,set(G), for ̲any̲element̲of(Z,set(G),
evaLon,(R,(X*Y)*Z,G)andevaLon(L,X*(Y*Z),G) and(L=R))))
(単 位 元 の 存 在)(⑪)2⊃
for ̲some̲element̲of(U,set(G), for̲any̲element̲of(X,set(G),
(eval̲on(Y1,U*X,G)and(Y1=X))and (evaしon(Y2,X*U,G)and(Y2=X))))
(逆 元 の 存 在)(⑫)2,・3,
1)〔 譜2〕 と 〔譜3〕 を 参 照 の こ と 。
2)こ こ で 使 わ れ るeva1‑Qn(X,Y,Z}は,systemZ上 で 式Yを 計 算 す る と そ の 値 がXに な る と い う 述 語 で あ る 。
3)unity̲of(X,Y)はsystemYの 単 位 元 がXで あ る と い う 述 語 で あ る 。
74 商 学 討 究 第36巻 第4号
unity̲of(U,G)and
for̲any̲element̲Qf(X,set(G), for̲some̲element̲of(Y,set(G),
evaLon(U,X*Y,G)andevaLon(U,Y*X,G))).
この 論 理 式 の 評 価 は,処 理 系 のeval‑wffに よ っ て イ ン タ ー プ リー ト さ れ る 。 そ の プ ロ グ ラ ム を 〔譜1〕 で 示 す 。
〔譜1〕 は 主 に,and,or,notの 論 理 計 算 の 部 分 と,全 称 限 量 と 存 在 限 量 の 部 分 と か ら構 成 さ れ て い る 。 論 理 計 算 の 部 分 の カ ッ トは 省 略 す る 訳 に は い か な い が,and式 中,も し く はor式 中 の バ ッ ク トラ ッ ク が あ っ て も カ ッ トは バ ッ ク トラ ッ ク を 阻 害 す る こ と は な い よ う に な っ て い る 。
全 称 限 量 を 実 施 す るfor̲any̲elemenLof1(E,S,Wff)は,集 合 の 各 要 素 をEに 取 出 して,Eを 含 む 論 理 式Wffの 真 偽 を テ ス トす る 。す べ て の 要 素 で 真 の と き,こ の 述 語 は 真 と な る よ う に な っ て い る 。 存 在 限 量 を 実 施 す るfor̲
some̲element̲of1(E,S,Wff)は,集 合 の 各 要 素 をEに 取 出 し,Eを 含 む 論 理 式Wffの 真 偽 を テ ス トす る 。 ど れ か あ る 要 素 で 真 に な れ ば,こ の 述 語 は 真 と な る。 しか も こ の 述 語 は バ ッ ク ト ラ ッ ク も可 能 に な って い る 点 は 好 ま し い と 言 え る。 そ の 理 由 は,論 理 式 の 評 価 は 式 の 前 の 方 か ら順 番 に 行 な わ れ る の で, 評 価 途 中 の 解 は 必 ず し も式 全 体 の 解 で は な い 。 そ こ で バ ッ ク ト ラ ッ ク 処 理 に よ っ て 式 全 体 の 解 を 求 め る と い う の で あ る 。
B.主 な 構 文 と例
定 義 文 は,function定 義,set定 義,mapping定 義,binary̲operation定 義,system定 義,relation定 義,morphism定 義 な ど を 用 意 し た 。
主 な 定 義 文 の 構 文 と 意 味 を 次 に 示 す 。
(1)function定 義
組合せ計算のための代数処理言語の開発
蜘 ㎞ 輔 数名{熱 い}プ・グ・ム部)・
嘉脇 憶1
̲レ
引 数 部=arguments(〔 引 数 指 定,。..〕) プ ロ グ ラ ム 部=program(〔 句,̲〕) 関 数 子=id名
引 数 変 数=変 数 名
一{聾}一 描 …}
型一胤 羅 d
叫 醜 、
句=prologの 項
function定 義 は,prologの 節 に 翻 訳 さ れ る。 関 数 名 と 引 数 部 は,そ の 節 頭 に な り,プ ロ グ ラ ム 部 は,並 べ ら れ た 句 の 順 序 の ま ま 節 体 と な る。nameis (̲)で 関 数 の 名 前 を 定 義 す る が,name̲isは 省 略 で き る。 引 数 部 に お い て, 各 引 数 の 入 出 力 の 方 向 の コ メ ン トを 書 け て,型 の チ ェ ッ ク を 指 定 す る こ と が で き る 。 入 力 変 数 は 入 力 時 の 型 の チ ェ ッ ク,出 力 変 数 は 出 力 時 の 型 の チ ェ ッ ク を 行 な う 。
check指 定 が な け れ ば,そ の 変 数 に つ い て あ 記 述 は 単 な る コ メ ン トと み な さ れ る 。
76商 学 討 究 第36巻 第4号
(2)binary̲operation定 義
…㎞(・瞬 聯 輔 算名 演算の型{選嚢獅}・
齪 一{鮮('d名)
演 算 の 型=演 算 記 号:[集 合 名,集 合 名]一 一 〉集 合 名
要素指定一 劃 〔{垂 案灘 グ
,ム}〕)
各 要 素 の 指 定=(要 素,要 素)一 一 〉 要 素,…
要素指定 プ ・グ・ム ー{演 算 入出力変数,選択 しな
い}句 …
演 算 入 出 力 変 数=variables((変 数 名,変 数 名)一 一 〉 変 数 名)
要 素 指 定 プ ロ グ ラ ム に つ い て 説 明 しよ う 。 要 素 ご と に 指 定 が で き な い 場 合 に は,2章Aで の 説 明 の よ う な マ ッ カ ー シ ー の 条 件 式 に な る よ う に,prologの 一 〉 と;を 使 っ てprologプ ロ グ ラ ム を 書 く。 そ の 場 合 要 素 を 指 す 変 数 が 必 要 な の で,そ れ を 演 算 入 出 力 変 数 で 指 定 す る 。evaLon(Value,Exp,Sys)の
Sysで この 演 算 のsystem名 が,演 算 式Expと と も にcallさ れ る と,こ の 要 素 指 定 プ ロ グ ラ ム が 実 行 さ れ る 。 要 素 指 定 プ ロ グ ラ ム の 代 り に'各 要 素 の 指 定 ・ が 選 択 さ れ て い た ら,そ の 指 定 の 内 容 が デ ー タ ベ ー ス と して 記 録 さ れ る 。
(3)代 数 処 理 言 語 の 例 文
言 語 の 概 略 の た め に6つ の 例 文 を 〔譜2〕 に 示 す 。 ど れ も読 み や す い と 思 わ れ る が,各 例 文 に つ い て,オ リ ジ ナ ル の 文 を 示 して お く。
' ・XintersectionY={ele∈Xande∈Y} .
・setN:set .
・*:setN×setN→setNで 次 の 表 で 与 え られ る 。
組合せ計算のための代数処理言語の開発 77
* a'bc
a b C
abc bca cab
・Sys1=(setN ,*).
uがGの 単 位 元 ⇔
πu∈Gγx∈G(u*x=xandl【*u=x)
ζ の よ う なuが 見 つ か れ ば,unity̲of(u,G)=一!.
と して デ ー タ ベ ー ス に 記 録 す る 。41
・G上xの 逆 元 がinvで あ る ⇔
uをGの 単 位 元 とす る と き,(u=inv*xandu=x*inの が 成 立 す る。
この よ うな定 義 を倖 つて・ あ るsystemが 群 の公 理 を 満 た して い るか ど うか を調 べ た り,あ る群 の部 分 群 を 列 挙 す る こ とが で き る。
C.処 理 系 の 構 成 と 実 行 例
代 数 処 理 言 語 の 各 定 義 文 はprologの 項 で あ る か ら,'prologのreadで 直 接 読 込 め る 。 読 込 ん だ 定 義 文 を 文 ご と にprolog言 語 の 文 に 翻 訳 す る 。 翻 訳 さ れ た 文 は,実 行 時 支 援 プ ロ グ ラ ム を 伴 な っ てprologKABAに ロ ー ドさ れ る 。[図1]
に この 概 略 を 示 す 。 実 行 時 支 援 プ ロ グ ラ ム に は,.例 え ばeva1‑wff述 語 な ど が 入 って お り,イ ン タ プ リ タ 的 な 働 き を して い る 。
〔譜2〕 の 翻 訳 結 果 を 〔譜3〕5}に 示 す 。 翻 訳 の 実 行 と,単 位 元 と 逆 元 を 求 め る 実 行 例 を 〔実 行 例 〕 に 示 す 。m串h.p1が 処 理 系 の プ 白 グ ラ ム で,sample
4)Unity̲Cla賂eにunity̲of(u,G):一!.の 内 容 が 代 入 され,そ れをasserta(Unity‑
Clause)で デ ー タベ ース に 記 録 す る 〔4〕 。
5):と 一 一〉 とcheckの オ ペ レー タ宣 言 はop(900,xfx,':7),op(800,yfk, ' 一一〉')
,oP(800・yf・chec≧)と な って い る。
、
,78 商 学 討 究 第36巻 第4号
代 数 処 理 言 語 ソ ース プ ロ グ ラ ム
翻 訳 プ ロ グ ラ ム
prolo9、 言 語 に 翻 訳 後 プ ロ グ ラ ム
実 行 時 支 援 プ ロ グ ラ ム
.1
prologKABA
〔図1〕 処 理 系 の 構 成
eval̲wff(or{X,YD'一!,{eva1 ̲wff(X};eゾa1̲wfF{YD.
eval ̲wff〔and(X,Y))一!,eva1̲wff{X},evaLwff{Y).
evaLwffωot(XD‑!,nOO(Xl.
evaLwff{X)‑X.
For ̲any̲element̲of〔E,[setlEs1,Wff):一
!,for ̲any̲element』of民(E,Es,Wff).f or̲any̲element̲of(E,set{Sys},Wff)=‑
get̲set̲from̲system{Set,Sys), for ̲any̲element̲of{E,Se亡,Wff).
for̲any̲element̲ofl{E,n,Wff}。
for ̲any̲element̲ofI{E,[EL】,Wff):一 ロot(evaLwff{Wff}), ,!,fai且.
for ̲any̲element̲of1〔E,LIDomain1,Wff)=‑
f。 ・̲・ ・y̲・1・ment̲・f1(E・D・mai・,Wff)・ .
for ̲some̲element̲of(E,lsetlEs1,Wff)=一
!,for ̲some̲element̲of1〔E,Es,Wff)。
fgr ̲some̲el㎝ent̲of{E,set{Sys),Wff}1‑
、get̲set̲from̲system(Set,Sys),
・for ̲some̲element̲of{E,Set,Wff).
for ̲some̲e見ement三 〇f皇 【E,口,Wff)=一
!,fai1.
for ̲some̲element̲of且{E,IEL1,Wff):一.' evalwff(Wff).
for ̲some̲element̲ofi(百,LIDomain1,Wff}=‑
for ̲some̲el㎝ent̲of童 〔E,Domain,Wff}.
〔譜1〕 論 理 式 評 価 プ ロ グ ラ ム
2.sorが 〔譜2〕 の フ ァ イ ル で あ る 。
ρ
組合せ計算のための代数処理 言語 の開発
define{function,name ̲is{intersect量on(R,X,Y}), arguments(【
outPUt(R):type(set}, 1nput{X};type(set)check, input̀Y):type{set}check1}, program{1
重s ̲a̲set̲oflR,E,.
,is̲an̲elemeht̲of(E,X)and且s̲an̲e且ement̲of(E,Y)}D}.
、def重ne(set,
define(
name is(setN},la,b,c1〕.
binaryoperation, 璽*●:τsetN
,setNI suchthat{〔
{a,a)一 一,a,
(b,a)r層 》b,
{C,a)一 一・C,
}.
name置S̀OP1}, 鴨噌♪setN
,
{a,b}r刷 》b,
(b,bl‑一,c, (C,b}r‑♪a,
{a,C}ロ ー》C,
(b,c)一 一>aジ (c,c)一 ゆbD
definelsystem,sys1, dehne(
deflne(
{setN,OPn )●
funct重on,unity ̲of{Unity,Group), arg㎜ents(l
output(Unlty}:type(element ̲of{se匡(Group}Dcheck, 1nput(GroμP}=type(systemlchecK
program(l
for ̲so無e̲eiement̲ofIUnity,set(Groupl, for ̲anyelement̲of(X,set(Group},τ
eva1 ̲on{R,U只ity*X,Group)aud(R冨X}l and (evaLon{L,X*Unlty,Group}and(L=X}〕
Unity ̲C且ause=・ ・ 【,;一 ㌧unity̲of(Unity,Group),U, asserta(Unity ̲C重ause)D}
.
Il,
D,
funcUQn,iuverse ̲Qf̲Qn([uverse,X,Group}, argumenしS{l
in̲out{Inversel:』type(element̲of{set(GroupD〕check, in ̲out{X):type(element̲of{set(Group)Dcheck,
input〔Group):type(system}check!1}, program(【
unltyof(Unity,Group}, evalδn{Unity,Inverse*X,Group), eva1一 〇n〔Unity,X*Inverse,Gro凹P}D}。
〔譜2〕 代 数 処 理 言 語 に よ る ソ ー ス プ ロ グ ラ ム
,
80 商 学 討 究 第36巻 第4号
藍ntersecUon⊂R ̲7,X̲7,Y̲71:■ コs̲type⊂ 興̲?,「setl,重8̲type⊂Y̲7,set}, setof{E7,evalwff〔ls ̲an̲e且 ㎝ent̲of{E̲7,X̲71andis̲an̲eiement̲of{E̲7,Y̲7D, 刷L47LR二7冨IsetTW」471.
setN⊂.Iset,a,b,cD.,
op1{b互nary ̲operation,声:18etN,setNト ー,setN}。
OPI⊂a*a,al. ,
op1⊂a宰b,b}.
。P1⊂a零c,c}.「 ・
op1⊂bホa,b,. .
op1{bホb,c}..
OP1⊂bホc,a}.
OP且 ⊂c事a,c,.
op1⊂c宰b,a}.
op1{cホc,b,。
・
syslllsystem,ISet̲19,(lplln=‑setN{Set ̲191. .
1
¥識 畠幽 謡 譲 膿 シ上烈1』 認1}§;1二 冨51P?llδ㌍ ・[Set‑30L1‑301Lsyst㎝L
。f{U,set⊂lsyst㎝,ISet30L1 ̲30丁1丁,evaL叩 〔U,Unity̲7*X̲7,for̲a氾y̲e且㎝ent
l:多:溜:1§::=181三1‑18ヨ翻i匙;:矧 癖vaLo"(り ・脚"'ty‑7・
9器 認 紘 灘31了 鷺 調 審畿1}i盤 更ラ!§:1=§8}71‑30m・り・
inverseof ̲on⊂Inverse̲7,XL7,【syst㎝,[Set̲301̲1̲3011}=‑istype{[syStem,
1§:ヒ灘Tllll:畿 留1二槻 琴丁?露 羅 乙1蜀豊=1ま〒1丁1呪⊥39m・
eval̲on{Un亘ty̲7,U零lnΨerse̲7,lsyst㎝,[Set̲30̲1̲301D,' is̲an̲e1㎝ent̲of{1nver3e̲7,Set̲30},且8̲an̲e且ement̲of{X̲7,Set̲301.・
〔譜3〕 〔譜2〕 の翻 訳 結 果
「
了el.llm。 、h.P円.
lel‑m。,、{ls㎝,,。 、.s。,・}
*compl艮ed=
寧compiled:
宰compHed=
*compi且ed=
零complled:
零comp童 且ed:
*ホ*endofcompning
***ObjeCt .
コ
intersect重on13 setN/1 0P塵 ノ2 sys111 unity ̲of/2i
nve『seofon/3一 一
sample2.30r isloaded
噛
lel.sy、 、⊂,).
S電[syst㎝,llset,a,b,c!,OPUI
〒el‑、y、11,い 。、、y.。,〔。,、}.
u需a,
S階lsyst㎝,llset,a,b,c1,0Pl11
了el.sy、11、},、̲se。,。 一 一。",、,、1.
1冒C,
S置lsyst㎝,llset,a,b,cl,OP111 yes
3帥,math.obj
℃
層
〔実 行 例 〕 〔譜2〕 の 翻 訳 と実 行 例
《 ま と め》
〔譜 ・2〕と 同 じ 内 容 を 直 接prolog言 語 で 書 く こ と は で き る が,そ の 内 容 に
脚
組 合せ計算 のための代数 処理言語の開発 8■
つ い て見 通 しが悪 い。 〔譜2〕 の表 現 法 に十 分 で は な いが 満 足 して い る。 不 満 が残 って い る所 は.す べ て を述 語 に翻 訳 す る た め に,本 来 関 数 のつ も りが,述 語 表 現 に な って い る点 で あ る。 この点 は,翻 訳 をprologの 節 にせ ず,prolog' の 項 に して,こ の 項 を イ ンタ プ リー トす る方 式 を 採 れ ば改 善 で き る と考 え て い
る。 そ うす れ ば,〔 譜2〕 もす っ き り した もの に な る で あ ろ う。
今 回 の テ ーマ の,具 体例 を与 え て そ の上 で,細 部 計 算 をす る と い う目 的 は達 成 され た 。 しか し,演 算 系 が群 や 体 に 限 られ,そ れ らの合 成 の方 法 が 提 供 さ れ て いな い。systemの 合 成 を一 貫 した方 式 で 行 な え るよ うにす る研 究 が今 後 の 課 題 で あ る と考 え て い る。
4.参 考 文 献
〔1〕Biggs,N.L.,White,A.T.,PermutationGroupsandCombinatorial structures,CAMBRIDGEUNIVERSITYPRESS,1979.
〔2〕佐 々 木 建 昭 ・元 吉 文 男 「数 式 処 理 」,数 学 の た め の コ ン ピ ュ ー タ シ ス テ ム,別 冊 数 学 セ ミナ ー,日 本 評 論 社,1985年.
〔3〕米 田 信 夫 「数 学 向 き 算 譜 言 語 」,同 上.
〔4〕荻 野 ・桜 川 ・柴 山 「PrologKABAReferenceManual」,岩 崎 技 研 工 業 株 式 会 社,1984年.
