|
Lupanov Representation
Lupanov's (''k'', ''s'')-representation, named after Oleg Lupanov, is a means of representing Boolean circuits to demonstrate an asymptotically tight upper bound on the circuit size (i.e., the number of gates) needed to represent a Boolean function. Claude Shannon showed that almost all Boolean functions of ''n'' variables need a circuit of size at least 2''n''''n''−1. Lupanov's (''k'', ''s'')-representation shows that all Boolean functions of ''n'' variables can be computed with a circuit of 2''n''''n''−1 + o(2''n''''n''−1) gates. Definition The idea is to represent the values of a boolean function ''ƒ'' in a table of 2''k'' rows, representing the possible values of the ''k'' first variables ''x''1, ..., ,''x''''k'', and 2''n''−''k'' columns representing the values of the other variables. Let ''A''1, ..., ''A''''p'' be a partition of the rows of this table such that for ''i'' < ''p'', , ''A'' [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Oleg Lupanov
Oleg Borisovich Lupanov (; 2 June 1932 – 3 May 2006) was a Soviet and Russian mathematician, dean of the Moscow State University's Faculty of Mechanics and Mathematics (1980–2006), head of the Chair of Discrete Mathematics of the Faculty of Mechanics and Mathematics (1981–2006). Oleg Borisovich Lupanov, a Russian Wikipedia entry Together with his graduate school advisor, Sergey Yablonsky, he is considered one of the founders of the Soviet school of Mathematical Cybernetics. In particular he authored pioneering works on synthesis and complexity of Boolean circuits, and of control systems in general (), the term used in the USSR and Russia for a generalization of finite-state automata, Boolean circuits and multi-valued logic circuits. Ingo Wegener, in his book ''The Complexity of Boolean Functions,'' I. Wegener, The Complexity of Boolean Function John Wiley and Sons Ltd, and B. G. Teubner, Stuttgart, 1987. page 87. credits O. B. Lupanov for coining the term '' Claude Sh ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Boolean Circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input length. Boolean circuits are defined in terms of the logic gates they contain. For example, a circuit might contain binary AND and OR gates and unary NOT gates, or be entirely described by binary NAND gates. Each gate corresponds to some Boolean function that takes a fixed number of bits as input and outputs a single bit. Boolean circuits provide a model for many digital components used in computer engineering, including multiplexers, adders, and arithmetic logic units, but they exclude sequential logic. They are an abstraction that omits many aspects relevant to designing real digital logic circuits, such as metastability, fanout, glitches, power consumption, and propagation delay variability. Formal definition In givi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Circuit Complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits C_,C_,\ldots (see below). Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes. For example, a prominent circuit class P/poly consists of Boolean functions computable by circuits of polynomial size. Proving that \mathsf\not\subseteq \mathsf would separate P and NP (see below). Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0, NC1, NC, and P/poly. Size and depth A Boolean circuit with n input bits is a directed acyclic graph in which every node (usually called ''gates'' in this context) is either an input node of in-degree 0 l ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Boolean Function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function (or logical function), used in logic. Boolean functions are the subject of Boolean algebra and switching theory. A Boolean function takes the form f:\^k \to \, where \ is known as the Boolean domain and k is a non-negative integer called the arity of the function. In the case where k=0, the function is a constant element of \. A Boolean function with multiple outputs, f:\^k \to \^m with m>1 is a vectorial or ''vector-valued'' Boolean function (an S-box in symmetric cryptography). There are 2^ different Boolean functions with k arguments; equal to the number of different truth tables with 2^k entries. Every k-ary Boolean function can be expressed as a propositional formula in k variables x_1,...,x_k, and two propositional formulas a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Claude Shannon
Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American mathematician, electrical engineer, computer scientist, cryptographer and inventor known as the "father of information theory" and the man who laid the foundations of the Information Age. Shannon was the first to describe the use of Boolean algebra—essential to all digital electronic circuits—and helped found artificial intelligence (AI). Roboticist Rodney Brooks declared Shannon the 20th century engineer who contributed the most to 21st century technologies, and mathematician Solomon W. Golomb described his intellectual achievement as "one of the greatest of the twentieth century". At the University of Michigan, Shannon dual degreed, graduating with a Bachelor of Science in electrical engineering and another in mathematics, both in 1936. A 21-year-old master's degree student in electrical engineering at MIT, his thesis, "A Symbolic Analysis of Relay and Switching Circuits", demonstrated that electric ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Boolean Algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denoted by 1 and 0, whereas in elementary algebra the values of the variables are numbers. Second, Boolean algebra uses logical operators such as Logical conjunction, conjunction (''and'') denoted as , disjunction (''or'') denoted as , and negation (''not'') denoted as . Elementary algebra, on the other hand, uses arithmetic operators such as addition, multiplication, subtraction, and division. Boolean algebra is therefore a formal way of describing logical operations in the same way that elementary algebra describes numerical operations. Boolean algebra was introduced by George Boole in his first book ''The Mathematical Analysis of Logic'' (1847), and set forth more fully in his ''An Investigation of the Laws of Thought'' (1854). According to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
