Human intelligence is based on language.
You can't have conscious, reflective "faith" or "belief" without language.
Therefore both faith and intelligence "evolved" at about the same time. So did inductive logic. ("If such-and-such is true, so-and-so should be true too.")
Deductive logic, however, took millennia.