Boole's expansion theorem (original) (raw)
Die Shannon-Zerlegung oder Shannon-Expansion (benannt nach Claude Elwood Shannon) stellt eine Möglichkeit dar, boolesche Funktionen mithilfe ihrer sogenannten Kofaktoren darzustellen. Die mathematische Aussage über diese Zerlegung wird auch als Entwicklungssatz von Shannon bezeichnet. Obwohl der Satz nach Shannon benannt ist, der ihn erstmals 1949 verwendete, wurde er bereits etwa hundert Jahre zuvor von George Boole aufgestellt.
| Property | Value |
|---|---|
| dbo:abstract | Die Shannon-Zerlegung oder Shannon-Expansion (benannt nach Claude Elwood Shannon) stellt eine Möglichkeit dar, boolesche Funktionen mithilfe ihrer sogenannten Kofaktoren darzustellen. Die mathematische Aussage über diese Zerlegung wird auch als Entwicklungssatz von Shannon bezeichnet. Obwohl der Satz nach Shannon benannt ist, der ihn erstmals 1949 verwendete, wurde er bereits etwa hundert Jahre zuvor von George Boole aufgestellt. (de) Boole's expansion theorem, often referred to as the Shannon expansion or decomposition, is the identity: , where is any Boolean function, is a variable, is the complement of , and and are with the argument set equal to and to respectively. The terms and are sometimes called the positive and negative Shannon cofactors, respectively, of with respect to . These are functions, computed by restrict operator, and (see valuation (logic) and partial application). It has been called the "fundamental theorem of Boolean algebra". Besides its theoretical importance, it paved the way for binary decision diagrams (BDDs), satisfiability solvers, and many other techniques relevant to computer engineering and formal verification of digital circuits.In such engineering contexts (especially in BDDs), the expansion is interpreted as a if-then-else, with the variable being the condition and the cofactors being the branches ( when is true and respectively when is false). (en) L'expansion de Shannon est, en logique, la décomposition d'une équation booléenne selon une ou plusieurs variables principales. Elle consiste en l'identité suivante, vraie quelle que soit la fonction : où est une formule booléenne, est une variable, est la négation de , et les formules et sont obtenus à partir de en affectant à et respectivement. (fr) In elettronica digitale il teorema di Shannon è un importante teorema riguardante le funzioni booleane principalmente usato per scomporre una funzione complessa in funzioni più semplici o per ottenere un'espressione canonica da una tabella della verità o da un'espressione non canonica. Nonostante sia attribuito a Claude Shannon, il teorema è stato enunciato per primo da George Boole. (it) В математике разложением Шеннона или декомпозицией Шеннона по переменной называется метод представления булевой функции от переменных в виде суммы двух подфункций от остальных переменных. Хотя этот метод часто приписывают Клоду Шеннону, но Буль доказал его гораздо раньше, а сама возможность такого разложения по любой из переменной непосредственно вытекает из возможности определения любой булевой функции с помощью таблицы истинности. (ru) 香农展开（英語：Shannon's expansion），或称香农分解（Shannon decomposition）是对布尔函数的一种变换方式。它可以将任意布尔函数表达为其中任何一个变量乘以一个子函数，加上这个变量的反变量乘以另一个子函数。 例如： 可以抽取其中的变量 及其反变量 （ 取反），而得到 对逻辑函数使用香农展开，就可以使用抽取的变量作为一个选择信号，然后用数据选择器来实现该函数。 (zh) |
| dbo:wikiPageExternalLink | https://web.archive.org/web/20070927201537/http:/homepages.ius.edu/JFDOYLE/c421/html/Chapter6.htm http://www1.cs.columbia.edu/~sedwards/papers/soviani2007optimizing.pdf |
| dbo:wikiPageID | 2733707 (xsd:integer) |
| dbo:wikiPageLength | 7884 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121119300 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Boolean_differential_calculus dbr:Conditional_(computer_programming) dbr:Claude_Shannon dbr:George_Boole dbr:Product_of_Sums dbr:Computer_engineering dbr:Partial_application dbr:Distributive_property dbr:Exclusive_or dbr:Formal_verification dbr:Binary_decision_diagrams dbc:Boolean_algebra dbr:Binary_decision_diagram dbc:Theorems_in_lattice_theory dbr:Boolean_function dbr:Boolean_satisfiability_problem dbr:Identity_(mathematics) dbr:Reed–Muller_expansion dbr:Multiplexer dbr:Valuation_(logic) dbr:Unate_function dbr:Switching_circuit_theory dbr:The_Laws_of_Thought dbr:Sum_of_Products dbr:Disjunction |
| dbp:cs1Dates | y (en) |
| dbp:date | May 2019 (en) |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Use_dmy_dates |
| dct:subject | dbc:Boolean_algebra dbc:Theorems_in_lattice_theory |
| rdf:type | yago:WikicatTheorems yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | Die Shannon-Zerlegung oder Shannon-Expansion (benannt nach Claude Elwood Shannon) stellt eine Möglichkeit dar, boolesche Funktionen mithilfe ihrer sogenannten Kofaktoren darzustellen. Die mathematische Aussage über diese Zerlegung wird auch als Entwicklungssatz von Shannon bezeichnet. Obwohl der Satz nach Shannon benannt ist, der ihn erstmals 1949 verwendete, wurde er bereits etwa hundert Jahre zuvor von George Boole aufgestellt. (de) L'expansion de Shannon est, en logique, la décomposition d'une équation booléenne selon une ou plusieurs variables principales. Elle consiste en l'identité suivante, vraie quelle que soit la fonction : où est une formule booléenne, est une variable, est la négation de , et les formules et sont obtenus à partir de en affectant à et respectivement. (fr) In elettronica digitale il teorema di Shannon è un importante teorema riguardante le funzioni booleane principalmente usato per scomporre una funzione complessa in funzioni più semplici o per ottenere un'espressione canonica da una tabella della verità o da un'espressione non canonica. Nonostante sia attribuito a Claude Shannon, il teorema è stato enunciato per primo da George Boole. (it) В математике разложением Шеннона или декомпозицией Шеннона по переменной называется метод представления булевой функции от переменных в виде суммы двух подфункций от остальных переменных. Хотя этот метод часто приписывают Клоду Шеннону, но Буль доказал его гораздо раньше, а сама возможность такого разложения по любой из переменной непосредственно вытекает из возможности определения любой булевой функции с помощью таблицы истинности. (ru) 香农展开（英語：Shannon's expansion），或称香农分解（Shannon decomposition）是对布尔函数的一种变换方式。它可以将任意布尔函数表达为其中任何一个变量乘以一个子函数，加上这个变量的反变量乘以另一个子函数。 例如： 可以抽取其中的变量 及其反变量 （ 取反），而得到 对逻辑函数使用香农展开，就可以使用抽取的变量作为一个选择信号，然后用数据选择器来实现该函数。 (zh) Boole's expansion theorem, often referred to as the Shannon expansion or decomposition, is the identity: , where is any Boolean function, is a variable, is the complement of , and and are with the argument set equal to and to respectively. The terms and are sometimes called the positive and negative Shannon cofactors, respectively, of with respect to . These are functions, computed by restrict operator, and (see valuation (logic) and partial application). (en) |
| rdfs:label | Shannon-Zerlegung (de) Boole's expansion theorem (en) Teorema di Shannon (elettronica) (it) Expansion de Shannon (fr) Разложение Шеннона (ru) 香农展开 (zh) |
| owl:sameAs | freebase:Boole's expansion theorem yago-res:Boole's expansion theorem wikidata:Boole's expansion theorem dbpedia-de:Boole's expansion theorem dbpedia-fr:Boole's expansion theorem dbpedia-it:Boole's expansion theorem dbpedia-ru:Boole's expansion theorem dbpedia-zh:Boole's expansion theorem https://global.dbpedia.org/id/29enp |
| prov:wasDerivedFrom | wikipedia-en:Boole's_expansion_theorem?oldid=1121119300&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Boole's_expansion_theorem |
| is dbo:notableIdea of | dbr:George_Boole__George_Boole__1 |
| is dbo:wikiPageRedirects of | dbr:Shannon's_Expansion_Theorem dbr:Shannon_cofactor dbr:Boole's_expansion dbr:Boole-Shannon_expansion dbr:Boole_expansion dbr:Boole–Shannon_expansion dbr:Shannon's_expansion dbr:Fundamental_theorem_of_Boolean_algebra dbr:Shannon's_expansion_theorem dbr:Shannon_decomposition dbr:Shannon_expansion |
| is dbo:wikiPageWikiLink of | dbr:Boolean_differential_calculus dbr:Shannon's_Expansion_Theorem dbr:George_Boole dbr:Shannon_cofactor dbr:Boole's_expansion dbr:Boole-Shannon_expansion dbr:Boole_expansion dbr:Boole–Shannon_expansion dbr:Boolean_function dbr:Shannon's_expansion dbr:Fundamental_theorem_of_Boolean_algebra dbr:Shannon's_expansion_theorem dbr:Shannon_decomposition dbr:Shannon_expansion |
| is dbp:notableIdeas of | dbr:George_Boole |
| is foaf:primaryTopic of | wikipedia-en:Boole's_expansion_theorem |