Démonstration (logique et mathématiques)vignette| : un des plus vieux fragments des Éléments d'Euclide qui montre une démonstration mathématique. En mathématiques et en logique, une démonstration est un ensemble structuré d'étapes correctes de raisonnement. Dans une démonstration, chaque étape est soit un axiome (un fait acquis), soit l'application d'une règle qui permet d'affirmer qu'une proposition, la conclusion, est une conséquence logique d'une ou plusieurs autres propositions, les prémisses de la règle.
Démonstration constructiveUne première vision d'une démonstration constructive est celle d'une démonstration mathématique qui respecte les contraintes des mathématiques intuitionnistes, c'est-à-dire qui ne fait pas appel à l'infini, ni au principe du tiers exclu. Ainsi, démontrer l'impossibilité de l'inexistence d'un objet ne constitue pas une démonstration constructive de son existence : il faut pour cela en exhiber un et expliquer comment le construire. Si une démonstration est constructive, on doit pouvoir lui associer un algorithme.
Théorie de la démonstrationLa théorie de la démonstration, aussi connue sous le nom de théorie de la preuve (de l'anglais proof theory), est une branche de la logique mathématique. Elle a été fondée par David Hilbert au début du . Hilbert a proposé cette nouvelle discipline mathématique lors de son célèbre exposé au congrès international des mathématiciens en 1900 avec pour objectif de démontrer la cohérence des mathématiques.
Proof (truth)A proof is sufficient evidence or a sufficient argument for the truth of a proposition. The concept applies in a variety of disciplines, with both the nature of the evidence or justification and the criteria for sufficiency being area-dependent. In the area of oral and written communication such as conversation, dialog, rhetoric, etc., a proof is a persuasive perlocutionary speech act, which demonstrates the truth of a proposition.
Proof by contradictionIn logic, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts this kind of nonconstructive proof as universally valid. More broadly, proof by contradiction is any form of argument that establishes a statement by arriving at a contradiction, even when the initial assumption is not the negation of the statement to be proved.
Algorithme gloutonUn algorithme glouton (greedy algorithm en anglais, parfois appelé aussi algorithme gourmand, ou goulu) est un algorithme qui suit le principe de réaliser, étape par étape, un choix optimum local, afin d'obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l'algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton.
Fonction sous-modulaireEn optimisation combinatoire, les fonctions sous-modulaires sont des fonctions d'ensemble particulières. Soient E un ensemble et f une fonction qui à tout sous-ensemble X de E associe un réel f(X), on dit que f est sous-modulaire si l'inégalité suivante est vérifiée pour tout sous-ensemble X et Y de E Les fonctions sous-modulaire peuvent être vues comme l'analogue discret des fonctions convexes.
Proof calculusIn mathematical logic, a proof calculus or a proof system is built to prove statements. A proof system includes the components: Language: The set L of formulas admitted by the system, for example, propositional logic or first-order logic. Rules of inference: List of rules that can be employed to prove theorems from axioms and theorems. Axioms: Formulas in L assumed to be valid. All theorems are derived from axioms. Usually a given proof calculus encompasses more than a single particular formal system, since many proof calculi are under-determined and can be used for radically different logics.
Contre-exempleEn logique, en rhétorique et en mathématiques, un contre-exemple est un exemple, un cas particulier ou un résultat général, qui contredit les premières impressions. Un contre-exemple peut aussi être donné pour rejeter une conjecture, c'est-à-dire un énoncé que les gens (et en particulier les mathématiciens) pensaient vrai. Exemple: Toute notre vie on voit des cygnes blancs. On fait donc l'inférence que tous les cygnes sont blancs, jusqu'à ce qu'un événement change notre perception du réel.
Algorithme d'approximationEn informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus précisément, c'est une heuristique garantissant à la qualité de la solution qui fournit un rapport inférieur (si l'on minimise) à une constante, par rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème.
