Expert System

“An expert system is a computer system that emulates with the decision making capabilities of a human expert.”

專家系統是模擬人類專家決策能力的電腦系統

“An intelligent computer program that uses knowledge and inference procedures to solve problems that are difficult enough to require significant human expertise for their solutions”.

一種智慧型電腦程序，它使用知識和推理程序來解決非常困難、需要大量人類專業知識才能解決的問題

Developing expert systems needs strong methods

• Knowledge representations
  • Representing that real world knowledge within computers
    (在電腦中表示現實世界的知識)
  • Logic vs. graphical notation vs. frame-based notation
    (邏輯與圖形符號與基於框架的符號)
• Inference on knowledge
  • Making inference to solve programs
    (進行推理來解決程序)
  • Forward chaining vs. backward chaining

Strong AI vs. Weak AI

• Strong AI
  • A computer can literally think and can be conscious in the same way that a human is conscious
    (電腦確實可以思考，並且可以像人類一樣有意識)
    • giving a computer program sufficient processing power (賦予電腦程式足夠的處理能力)
    • providing it with enough intelligence (為其提供足夠的情報)
• Weak AI
  • A computer cannot actually intelligent in the way that a human is (電腦實際上無法像人類那樣有智慧的思考)
    • the intelligent behavior is merely modeled by humans and used by computers to solve complex problems (智能行為只是由人類建模並由電腦用來解決複雜問題)
    • emotions and real consciousness are not reachable (情感和真實意識無法實現)

Strong Methods vs. Weak Methods

• Do not be confused with strong AI and weak AI
• Weak methods in AI
  • Use logic, reasoning, and other general structures to solve a wide range of problems (使用邏輯、推理和其他通用結構來解決廣泛的問題)
  • General methods (methods that work on a large variety of problems, 通用方法)
  • It is not necessary to incorporate real world knowledge
• Strong methods in AI
  • Given a great deal of knowledge about the problem and the real world. (擁有大量有關問題和現實世界的知識)
  • Methods specially designed and tailored to work efficiently on particular problems. (專門設計和客製化的方法，可有效解決特定問題)
  • Use weak methods to deal with knowledge

Knowledge Representation

• Predicate Logic 謂詞邏輯
  • Builder(Bob) ∧ Dog(Fido) ∧ Cat(Fang) ∧ owns(Bob,Fido) ∧ eats(Bob,Cheese) ∧ chases(Fido,Fang) ∧ chases(Fang,Mise) ∧ eat(Mice,Cheese)
• Semantic Nets 語意網
  
• Frame
  ​​​​+------------+--------+------------+
  ​​​​| Frame Name | Slot   | Slot Value |
  ​​​​+------------+--------+------------+
  ​​​​| Bob        | is a   | Builder    |
  ​​​​|            +--------+------------+
  ​​​​|            | owns   | Fido       |
  ​​​​|            +--------+------------+
  ​​​​|            | eats   | Cheese     |
  ​​​​+------------+--------+------------+
  ​​​​| Fido       | is a   | dog        |
  ​​​​|            +--------+------------+
  ​​​​|            | chases | Fang       |
  ​​​​+------------+--------+------------+
  ​​​​| Fang       | is a   | Cat        |
  ​​​​|            +--------+------------+
  ​​​​|            | chases | Mice       |
  ​​​​+------------+--------+------------+
  ​​​​| Mice       | eat    | Cheese     |
  ​​​​+------------+--------+------------+
  

Inference

• Forward chaining
  • data-driven
• Backward chaining
  • goal-driven

Example - Forward Chaining

• The Goal is to conclude the color of the alien Keroro, given that he croaks and play gunpla.
• The rule base contains
  1. If X croaks and X plays gunpla – then X is an alien frog
  2. If X macerates food and X produces mucus – then X is an alien slug
  3. If X is an alien frog – then X is green
  4. If X is an alien slug – then X is yellow
• Given facts -> #1 -> #3

Example - Backward Chaining

