RUS  ENG
Full version
JOURNALS // Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika // Archive

Izv. Vyssh. Uchebn. Zaved. Mat., 2011 Number 11, Pages 72–77 (Mi ivm8396)

This article is cited in 3 papers

Brief communications

Iterated Boolean functions in the elementary basis

A. A. Voronenko, V. S. Fedorova, D. V. Chistikov

Chair of Mathematical Cybernetics, Moscow State University, Moscow, Russia

Abstract: We establish a new criterion for a Boolean function to be read-once over the basis of conjunction, disjunction, and negation. We prove that each Boolean function is either read-once or has a set of four or six input vectors such that values of this function on these vectors show that it is iterated. We use this criterion to deduce an alternative proof of the known Stetsenko criterion.

Keywords: read-once Boolean function, criterion.

UDC: 519.716

Presented by the member of Editorial Board: N. K. Zamov
Received: 25.05.2011


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2011, 55:11, 61–65

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024