Je suis plutôt d'accord avec Ronin dans le sens où la logique formelle est loin d'être "naturelle" pour la plupart des humains.
Par contre, il existe une logique pratique, plus concrète et plus souple, que tous les humains ont, et celle-ci se construit en référence à une culture. Il existe certainement des traits généraux communs à toutes ces logiques (mais je ne suis pas anthropologue).
Néanmoins je sais que d'un point de vue cognitif, l'homme (indépendamment de sa culture) est aussi habile à détecter des régularités, à extraire schématiquement de l'information pertinente de son monde, et tous y cherchent des explications. Ces éléments de rationalité peuvent aussi bien déboucher sur diverses mythologies, sciences ou philosophies.
Un autre cas qui me vient en tête est celui de l'universalité de la grammaire générative de Chomsky (je crois que c'est encore débattable, mais ce semble plutôt bien établi aujourd'hui). Chacun aurait déjà en tant qu'humain une structure cérébrale propre à "accueillir" la grammaire de la première langue qu'il apprendra. La grammaire étant la logique de la langue, on aurait déjà un point à propos duquel une structure logique serait naturalisée chez l'homme. (Il faut rappeler qu'une grammaire formelle suffisamment élaborée est équivalente au modèle mathématique de l'ordinateur (une machine de Turing))
Donc l'homme aurait en lui des structures destinées à se modeler aisément sur une cohérence qu'il aurait perçue. Si cela est vrai pour le langage, cela l'est peut-être pour d'autres formes de "structures".
La logique moderne et les mathématiques peuvent être vues comme l'organisation humaine d'une cohérence universelle. Pour moi elles sont des inventions culturelles humaines venant de certains hommes cherchant à structurer d'une façon "parfaite" (c-a-d "simple") une cohérence déjà présente dans le monde (en nous et autour de nous, dans le monde physique). Et en retour, il n'est alors pas si mystérieux que les mathématiques soient utiles à la modélisation des phénomènes physiques.
Cette idée n'est pas la seule possible sur la nature de la logique... Beaucoup de mathématiciens continuent de croire que la logique formelle existe indépendamment d'eux, et qu'ils n'inventent rien, mais découvrent seulement des mystères de Dieu. Ici on arrive au 3e point. Pour certains de mes profs de math, la logique pouvait être l'expression du divin, l'ultime réalité du Monde. (Un réalisme logique qui tend vers une forme de théologie.)