• Suppose a new life form, Keroro, is travelling to Earth with a space ship with two facts about Keroro:
  • Keroro croaks
  • Keroro plays gunpla
• The goal is to decide whether Keroro is green, based on a rule base containing the following rules:
  1. If X croaks and X plays gunpla – then X is an alien frog
  2. If X macerates food and X produces mucus – then X is an alien slug
  3. If X is an alien frog – then X is green
  4. If X is an alien slug – then X is yellow
• #3 -> #1 -> given facts

AI Programming Languages

• Prolog (PROgramming in LOGic)
  • Build a database of facts and rules (in logic)
  • Answer questions by a process of logical deduction
  • Backward chaining (backtracking)
• LISP (LISt Programming)
  • Use lists to represent programs and data
  • Provide list manipulation functions to handle lists
  • Forward chaining
• CLIPS (C Language Integrated Production System)
  • Build a Knowledge base (rules)
  • Match known facts and the rules (inference engine)
  • Forward chaining

Expert System Main Components

• Knowledge base
  • obtainable from books, magazines, knowledgeable persons, etc.
• Inference engine
  • draws conclusions from the knowledge base

Problem Domain vs. Knowledge Domain

• An expert’s knowledge is specific to one problem domain
  • medicine, finance, science, engineering, etc.
• The expert’s knowledge about solving specific problems is called the knowledge domain.
• The problem domain is always a superset of the knowledge domain.

Representing the Knowledge

• The knowledge of an expert system can be represented in a number of ways, including IF-THEN rules:
  • IF you are hungry THEN eat

Knowledge Engineering

• The process of building an expert system:
  1. The knowledge engineer establishes a dialog with the human expert to elicit knowledge. (知識工程師與人類專家對話以獲得知識。)
  2. The knowledge engineer codes the knowledge explicitly in the knowledge base. (知識工程師在知識庫中明確地編碼知識。)
  3. The expert evaluates the expert system and gives a critique to the knowledge engineer. (專家對專家系統進行評價並對知識工程師提出建議。)

Development of an Expert System

The Role of AI

• An algorithm is an ideal solution guaranteed to yield a solution in a finite amount of time.
• When an algorithm is not available or is insufficient, we rely on artificial intelligence. (當演算法不可用或無法滿足時，我們依靠人工智慧。)
• Expert system relies on inference
  • we accept a “reasonable solution” or “feasible solution”

Limitations of Expert Systems

• It is easier to program expert systems with shallow knowledge than with deep knowledge
• Lack of causal knowledge (deep knowledge)
  (缺乏因果知識（深層知識）)
  • do not really have an understanding of the underlying causes and effects in a system. (沒有真正了解系統的根本原因和影響。)
• Typical expert systems cannot generalize through analogy to reason about new situations in the way people can. (典型的專家系統無法像人們一樣透過類比來推理新情況。)
• Knowledge acquisition is the bottleneck of building an expert system. (a time-consuming and labor intensive task)
  (知識獲取是建構專家系統的瓶頸。 （一項耗時耗力的工作。）)

Shallow Knowledge vs. Deep Knowledge

• Shallow Knowledge
  • based on empirical and heuristic knowledge (based on syntax)
    (基於經驗和啟發式知識（基於文法）。)
    • Algorithmic：guaranteed to have a solution
    • Heuristic 啟發式：no guarantee
• Deep Knowledge (Causal Knowledge, 因果知識)
  • based on the basic structure, function, and behavior of objects (based on semantics)
    (基於物件的基本結構、功能和行為（基於語義）。)
• Example：
  • Prescribe an aspirin for a person’s headache (shallow)
  • Programming of a causal model of a human body (deep)

Problems with Algorithmic Solutions

• Conventional computer programs generally solve problems having algorithmic solutions.
• Algorithmic languages include C, Java, and VB.
• The inability to deal with knowledge-intensive applications or heuristic problem-solving
  (無法處理知識密集應用或啟發式問題。)
