Presburger arithmetic

Presburger arithmetic
A set of axioms of first-order logic for the natural numbers specifying the operations of zero, successor, and addition, including a first-order schema of induction, without multiplication.

Wikipedia foundation.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Presburger arithmetic — is the first order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who published it in 1929. It is not as powerful as Peano arithmetic because it omits multiplication.OverviewThe language of Presburger… …   Wikipedia

  • Mojżesz Presburger — (1904–1943) was a Polish Jewish mathematician, logician, and philosopher. He was a student of Alfred Tarski and is known for, among other things, having invented Presburger arithmetic as a student in 1929. He was born in 1904 and died in a… …   Wikipedia

  • Second-order arithmetic — In mathematical logic, second order arithmetic is a collection of axiomatic systems that formalize the natural numbers and sets thereof. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics. The… …   Wikipedia

  • Robinson arithmetic — In mathematics, Robinson arithmetic, or Q, is a finitely axiomatized fragment of Peano arithmetic (PA), first set out in Robinson (1950). Q is essentially PA without the axiom schema of induction. Even though Q is much weaker than PA, it is still …   Wikipedia

  • Decidability (logic) — In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their… …   Wikipedia

  • Uclid — (pronounced IPA|/ˈjuklɪd/, the same as Euclid ) is a decision procedure for CLU logic and can be used as a tool for bounded model checking of infinite state systems.Decision Procedure and Verification ToolUCLID is a tool for verifying models of… …   Wikipedia

  • List of algebraic structures — In universal algebra, a branch of pure mathematics, an algebraic structure is a variety or quasivariety. Abstract algebra is primarily the study of algebraic structures and their properties. Some axiomatic formal systems that are neither… …   Wikipedia

  • Outline of algebraic structures — In universal algebra, a branch of pure mathematics, an algebraic structure is a variety or quasivariety. Abstract algebra is primarily the study of algebraic structures and their properties. Some axiomatic formal systems that are neither… …   Wikipedia

  • Consistency — For other uses, see Consistency (disambiguation). In logic, a consistent theory is one that does not contain a contradiction.[1] The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a …   Wikipedia

  • Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”