How would one show the above

I have (at the moment) no idea.

or even build up a system on top of physical laws without using logic?

It's clear that such a demonstration needs to use some kind of logic, but I think that doesn't undermine the (possible) reduction: if you show that the (set of) logic available to a system depends on the physical laws, you have shown that our own logic is determined by our own laws. This would entail that (possibly) different laws would have granted us different logics. I'm fascinated for example by the fact that the concept of "second order arithmetical truth" (SOAT) is inacessible by effective finite computation, but there are space-times that allow for infinite computation (and so system inhabiting such a world could possibly grasp effectively SOATs).