|
Resolution Proof Compression By Splitting
In mathematical logic, proof compression by splitting is an algorithm that operates as a post-process on resolution Resolution(s) may refer to: Common meanings * Resolution (debate), the statement which is debated in policy debate * Resolution (law), a written motion adopted by a deliberative body * New Year's resolution, a commitment that an individual mak ... proofs. It was proposed by Scott Cotton in his paper "Two Techniques for Minimizing Resolution Proof".Cotton, Scott. "Two Techniques for Minimizing Resolution Proofs". 13th International Conference on Theory and Applications of Satisfiability Testing, 2010. The Splitting algorithm is based on the following observation: Given a proof of unsatisfiability \pi and a variable x, it is easy to re-arrange (split) the proof in a proof of x and a proof of \neg x and the recombination of these two proofs (by an additional resolution step) may result in a proof smaller than the original. Note that applying Splitting in a proo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematical Logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics. Since its inception, mathematical logic has both contributed to and been motivated by the study of foundations of mathematics. This study began in the late 19th century with the development of axiomatic frameworks for geometry, arithmetic, and analysis. In the early 20th century it was shaped by David Hilbert's program to prove the consistency of foundational theories. Results of Kurt Gödel, Gerhard Gentzen, and others provided partial resolution to the program, and clarified the issues involved in proving consistency. Work in set theory s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Proof Compression
In proof theory, an area of mathematical logic, proof compression is the problem of algorithmically compressing formal proofs. The developed algorithms can be used to improve the proofs generated by automated theorem proving tools such as SAT solvers, SMT-solvers, first-order theorem provers and proof assistants. Problem Representation In propositional logic a resolution proof of a clause \kappa from a set of clauses ''C'' is a directed acyclic graph (DAG): the input nodes are axiom inferences (without premises) whose conclusions are elements of ''C'', the resolvent nodes are resolution inferences, and the proof has a node with conclusion \kappa. The DAG contains an edge from a node \eta_ to a node \eta_ if and only if a premise of \eta_ is the conclusion of \eta_. In this case, \eta_ is a child of \eta_, and \eta_ is a parent of \eta_. A node with no children is a root. A proof compression algorithm will try to create a new DAG with fewer nodes that represents a valid proof of \ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can perform automated deductions (referred to as automated reasoning) and use mathematical and logical tests to divert the code execution through various routes (referred to as automated decision-making). Using human characteristics as descriptors of machines in metaphorical ways was already practiced by Alan Turing with terms such as "memory", "search" and "stimulus". In contrast, a heuristic is an approach to problem solving that may not be fully specified or may not guarantee correct or optimal results, especially in problem domains where there is no well-defined correct or optimal result. As an effective method, an algorithm can be expressed within a finite amount of spac ... [...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 need ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
