Structural induction
http://dbpedia.org/resource/Structural_induction an entity of type: Software
構造的帰納法(英: structural induction)とは、数学的帰納法を一般化した証明手法の一つ。数理論理学、計算機科学、グラフ理論などの数学分野で使用される。 構造的再帰(structural recursion)は再帰の手法の一つ。通常の再帰が数学的帰納法と関係を持つのと同様に、構造的再帰は構造的帰納法と関係を持つ。
rdf:langString
Indukcja strukturalna – 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 z tego, że własność tę mają termy wynika, że ma ją również term to mają ją wszystkie termy.
rdf:langString
结构归纳法是应用在数理逻辑、计算机科学、图论和一些其他数学领域的证明方法（比如Łoś定理的证明），是一般化的数学归纳法 （数学归纳法仅仅定义在自然数上）。 其通常用来证明一些命题 P（x），x 是递归定义结构（例如树和表）的一种。良基偏序是定义在这种结构上的。结构归纳法的证明是由证明命题对于所有的极小结构成立，以及如果他在一个结构 S 的基础结构中成立，那么其一定也在整个 S 中成立这些组成。比如，如果一个结构是个这样一个表，含有偏序 '<'，只要表 L 在表 M 的尾部，那么 L < M。在这样的排序中，空的 list[ ] 是唯一的最小元素。结构归纳法中，一些命题 P（l） 的证明由两个部分组成：
* 证明 P（[]）成立
* 如果 P（L） 在表 L 中成立， 如果 L 是表 M 的底部， 那么 P（M） 也成立。
rdf:langString
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 (zum Beispiel Mengen von Listen, Formeln, Graphen) beweisen. Strukturelle Induktion ist ein Spezialfall der Induktion für Mengen mit einer wohlfundierten (partiellen) Ordnung.
rdf:langString
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 otras áreas. Se trata de una generalización de la inducción matemática. Dado un conjunto con un orden parcial bien fundamentado sobre sus elementos, la prueba de una propiedad para todo elemento de se realiza por inducción estructural basándose en la siguiente regla de inferencia:
rdf:langString
En mathématiques et davantage en informatique, la définition récursive ou induction structurelle est un procédé de définition conjointe d'un type (classe ou ensemble) et d'objets (éléments) qui le compose au moyen de règles de construction (constructeurs) qui agencent ou structurent ces objets.
rdf:langString
Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction over natural numbers and can be further generalized to arbitrary Noetherian induction. Structural recursion is a recursion method bearing the same relationship to structural induction as ordinary recursion bears to ordinary mathematical induction.
rdf:langString
Structurele inductie of structuurinductie is een bewijsmethode waarmee bewezen kan worden dat een bepaalde eigenschap geldt voor alle elementen van een inductief gedefinieerde verzameling. Het is een vorm van wiskundige inductie. Een inductief (of recursief) gedefinieerde verzameling bestaat uit een aantal basisobjecten en wordt vervolgens afgesloten onder een aantal operaties. Voorbeelden van inductief gedefinieerde verzamelingen zijn logische formules, wiskundige termen, en veel structuren uit de theoretische informatica, zoals bomen. Het idee achter structuurinductie is dat als
rdf:langString
Структурная индукция — конструктивный метод математического доказательства, обобщающий математическую индукцию (применяемую над натуральным рядом) на произвольные рекурсивно определённые частично упорядоченные совокупности. Структурная рекурсия — реализация структурной индукции в форме определения, процедуры доказательства или программы, обеспечивающая индукционный переход над частично упорядоченной совокупностью.
rdf:langString
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.
rdf:langString
Структу́рна інду́кція — конструктивний метод математичного доведення, який узагальнює математичну індукцію (застосовувану над натуральним рядом) на довільні рекурсивно означені частково впорядковані сукупності. Структурна рекурсія — реалізація структурної індукції у формі визначення, процедури доведення або програми, що забезпечує індукційний перехід над частково впорядкованою сукупністю.
rdf:langString
rdf:langString
Strukturelle Induktion
rdf:langString
Inducción estructural
rdf:langString
Induction structurelle
rdf:langString
構造的帰納法
rdf:langString
Indukcja strukturalna
rdf:langString
Structurele inductie
rdf:langString
Structural induction
rdf:langString
Indução estrutural
rdf:langString
Структурная индукция
rdf:langString
结构归纳法
rdf:langString
Структурна індукція
xsd:integer
211399
xsd:integer
1108317419
rdf:langString
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 (zum Beispiel Mengen von Listen, Formeln, Graphen) 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 (auch: einfachste oder Grund-)Elemente und rekursiv definierte (oder: rekursiv gebildete) Elemente der Menge.Bei den natürlichen Zahlen ist das Grundelement (oder , je nach Definition der natürlichen Zahlen) und der Konstruktionsschritt ist der Übergang von einer Zahl zur Zahl . 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.
rdf:langString
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 otras áreas. Se trata de una generalización de la inducción matemática. Dado un conjunto con un orden parcial bien fundamentado sobre sus elementos, la prueba de una propiedad para todo elemento de se realiza por inducción estructural basándose en la siguiente regla de inferencia: 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(x::L).
rdf:langString
En mathématiques et davantage en informatique, la définition récursive ou induction structurelle est un procédé de définition conjointe d'un type (classe ou ensemble) et d'objets (éléments) qui le compose au moyen de règles de construction (constructeurs) qui agencent ou structurent ces objets. L'on peut ainsi définir des nombres, des listes, des arbres, des relations, et plus généralement, toute structure mathématique (langage, système, …). En permettant par le même principe de définir un prédicat total[pas clair] i.e. qui est défini partout, l'induction structurelle est aussi une méthode de démonstration d'une propriété sur une structure.
rdf:langString
Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction over natural numbers and can be further generalized to arbitrary Noetherian induction. Structural recursion is a recursion method bearing the same relationship to structural induction as ordinary recursion bears to ordinary mathematical induction. Structural induction is used to prove that some proposition P(x) holds for all x of some sort of recursively defined structure, such asformulas, lists, or trees. A well-founded partial order is defined on the structures ("subformula" for formulas, "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: 1.
* a proof that P(BC) is true for each base case BC, 2.
* 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.
rdf:langString
構造的帰納法(英: structural induction)とは、数学的帰納法を一般化した証明手法の一つ。数理論理学、計算機科学、グラフ理論などの数学分野で使用される。 構造的再帰(structural recursion)は再帰の手法の一つ。通常の再帰が数学的帰納法と関係を持つのと同様に、構造的再帰は構造的帰納法と関係を持つ。
rdf:langString
Structurele inductie of structuurinductie is een bewijsmethode waarmee bewezen kan worden dat een bepaalde eigenschap geldt voor alle elementen van een inductief gedefinieerde verzameling. Het is een vorm van wiskundige inductie. Een inductief (of recursief) gedefinieerde verzameling bestaat uit een aantal basisobjecten en wordt vervolgens afgesloten onder een aantal operaties. Voorbeelden van inductief gedefinieerde verzamelingen zijn logische formules, wiskundige termen, en veel structuren uit de theoretische informatica, zoals bomen. Het idee achter structuurinductie is dat als 1.
* alle mogelijke basisobjecten een bepaalde eigenschap hebben; en 2.
* alle manieren om een nieuw object te maken uit oude objecten waarvoor die eigenschap geldt, weer een object opleveren waarvoor geldt de eigenschap dan geldt voor alle objecten in de verzameling. Inductie in het algemeen is een bewijsmethode die gebruikt kan worden voor welgefundeerde verzamelingen (verzamelingen met een welgefundeerde ordening). Structuurinductie onderscheidt zich van inductie op de natuurlijke getallen (volledige inductie) omdat de gebruikte ordening niet totaal is. Bovendien wordt de ordening meestal impliciet gedefinieerd in de inductieve definite. De kleinste objecten zijn de basisobjecten en wanneer objecten samengesteld worden ontstaat een groter object. Structuurinductie komt vaak voor binnen de algebra, logica, theoretische informatica en andere gebieden waarin formules, termen, lijsten, programma's en andere inductief gedefinieerde verzamelingen een rol spelen. In de grondslagen van de wiskunde worden de natuurlijke getallen soms inductief als volgt gedefinieerd:
* (nul) is een natuurlijk getal.
* Als een natuurlijk getal is, dan is ook (lees: opvolger van , of ) een natuurlijk getal.
* Niets anders is een natuurlijk getal. Als we de natuurlijke getallen zo definiëren, is de volledige inductie op natuurlijke getallen een speciaal geval van structuurinductie; dat wil zeggen, dat structuurinductie een generalisatie van volledige inductie is.
rdf:langString
Indukcja strukturalna – 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 z tego, że własność tę mają termy wynika, że ma ją również term to mają ją wszystkie termy.
rdf:langString
Структурная индукция — конструктивный метод математического доказательства, обобщающий математическую индукцию (применяемую над натуральным рядом) на произвольные рекурсивно определённые частично упорядоченные совокупности. Структурная рекурсия — реализация структурной индукции в форме определения, процедуры доказательства или программы, обеспечивающая индукционный переход над частично упорядоченной совокупностью. Изначально метод использовался в математической логике, также нашёл применение в теории графов, комбинаторике, общей алгебре, математической лингвистике, но наибольшее распространение как самостоятельно изучаемый метод получил в теоретической информатике, где применяется в вопросах семантики языков программирования, формальной верификации, вычислительной сложности, функционального программирования. В отличие от — наиболее общей формы математической индукции, применяемой над произвольными фундированными множествами, — в понятии о структурной индукции подразумевается конструктивный характер, вычислительная реализация. При этом фундированность совокупности — свойство, необходимое для рекурсивной определяемости, таким образом, структурную рекурсию можно считать частным вариантом нётеровой индукции.
rdf:langString
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 ideia é 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 (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 ideia 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 seL < M (L for a cauda de uma lista M), então P(M) também deve ser verdadeiro.
rdf:langString
Структу́рна інду́кція — конструктивний метод математичного доведення, який узагальнює математичну індукцію (застосовувану над натуральним рядом) на довільні рекурсивно означені частково впорядковані сукупності. Структурна рекурсія — реалізація структурної індукції у формі визначення, процедури доведення або програми, що забезпечує індукційний перехід над частково впорядкованою сукупністю. Спочатку метод використовувався в математичній логіці, також знайшов застосування в теорії графів, комбінаториці, загальній алгебрі, математичній лінгвістиці, але найбільшого поширення як самостійно досліджуваний метод набув у теоретичній інформатиці, де застосовується в питаннях семантики мов програмування, формальної верифікації, обчислювальної складності, функційного програмування. На відміну від нетерівської індукції — найзагальнішої форми математичної індукції, застосовуваної над довільними фундованими множинами, — в понятті про структурну індукцію мається на увазі конструктивний характер, обчислювальна реалізація. При цьому фундованість сукупності — властивість, необхідна для рекурсивної ви́значності, таким чином, структурну рекурсію можна вважати частковим варіантом нетерівської індукції.
rdf:langString
结构归纳法是应用在数理逻辑、计算机科学、图论和一些其他数学领域的证明方法（比如Łoś定理的证明），是一般化的数学归纳法 （数学归纳法仅仅定义在自然数上）。 其通常用来证明一些命题 P（x），x 是递归定义结构（例如树和表）的一种。良基偏序是定义在这种结构上的。结构归纳法的证明是由证明命题对于所有的极小结构成立，以及如果他在一个结构 S 的基础结构中成立，那么其一定也在整个 S 中成立这些组成。比如，如果一个结构是个这样一个表，含有偏序 '<'，只要表 L 在表 M 的尾部，那么 L < M。在这样的排序中，空的 list[ ] 是唯一的最小元素。结构归纳法中，一些命题 P（l） 的证明由两个部分组成：
* 证明 P（[]）成立
* 如果 P（L） 在表 L 中成立， 如果 L 是表 M 的底部， 那么 P（M） 也成立。
xsd:nonNegativeInteger
11760
