% EJC papers must begin as follows
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P37}{19(2)}{2012}

% only use standard LaTeX packages
% only include essential packages

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsfonts}
\usepackage{stmaryrd}
%\usepackage{amsmath,amsthm,amssymb}
%\usepackage{a4wide}
\usepackage{array}
\usepackage{graphicx}
\usepackage{nicefrac}

\usepackage{tikz}

% we recommend the graphicx package for importing figures
%\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
%\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
%\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
%\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; i.e. there must be no text protruding into the margins
% use \sloppy to avoid overly wide text
\sloppy

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{thm}{Theorem}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lem}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}


\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\newtheorem{df}[theorem]{Definition}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{fct}[theorem]{Fact}
\newtheorem{ex}[theorem]{Example}


\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{rmq}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}




\author{Antoine Genitrini\thanks{Partially supported by  the A.N.R. project {\em  BOOLE}, 09BLAN0011,
and by the P.H.C. Amadeus project {\em Probabilities and tree representations for Boolean
functions}.}\\
\small Laboratoire d'Informatique de Paris 6,\\[-0.8ex]
\small CNRS UMR 7606 and\\[-0.8ex]
\small Universit\'e Pierre et Marie Curie,\\[-0.8ex]
\small 4 place Jussieu,\\[-0.8ex]
\small 75252 Paris cedex~05, France.\\
\small\tt antoine.genitrini@lip6.fr
\and
Bernhard Gittenberger\thanks{Partially supported by the P.H.C. Amadeus project {\em Probabilities and tree representations for Boolean
functions}, and by {\em FWF (Austrian Science Foundation),
National Research Area S9600, grant S9604} and {\em \"OAD, grant F03/2010}.}\\
\small Institute for Discrete Mathematics \\[-0.8ex]
\small and Geometry, \\[-0.8ex]
\small Technische Universit\"at Wien,\\[-0.8ex]
\small Wiedner Hauptstrasse 8-10/104,\\[-0.8ex]
\small A-1040 Wien, Austria.\\
\small\tt gittenberger@dmg.tuwien.ac.at
\and
Veronika Kraus$^\dag$\\
\small Institute of Bioinformatics \\[-0.8ex]
\small and Translational Research, \\[-0.8ex]
\small UMIT, \\[-0.8ex]
\small Eduard-Wallnoefer Zentrum 1, \\[-0.8ex]
\small 6060 Hall in Tyrol, Austria \\
\small\tt veronika.kraus@umit.at
\and
C\'ecile Mailler$^*$\\
\small Laboratoire de Math\'ematiques de Versailles,\\[-0.8ex]
\small CNRS UMR 8100 and\\[-0.8ex]
\small Universit\'e de Versailles Saint-Quentin,\\[-0.8ex]
\small 45 avenue des \'Etats-Unis,\\[-0.8ex]
\small 78035 Versailles, France.\\
\small\tt cecile.mailler@math.uvsq.fr}

\date{\dateline{Dec 14, 2011}{May 31, 2012}{Jun 6, 2012}\\
\small Mathematics Subject Classifications: 03B05, 05A15, 05A16}


\newcommand{\mc}[1]{\ensuremath{\mathcal{#1}}}
\def\indi{\mbox{\hspace{0.2em}l\hspace{-0.55em}1}}


\title{Probabilities of Boolean Functions Given\\ 
by Random Implicational Formulas}


\begin{document}
\maketitle

\begin{abstract}
  We study the asymptotic relation between the probability and the
  complexity of Boolean functions in the implicational fragment which
  are generated by large random Boolean expressions involving
  variables and implication, as the number of variables tends to
  infinity. In contrast to models studied in the literature so far, we
  consider two expressions to be equal if they differ only in the
  order of the premises. A precise asymptotic formula is derived for
  functions of low complexity. Furthermore, we show that this model
  does not exhibit the Shannon effect.

\phantom{spacer}
\end{abstract}


\section{Introduction}

Since almost two decades a rising interest in probability distributions on a set of Boolean
functions which are induced by random Boolean expressions can be observed. To our knowledge the
first systematic investigations in this direction have been done by Paris et al. \cite{PVW94} on
expressions composed of the two connectives \emph{AND} and \emph{OR}. Lefmann and Savick\'y~\cite{LS97}
proved the existence of a limiting distribution (as the size of the expressions
tends to infinity) and established estimates relating probability and complexity. These bounds were
later improved in~\cite{CFGG04} and the precise asymptotic behaviour for functions
of low complexity was determined by Kozik~\cite{kozik}.
A generalisation which takes commutativity of the connectives into account and maps
this property into the model was presented recently in~\cite{GGKM11}. 
The question for the probability of a tautology was pursued for instance in~\cite{Kos04, Kos06, KoZa04, Mat05}
for various logical systems. An overview is presented in
Gardy's survey~\cite{G06}. 

In this paper we consider Boolean formulas built of positive variables taken from a fixed set
$\{x_1,\dots,x_n\}$ of Boolean variables and the logical connective of implication. The functions
which can be represented by such formulas form the so-called implicational fragment. The
implicational fragment plays an important role in the theory of programming since there are linear
time satisfiability tests for such expressions (see \cite{DoGa84}). A thorough study of a closely
related model was carried out in \cite{FGGG11}: There expressions of the form $A_1 \rightarrow
(A_2\rightarrow (A_3 \rightarrow \ldots (A_p \rightarrow \alpha)))$ have been represented by
binary trees where internal nodes represent implication and external nodes (leaves) carry
labels which correspond to the variables. Though technically more convenient, a drawback of using 
plane binary trees (i.e., binary trees embedded in the plane) is that two expressions which differ
only w.r.t. the order of the premises are considered different. It is more natural to consider
$x\rightarrow(y\rightarrow z)$ and $y\rightarrow(x\rightarrow z)$ to be the same expression since both
represent the function $(x \land y)\rightarrow z$. The aim of this paper is to study a model of
Boolean expressions which takes into account that the premises of an implication can be permuted.
%This is based on technically more involved non-plane trees and the restriction \emph{binary} is
%dropped as well. 
In particular, we present a quantitative relation between the probability of a
function and its (formula size) complexity.  

Plan of the paper: In the next section we will give a precise description of the model and state
our main result. It will turn out that it is \emph{a priori} not guaranteed that the probability
measure we introduce actually exists. This issue is discussed in Section~\ref{grenzverteilung}. In 
Section~\ref{sec:tautologies} we study the structure of tautologies. We will show that
asymptotically almost all tautologies are simple, i.e. of a particular shape.
Section~\ref{genprob} is then devoted to the asymptotic computation of the probabilities of a
general Boolean function. We will succeed by following the approach of \cite{FGGG11} and introducing
certain expansion techniques which may be applied repeatedly to formulas. After all, we prove that
applying one expansion to a minimal formula representing $f$ yields a sufficiently rich class of
formulas from which the asymptotic probability can be computed. In the last section we disprove the Shannon effect for our model. Roughly speaking, a model exhibits the Shannon effect if a random function asymptotically almost surely has exponential complexity (w.r.t. to the
number of variables). This is, for instance, true for the set of all Boolean functions on
$n$ variables equipped with the uniform probability. 


\section{Model and main result}

We start with a precise description of the model: 

\begin{df}
An {\bf implicational formula} (or {\bf expression})
is either a single variable taken from $\{x_1,\dots,x_n\}$ or defined recursively
as an expression of the form $\{A_1,A_2,\dots A_k\}\rightarrow \alpha$ where $A_1,\dots, A_k$ are
themselves formulas and $\alpha$ is a variable.  
The order of the premises $A_1,\dots,A_k$ is not relevant, i.e., all expressions $\{A_{\sigma(1)}, 
A_{\sigma(2)}, \dots, A_{\sigma(k)}\} \rightarrow \alpha$ where $\sigma$ is a permutation of
$\{1,\dots,k\}$ are equal. We call $\alpha$ the {\bf goal} of the expression.
The {\bf size} of a formula is the number of variables it is composed of, where repetitions are
counted. 
\end{df}

\begin{rmq}
Let us illustrate this definition by an example: Both formulas 
$\{(x\rightarrow y), x \}\rightarrow z$ and $\{x, (x\rightarrow y)\}\rightarrow z$ are the same
object. Its size is 4 and it represents the Boolean function $(x\land (x\rightarrow
y))\rightarrow z$. 
\end{rmq}

Expressions according to the above definition can be easily represented by trees: 

\begin{df} 
A rooted and non-plane tree where the vertices are labelled by variables from $\{x_1,\dots,x_n\}$
(see Figure~\ref{fig:ex}) is called a {\bf general implication tree}. The set of all general
implication trees is denoted by $\mathcal A_n$, the set of those with $m$ vertices by $\mathcal
A_{n,m}$. 
\end{df}

Obviously, general implication trees represent expressions. The label of the root is the goal
and the subtrees are trees representing the premises. Clearly, the tree must be non-plane, since
the order of the subtrees is irrelevant. The size of the corresponding expression equals the
number of vertices of the tree. 


\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.3\textwidth]{fig-ex}
%\input{fig-ex}
\end{center}
\vskip-8pt\vskip-8pt
\caption{A general implication tree representing the expression $A_1 \rightarrow (A_2\rightarrow
(A_3 \rightarrow \ldots (A_p \rightarrow \alpha)))$ where $A_1,\ldots,A_p$ are the expressions
represented by $T_1,\ldots,T_p$, respectively.}
\label{fig:ex}
\end{figure}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.5\textwidth]{fig-general-tree}
%\input{fig-general-tree}
\end{center}
\vskip-8pt\vskip-8pt
\caption{A general implication tree representing the Boolean function $x_3 \rightarrow x_1$.}
\label{fig:impltree}
\end{figure}

Our particular interest is the relation between probability and complexity of a Boolean function.
Let $\mathcal F_n$ denote the implicational fragment of all Boolean functions in the variables
$x_1,\dots,x_n$. We do not require that a function in $\mathcal F_n$ actually depends on all the
variables. E.g. the constant functions $\top$ (tautologies) and $\bot$ (contradictions) do not
depend on any variable. 

\begin{df}\label{def:essential}
We call a variable $x$ an {\bf essential variable} for a function $f=f(x,x_1,\ldots,x_{n-1})$ if there exists an assignment of $True$ or $False$ to the variables $x_1,\ldots,x_{n-1}$, which we denote by $\underline{x}_0$, such that $f(True,\underline{x}_0)\neq f(False,\underline{x}_0)$. 
\end{df}

% Given $f\in \mathcal F_n$ we call a variable $x_i$ {\bf essential
% variable} if it may influence the value $f$. Whether it actually does depends in general on the
% values assigned to the other variables ($x$ and $y$ are both essential for 
% $f=x\rightarrow y$, but $y$ has no influence on $f$ if $x$ is false). 

\begin{df} \label{probcomp}
Let $f\in \mathcal F_n$. The {\bf complexity} $L(f)$ is defined as the minimal size of expressions representing $f$. 

Let $\mathbb P_{m,n}$ be the probability distribution induced by the uniform distribution on the set of all
general implication trees of size $m$. The probability measure $\mathbb P_n$ is defined as the limit of the measures $\mathbb P_{m,n}$ as $m$ tends to infinity, i.e., $\mathbb P_n=\lim_{m\to \infty} \mathbb P_{m,n}$. 
We call $\mathbb P_n(f)$ the {\bf probability} of $f$. 

A general implication tree representing $f$ and having $L(f)$ vertices is called a {\bf minimal
tree of} $f$. The set of all minimal trees of $f$ is denoted by $\mc M_f$.
\end{df}

\begin{rmq}
Note that the probability of the function is defined as the limit of a sequence of
probabilities. A priori, we cannot be sure that this limit exists. We will see in the next
section that this limit indeed exists.
\end{rmq}

We aim at a quantitative description of the asymptotic probability of a function, 
as $n$ tends to infinity, and its relation to the complexity. Precisely, we will show: 
\begin{thm}
\label{prop:lambda}
Let $n_0$ be a fixed positive integer and $f\in \mathcal F_{n_0}$. Then we have 
$$
\mathbb{P}_n(f)=\frac{\lambda_f}{n^{L(f)+1}}+\mathcal{O}\left(\frac1{n^{L(f)+2}}\right), \mbox{ as
} n\to\infty, 
$$
where $\lambda_f$ is a constant independent of $n$.
\end{thm} 

\begin{rmq}
Note that we fix the function in advance. Thus the number of essential variables is fixed as well.
Nevertheless, we may always regard a function in $n_0$ variables as an element of $\mathcal F_n$
for $n>n_0$. For instance, $x\rightarrow y$ is the same function as $\{z\rightarrow z,
x\}\rightarrow y$. 
\end{rmq}















\section{Existence of the limiting probability $\mathbb P_n$} \label{grenzverteilung}

In order to show our result we will use the so-called symbolic method (see \cite{FlSe} for
a description of this method). A general implication tree can be formally described by
a grammar: If $\mathcal P$ denotes the set of all general implication trees and $\mathcal L$ the
set of all variables, then obviously $\mathcal P=\mathcal L\times \mbox{\tt multiset}(\mathcal P)$.
Let us denote by $P(z)=\sum_{m\ge 0} P_mz^m$ the generating function of general implication trees. 
Then the coefficient $P_m=[z^m]P(z)$ is the number of general implication trees of size $m$. 
According to the symbolic method, the grammar can be translated into the functional equation 
\[P(z)=nz\exp \left(\sum_{i\geq 1}\frac{P(z^i)}{i}\right).\]
Moreover, let $P_f(z)=\sum_{m\ge 0} P_{f,m}z^m$ denote the generating function of general
implication trees representing the Boolean function $f$. $P_{f,m}$ is the number of all general
implication trees with $m$ vertices which represent $f$. Similarly as before, we get
\[P_f(z)=z\indi_{\{f\text{ lit}\}}+z\sum_{j=1}^n\sum_{l=1}^\infty 
 \sum_{\{g_1 \land \ldots \land g_l\}\rightarrow x_j=f}\prod_{k=1}^l \exp\left(\sum_{i=1}^\infty \frac{P_{g_k}(z^i)}{i}\right)\]
where $\indi_{\{f\text{ lit}\}}$ gives $1$ if $f$ is a variable and $0$ otherwise, the index $j$ chooses the label of the root of the tree and the index $l$ counts the number
of different Boolean functions represented by at least one subtree of the root. Thus the range of
the innermost sum is the set of all choices of mutually different functions $g_1,\dots, g_l$. For
every $f$ we get an equation like this, altogether forming a system of functional equations. 

We can apply the Drmota-Lalley-Woods theorem (DLW) to this system. We will not go into details here 
but refer the reader to \cite[Chapter~VII]{FlSe} or \cite[Sec.~2.2.5]{Drmota09}. 

DLW states that, under certain technical conditions, all functions in the system have the same
dominant singularity $\eta$ and admit, locally around $\eta$, an expansion of the form 
\begin{equation} \label{singexp}
P_f(z)=g_f(z)-h_f(z)\sqrt{1-\frac{z}{\eta}} 
\end{equation} 
where $g_f(z)$ and $h_f(z)$ are analytic at $z=\eta$. The system above fulfills all assumptions of DLW.
We refer to \cite[Sec.~3]{FGGG11} where an application of DLW in a very similar context is carried
out in detail. 

By the transfer lemma (see \cite[Corollary 2]{FlOd}) we can further extract asymptotic coefficients
from an expansion like \eqref{singexp} and obtain
\begin{equation}\label{eq:coeffs}
[z^m]P_f(z)\sim a_{n}(f) n^{-\nicefrac{3}{2}}\eta^{-n} \textrm{as } m\to \infty,
\end{equation}
where $a_n$ is a positive constant. Note that $P(z)=\sum_f P_f(z)$ and $P(z)$ admits a singular
expansion of the same type,
it has the same singularity and therefore has coefficients of the same asymptotic behaviour. 
Since the limiting distribution $\mathbb P_n$ is determined by the limits
 $\lim_{m\to \infty}[z^m] P_f(z) / [z^m] P(z)$, \eqref{eq:coeffs}~immediately implies the existence of the limiting
distribution. 











\section{Simple tautologies} 
\label{sec:tautologies}

The proof of our main result relies on the expansion techniques introduced in the next section.
These are essentially sets of rules how to attach certain trees to a given tree. For instance,
adding a tautology as a premise never changes the function. Thus we want to count the number of
trees obtained by expansions and in particular the trees representing a tautology. Exact counting of 
tautologies is not easy, but fortunately only tautologies of a simple shape are asymptotically
relevant. 
The three families that will be presented in the next definition have been introduced in the
paper~\cite{FGGZ07} in the case where premises cannot commute.

\begin{df}
A {\bf simple tautology} is a general implication tree in which exactly one subtree of the root is 
a leaf labelled by the same label as the root itself (c.f. Figure~\ref{fig:st}). If this label is
$x$, we say that the simple tautology is {\bf realised by} $x$.  

\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.3\textwidth]{fig-st}
%\input{fig-st}
\end{center}
\vskip-8pt\vskip-8pt
\caption{A simple tautology realised by the variable $x$.}
\label{fig:st}
\end{figure}


A {\bf simple non-tautology} is a general implication tree such that the label of the root is
different from the labels of all its children (c.f. Figure~\ref{fig:snt}).

\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.8\textwidth]{fig-snt}
%\input{fig-snt}
\end{center}
\vskip-8pt\vskip-8pt
\caption{A simple non-tautology: $x\notin \{x_{i_1},\ldots,x_{i_p}\}$.}
\label{fig:snt}
\end{figure}


A {\bf less simple non-tautology} 
is a general implication tree such that (c.f. Figure~\ref{fig:lsnt}):
\begin{itemize}
\item exactly one of the children of the root, say $s$, has the same label $x$ as the root itself,
\item the subtree rooted at $s$ has more than one vertex,
\item every child of $s$ has a root labelled by a label different from all the labels appearing on the first level of the tree, and all
the grand-children of $s$ have root-labels different from $x$ and
from their parent's label.
\end{itemize}

\begin{figure}[ht]
%\[
%\includegraphics[width=0.8\textwidth]{fig-lsnt}
\input{fig-lsntMY}
%\]
\vskip-10pt
\vskip-10pt
\vskip-10pt
\caption{A less simple non-tautology}
\label{fig:lsnt}
\end{figure}
\end{df}



In order to proceed, we will show that asymptotically almost every expression is a simple
tautology, a simple non-tautology or a less simple non-tautology. 

\begin{df}
Let $\mathcal B_n\subseteq \mathcal A_n$ and $\mathcal B_{n,m}=\{t\in \mathcal B_n\:\mid\: t \mbox{ has
$m$ vertices}\}$. We define the {\bf limiting ratio} of $\mathcal B_n$ by 
\[\mu_n(\mathcal B_n)=\lim_{m\to\infty}\frac{|\mathcal B_{n,m}|}{|\mathcal A_{n,m}|}.\]
\end{df}

\begin{rmq}
Note that we can easily construct sets $\mathcal B_n$ such that $\mu_n(\mathcal B_n)$ does not exist.
%Furthermore, we remark that though the definition reminds us of a discrete probabilities, it can
%be shown that the limiting ratio is not a probability measure on the set of all sets which have a
%limiting ratio.
But the considerations of the previous section imply that for all $f\in \mc F_n$ 
the set $\mathcal A_{n,f}$ of all
general implication trees which represent $f$ has a limiting ratio and even more we have 
$\mu_n(\mathcal A_{n,f}) = \mathbb P_n(f)$. 
\end{rmq}

Let $\mathcal T$ denote the set of tautologies, $\mathcal T_s$ the set of simple tautologies,
$\mathcal N_s$ and $\mathcal N_\ell$ the set of simple and less simple non-tautologies,
respectively. 

\begin{thm}
Asymptotically almost every tautology is simple, i.e. $\mu_n(\mathcal T_s)\sim \mu_n(\mathcal T)$
as $n\to\infty$.
\end{thm}

In order to prove this theorem we will show that $\mu_n(\mathcal T_s \cup \mathcal N_s \cup
\mathcal N_\ell)=1-\mc O\left(\frac 1{n^2}\right)$ which implies $\mu_n(\mathcal T\setminus
\mathcal T_s)=\mc O\left(\frac 1{n^2}\right)$. 
On the other hand, the set of simple tautologies is much larger, as the following
proposition shows.


\begin{prop}\label{prop:st}
The limiting ratio of simple tautologies satisfies $\mu_n(\mathcal T_s)=
\frac{1}{en}+\mc{O}\left(\frac1{n^2}\right)$, 
as $n\to\infty$.
\end{prop}

\begin{proof}
A simple tautology is constructed by $\mathcal L\times \mathcal Z \times {\tt multiset}(\mathcal
P\setminus\mathcal Z)$ where $\mathcal P$ and $\mathcal L$ are the set of general implication trees
and the set of variables, respectively, and $\mathcal Z$ is the set of a single variable. The $\mathcal Z$ corresponds to the distinguished leaf in the first level determined by the label of the
root. Hence the generating function of simple tautologies is 
\[
S(z)=nz^2\exp\left(\sum_{i\geq 1}\frac{P(z^i)-z^i}{i}\right)=zP(z)\exp \left(-\sum_{i\geq
1}\frac{z^i}{i}\right)=z(1-z)P(z).
\]

We know that $S(z)$ and $P(z)$ have the same singularity $\eta$ and singular expansions of the kind~\eqref{singexp} around them. It follows that (cf. \cite[Lemma 3.4]{GGKM11})
\[\mu_n(\mathcal T_s)=\lim_{m\to \infty}\frac{S_m}{P_m}=\lim_{z\to \eta} \frac{S'(z)}{P'(z)}.\]
We have
\[\frac{S'(z)}{P'(z)}=\frac{(1-z)P(z)}{P'(z)}-\frac{zP(z)}{P'(z)}+\frac{z(1-z)P'(z)}{P'(z)}.\]
From~\eqref{singexp} we can deduce that $P'(z)$ tends to infinity as $z$ tends to $\eta$, while $P(\eta)$ is bounded. Therefore, the first two summands become negligible compared to the
third one if $z$ tends to $\eta$, and
\[\lim_{z\to \eta} \frac{S'(z)}{P'(z)}=\eta(1-\eta).\]

We now have to determine an asymptotic expansion of $\eta$, as $n\to\infty$.
By an application of the implicit function theorem (cf. \cite[Theorem 2.19]{Drmota09}), $(\eta,P(\eta))$ is a solution of the system
\[
\left\{\begin{matrix}
P=nz e^P Q\\
1=nz e^P Q
\end{matrix}\right.
\]
where $Q=\exp\left(\sum_{i\geq 2}\frac{P(z^i)}{i}\right)$ is analytic in $\eta$. Therefore,
$P(\eta)=1$ and $\eta = \frac1{neQ(\eta)}$. Further, as $P(z)=nz+\mc{O}(z^2)$, we know that $Q(z)=1+nz^2+\mc{O}(z^3)$, which implies $\eta=\mc{O}\left(\frac{1}{n}\right)$
and $Q(\eta)=1+\mc{O}\left(\frac1{n}\right)$. We can thus conclude that $\eta
=\frac1{en}+\mc{O}\left(\frac{1}{n^2}\right)$. By further bootstrapping it is possible to show 
\begin{equation} \label{eta}
\eta=\frac1{en}-\frac1{2e^2n^2}+\mc O\left(\frac1{n^3}\right).
\end{equation} 

We finally get
$\lim_{z\to \eta} \frac{S'(z)}{P'(z)}=\eta(1-\eta) = \frac1{en}+\mc{O}\left(\frac{1}{n^2}\right)$.
\end{proof}


\begin{prop}
The limiting ratio of simple non-tautologies satisfies 
$\mu_n(\mathcal N_s)=1-\frac{2}{n}+\mc{O}\left(\frac1{n^2}\right)$. 
\end{prop}

\begin{proof}
The set of simple non-tautology satisfies $\mathcal N_s=\mc L \times {\tt multiset}( (\mc L\setminus \mc Z) \times  {\tt  multiset}(\mc P))$. Since $(\mc L\setminus \mc Z) \times  {\tt  multiset}(\mc P)$ gives \[(n-1)z\exp\left(\sum_{i\geq 1}\frac{P(z^i)}{i}\right)=\frac{n-1}nP(z),\]
 the generating function of simple non-tautologies is given by the equation
\[N_s(z)=nz \exp \left(\frac{n-1}{n}\sum_{i\geq 1} \frac{P(z^i)}{i}\right)=nz \left(\frac{P(z)}{nz}\right)^{\frac{n-1}{n}}= (nz)^{\nicefrac1{n}}P(z)^{\frac{n-1}{n}}.\]
The limiting ratio of simple non-tautologies is $\mu_n(\mathcal N_s)=
\lim_{m\to \infty}\frac{[z^m]N_s(z)}{P_m}=\lim_{z\to \eta}\frac{N_s'(z)}{P'(z)}$, and
\[N_s'(z)=\frac1n(nz)^{\frac{1-n}{n}}P(z)^{\frac{n-1}{n}} + \frac{n-1}{n}(nz)^{\nicefrac1{n}}P'(z)P(z)^{\frac{n-1-n}{n}}.\]
If we divide by $P'(z)$ and consider the limit when $z$ tends to $\eta$, the first term of the sum
becomes negligible compared to the second. Eventually, $P(\eta)=1$ implies
\[\lim_{z\to \eta}\frac{N_s'(z)}{P'(z)}
=\frac{n-1}{n}\left(\frac1{e}\right)^{\nicefrac1{n}}\!\!+\mc{O}\left(\frac{1}{n^2}\right)
= \left(1-\frac1{n}\right)^2 +\mc{O}\left(\frac1{n^2}\right)
= 1-\frac2{n}+\mc{O}\left(\frac1{n^2}\right),\]
which completes the proof.
\end{proof}



\begin{prop}
We have $\mu_n(\mc N_\ell)=\left(2-\frac{1}{e}\right)\cdot \frac1n+\mc{O}\left(\frac1{n^2}\right)$.
\end{prop}

\begin{proof}
First, we may assume that $y_1,\dots,y_r$ (c.f. Figure~\ref{fig:lsnt}) are pairwise 
different. Any dependency introduces an additional factor $\nicefrac1n$ and therefore the set of
such trees is negligibly small.

Let us fix an integer $r\ge 0$ and variables $\{x,y_1,\ldots, y_r\}$. Moreover, let $T(z)$ be the
generating function of the $T_i$, $i=1\ldots p$, as in Figure~\ref{fig:lsnt}. 
Since for the choice of the root-label $r+1$ possible labels are forbidden, and for the labels 
in the first generation two possible labels are ineligible, we obtain 
\begin{equation} \label{Tis}
T(z)=(n-r-1)z\exp \left(\sum_{i\geq
0}\frac{n-2}{n}\frac{P(z^i)}{i}\right)=(n-r-1)z\left(\frac{P(z)}{nz}\right)^{\frac{n-2}{n}}.
\end{equation} 

To construct $\mc N_\ell$ we start with a pair of equally labelled vertices
(the root and one of its children). Then we have $\binom{n-1}r$ possibilities to choose $y_1,\ldots, y_r$. The
resulting subtrees are all different, hence this is no multiset but an ordinary set of trees.
Finally, from the multiset comprising the $T_i$'s (c.f. Figure~\ref{fig:lsnt}) we must exclude the
empty set, since $x$ is not a leaf. These considerations yield the formal relation 
\[
\mc N_\ell=\mc L\times \mc Z\times \bigcup_{r\ge 0} \binom{n-1}r (\mc Z\times {\tt multiset}(\mc
P))^r\times ({\tt multiset}(\mc T_r)\setminus \{\emptyset\}),
\]
where $\mc T_r$ is the set of trees with the generating function given in~\eqref{Tis}. 
Therefore, the generating function $N_\ell(z)$ of less simple
non-tautologies is given by
\begin{align*}
N_\ell(z)
&=nz^2 \sum_{r\geq 0}\binom{n-1}r\left(\frac{P(z)}{n}\right)^r\left(\exp\left(\sum_{i\geq 1}\frac{T(z^i)}{i}\right)-1\right)\\
&=nz^2 \sum_{r\geq 0}\binom{n-1}r\left(\frac{P(z)}{n}\right)^r \left(\exp\left(\sum_{i\geq 1}\frac{(n-r-1)z^i}{i}\left(\frac{P(z^i)}{nz^i}\right)^{\frac{n-2}{n}}\right)-1\right).
\end{align*}
As before, the limiting ratio of less simple non-tautologies is 
$\mu_n(\mc N_\ell)=\lim_{z\to \eta}\frac{N_\ell'(z)}{P'(z)}$. 
Let $Q(z)=\exp\left(\sum_{i\geq
2}\frac{(n-r-1)z^i}{i}\left(\frac{P(z^i)}{nz^i}\right)^{\frac{n-2}{n}}\right)$. 
Then 
\begin{align*}
\lim_{z\to \eta}\frac{N_\ell'(z)}{P'(z)}
&\sim n\eta^2 \sum_{r\geq 0}   \binom{n-1}r \frac{P(\eta)^{r-1}}{n^r} \times\\  
&\qquad\left(\left(\frac{n-2}{n}(n-r-1)\eta\left(\frac{P(z)}{n\eta}\right)^{\frac{n-2}{n}}+r\right)Q(\eta)e^{(n-r-1)\eta \left(\frac{P(\eta)}{n\eta}\right)^{\frac{n-2}{n}}}-r\right).
%&\quad -n\eta^2 \sum_{r\geq 0} \binom{n-1}r \frac{P(\eta)^{r-1}}{n^r}\cdot r.
\end{align*}
We know that $P(\eta)=1$ and $\eta \sim \frac1{en}$. Therefore $Q(\eta) \sim 1$ and
hence  
\begin{align*}
\lim_{z\to \eta}\frac{N_\ell'(z)}{P'(z)}
&\sim \frac1{n e^2} \sum_{r\geq 0}\frac{(n-1)_r}{r! n^r} 
\left(\left(\frac{n-2}{n}(n-r-1)\frac{\nicefrac1{n e}}{(\nicefrac1{e})^{\frac{n-2}{n}}}+r\right)
e^{(n-r-1)\frac1{en} e^{\frac{n-2}{n}}}-r\right)
%&\quad -\frac{1}{n e^2} \sum_{r\geq 1} \frac{(n-1)_r}{(r-1)! n^r}.
\end{align*}
%Considering that the queues of the sums over $r$ are negligible compared to their truncations to
%$n^{\frac13}$, we can show that:a
Truncating the sums at $n^{1/3}$ causes a negligibly small error, moreover we can use the
estimate $(n-1)_r/n^r\sim 1$ and obtain 
\begin{align*}
\lim_{z\to \eta}\frac{N_\ell'(z)}{P'(z)}
&\sim \frac1{ne^2} \sum_{r= 0}^{\lceil\frac n3 \rceil}\frac1{r!}\left( (r+1) e -r\right)  \sim \frac2{n}-\frac1{en}.
\end{align*}
\vskip-6pt
\vskip-6pt
\vskip-6pt
\end{proof}

It is interesting to note that,
asymptotically, these three families of trees play the same r\^ole in the model without commutativity
of the premises~\cite{FGGZ07} and in our model.



\section{Probability of a general Boolean function} \label{genprob}

To show Theorem~\ref{prop:lambda} we follow the ideas used in \cite{FGGG11} and define 
different kinds of expansions: tautology expansions, premise expansions and goal expansions.

\begin{df}
Given a general implication tree, the tree obtained by adding a new subtree $t_e$ to a node $\nu$
of $t$ is called an expansion of $t$.
\begin{itemize}
\item If the expanded tree represents the same function as $t$, we call the
expansion a {\bf valid expansion}.
\item If $t_e$ is a simple tautology, the expansion is called a {\bf tautology expansion} of $t$. 
For any choice of $\nu$, the expanded tree represents the same function as $t$ and the expansion is valid.
\item If $t_e$ has exactly one subtree being a leaf labelled by $x$, then the expansion is an 
$x${\bf -premise expansion}. If $\nu$ has an ancestor labelled by $x$, or is labelled by $x$,
then the expansion is valid(c.f. Figure~\ref{fig:premise}). 

\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.6\textwidth]{fig-premise-exp}
%\input{fig-premise-exp}
\end{center}
\vskip-8pt\vskip-8pt
\caption{A valid $x$-premise expansion in $\nu$ ($y$ can be any label in $\{x_1,\ldots,x_k\}$).}
\label{fig:premise}
\end{figure}


\item If the root of $t_e$ is labelled by $x$, then the expansion is called $x${\bf -goal
expansion}. If $\nu$ is the parent of a leaf labelled by $x$ or if $\nu$ has an ancestor which is
a brother of a leaf labelled by $x$, then the expansion is valid (c.f. Figure~\ref{fig:goal}).
\end{itemize}
\end{df}


\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.6\textwidth]{fig-goal-exp}
%\input{fig-goal-exp}
\end{center}
\vskip-8pt\vskip-8pt
\caption{A valid $x$-goal expansion in $\nu$ ($y$ and $z$ can be any label in $\{x_1,\ldots,x_k\}$).}
\label{fig:goal}
\end{figure}

Fix a Boolean function $f\in \mc F_{n_0}$. We denote by $E_t(\mathcal{M}_f)$ (resp.
$E_p(\mathcal{M}_f)$, resp. $E_g(\mathcal{M}_f)$) the set of trees obtained by a valid tautology (resp.
premise, resp. goal) expansion of a minimal tree of $f$, and by $E(\mathcal{M}_f)$ the union of
these three sets.

\begin{lem}
\label{lem:min}
The limiting ratio of the family $E(\mathcal{M}_f)$ verifies, asymptotically when $n$ tends to infinity, 
\[
%\lim_{m\to\infty} \frac{E(\mathcal{M}_f)_m}{P_m} 
\mu_n(E(\mc M_f)) = \frac{\lambda_f}{n^{L(f)+1}} + \mathcal{O}\left(\frac1{n^{L(f)+2}}\right),
\]
with $\lambda_f$ being a constant depending only on $f$.
\end{lem}

\begin{proof}
Let $\mc E_x$ denote the set of trees with exactly one child of the root being a leaf labelled by $x$ and by
$\mc G_x$ the set of trees with root labelled by $x$. Every $x$-premise (resp. $x$-goal) expansion 
of a tree $t$ is realised by attaching a tree from $\mc E_x$ (resp. $\mc G_x$) to some node of $t$. 

