Rules of Inference, Unification, Resolution Refutation System (RRS), Answer Extraction From RRS, Rule Based Deduction System,

Rules of inference are the process of deriving new facts from the given one or more existing facts. While undertaking this process we need to follow certain rules which are called as the rules of inference and they are AND-elimination, AND-introduction, OR-elimination, Double-Negation Elimination, Modus Ponen, Modus Tollen, Unit resolution and Transitivity rule. In propositional logic, it is easy to determine that the two literals can not be both true at the same time. Simply look for L and ~L . In a predicate logic, this matching process is more complicated since the bindings of variables must be considered. In order to determine contradictions, we need a matching procedure that compares two literals and discovers whether there exist a set of substitutions that makes them identical . There is a recursive procedure that does this matching . It is called Unification algorithm. In Unification algorithm, each literal is represented as a list, where the first element is the name of a predicate and the remaining elements are arguments. The argument may be a single element (atom) or may be another list. Resolution is the process which is equivalent to multi-state processing with all the premises given in DNF. Resolution in propositional logic can be done in two ways and they are by answer extraction method and by contradiction method. Rule-based deduction system is a system that derives a conclusion by using some rules is called rule-based deduction system. Basically, there are two approaches for such deduction method and they are: Forward chaining starts with the available data and uses the inference rules to extract more data until a goal is found. It is also known as goal-driven reasoning. The main advantage of forward chaining is that the reception of new data can trigger new inference which makes the engine better suited to the dynamic situations in which conditions are likely to change. A form of reasoning that starts with conclusion and works backward is called Backward Chaining. Backward chaining starts with the list of goals to see if there is any data available which will support any of these goals.

Summary

Rules of inference are the process of deriving new facts from the given one or more existing facts. While undertaking this process we need to follow certain rules which are called as the rules of inference and they are AND-elimination, AND-introduction, OR-elimination, Double-Negation Elimination, Modus Ponen, Modus Tollen, Unit resolution and Transitivity rule. In propositional logic, it is easy to determine that the two literals can not be both true at the same time. Simply look for L and ~L . In a predicate logic, this matching process is more complicated since the bindings of variables must be considered. In order to determine contradictions, we need a matching procedure that compares two literals and discovers whether there exist a set of substitutions that makes them identical . There is a recursive procedure that does this matching . It is called Unification algorithm. In Unification algorithm, each literal is represented as a list, where the first element is the name of a predicate and the remaining elements are arguments. The argument may be a single element (atom) or may be another list. Resolution is the process which is equivalent to multi-state processing with all the premises given in DNF. Resolution in propositional logic can be done in two ways and they are by answer extraction method and by contradiction method. Rule-based deduction system is a system that derives a conclusion by using some rules is called rule-based deduction system. Basically, there are two approaches for such deduction method and they are: Forward chaining starts with the available data and uses the inference rules to extract more data until a goal is found. It is also known as goal-driven reasoning. The main advantage of forward chaining is that the reception of new data can trigger new inference which makes the engine better suited to the dynamic situations in which conditions are likely to change. A form of reasoning that starts with conclusion and works backward is called Backward Chaining. Backward chaining starts with the list of goals to see if there is any data available which will support any of these goals.

Things to Remember

  • Rules of inference are the process of deriving new facts from the given one or more existing facts.
  • While under taking this process we need to follow certain rules which are called as the rules of inference and they are AND-elimination, AND-introduction, OR-elimination, Double-Negation Elimination, Modus Ponen, Modus Tollen, Unit resolution and Transitivity rule. 
  • In propositional logic, it is easy to determine that the two literals can not be both true at the same time. Simply look for L and ~L . 
  • In a predicate logic, this matching process is more complicated since the bindings of variables must be considered.
  • In order to determine contradictions, we need a matching procedure that compares two literals and discovers whether there exist a set of substitutions that makes them identical. There is a recursive procedure that does this matching . It is called Unification algorithm.
  • In Unification algorithm, each literal is represented as a list, where the first element is the name of a predicate and the remaining elements are arguments. The argument may be a single element (atom) or may be another list.
  • Resolution is the process which is equivalent to multi-state processing with all the premises given in DNF. Resolution in propositional logic can be done in two ways and they are by answer extraction method and by contradiction method. 
  • Rule-based deduction system is a system that derives a conclusion by using some rules is called rule-based deduction system.
  • Forward chaining starts with the available data and uses the inference rules to extract more data until a goal is found. It is also known as goal-driven reasoning.
  • A form of reasoning that starts with conclusion and works backward is called Backward Chaining. Backward chaining starts with the list of goals to see if there is any data available which will support any of these goals.

