Complexité des preuvesEn informatique théorique, la complexité des preuves ou complexité des démonstrations est le domaine qui étudie les ressources nécessaires pour prouver ou réfuter un énoncé mathématique. Le démarche classique du domaine est de fixer une sorte de preuve, puis de montrer des bornes sur la longueur des preuves pour certains énoncés. La sorte de preuve peut être d'origine logique, comme la déduction naturelle, le calcul des séquents, des systèmes basés sur la règle de résolution, ou plus combinatoire, comme l'algorithme DPLL et la méthode des plans sécants.
Prédicat (logique mathématique)En logique mathématique, un prédicat d'un langage est une propriété des objets du domaine considéré (l'univers du discours) exprimée dans le langage en question. Plus généralement cette propriété peut porter non seulement sur des objets (on peut préciser prédicat d'arité 1, à une place, monadique ou bien encore unaire), mais aussi sur des couples d'objets (on parle alors de prédicat binaire, ou d'arité 2, ou à deux places, ou encore de relation binaire), des triplets d'objets (prédicat ou relation ternaire ou d'arité 3 etc.
Loi d'absorptionEn algèbre, la loi d'absorption est une identité reliant deux lois de composition interne. Deux lois de composition interne et vérifient la loi d'absorption si : Soit un ensemble muni de deux lois de composition interne et . Si ces lois sont commutatives, associatives et vérifient la loi d'absorption, la structure algébrique résultante est un treillis.
ThéorèmeEn mathématiques et en logique, un théorème (du grec théorêma, objet digne d'étude) est une assertion qui est démontrée, c'est-à-dire établie comme vraie à partir d'autres assertions déjà démontrées (théorèmes ou autres formes d'assertions) ou des assertions acceptées comme vraies, appelées axiomes. Un théorème se démontre dans un système déductif et est une conséquence logique d'un système d'axiomes. En ce sens, il se distingue d'une loi scientifique, obtenue par l'expérimentation.
Dependence logicDependence logic is a logical formalism, created by Jouko Väänänen, which adds dependence atoms to the language of first-order logic. A dependence atom is an expression of the form , where are terms, and corresponds to the statement that the value of is functionally dependent on the values of . Dependence logic is a logic of imperfect information, like branching quantifier logic or independence-friendly logic (IF logic): in other words, its game-theoretic semantics can be obtained from that of first-order logic by restricting the availability of information to the players, thus allowing for non-linearly ordered patterns of dependence and independence between variables.
Logique temporelleLa logique temporelle est une branche de la logique mathématique et plus précisément de la logique modale, qui est formalisée de plusieurs manières. La caractéristique commune de ces formalisations réside en l'ajout de modalités (autrement dit de « transformateurs de prédicats ») liées au temps ; par exemple, une formule typique de la logique modale est la formule , qui se lit : « la formule est satisfaite jusqu'à ce que la formule le soit » et qui signifie que l'on cherche à garantir qu'une certaine propriété (ici ) est satisfaite pendant tout le temps qui court avant qu'une autre formule (ici ) le soit.
VaguenessIn linguistics and philosophy, a vague predicate is one which gives rise to borderline cases. For example, the English adjective "tall" is vague since it is not clearly true or false for someone of middling height. By contrast, the word "prime" is not vague since every number is definitively either prime or not. Vagueness is commonly diagnosed by a predicate's ability to give rise to the Sorites paradox. Vagueness is separate from ambiguity, in which an expression has multiple denotations.
LogicismeLe logicisme est une attitude vis-à-vis des mathématiques selon laquelle celles-ci sont une extension de la logique et donc que tous les concepts et théories mathématiques sont réductibles à la logique. Si ce programme était réalisable, il pourrait soutenir le positivisme logique en particulier, et le réductionnisme en général. Bertrand Russell et Alfred North Whitehead ont défendu cette approche, créée par le mathématicien Gottlob Frege. Le logicisme a joué un rôle clé dans le développement de la philosophie analytique au .
Branching quantifierIn logic a branching quantifier, also called a Henkin quantifier, finite partially ordered quantifier or even nonlinear quantifier, is a partial ordering of quantifiers for Q ∈ {∀,∃}. It is a special case of generalized quantifier. In classical logic, quantifier prefixes are linearly ordered such that the value of a variable ym bound by a quantifier Qm depends on the value of the variables y1, ..., ym−1 bound by quantifiers Qy1, ..., Qym−1 preceding Qm. In a logic with (finite) partially ordered quantification this is not in general the case.
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.