We already know (cf. Section~\ref{sec:tautologies}) that $\mu_n(\mc T)\sim \nicefrac1{en}$, as
$n\to\infty$. Using again the symbolic method, we obtain the generating function of the family
$\mc E_x$:  
\[
E_x(z)=nz^2\exp{\sum_{i\geq 0} \frac{P(z^i)-z^i}{i}}= z(1-z) P(z)=S(z),
\]
and therefore $\mu_n(\mc E_x)=\frac1{en}+\mc O(\frac1{n^2})$. The generating function of
the family $\mc G_x$ is given by $G_x(z)=\nicefrac{P(z)}n$ and therefore $\mu_n(\mc
G_x)=\nicefrac1{n}$. 

Let $t$ be a tree and define 
\begin{align*} 
p(t)&=\sum_{x\in\{x_1,\dots,x_n\}} \# \text{vertices of $t$ where a valid $x$-premise expansion is
possible},  \\
g(t)&=\sum_{x\in\{x_1,\dots,x_n\}} \# \text{vertices of $t$ where a valid $x$-goal expansion is
possible}.
\end{align*} 
Note that a tautology expansion is always valid. Hence the limiting ratio of $E(\mc{M}_f)$ is
given by
\begin{align*}
\mu_n(E(\mc M_f))&\! = \!  \lim_{m\to\infty} \sum_{t\in \mc{M}_f} 
\left(
p(t)\frac{[z^{m-L(f)}] E_x(z)}{[z^m]P(z)} + g(t)\frac{[z^{m-L(f)}] G_x(z)}{[z^m]P(z)}
+L(f) \frac{[z^{m-L(f)}] S(z)}{[z^m]P(z)}\right)\\
 &\!= \! \frac1{(en)^{L(f)}} \left( \lambda_p \frac1{en} + \lambda_g \frac1n + L(f)
\frac1{en}\right),\end{align*}
where $\lambda_p = \sum_{t\in \mc{M}_f} p(t)$ and $\lambda_g = \sum_{t\in \mc{M}_f} g(t)$.
Set  
\[\lambda_f = \frac1{e^{L(f)}} \left(\frac{\lambda_p}{e} + \lambda_g +  \frac{L(f)}{e}\right).\]
Thus,
\[\mu_n(E(\mc M_f)) = \frac{\lambda_f}{n^{L(f)+1}} + \mathcal{O}\left(\frac1{n^{L(f)+2}}\right).\]
Note that trees obtained by at least two distinct kinds of expansions have been counted several times here. These trees have two constraints though: either two premises with specific labels, or a premise and the goal with fixed labels.
As $\lambda_p, \lambda_g$ and $L(f)$ are independent of $n$, such double expansions have a limiting
ratio~$\mathcal{O}(\nicefrac1{n^{L(f)+2}})$.
\end{proof}

