Symbolic Reasoning

Symbolic Reasoning

The basis for intelligent mathematical software is the integration of the "power of symbolic mathematical tools" with the suitable "proof technology".

Mathematical reasoning enjoys a property called monotonic.

"If a conclusion follows from given premises A, B, C, …

then it also follows from any larger set of premises, as long as the original premises are included."

Human reasoning is not monotonic.

People arrive to conclusions only tentatively, based on partial or incomplete information, reserve the right to retract those conclusions while they learn new facts. Such reasoning is non-monotonic, precisely because the set of accepted conclusions have become smaller when the set of premises is expanded.

1. Non-Monotonic Reasoning

Non-Monotonic reasoning is a generic name to a class or a specific theory of reasoning. Non-monotonic reasoning attempts to formalize reasoning with incomplete information by classical logic systems.

The Non-Monotonic reasoning are of the type

■                Default reasoning

■                Ci    umscription

■ Truth Maintenance Systems

Default Reasoning

This is a very common from of non-monotonic reasoning. The conclusions are drawn based on what is most likely to be true.

There are two approaches, both are logic type, to Default reasoning :

one is  Non-monotonic logic and               the other is Default logic.

Non-monotonic logic

It has already been defined. It says, "the truth of a proposition may change when new information (axioms) are added and a logic may be build to allows the statement to be retracted."

Non-monotonic logic is predicate logic with one extension called modal operator M which means “consistent with everything we know”. The purpose of M is to allow consistency.

A way to define consistency with PROLOG notation is : To show that fact P is true, we attempt to prove ¬P.

If we fail we may say that P is consistent since ¬P is false.

Example :

∀ x : plays_instrument(x) ∧   M manage(x) →  jazz_musician(x)

States that for all x,  the x      plays  an instrument  and  if  the fact

that x can manage is consistent with all other knowledge then we can conclude that x is a jazz musician.

■  Default Logic

Read the above inference rule as:

" if A, and if it is consistent with the rest of what is known to assume that B, then conclude that C ".

The rule says that given the prerequisite, the consequent can be inferred, provided it is consistent with the rest of the data.

‡ Example : Rule  that "birds typically fly" would be represented as

‡ Note : Since, all we know about Tweety is that :       

Tweety is a bird,  we therefore inferred      that   Tweety flies.

The idea behind non-monotonic reasoning is to reason with first order logic, and if an inference can not be obtained then use the set of default rules available within the first order formulation.

‡ Applying Default Rules :

While applying default rules, it is necessary to check their justifications for consistency, not only with initial data, but also with the consequents of any other default rules that may be applied. The application of one rule may thus block the application of another. To solve this problem, the concept of default theory was extended.

‡ Default Theory

Example :

A Default Rule says " Typically an American adult owns a car ".

The rule is explained below :

The rule is only accessed if we wish to know whether or not John owns a car then an answer can not be deduced from our current beliefs.

This default rule is applicable if we can prove from our beliefs that John is an American and an adult, and believing that there is some car that is owned by John does not lead to an inconsistency.

If these two sets of premises are satisfied, then the rule states that we can conclude that John owns a car.

Ci umscription

Ci      umscription is a non-monotonic logic to formalize the common sense assumption. Ci          umscription is a formalized rule of conjecture (guess) that can be used along with the rules of inference of first order logic.

Ci      umscription  involves  formulating  rules  of  thumb  with "abnormality"

predicates  and     then  restricting  the  extension  of  these  predicates,

ci       umscribing them, so that they apply to only those things to which they are currently known.

Example :   Take the case of  Bird Tweety

The  rule  of  thumb  is  that  "birds  typically  fly"  is  conditional.  The predicate "Abnormal" signifies abnormality with respect to flying ability.

Observe that the rule ∀ x(Bird(x) & ¬ Abnormal(x) → Flies)) does not allow us to infer that "Tweety flies", since we do not know that he is abnormal with respect to flying ability.

But if we add axioms which ci umscribe the abnormality predicate to which they are currently known say "Bird Tweety" then the inference can be drawn. This inference is non-monotonic.

Truth Maintenance Systems

Reasoning Maintenance System (RMS) is a critical part of a reasoning system. Its purpose is to assure that inferences made by the reasoning system (RS) are valid.

The RS provides the RMS with information about each inference it performs, and in return the RMS provides the RS with information about the whole set of inferences.

Several implementations of RMS have been proposed for non-monotonic reasoning. The important ones are the :

Truth Maintenance Systems (TMS) and Assumption-based Truth Maintenance Systems (ATMS).

The TMS maintains the consistency of a knowledge base as soon as new knowledge is added. It considers only one state at a time so it is not possible to manipulate environment.

The ATMS is intended to maintain multiple environments.

The typical functions of TMS are presented in the next slide.

Truth Maintenance Systems (TMS)

A truth maintenance system maintains consistency in knowledge representation of a knowledge base.

The functions of TMS are to :

■                Provide justifications for conclusions

When a problem solving system gives an answer to a user's query, an explanation of that answer is required;

Example : An advice to a stockbroker is supported by an explanation of the reasons for that advice. This is constructed by the Inference Engine (IE) by tracing the justification of the assertion.

Recognize inconsistencies

The Inference Engine (IE) may tell the TMS that some sentences are contradictory. Then, TMS may find that all those sentences are believed true, and reports to the IE which can eliminate the inconsistencies by determining the assumptions used and changing them appropriately. Example : A statement that either Abbott, or Babbitt, or Cabot is guilty together with other statements that Abbott is not guilty, Babbitt is not guilty, and Cabot is not guilty, form a contradiction.

Support default reasoning

In the absence of any firm knowledge, in many situations we want to reason from default assumptions.

Example : If "Tweety is a bird", then until told otherwise, assume that "Tweety flies" and for justification use the fact that "Tweety is a bird" and the assumption that "birds fly".

2. Implementation Issues

The issues and weaknesses related to implementation of non-monotonic reasoning in problem solving are :

How to derive exactly those non-monotonic conclusion that are relevant to solving the problem at hand while not wasting time on those that are not necessary.

How to update our knowledge incrementally as problem solving progresses.

How to over come the problem where more than one interpretation of the known facts is qualified or approved by the available inference rules.

In general the theories are not computationally effective, decidable or semi decidable.

The solutions offered, considering the reasoning processes into two parts : one, a problem solver that uses whatever mechanism it happens to have to draw conclusions as necessary, and second, a truth maintenance system whose job is to maintain consistency in knowledge representation of a knowledge base.