|
Negation As Failure
Negation as failure (NAF, for short) is a non-monotonic inference rule in logic programming, used to derive \mathrm~p (i.e. that ~p is assumed not to hold) from failure to derive ~p. Note that \mathrm ~p can be different from the statement \neg p of the logical negation of ~p, depending on the completeness of the inference algorithm and thus also on the formal logic system. Negation as failure has been an important feature of logic programming since the earliest days of both Planner and Prolog. In Prolog, it is usually implemented using Prolog's extralogical constructs. More generally, this kind of negation is known as weak negation, in contrast with the strong (i.e. explicit, provable) negation. Planner semantics In Planner, negation as failure could be implemented as follows: :''if'' (''not'' (''goal'' p)), ''then'' (''assert'' ¬p) which says that if an exhaustive search to prove p fails, then assert ¬p. This states that proposition p shall be assumed as "not true" in any ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Non-monotonic Logic
A non-monotonic logic is a formal logic whose conclusion relation is not monotonic. In other words, non-monotonic logics are devised to capture and represent defeasible inferences (cf. defeasible reasoning), i.e., a kind of inference in which reasoners draw tentative conclusions, enabling reasoners to retract their conclusion(s) based on further evidence. Most studied formal logics have a monotonic entailment relation, meaning that adding a formula to a theory never produces a pruning of its set of conclusions. Intuitively, monotonicity indicates that learning a new piece of knowledge cannot reduce the set of what is known. A monotonic logic cannot handle various reasoning tasks such as reasoning by default (conclusions may be derived only because of lack of evidence of the contrary), abductive reasoning (conclusions are only deduced as most likely explanations), some important approaches to reasoning about knowledge (the ignorance of a conclusion must be retracted when the concl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Circumscription (logic)
Circumscription is a non-monotonic logic created by John McCarthy to formalize the common sense assumption that things are as expected unless otherwise specified. Circumscription was later used by McCarthy in an attempt to solve the frame problem. To implement circumscription in its initial formulation, McCarthy augmented first-order logic to allow the minimization of the extension of some predicates, where the extension of a predicate is the set of tuples of values the predicate is true on. This minimization is similar to the closed-world assumption that what is not known to be true is false. The original problem considered by McCarthy was that of missionaries and cannibals: there are three missionaries and three cannibals on one bank of a river; they have to cross the river using a boat that can only take two, with the additional constraint that cannibals must never outnumber the missionaries on either bank (as otherwise the missionaries would be killed and, presumably, eaten) ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stable Model Semantics
The concept of a stable model, or answer set, is used to define a declarative semantics for logic programs with negation as failure. This is one of several standard approaches to the meaning of negation in logic programming, along with program completion and the well-founded semantics. The stable model semantics is the basis of answer set programming. Motivation Research on the declarative semantics of negation in logic programming was motivated by the fact that the behavior of SLDNF resolution — the generalization of SLD resolution used by Prolog in the presence of negation in the bodies of rules — does not fully match the truth tables familiar from classical propositional logic. Consider, for instance, the program :p\ :r \leftarrow p,\ q :s \leftarrow p,\ \operatorname q. Given this program, the query will succeed, because the program includes as a fact; the query will fail, because it does not occur in the head of any of the rules. The query will fail also ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Answer Set Programming
Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems. It is based on the stable model (answer set) semantics of logic programming. In ASP, search problems are reduced to computing stable models, and ''answer set solvers''—programs for generating stable models—are used to perform search. The computational process employed in the design of many answer set solvers is an enhancement of the DPLL algorithm and, in principle, it always terminates (unlike Prolog query evaluation, which may lead to an infinite loop). In a more general sense, ASP includes all applications of answer sets to knowledge representation and the use of Prolog-style query evaluation for solving problems arising in these applications. History An early example of answer set programming was the planning method proposed in 1997 by Dimopoulos, Nebel and Köhler. Their approach is based on the relationship between plans and stable model ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Vladimir Lifschitz
Vladimir Lifschitz (born 30 May 1947) is the Gottesman Family Centennial Professor in Computer Sciences at the University of Texas at Austin. He received a degree in mathematics from the Steklov Institute of Mathematics in Russia in 1971 and emigrated to the United States in 1976. Lifschitz's research interests are in the areas of computational logic and knowledge representation. He is a Fellow of the Association for the Advancement of Artificial Intelligence, the Editor-in-Chief of the ACM Transactions on Computational Logic, and an Editorial Advisor of the journal ''Theory and Practice of Logic Programming''. He, together with Michael Gelfond, defined stable model semantics for logic programs, which later became the theoretical foundation for Answer Set Programming,Victor Marek and Miroslaw Truszczynski. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: a 25-Year Perspective, pages 375-398. Springer Verlag, 1999 a new declarative pro ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Autoepistemic Logic
The autoepistemic logic is a formal logic for the representation and reasoning of knowledge about knowledge. While propositional logic can only express facts, autoepistemic logic can express knowledge and lack of knowledge about facts. The stable model semantics, which is used to give a semantics to logic programming with negation as failure, can be seen as a simplified form of autoepistemic logic. Syntax The syntax of autoepistemic logic extends that of propositional logic by a modal operator \BoxTo clarify, the modal operator \Box is a medium white square; this is not a browser rendering issue indicating knowledge: if F is a formula, \Box F indicates that F is known. As a result, \Box \neg F indicates that \neg F is known and \neg \Box F indicates that F is not known. This syntax is used for allowing reasoning based on knowledge of facts. For example, \neg \Box F \rightarrow \neg F means that F is assumed false if it is not known to be true. This is a form of negation as failur ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Michael Gelfond
Michael Gelfond is a Professor in Computer Sciences at Texas Tech University in the United States. He received a degree in mathematics from the Steklov Institute of Mathematics in Russia in 1974 and emigrated to the United States in 1978. Gelfond's research interests are in the areas of computational logic and knowledge representation. He is a Fellow of the Association for the Advancement of Artificial Intelligence, and an Area Editor (in Knowledge Representation and Nonmonotonic Reasoning) of the journal ''Theory and Practice of Logic Programming''. He, together with Vladimir Lifschitz, defined stable model semantics for logic programs, which later became the theoretical foundation for Answer Set Programming Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems. It is based on the stable model (answer set) semantics of logic programming. In ASP, search problems are reduced ...,Victor Marek and Mirosla ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Closed World Assumption
The closed-world assumption (CWA), in a formal system of logic used for knowledge representation, is the presumption that a statement that is true is also known to be true. Therefore, conversely, what is not currently known to be true, is false. The same name also refers to a logical formalization of this assumption by Raymond Reiter. The opposite of the closed-world assumption is the open-world assumption (OWA), stating that lack of knowledge does not imply falsity. Decisions on CWA vs. OWA determine the understanding of the actual semantics of a conceptual expression with the same notations of concepts. A successful formalization of natural language semantics usually cannot avoid an explicit revelation of whether the implicit logical backgrounds are based on CWA or OWA. Negation as failure is related to the closed-world assumption, as it amounts to believing false every predicate that cannot be proved to be true. Example In the context of knowledge management, the closed-worl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Atomic Formula
In mathematical logic, an atomic formula (also known as an atom or a prime formula) is a formula with no deeper propositional structure, that is, a formula that contains no logical connectives or equivalently a formula that has no strict subformulas. Atoms are thus the simplest well-formed formulas of the logic. Compound formulas are formed by combining the atomic formulas using the logical connectives. The precise form of atomic formulas depends on the logic under consideration; for propositional logic, for example, a propositional variable is often more briefly referred to as an "atomic formula", but, more precisely, a propositional variable is not an atomic formula but a formal expression that denotes an atomic formula. For predicate logic, the atoms are predicate symbols together with their arguments, each argument being a term. In model theory, atomic formulas are merely strings of symbols with a given signature, which may or may not be satisfiable with respect to a given mo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Logic Programming
Logic programming is a programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic programming language families include Prolog, answer set programming (ASP) and Datalog. In all of these languages, rules are written in the form of ''clauses'': :H :- B1, …, Bn. and are read declaratively as logical implications: :H if B1 and … and Bn. H is called the ''head'' of the rule and B1, ..., Bn is called the ''body''. Facts are rules that have no body, and are written in the simplified form: :H. In the simplest case in which H, B1, ..., Bn are all atomic formulae, these clauses are called definite clauses or Horn clauses. However, there are many extensions of this simple case, the most important one being the case in which conditions in the body of a clause can also be negations of atomic formulas. Logic programming languag ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Keith Clark (computer Scientist)
Keith Leonard Clark (born 29 March 1943) is an Emeritus Professor in the Department of Computing at Imperial College London, England. Education Clark studied Mathematics at Durham University (Hatfield College), graduating in 1964 with a first-class degree. Clark then continued his studies at Cambridge University, taking a second undergraduate degree in Philosophy in 1966. He earned a Ph.D. in 1980 from the University of London with thesis titled ''Predicate logic as a computational formalism''. Career Clark undertook Voluntary Service Overseas from 1967 to 1968 as a teacher of Mathematics at a school in Sierra Leone. He lectured in Computer Science at the Mathematics Department of Queen Mary, University of London, Queen Mary College from 1969 to 1975. In 1975 he moved to Imperial College London, where he became a Senior Lecturer in the Department of Computer Science and joined Robert Kowalski in setting up the Logic programming group. From 1987 to 2009 he was Professor of Co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Springer-Verlag
Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing. Originally founded in 1842 in Berlin, it expanded internationally in the 1960s, and through mergers in the 1990s and a sale to venture capitalists it fused with Wolters Kluwer and eventually became part of Springer Nature in 2015. Springer has major offices in Berlin, Heidelberg, Dordrecht, and New York City. History Julius Springer founded Springer-Verlag in Berlin in 1842 and his son Ferdinand Springer grew it from a small firm of 4 employees into Germany's then second largest academic publisher with 65 staff in 1872.Chronology ". Springer Science+Business Media. In 1964, Springer expanded its business internationally, o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |