Scholarlink

Abstract <p> The exact value of the complexity of the circuit implementation of an arbitrary Boolean function in a certain basis consisting of negation and all monotone Boolean functions is found. The complexity of a function is defined as the least number of basis elements sufficient to construct a circuit implementation of this function. </p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

The Exact Circuit Complexity of Boolean Functions in an Infinite Basis

  • 期刊论文

  • 发表日期：

    2025年4月1日

查看全文
  • V. V. Kochergin,
  • A. V. Mikhailovich

摘要

Abstract

The exact value of the complexity of the circuit implementation of an arbitrary Boolean function in a certain basis consisting of negation and all monotone Boolean functions is found. The complexity of a function is defined as the least number of basis elements sufficient to construct a circuit implementation of this function.