. .. , Then x i appears in exactly one of the subterms t 1, resp.) in the i-th argument, then [t] is decreasing (increasing, resp.) in the i-th argument. Assume now that t = ?

.. .. ?-?-;-b),

, Let ? and ? be connectives. If ? is not pseudo-monotone and ? is monotone

.. ?-{1, n} such that ? is neither increasing nor decreasing in the i-th argument. Let t be a term in T (?¬) such that [t] = ?. By Proposition 59, we must have |t| x i > 1. Consider now the following terms in T (?): s 1 := ?(x 1, Assume now that ? is a monotone connective and ? is an n-ary connective that is not pseudo-monotone. Then there is an index i

F. Baader and T. Nipkow, Term rewriting and all that, 1998.

E. Böhler and H. Vollmer, Boolean functions and Post's lattice with applications to complexity theory, 2002.

M. L. Bonet and S. R. Buss, Size-depth tradeoffs for Boolean formulae, Information Processing Letters, vol.49, issue.3, pp.151-155, 1994.

A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer, Alternation. J. ACM, vol.28, issue.1, pp.114-133, 1981.

M. Couceiro, S. Foldes, and E. Lehtonen, Composition of Post classes and normal forms of Boolean functions, Discrete Mathematics, vol.306, issue.24, pp.3223-3243, 2006.

M. Couceiro and E. Lehtonen, Galois theory for sets of operations closed under permutation, cylindrification and composition. Algebra Universalis, vol.67, pp.273-297, 2012.
URL : https://hal.archives-ouvertes.fr/hal-01090609

M. Couceiro, E. Lehtonen, J. Marichal, and T. Waldhauser, An algorithm for producing median formulas for Boolean functions, Proc. of the Reed Muller 2011 Workshop, pp.49-54, 2011.

M. Couceiro, E. Lehtonen, and T. Waldhauser, Decompositions of functions based on arity gap. Discrete Mathematics, vol.312, pp.238-247, 2012.
URL : https://hal.archives-ouvertes.fr/hal-01090606

M. Couceiro, E. Lehtonen, and T. Waldhauser, A survey on the arity gap. Multiple-Valued Logic and Soft Computing, vol.24, pp.223-249, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01093666

Y. Crama and P. L. Hammer, Boolean functions: Theory, algorithms, and applications, 2011.

S. Foldes and G. R. Pogosyan, Post classes characterized by functional terms, Discrete Applied Mathematics, vol.142, issue.1, pp.35-51, 2004.

I. I. Ianov and A. A. Muchnik, The existence of k-valued closed classes having no finite basis, Doklady Akademii Nauk SSSR, vol.127, issue.1, pp.44-46, 1959.

D. Lau, Function Algebras on Finite Sets: Basic Course on Many-Valued Logic and Clone Theory, 2006.

J. Marichal, Weighted lattice polynomials, Discrete Mathematics, vol.309, issue.4, pp.814-820, 2009.

E. L. Post, The Two-Valued Iterative Systems of Mathematical Logic, Annals of Mathematical Studies, vol.5, pp.1-122, 1941.

A. Salomaa, On essential variables of functions, especially in the algebra of logic, Annales Academiae Scientiarum Fennicae, Series A I, vol.339, p.11, 1963.

T. J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, pp.216-226, 1978.

C. Shannon, The synthesis of two-terminal switching circuits, Bell Labs Technical Journal, vol.28, issue.1, pp.59-98, 1949.

P. Spira, On time-hardware complexity tradeoffs for boolean functions, Proceedings of the 4th Hawaii Symposium on System Sciences, pp.525-527, 1971.

W. Wernick, Complete sets of logical functions, Trans. Amer. Math. Soc, vol.51, pp.117-132, 1942.

R. Willard, Essential arities of term operations in finite algebras, Discrete Mathematics, vol.149, issue.1-3, pp.239-259, 1996.