non-monotonic reasoning
In plain wordsReasoning in which new information can overturn earlier conclusions — you assume a bird can fly until you learn it is a penguin — as people do constantly but classical logic does not allow.
Reasoning in which adding premises can invalidate conclusions drawn earlier, unlike classical logic, where the set of consequences only grows (monotonicity). It formalizes default reasoning — drawing conclusions that hold typically but have exceptions — which is essential for commonsense reasoningcommonsense reasoning, n.: The everyday background knowledge and reasoning people take for granted — dropped glasses break, hungry people eat, nobody is in two places at once — which machines long struggled to match. and for describing actions without listing every exception (the frame problemframe problem, n.: The difficulty of getting an AI to work out what does and does not change when something happens, without spelling out every one of the countless things that stay the same. and the related qualification problem). Major formalisms include Raymond Reiter's default logic, with rules such as 'if x is a bird and it is consistent to assume x flies, conclude that x flies'; John McCarthy's circumscription, which minimizes the extent of 'abnormality' predicates; Robert Moore's autoepistemic logic; negation as failure under the closed-world assumptionclosed-world assumption, n.: The rule of treating whatever a system cannot confirm as false: if a library's catalog does not list a book, the library is assumed not to have it.; and answer set programminganswer set programming, n.: A way to solve hard puzzles and scheduling problems by describing in logical rules what a valid solution looks like; a solver then finds the arrangements that fit those rules.. Truth maintenance systems record which beliefs rest on which assumptions so that retractions propagate correctly. Non-monotonic logics are generally harder to compute with than classical logic.
Origin
Emerged in the late 1970s. A landmark special issue of the journal Artificial Intelligence (volume 13, 1980) presented McCarthy's circumscription, Reiter's default logic, and Drew McDermott and Jon Doyle's non-monotonic logic; Doyle's truth maintenance system (1979) and Moore's autoepistemic logic (1985) were further milestones.
Related
- closed-world assumptionclosed-world assumption, n.: The rule of treating whatever a system cannot confirm as false: if a library's catalog does not list a book, the library is assumed not to have it.
- answer set programminganswer set programming, n.: A way to solve hard puzzles and scheduling problems by describing in logical rules what a valid solution looks like; a solver then finds the arrangements that fit those rules.
- commonsense reasoningcommonsense reasoning, n.: The everyday background knowledge and reasoning people take for granted — dropped glasses break, hungry people eat, nobody is in two places at once — which machines long struggled to match.
- frame problemframe problem, n.: The difficulty of getting an AI to work out what does and does not change when something happens, without spelling out every one of the countless things that stay the same.
- logic programminglogic programming, n.: A style of programming in which you write down facts and rules in logic and then ask questions; the computer works out the answers itself by logical deduction.
- situation calculussituation calculus, n.: A logical language for describing how the world changes as actions happen, so that a program can work out what will be true after any sequence of actions.
Sources
- Reiter, R. (1980). A Logic for Default Reasoning. Artificial Intelligence 13(1–2), 81–132.
- McCarthy, J. (1980). Circumscription — A Form of Non-Monotonic Reasoning. Artificial Intelligence 13(1–2), 27–39.
Mentioned in
commonsense reasoningcommonsense reasoning, n.: The everyday background knowledge and reasoning people take for granted — dropped glasses break, hungry people eat, nobody is in two places at once — which machines long struggled to match., frame problemframe problem, n.: The difficulty of getting an AI to work out what does and does not change when something happens, without spelling out every one of the countless things that stay the same., fuzzy logicfuzzy logic, n.: A kind of logic that allows degrees of truth, so a statement like 'the room is warm' can be 70 percent true, which helps machines handle vague everyday categories., John McCarthyJohn McCarthy, prop. n.: The American computer scientist who coined the term 'artificial intelligence', invented the Lisp programming language and championed formal logic as the route to machine common sense., knowledge representationknowledge representation, n.: The study of how to record knowledge about objects, categories, rules and events in a precise format, so that a program can reason with it and reach conclusions nobody typed in., answer set programminganswer set programming, n.: A way to solve hard puzzles and scheduling problems by describing in logical rules what a valid solution looks like; a solver then finds the arrangements that fit those rules., closed-world assumptionclosed-world assumption, n.: The rule of treating whatever a system cannot confirm as false: if a library's catalog does not list a book, the library is assumed not to have it., situation calculussituation calculus, n.: A logical language for describing how the world changes as actions happen, so that a program can work out what will be true after any sequence of actions.