N. Nfss, However we conjecture that non-monotonic (quasi-)Sheffer NFSs are strictly more efficient than other NFSs. To motivate our intuition, consider the set of terms ? = T (?) where ? := [(x 1 ?x 2 ) ? (¬x 1 ?x 3 )]. Observe that ? is not pseudo-monotone since ?(x 1 , 1, 0) ? x 1 and ?(x 1 , 0, 1) ? ¬x 1 . Also, from the equivalences ?(x 1 , 0, 1) ? ¬x 1 , and ?(x 1 , x 2 , 0) ? x 1 ?x 2, The case of non-monotonic NFSs still eludes us

, Lemma 58. For any set of terms T (?¬) (resp. T (?)), ? T (?¬) (resp. T (?))

, By Boole's expansion theorem (also known as Shannon's decomposition [18]), for any connective ? of arity n: ?(x 1

, As ?j, |t j | x j = 1, T (?¬) ? ?. By Proposition 35, ? T (?¬)

, However, the converse seems unlikely, due to the fact that ? is neither

. .. , Assume now that t = ?(t 1 , . . . , t n ) for some terms t 1, projection, which is clearly increasing in the i-th argument. If t = ¬t for some term t such that [t ] is increasing (decreasing, resp.) in the i-th argument, then [t] is decreasing (increasing, resp.) in the i-th argument

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

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, issue.3, 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.

M. Couceiro)-université-de-lorraine, . Cnrs, L. Inria, and F. , , p.1062

G. Dresden, E. Lehtonen@tu-dresden, and . De, Current address: Centro de Matemática e Aplicações, Faculdade de Ciências e Tecnologia, pp.2829-516