The aim of this paper is to study the threshold behavior for the satisfiability property of a random -XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with variables per equation. For we show the existence of a sharp threshold for the satisfiability of a random -XOR-CNF formula, whereas there are smooth thresholds for and .
Il s'agit de présenter l'article de Schönfinkel «Über die Bausteine der mathematischen Logik», préparé pour la publication (1924) par H. Behmann, d'après une conférence de Schönfinkel en 1920, qui fonde ce que Curry nommera «la logique combinatoire». L'objectif principal du travail de Schönfinkel est l'élimination générale des variables (propositionnelles, prédicatives, individuelles), grâce à l'usage de plusieurs «fonctions particulières». On trouvera ici : (1) une introduction à l'article de Schönfinkel,...