Proving with floor and ceiling functions formally for computer scientists

tags:

logic

views:

315

answers:

+2 Q:

Proving with floor and ceiling functions formally for computer scientists

Hi there,

This is indeed a sort of exercise I have to complete but a little direction would be wonderful. I have to determine if I should prove or disprove these three statements...

The definition I have of floor and ceil are pretty basic. I wont bother placing them here. Once I determine if they need proof/disproof I have to get to work on actually making that happen.

My hunch is that the first needs a disproof because it's not the case that all X and Y floor and ceiled equal are less than the floor of them multiplied. It seems too strict.

The second statement seems less strict. The floor times the ceil are greater than the floor xy...that's very much possible.

The third, also seems possible though most of the time I bet they would be equal in value.

Wondering if I'm on the right track. Sorry for my notation, I didn't want to use formal mathematical symbols. I'll have to write out a formal and rigorous proof for each.

+2 A:

Counter-example: x = 2.9, y = 2.9; ⎣x⎦ = 2; ⎡y⎤ = 3; ⎣xy⎦ = 8.
Consider x = 2.4, y = 2.4, but ∃x ∃y ⎣x⎦.⎡y⎤ ≥ ⎣xy⎦ isn't a very strong statement.
Counter-example: x = 2, y = 2; ⎣x⎦ = 2, ⎡y⎤ = 2, ⎡xy⎤ = 4.

I didn't have to work all that hard to find appropriate examples.

Jonathan Leffler 2009-11-12 04:22:38

Hi there, thanks for laying it out like that. Makes a lot of sense! I have this other statement: For all X, for all y, floor(x) * floor(y) <= floor(xy) that I'm trying to workout. The result I got with x = 2.4 and y = 2.4 is a considered example. It seems like in all cases flooring both x and y and flooring their product make them equal. Now I have to write a proof on it...examples would be wonderful Jonathan.

Mike 2009-11-12 14:26:35

For integers, ⎣x⎦⎣y⎦ = ⎣xy⎦; clearly, for fractional bits, the RHS will be larger, and might exceed the LHS.

Jonathan Leffler 2009-11-12 16:39:33

+3 A:

A great book that will make you extremely proficient at working with floors and ceilings, as well as several other useful things besides, is Concrete Mathematics: A Foundation for Computer Science by Graham, Knuth and Patashnik. It's a lot of fun, you should read it!

For your specific questions, there are simple examples/counterexamples for each:

"For all x, for all y, floor(x) * ceil(y) <= floor(xy)" — Just take x=1, and y not integer: then it's saying that ceil(y) ≤ floor(y), which is obviously not true.
"Some X, Some Y, floor(x) * ceil(y) >= floor(xy)" — Again, take x=1, and any y: then it's saying that ceil(y) ≥ floor(y), which is true.
"For all X, for all Y, floor(x) * ceil(y) > ceil(xy)" — Take x=1 again! It says that ceil(y) > ceil(y), which cannot be true. You can in fact get strictly less, by taking e.g. x=0.99 and y positive: then the left-hand-side is 0, while the right is positive.

ShreevatsaR 2009-11-12 04:39:59

Thanks for the book suggestion. I have a similar text, though it's horrible. Thanks for the recommendations. Those ones were actually fake samples I came up to see if I can get the real question. Haha. I understand the methodology to solving it though.How about: For all X, for all y, floor(x) * floor(y) <= floor(xy).If I take x = 2.4 and y = 2.4 then 2 * 2 <= 4 is true. My proof structure would in essence look likeAssume xeQ+ # generic positive rational numbers Assume yeQ // Argue floor of values always equal to floor of product.

Mike 2009-11-12 14:09:16

What you said is not a proof: to prove that something *is* true for all x and y, giving an example won't do. But you can prove it as follows: ⎣x⎦≤x, ⎣y⎦≤y, so ⎣x⎦⎣y⎦≤xy. Now, as ⎣x⎦⎣y⎦ is *some* integer less than or equal to xy, and ⎣xy⎦ is the *largest* integer less than or equal to xy, we have ⎣x⎦⎣y⎦≤⎣xy⎦. More generally, the "methodology" would be to write x=⎣x⎦+{x}, y=⎣y⎦+{y}, where {x} and {y} are the fractional parts, and work it out by hand: xy=(⎣x⎦+{x})(⎣y⎦+{y})=(⎣x⎦⎣y⎦ + ⎣x⎦{y} + {x}⎣y⎦ + {x}{y}), so its floor is ⎣xy⎦ = ⎣x⎦⎣y⎦ + ⎣(⎣x⎦{y} + {x}⎣y⎦ + {x}{y})⎦ ≥ ⎣x⎦⎣y⎦.

ShreevatsaR 2009-11-12 15:37:27

And in general, the two are not equal: e.g. take x=100.9 and y=100.9, you have ⎣x⎦⎣y⎦=100×100=10000, while ⎣xy⎦=⎣10180.81⎦=10180, much larger. :-) If all this is mystifying, read the Concrete Mathematics book — it's very clear and not at all horrible!

ShreevatsaR 2009-11-12 15:42:08

ansaurus

tags:

views:

answers:

Proving with floor and ceiling functions formally for computer scientists

related questions