An Entity of Type: software, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases, and where each type of case is checked to see if the proposition in question holds. This is a method of direct proof. A proof by exhaustion typically contains two stages: In the Curry–Howard isomorphism, proof by exhaustion and case analysis are related to ML-style pattern matching.

Property Value
dbo:abstract
  • Důkaz rozborem případů neboli dokonalá indukce nebo důkaz hrubou silou je metoda matematického důkazu založená na tom, že dokazované tvrzení se rozpadne na konečný počet dílčích případů a důkaz je podán zvlášť pro každý z těchto dílčích případů. Důkaz tedy sestává ze dvou fází: 1. * Dokáže se, že seznam dílčích případů je vyčerpávající, tedy že každá instance tvrzení se dá zahrnout aspoň do jednoho z nich. 2. * Pro každý z dílčích případů se zvlášť provede důkaz tvrzení. Příklad: Dokažme tvrzení Je-li číslo m třetí mocninou nějakého přirozeného čísla, pak se neliší o víc než o jednu od nějakého přirozeného násobku devíti. Označme jako n přirozené číslo, jehož je m třetí mocninou. Každé n je buď a) samo násobkem tří, nebo b) je o jednu vyšší než nějaký přirozený násobek tří, nebo konečně c) je o jednu nižší než nějaký přirozený násobek tří. Tyto tři kategorie odpovídají třem možným zbytkům po dělení přirozeného čísla třemi, tedy 0, 1 a 2, takže pokrývají všechny možnosti. Pro každou z těchto tří kategorií n zvlášť dokážeme uvedené tvrzení. a) Je-li n násobkem tří, lze ho napsat jako 3p, a pak n3 = 27p3, což je přímo dělitelné devíti.b) Je-li n = 3p + 1, tak podle binomické věty n3 = 27p3 + 27p2 + 9p + 1, což je o jednu vyšší než násobek devíti 27p3 + 27p2 + 9p.c) Je-li n = 3p − 1, tak podobně n3 = 27p3 − 27p2 + 9p − 1, což je o jednu menší než násobek devíti. Protože tvrzení platí pro všechny možné tři typy n, z nichž m mohlo vzniknout umocněním na třetí, musí platit obecně, a tím je dokázáno. (cs)
  • La demostración por casos es un método de demostración matemática en el cual la proposición a ser probada se divide en un número finito de casos, y cada caso es demostrado por separado. También se la conoce como demostración exhaustiva, demostración por agotamiento o método de fuerza bruta. Una demostración por casos consta de dos etapas: * Una prueba de que los casos son exhaustivos; es decir, que cada instancia de la proposición a ser probada coincide con las condiciones de (al menos) uno de los casos. * Una demostración de cada uno de los casos. Por el contrario, el método exhaustivo del matemático griego Eudoxo de Cnidos era una forma geométrica y esencialmente rigurosa de calcular límites matemáticos. (es)
  • Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases, and where each type of case is checked to see if the proposition in question holds. This is a method of direct proof. A proof by exhaustion typically contains two stages: 1. * A proof that the set of cases is exhaustive; i.e., that each instance of the statement to be proved matches the conditions of (at least) one of the cases. 2. * A proof of each of the cases. The prevalence of digital computers has greatly increased the convenience of using the method of exhaustion (e.g., the first computer-assisted proof of four color theorem in 1976), though such approaches can also be challenged on the basis of mathematical elegance. Expert systems can be used to arrive at answers to many of the questions posed to them. In theory, the proof by exhaustion method can be used whenever the number of cases is finite. However, because most mathematical sets are infinite, this method is rarely used to derive general mathematical results. In the Curry–Howard isomorphism, proof by exhaustion and case analysis are related to ML-style pattern matching. (en)
  • Le raisonnement par disjonction de cas est une forme de raisonnement mathématique qui consiste à décomposer la proposition que l'on cherche à démontrer en un nombre fini de cas (sous-propositions) vérifiés indépendamment. * Portail des mathématiques (fr)
  • Een bewijs door gevalsonderscheiding of bewijs door uitputting is een manier om een wiskundig bewijs te leveren. Deze manier maakt er gebruik van de gevraagde stelling in verschillende gevallen te knippen en elk geval afzonderlijk te bewijzen. De gevallen waarin de stelling wordt opgeknipt moeten wel uitputtend zijn, het moet dus duidelijk zijn dat alle gevallen zijn te noemen en te onderscheiden. Wanneer dan is aangetoond dat de stelling voor alle gevallen geldt, is de stelling zelf daarmee bewezen. Voorbeelden * De stelling dat voor ieder natuurlijk getal geldt dat even is. Om dit te bewijzen kan men onderscheid maken tussen het geval dat even of oneven is. Is even, dan is dat als veelvoud van ook. Is oneven dan is even en is dus als veelvoud van ook even. * Het eerste bewijs dat door Appel en Haken in 1976 werd gegeven van de vierkleurenstelling. Zij onderscheidden 1936 gevallen, waarvan zij met behulp van de computer de kleurbaarheid met 4 kleuren aantoonden. * Aangenomen wordt dat TC Hales het vermoeden van Kepler met behulp van gevalsonderscheiding heeft bewezen, dus dat er een dichtste bolstapeling is. (nl)
  • Força bruta e ignorância, em matemática, é o método que consiste em provar algum teorema (ou apresentar algum contra-exemplo) pelo método exaustivo de calcular cada caso possível. Algumas vezes abreviado, em inglês, como BFI (de brute force and ignorance). (pt)
  • 穷举法,亦称作分类证明、分类分析证明、完全归纳法或暴力法,是一种数学证明方法, 它将所求证的命题分为有限种情形或是等价情形的集合,接著依每种类型分别检验该命题是否成立,此乃一种法。 穷举法证明包括两阶段: 1. * 证明分类是完全的, 也就是说每一个待证的个例皆符合(至少)一类情形的条件; 2. * 分别对每一类情形给出证明。 计算机(電腦)的普及大大提升了穷举法的易用性,计算机专家系统可用窮舉法解答許多问题。理论上而言,穷举法适用于任何有限情形,然而因数学的大部分集合是无限的,此法鲜少能够用以导出一般的数学结论。 在柯里-霍华德同构(Curry–Howard correspondence)中,穷举法与ML-型模式匹配相关联。 (zh)
