On Two-Level Exclusive-or Majority Networks

It is shown that not all Boolean functions can be realized by a two-level EXCLUSIVE-OR majority network. However, if repeats at the first level are allowed, then it is shown that such a network is universal. A minimal weight vector with respect to this latter network is defined. By using the restric...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 1974-01, Vol.C-23 (1), p.34-41
Main Authors: Robbins, W.E., Rudolph, L.D.
Format: Article
Language:English
Subjects:
Majority gate
restricted-affine-group (RAG) equivalence
threshold logic
two-level EXCLUSIVE-OR majority network
two-level EXCLUSIVE-OR weighted majority network
universal networks
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:It is shown that not all Boolean functions can be realized by a two-level EXCLUSIVE-OR majority network. However, if repeats at the first level are allowed, then it is shown that such a network is universal. A minimal weight vector with respect to this latter network is defined. By using the restricted-affine-group (RAG) equivalence of Boolean functions, it is shown that if two functions are in the same RAG class, then they are realized by the same minimal weight vector to within permutations and/or sign changes.
ISSN:0018-9340
1557-9956
DOI:10.1109/T-C.1974.223774