翻訳と辞書
Words near each other
・ Boole & Babbage
・ Boole (band)
・ Boole (crater)
・ Boole (disambiguation)
・ Boole (tree)
・ Boole polynomials
・ Boole's expansion theorem
・ Boole's inequality
・ Boole's rule
・ Boole's syllogistic
・ Boolean
・ Boolean algebra
・ Boolean algebra (structure)
・ Boolean algebras canonically defined
・ Boolean analysis
Boolean circuit
・ Boolean conjunctive query
・ Boolean data type
・ Boolean delay equation
・ Boolean domain
・ Boolean expression
・ Boolean function
・ Boolean grammar
・ Boolean hierarchy
・ Boolean model (probability theory)
・ Boolean network
・ Boolean operation
・ Boolean operations on polygons
・ Boolean prime ideal theorem
・ Boolean ring


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Boolean circuit : ウィキペディア英語版
Boolean circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for 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 also used as a formal model for combinational logic in digital electronics.
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.
== Formal definition ==
In giving a formal definition of Boolean circuits, Vollmer starts by defining a basis set ''B'' of Boolean functions, corresponding to the gates allowable in the circuit model. A Boolean circuit over a basis ''B'', with ''n'' inputs and ''m'' outputs, is then defined as a finite directed acyclic graph. Each vertex corresponds to either a basis function or one of the inputs, and there is a set of exactly ''m'' nodes which are labeled as the outputs.〔Vollmer 1999, p. 8.〕 The edges must also have some ordering, to distinguish between different arguments to the same Boolean function.〔Vollmer 1999, p. 9.〕
As a special case, a propositional formula or Boolean expression is a Boolean circuit with a single output node in which every other node has fan-out of 1. Thus, a Boolean circuit can be regarded as a generalization that allows shared subformulas and multiple outputs.
A common basis for Boolean circuits is the set , from which all other Boolean functions can be constructed.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Boolean circuit」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.