This article is cited in 2 papers

Short notes

A circuit of depth two with limited input branching for voting function

Yu. A. Kombarov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: We show that majority Boolean function of $n$ variables can be computed by a depth-2 circuit consisting of majority gates with fan-in $n-2$ (for every odd $n$ greater than 5).

Key words: Boolean circuits, Boolean functions, majority function, bounded fan-in.

UDC: 519.95

Received: 27.12.2017

 English version: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2018, 73:5, 196–198

Bibliographic databases:

• 
• 
• 
•