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.
Type dépendantEn Informatique et en Logique, un type dépendant est un type qui peut dépendre d'une valeur définie dans le langage typé. Les langages Agda et Gallina (de l'assistant de preuve Coq) sont des exemples de langages à type dépendant. Les types dépendants permettent par exemple de définir le type des listes à n éléments. Voici un exemple en Coq. Inductive Vect (A: Type): nat -> Type := | nil: Vect A 0 | cons (n: nat) (x: A) (t: Vect A n): Vect A (S n).
Simply typed lambda calculusThe simply typed lambda calculus (), a form of type theory, is a typed interpretation of the lambda calculus with only one type constructor () that builds function types. It is the canonical and simplest example of a typed lambda calculus. The simply typed lambda calculus was originally introduced by Alonzo Church in 1940 as an attempt to avoid paradoxical use of the untyped lambda calculus. The term simple type is also used to refer extensions of the simply typed lambda calculus such as products, coproducts or natural numbers (System T) or even full recursion (like PCF).
Typed lambda calculusA typed lambda calculus is a typed formalism that uses the lambda-symbol () to denote anonymous function abstraction. In this context, types are usually objects of a syntactic nature that are assigned to lambda terms; the exact nature of a type depends on the calculus considered (see kinds below). From a certain point of view, typed lambda calculi can be seen as refinements of the untyped lambda calculus, but from another point of view, they can also be considered the more fundamental theory and untyped lambda calculus a special case with only one type.
Lambda cubethumb|Le lambda-cube. Initialement proposé par Henk Barendregt, le -cube permet de visualiser les différentes dimensions pour lesquelles le calcul des constructions apporte une généralisation par rapport au lambda-calcul simplement typé où un terme ne peut dépendre que d'un autre terme. Chaque axe représente une nouvelle forme d'abstraction : Terme dépendant de type : le polymorphisme ; Type dépendant de type : présence d'opérateurs de types ; Type dépendant de terme. Catégorie:Calculabilité Catégorie:Théor
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.
Système FLe est un formalisme logique qui permet d'exprimer de façon très riche et très rigoureuse des fonctions et d'y démontrer formellement des propriétés difficiles. Plus précisément, le (également connu sous le nom de lambda-calcul polymorphe ou de lambda-calcul du second ordre) est une extension du lambda-calcul simplement typé introduite indépendamment par le logicien Jean-Yves Girard et par l'informaticien John C. Reynolds. Ce système se distingue du lambda-calcul simplement typé par l'existence d'une quantification universelle sur les types qui permet d'exprimer du polymorphisme.
Connecteur logiqueEn logique, un connecteur logique est un opérateur booléen utilisé dans le calcul des propositions. Comme dans toute approche logique, il faut distinguer un aspect syntaxique et un aspect sémantique. D'un point de vue syntaxique, les connecteurs sont des opérateurs dans un langage formel pour lesquels un certain nombre de règles définissent leur usage, au besoin complétées par une sémantique. Si l'on se place dans la logique classique, l'interprétation des variables se fait dans les booléens ou dans une extension multivalente de ceux-ci.
Formule logiqueEn logique on dit d’une suite finie de lettres qu’elle est une formule, ou parfois formule bien formée, d'un langage logique donné lorsqu’elle peut être construite en appliquant une combinaison des règles de la grammaire formelle associée, on parle de la syntaxe du langage. Informellement les formules sont les assemblages de lettres auxquels il est possible de donner une signification en termes de valeur de vérité (Vrai, ou Faux). Les formules logiques sont l'équivalent des phrases du langage naturel.
Déduction logiqueLa déduction logique est un type de relation que l'on rencontre en logique mathématique. Elle relie des propositions dites prémisses à une proposition dite conclusion et préserve la vérité. Prémisses et conclusion qui sont ainsi reliées par une règle de déduction, assurent que si la règle est valide et si les prémisses sont vraies, la conclusion est elle aussi vraie. On dit alors que la conclusion est une conséquence des prémisses, ou parfois que la conclusion vient des prémisses.
Disjonction logiqueLa disjonction logique, ou disjonction non exclusive, de deux assertions est une façon d'affirmer qu'au moins une de ces deux assertions est vraie (la première, la deuxième, ou les deux). Dans le langage logique ou mathématique, et dans les domaines techniques qui l'emploient, elle se traduit par le OU logique, un opérateur logique dans le calcul des propositions. La proposition obtenue en reliant deux propositions par cet opérateur s'appelle également leur disjonction ou leur somme logique.
Raisonnement par disjonction de casProof 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: A proof that the set of cases is exhaustive; i.e.
Conjonction logiqueEn logique, la conjonction est une opération mise en œuvre par le connecteur binaire et. Le connecteur et est donc un opérateur binaire qui lie deux propositions pour en faire une autre. Si on admet chacune des deux propositions, alors on admettra la proposition qui en est la conjonction. En logique mathématique, le connecteur de conjonction est noté soit &, soit ∧. En théorie de la démonstration, plus particulièrement en calcul des séquents, la conjonction est régie par des règles d'introduction et des règles d'élimination.
Raisonnement par récurrencevignette|Le raisonnement par récurrence est comme une suite de dominos. Si la propriété est vraie au rang n0 (i. e. le premier domino de numéro 0 tombe) et si sa véracité au rang n implique celle au rang n + 1 (i. e. la chute du domino numéro n fait tomber le domino numéro n + 1) alors la propriété est vraie pour tout entier (i. e. tous les dominos tombent). En mathématiques, le raisonnement par récurrence (ou par induction, ou induction complète) est une forme de raisonnement visant à démontrer une propriété portant sur tous les entiers naturels.
Formule atomiqueEn logique mathématique, une formule atomique ou atome est une formule qui ne contient pas de sous-formules propres. La structure d'une formule atomique dépend de la logique considérée, p. ex. en logique des propositions, les formules atomiques sont les variables propositionnelles. Les atomes sont les formules les plus simples dans un système logique et servent à construire les formules les plus générales.
Traductionvignette|La Pierre de Rosette, qui a permis le déchiffrement des hiéroglyphes au . La traduction (dans son acception principale de traduction interlinguale) est le fait de faire passer un texte rédigé dans une langue (« langue source », ou « langue de départ ») dans une autre langue (« langue cible », ou « langue d'arrivée »). Elle met en relation au moins deux langues et deux cultures, et parfois deux époques.
Vérité logiqueLa vérité logique est l'un des concepts les plus fondamentaux de la logique. D'une manière générale, une vérité logique est une proposition qui est vraie indépendamment de la vérité ou la fausseté de ses propositions constitutives. En d'autres termes, une vérité logique est une affirmation qui n'est pas seulement vraie, mais qui est vraie sous toutes les interprétations de ses composants logiques (autres que ses constantes logiques). Ainsi, des vérités logiques telles que "si p, alors p" peuvent être considérées comme des tautologies.
Logique intuitionnisteLa logique intuitionniste est une logique qui diffère de la logique classique par le fait que la notion de vérité est remplacée par la notion de preuve constructive. Une proposition telle que « la constante d'Euler-Mascheroni est rationnelle ou la constante d'Euler-Mascheroni n'est pas rationnelle » n'est pas démontrée de manière constructive (intuitionniste) dans le cadre de nos connaissances mathématiques actuelles, car la tautologie classique « P ou non P » (tiers exclu) n'appartient pas à la logique intuitionniste.
Lambda-calculLe lambda-calcul (ou λ-calcul) est un système formel inventé par Alonzo Church dans les années 1930, qui fonde les concepts de fonction et d'application. On y manipule des expressions appelées λ-expressions, où la lettre grecque λ est utilisée pour lier une variable. Par exemple, si M est une λ-expression, λx.M est aussi une λ-expression et représente la fonction qui à x associe M. Le λ-calcul a été le premier formalisme pour définir et caractériser les fonctions récursives : il a donc une grande importance dans la théorie de la calculabilité, à l'égal des machines de Turing et du modèle de Herbrand-Gödel.
Récurrence transfinieEn mathématiques, on parle de récurrence transfinie ou de récursion transfinie pour deux principes reliés mais distincts. Les définitions par récursion transfinie — permettent de construire des objets infinis, et généralisent les définitions de suite par récurrence sur l'ensemble N des entiers naturels en considérant des familles indexées par un ordinal infini quelconque, au lieu de se borner au plus petit d'entre eux qu'est N, appelé ω en tant que nombre ordinal.
