Editing Linear separability (section)

== Threshold logic ==
A linear threshold logic gate is a Boolean function defined by <math>n</math> weights <math>w_1, \dots, w_n</math> and a threshold <math>\theta</math>. It takes <math>n</math> binary inputs <math>x_1, \dots, x_n</math>, and outputs 1 if <math>\sum_i w_i x_i > \theta</math>, and otherwise outputs 0. 

For any fixed <math>n</math>, because there are only finitely many Boolean functions that can be computed by a threshold logic unit, it is possible to set all <math>w_1, \dots, w_n, \theta</math> to be integers. Let <math>W(n)</math> be the smallest number <math>W</math> such that every possible real threshold function of <math>n</math> variables can be realized using integer weights of absolute value <math>\leq W</math>. It is known that<ref>{{Cite journal |last=Alon |first=Noga |last2=Vũ |first2=Văn H |date=1997-07-01 |title=Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs |url=https://linkinghub.elsevier.com/retrieve/pii/S0097316597927801 |journal=Journal of Combinatorial Theory, Series A |volume=79 |issue=1 |pages=133–160 |doi=10.1006/jcta.1997.2780 |issn=0097-3165}}</ref><math display="block">\frac 12 n \log n - 2n + o(n) \leq \log_2 W(n) \leq \frac 12 n \log n - n + o(n)</math>See <ref>{{Cite book |last=Jukna |first=Stasys |title=Boolean Function Complexity: Advances and Frontiers |date=2012 |publisher=Springer Berlin Heidelberg |isbn=978-3-642-24507-7 |series=Algorithms and Combinatorics |location=Berlin, Heidelberg}}</ref>{{Pg|location=Section 11.10}} for a literature review.