Logic is one of the fundamental axioms of the universe. We assume logic is true and consistently applies everywhere throughout the universe. This "rewriting expressions" thing is just a symbolic representation of logic. It is not logic in itself. The symbolic representation of logic by writing down "expressions" works because logic is a inherit property of our universe and since you are writing those "expressions" in that same universe, it works.
There is no way to prove or verify logic is consistently real. We just recursively assume logic is real. We observe it to be real and assume that the observation will consistently apply across all time and space.
Another thing that I should mention that is an axiom of our universe is probability. WE have no way of knowing why rolling dice or random variables follow the rules of probability. These are just arbitrary rules and we assume that they're consistently true about our universe. Logic along with probability are two things that we have zero methodology of verifying the veracity of but we just assume these two things are fundamental properties of the universe.
A more elegant way to look at it is to just assume probability is the foundational axiom of our universe. Logic is just a special case of probability where all causal connections are 100%. Of course given inherit unreliability and limited knowledge of all things we never actually see or can verify 100% causality on anything. This effectively limits logic to mathematical and axiomatic games while science is the only available tool for the real world.
Science is a whole different beast. Given the assumptions that probability is real and that logic is real, science is an attempted methodology to verify theorems or statements about the universe using the axioms of probability and logic.
For example Newton guesses that a ball should travel a certain distance according to his made up laws of motion. Using science we perform several experimental observations of moving a ball and statistically correlate to a certain degree that yes the ball does indeed move according to newtons laws of motion. This is what science is. It is making a hypothesis and using statistics to sort of verify it. The term "sort of" is key here because science is limited to the fact that it can never prove anything.
One thing to note here is that EVEN when we assume logic and probability is true, science is unable to prove anything is true. You can make 10,000 observations about newtons law, it proves nothing because at any point in time a new observation can render the entire hypothesis as false. Thus falsification is possible with science [1] but proof is impossible. Proof is the domain of mathematics and logic games and cannot exist in the real world due to limited knowledge.
This is not some pedantic philosophy I'm making up. This is foundational to a true understanding of what science and logic is. To quote Einstein:
"No amount of experimentation can ever prove me right; a single experiment can prove me wrong."
There are a lot of intelligent people who don't understand the true depth of the above quote. But if you get it, then you truly understand what science is, and the differences between science and logic. Obviously both the OP and the parent poster don't fully get it... by combining logic and science into one thing and calling it the "science of the possible" it shows that they don't have a clear delineation of the two terms. Most people think of science as some kind of fuzzy "technical study" of a topic. No. This is wrong. There is a clearer definition of science that separates it from logic and mathematics.
[1] Note that technically total falsification is also impossible. Inherit unreliability of observation tools and limited knowledge makes it so that no observation can be 100% reliable. Thus even falsification is technically limited to the domain of logic and mathematical games.