In logic, there is an important concept known as an "axiom", which is defined as "a statement accepted as true as the basis for argument or inference". These are elements that are not defined logically, rather they are simply accepted as true in and of themselves, and they are the foundation upon which any logical conclusion is built upon.
If an axiom cannot be proven in and of itself, its acceptance is entirely a matter of belief; this has nothing to do with religion, simply a concession that we can't (or don't yet) know everything, but we need to start somewhere.
This is entirely compatible with Islam: One major concept in Islam, one of the pillars of Imaan, is acceptance of al-Ghaib — the Unseen — those things which are fundamentally unobservable and that we only know via revelation. These are things faithful Muslims simply accept as true, regardless of proof.
If logic leads you to a conclusion that is illogical or obviously untrue, that's not a failure of logic, that's a failure of one or more of the axioms you're working with, a failure of the foundation you built on. You just need to revisit your initial assumptions.
Muslims don't worship logic, we worship Allah who guides whosoever He wills to the truth. Ultimately, Allah either exists, or He does not, and whether His existence or His revelations are logically provable is irrelevant.
You either believe, or you do not.