| dbpprop:abstract
|
- Structural induction is a proof method that is used in mathematical logic (e.g. , the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction. Structural recursion is a recursion method bearing the same relationship to structural induction as ordinary recursion bears to ordinary mathematical induction. In general, the idea is that one wishes to prove some proposition P(x), where x is any instance of some sort of recursively-defined structure such as lists or trees. A well-founded partial order is defined on the structures ("sublist" for lists and "subtree" for trees). The structural induction proof is a proof that the proposition holds for all the minimal structures, and that if it holds for the immediate substructures of a certain structure S, then it must hold for S also. (Formally speaking, this then satisfies the premises of an axiom of well-founded induction, which asserts that these two conditions are sufficient for the proposition to hold for all x. ) A structurally recursive function uses the same idea to define a recursive function: "base cases" handle each minimal structure and a rule for recursion. Structural recursion is usually proved correct by structural induction; in particularly easy cases, the inductive step is often left out. The length and ++ functions in the example below are structurally recursive. For example, if the structures are lists, one usually introduces the partial order '<' in which L < M whenever list L is the tail of list M. Under this ordering, the empty list is the unique minimal element. A structural induction proof of some proposition P(l) then consists of two parts: A proof that P is true, and a proof that if P(L) is true for some list L, and if L is the tail of list M, then P(M) must also be true. Eventually, there may exist more than one base case, and/or more than one inductive case, depending on how the function or structure was constructed. In those cases, a structural induction proof of some proposition P(l) then consists of: A) a proof that P(BC) is true for each base case BC, and B): a proof that if P(I) is true for some instance I, and M can be obtained from I by applying any one recursive rule once, then P(M) must also be true.
- Die strukturelle Induktion ist ein Beweisverfahren, das unter anderem in der Logik, der theoretischen Informatik und der Graphentheorie eingesetzt wird. Es handelt sich um eine allgemeinere Form der vollständigen Induktion. Mit dem Verfahren lassen sich Aussagen über die Elemente von rekursiv aufgebauten Mengen beweisen. Bei der vollständigen Induktion werden Eigenschaften der natürlichen Zahlen bewiesen; bei der strukturellen Induktion werden Eigenschaften für Mengen bewiesen, deren Elemente aus Grundelementen durch eine endliche Anzahl von Konstruktionsschritten (unter Verwendung bereits konstruierter Elemente) bzw. mittels eines Erzeugungssystems entstehen. Es gibt also minimale Elemente und rekursiv definierte Elemente der Menge. Bei den natürlichen Zahlen ist das Grundelement <math>0</math> und der Konstruktionsschritt ist der Übergang von einer Zahl <math>n</math> zur Zahl <math>n+1</math>. Um eine Aussage für die Elemente einer Menge zu beweisen, zeigt man im Induktionsanfang die Gültigkeit der Aussage für die einfachsten Elemente und im Induktionsschluss die Gültigkeit der Aussage für die rekursiv gebildeten Elemente unter der Voraussetzung, dass die Aussage für die in der Konstruktion verwendeten Elemente gilt. Ist beides erfüllt, so gilt die Aussage für alle Elemente. Man führt die Induktion also über den strukturellen Aufbau der Elemente. Strukturelle Induktion ist ein Spezialfall der Induktion für Mengen mit einer wohlfundierten (partiellen) Ordnung.
- La inducción estructurada es un método de demostración utilizado en Lógica matemática, teoría de los grafos, Computación y en otras áreas. Se trata de una generalización de la inducción matemática. Dado un conjunto <math>C</math> con un orden parcial bien fundamentado <math><</math> sobre sus elementos, la prueba de una propiedad <math>P(x)</math> para todo elemento <math>x</math> de <math>C</math> se realiza por inducción estructural basándose en la siguiente regla de inferencia: <math>\frac{\forall x:x\in C:\Rightarrow P(x)}{\forall x:x\in C:P(x)} La prueba por inducción estructural consiste en demostrar que una proposición se cumple para todos los elementos mínimos del tipo, y que si la propiedad se cumple para todas las subestructuras de una cierta estructura S, entonces se debe cumplir también para S. Por ejemplo, si la estructura es una lista, normalmente se introduce el orden parcial '<' tal que L < M siempre que exista x tal que x::L=M Bajo este orden, la lista vacía es el único elemento mínimo. Así, una prueba por inducción estructural de una proposición P(l) consta de dos partes: Una prueba de P y una prueba de P(L) implica P.
- Indukcja strukturalna to dość powszechnie stosowany wariant indukcji matematycznej, w którym rozważa się pewien zbiór termów uporządkowany następującą relacją: jeden term jest mniejszy od drugiego wtedy i tylko wtedy, gdy jest jego podtermem. Zasada indukcji strukturalnej głosi, co następuje. Jeśli udowodnimy, że pewną własność mają wszystkie termy atomowe (czyli takie, które nie zawierają żadnych właściwych podtermów) oraz że dla każdego n-arnego symbolu funkcyjnego <math>f</math> z tego, że własność tę mają termy <math>x_1,\cdots,x_n</math>, wynika, że ma ją również term <math>f(x_1,\cdots,x_n)</math>, to mają ją wszystkie termy.
- A indução estrutural é um método de demonstração que é usado na lógica matemática (por exemplo, para provar teoremas), em ciência da computação, em teoria dos grafos, e alguns outros campos da matemática. Podemos dizer que é uma generalização do método de indução matemática. A recursão estrutural é um método de recursão que está para a indução estrutural assim como a recursão ordinária está para a indução matemática usual. Em geral, a idéia é que se deseja demonstrar alguma proposição P(x), onde x é alguma instância de algum tipo de estrutura recursivamente definida, tais como listas ou árvores. Uma ordem parcial bem-fundada (Well-founded) é definida sobre as estruturas. Indução estrutural é um método de demonstração em que a proposição vale para todas as estruturas minimais, e que se valer para as subestruturas de uma determinada estrutura S, então deverá valer para S também. Uma função estruturalmente recursiva usa a mesma idéia de modo a definir uma função recursiva: "os casos base" dão conta de cada estrutura minimal e se há regras para o caso recursivo. A recursão estrutural é geralmente demonstrada correta através da indução estrutural; em casos mais triviais, a etapa indutiva é deixada frequentemente de fora da prova. A função comprimento (length) e a função concatenação são estruturalmente recursivas e mostradas no exemplo abaixo. Por exemplo, imagine que as estruturas que vamos utilizar sejam listas, agora introduza uma ordem parcial ‘<’ na qual L < M. Essa ordem parcial indica que a lista L é a cauda da lista M. Segundo esta ordem parcial, o único elemento minimal é quando temos a lista vazia . Uma demonstração por indução estrutural de alguma proposição P(L) consiste então em duas partes: Uma demonstração de que P é verdadeiro, e uma demonstração que se P(L) for verdadeiro para alguma lista L, e se L < M (L for a cauda de uma lista M), então P(M) também deve ser verdadeiro.
- Структурная индукция — метод доказательства, который используется в математической логике (например, доказательство и теоремы Łoś, информатика, теория графа, и некоторые другие математические области. Это — обобщение математической индукции. Структурная рекурсия — метод рекурсии, имеющий те же самые отношения к структурной индукции как обычные рекурсии к обычной математической индукции.
- 结构归纳法 是应用在数理逻辑、计算机科学、图论和一些其他数学领域中的一种证明方法(比如Los's 定理的证明)。它是一种特殊化的数学归纳法。 通常，它用来证明一些命题P(x)，x是一些递归定义的结构（例如树和表）中的一种。一个良基偏序是定义在这种结构上的。结构归纳法的证明是由证明命题对于所有的极小结构成立，以及如果他在一个结构S的基础结构中成立，那么它一定也在整个S中成立这些组成。比如，如果一个结构是个这样一个表，含有偏序 '<'，只要表 L 在表M的尾部，那么L < M。在这样的排序中，空的list是唯一的最小元素。结构归纳法中，一些命题P(l) 的证明由两个部分组成： 证明P成立 如果P(L) 在表L中成立， 如果L 是表 M的底部， 那么P(M) 也成立。
|
| rdfs:comment
|
- Structural induction is a proof method that is used in mathematical logic (e.g. , the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction. Structural recursion is a recursion method bearing the same relationship to structural induction as ordinary recursion bears to ordinary mathematical induction.
- Die strukturelle Induktion ist ein Beweisverfahren, das unter anderem in der Logik, der theoretischen Informatik und der Graphentheorie eingesetzt wird. Es handelt sich um eine allgemeinere Form der vollständigen Induktion. Mit dem Verfahren lassen sich Aussagen über die Elemente von rekursiv aufgebauten Mengen beweisen.
- La inducción estructurada es un método de demostración utilizado en Lógica matemática, teoría de los grafos, Computación y en otras áreas. Se trata de una generalización de la inducción matemática.
- Indukcja strukturalna to dość powszechnie stosowany wariant indukcji matematycznej, w którym rozważa się pewien zbiór termów uporządkowany następującą relacją: jeden term jest mniejszy od drugiego wtedy i tylko wtedy, gdy jest jego podtermem. Zasada indukcji strukturalnej głosi, co następuje.
- A indução estrutural é um método de demonstração que é usado na lógica matemática (por exemplo, para provar teoremas), em ciência da computação, em teoria dos grafos, e alguns outros campos da matemática. Podemos dizer que é uma generalização do método de indução matemática. A recursão estrutural é um método de recursão que está para a indução estrutural assim como a recursão ordinária está para a indução matemática usual.
- Структурная индукция — метод доказательства, который используется в математической логике (например, доказательство и теоремы Łoś, информатика, теория графа, и некоторые другие математические области. Это — обобщение математической индукции.
|
![[RDF Data]](/statics/sw-cube.png)