MCQs

No MCQs found.

Subjective Questions

No subjective questions found.

Videos

No videos found.

Rules of Inference, Unification, Resolution Refutation System (RRS), Answer Extraction From RRS, Rule Based Deduction System,

Rules of Inference, Unification, Resolution Refutation System (RRS), Answer Extraction From RRS, Rule Based Deduction System,

Rules of Inference:

It is the process of deriving new facts from the given one or more existing facts. While undertaking this process we need to follow certain rules which is called as the rules of inference and they are presented below:

  1. AND-elimination: If P∧ Q∧ R............∧ Z is premised then P, Q, R, ......., Z is premised..
    From a conjunction of sentences, any of the conjunctions can be inferred.

  2. AND-introduction: If P, Q, R are individually premises then P∧ Q∧ R is also a premises..
    From a list of sentences their conjunction can be inferred.

  3. OR-elimination:
    .
    From a sentence, its disjunction with anything else at all can be inferred.

  4. Double-Negation Elimination:
    .

  5. Modus Ponen or Implication Elimination: From an implication and a premise we can derive a conclusion that is,
    .
    From two sentences a ⇒b and a that are true and are also called axioms hence the new true sentence b can be concluded. A theorem is proved with respect to the axioms that is the theorem logically follows from the axioms. For example: The sentence is "If sun shines it is warm" then,
    A: “sun shines”; B:“it is warm”.
    Axioms:
    A ⇒B.
    A.
    Theorem: B; that is“it is warm”.


  6. Modus Tollen: For an implication and negation of an implied premise we can derive a negation of given premise.
    .


  7. Unit Resolution: From two premises that are given in disjunctive normal form we can derive a resolution but it should be always in disjunctive form.
    .
    From a disjunction, if one of the disjuncts is false it can be inferred that the other one is true.

  8. Transitivity Rule:
    .
    Sinceβ cannot be both true and false one of the other disjuncts must be true in one of the premises. The implication is equivalently transitive otherwise.

Unification:

