114-20aa.1
COMP 114
Spring 2005
Written assignment 1 Answers (Stanat & Weiss, Chapter 2)
You are free to collaborate on this assignment, but write out your own answers and be sure you understand your answers. Similar questions will appear on the exams where collaboration will not be possible.
Do the following exercises
Part I, problems 1-32
Part II, Do problems 1-6, 7a and 7b
Do at least four functions in each of 7c and 7d (do one in each row and one in each column).
Be sure you understand the implication of this question.
Study the answers to 8 and 9 in Chapter 2. Be sure you understand.
Talk about 10. It is essential that you understand how quantifiers work on the empty domain.
Think about 11
COMP 114Name ______
Exercises for Stanat & Weiss, Chapter 2
These exercises are intended to develop your skill in reading and understanding simple assertions.
In each of the following, letters represent integer or real program variables. Translate each assertion to an appropriate boolean expression. Note that Java does not allow, for example, expressions such as 'x < y < z.' Give your answer in as simple a form as possible. Although Java does not support the implication operator, you can use P => Q in your answers as a shorthand for
(! P || Q). While they are equivalent, the shorthand form is a lot more illustrative of what’s intended.
Part I
1. x is equal to the smaller of y and z. (Hint: use Math.min)
x = Math.min(y,z) also (x == y & y <= z) || (x == z & z <= y)
2. 3 is not a divisor of x.
x % 3 != 0.
3. x is greater than y or x is less than z, and possibly both.
(x > y) || (x < z)
4. x is not the smallest value of x, y and z.
(x >= y) || (x >= z) also: !((x < y) & (x < z))
5. not both x and y are greater than z.
(x <= z) || (y <= z) also: !((x>z) & (y>z))
6. If x is not larger than y, then the value of w is 10. (This asserts (x <= y) implies (w == 10) )
((x<=y)) => (w == 10) also: (x > y) or (w == 10)
7. When x is less than y, then y is less than z, and when x is at least as large as y, then y is equal to w.
((x < y) => (y < z)) & ((x >= y) => (y == w)) also ((x >= y) || (y < z)) & ((x < y) || (y == w))
8. y is not even if x is even . (Hint: Use the mod (%) operation.)
x % 2 == 0 => !(y % 2 == 0)
9. x is not a divisor of y when y is a multiple of 3
(y % 3 == 0) =>!(y % x == 0) also (y % 3 == 0) =>(y % x != 0)
In the following, B and C are integer arrays. Assume the arrays and all variables have been declared and initialized so that all the following statements make sense. Variables used to specify subarrays (e.g., lo, hi, n, etc.) are all initialized and within the range of the array indices. Moreover, in any reference such as B[r...s], assume that r s+1. (Note that if r = s+1, then the expression B[r...s] denotes the empty array. If r > s+1, the expression B[r...s] is undefined.) Using the quantifiers defined in the chapter on assertions, express the following assertions formally.
Example: All the entries of B[0..10] are zero. (Ai: 0 <= i <= 10: B[i] == 0)
10. Some entry of B[lo...hi] is negative.
(Ei: lo <= i <= hi: B[i] < 0)
11. All entries in C[0...10] are equal.
(Ai,j: 0 <= i,j <= 10: C[i] == C[j))
12. Not all entries in C[0...10] are equal.
(Ei,j: 0 <= i, j <= 10: C[i] != C[j]) also: !(Ai,j: 0 <= i,j <= 10: C[i] == C[j])
- The two first entries of B[0...10] are zero. B[0] == 0 & B[1] == 0
14. The entries of B[0...2] are sorted in increasing order.
B[0] <= B[1] <= B[2]
15. The entries of B[0...100] are sorted in increasing order.
(Ai: 0 <= i < 100: B[i] <= B[i+1])
also (Ai,j: 0 <= i < j <= 100: B[i] <= B[j]) also (Ai,j: 0 <= i,j <= 100: (i < j) => (B[i] <= B[j]))
16. The entries of B[0...100] are all between low and high.
(Ai : 0 <= i <= 100 : low < B[i] < high) Note: 'between' is often ambiguous. This might have meant either < or <=
17. C[lo...hi] contains at least two zeroes. Hint: requires two variables.
Ei,j: lo <= i < j <= hi: C[i] == 0 & C[j] == 0) also: Ni: (lo <= i <= hi) : C[i] == 0) >= 2
18. Every value of B[0...k] occurs in C[r...s].
(Ai : 0 <= i <= k : (Ej : r <= j <= s : B[i] == C[j])) also (Ai Ej : (0 <= i <= k) & ( r <= j <= s) : B[i] == C[j]))
19. Each of the entries of B[low1...high1] is larger than any entry of C[low2...high2]
Ai,j : (low1 <= i <= high1) & (low2 <= j <= high2) : B[i] > C[j]
20. One value in B[0...100] is larger than all the others.
(Ei: 0 <= i <= 100: (Aj: 0 <= j <= 100 & j != i : B[i] > B[j]))
also (EiAj: 0 <= i ,j<= 100: (B[i] >= B[j]) & (B[i] == B[j] => (i == j)))
also (Ni: 0 <= i <= 100: B[i] == (Max k: 0 <= k <= 100: B[k])) == 1
21. The values in C[0...r] are all larger than the values in C[r+1...n].
Ai,j : (0 <= i <= r < j <= n) : C[i] > C[j]
22. The values stored in C[0...n] are successive powers of 2, beginning with C[0] == 20 == 1.
(Ai : 0 <= i <= n : C[i] == 2i)
23. Each of the integers 0 through n is stored in some location of the array C[0...n].
(Ai : 0 <= i <= n : (Ej : 0 <= j <= n : C[j] == i))
24. If any of the entries of B[0...n] is 0, then k == 1.
(Ei: 0 <= i <= n: B[i] == 0) => (k == 1) also (Ai: 0 <= i <= n: (B[i] = 0) => k = 1)
25 For B[0...n], whenever B[i] is equal to i, C[i] is 0.
(Ai : 0 <= i <= n : ((B[i] == i) => (C[i] == 0)))
26. The value of the variable named count is the number of zeroes stored in B[0...n] Hint: Use the quantifier 'N'
count == (Ni : 0 <= i <= n : B[i] == 0)
27. For 0 <= i <= n, the value of B[i] is the sum of the first i entries of C[0...n]
(Ai : 0 <= i <= n : B[i] == (Sj : 0 <= j <= i: C[j]))
28. The value stored in the variable named biggest is at least as large as any entry in B[0...k]. Hint: Use the quantifier 'Max'
biggest >= (Max i: 0 <= i <= k : B[i]) also (Ai : 0 <= i <= k : biggest >= B[i])
29. For every i from 0 to k, the value stored in B[i] is the number of occurrences of the integer i in the array C[0...n].
(Ai : 0 <= i <= k : B[i] == (Nj : 0 <= j <= n : C[j] == i))
30. The array A[0...100] has an entry that is larger than any of the entries of C[0...100]
(Max i:0 <= i <= 100: B[i]) > (Max i:0 <= i <= 100: C[i])
31. Each entry (except the last) of the array B[0...n] is a divisor of the next one.
(Ai: 0 <= i < n : B[i+1] % B[i] == 0)
32. Each entry (except the first one) of the array B[0...n] is the sum of all the preceding entries.
(Ai : 0 < i <= n : B[i] == (Sj: 0 <= j < i : B[j]))
Part II
Assume that all variables are integer variables and that all have been initialized.
1. In each of the following, what arithmetic relation (<,>,≤,≥) should replace each question mark to make the implication true? (In this question, and in general, your answer should be the strongest (most informative) one you can make. Thus, if < is correct, then ≤ will be considered incorrect.)
_____a.k ≥ 0 => [i < j => [k*i ? k*j]] ≤ (Would be <, but k can equal 0.)
_____b.k > 0 => [i < j => [k*i ? k*j]]
_____c.k < 0 => [i < j => [k*i ? k*j]]
_____d.k ≤ 0 => [i ≤ j => [k*i ? k*j]] ≥
2. True or false.
.
_____a.i < j == i+1 < j False
_____b. i < j+1 == i ≤ j True (Would not be true if variables were real instead of integer.)
3. Simplify the following expressions:
a.i ≤ j < i+1 i = j
b.even(k) & 2*(k / 2) = n] => k == n (Note: even(k) is true if and only if k is even)
true: The left side simplifies to k==n, hence the expression becomes (k==n) => (k==n) which is just true.
c.Simplify the following assertion about the variable k: 1 ≤ k ≤ m & q < k ≤ 100 & 1 < q < m
q < k ≤ min(m,100) (Alternatively, 1 < q < k ≤ min(m,100))
4. In each of the following pairs, circle the stronger assertion. The letter S appears beside the stronger assertion.
a. x < 6 Sx ≤ 6
b. x+y < 20x < 10 & y < 8 S
c.x - y == z Sx - z < y+6
5. Number the following predicates from 1 to 6 in order of decreasing strength, with 1 denoting the strongest:
4.P(x): x > 3
5.Q(x): x2 > 9
3.R(x): x > 3 & x < 7
2.S(x): x = 5
1.T(x): x > 3 & x < 3
6.V(x): x > 3 || x ≤ 3
Note that the weakest assertion is true; the strongest assertion is false.
6. Give an example of two predicates over x (similar to the ones in problem 5) such that neither predicate is stronger than the other.
There are many examples. One is the pair of assertions x < 10 and x > 1. Neither of these assertions implies
the other although they convey related information.. Contradictory assertions, such as x < 1 and x > 1, are similar.
Unrelated assertions such as x < 10 and y = 3 are also unrelated by 'strength' unless one of them is true or false.
7. a. Show that there are sixteen possible boolean functions with two operands by completing the following (sixteen) truth tables. The first has been completed; it specifies the function that maps all pairs of arguments to 0 (that is, false). (Life will be easier if you enumerate the functions in a logical fashion.)
x / y / f0 / f1 / f2 / f3 / f4 / f5 / f6 / f7 / f8 / f9 / f10 / f11 / f12 / f13 / f14 / f150 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 1 / 1 / 1 / 1 / 1 / 1 / 1 / 1
0 / 1 / 0 / 0 / 0 / 0 / 1 / 1 / 1 / 1 / 0 / 0 / 0 / 0 / 1 / 1 / 1 / 1
1 / 0 / 0 / 0 / 1 / 1 / 0 / 0 / 1 / 1 / 0 / 0 / 1 / 1 / 0 / 0 / 1 / 1
1 / 1 / 0 / 1 / 0 / 1 / 0 / 1 / 0 / 1 / 0 / 1 / 0 / 1 / 0 / 1 / 0 / 1
b. Which function is and? f1 Which is or? f7 Which is x => y? f13
c. The sixteen boolean functions are redundant in the sense that a small set of them can be used to construct the others. Two common sets that will generate all the functions are the sets consisting of and and not, and the set consisting of or and not. For example, if we have or and not, then and is superfluous since, for every value of x and y, x y = not(not x || not y). Show that all sixteen functions can be constructed using only and and not.
f0(x,y) == x ! x / f1(x,y) == x y / f2(x,y) == x & ! y / f3(x,y) == xf4(x,y) == ! x y / f5(x,y) == y / f6(x,y) == !(! (x ! y)
! (! x y)) / f7(x,y) == ! (! x ! y)
f8(x,y) == ! x ! y / f9(x,y) == ! (! (x y)
! (! x ! y)) / f10(x,y) == ! y / f11(x,y) == !(! x y)
f12(x,y) == ! x / f13(x,y) == !(x ! y) / f14(x,y) == ! (x y) / f15(x,y) == ! (x ! x)
d. Show that all sixteen functions can be constructed using only or and not.
f0(x,y) == !(x ||! x) / f1(x,y) == ! (! x || ! y) / f2(x,y) == ! (! x || y) / f3(x,y) == xf4(x,y) == !(x || ! y) / f5(x,y) == y / f6(x,y) == ! (! x || y) ||
! (x ||! y) / f7(x,y) ==x || y
f8(x,y) ==! (x || y)x / f9(x,y) ==! f6 / f10(x,y) ==! y / f11(x,y) == x || ! y
f12(x,y) ==! x / f13(x,y) ==! x || y / f14(x,y) ==! x || ! y / f15(x,y) ==x || ! x
A subset of functions such as and and not, or or and not from which all the others can be constructed is called a complete set. It turns out that the set consisting of and and or is not complete. But there are single functions such as not and (f14) that are complete.
10. a. Argue the following claim: The quantifier "for all" is based on the operation and, and consequently, since the identity value for and is true, the value of a universally quantified expression with an empty domain is true.
I is an identity for an operation ☺ if (I ☺x)==x for all x. For example, 0 is the identity for addition since (0+x)==x. Similarly, 1 is the identity for multiplication. We generally define combination of zero elements under an operation to be the identity for that operation. So the sum of no values is zero, and (although less common) the product of no elements is 1. True is the identity for logical and (&) since (true & x)== x. Hence we can claim that the logical and of no elements is the identity true. Same reasoning will work for logical or for which the identity is false.
b.Construct an analogous claim for any existentially quantified expression with an empty domain.
An existentially quantified assertion Ex:D(x):P(x) can be written as P(x1)||P(x2)||...||P(xn) where x1,x2,..xn is the domain D(x). So an existentially quantified assertion is really the logical or of some number of constituents. When the domain is empty, the existentially quantified assertion is the logical or of no elements. And by definition, that's the identity. The identity for or is false since (false || x)==x.
11. {P} C {Q} is a predicate of three variables defined to mean "the program C is partially correct with respect to the precondition P and the postcondition Q. The domain of the variables P and Q is the set of predicates; the domain of the variable C is the set of programs.
Each of the following assertions has a truth value (that is, each assertion is either true or false). For each assertion, give an assertion in English that is equivalent to the formal assertion, and state whether the formal assertion is true or false.
(A P : true : (A Q : true : (E C : true : {P} C {Q} )))
For an arbitrary precondition P and postcondition Q there exists a program C such that C is partially correct with respect to the precondition P and the postcondition Q. The assertion is false, as may be seen by setting the postcondition to false.
(A C : true : (E P : true : (E Q : true : {P} C {Q} )))
For an arbitrary program C there exists a precondition P and a postcondition Q such that C is partially correct with respect to the precondition P and the postcondition Q. This assertion is a formal statement of the claim that every program does something. The assertion is true, as may be seen by setting the pre and postcondition to true.
(A C, Q : true: {false} C {Q})
Any program C is partially correct with respect to the precondition false and an arbitrary postcondition Q. This claim is true
(A Q: true : (E P : true : (E C : true : {P} C {Q} )))
For any postcondition Q, there exists a precondition P program C and such that C is partially correct with respect to the precondition P and the postcondition Q. This claim is true; it can be satisfied by setting P to the value of Q and making C a program that does not change the state, such as the single assignment 'x = x;'