Abstract FR:

De l'etude conjointe, en theorie des modeles finis, du probleme de decision, du pouvoir d'expression et de l'existence d'une loi a-1 pour une meme logique, est apparu des connexions significatives. Ainsi, les resultats de kolaitis et vardi, d'une part, et de pacholski et szwast, d'autre part, ont revele une remarquable equivalence : une classe prefixe avec l'egalite est decidable si et seulement si le fragment existentiel de la logique du second ordre correspondant admet une loi 0-1. Les deux resultats principaux de cette these, qui repondent a des problemes ouverts, consiste a montrer que cette equivalence n'est pas preservee pour la logique du premier ordre a deux variables et pour la classe prefixe sans l'egalite de godel. En effet, ces deux logiques sont decidables et pourtant leur fragment existentiel de la logique du second ordre respectif n'admet pas de loi. Les contre-exemples s'obtiennent a partir de variantes de la propriete de noyau dans les graphes. On montre que celles-ci n'admettent pas de probabilite asymptotique. Ces resultats requiert une bonne maitrise des techniques probabilistes utilisees dans l'etude des graphes aleatoires.