|
Herbrand Universe
In first-order logic, a Herbrand structure S is a structure over a vocabulary \sigma (also sometimes called a ''signature'') that is defined solely by the syntactical properties of \sigma. The idea is to take the symbol strings of terms as their values, e.g. the denotation of a constant symbol c is just "c" (the symbol). It is named after Jacques Herbrand. Herbrand structures play an important role in the foundations of logic programming. Herbrand universe Definition The ''Herbrand universe'' serves as the universe in a ''Herbrand structure''. Example Let L^\sigma, be a first-order language with the vocabulary * constant symbols: c * function symbols: f(\cdot), \, g(\cdot) then the Herbrand universe H of L^\sigma (or of \sigma) is H = \ The relation symbols are not relevant for a Herbrand universe since formulas involving only relations do not correspond to elements of the universe. Formulas consisting only of relations R evaluated at a set of constants or variables cor ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
First-order Logic
First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables. Rather than propositions such as "all humans are mortal", in first-order logic one can have expressions in the form "for all ''x'', if ''x'' is a human, then ''x'' is mortal", where "for all ''x"'' is a quantifier, ''x'' is a variable, and "... ''is a human''" and "... ''is mortal''" are predicates. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic. A theory about a topic, such as set theory, a theory for groups,A. Tarski, ''Undecidable Theories'' (1953), p. 77. Studies in Logic and the Foundation of Mathematics, North-Holland or a formal theory o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Skolem Normal Form
In mathematical logic, a formula of first-order logic is in Skolem normal form if it is in prenex normal form with only universal first-order quantifiers. Every first-order formula may be converted into Skolem normal form while not changing its satisfiability via a process called Skolemization (sometimes spelled Skolemnization). The resulting formula is not necessarily equivalent to the original one, but is equisatisfiable with it: it is satisfiable if and only if the original one is satisfiable. Reduction to Skolem normal form is a method for removing existential quantifiers from formal logic statements, often performed as the first step in an automated theorem prover. Examples The simplest form of Skolemization is for existentially quantified variables that are not inside the scope of a universal quantifier. These may be replaced simply by creating new constants. For example, \exists x P(x) may be changed to P(c), where c is a new constant (does not occur anywhere els ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Herbrand Interpretation
In mathematical logic, a Herbrand interpretation is an interpretation in which all constants and function symbols are assigned very simple meanings. Specifically, every constant is interpreted as itself, and every function symbol is interpreted as the application function on terms. The interpretation also defines predicate symbols as denoting a subset of the relevant Herbrand base, effectively specifying which ground atoms are true in the interpretation. This allows the symbols in a set of clauses to be interpreted in a purely syntactic way, separated from any real instantiation. The importance of Herbrand interpretations is that, if there exists an interpretation that satisfies a given set of clauses ''S'' then there is a Herbrand interpretation that satisfies the clauses. Moreover, Herbrand's theorem states that if ''S'' is unsatisfiable then there is a finite unsatisfiable set of ground instances from the Herbrand universe defined by ''S''. Since this set is finite, it ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Herbrandization
The Herbrandization of a logical formula (named after Jacques Herbrand) is a construction that is dual to the Skolemization of a formula. Thoralf Skolem had considered the Skolemizations of formulas in prenex form as part of his proof of the Löwenheim–Skolem theorem (Skolem 1920). Herbrand worked with this dual notion of Herbrandization, generalized to apply to non-prenex formulas as well, in order to prove Herbrand's theorem (Herbrand 1930). The resulting formula is not necessarily equivalent to the original one. As with Skolemization, which only preserves satisfiability, Herbrandization being Skolemization's dual preserves validity: the resulting formula is valid if and only if the original one is. Definition and examples Let F be a formula in the language of first-order logic. We may assume that F contains no variable that is bound by two different quantifier occurrences, and that no variable occurs both bound and free. (That is, F could be relettered to ensure these ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Herbrand's Theorem
Herbrand's theorem is a fundamental result of mathematical logic obtained by Jacques Herbrand (1930). It essentially allows a certain kind of reduction of first-order logic to propositional logic. Herbrand's theorem is the logical foundation for most automatic theorem provers. Although Herbrand originally proved his theorem for arbitrary formulas of first-order logic, the simpler version shown here, restricted to formulas in prenex form containing only existential quantifiers, became more popular. Statement Let :(\exists y_1,\ldots,y_n)F(y_1,\ldots,y_n) be a formula of first-order logic with F(y_1,\ldots,y_n) quantifier-free, though it may contain additional free variables. This version of Herbrand's theorem states that the above formula is valid if and only if there exists a finite sequence of terms t_, possibly in an expansion of the language, with :1 \le i \le r and 1 \le j \le n, such that :F(t_,\ldots,t_) \vee \ldots \vee F(t_,\ldots,t_) is valid. If it is valid ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theory (logic)
In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language. In most scenarios a deductive system is first understood from context, giving rise to a formal system that combines the language with deduction rules. An element \phi\in T of a deductively closed theory T is then called a theorem of the theory. In many deductive systems there is usually a subset \Sigma \subseteq T that is called "the set of axioms" of the theory T, in which case the deductive system is also called an "axiomatic system". By definition, every axiom is automatically a theorem. A first-order theory is a set of first-order sentences (theorems) recursively obtained by the inference rules of the system applied to the set of axioms. General theories (as expressed in formal language) When defining theories for foundational purposes, additional care must be taken, as normal set-theoretic language may not be appropriate. The construction of a theory begins by sp ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Model (logic)
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it. Universal algebra studies structures that generalize the algebraic structures such as groups, rings, fields and vector spaces. The term universal algebra is used for structures of first-order theories with no relation symbols. Model theory has a different scope that encompasses more arbitrary first-order theories, including foundational structures such as models of set theory. From the model-theoretic point of view, structures are the objects used to define the semantics of first-order logic, cf. also Tarski's theory of truth or Tarskian semantics. For a given theory in model theory, a structure is called a model if it satisfies the defining axioms of that theory, although it is sometimes disambiguated as a '' semantic model'' when one discusses the notion in the more general setting of mathematical models. Lo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
First-order Logic
First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables. Rather than propositions such as "all humans are mortal", in first-order logic one can have expressions in the form "for all ''x'', if ''x'' is a human, then ''x'' is mortal", where "for all ''x"'' is a quantifier, ''x'' is a variable, and "... ''is a human''" and "... ''is mortal''" are predicates. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic. A theory about a topic, such as set theory, a theory for groups,A. Tarski, ''Undecidable Theories'' (1953), p. 77. Studies in Logic and the Foundation of Mathematics, North-Holland or a formal theory o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Resolution (logic)
In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation-complete theorem-proving technique for sentences in propositional logic and first-order logic. For propositional logic, systematically applying the resolution rule acts as a decision procedure for formula unsatisfiability, solving the (complement of the) Boolean satisfiability problem. For first-order logic, resolution can be used as the basis for a semi-algorithm for the unsatisfiability problem of first-order logic, providing a more practical method than one following from Gödel's completeness theorem. The resolution rule can be traced back to Davis and Putnam (1960); however, their algorithm required trying all ground instances of the given formula. This source of combinatorial explosion was eliminated in 1965 by John Alan Robinson's syntactical unification algorithm, which allowed one to instantiate the formula during the proof "on demand" just as far as needed ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Closed Formula
In mathematics, an expression or equation is in closed form if it is formed with constants, variables, and a set of functions considered as ''basic'' and connected by arithmetic operations (, and integer powers) and function composition. Commonly, the basic functions that are allowed in closed forms are ''n''th root, exponential function, logarithm, and trigonometric functions. However, the set of basic functions depends on the context. For example, if one adds polynomial roots to the basic functions, the functions that have a closed form are called elementary functions. The ''closed-form problem'' arises when new ways are introduced for specifying mathematical objects, such as limits, series, and integrals: given an object specified with such tools, a natural problem is to find, if possible, a ''closed-form expression'' of this object; that is, an expression of this object in terms of previous ways of specifying it. Example: roots of polynomials The quadratic formula ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Structure (mathematical Logic)
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it. Universal algebra studies structures that generalize the algebraic structures such as groups, rings, fields and vector spaces. The term universal algebra is used for structures of first-order theories with no relation symbols. Model theory has a different scope that encompasses more arbitrary first-order theories, including foundational structures such as models of set theory. From the model-theoretic point of view, structures are the objects used to define the semantics of first-order logic, cf. also Tarski's theory of truth or Tarskian semantics. For a given theory in model theory, a structure is called a model if it satisfies the defining axioms of that theory, although it is sometimes disambiguated as a '' semantic model'' when one discusses the notion in the more general setting of mathematical models. Log ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Arity
In logic, mathematics, and computer science, arity () is the number of arguments or operands taken by a function, operation or relation. In mathematics, arity may also be called rank, but this word can have many other meanings. In logic and philosophy, arity may also be called adicity and degree. In linguistics, it is usually named valency. Examples In general, functions or operators with a given arity follow the naming conventions of ''n''-based numeral systems, such as binary and hexadecimal. A Latin prefix is combined with the -ary suffix. For example: * A nullary function takes no arguments. ** Example: f()=2 * A unary function takes one argument. ** Example: f(x)=2x * A binary function takes two arguments. ** Example: f(x,y)=2xy * A ternary function takes three arguments. ** Example: f(x,y,z)=2xyz * An ''n''-ary function takes ''n'' arguments. ** Example: f(x_1, x_2, \ldots, x_n)=2\prod_^n x_i Nullary A constant can be treated as the output of an operation o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
