Daniel Lewis
CSC165 A3
1)
Claim S1: for all x in R, ceil(x) = -floor(-x)
Proof:
Let x be an element of R //x arbitrary
Let (y = floor(-x)) be an element of Z //y specific
So y <= -x //definition of floor(-x)
Therefore -y >= x //times -1
And for all w in Z, w <= -x -> w <= y //definition of floor(-x)
So for all (-w) in Z, -w >= x -> -w >= -y //times -1
Substituting z = -w
Then for all z in Z, z >= x -> z >= -y
And since -y is an element of Z //Z closed under multiplication
Therefore -y is an element of Z /\ -y >= x
/\ for all z in Z, z >= x -> z >= -y
Thus -y = ceil(x) //from above
Thus -floor(-x) = ceil(x) //substitution
Thus for all x in R, -floor(-x) = ceil(x) //x is arbitrary
2)
Claim: In the two dimensional array S[m][n], S[2][5] = 9
Proof:
Let a be an element of D intersect {8, 3, 6, 7} //#s in row 2
Case 1: S[2][5] = a
S[2][1] = 8 //diagram
S[2][4] = 3 //diagram
S[2][6] = 6 //diagram
S[2][8] = 7 //diagram
Since S[2][5] = S[2][1] \/ S[2][5] = S[2][4] \/ S[2][5] = S[2][6]
\/ S[2][5] = S[2][8] //def'n a
Then 5 = 1 \/ 5 = 4 \/ 5 = 6 \/ 5 = 8 //R2 -><-
So S[2][5] ~= a //assumption leads to contradiction
So S[2][5] is not an element of D intersect {8, 3, 6, 7} //definition
//of a
Let b be an element of D intersect [1, 6] //#s in columns 4 and 6
Case 2: S[2][5] = b
S[1][4] = 1 //diagram
S[2][4] = 3 //diagram
S[3][4] = 2 //diagram
S[1][6] = 5 //diagram
S[2][6] = 6 //diagram
S[3][6] = 4 //diagram
Since ceil(1 / 3) = ceil(2 / 3) = ceil(3 / 3) = 1 //ceil(row / 3)
/\ ceil(4 / 3) = ceil(5 / 3) = ceil(6 / 3) = 2 //ceil(column / 3)
/\ (S[2][5] = S[1][4] \/ S[2][5] = S[2][4] \/ S[2][5] = S[3][4]
\/ S[2][5] = S[1][6] \/ S[2][5] = S[2][6] \/ S[2][5] = S[3][6])
//definition of b
Then (2 = 1 /\ 5 = 4) \/ (2 = 2 /\ 4 = 5) \/ (2 = 3 /\ 5 = 4)
\/ (2 = 1 /\ 5 = 6) \/ (2 = 2 /\ 5 = 6) \/ (2 = 3 /\ 5 = 6) //R4
//-><-
So S[2][5] ~= b //assumption leads to contradiction
So S[2][5] is not a element of D intersect [1, 6] //definition of b
Therefore S[2][5] is not an element of (D intersect {8, 3, 6, 7})
union (D intersect [1, 6]) //cases
//1 & 2
Then S[2][5] is not an element of D intersect [1, 8] //union operation
But there exists k in D, S[2][5] = k //R1
So S[2][5] = D - (D intersect [1, 8]) = 9 //only element in D not ruled out