The most basic principle of logic is, on most views, the law of non-contradiction. It is considered to be a presupposition of rational discourse. When you say "the cat is no the mat" you are implicitly denying that the cat is not on the mat, otherwise you're just making noises.
Now, you say that if God is omnipotent, and then put a bunch of noise after it, and call that true. So, omnipotence has to be defined in terms of what is coherently possible.
But what happens to the definition of omnipotence if you buy into paraconsistent logics?