Article collection "Mathematical Problems of Cybernetics" №8, Moscow, 1999
Random set partitions
The first part of the article presents an overview of research history in the field of random set partitions, and describes a series of objects that can be treated as such partitions. The second part present's the author's results on contradictory partitions in application to the study of read-once conjunctive normal forms. We also consider m-set partitions that have a prescribed number of blocks in common with a fixed partition as well as random partitions with a prescribed number of blocks. We present a formula for the number of read-once conjunctive normal forms of a special type and an asymptotic estimate for the number of read-once conjunctive normal forms that depend essentially on every variable. The article also includes a formula for the size of the Boolean function subclass where the solution of corresponding equation systems has polynomial complexity.
random set partitions, fixed partition, contradictory partition, read-once conjunctive normal forms
Publication language:russian, pages:22 (p. 33-54)
Mathematical problems and theory of numerical methods