Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


3.5.3.1. Logical Approaches

Logic-based approaches to knowledge representation emphasize particularly the role of "inference" (deductive inference). They consist mainly, in fact, of (1) a knowledge base of axioms written in some variant of the First-Order Predicate Calculus (FOPC), that makes up the proper knowledge representation component of a logic-based system; and (2) a collection of theorem-proving strategies that represent the deductive component.

In FOPC, we deal with "terms" and "predicates." A term corresponds to some "object" in the universe; predicates are functions that map their arguments (i.e., the terms) into the logic values "true" and "false." If we consider this example built up on the model of the famous "all men are mortal": "All the Artificial Intelligence professors are mad. X is an AI professor. X is mad," we can now say that, if M represents the predicate "mad," M(X) represents the sentence "X is mad." An expression like M(X) is an "atom," and corresponds to a proposition in propositional logic. As is well known, FOPC adds to the usual logical operators used in propositional logic, "and = [wedge]," "or = [logical not]," "not = ¬," "implication = —>," two new operators corresponding to the "universal" ("for all, ") and existential ("there is one, [inverted E]") quantification. Making use of them, we can now represent the sentence "all the AI professors are mad" as "(x) A(x) —> M(x)," i.e., "for all x, if x is an AI professor, then x is mad"; using simple logical artifices like the "universal instantiation" and the "modus ponens," we can deduce from x = X that M(X).

It should be noticed that, under the influence of the programming language PROLOG, several modern FOPC-based representation systems are, in reality, "Horn clauses systems." These systems are characterized by two important properties. The first is that, in these systems, all logical formulas are converted to a normal form, called "clause form." Horn clauses are disjunctive logic formulas with at most one positive (unnegated) "literal"; a literal is an atomic formula P (term1, ..., termn) for some predicate P, where "term..." are, as usual, the arguments. Restriction to Horn clauses is conceptually equivalent to disallowing implications of the type "A —> B [inverted wedge] C," i.e., giving rise to disjunctions within the body of the clause. The second property consists of the fact that Horn clauses systems make use of a single deductive mechanism based on Robinson's "resolution principle." The resolution principle tries to prove that a "theorem," i.e., a clause whose truth value is as yet unknown, can be derived from a set of "axioms," i.e., clauses that are assumed to be true. This principle is based on the notion of contradiction, i.e., a clause and its negation cannot both be true.

Having chosen some form of FOPC for semantic representation, the automatic or semi-automatic translation from NL into this form is normally a two-step procedure. In the first one, a syntactic parse of the input is accomplished. The second translates this parse into a FOPC expression by establishing a correspondence between the types of syntactic constructs found in the input and the FOPC types to be inserted in the output. For example, and sticking to the most general from of FOPC representation, the root of the syntactic tree, S(entence), will give rise to the overall FOPC formula according to a "compositional principle" stating that we can compute the logical form associated with each nonterminal node of the parse tree as a function of the logical form of its immediate constituents. Within the general formula, proper names are translated straightway into terms, with the verb giving rise to the predicate. NPs other than proper names usually introduce variables and set theoretic denotations, as in the example "every professor" which can be translated as "( p [element of] professors)": the NP is represented here as a quantifier over a set, where the set corresponds to the noun, and the quantifier is obtained from the determiner, etc.

From a knowledge representation point of view, pure predicate calculus is constrained by all sorts of limitations, where the main ones concern the impossibility of representing modality (possible, necessary etc.), time, and belief. Even in the quantifier domain, FOPC presents some important limitations: for example, quantifying expressions like "most" or "more than half" cannot be fully rendered within FOPC. Following Montague and his disciples, several extensions to FOPC have been proposed, trying to capture additional linguistic phenomena when conserving the very precise, formal semantics of FOPC. Montague himself has proposed an "intensional logic" for the representation of the semantics of natural language, giving very accurate rules for a limited subset of English where he emphasizes the quantification problems. We can mention here Kamp's "Discourse Representation Theory," see also subsection 3.6. Another well-known, formal semantic theory is Barwise and Perry's "Situation Semantics," which reformulates the logical foundations of FOPC and other formal semantic theories in order to produce a sound formulation of the notion of "partial state of the world" or "situation." Other formal semantic theories are the "Dynamic Predicate Logic," the "Property Theory," etc. We must emphasize here that all these formal semantic theories, which try to extend the conceptual framework of FOPC while conserving its rigid formal properties, had been until now a very limited impact on the production of practical NLP systems, even if they are sometimes invoked a posteriori to give a theoretical justification to some successful prototype.


Previous Table of Contents Next

footer nav
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.