\begin{lem}
\label{lem:min1exp}
Further expansions yield an asymptotically negligible contribution to the limiting ratio. Precisely,
we have 
\[
\mu_n\left( \bigcup_{k\geq 2} E^k(\mathcal{M}_f) \setminus E(\mc{M}_f)\right)=\mathcal{O}
\left(\frac1{n^{L(f)+2}}\right), \text{ when $n\to\infty$.} 
\]
\end{lem}

\begin{proof}
First, consider a minimal tree $t$ and expand it once by a tree $t'$, such that the resulting
tree $t''$ is in $E_g(\mc{M}_f)$. Then any tree obtained from $t''$ by doing a
second expansion at a node of $t'$ lies in $E(\mc{M}_f)$. 

Second, consider a minimal tree $t$ and expand it once (by attaching a tree $t'$) such that the
resulting tree $t''$ lies in $E_p(\mc{M}_f) \cup E_t(\mc{M}_f)$.
If we expand a second time, then we obtain a tree not in $E(\mc{M}_f)$ if and only if the second expansion is done at a node of $t$ or the
expansion is done at the (unique) child of the root of $t'$ which is a leaf labelled by the
variable realising the expansion
(or the child labelled in the same way than the root in tautology expansions, respectively).

Let us calculate the limiting ratio of the set of premise expansion trees where the expansion is 
done at the child of the root which realises the expansion: the generating function of
this family is
\[N(z) = E_x(z) (E_x(z)+E_g(z)+S(z)).\]
Hence, its limiting ratio is of order $\frac1{n^2}$ and the trees obtained by such a nested expansion
of a minimal tree have limiting ratio $\mc{O}\left(\frac1{n^{L(f)+2}}\right)$.

We obtain an analogous result for the set of trees obtained by a second expansion in the specific
node related to the first tautology expansion.

The considerations above imply that the only possibly non-negligible family of expanded trees in
$\bigcup_{k\geq 2} E^k(\mathcal{M}_f) \setminus E(\mc{M}_f)$ is the set of trees obtained by $k$
expansions of some minimal tree $t$, all of which have been done at nodes of $t$. The limiting
ratio of the family of trees obtained by $k$ expansions of a minimal tree, done in $k$ 
of its initial nodes (counted with possible repetitions), is 
\[
%G_k(z) = \binom{L(f)}k (E_t(z)+E_p(z)+E_g(z))^k m_f z^{L(f)},
G_k(z) = \frac{L(f)^k}{k!} (E_t(z)+E_p(z)+E_g(z))^k m_f z^{L(f)},
\]
where $m_f$ is the number of minimal trees of $f$. Its limiting ratio is $\mc
O(\frac1{n^{L(f)+k}})$ which is negligible compared to $\frac1{n^{L(f)+1}}$ for all $k\geq
2$.
\end{proof}

Note that expanding a tree is obviously a reversible procedure. Thus valid expansions have valid
reductions as their counterparts. In \cite{FGGG11} the authors presented an example of a tree
which cannot be reduced though it is not minimal. 

\begin{df}
We pick a tree representing $f$ and simplify it by removing every subtree which is a tautology, a premise or a goal expansion. If the tree cannot be simplified further and is not minimal, we call the obtained tree an {\bf irreducible} tree of $f$. The set of such trees is denoted by $\mc{I}_f$.
\end{df}

In order to complete the proof of Theorem~\ref{prop:lambda}, we have to show that the set of
trees obtained by sucessive expansions of all irreducible trees has a negligibly small limiting ratio.
The reader will observe that these reductions are not confluent, consequently by expanding
irreducible trees we will obtain some trees several times. The following results will
state that this double counting is negligible.
We will adopt some ideas of the corresponding proof in~\cite{FGGG11} for binary plane
implication trees. In fact, we only have to prove the analogue of \cite[Corollary~25]{FGGG11}: 
\begin{lem}
\label{lem:paperFGGG}
Fix a subset $\Gamma\subseteq \{x_1,\dots,x_n\}$. Let $\mathcal{A}_q^p$ be the set of trees having
at least $p$ nodes labelled by a variable in $\Gamma$ at depth less than or equal to $q$. 
Moreover, set $E^*(\mc{A}_q^p) = \bigcup_{k\geq 0} E^k(\mc{A}_q^p)$. Then 
\[
\mu_n(E^*(\mc{A}_q^p) =\mc{O}\left(\frac1{n^p}\right).
\]
\end{lem}

\begin{proof}
Let us consider the set $\mathcal{B}_q^p$ of trees of height less than or equal to $q$ and with at
most $pq$ vertices, at least $p$ of which have labels chosen from $\Gamma$. Let $X(\mathcal{B}_q^p)$ denote the set of trees obtained by adding an arbitrary number of general implication trees at nodes of
$\mc{B}_q^p$. Note that $\mc{A}_q^p
\subseteq X(\mc{B}_q^p)$. If we denote by $\Phi_{q,p}(z)$ the generating function of $\mc{B}_q^p$,
then
\[
[z^{\ell}]\Phi_{q,p}(z) \leq c_{\ell} \begin{pmatrix}\ell \\ p\end{pmatrix} \gamma^p n^{\ell-p},
\]
with $\gamma$ being the cardinality of $\Gamma$ and $c_\ell$ a constant. Adding a multiset of trees at a node $z$ of $\mc{B}_{q,p}$ gives an additional $\exp(\sum_{i\geq1}\nicefrac{P(z^i)}{i})=\nicefrac{P(z)}{nz}$. Therefore, the generating function $\Phi_{X_{q,p}}(z)$ of $X(\mc{B}_{q,p})$ verifies
\[
[z^{m}]\Phi_{X_{q,p}}(z) \leq [z^m] \sum_{\ell \leq pq} c_{\ell} \begin{pmatrix}\ell \\
p\end{pmatrix} \gamma^p n^{l-p} \frac{P(z)^\ell}{n^\ell} = \frac1{n^p} \sum_{\ell \leq pq} [z^m]
C_\ell P(z)^\ell,
\]
where $C_\ell$ is a constant. Thanks to the asymptotic coefficients derived from the singular expansion of type \eqref{singexp} by a transfer lemma (see \cite{FlOd}), we know that $\frac{[z^m] P(z)^\ell}{[z^m] P(z)}$ tends to a constant as $m\to \infty$, since 
$P(z)$ and $P^\ell(z)$ both have a square-root singularity at $\eta$. 
Therefore, there are constants $K_\ell$ such that 
\[\frac{[z^{m}]\Phi_{X_{q,p}}(z)}{[z^m]P(z)} \leq \frac1{n^p} \sum_{\ell \le pq} K_\ell,\]
which implies that the limiting ratio of the set $\mc{A}_q^p$ is of order $\mc{O}\left(\frac1{n^p}\right)$.
\end{proof}

Thanks to this lemma the proofs of~\cite{FGGG11} can easily be adapted to our new model: The idea
is to define a set $\mc N$ which is the union of certain sets of the form
$\mc{A}_q^p$, all of them satisfying $p>L(f)+1$ which implies $\mu_n(\mc N)=\mc
O\left(\nicefrac1{n^{L(f)+2}}\right)$. Then the set of irreducible trees $\mc I_f$ is partitioned
according to the tree size and the number of essential and inessential variables of $f$ that occur
among the labels. The final step is to show that the sets in this decomposition are either
empty or subsets of $\mc N$. All those arguments are independent of whether the premises
are considered permutable or not. Thus the following lemma holds in our model. 

\begin{lem}
\label{lem:irr}
The limiting ratio of the set $E^*(\mc{I}_f)$ verifies
\[
\mu_n (E^*(\mc{I}_f))=\mc{O}\left(\frac1{n^{L(f)+2}}\right).
\]
\end{lem}

\begin{proof}
See \cite[Sec.~5]{FGGG11}.
\end{proof}

%\begin{proof}
\noindent\emph{Proof of Theorem~\ref{prop:lambda}}.
The set of implication trees representing a fixed Boolean function $f$ is the union of the
following sets: the set $\mathcal{M}_f$ of minimal trees of $f$, the set $E(\mc{M}_f)$ of minimal
trees of $f$ expanded once, the set $E^{\ge 2}(\mc{M}_f)$ of minimal trees of $f$ expanded at
least twice, and the set $E^*(\mc{I})$ of (iterated) expansions of irreducible trees representing
$f$.

When $n$ tends to infinity, thanks to Lemmas~\ref{lem:min1exp} and~\ref{lem:irr}, the set
$E(\mc{M}_f)$ is the only one to contribute to the asymptotic probability of $f$. This contribution is given in
Lemma~\ref{lem:min}. \qed
%\end{proof}




\section{Disproving the existence of the Shannon effect} \label{shannon}

To show that our model does not exhibit the Shannon effect, we will follow the proof presented
in~\cite{GG10} for binary plane implication trees: we consider a family $\Pi$ of trees with less than
$g(n)$ vertices where $g(n)$ is a suitable function of sufficiently fast but subexponential growth
in $n$. If we show that the limiting ratio of all expansions of all trees of $\Pi$ is non-zero,
then there is a set of functions of subexponential complexity (actually bounded by
$g(n)$) with positive probability, which contradicts the assertion of the Shannon effect. 


Some care is required since we want to avoid double-counting. Thus we restrict the expansions to those where, given an expanded tree, the location where the expansion took place can be
identified. Of course, doing so we will not get all trees of $E(\Pi)$ but alone all those
representing a function $f$ with $L(f)<g(n)$. Since we are only interested in lower bounds, 
it is sufficient to get enough trees to guarantee a positive probability. 

Given two variables $x,y$, we denote by $\mc{H}_{x,y}$ the family of trees with exactly two
children of the root being leaves labelled by $x$ and $y$, respectively, and with no siblings $x$ and
$\tilde y$, where $\tilde y\neq y$, in the first $g(n)$ levels. Let $H_{x,y}(z)$ be the generating
function of this family. Moreover, consider the family $\Pi_{x,y}$ of trees with root label $x$
and in which a leaf labelled by $x$ and a leaf labelled by $y$ cannot be siblings. The generating
function of this family is denoted by $\Pi_{x,y}(z)$. We generate trees by expanding a tree $t\in
\Pi_{x,y}$ with trees only from $\mc{H}_{x,y}$. Hence, an
expansion can easily be identified: the forbidden pattern of $t$ appears in
every tree of $\mc{H}_{x,y}$ among the children of the root. So, the topmost occurence (from
the root) of siblings $x$ and $y$ exhibits the location where the expansion took place. The second
condition (forbidden siblings $x$ and $\tilde y$) enables us to identify $y$. Finally, 
note that every such expansion is an $x$-premise expansion of $t$.

In order to derive an expression for $H_{x,y}(z)$ let us introduce the following operator: Let
$Q(z)$ be a generating function and set 
$$
\Psi(Q)=nz\exp\left(\sum_{i\ge 1} \frac{Q(z^i)-nz^i}i\right)((1-z)^{-n}-(n-1)z^2).
$$
If we assume that the combinatorial structure $\mc Q$ corresponding to $Q(z)$ is a tree class
related to our model, then the exponential term corresponds to a multiset of non-leaves. The last
factor corresponds to a multiset of leaves with a restriction on the multisets of size two.
Indeed, we subtract the $n-1$ forbidden multisets $\{x,\tilde y\}$. Therefore the combinatorial
structure which corresponds to $\Psi(Q)$ has the following property: Either the number of leaves
in the first level is different from two or the set of labels of the two leaves is different from
any set $\{x,\tilde y\}$ with $\tilde y\neq y$. Then we obtain 
$$
H_{x,y}(z)=nz^3(1-z)\exp\left(\sum_{i\ge 1}\frac{\tilde P(z^i)}i\right)
$$
where $\tilde P(z)=\Psi^{g(n)}(P)$. Here $\Psi^l$ denotes $l$ consecutive applications of $\Psi$.
Observe that $\tilde P(z)$ has the same dominant singularity $\eta$ as $P(z)$.


To count the number of trees of the family $\Pi_{x,y}$ let us first count the number $N_k$ of trees
where the root is unlabelled, it has exactly $k$ children, all those children are leaves, and the set
of the labels of these leaves does not contain the set $\{x,y\}$ as a subset. This is exactly the 
number of $k$-multisets of labels which contain at most one of the labels $x$ and $y$. 
The number of such trees without this restriction is given by
$\mc{Z}_k(n,n,\ldots,n)= \mc{Z}_k(\mathbf n)=\binom{n+k-1}k$ where $\mc{Z}_k$ denotes the cycle 
index of the symmetric group $S_k$. Moreover, the number of such trees with at least one leaf 
labelled by $x$ and one leaf labelled by $y$ is 
\begin{align*}
\sum_{l_x,l_y\geq 1}^{l_x+l_y\leq k} &\mc{Z}_{k-l_x-l_y}(n-2,n-2,\ldots,n-2)\\
&=\sum_{l=2}^k (l-1)\mc{Z}_{k-l}(n-2,n-2,\ldots,n-2)
= \sum_{l=2}^k (l-1) \mc{Z}_{k-l}(\mathbf{n}-2),
\end{align*}
which gives $N_k = \mc Z_k(\mathbf{n}) - \sum_{l=2}^k (l-1) \mc Z_{k-l}(\mathbf{n}-2)$. 

\begin{lem}
For $k\ge 0$ we have $N_k = \binom{n+k-1}k - (k-1)\binom{n+k-4}{k-2} + (n-2)\binom{n+k-4}{k-3}$.
\end{lem}

\begin{proof}
The well-known identity (see for example~\cite[page~174]{GKP94})
\[
\sum_{m=0}^M m\binom{x+m}m = (x+1) \sum_{m=1}^M \binom{x+1+m-1}{m-1} = (x+1) \binom{x+1+M}{M-1}
\]
yields 
\begin{align*}
N_k &= \binom{n+k-1}k - (k-1) \sum_{l=0}^{k-2} \binom{n-3+l}l 
+ \sum_{l=0}^{k-2} l \binom{n-3+l}l 
\\
&=  \binom{n+k-1}k - (k-1) \binom{n+k-4}{k-2} 
+ (n-2)\binom{n+k-4}{k-3}.
\end{align*}
\end{proof}

Let $D_{x,y}(z)$ be the generating function associated to the class $\mc D_{x,y}$ of trees in
which a leaf labelled by $x$ and a leaf labelled by $y$ cannot be siblings. Clearly, 
$D_{x,y}(z)=n\Pi_{x,y}(z)$. Decomposing $\mc D_{x,y}$ according to the number of leaves in the
first level we obtain
%Let $C(z)=\exp\left(\sum_{i\geq 1}\frac{D_{x,y}(z^i)-nz^i}{i}\right)$, then by symbolic arguments,
\begin{align*}
D_{x,y}(z)&=nz\exp\left(\sum_{i\geq 1}\frac{D_{x,y}(z^i)-nz^i}{i}\right)\sum_{k\ge 0}z^k N_k \\
&= nze^{D_{x,y}(z)}Q(z)
\end{align*} 
where 
\begin{align}
Q(z) &=\exp\left(\sum_{i\geq 2}\frac{D_{x,y}(z^i)-nz^i}{i}\right)\sum_{k\ge 0}z^k N_k \nonumber\\
&= (1-z)^n \exp\left(\sum_{i\geq 2}\frac{D_{x,y}(z^i)}{i}\right)\sum_{k\ge 0}z^k N_k \label{QQQ}
\end{align}

\begin{prop}
The singularity $\rho$ of $D_{x,y}$ verifies $\frac{\rho}{\eta} = 1+ \frac{d}{n^2} + \mc O(n^{-3})$,  
as $n\to \infty$, where $d$ is a non-negative constant. Moreover, the function $Q(z)$ given in~\eqref{QQQ}
is analytic in the domain $|z|\le \rho$.
\end{prop}

\begin{proof}
The second assertion is an immediate consequence of the first one, since the first one implies
$\rho\sim \nicefrac1{en}$. 

Note that $(z,D)=(\rho,D_{x,y}(\rho))$ is a solution of the system
\begin{equation} \label{Dsys}
\left\{
\begin{matrix}
D = nz e^D Q \\
1= nz e^D Q
\end{matrix}
\right.
\end{equation} 
where $Q=Q(z)$ is the function given in~\eqref{QQQ}. 
Moreover, $Q(0)=1$ and $D_{x,y}(0)=0$ immediately imply $\rho \sim \nicefrac1{en}$ when
$n\to\infty$. For further bootstrapping set $\rho \sim
\frac1{en}\left(1+\frac{\alpha}{n}\right)$. First we wish to get a more accurate asymptotic
expansion of $Q(\rho)$, as $n\to\infty$. Therefore, let us study the three factors in~\eqref{QQQ}
separately. Observe that 
\begin{align*}
(1-z)^n &= \left(1-\frac1{en}\left(1+\frac{\alpha}{n}\right)\right)^n\\
%&= \exp\left(n\ln \left(1-\frac1{en}\left(1+\frac{\alpha}{n}\right)\right) \right)\\
&= \exp \left(-n\ln \frac{1}{1-\frac1{en}\left(1+\frac{\alpha}{n}\right)}\right)\\
& = \exp \left(-\frac1{e}\left(1+\frac{\alpha}{n}\right) -
\frac1{2e^2n}\left(1+\frac{\alpha}{n}\right)^2 + \mc{O}\left(\frac1{n^2}\right)\right)\\
& =
\exp\left(-\frac1{e} -\frac{\alpha}{en}-\frac1{2e^2n} + \mc{O}\left(\frac1{n^2}\right)\right).
\end{align*}
Examination of the second factor yields 
\begin{align*}
\exp\left(\sum_{i\geq 2} \frac{D_{x,y}(z^i)}{i}\right) =\exp\left(\frac{n\rho^2}{2}+\mc
O\left(\frac1{n^2}\right)\right) = 1+ \frac{1}{2e^2n}+\mc O\left(\frac1{n^2}\right).
\end{align*}
Turning to the last factor, we obtain
\begin{align*}
&1 + n\rho + \frac{(n-1)(n+2)}{2}\rho^2 + \sum_{k\geq 3} \left[\binom{n+k-1}kz^k + \mc{O}
\left(n^{k-2}\rho^k\right)\right]\\
& \qquad = \sum_{k\geq 0} \frac1{k!}\left(1+\frac{\alpha}{n}\right)^k \left(\frac1{e}\right)^k +
\frac12\sum_{k\geq 2} \frac{n^{-1}}{e^k(k-2)!}\left(1+\frac{\alpha}{n}\right)^k  + 
\mc{O}\left(\frac1{n^2}\right)\\
& \qquad = \exp\left(\frac1{e}+\frac{\alpha}{en} \right)\left(1+ \frac1{2e^2n} +
\mc{O}\left(\frac1{n^2}\right)\right).
\end{align*}
Finally, collecting the contributions of the three factors gives 
$Q(\rho)=1+\frac1{2e^2n} + \mc{O}\left(\nicefrac1{n^2}\right)$, then the second equation of
\eqref{Dsys} implies $\rho =
\frac1{en}\left(1-\frac1{2e^2n}+\mc{O}\left(\frac1{n^2}\right)\right)$. Now, \eqref{eta} implies
the assertion, after all. 
\end{proof}

Now we are ready to turn to the Shannon effect. We add all the contributions coming from
expansions of a tree $t\in \Pi_{x,y}$, say of size $r$, by attaching a tree $t'\in \mc H_{x,y}$.
Note that there are $r$ positions where $t'$ can be attached and that
$\Pi_{x,y}(z)=\nicefrac{D_{x,y}(z)}n$. Finally, recall that $[z^m]R(z)\sim C\eta^{-m}m^{-3/2}$ for
$R(z)=P(z)$ as well as $R(z)=H_{x,y}(z)$ (possibly with different constants $C$) and
$[z^m]D_{x,y}(z)\sim C \rho^{-m} m^{-3/2}$, as $m\to\infty$. Hence we obtain
\begin{align}
\sum_{f: L(f)\leq g(n)}\mathbb{P}_n(f) 
&\geq \lim_{m\rightarrow \infty} \sum_{r\leq g(n)} \sum_{x\neq y} r \frac{[z^r]D_{x,y}(z)}{n} \frac{[z^{m-r}]
H_{x,y}(z)}{[z^m]P(z)} \notag\\
& = \lim_{m\rightarrow \infty} \sum_{x\neq y}  \sum_{r\leq L(f)} c r^{-\nicefrac12} \eta^{r+3} \rho^{-r}\notag\\
\label{beuh}& = \lim_{m\rightarrow \infty} c\eta^3n(n-1) \sum_{r\leq g(n)} r^{-\nicefrac12} u^r
\end{align}
where $u=\frac{\eta}{\rho} = 1- \frac{d}{n^2} + \mc{O}\left(\frac1{n^3}\right)$ and $c$ is a
positive constant. Therefore,
\begin{align*}
\sum_{L(f)\leq g(n)}\mathbb{P}_n(f)
&\geq \frac{c}{n} \int_0^{g(n)} \frac{u^r}{\sqrt{r}}dr\\
& = \frac{c}{n}\left( \frac{\sqrt{\pi}}{\sqrt{-\ln u}} - \int_{g(n)}^{\infty} \frac{u^r}{\sqrt{r}}dr\right)\\
& = \frac{c}{n} \left(\frac{\sqrt{\pi}}{\sqrt{-\ln u}} + \mc{O}\left(\frac{u^{g(n)}}{-\ln u \sqrt{g(n)}}\right)\right).
\end{align*}
We know that $u=1-\mathcal{O}\left(\frac1{n^2}\right)$, and thanks to~\eqref{beuh}, we can
conclude that $u=1-\Theta\left(\frac1{n^2}\right)$, because otherwise the right-hand side
of~\eqref{beuh} would tend to infinity while the left-hand side is a probability bounded by 1. Thus,
\begin{align*}
\frac{u^{g(n)}}{-\ln u \sqrt{g(n)}} = \frac{n^2}{d\sqrt{g(n)}}\left(1 +
\mc{O}\left(\frac1n\right)\right)
\left(1-\frac{d}{n^2}+ \mc{O}\left(\frac1{n^3}\right)\right)^{g(n)}
& = \Omega(n) \text{ if } g(n)=\mc{O}(n^2).\\
& = o(n) \text{ if } \frac{n^2}{g(n)} = o(1).
\end{align*}

Therefore, taking $g(n)$ such that $n^2=o(g(n))$ gives, as $n\to\infty$,
\begin{align*}
\sum_{L(f)\leq g(n)}\mathbb{P}_n(f)
& \geq \frac{c\sqrt{\pi}}{n}\frac1{\sqrt{-\ln u}} + o\left(1\right)
%&= \frac{c\sqrt{\pi}}{n}\cdot \frac{n}{\sqrt{d}}\\
 = \frac{c\sqrt{\pi}}{d} +o\left(1\right)
\end{align*}
with $\frac{c\sqrt{\pi}}{d}\neq 0$. We thus have shown the following result.

\begin{thm}
If $g(n)$ is a function in $n$ growing faster than $n^2$, then $\lim_{n\to \infty} \mathbb{P}_n(\{f |
L(f)\leq g(n)\}) \geq \alpha >0$. Consequently, there is no Shannon effect in our model.
\end{thm}


\section{Conclusion}


It is interesting to note here that the ideas developed in~\cite{FGGZ07} and in~\cite{FGGG11} in the implication model without commutativity
of the premises can be directly adapted to the present model with commutativity.
However, the singularity of the generating function of general trees, which is the fundamental key point of the analysis, cannot be explicitely determined.
This makes all computations more intricate in this model, and whereas in the previous model we got exact formulas, we must deal with
approximations here.
Finally, although both distributions on Boolean functions (with or without commutativity of the premises) are distinct, they are still quite
similar: in fact the order of magnitude of the probability of each fixed function is the same for both distributions
(cf. Theorem~\ref{prop:lambda}).
Moreover in both distributions there is no Shannon effect.

We have already noticed that in fact the probability distributions with or without associativity or commutativity in AND/OR trees are almost
identical (see~\cite{GGKM11}). Would it be possible to prove a meta-theorem that would give a relation between the probability distributions
induced by logical models taking some properties of the connectives into account, or not?

In this model of general implicational trees the connectives naturally disappear in the tree representation and consequently the size is the
number of occurrences of variables,
 or the total number of nodes in the tree. When we studied commutativity and associativity in AND/OR trees~\cite{GGKM11}
 we defined the size to be the number of leaves, which is equal to the number of variables. In the non-associative case,
this choice is equivalent to counting every node, because the number of internal nodes is equal to the number of leaves minus~one.
 But in general trees, there is no link between the number of leaves and the number of internal nodes and one could imagine different
 definitions of the size. Since in~\cite{GGKM11} we aimed to compare the distribution induced on Boolean functions of this
 model with the model without the properties of commutativity and associativity (see~\cite{kozik}), the complexity
 notion and therefore the size notion had to be kept.

But if we take into account the storage of the trees, the natural notion of size in general AND/OR trees is
 the total number of nodes, i.e. the number of connectives plus the number of occurrences of variables. We are currently working
 on this different notion size (\cite{GGKM12}), which induces a change of the notion of complexity:
 We expect that the induced distribution will be biased to functions of larger complexity in this model.



\bibliographystyle{plain}
\begin{thebibliography}{10}

\bibitem{CFGG04}
B.~Chauvin, P.~Flajolet, D.~Gardy, and B.~Gittenberger.
\newblock {A}nd/{O}r trees revisited.
\newblock {\em Combinatorics, Probability and Computing}, 13(4-5):475--497,
  July-September 2004.

\bibitem{DoGa84}
William~F. Dowling and Jean~H. Gallier.
\newblock Linear-time algorithms for testing the satisfiability of
  propositional {H}orn formulae.
\newblock {\em J. Logic Programming}, 1(3):267--284, 1984.

\bibitem{Drmota09}
M.~Drmota.
\newblock {\em Random {T}rees}.
\newblock Springer, Vienna-New York, 2009.

\bibitem{FlOd}
P.~Flajolet and A.~M. Odlyzko.
\newblock Singularity analysis of generating functions.
\newblock {\em In SIAM J. Discrete Math.}, 3:216--240, 1990.

\bibitem{FlSe}
P.~Flajolet and R.~Sedgewick.
\newblock {\em Analytic Combinatorics}.
\newblock Cambridge U.P., Cambridge, 2009.

\bibitem{FGGG11}
H.~Fournier, D.~Gardy, A.~Genitrini, and B.~Gittenberger.
\newblock The fraction of large random trees representing a given {B}oolean
  function in implicational logic.
\newblock {\em {R}andom {S}tructures and {A}lgorithms}, 40(3):317--349, 2012.

\bibitem{FGGZ07}
H.~Fournier, D.~Gardy, A.~Genitrini, and M.~Zaionc.
\newblock Classical and intuitionistic logic are asymptotically identical.
\newblock In Springer-Verlag, editor, {\em Annual Conference on Computer
  Science Logic (CSL)}, pages 177--193, Lausanne, Swiss, 2007.

\bibitem{G06}
D.~Gardy.
\newblock Random {B}oolean expressions.
\newblock In {\em Colloquium on Computational Logic and Applications},
  volume~AF, pages 1--36. DMTCS Proceedings, 2006.

\bibitem{GG10}
A.~Genitrini and B.~Gittenberger.
\newblock No {S}hannon effect on probability distributions on {B}oolean
  functions induced by random expressions.
\newblock In {\em 21st International Meeting on Probabilistic, Combinatorial
  and Asymptotic Methods for the Analysis of Algorithms}, Vienna, Austria, july
  2010. DMTCS Proceedings.

\bibitem{GGKM11}
A.~Genitrini, B.~Gittenberger, V.~Kraus, and C.~Mailler.
\newblock Associative and commutative tree representations for {B}oolean
  functions.
\newblock 2011.
\newblock submitted.

\bibitem{GGKM12}
A.~Genitrini, B.~Gittenberger, V.~Kraus, and C.~Mailler.
\newblock A new notion of complexity for random {B}oolean expressions., 2012.
\newblock Work in progress.

\bibitem{GKP94}
R.L. Graham, D.E. Knuth, and O.~Patashnik.
\newblock {\em Concrete {M}athematics: a {F}oundation for {C}omputer
  {S}cience}, volume~2.
\newblock Addison-Wesley Reading, MA, 1994.

\bibitem{Kos04}
Z.~Kostrzycka.
\newblock On the density of truth in {G}rzegorczyk's modal logic.
\newblock {\em Bull. Sect. Logic Univ. \L\'od\'z}, 33(2):107--120, 2004.

\bibitem{Kos06}
Z.~Kostrzycka.
\newblock On the density of truth in modal logics.
\newblock In {\em Mathematics and Computer Science}, volume~AG, pages 161--170,
  Nancy (France), September 2006. DMTCS Proceedings.

\bibitem{KoZa04}
Z.~Kostrzycka and M.~Zaionc.
\newblock Statistics of intuitionistic versus classical logics.
\newblock {\em Studia Logica}, 76(3):307--328, 2004.

\bibitem{kozik}
J.~Kozik.
\newblock Subcritical pattern languages for {A}nd/{O}r trees.
\newblock In {\em Fifth Colloquium on Mathematics and Computer Science},
  Blaubeuren, Germany, september 2008. DMTCS Proceedings.

\bibitem{LS97}
H.~Lefmann and P.~Savick\'y.
\newblock Some typical properties of large {A}nd/{O}r {B}oolean formulas.
\newblock {\em Random Structures and Algorithms}, 10:337--351, 1997.

\bibitem{Mat05}
G.~Matecki.
\newblock Asymptotic density for equivalence.
\newblock {\em Electronic Notes in Theoretical Computer Science}, 140:81--91,
  2005.

\bibitem{PVW94}
J.~B. Paris, A.~Vencovsk\'a, and G.~M. Wilmers.
\newblock A natural prior probability distribution derived from the
  propositional calculus.
\newblock {\em Annals of Pure and Applied Logic}, 70:243--285, 1994.

\end{thebibliography}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
