login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A064436 Number of switching functions of n or fewer variables which cannot be realized as threshold gates. 5
0, 0, 2, 152, 63654, 4294872724, 18446744073694523482, 340282366920938463463374607423390140592, 115792089237316195423570985008687907853269984665640564039457583990351590086990 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

The corresponding systems of linear inequalities are not solvable: linearly non-separable truth or switching functions. Truth functions which ar "non-neurons" and are realizable only as two levels threshold gate networks.

LINKS

Wang Lan, Table of n, a(n) for n = 0..9

FORMULA

a(n) = 2^(2^n) - A000609(n).

EXAMPLE

n=2: out of the 16 B^2 -> B^1 truth functions, 14 are linearly separable; the 2 exceptions are XOR and its negation: f(x,y) = !xz + x!y and !f(x,y) = xy + !x!y. So a(2)=2. With increasing n, the chance that a switching function belongs to this sequence tends to 1.

CROSSREFS

Cf. A000609.

Sequence in context: A102458 A206309 A265880 * A012605 A012602 A157087

Adjacent sequences:  A064433 A064434 A064435 * A064437 A064438 A064439

KEYWORD

nonn

AUTHOR

Labos Elemer, Oct 01 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 05:29 EDT 2019. Contains 328315 sequences. (Running on oeis4.)