:
B
(11)
B
2010
B
•
•
•
•
B
• B
typing
• B
•
•
Formal Methods: Software Development in B Qiu Zongyan (May 18, 2010) 1
B
B
Hoare Dijkstra 1960
1970
• invariant
• variant
B
“”
B
Formal Methods: Software Development in B Qiu Zongyan (May 18, 2010) 2
while
for repeat-until while
B while while
while
while
“” while
while
while E do S
E S
S
1. E
2. E “”
3. E “” S
S 1
Formal Methods: Software Development in B Qiu Zongyan (May 18, 2010) 3
B
B
WHILE E
DO S
END
• E “”guard
• E skip
• E s S s
s
• S
S
WHILE TRUE DO skip END
x := 1; WHILE x<10 DO WHILE x>4 DO skip END; x := x +1END
Formal Methods: Software Development in B Qiu Zongyan (May 18, 2010) 4
“” “”“” “”
a b
x := a;
y := b;
prod := 0;
WHILE x>0
DO
IF
x mod 2=1THEN prod := prod + y END;
x := x/2;
y := y × 2
END
“”
prod = a × b
B
Formal Methods: Software Development in B Qiu Zongyan (May 18, 2010) 5
S
s = s
0
,s
1
,...,s
n−1
,s
n
= s
t
[S]s
i
= s
i−1
i =2,...,n
s s
t
“”Hoare, 1969
“”
I S
S S S
I
Formal Methods: Software Development in B Qiu Zongyan (May 18, 2010) 6
TRUE “”
B
S I
•
s
0
I
• I s E s S
S I
I E S I
∀
v.(I ∧ E ⇒ [S]I)
v I
Formal Methods: Software Development in B Qiu Zongyan (May 18, 2010) 7
Q
Q E I
Q
∀
v.(I ∧¬E ⇒ Q)
prod = a × b
x = a ∧ y = b ∧ prod =0 I
I I ∧¬(x>0) prod = a × b
x x := x/
2 ¬(x>0) x =0
prod + x × y = a × b
Formal Methods: Software Development in B Qiu Zongyan (May 18, 2010) 8
prod + x × y = a × b
• prod =0 x × y a × b
•
– x x y (x/2) × (y × 2) = x × y
– x prod y x y
(prod + y)+(x/2) × (y × 2) prod + x × y
• prod + x × y = a × b ¬(x>0) x =0
prod = a × b
B
WHILE INVARIANT
WHILE
Formal Methods: Software Development in B Qiu Zongyan (May 18, 2010) 9
评论2
最新资源