Dickson Lukose,  Rob Kremer

KNOWLEDGE ENGINEERING, PART A: Knowledge Representation

index

Lecture 8. Reasoning and Computation

---

 8.1. Symbolic Logic

• Symbolic logic has two main branches:
• Propositional calculus; and
• Predicate Calculus.
• Frege's Begriffsschrift (1879) was the first complete form of predicate calculus, used a graphical notation. It was not popular because it took too much space on the printed page.
• The standard notation for symbolic logic was developed by Peano, Russell and Whitehead, who patterned it after algebra. The standard notation was presented by Giuseppe Peano (1889) and extended by Whitehead and Russell in the Principia Mathematica.
• Jan Lukasiewicz developed a prefix notation, which is commonly known as Polish notation. For complex formulas, most people find it more difficult to read than an infix notation.
• Lesniewski developed an elegant infix notation with highly symmetric rules of inference (Luschei, 1962).
• But of all the alternatives to Peano-Russell notation, one of the simplest and most elegant is Charles Sanders Peirce's notation of existential graphs (1897).
• Charles Sanders Peirce used the graph notation for his logic. He developed existential graphs (logic of the future). Existential graphs forms the logical basis for conceptual graphs:
• They have the full power of first-order logic;
• They can represent modal and higher-order logic;
• The rules of inference are simple and elegant;
• The notation is easily adapted to conceptual graphs.

8.2. Propositional Calculus

• Propositional calculus deals with statements or propositions and the connections between them.
• A symbol m, for example, could represent the proposition, Lillian is the mother of Leslie.
• In propositional calculus, a formula is either:
• an atom ( a single letter like p that represents a proposition);
• a formula preceded by ~; or
• any two formulas A and B together with any dyadic Boolean operators.
• Beside symbols for propositions, propositional calculus also includes symbols for the following boolean operators:

Let p and q be any propositions.

Conjunction   (and)            p ^ q

Disjunction   (or)             p v q

Negation      (not)            ~p

Implication   (if - then)      p -> q

Biconditional (if-and-only-if) p <-> q

• Boolean operators are called truth functions because they take truth values as input and generate truth values as output.
• The above five boolean operators can by represented by using a pair of primitive boolean operators ~ and ^ as follows:

Disjunction   (or)             p v q    ~(~p ^ ~q)

Implication   (if - then)      p -> q   ~(p ^ ~(q))

Biconditional (if-and-only-if) p <-> q  ~(p^~q)^~(~p^q)

• In fact, only one primitive operator, either NAND or NOR, is necessary since both ~ and ^ can be defined in terms of either one of them:

Negation    (not) ~p     (p NAND p)

Negation    (not) ~p     (p NOR p)

Conjunction (and) p ^ q  (p NAND q) NAND (p NAND q)

Conjunction (and) p ^ q  (p NOR p) NOR (q NOR q)

• To derive true formulas from other true formulas, rules of inference are needed.
• In a sound theory, the rules of inference preserves truth.
• If all formulas in the starting set are true, only true formulas can be inferred from them.
• Some of the rules of inference for the propositional calculus are as follows:

Let symbols p, q and r represent any formulas whatever:
 

Modus Ponens.	From p and p -> q,	derive q.
Modus Tollens.	From ~q and p -> q, .	derive ~p
Hypothetical Syllogism.	From p -> q and q -> r,	derive p -> r.
Disjunctive Syllogism.	From p v q and ~p,	derive q.
Conjunction.	From p and q,	derive p ^ q.
Addition.	From p,	derive p v q .
this rule allows any formula whatever to be added to a disjunction.
Subtraction.	From p ^ q,	derive p.
this rule simplifies formulas by throwing away unneeded conjuncts.

 

• Following are some common identities. Either of the formulas in an identity can be substituted for any occurrence of the other, either alone or as part of some larger formula:

Idempotency.     p ^ p       is identical to p

                 p v p       is identical to p

Commutativity.   p ^ q       is identical to q ^ p

                 p v q       is identical to q v p

