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 ,
,
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, issue.3, 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. ,
, , p.1062
, Current address: Centro de Matemática e Aplicações, Faculdade de Ciências e Tecnologia, pp.2829-516