Proving with floor and ceiling functions formally for computer scientists

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.

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:

1. "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.
2. "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.
3. "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.

1. Counter-example: x = 2.9, y = 2.9; ⎣x⎦ = 2; ⎡y⎤ = 3; ⎣xy⎦ = 8.
2. Consider x = 2.4, y = 2.4, but ∃x ∃y ⎣x⎦.⎡y⎤ ≥ ⎣xy⎦ isn't a very strong statement.
3. 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.