• Classic AI languages include LISP and PROLOG, both used for symbolic manipulation.
• Expert system languages (e.g. CLIPS) focus on ways to represent knowledge

Elements of an Expert System

• Knowledge base – rules
• Working memory – facts used by rules
• Inference engine – makes inferences deciding which rules are satisfied and prioritizing.
• Agenda – a prioritized list of rules in the inference engine
• Explanation facility – explains reasoning of expert system
• Knowledge acquisition facility – the user to enter knowledge in the system bypassing the knowledge engineer
• User interface – mechanism by which user and system communicate.

Structure of a Rule-Based Expert System

Production Rules

• Knowledge base contains production rules
  • KB is also called production memory
• Production rules can be expressed in IF-THEN format
• In rule-based systems, the inference engine
  • determines which rule antecedents (IF parts) are satisfied by the facts
  • determines a prioritized list of rules

General Methods of Inferencing

• Forward chaining
  • reasoning from facts to the conclusions resulting from those facts – best for prognosis, monitoring, and control.
  • Data driven
• Backward chaining
  • reasoning in reverse from a hypothesis, a potential conclusion to be proved to the facts that support the hypothesis – best for planning problems.
  • Goal driven

Knowledge in Rule-Based Systems

• Knowledge is of primary importance in expert systems.
• In Pascal:
  • Algorithms + Data Structures = Programs
• In expert systems
  • Knowledge + Inference = Expert Systems

---

• Knowledge is part of a hierarchy.
• Knowledge refers to rules that are activated by facts or other rules.
• Activated rules produce new facts or conclusions.
• Conclusions are the end-product of inferences when done according to formal rules.

Expert Systems vs. Humans

• Expert systems infer – reaching conclusions as the end product of a chain of steps called inferencing when done according to formal rules.
• Humans reason

Expert Systems vs. ANS

• ANS (Artificial Neural System, 人工神經網路) does not make inferences but searches for underlying patterns.
  • E.g. how do you read letters? What if the letters rotates 180 degrees?
• Expert systems
  • Draw inferences using facts
  • Separate data from noise
  • Transform data into information
  • Transform information into knowledge

Noise or Data

• Consider the following sequence of 24 numbers
  • 137178766732525156430015
• Without knowledge, this entire sequence may appear to be noise.
• What is noise and what is data? The difference?
  • An old saying:
    • "A weed is anything that grows which isn’t what you want."

Transforming

• Applying the following algorithm to the above sequence
  • Group the numbers by twos.
    • 13 71 78 76 67 32 52 51 56 43 00 15
  • Ignore any two-digit numbers less than 32.
    • 71 78 76 67 32 52 51 56 43
  • Substitute the ASCII characters for the two-digit numbers.
    • G O L D 4 3 8 +
• The 24 numbers yields
  • GOLD 438+
• What next?!

Applying Knowledge

• Now knowledge can be applied to this information.
  • For example:
    • IF gold is less than 500 and the price is rising (+)
    • THEN buy gold
• Above is what an expert system may do
  1. separate data from noise
  2. transform data into information
  3. transform information into knowledge

Metaknowledge

• Metaknowledge is knowledge about knowledge and expertise. (“meta” means “above”)
• Most successful expert systems are restricted to as small a domain as possible.
• In an expert system, an ontology is the metaknowledge that describes everything known about the problem domain.
• Wisdom is the metaknowledge of determining the best goals of life and how to obtain them.

Logic

Deductive Logic 演繹邏輯

• Argument 論證
  • group of statements where the last is justified on the basis of the previous ones
• Deductive logic can determine the validity of an argument.
• Syllogism 三段論
  • has two premises (前提) and one conclusion
• Premises are also called antecedent, conclusion is called the consequent.
• Deductive argument
  • conclusions reached by following true premises must themselves be true

Syllogisms vs. Rules

• Syllogism
  ​​​​- All basketball players are tall.
  ​​​​- Jason is a basketball player.
  ​​​​---------------------------------
  ​​​​∴ Jason is tall.
  

