![]() |
|||
![]()
|
![]() |
![]() |
![]() |
3. LOGIC AND REASONINGLogic studies the principles of reasoning. As a scientific discipline, logic has found a wide range of applications in many disciplines, which include computer science and artificial intelligence (gen_and_nil). In the design of AI systems, logic has often been regarded as one of several knowledge tools. While some important aspects of logic have been criticized (e.g., see Minsky and Minsky), the best of those criticisms have typically resulted in strengthening the role of logic within AI by using the simplest of logics -- deductive logic -- as a basis for important extensions. 3.1. DEDUCTIONLogical inference or deduction is the classical approach to reasoning. We have a knowledge base that is a set of logic formulae and one or more sound inference rules from which we can derive new knowledge that we add to the knowledge base. As a transformation of a given knowledge base, deduction (or deductive rules of inference that define a deductive proof procedure) has the property of preserving truth: sound rules of inference will preserve the truth of original information in deduced information. From another view, deduction forms the basis upon which AI-motivated extensions can be constructed. As a mathematical structure, logic is characterized by the following three components: a formal language in which knowledge can be expressed, a semantics to give meaning to the sentences of the language, and proof procedures to infer knowledge. A formal language is defined by a syntax that uses an alphabet of symbols and defines rules to combine the elements of the alphabet to form sentences called well-formed formulae. Symbols of the alphabet include constants, variables, functions, predicates, and connectives. The semantics of classical logic assigns meaning to the formulae by defining a mapping between the symbols of the formula and the objects and relationships of the world. This mapping is called an interpretation. An interpretation consists of a domain and a mapping from elements, functions, and relations of the domain to constant, variables, function, and predicate symbols in the formula. Constants, variables, and terms denote elements of the domain. A formula can take the values true or false. A model [curly M] is an interpretation that makes a formula [alpha] true and is denoted: [curly M] [implies equal][alpha], which is read [curly M]" satisfies [alpha]." A formula [alpha] is valid if it is true for every interpretation, and denoted by [implies equal][alpha]. A formula is satisfiable if it has a model, and is a contradiction if it is false for every interpretation. A set of formulae [cap gamma] is satisfiable if there is an interpretation that satisfies every formula in [cap gamma]. The fact that every interpretation that satisfies a set of formulae [cap gamma] also satisfies a formula [alpha], is denoted by [cap gamma] [implies equal][alpha] and read "[cap gamma] logically implies [alpha]." A proof procedure (or calculus) consists of a set of axioms, and a set of rules of inference for deductive reasoning. A formula a which is derived from the axioms by a sequence of inference rules applications is called a theorem and is denoted by: [implies] [alpha]. If a is derived from a set of formulae [cap gamma], we write [cap gamma] [implies] [alpha], which is read [alpha] is deduced from [cap gamma]. Soundness and completeness are two attributes of a proof procedure with respect to semantics. Soundness means that any theorem deduced by the proof procedure is valid. Completeness means that any valid formula can be proved by the proof procedure. The completeness theorem establishes the relationship between deduction and logical implication: [cap gamma] [implies equal] [alpha] [mutually implies] [cap gamma] [implies] [alpha] which establishes the equivalence between logical consequence and deduction. In the following section we characterize deductive reasoning for various types of logics, and then we study variations to the deductive approach, which include nonmonotonic reasoning, induction, abduction, and probabilistic reasoning. Many types of logics can and have been derived, depending upon the constraints imposed on the syntax and semantics of the logic. Without being exhaustive, we survey some of the main logics: propositional logic, first-order logic, and higher-order logic. Logic can be studied with respect to ontological and epistemological commitments. Ontological commitments have to do with what is assumed to exist in the world; thus, propositional logic assumes that the world consists of facts that are either true or false. First-order logic assumes that the world consists of objects with relationships among them that either hold or do not hold; quantification is made only on objects. Higher-order logic assumes that the world is made of objects, categories of objects, and relationships among them; quantification is made over objects, predicates, and functions. Epistemological commitments have to do with the possible states of knowledge owned by an intelligent system. A system that represents knowledge using propositional, first-order, or higher-order logic believes a formula that represents a fact about the world to be true, to be false, or it could be unable to conclude either way. Systems that represent uncertain knowledge using probability theory, on the other hand, can have any degree of belief, typcially rendered as numbers in the range 0 (e.g., "total disbelief") to 1 (e.g., "total belief"). Systems that represent uncertain knowledge using fuzzy logic can have degrees of belief in a sentence like probabilistic systems, but their ontological commitment assumes that what exists does so with associated degrees of truth.
|
![]() |
|
Use of this site is subject certain Terms & Conditions. Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details. |