In propositional logic it is easy to determine that the two literals can not be both true at the same time. Simply look for L and ~L . In a predicate logic this matching process is more complicated since the bindings of variables must be considered.
For example man (john) and man(john) is a contradiction while man (john) and man(Himalayas) is not. Thus in order to determine contradictions we need a matching procedure that compares two literals and discovers whether there exist a set of substitutions that makes them identical . There is a recursive procedure that does this matching . It is called Unification algorithm.
In Unification algorithm each literal is represented as a list, where first element is the name of a predicate and the remaining elements are arguments. The argument may be a single element (atom) or may be another list.
The unification algorithm recursively matches pairs of elements, one pair at a time. The matching rules are :
  • Different constants , functions or predicates can not match, whereas identical ones can.
  • A variable can match another variable , any constant or a function or predicate expression, subject to the condition that the function or [predicate expression must not contain any instance of the variable being matched (otherwise it will lead to infinite recursion).
  • The substitution must be consistent. Substituting y for x now and then z for x later is inconsistent. (a substitution y for x written as y/x).

Resolution Refutation System (RRS):

Resolution is the process which is equivalent to multi-state processing with all the premises given in DNF. Resolution in propositional logic can be done in two ways and they are:
  • By answer extraction method
  • By contradiction method.

By answer extraction method:

In the simple example,

Axioms:
(∀x)(Bird(x) →Flies(x))
Bird(Tweety)
Goal: Flies(Tweety).

It is easy to establish the goal by using resolution. However, we must predetermine who it is and who does not fly. Suppose that we replace the above goal by the more general one which states that someone flies. Goal: (∃y)Flies(y) In that case, the proof process tells us who it is via the binding of y.

.

We must note that this will only give one instance of a solution. If the fact that Spike is also a bird is added to the hypothesis which is Bird (Spike). Then a separate proof is required to determine that Spike can fly..

In order to find all the answers one must generate all proofs (or do a special intelligent analysis of the problem). We should note that since inference in first-order logic is undecidable it is not always possible to search for all answers.

By contradiction method:

The following steps should be followed to prove the given premises using contradiction method:

  • Express the given sentence into FOPL that is first order predicate logic.
  • Convert all the FOPL into corresponding CNF.
  • Negate all the predicates to be proved and convert it into clausal normal form and add it to given premises.
  • Repeat all the following process until a contradiction is found or no progress is made.
    Take any two premises and find out resolvent.
    Add the resolvent into given premises.
  • If the contradiction is found then the negation of predicate to be proved is false otherwise it is true.

For example:

  1. Everyone who passes the AI exam and wins the lottery is happy.
  2. Everyone who studies or are lucky can pass all the exam.
  3. Ram did not study but he is lucky.
  4. Everyone who is lucky wins the lottery

Question: Is Ram happy?

We can solve this problem using contradiction method:

Convert all the sentences into FOPL.

  1. ∀x: passes (x, AI exam)∧ win (x, lottery)⇒ happy (x).
  2. ∀x:∀y: studies (x)∨ lucky(x)⇒ pass (x, y).
  3. ¬ study (Ram)∧ lucky (Ram).
  4. ∀x: lucky (x)⇒ wins (x, lottery).
  5. ¬ happy (Ram).

Again converting all the FOPL into CNF.

  1. ¬ (passes (x, AI)∧ wins (x, lottery))∨ happy(x).
    ¬ passes (x, AI) ∨¬ wins (x, lottery) ∨ happy(x).
  2. ¬ (studies (x) ∨ lucky (x)) ∨ pass (x, y).
    ¬ (studies (x) ∧¬ lucky (x)) ∨ pass (x, y).
    ¬ (studies (x)∨ pass (x, y))∧ (¬ lucky (x) ∨ pass (x, y)).

    ¬ studies (x)∨¬ pass (x,y).
    ¬ lucky (x)∨ pass (x,y).

  3. ¬ study (Ram).
    lucky (Ram).
  4. ¬ lucky (x)∨ wins (x, lottery).
  5. ¬ happy (Ram).

Rule Based Deduction System:

A system that derives a conclusion by using some rules is called rule-based deduction system. Basically there are two approaches for such deduction method.

  1. Forward Chaining: It is simple to understand and implement. Forward chaining starts with the available data and uses the inference rules to extract more data until a goal is found. It is also known as goal-driven reasoning. The main advantage of forward chaining is that the reception of new data can trigger new inference which makes the engine better suited to the dynamic situations in which conditions are likely to change.

  2. Backward Chaining: A form of reasoning that starts with conclusion and works backward is called Backward Chaining. Backward chaining starts with the list of goals to see if there is any data available which will support any of these goals.

References:

  1. Elaine Rich, Kevin Knight 1991, "Artificial Intelligence".
  2. Nilsson, Nils J. Principles of Artificial Intelligence, Narosa Publishing House New Delhi, 1998.
  3. Norvig, Peter & Russel, Stuart Artificial Intelligence: A modern Approach, Prentice Hall, NJ, 1995
  4. Patterson, Dan W. Introduction to Artificial Intelligence and Expert Systems, Prentice Hall of India Private Limited New Delhi, 1998.

Lesson

Knowledge Representation, Inference and Reasoning

Subject

Computer Engineering

Grade

Engineering

Recent Notes

No recent notes.

Related Notes

No related notes.