• IF-THEN rule
  ​​​​IF    All basketball players are tall and
  ​​​​      Jason is a basketball player.
  ​​​​THEN  Jason is tall.
  

Categorical Syllogism

• Premises and conclusions are defined using categorical statements of the form

+--------+------------------+------------------------+
| Form   | Schema           | Meaning                |
+----------------------------------------------------+
| A      | All S is P       | universal affirmative  |
| E      | No S is P        | universal negative     |
| I      | Some S is P      | particular affirmative |
| O      | Some S is not P  | particular negative    |
+----------------------------------------------------+

      middle term - common to both premises
      ↓
  All A is B    <-- the major premise because it contains the 'major term'
  All C is A    <-- the minor premise because it contains the 'minor term'
--------------
∴ All C is B
      ↑    ↑
           predicate of the conclusion is called the 'major term'
      C - the subject of the conclusion is called the 'minor term'

• To write the syllogism in standard form, we would write:
  ​​​​Major Premise:    All A is B
  ​​​​Minor Premise:    All C is A
  ​​​​---------------------------------
  ​​​​Conclusion      ∴ All C is B
  

The Mood of a Syllogism

• Defined by the three letters in the form of major premise, minor premise, and conclusion.
  • e.g.
    • ​​​​​​​​​​  All M is P
      ​​​​​​​​​​  All S is M
      ​​​​​​​​​​-------------------
      ​​​​​​​​​​∴ All S is P
      

    • Is an AAA mood (AAA-1)
• There four possible patterns of arranging the S, P, M terms
  ​​​​+---------------+----------+-----------+-----------+----------+
  ​​​​|               | Figure1  | Figure2   | Figure3   | Figure4  |
  ​​​​+---------------+----------+-----------+-----------+----------+                
  ​​​​| Major premise | MP       | PM        | MP        | PM       |
  ​​​​| Minor premise | SM       | SM        | MS        | MS       |
  ​​​​+---------------+----------+-----------+-----------+----------+
  

• Consider the AEE-1 syllogism
  • ​​​​​​  All M is P
    ​​​​​​  No S is M
    ​​​​​​--------------
    ​​​​​​∴ No S is P
    

  • Is not a valid syllogism
  • e.g.
    • All microcomputers are computers
    • No mainframe is a microcomputer
    • $\Rightarrow$ No mainframe is a computer

Decision Procedure of a Syllogism

• Can be done by using Venn diagrams.
  • Using shaded or lined section to indicate that there are no elements in that portion
  • AEE-1
    • ​​​​​​​​​​  All M is P
      ​​​​​​​​​​  No S is M
      ​​​​​​​​​​--------------
      ​​​​​​​​​​∴ No S is P
      

  • EAE-1
    • ​​​​​​​​​​  No M is P
      ​​​​​​​​​​  All S is M
      ​​​​​​​​​​--------------
      ​​​​​​​​​​∴ No S is P
      

Proving the Validity of Syllogistic Arguments Using Venn Diagrams

• If a class is empty, it is shaded.
• Universal statements, A and E are always drawn before particular ones.
• If a class has at least one member, mark it with an *.
• If a statement does not specify in which of two adjacent classes an object exists, place an * on the line between the classes.
• If an area has been shaded, not * can be put in it.

---

• Try to prove the following syllogism using Venn diagram:
  • ​​​​​​  Some computers are laptops
    ​​​​​​  All laptops are transportable
    ​​​​​​------------------------------------
    ​​​​​​∴ Some transportables are computers
    

  • Which can be put in IAI-4 types
    • ​​​​​​​​​​  Some P are M
      ​​​​​​​​​​  All M are S
      ​​​​​​​​​​-----------------
      ​​​​​​​​​​∴ Some S are P
      

Rules of Inference

• Venn diagrams are insufficient for complex arguments.
• Syllogisms address only a small portion of the possible logical statements.
  • Categorical statements of the A, E, I, and O form.
• Propositional logic (命題邏輯) offers another means of describing arguments.

