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 = ? ,
,
, Let ? and ? be connectives. If ? is not pseudo-monotone and ? is monotone
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 ,
Term rewriting and all that, 1998. ,
Boolean functions and Post's lattice with applications to complexity theory, 2002. ,
Size-depth tradeoffs for Boolean formulae, Information Processing Letters, vol.49, issue.3, pp.151-155, 1994. ,
, Alternation. J. ACM, vol.28, issue.1, pp.114-133, 1981.
Composition of Post classes and normal forms of Boolean functions, Discrete Mathematics, vol.306, issue.24, pp.3223-3243, 2006. ,
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
An algorithm for producing median formulas for Boolean functions, Proc. of the Reed Muller 2011 Workshop, pp.49-54, 2011. ,
, Decompositions of functions based on arity gap. Discrete Mathematics, vol.312, pp.238-247, 2012.
URL : https://hal.archives-ouvertes.fr/hal-01090606
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
Boolean functions: Theory, algorithms, and applications, 2011. ,
Post classes characterized by functional terms, Discrete Applied Mathematics, vol.142, issue.1, pp.35-51, 2004. ,
The existence of k-valued closed classes having no finite basis, Doklady Akademii Nauk SSSR, vol.127, issue.1, pp.44-46, 1959. ,
Function Algebras on Finite Sets: Basic Course on Many-Valued Logic and Clone Theory, 2006. ,
Weighted lattice polynomials, Discrete Mathematics, vol.309, issue.4, pp.814-820, 2009. ,
The Two-Valued Iterative Systems of Mathematical Logic, Annals of Mathematical Studies, vol.5, pp.1-122, 1941. ,
On essential variables of functions, especially in the algebra of logic, Annales Academiae Scientiarum Fennicae, Series A I, vol.339, p.11, 1963. ,
The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, pp.216-226, 1978. ,
The synthesis of two-terminal switching circuits, Bell Labs Technical Journal, vol.28, issue.1, pp.59-98, 1949. ,
On time-hardware complexity tradeoffs for boolean functions, Proceedings of the 4th Hawaii Symposium on System Sciences, pp.525-527, 1971. ,
Complete sets of logical functions, Trans. Amer. Math. Soc, vol.51, pp.117-132, 1942. ,
Essential arities of term operations in finite algebras, Discrete Mathematics, vol.149, issue.1-3, pp.239-259, 1996. ,