Minimal contact circuits for a sequence of Boolean functions
type: Item
instance of: scholarly article
title: Minimal contact circuits for a sequence of Boolean functions
zbMATH Open document ID: 1497.94202
DOI: 10.1134/S0001434621070178
published in: Mathematical Notes
publication date: 2021-08-25T00:00:00Z
review text: In this paper the author develops a sequence of Boolean functions \[ \begin{array}{l} p_1(\tilde x,\tilde y)-p_1(x_1,y_1)=x_1y_1 \\ p_{n}(\tilde x,\tilde y)-p_n(x_1,\ldots ,x_n,y_1\ldots ,y_n)=x_1y_1\lor (x_1\lor y_1)p_{n-1}(x_2,\ldots ,x_n,y_2,\ldots,y_n)\\ n=2,3,\ldots \end{array} \] It is easy to see that the function \(p_n(x,y)\) specifies the transfer to the highest \((n + 1)\)-digit of the sum that occurs when two \(n\)-digit binary numbers \(x\) and \(y\) are added arithmetically (it is assumed that \(x_1,y_1\) are the highest digits). The following theorem is proved: Theorem. To implement the transfer function \(p_n(x,y)\) by a contact circuit, it is necessary and sufficient to have \(4n-2\) contacts. The resulting estimate is a contribution to mathematical theory of Control Systems.
reviewed by: Nikolay Kyurkchiev
Mathematics Subject Classification ID: 94C11
Mathematics Subject Classification ID: 68Q06
zbMATH DE Number: 7384978
zbMATH Keywords: Boolean function
zbMATH Keywords: contact circuit
zbMATH Keywords: complexity of circuit
author: Nikolay P. Red'kin
MaRDI profile type: Publication
cites work: Minimal contact circuits for symmetric threshold functions
cites work: Q4242301
cites work: Q2968777
full work available at URL: s0001434621070178
OpenAlex ID: W3195704069
description: scientific article; zbMATH DE number 7384978