Direct Reasoning Modus Ponens

If I am hungry, I will eat.
I am hungry.
---------------------------
∴ I will eat.

A = I am hungry.
B = I will eat.

A -> B
A
-------
∴ B

Modus Ponens

• Constant propositions
  • Using uppercase letters, such as A, B, C…
  • e.g. “There is power”
• Logical variables
  • Using lowercase letters, such as p, q, r…
  • Stands for different constant propositions.
• Different notation for modus ponens
  • ​​​​​​r -> s
    ​​​​​​r
    ​​​​​​------
    ​​​​​​∴ s
    

  • r, r -> s; ∴ s

Truth Table Modus Ponens

p -> q
p
------
∴ q

Is valid because it can be expressed as a tautology
((p -> q) ^ p) -> q

+---+---+--------+--------------+-------------------+
| p | q | p -> q | (p -> q) ^ p | (p -> q) ^ p -> q |
+---+---+--------+--------------+-------------------+
| T | T |    T   |       T      |         T         |
+---+---+--------+--------------+-------------------+
| T | F |    F   |       F      |         T         |
+---+---+--------+--------------+-------------------+
| F | T |    T   |       F      |         T         |
+---+---+--------+--------------+-------------------+
| F | F |    T   |       F      |         T         |
+---+---+--------+--------------+-------------------+

short-form truth table

p -> q
q
------
∴ p

Is this a valid argument?
Using the truth table to check the result.
((p -> q) ∧ q) -> p

+-------+------------+------------+
|       |  Premises  | Conclusion |
+---+---+--------+---+------------+
| p | q | p -> q | q |      p     |
+---+---+--------+---+------------+
| T | T |    T   | T |      T     |
+---+---+--------+---+------------+
| T | F |    F   | F |      T     |
+---+---+--------+---+------------+
| F | T |    T   | T |      F     |
+---+---+--------+---+------------+
| F | F |    T   | F |      F     |
+---+---+--------+---+------------+

p -> q
~q
------
∴ ~p

Is this a valid argument? 
Using the truth table to check the result.
((p -> q) ^ ~q) -> ~p

+-------+-------------+------------+
|       |   Premises  | Conclusion |
+---+---+--------+----+------------+
| p | q | p -> q | ~q |     ~p     |
+---+---+--------+----+------------+
| T | T |    T   |  F |      F     |
+---+---+--------+----+------------+
| T | F |    F   |  T |      F     |
+---+---+--------+----+------------+
| F | T |    T   |  F |      T     |
+---+---+--------+----+------------+
| F | F |    T   |  T |      T     |
+---+---+--------+----+------------+

Some Rules of Inference

1. Law of Detachment
   • p -> q, p; ∴ q
2. Law of the Contrapositive
   • p -> q; ∴ ~q -> ~p
3. Law of Modus Tollens
   • p -> q, ~q; ∴ ~p
4. Chain Rule (Law of the Syllogism)
   • p -> q, q -> r; ∴ p -> r
5. Law of Disjunctive Inference
   • p v q, ~p; ∴ q
   • p v q, ~q; ∴ p
6. Law of the Double Negation
   • ~(~p); ∴ p
7. De Morgan's Law
   • ~(p ^ q); ∴ ~p v ~q
   • ~(p v q); ∴ ~p ^ ~q
8. Law of Simplification
   • p ^ q; ∴ p
   • ~(p v q); ∴ ~q
9. Law of Conjunction
   • p, q; ∴ p ^ q
10. Law of Disjunctive Addition
    • p; ∴ p v q
11. Law of Conjunctive Argument
    • p; ∴ ~q
    • q; ∴ ~p

---

• Consider the following argument:
  • Chip prices rise only if the yen rises.
  • The yen rises only if the dollar falls and if the dollar falls then the yen rises.
  • Since chip prices have risen, the dollar must haven fallen.
• Let the propositions be defined as follows:
  • C = chip prices rise
  • Y = yen rises
  • D = dollar falls
