- 8 Q Question 1 I 2 5 Ii Iii Iv 1 1 State Whether Each Of The Following Hoare Triples Are Valid Or Not 0 Xax 5 X 1 (24.67 KiB) Viewed 147 times
- 8 Q Question 1 I 2 5 Ii Iii Iv 1 1 State Whether Each Of The Following Hoare Triples Are Valid Or Not 0 Xax 5 X 2 (10.9 KiB) Viewed 147 times
- 8 Q Question 1 I 2 5 Ii Iii Iv 1 1 State Whether Each Of The Following Hoare Triples Are Valid Or Not 0 Xax 5 X 3 (22.34 KiB) Viewed 147 times
- 8 Q Question 1 I 2 5 Ii Iii Iv 1 1 State Whether Each Of The Following Hoare Triples Are Valid Or Not 0 Xax 5 X 4 (24.32 KiB) Viewed 147 times
- 8 Q Question 1 I 2 5 Ii Iii Iv 1 1 State Whether Each Of The Following Hoare Triples Are Valid Or Not 0 Xax 5 X 5 (25.58 KiB) Viewed 147 times
- 8 Q Question 1 I 2 5 Ii Iii Iv 1 1 State Whether Each Of The Following Hoare Triples Are Valid Or Not 0 Xax 5 X 6 (28.8 KiB) Viewed 147 times
- 8 Q Question 1 I 2 5 Ii Iii Iv 1 1 State Whether Each Of The Following Hoare Triples Are Valid Or Not 0 Xax 5 X 7 (16.49 KiB) Viewed 147 times
- 8 Q Question 1 I 2 5 Ii Iii Iv 1 1 State Whether Each Of The Following Hoare Triples Are Valid Or Not 0 Xax 5 X 8 (12.07 KiB) Viewed 147 times
- 8 Q Question 1 I 2 5 Ii Iii Iv 1 1 State Whether Each Of The Following Hoare Triples Are Valid Or Not 0 Xax 5 X 9 (19.97 KiB) Viewed 147 times
1.2 The following Hoare triple is invalid: (x > 0) x:=x-1 (x > 0). Change the Hoare triple to valid by i. defining a stronger precondition ii. defining a weaker postcondition iii. changing the program
1.3 Using the assignment axiom (9.2 of the textbook) determine the precondition for the following statements and postconditions. Where necessary, simplify the precondition i. ii. iii. iv. V. Precondition Statement X:=x+y x:xxy x :=x-y y := 0 -x X:=XX 2+3 Postcondition {x<2xy) {xx y = C) (x>2) {y <0^x#y] (x>1)
Question 2 Use the proof rules of Chapters 9 and 10 in RB as well as selected portions in Chapter 3 of Baber to derive preconditions for the following post conditions and program statements. Show all your working. 2.1 (2) i:=i+1; k:=k*2; j:=j-1 (i=j) 2.2 (?) while (0≤x≤3) do y := y*x; x:=x+1(x=4Ay=n!} 2.3 (?) if even(x)→x:=x-1 odd(x)-2:=2+yx (x20Az+y*x=a*b] fi //x is an even integer //x is an odd integer
2.4 (?) while 02x2-2 do x:=x-1 endwhile (x = -3) Hint: Rewrite the relevant statements into their guarded-command equivalents before calculating their respective preconditions. Question 3 Verify the following Hoare triples: 3.1 (x=y} if (x = 0) then x:= y + 1 else z:= y + 1[(x=y+1) V (z=x+1)] 3.2 {[y>4} if (2>1) then y:= y + z else y:=y-1 endif [y > 3) 3.3 (3≤/x/≤4) ifx<0 then y=-x else y :=x endif (2 ≤ y ≤4) Hint: First rewrite each if-then-else statement as its guarded-command equivalent before calculating a new precondition.
Question 4 4.1 Suppose there are two integer values and p. Calculate what must be assigned to p to maintain invariant the sum i + p under the increment of /by 1. In other words, calculate Xsuch that for arbitrary C (i+p=C) ip:=i+1, X (i+p=C) 4.2 Suppose there are three program variables a, band z. Calculate the assignments to a so that the following invariant is maintained: 2+axb=C In other words, calculate X such that {z+vxb=C} aa!=a+bX{z+axb=C) 3
Question 5 5.1 Evaluate the following summations: i. (k: 1 ≤k ≤ 12:k + 1) ii. (En: 1 ≤ns 4:3n-1) iii. (21,j:0 ≤i<j ≤8 Aeven.j Aodd.j:i+j) 5.2 Evaluate both sides of the following equations and state whether they are true or false 1. Σ₁5(2)/² = 10(2" - 1) ii. Σ|=1(3n - 2) = n(3n-1) 2
Question 6 6.1 6.2 Prove that 2 < (n + 1)!, for n ≥2. Prove that, for any natural number n, i. (k:0 ≤k<n: 2k) = 2" - 1 ii. 13 + 23 +33 + + ³ = n²³(n + 1)²
Question 7 For each of the loop invariants given below, determine if it is a possible loop invariant for Precondition: (x20) (x>0} y = 1; y, z:= 1,0; z=0; do (z!=x)->zy:=z+1, y z while (z!=x) { od 2=2+1; (y=x!) y = y*z; } Postcondition: (y=x!) a. ¬(z=x) b. (z≤x) c. (y=z!) d. (y=x!) e. ((2≤x) A (y=z!))