Ensemble récursifEn théorie de la calculabilité, un ensemble récursif ou ensemble décidable est un ensemble d'entiers (ou d'éléments facilement codables dans les entiers) dont la fonction caractéristique est une fonction récursive au sens de la logique mathématique. En d'autres termes, un ensemble est récursif si, et seulement si, il existe une machine de Turing (un programme informatique) permettant de déterminer en un temps fini si un entier quelconque est dans ou pas. Ce type d'ensemble correspond à un concept effectif de John R.
Necessity and sufficiencyIn logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If P then Q", Q is necessary for P, because the truth of Q is guaranteed by the truth of P. (Equivalently, it is impossible to have P without Q, or the falsity of Q ensures the falsity of P.) Similarly, P is sufficient for Q, because P being true always implies that Q is true, but P not being true does not always imply that Q is not true.
Substitution (logic)A substitution is a syntactic transformation on formal expressions. To apply a substitution to an expression means to consistently replace its variable, or placeholder, symbols with other expressions. The resulting expression is called a substitution instance, or instance for short, of the original expression. Where ψ and φ represent formulas of propositional logic, ψ is a substitution instance of φ if and only if ψ may be obtained from φ by substituting formulas for symbols in φ, replacing each occurrence of the same symbol by an occurrence of the same formula.
Idéographiethumb|Page de titre de l'ouvrage de Frege de 1879, Begriffschrift (Idéographie). L'idéographie (Begriffsschrift) est un langage entièrement formalisé inventé par le logicien Gottlob Frege et qui a pour but de représenter de manière parfaite la logique mathématique. Le projet d'un langage entièrement formalisé n'est pas nouveau : Leibniz en avait développé un, qui n'aboutit pas, sous le nom de caractéristique universelle.