• The entire argument has the following form:
  • ​​​​​​C -> Y
    ​​​​​​(Y -> D) ^ (D -> Y)
    ​​​​​​C
    ​​​​​​------------------
    ​​​​​​∴ D
    

• If the conditional p -> q and its converse q -> p are both true, the p and q are equivalent
• The argument becomes
  • ​​​​​​C -> Y
    ​​​​​​Y ≡ D
    ​​​​​​C
    ​​​​​​------
    ​​​​​​∴ D
    

• Since Y ≡ D, replace Y with D
  • ​​​​​​C -> D
    ​​​​​​C
    ​​​​​​------
    ​​​​​​∴ D
    

Limitations of Propositional Logic

• If an argument is invalid, it should be interpreted as such – that the conclusion is necessarily incorrect.
• An argument may be invalid because it is poorly concocted.
• An argument may not be provable using propositional logic, but may be provable using predicate logic.
  • Consider the Socrates example.
    • ​​​​​​​​​​All men are moral
      ​​​​​​​​​​Socrates is a man
      ​​​​​​​​​​------------------
      ​​​​​​​​​​Therefore, Socrates is moral
      

  • Try to prove it with Venn Diagram and propositional logic.

First-Order Predicate Logic

• Syllogistic logic can be completely described by predicate logic

  Type	Schema	Predicate Representation
  A	All S is P	(∀x)(S(x) -> P(x))
  E	No S is P	(∀x)(S(x) -> ~P(x))
  I	Some S is P	(∃x)(S(x) ^ P(x))
  O	Some S is not P	(∃x)(S(x) ^ ~P(x))

• The Rule of Universal Instantiation states that an individual may be substituted for a universe.
  • Re-consider the example in the previous slide.
    • Let H = man, M = mortal, and s = Sorcrates

Logic Systems

• A logic system is a collection of objects such as rules, axioms, statements, and so forth in a consistent manner.
• Each logic system relies on formal definitions of its axioms (postulates) which make up the formal definition of the system.
• Axioms cannot be proven from within the system.
  • An axiom is simply a fact or assertion
• From axioms, it can be determined what can be proven.

Goals of a Logic System

• Be able to specify the forms of arguments – well-formed formulas (wffs).
  • e.g. All S is P is wffs.
  • But All, All is S P, Is S all are not wffs.
• Indicate the rules of inference that are valid.
• Extend itself by discovering new rules of inference that are valid, extending the range of arguments that can be proven – theorems.

Requirements of a Formal System

1. An alphabet of symbols.
2. A set of finite strings of these symbols, the wffs.
3. Axioms, the definitions of the system.
4. Rules of inference, which enable a wff to be deduced as the conclusion of a finite set of other wffs – axioms or other theorems of the logic system.
5. Completeness – every wff can either be proved or refuted (反駁).
   • Refute means to prove some assertion is false.
6. The system must be sound – every theorem is a logically valid wff.

Interpretation & Model

• An assignment of truth values is an interpretation of a wff.
• A model is an interpretation in which the wff is true.
• For example
  • A model of p -> q is p = T and q = T.
• A wff is called consistent or satisfiable if there is an interpretation that makes it true.
• Inconsistent or unsatisfiable if the wff is false in all interpretations. (such as p ^ ~p)
• A wff is valid if it is true in all interpretation; else it is invalid. ( p v ~p is valid, p -> q is an invalid wff)
• A wff is proved if it can be shown to be valid.
• All propositional wffs can be proved by truth table method, and so the propositional calculus is decidable.
• However, the predicate calculus is not decidable (or semidecidable) since there is no general method of proof like truth table for all predicate calculus wffs.

Example of a Formal System

• Alphabet: the single symbol "1"
• Axiom: The string "1"
• Rule of inference: If any string $ is a theorem, then so is the string $11.
  • $ -> $11
  • If $ = 1 then this rule gives $11 = 111.
  • If $ = 111 then this rule gives $11 = 11111.

Orders of logic

