Enumeration of Boolean Functions Sheffer with Constants

Teruo HIKITA

Enumeration of Boolean Functions Sheffer with Constants

Teruo HIKITA

Full Text Views

0

Cite this

Summary :

A Sheffer function is a Boolean function such that one can produce all Boolean functions by using it as a sole basic logic element, and a typical example is the NAND operation. Here we investigate two variations of this concept, that is, Sheffer with constants" and Sheffer with constants under uniform composition". These are considered as more suitable assumptions complying with real electronic circuitry. Our new results in this paper are two explicit formulas, one for the number of n-variable functions Sheffer with constants, and the other for that of those uniformly Sheffer with constants. In particular, it is shown that almost all functions are Sheffer with constants when n is large. Some numerical values of these numbers are calculated in the range of 1n6.

Publication: IEICE TRANSACTIONS on transactions Vol.E65-E No.12 pp.714-716

Publication Date: 1982/12/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Digital Circuits

Authors

Teruo HIKITA

Keyword

Cite this

Copy

Teruo HIKITA, "Enumeration of Boolean Functions Sheffer with Constants" in IEICE TRANSACTIONS on transactions, vol. E65-E, no. 12, pp. 714-716, December 1982, doi: .
Abstract: A Sheffer function is a Boolean function such that one can produce all Boolean functions by using it as a sole basic logic element, and a typical example is the NAND operation. Here we investigate two variations of this concept, that is, Sheffer with constants" and Sheffer with constants under uniform composition". These are considered as more suitable assumptions complying with real electronic circuitry. Our new results in this paper are two explicit formulas, one for the number of n-variable functions Sheffer with constants, and the other for that of those uniformly Sheffer with constants. In particular, it is shown that almost all functions are Sheffer with constants when n is large. Some numerical values of these numbers are calculated in the range of 1n6.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e65-e_12_714/_p

Copy

@ARTICLE{e65-e_12_714,
author={Teruo HIKITA, },
journal={IEICE TRANSACTIONS on transactions},
title={Enumeration of Boolean Functions Sheffer with Constants},
year={1982},
volume={E65-E},
number={12},
pages={714-716},
abstract={A Sheffer function is a Boolean function such that one can produce all Boolean functions by using it as a sole basic logic element, and a typical example is the NAND operation. Here we investigate two variations of this concept, that is, Sheffer with constants" and Sheffer with constants under uniform composition". These are considered as more suitable assumptions complying with real electronic circuitry. Our new results in this paper are two explicit formulas, one for the number of n-variable functions Sheffer with constants, and the other for that of those uniformly Sheffer with constants. In particular, it is shown that almost all functions are Sheffer with constants when n is large. Some numerical values of these numbers are calculated in the range of 1n6.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Enumeration of Boolean Functions Sheffer with Constants
T2 - IEICE TRANSACTIONS on transactions
SP - 714
EP - 716
AU - Teruo HIKITA
PY - 1982
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E65-E
IS - 12
JA - IEICE TRANSACTIONS on transactions
Y1 - December 1982
AB - A Sheffer function is a Boolean function such that one can produce all Boolean functions by using it as a sole basic logic element, and a typical example is the NAND operation. Here we investigate two variations of this concept, that is, Sheffer with constants" and Sheffer with constants under uniform composition". These are considered as more suitable assumptions complying with real electronic circuitry. Our new results in this paper are two explicit formulas, one for the number of n-variable functions Sheffer with constants, and the other for that of those uniformly Sheffer with constants. In particular, it is shown that almost all functions are Sheffer with constants when n is large. Some numerical values of these numbers are calculated in the range of 1n6.
ER -