Associativity.   p ^ (q ^ r) is identical to (p ^ q) ^ r

                 p v (q v r) is identical to (p v q) v r

Distributivity.  p ^ (q v r) is identical to (p ^ q) v (p ^ r)

                 p v (q ^ r) is identical to (p v q) ^ (p v r)

Absorption.      p ^ (p v q) is identical to p

                 p v (p ^ q) is identical to p

Double Negation. p           is identical to ~~p

De Morgan's Law. ~(p ^ q)    is identical to ~p v ~q

                 ~(p v q)    is identical to ~p ^ ~q

• For example, let p, q and r be any formula.
1. Prove: (p v p) -> p

Derivation: (p v p) -> p
=> ~((p v P) ^ ~p) (Implication in the form of ~ and ^)
=> ~(p v P) v ~ ~ p (De Morgan's Law)
=> ~(p v p) v p (Elimination of Double Negation)
=> p (we know p is true, as it is given)
=> TRUE
2. Prove: q -> (p v q)

Derivation: q -> (p v q)
=> ~(q ^ ~(p v q))
=> ~q v ~~(p v q)
=> ~q v (p v q)
=> p v q
=> p
=> TRUE
3. Prove: (p v q) -> (q v p)

Derivation: (p v q) -> (q v p)
=> ~((p v q) ^ ~(q v p))
=> ~(p v q) v ~~(q v p)
=> ~(p v q) v (q v p)
=> (~p ^ ~q) v q v p
=> q v p
=> p
=> TRUE
4. Prove: (q -> r) -> ((p v q) -> (p v r))

Derivation: (q -> r) -> ((p v q) -> (p v r))
=> (q -> r) -> (~((p v q) ^ ~(p v r)))
=> (q -> r) -> (~(p v q) v ~~(p v r))
=> (q -> r) -> (~(p v q) v (p v r))
=> (q -> r) -> ((~p ^ ~q) v p v r)
=> (q -> r) -> p v r
=> (q -> r) -> p
=> ~(q ^ ~r) -> p
=> (~q v ~~r) -> p
=> (~q v r) -> p
=> ~((~q v r) ^ ~p)
=> ~(~q v r) v ~~p
=> ~(~q v r) v p
=> (~~q ^ ~r) v p
=> (q ^ ~r) v p
=> p
=> TRUE

8.3. Predicate Calculus

• Predicate calculus deals with predicates and connections between them.
• For example, in predicate calculus, the proposition Lillian is the mother of Leslie, would be represented by a predicate MOTHER applied to two individuals, as follows:
mother(Lillian, Leslie)
• In predicate calculus, a formula is either:
• n-adic predicate symbol applied to n arguments, each of which is a term (a term is either a constant like 2, a variable like x, or an n-adic function symbol applied to n arguments, each of which is itself a term);
• a formula preceded by ~;
• any two formulas A and B together with any dyadic Boolean operators; or
• any formula A and any variable x in either of the combination $xA or "xA.
• In First-Order Predicate Calculus, the rules of inference include the rules of inference of propositional calculus together with rules for handling quantifiers.
• Distinction between free occurrences and bound occurrences of a variable:
• If A is an atom, then all occurrences of a variable x in A are said to be free.
• If a formula C was derived from formulas A and B by combining them with boolean operators, then all occurrences of variables that are free in A and B are also free in C.
• If a formula C was derived from a formula A by preceding A with either "x or $x, then all free occurrences of x in A are said to be bounded in C. All free occurrences of other variables in A remain free in C.
• Rules of inference that deal with quantifiers:
 

Universal Instantiation.	From "xF(x), derive F(c), where c is any constant.
Existential Generalisation.	From F(c), where c is any constant, derive $xF(x), provided that every occurrence of x in F(x) must be free.
Dropping Quantifiers.	If the variable x does not occur free in F, then from $xF derive F, and from "xF derive F.
Adding Quantifiers.	From F derive "xF or derive $xF, where x is any variable whatever.
Substituting equals for equals.	From F(t) and t=u, derive F(u), provided that all free occurrence of variable in u remain free in F(u).

 
• The following are the identities common in predicate calculus:
• $xA is identical to ~"x~A
• "xA is identical to ~ $x~A
• For example, the following two formulas are equivalent:

"x(PEACH(x) -> FUZZY(x)) 
~$x(PEACH(x) ^ ~FUZZY(x))

• Derivation:

"x(PEACH(x) -> FUZZY(x)) 
=> ~$x~(PEACH(x) -> FUZZY(x)) 
=> ~$x~~(PEACH(x) ^ ~FUZZY(x)) 
=> ~$x(PEACH(x) ^ ~FUZZY(x))

• The order of quantifiers in symbolic logic makes a crucial difference, as it does in English. Consider the sentence Every man in department C99 married a woman who came from Boston, which may be represented by the formula:

 
"x$y ((MAN(x) ^ DEPT(x, C99)) -> (WOMAN(y) ^ HOMETOWN(y, BOSTON) ^ MARRIED(x, y))).
The above formula says that there exists a y such that for every x, if x is a man and x works in department C99, then y is a woman, the home town of y is Boston, and x married y.

Since the dyadic predicate MARRIED is symmetric, MARRIED(Ike, Mamie) is equivalent to MARRIED(Mamie, Ike).

Interchanging arguments of that predicate makes no difference, but interchanging the two quantifiers lead to the formula:

$y"x ((MAN(x) ^ DEPT(x, C99)) -> (WOMAN(y) ^ HOMETOWN(y, BOSTON) ^ MARRIED(x, y))).

This formula says that there exists a y such that for every x, if x is a man and x works in department C99, then y is a woman, the home town of y is Boston, and x married y.

In English, that would be the same as saying, A woman who came from Boston married every man in department C99.

If there are more than one man in department C99, this sentence has implication that are very different from the preceding one.

8.4. Existential Graphs

• Peirce's existential graphs take negation and conjunction as the two primitive boolean operators.
• There are two ways of writing existential graps:
• graphical form (drawings)
• linear form (pure text)
• A conjunction of two propositions are represented by writing both propositions on a sheet of paper. For example, if we want to represent the proposition p and q, then it is written simply as:

in graphical form;
"p q" in linear form;
equivalent to "p ^ q" in Peano-Russell notation.
• Peirce represents negation by a cut that partitions the negative context from the surrounding sheet of assertion.
• We represent a conjunction of propositions within a negative context with a round bracket, as follows:

in graphical form;
"(p q)" in linear form;
equivalent to ~(p ^ q) in Peano-Russell notation.
• Given that p, q and r any propositions, then the convention for representing positive and negative propositions:

 

Standard Notation	Graphical Form	Linear Form
p ^ q ^ r		p q r
~(p ^ q ^ r)		(p q r)
~~(p ^ q ^ r)		((p q r))

 
• Boolean combinations can be represented as follows:

 

Standard Notation	Equivalent Standard Notation	Graphical Form	Linear Form
p v q v r	~(~p ^ ~q ^ ~r)		((p) (q) (r))
p -> q	~(p ^ ~q)		(p (q))
p -> (q v r)	~(p ^ ~q ^ ~r)		(p (q) (r))
(p ^ q) -> (r ^ s)	~( p ^ q ~(r ^ s))		(p q (r s))
(p <-> q)	~(p ^ ~q) ^ ~(~p ^ q)		(p (q)) ((p) q)

 
 

• If a concept or conceptual graphs occurs in the outermost context, it is said to be enclosed at depth 0.
• If x is a negative context that is enclosed at depth n, then any graph or concept that occurs in the context of x is said to be enclosed at depth n + 1.
• For any integer n >= 0, a graph or concept enclosed at depth 2n is said to be evenly enclosed, and a graph or concept enclosed at depth 2n + 1 is said to be oddly enclosed.
• If a context y occurs in a context x, then x is said to dominate y. If y dominates another context z, then x also dominates z. The outermost context dominates all other contexts.

8.5. Peirce's Alpha Rules for Propositional Calculus

 

Erasure	Any evenly enclosed graph may be erased.
Insertion	Any graph may be inserted in any oddly enclosed context.
Iteration	A copy of any graph u may be inserted into the same context in which u occurs or into any context dominated by u.
Deiteration	Any graph whose occurrence could be the result of iteration may be erased (i.e., if it is identical to another graph in the same context or in a dominating context).
Double  Negation	A double negation may be drawn around or removed from any graph or set of graphs in any context.

 
• The empty set of graphs is the only logical axiom: it is written either as {} or as just a blank space. Any graph that is provable from {} by these rules is called a theorem.
• An empty set of graphs makes no assertion whatever. By convention, it is assumed to be true. The negation of the empty set, called the empty clause, must therefore be false: it is written as ().

4.3.3 Theorem. For any set S of conceptual graphs, the following three statements are equivalent:

• S is inconsistent.
• The negation of the empty set (), called the empty clause is provable from S.
• Any conceptual graphs whatever is provable from S.
• For example, prove the following are theorem:

(a) Prove:      (p v p) -> p 
    Graph Notation: (p v p) -> p 
                  => ~(~p ^ ~p) - > p 
                  => ~(~(~p ^ ~p) ^ ~p) 
                  => (((p) (p)) (p))
    Constriction:    {} 
                  => (()) 
                  => (() (p)) 
                  => (((p)) (p)) 
                  => (((p) (p)) (p))

(b) Prove:           q -> (p v q) 
    Graph Notation:  (q (p) (q)) 
    Construction:    {} 
                     (())       - double negation 
                     (q ())     - insertion of q 
                     (q (q) )   - iteration of q 
                     (q (q) (p))- insertion of (p)

(c) Prove:           (p v q) -> (q v p) 
    Graph Notation:  (((p) (q)) (p) (q)) 
    Construction:    <exercise>

(d) Prove:           (q -> r) -> ((p v q) -> (p v r)) 
    Construction:    <exercise>

• One can informally justify the rules of inference (due to Sowa):

 

Erasure.	A collection of graphs in a positive context is asserted to be true. Erasing any of them   leaves the remaining graphs just as true as they were before. If all the graphs are erased, the   empty sheet that is left says nothing false: silence is golden.
Insertion	A collection of graphs in a negative context is asserted to be false or at best hypothetical. Adding more graphs can never make the collection true. Therefore, the negative context remains false, and the negation of falsehood is true.
Iteration	Copying a subgraph in the same context makes a redundant copy that has no effect on the truth value. If a subgraph is copied into a nested context, its main contribution to the truth value was made in the outer context, and the copy has no effect on the truth value.
Deiteration	A copy of a subgraph in the same context or a nested context adds nothing new   to the truth value of the entire graph, and the nested copy may be erased without changing the   truth value.
Double  Negation	Two negations with nothing between the inner and outer oval cancel each   other out, and they may be added or erased without having any effect on the overall truth value.

 

8.6. Peirce's Beta Rules for Predicate Calculus

• The propositional rules of inference corresponds to Peirce's system Alpha. They treat each graph as a single, indivisable unit and do not allow graphs to be combined or split apart. Furthermore, they do not apply to graphs containing lines of identity.

• No concept may belong to more than one line of identity.
• A concept a in g is said to dominate another concept b if there is a path <a1, a2,....,an> in g where a=a1, b=an, and for each i, either ai and ai+1 both occur in the same context or the context of ai dominates the context of ai+1.
• Two concepts a and b are coreferent if either a dominates b or b dominates a.
• A concept a is dominant if a dominate every concept that dominates b.
• A collection of conceptual graphs connected by one or more line of identity is called a compound graph.
• A conceptual graph without any lines of identity or nested contexts is called a simple graph.
• Lines of identity show anaphoric references.
• Peirce generialised the Alpha rules to form his Beta rules which are equivalent to first-order predicate calculus.

 

Erasure	In an evenly enclosed context, any graph may be erased, any coreference link from a dominating concept to an evenly enclosed concept may be erased, any referent may be erased, and any type label may be replaced with a supertype.
Insertion	In an oddly enclosed context, any graph may be inserted, a coreference link may be drawn between any two identical concepts, and restriction may be performed on any concept.
Iteration	A copy of any graph u may be inserted into the same context in which u occurs or into any context dominated by u. A coreference link may be drawn from any concept of u to the corresponding concept in the copy of u. If concepts a and b in some context c are both dominated by a concept d on some line of identity, then a coreference link may be drawn from a to b.
Deiteration	Any graph or coreference link whose occurrence could be the result of iteration may be erased. Duplicate conceptual relations may be erased from any graph.
Double  Negation	A double negation may be drawn around or removed from any graph in any context.
Coreferent  Join	Two identical, coreferent concepts in the same context may be joined, and the coreference link between them may then be erased.
Individuals	If any individual concept a dominates a generic concept b where a and b are coreferent, the referent(a) may be copied to b, and then coreference link may be erased.

 
• The empty set of graphs {} is the only logical axiom. Any graph that is provable from {} by these rules is called a theorem.
• In oddly enclosed contexts, the rules add properties:
• they restrict a concept;
• adds graphs;
• join new parts to a graph; or
• add coreference links.
• In evenly enclosed contexts (including the outermost context, which is at level 0), the rules remove properties:
• they erase graphs;
• erase coreference links; and
• replace a concept with a more general one.
• Peirce's rules for drawing and erasing coreference links replace the standard rules of universal instantiation and existential generalisation.
• Example:

Given the following law defining citizenship in the Land of Oz.

( [person:*x]<-(obj)<-[born]->(loc)->[country:oz]             r1 
    ([citizen:*x]<-(memb)<-[country:oz]) 
) 
( [person:*x]<-(chld)<-[citizen]<-(memb)<-[country:oz]        r2 
    ([citizen:*x]<-(memb)<-[country:oz]) 
)
( [person:*x]<-(rcpt)<-[naturalise]->(loc)->[country:oz]      r3 
    ([citizen:*x]<-(memb)<-[country:oz]) 
) 
( [citizen:*x]<-(memb)<-[country:oz]                          r4 
    ( [person:*x]<-(obj)<-[born]->(loc)->[country:oz] ) 
    ( [person:*x]<-(chld)<-[citizen]<-(memb)<-[country:oz] ) 
    ( [person:*x]<-(rcpt)<-[naturalise]->(loc)->[country:oz] ) 
)

Suppose that the outermost context contain the above four graphs together with the following graph:

[person:tinman]<-(rcpt)<-[naturalise]->(loc)->[country:oz]

By iteration, a copy of this graphs may be inserted into the r3 to produce a graph as shown below:

( [person:tinman]<-(rcpt)<-[naturalise]->(loc)->[country:oz] 
   [person:*x]<-(rcpt)<-[naturalise]->(loc)->[country:oz] 
      ([citizen:*x]<-(memb)<-[country:oz]) 
)

The two oddly enclosed graphs may be joined: first [person] is restricted to [person:tinman]; then a coreference link is drawn between them; finally, they are joined.

Similar joins of [naturalise] to [naturalise] and [country:oz] to [country:oz] may be made.

The duplicate copies of (rcpt) and (loc) may be erased by deiteration.

Next, the referent Tinman may be copied to the coreferent concept [citizen] in the innermost context and the coreference link erased.

The resulting graph is shown below:

( [person:tinman]<-(rcpt)<-[naturalise]->(loc)->[country:oz] 
       ([citizen:tinman]<-(memb)<-[country:oz]) 
)

By deiteration, the oddly enclosed graph may be erases because it is an exact copy of the graph that says the Tinman was naturalised in Oz.

The result is the following graph:

( 
    ([citizen:tinman]<-(memb)<-[country:oz]) 
)

Removal of double negation results in the following graph:

[citizen:tinman]<-(memb)<-[country:oz]

Dickson Lukose &  Rob Kremer.  KNOWLEDGE ENGINEERING, PART A: Knowledge Representation.  July 1996.

index