CSE 473 Autumn 1998, Copyright, S. Tanimoto, Univ. of Washington 
Introduction to Artificial Intelligence (Oct 16, 1998)

"Using the Propositional Calculus"

• Why? To connect knowledge representation with sound inference methods
• Preparing English sentences for encoding
• Identifying atomic propositions
• Expressing logical relationships
• Making inferences with Modus Ponens
• Other rules of inference

Fundamental assumption:  much knowledge can be expressed as statements that are true or false.

Some of this knowledge takes the form of implications, If A then B.

There are logically sound rules of inference available for combining true-false statements.

These inferences can be performed by a computer.
 
 

An Example

"If both networks A and B are up, then John can send a message to the world gateway.  If either network C or D is up, then Marie can receive a message from the world gateway.  If John can send a message to the world gateway and Marie can receive a message from it, then John can send to Marie."

"If networks A is up and network B is up, then John can send a message to the world gateway.  If network C is up or network D is up, then Marie can receive a message from the world gateway.  If John can send a message to the world gateway and Marie can receive a message from the world gateway, then John can send a message to Marie."

P1: Network A is up.
P2. Network B is up.
P3: Network C is up.
P4: Network D is up.
Q1: John can send a message to the world gateway.
Q2: Marie can receive a message from the world gateway.
Q3: John can send a messsage to Marie.

1.  (P1 ^ P2) => Q1
2.  (P3 v P4) => Q2
3.  (Q1 ^ Q2) => Q3
 

((P1 ^ P2) => Q1) ^ ((P3 v P4) => Q2) ^ ((Q1 ^ Q2) => Q3)
 
 
 

Preparing English Sentences for Encoding

Substitute antecedents for pronouns.

Expand abbreviations.

Expand factored phrases so that each fact is expressed with a clause consisting of a subject and a predicate.
 

Identifying Atomic Propositions

Generally each clause represents one atomic proposition.

Due to wording variations, one atomic proposition might appear in English in several different forms.

Assign a proposition symbol (e.g., P, Q, R,  P1, P2, etc) to each atomic proposition.
 
 

Expressing Logical Relationships
 

Conjunctions normally use AND or BOTH == AND or ALL.

Disjunctions normally use OR or EITHER -- OR, or ANY.

Implications generally use  IF -- THEN -- or  WHENEVER x is true, y is true.

Negation uses NOT.

NEITHER -- NOR expresses a conjunction of negations.
 
 

Making Inferences with Modus Ponens

P,   P --> Q
therefore
Q

Forward Chaining:
P, P --> Q, Q --> R
therefore
R

.

Example Inferences

Add to the above list of premises:

4. P1
5. P2
6. P4

Prove Q3

Derivation...
7. P1 ^ P2  make conjunction of 4 and 5 explicit
8. Q1          apply modus ponens using 7 and 1.
9. P4 v P3  disjunctive syllogism with 6.
10. P3 v P4  commute in 9
11. Q2          apply modus ponents using 10 and 2.
12. Q1 ^ Q2  make conjunction of 8 and 11 explicit.
13. Q3          apply modus ponens using 12 and 3.

Q.E.D.  quod erat demonstrandum
 
 
 

Last modified: October 16, 1998