C.S. Peirce developed *existential graphs*, which is a way of
expressing propositional calculus using graphs. Peirce also developed
five rules of inference to go with his existential graphs, which can
be used for reasoning with existential graphs.

Conceptual graphs are a further development and refinement of Peirce's existential graphs. In this chapter, we present Peirce's rules of inference, reformulated so that they fit conceptual graphs. Much of the discussion was inspired by Lukose and Kremer's online course in Knowledge Engineering. Errors are mine, of course (see About for who the author of these materials is).

First, we give some definitions that are necessary for formulating the rules precisely. Next, we present the rules themselves and give some evidence for their validity. Finally, we give an example of how the rules are used to prove a statement.

In order to be able to formulate Peirce's rules precisely, we first need to give some definitions. The definitions will be accompanied by explanations and examples.

A *negative context* is a concept that has the negation-sign
in front of it:

[Proposition: [Person: JohnTheBaptist]- - - - -[Christ: #] ] "John the Baptist is not the Christ"

Every graph must -- explicitly or implicitly -- be part of a knowledge base, and every
knowledge base has an *outermost context*. The outermost
context is a concept of type Assertion whose referent is a collection
of conceptual graphs.

A concept or conceptual graph is said to be *evenly
enclosed* if, going outwards to the outermost context, we
encounter an even number of negative contexts on our way out.

For example:

[Proposition: [Proposition: [Men: ]->(Attr)->[Mortal] ] "It is not the case that it is not the case that all men are mortal" "All men are mortal"

here, the innermost graph,

[Men: ]->(Attr)->[Mortal]

is evenly enclosed because, going outwards towards the outermost context, we encounter an even number of negative contexts (in this case, 2).

Here is another example:

[Proposition: [Situation: [Person: John]<-(Agnt)<-[Act: Say]- ->(Thme)->[Proposition: [Person: #I]- - - -[Swindler] ] ] ] "It is not the case that there is the following situation: John said, 'I am not a swindler" "John never said, 'I am not a swindler"

Here, the innermost graph:

[Person: #I]- - - -[Swindler]

is evenly enclosed because we encounter an even number (two)
negative contexts on our way outwards to the outermost context.
Notice that there is an extra context, "Situation" in between the
outer negative context ("Proposition") and the inner negative context
(also "Proposition"). Thus the predicate *even* applies to
*negative contexts*, not just any contexts.

A concept or conceptual graph is said to be *oddly enclosed*
if, going outwards to the outermost context, we encounter an
*odd* number of negative contexts.

For example:

[Situation: [Person: JohnTheBaptist]<-(Agnt)<-[Act: Say]- ->(Thme)->[Proposition: [Person: #I]- - - -[Christ: #] ] ] "There is this situation: John the baptist says, 'I am not the Christ'".

Here, the innermost graph:

[Person: #I]- - - -[Christ: #]

is oddly enclosed because, on our way outwards to the outermost context, we meet an odd (one) number of negative contexts.

Again, it is precisely the number of *negative contexts* we
meet on our way that counts, not the number of contexts.

If a context y occurs nested in a context x, then x is said to
*dominate* y. This is true for any level of nesting that can
obtain between y and x.

For example:

[x: [y: [z] ] ]

y dominates z, while x dominates both y and z.

A double negation is two nested negative contexts of type Proposition, where one is directly nested inside the other:

[Proposition: [Proposition: // Content ] ]

If we draw a double negation around any conceptual graph, the effect is to leave the graph's meaning unchanged. This is because ((p)) is the same as p. (To see this, try to say, "It is not the case that I am not hungry" and derive the meaning, "I am hungry".)

A concept c is said to be a *negative context* if it has the
negation sign () in front of it.

A concept c is *evenly enclosed* if, going outwards from c
to the outermost context, we encounter an *even* number of
*negative contexts*. Likewise, a concept c is *oddly
enclosed* if, going outwards from c to the outermost context, we
encounter an *odd* number of negative contexts.

A concept x is said to *dominate* another concept y if y
occurs inside the referent of x. This is regardless of whether y
occurs directly in x's referent or nested inside x's referent.

A *double negation* is two negative contexts of type
Proposition where one is nested directly inside the other.

With these definitions, we are ready to formulate Peirce's rules.

Peirce's rules of inference can be used to reason with conceptual graphs. Here, we formulate the rules for conceptual graphs using the definitions we have just given.

- 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 a concept in 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 only axiom for Peirce's rules of inference is the empty graph. The empty graph says nothing about anything, and by convention is assumed to be true.

When one starts with a collection of conceptual graphs S and then
applies the rules to form another collection of conceptual graphs V,
we say that we have *proved* V from S.

If we start with the empty graph and prove a collection of
conceptual graphs V, V is said to be a *theorem*.

Next, we give an example of how to use the rules.

Most of us would argue that if it is true that "No cat is sleeping in the kitchen", then it is also true that "No black cat is sleeping in the kitchen". Adding the extra qualifier "black" does not change the truth-value of the statement. But how do we prove this?

With Peirce's rules, we can. Consider the following graph:

[Proposition: [Kitchen: #]<-(Loc)<-[Cat]<-(Expr)<-[Sleep] ] "No cat is sleeping in the kitchen".

Recall that one of the rules is:

- Insertion:
- Any graph may be inserted in any oddly enclosed context.

Since we have a graph (the Cat graph) that is oddly enclosed (in the negative Proposition context), we are entitled to add any graph. The new graph could look like this:

[Proposition: [Kitchen: #]<-(Loc)<-[Cat]<-(Expr)<-[Sleep] [Cat: #]->(Attr)->[Black] ] "No cat is sleeping in the kitchen. The cat that is not in the kitchen is black.". "No black cat is sleeping in the kitchen."

Next, we give another example.

In logic, there is a logical connective which is usually written as a long, single-lined arrow. It is used to connect two statements, e.g., p and q, like this:

p --> q

It means "If p is true, then q is true". According to the definition of this logical connective, this statement is true unless p is true but q is false. This also means that if p is false, then the whole statement is true regardless of whether q is true or false.

The statement can defined in terms of the boolean operators "and" and "not" as follows:

p --> q is equivalent to not(p and not(q))

This definition allows us to use Peirce's rules to form such a statement. It can be formulated as follows:

[Proposition: P [Proposition: Q ] ]

where P and Q stand for any conceptual graphs. Verify for yourself that this closely matches the definition.

Thus we have a way to say "if p is true, then q is true".

Consider the statement, "If I were rich, I would be happy". This is not generally true, of course, but this is just an example. What we are now going to do is to prove that, given that I am happy, then one reason for this could be that I am rich.

Thus we are going to start with the statement "I am happy" and apply Peirce's rules to say "If I am rich, then I am happy."

We start with the statement, "I am happy"

[Person: #I]<-(Expr)<-[State: Happy] "I am the experiencer of a State which is Happy."

We will assume that this is true.

Then we apply the "Double negation" rule:

- Double negation:
- A double negation may be drawn around or removed from any graph or set of graphs in any context.

[Proposition: [Proposition: [Person: #I]<-(Expr)<-[State: Happy] ] ]

The statement is still true:

"It is not the case that it is not the case that I am happy," which is equivalent to "I am happy."

Then we apply the "Insertion" rule:

- Insertion:
- Any graph may be inserted in any oddly enclosed context.

[Proposition: [Person: #I]<-(Expr)<-[State: Rich] [Proposition: [Person: #I]<-(Expr)<-[State: Happy] ] ] "It is not the case that: (I am rich AND it is not the case that: (I am happy))"

This perfectly fits our schema for the "if...then" statement. So what we have said, in effect, is "If I am rich, I am happy."

We started by assuming that I was happy. Therefore, there is nothing magical in this derivation. The statement is bound to be true, and we have just proved the statement "If I am rich, I am happy" from the true statement "I am happy". An implication can only be false if the premise is true and the conclusion is false. Since the conclusion is true, i.e., since it is true that I am happy, there is no way the implication can be false.

Next, we have a summary.

Peirce's rules of inference form a system of logic that is equivalent to First Order Predicate Logic. They can be used to reason using conceptual graphs.

A context is negative if it has the "not" symbol () in front of it.

A graph is said to be *evenly enclosed* if, going from the
graph outwards to the outermost level, we encounter an even number of
negative contexts. The term "oddly enclosed" is defined
analogously.

A context x is said to dominate a context y if y is nested somewhere inside x.

The five rules are:

- 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 a concept in 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.

You have reached the end of the main part of the course-material. Congratulations!

Next, we have some exercises.