• A first-order language
  • the quantifiers operate on objects that are variables such ∀x.
• A second-order language
  • Have additional features such as two kinds of variables and quantifiers.
  • Can have quantifiers that range over function and predicate symbols.
  • Example: equality axiom
    • Two objects are equal if all predicates of them are equal.
    • x = y ≡ (∀P) [P(x) <-> P(y)], where P is any predicate of one argument.

Resolution

• Before resolution can be applied, the wff must be in a normal or standard form.
  • To express wffs with only ^, v, and possibly ~.
• Three main types of normal forms
  • Conjunctive normal form,
    • (P1 v P2 v…) ^ (Q1 v Q2 v…) ^…(Z1 v Z2 v…)
      • Pi must be literals, which means that they contain no logical connectives such as the conditional and biconditional, or quantifiers.
  • Clausal form,
    • A set of wffs w1, w2, … wn is in Clausal form if each wi is a clause. i.e. it is a disjunction of literals
  • And its Horn clause subset
    • A Horn clause is a clause with at most one positive literal
• The conversion to normal form is necessary because resolution is an operation on pairs of disjuncts.
• Example
  • A1, A2, …, An -> B1, B2, …, Bm
    • Can be written in standard predicate notation
  • A1 ^ A2 … An -> B1 v B2 … Bm
    • This can be expressed in disjunctive form using p -> q ≡ ~p v q
  • ~(A1 ^ A2 … An) v (B1 v B2 … Bm)
    • With de Morgan's Law
  • ≡ ~A1 v ~A2 … ~An v B1 v B2 … Bm
• reductio ad absurdum 反證法
  • A classical method to prove a theorem, also known as method of contradiction.
• The basic goal of resolution is to infer a new clause, the resolvent, from two other clauses called parent clauses.

• Given a theorem C
  • A1 ^ A2 … AN ├ C
  • Is equivalent to stating:
  • (1) A1 ^ A2 … AN -> C ≡ ~(A1 ^ A2 … AN) v C
  • ≡ ~A1 v ~A2 … ~AN v C
• The negation will be
  • (2) ~[A1 ^ A2 … AN -> C] ≡ A1 ^ A2 … AN ^ ~C
• If (1) is valid, then its negation (2) must be invalid.
  • In other word, if (1) is a tautology then (2) must be a contradiction.

Clauses and Resolvents

Resolution Refutation

Shallow and Causal Reasoning

• Experiential knowledge, another definition of shallow knowledge, is based on experience.
• In shallow reasoning, there is little/no causal chain of cause and effect from one rule to another.
• Advantage of shallow reasoning is ease of programming.
• e.g.
  • ​​​​​​(1) IF a car has        <-- All the knowledge is contained in the rule
    ​​​​​​       a good battery
    ​​​​​​       good sparkplugs
    ​​​​​​       gas
    ​​​​​​       good tires
    ​​​​​​    THEN the car can move
    

• Frames are used for causal / deep reasoning.
• Causal reasoning can be used to construct a model that behaves like the real system.

(2) IF the battery is good
    THEN there is electricity

(3) IF there is electricity
        and the sparkplugs are good
    THEN the sparkplugs will fire
    
(4) IF the sparkplugs fire
        and there is gas
    THEN the engine will run
    
(5) IF the engine runs and
        there are good tires
    THEN the car will move

• MUD expert system vs. medicine expert system
  • Shallow reasoning vs. Causal reasoning
• Because of the increased requirements for causal reasoning, it may become necessary to combine certain rules into a shallow reasoning one
  • Suppose we want to prove that rule (1) is a logical conclusion of rules (2)-(5)

Combining Rules

Other Inference Methods

• Analogy – relating old situations (as a guide) to new ones.
  • e.g. the 15 Game
• Generate-and-Test – generation of a likely solution then test to see if proposed meets all requirements.
• Abduction – Fallacy of the Converse
• Nonmonotonic Reasoning – theorems may not increase as the number of axioms increase.

Types of Inference