|
Vampire Theorem Prover
Vampire is an automatic theorem prover for first-order classical logic developed in the Department of Computer Science at the University of Manchester. Up to Version 3, it was developed by Andrei Voronkov together with Kryštof Hoder and previously with Alexandre Riazanov. Since Version 4, the development has involved a wider international team including Laura Kovacs, Giles Reger, and Martin Suda. Since 1999 it has won at least 53 trophies in the CADE ATP System Competition, the "world cup for theorem provers", including the most prestigious FOF division and the theory-reasoning TFA division. Background Vampire's kernel implements the calculi of ordered binary resolution and superposition (for handling equality). The splitting rule and negative equality splitting can be simulated by the introduction of new predicate definitions and dynamic folding of such definitions. A DPLL-style algorithm splitting is also supported. A number of standard redundancy criteria and simplifi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Andrei Voronkov
Andrei Anatolievič Voronkov (born 1959) is a Professor of Formal methods in the Department of Computer Science, University of Manchester, Department of Computer Science at the University of Manchester. Education Voronkov was educated at Novosibirsk State University, graduating with a PhD in 1987. Research Voronkov is known for the Vampire (theorem prover), Vampire Automated theorem proving, automated theorem prover, the EasyChair conference management software, the ''Handbook of Automated Reasoning'' (with John Alan Robinson, 2001), and as organiser of the Alan Turing Centenary Conference 2012. Voronkov's research has been funded by the Engineering and Physical Sciences Research Council, Engineering and Physical Sciences Research Council (EPSRC). Awards and honours In 2015, his contributions to the field of automated reasoning were recognized with the Herbrand Award. He has won 25 division titles in the CADE ATP System Competition (CASC) at the Conference on Automated Deduction ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tautology (logic)
In mathematical logic, a tautology (from ) is a formula that is true regardless of the interpretation of its component terms, with only the logical constants having a fixed meaning. For example, a formula that states, "the ball is green or the ball is not green," is always true, regardless of what a ball is and regardless of its colour. Tautology is usually, though not always, used to refer to valid formulas of propositional logic. The philosopher Ludwig Wittgenstein first applied the term to redundancies of propositional logic in 1921, borrowing from rhetoric, where a tautology is a repetitive statement. In logic, a formula is satisfiable if it is true under at least one interpretation, and thus a tautology is a formula whose negation is unsatisfiable. In other words, it cannot be false. Unsatisfiable statements, both through negation and affirmation, are known formally as contradictions. A formula that is neither a tautology nor a contradiction is said to be logically c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theorem Proving Software Systems
In mathematics and formal logic, a theorem is a statement that has been proven, or can be proven. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of the axioms and previously proved theorems. In mainstream mathematics, the axioms and the inference rules are commonly left implicit, and, in this case, they are almost always those of Zermelo–Fraenkel set theory with the axiom of choice (ZFC), or of a less powerful theory, such as Peano arithmetic. Generally, an assertion that is explicitly called a theorem is a proved result that is not an immediate consequence of other known theorems. Moreover, many authors qualify as ''theorems'' only the most important results, and use the terms ''lemma'', ''proposition'' and ''corollary'' for less important theorems. In mathematical logic, the concepts of theorems and proofs have been formalized in order to allow mathematical reasonin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Executable
In computer science, executable code, an executable file, or an executable program, sometimes simply referred to as an executable or binary, causes a computer "to perform indicated tasks according to encoded instruction (computer science), instructions", as opposed to a data (computing), data file that must be interpreted (parser, parsed) by an interpreter (computing), interpreter to be functional. The exact interpretation depends upon the use. "Instructions" is traditionally taken to mean machine code instructions for a physical central processing unit, CPU. In some contexts, a file containing scripting instructions (such as bytecode) may also be considered executable. Generation of executable files Executable files can be hand-coded in machine language, although it is far more convenient to develop software as source code in a high-level language that can be easily understood by humans. In some cases, source code might be specified in assembly language instead, which rema ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Craig Interpolation
In mathematical logic, Craig's interpolation theorem is a result about the relationship between different logical theory (mathematical logic), theories. Roughly stated, the theorem says that if a well formed formula, formula φ implies a formula ψ, and the two have at least one atomic variable symbol in common, then there is a formula ρ, called an interpolant, such that every non-logical symbol in ρ occurs both in φ and ψ, φ implies ρ, and ρ implies ψ. The theorem was first proved for first-order logic by William Craig (logician), William Craig in 1957. Variants of the theorem hold for other logics, such as propositional logic. A stronger form of Craig's interpolation theorem for first-order logic was proved by Roger Lyndon in 1959; the overall result is sometimes called the Craig–Lyndon theorem. Example In propositional logic, let ::: \varphi = \lnot(P \land Q) \to (\lnot R \land Q) ::: \psi = (S \to P) \lor (S \to \lnot R) . Then \varphi tautological implication ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Conjunctive Normal Form
In Boolean algebra, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. In automated theorem proving, the notion "''clausal normal form''" is often used in a narrower sense, meaning a particular representation of a CNF formula as a set of sets of literals. Definition A logical formula is considered to be in CNF if it is a conjunction of one or more disjunctions of one or more literals. As in disjunctive normal form (DNF), the only propositional operators in CNF are or (\vee), and (\and), and not (\neg). The ''not'' operator can only be used as part of a literal, which means that it can only precede a propositional variable. The following is a context-free grammar for CNF: : ''CNF'' \, \to \, ''Disjunct'' \, \mid \, ''Disjunct'' \, \land \, ''CNF'' : ''Disjunct'' \, \to \, ''Literal'' \, \mid\, ''Literal'' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Run-time Algorithm Specialisation
In computer science, run-time algorithm specialization is a methodology for creating efficient algorithms for costly computation tasks of certain kinds. The methodology originates in the field of automated theorem proving and, more specifically, in the Vampire theorem prover project. The idea is inspired by the use of partial evaluation in optimising program translation. Many core operations in theorem provers exhibit the following pattern. Suppose that we need to execute some algorithm \mathit(A,B) in a situation where a value of A ''is fixed for potentially many different values of'' B. In order to do this efficiently, we can try to find a specialization of \mathit for every fixed A, i.e., such an algorithm \mathit_A, that executing \mathit_A(B) is equivalent to executing \mathit(A,B). The specialized algorithm may be more efficient than the generic one, since it can ''exploit some particular properties'' of the fixed value A. Typically, \mathit_A(B) can avoid some operations th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clause (logic)
In logic, a clause is a propositional formula formed from a finite collection of literals (atoms or their negations) and logical connectives. A clause is true either whenever at least one of the literals that form it is true (a disjunctive clause, the most common use of the term), or when all of the literals that form it are true (a conjunctive clause, a less common use of the term). That is, it is a finite disjunction or conjunction of literals, depending on the context. Clauses are usually written as follows, where the symbols l_i are literals: :l_1 \vee \cdots \vee l_n Empty clauses A clause can be empty (defined from an empty set of literals). The empty clause is denoted by various symbols such as \empty, \bot, or \Box. The truth evaluation of an empty disjunctive clause is always false. This is justified by considering that false is the neutral element of the monoid (\, \vee). The truth evaluation of an empty conjunctive clause is always true. This is related to the conc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Term Indexing
In computer science, a term index is a data structure to facilitate fast lookup of terms and Clause (logic), clauses in a logic programming, logic program, deductive database, or automated theorem prover. Overview Many operations in automatic theorem provers require search in huge collections of terms and clauses. Such operations typically fall into the following scheme. Given a collection S of terms (clauses) and a query term (clause) q, find in S some/all terms t related to q according to a certain retrieval condition. Most interesting retrieval conditions are formulated as existence of a substitution that relates in a special way the query and the retrieved objects t. Here is a list of retrieval conditions frequently used in provers: * term q is unifiable with term t, i.e., there exists a substitution \theta , such that q\theta = t\theta * term t is an instance of q, i.e., there exists a substitution \theta, such that q\theta = t * term t is a generalisation of q, i.e., there ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Knuth–Bendix Completion Algorithm
The Knuth–Bendix completion algorithm (named after Donald Knuth and Peter Bendix) is a semi-decision algorithm for transforming a set of equations (over terms) into a confluent term rewriting system. When the algorithm succeeds, it effectively solves the word problem for the specified algebra. Buchberger's algorithm for computing Gröbner bases is a very similar algorithm. Although developed independently, it may also be seen as the instantiation of Knuth–Bendix algorithm in the theory of polynomial rings. Introduction For a set ''E'' of equations, its deductive closure () is the set of all equations that can be derived by applying equations from ''E'' in any order. Formally, ''E'' is considered a binary relation, () is its rewrite closure, and () is the equivalence closure of (). For a set ''R'' of rewrite rules, its deductive closure ( ∘ ) is the set of all equations that can be confirmed by applying rules from ''R'' left-to-right to both sides until they are lite ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Term (logic)
In mathematical logic, a term denotes a mathematical object while a formula denotes a mathematical fact. In particular, terms appear as components of a formula. This is analogous to natural language, where a noun phrase refers to an object and a whole sentence refers to a fact. A first-order term is recursively constructed from constant symbols, variable symbols, and function symbols. An expression formed by applying a predicate symbol to an appropriate number of terms is called an atomic formula, which evaluates to true or false in bivalent logics, given an interpretation. For example, is a term built from the constant 1, the variable , and the binary function symbols and ; it is part of the atomic formula which evaluates to true for each real-numbered value of . Besides in logic, terms play important roles in universal algebra, and rewriting systems. Definition Given a set ''V'' of variable symbols, a set ''C'' of constant symbols and sets ''F''''n'' of ''n''-ary ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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. Propositional logic Definition Where ''ψ'' and ''φ'' represent formulas of propositional logic, ''ψ'' is a ''substitution instance'' of ''φ'' if and only if ''ψ'' may be obtained from ''φ'' by substituting formulas for propositional variables in ''φ'', replacing each occurrence of the same variable by an occurrence of the same formula. For example: ::''ψ:'' (R → S) & (T → S) is a substitution instance of ::''φ:'' P & Q That is, ''ψ'' can be obtained by replacing P and Q in ''φ'' with (R → S) and (T → S) respectively. Similarly: ::''ψ:'' (A ↔ A) ↔ (A ↔ A) is a substitution instance of: ::''φ:'' (A ↔ A) since ''ψ'' can be obta ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