dbo:wikiPageID
  • 359970 (xsd:integer)
dbo:wikiPageInterLanguageLink
dbo:wikiPageLength
  • 6916 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1108317128 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
gold:hypernym
rdf:type
rdfs:comment
  • Le raisonnement par disjonction de cas est une forme de raisonnement mathématique qui consiste à décomposer la proposition que l'on cherche à démontrer en un nombre fini de cas (sous-propositions) vérifiés indépendamment. * Portail des mathématiques (fr)
  • Força bruta e ignorância, em matemática, é o método que consiste em provar algum teorema (ou apresentar algum contra-exemplo) pelo método exaustivo de calcular cada caso possível. Algumas vezes abreviado, em inglês, como BFI (de brute force and ignorance). (pt)
  • 穷举法,亦称作分类证明、分类分析证明、完全归纳法或暴力法,是一种数学证明方法, 它将所求证的命题分为有限种情形或是等价情形的集合,接著依每种类型分别检验该命题是否成立,此乃一种法。 穷举法证明包括两阶段: 1. * 证明分类是完全的, 也就是说每一个待证的个例皆符合(至少)一类情形的条件; 2. * 分别对每一类情形给出证明。 计算机(電腦)的普及大大提升了穷举法的易用性,计算机专家系统可用窮舉法解答許多问题。理论上而言,穷举法适用于任何有限情形,然而因数学的大部分集合是无限的,此法鲜少能够用以导出一般的数学结论。 在柯里-霍华德同构(Curry–Howard correspondence)中,穷举法与ML-型模式匹配相关联。 (zh)
  • Důkaz rozborem případů neboli dokonalá indukce nebo důkaz hrubou silou je metoda matematického důkazu založená na tom, že dokazované tvrzení se rozpadne na konečný počet dílčích případů a důkaz je podán zvlášť pro každý z těchto dílčích případů. Důkaz tedy sestává ze dvou fází: 1. * Dokáže se, že seznam dílčích případů je vyčerpávající, tedy že každá instance tvrzení se dá zahrnout aspoň do jednoho z nich. 2. * Pro každý z dílčích případů se zvlášť provede důkaz tvrzení. Příklad: Dokažme tvrzení (cs)
  • La demostración por casos es un método de demostración matemática en el cual la proposición a ser probada se divide en un número finito de casos, y cada caso es demostrado por separado. También se la conoce como demostración exhaustiva, demostración por agotamiento o método de fuerza bruta. Una demostración por casos consta de dos etapas: * Una prueba de que los casos son exhaustivos; es decir, que cada instancia de la proposición a ser probada coincide con las condiciones de (al menos) uno de los casos. * Una demostración de cada uno de los casos. (es)
  • Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases, and where each type of case is checked to see if the proposition in question holds. This is a method of direct proof. A proof by exhaustion typically contains two stages: In the Curry–Howard isomorphism, proof by exhaustion and case analysis are related to ML-style pattern matching. (en)
  • Een bewijs door gevalsonderscheiding of bewijs door uitputting is een manier om een wiskundig bewijs te leveren. Deze manier maakt er gebruik van de gevraagde stelling in verschillende gevallen te knippen en elk geval afzonderlijk te bewijzen. De gevallen waarin de stelling wordt opgeknipt moeten wel uitputtend zijn, het moet dus duidelijk zijn dat alle gevallen zijn te noemen en te onderscheiden. Wanneer dan is aangetoond dat de stelling voor alle gevallen geldt, is de stelling zelf daarmee bewezen. (nl)
rdfs:label
  • Důkaz rozborem případů (cs)
  • Demostración por casos (es)
  • Raisonnement par disjonction de cas (fr)
  • Proof by exhaustion (en)
  • Bewijs door gevalsonderscheiding (nl)
  • Força bruta e ignorância (pt)
  • 穷举法 (zh)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License