Quantitative Logic.

Quantitative logic is mostly concerned about statistics of random logical expressions. A typical question might be: what is the probability that a random expression, in a specific logical system, is a tautology? (It turns out that, for many logical systems, this happens with a rather high probability...). Until recently, most of the results in this area were about various versions of propositional logic (depending on the exact set of connectors, whether they are commutative or associate, etc.).

Our first results were about defining precisely various probability distributions on boolean functions from initial distributions on random logical expressions (i.e., trees) from the propositional calculus, and investigating their relationship with the tree complexity of the boolean functions (size of a minimal tree representation of the function). Another interesting point concerns the expressive power of different systems, for various sets of connectors and properties.

The statistical study of random expressions with quantifiers is more recent and has its own special challenges. If we assume that there is a single quantifier, then we are actually modeling terms from the lambda-calculus. Such terms are no longer trees, but rather directed acyclic graphs, satisfying some specific conditions - not surprisingly, the behaviour of quantified expressions widely differs from that of non-quantified ones.

List of publications