17. 問題1 事例の生成
? sig による集合及び関係の定義,pred 及びrun
による事例生成を試してみる.
– 以下の例で,スコープ(事例の探索範囲)が1(各シグネ
チャに含まれる要素数が高々一つという意味)の場合,
2つの事例が生成された.
? 実は,多重度(multiplicity)のキーワードが隠れている
– “f: B” という記述は“f: one B” の省略形
? Aのインスタンスが一つだけ,という事例は導出されない
? 問題:スコープを2としたら何通りになるか?
sig A{ f: B}
sig B {}
pred show {}
run show for 1
事例1 事例2
A0
B0
B0
f
事例3
A0
18. 答え:7通り
A
B
B
f
対象にしない
A
B1
f
B0
B1 B0
A1
B1
f
A0
B0
f
A1
B
f
A0
f
A0
B1
f
A1
B0
f
A0個,B0個A0個,B1個A0個,B2個
A1個,B0個A1個,B1個A1個,B2個
A2個,B0個A2個,B1個A2個,B2個
あり得ない
20. 部分集合の定義
? extends による部分集合の定義
– 右の例ではA1, A2 はA の部分集合.
– A1とA2 は共通部分を持たない
– A = A1 + A2 とは限らない
? A のシグネチャ定義でabstract をつけ
ると,A=A1+A2 となる.
? 一つだけの要素からなる集合
– シグネチャ定義の先頭にone をつ
けると,一つの要素を含む集合とな
る
? in による部分集合の表現
– extend の代わりにin で部分集合を
定義できる
? 定義された部分集合同士は共通要素を持
ち得る
sig A {}
sig A1 extends A {}
sig A2 extends A {}
A
A1 A2
sig A {}
sig A3 in A {}
sig A4 in A {}
A
A3 A4
21. 問題2
? 以下の例では,いくつの事例が生成されるか
– 2つのrun文の結果の違いは何か?
abstract sig A{ f: B}
sig A1 extends A {}
sig A2 extends A {}
abstract sig B {}
sig B1 extends B {}
sig B2 extends B {}
pred show {}
run show for 2
run show for 1 A1, 1 A2, 1 B1, 1 B2
26. 推移的閉包(2)
? 関係r の閉包
– r を部分集合としてもち,かつ,ある性質(反射的,
推移的など)を持つような最小の関係
? r の推移的閉包^r は次のようになる
^r= {(e,a), (e,d), (e,b), (a,d), (a,b), (c,d), (c,b),
(d,b)}
e a d b
c
29. 関係の多重度
? 一般形式r: A m -> n B
– 読み方:「Aの各メンバはBのnメンバに対応し,Bの
各メンバはAのmメンバに対応する」
– 次の意味に等しい
? all a: A | n a.r
? all b: B | m r.b
r: A -> one B A を定義域とする(全)関数
r: A -> lone B 定義域がAの部分関数
r: A one -> B 値域がBの単射的関係
r: A one -> one B 全単射(bijection)
r: A some -> some B 定義域がA,値域がBの関係
r: A lone -> some B Aの各メンバに一つ以上のBのメンバが対応し,Bの各メンバ
に高々一つのAのメンバが対応する
?A -> B で置き換え可能
30. 制約表現のためのキーワード
集合間の関係
P in Q P はQ の部分集合である
P = Q P とQ は(集合が)等しい
論理演算子
not ! ???ではない(否定, negation)
P and Q P && Q P かつQ (合接, conjunction)
P or Q P || Q P またはQ , (離接, disjunction)
P implies
Q [else R]
P => Q else R PならばQ ,PでなければR (含意, implication, 代替,
alternative)
P iff Q P <=> Q P ならばQ かつQ ならばP (両含意, bi-implication)
量化(quantifier)
all すべての
some 存在する
no ない
lone 高々一つ
one 厳密に一つ
32. 記述を楽にするための記法
? let というキーワードを利用して,繰り返し使われ
る表現や長く複雑な表現を簡略化する
? 例
all a: Alias | let w=a.workAddress |
a.address = if some w then w else a.homeAddress
33. 記号の優先順位
~ * ^
.
[]
:>
<:
->
&
++
#X
+ -
<< >> >>>
no X some X lone X one X set X seq X
in = < > <= >= !in != !< !> !<= !>=
!
&&
=> => Else
<=>
||
let all a:X|F no a:X|F some a:X|F lone a:X|F one a:x|F sum a:x|F
優先順位高
優先順位低
36. 行事及び買ったもの
abstract sig Event {}
one sig GraduationCeremony extends Event {} // 卒業式
one sig TravelingAbroad extends Event {} // 海外旅行
one sig InitiationCeremony extends Event {} // 入社式
one sig FlowerViewing extends Event {} // 花見
one sig Hiking extends Event {} // ハイキング
abstract sig Item {}
one sig Shoes extends Item {} // 靴
one sig Handkerchief extends Item {} // ハンカチ
one sig Shirt extends Item {} // シャツ
one sig Slacks extends Item {} // ズボン
one sig Camera extends Item {} // カメラ
37. 人
abstract sig Person {
event: Event,
item: Item
}
one sig Tanaka extends Person {}
one sig Takeuchi extends Person {}
one sig Ishida extends Person {}
one sig Kasai extends Person {}
one sig Aoyama extends Person {}
// 参加した人は皆,一つの行事に参加し,一つのものを買っている.
// 参加した行事と買ったものはそれぞれ異なる.
fact {
all p1, p2: Person | p1=p2 implies p1.event = p2.event else p1.event != p2.event
all p1, p2: Person | p1=p2 implies p1.item = p2.item else p1.item != p2.item
}
38. fact による制約記述と事例解析
// 田中さん「私はシャツを買いました」
fact {
Tanaka.item in Shirt
}
// 竹内さん「私は花見に行く前にズボンを買いました」
fact {
Takeuchi.item in Slacks
Takeuchi.event in FlowerViewing
}
// 石田さん「私ではありませんが,入社式に行った人は靴を買ったそうです」
fact {
all p:Person | p.event in InitiationCeremony implies p.item in Shoes
Ishida.item not in Shoes
Ishida.event not in InitiationCeremony
}
// 残りの話は省略(課題)
pred show {}
run show
41. 担当日,担当者
// 順序関係を表現するためのライブラリを利用
open util/ordering[Day]
// 担当日.メインとサブがいる.
sig Day {
main : Person,
sub: Person
}
// 担当者.メインとなる日とサブとなる日がある.
abstract sig Person {
mainDays : set Day,
subDays: set Day
}
// それぞれの職員.
one sig PersonS extends Person {}
one sig PersonO extends Person {}
one sig PersonW extends Person {}
42. ルール
// いろんなルール
fact {
// メインを担当する人とサブを担当する人が等しくなる日はない
no d: Day | d.main = d.sub
// すべての人は,メインとなる日にサブに割り当てられることはない
all d: Day, p: Person | d in p.mainDays implies d not in p.subDays
// dのメインがpならpのメイン担当日にdは入っている,そうじゃなければ入ってない
all d: Day, p: Person |
p in d.main implies d in p.mainDays else d not in p.mainDays
// dのサブがpならpのサブ担当日にdは入っている,そうじゃなければ入ってない
all d: Day, p: Person |
p in d.sub implies d in p.subDays else d not in p.subDays
// dのメイン担当者がpならpはdのサブ担当者ではない
all d: Day, p: Person | p in d.main implies p not in d.sub
}
// すべての人の担当日数の差は1日以内
fact {
all p1, p2: Person | #p1.(mainDays+subDays) - #p2.(mainDays+subDays) =< 1
}
43. ルール
// 一日目のメインはO が担当
// 二日目のメインはW が担当
// 三日目のメインはS が担当
fact {
first.main in PersonO
first.next.main in PersonW
first.next.next.main in PersonS
}
// 続けて2日間メインを担当しない
fact {
all d: (Day-last) | d.main not in (d.next.main+d.next.sub)
}
44. 事例チェック
// 事例の解析(6日間のコースの場合)
run {} for 3 but 6 Day
// 事例の解析(4日間のコースの場合)
run {} for 3 but 4 Day
// 日付と担当者の関係は,担当者と日付の関係に等しい
// 図を見ればそれらしいことがわかるが,
// すべての場合でそうなるかを確認.
assert mainEqualmainDay{
~mainDays = main
~subDays = sub
}
check mainEqualmainDay for 3 but 6 Day
47. 色,信号機,合流点
// 色の定義
enum Color {Red, Yellow, Green}
// 正しい色の順番を示す関係,を返す関数
fun colorSequence: Color -> Color {
Color <: iden + Red->Green + Green->Yellow + Yellow->Red
}
// 信号機の集合
sig Light {}
// 信号機の状態.
sig LightState {color: Light -> one Color}
// 合流点.
sig Junction {lights: set Light}
48. 制約の記述
// 赤の信号機の集合を返す関数
fun redLights [s: LightState]: set Light { s.color.Red }
// 合流点に存在する信号機のうち,赤でないものは高々1つ.
pred mostlyRed [s: LightState, j: Junction] {
lone j.lights - redLights[s]
}
// 信号機の変化
pred trans [s, s': LightState, j: Junction] {
// 合流点に存在するライトのうち,色が変化するものは高々一つ
lone x: j.lights | s.color[x] != s'.color[x]
all x: j.lights | let step = s.color[x] -> s'.color[x] {
// 合流点に存在する信号はすべて,決められた色の変化をする.
step in colorSequence
// ある信号機が赤から赤以外へ変化する場合,
// 変化前では同じ合流点内のすべての信号機は赤である
step in Red->(Color-Red) => j.lights in redLights[s]
}
}
49. 事例の確認
// 可能性のある組合せを表示する.
run {} for 3 but 1 Junction
// 有効な信号変化の事例を表示してみる
run trans for 3 but 1 Junction
// 信号変化のうち,特定の部分だけを取り出してみる.
pred show[s, s': LightState, j: Junction] {
// 信号機が変化する条件を満たす
trans[s, s', j]
// 合流点に存在する信号機の数が2つ以上
all j: Junction | #(j.lights) >= 2
// 合流点に存在する信号機のうち,
// 少なくとも一つが赤から別の色に変化する場合
some x: j.lights| s.color[x] -> s'.color[x] in Red -> (Color-Red)
}
run show for 3 but 1 Junction
50. 事例の表示
? run show for 3 but 1 Junction の表示例
– 操作trans により状態がLightState2 から
LightState1 へ変化したことを示している