# Part IV: Peirce's rules

## Introduction

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).

## Next

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.

# Definitions

## Introduction

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.

## Definitions

### Negative context

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

```
<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[Proposition:
[Person: JohnTheBaptist]- - - - -[Christ: #]
]
"John the Baptist is not the Christ"
```

### Outermost context

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.

### Evenly enclosed

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:

```
<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[Proposition:

<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[Proposition:
[Men:
<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">\"</FONT>");
} else {
document.write("&forall;");
}
-->
]->(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:
<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">\"</FONT>");
} else {
document.write("&forall;");
}
-->
]->(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:

```
<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[Proposition:
[Situation:
[Person: John]<-(Agnt)<-[Act: Say]-
->(Thme)->
<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[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.

### Oddly enclosed

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)->
<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[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.

### Domination

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.

### Double negation

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

```
<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[Proposition:

<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[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".)

## Summary

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.

## Next

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

# Peirce's rules of inference

## Introduction

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.

## The rules

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.

## An axiom: The empty graph

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.

## Applying the rules

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

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

# Example of usage

## Introduction

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?

## Using one of Peirce's rules

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

```
<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[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:

```
<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[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

Next, we give another example.

# Another example of usage

## Introduction

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:

```
<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[Proposition:
P

<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[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".

## Application to Peirce's rules

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."

## Step 1

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

We will assume that this is true.

## Step 2

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.
```
<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[Proposition:

<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[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."

## Step 3

Then we apply the "Insertion" rule:

Insertion:
Any graph may be inserted in any oddly enclosed context.
```
<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[Proposition:
[Person: #I]<-(Expr)<-[State: Rich]

<!--
var agt=navigator.userAgent.toLowerCase();
var is_win = ( (agt.indexOf("win")!=-1) || (agt.indexOf("16bit")!=-1) );
var is_gecko = (agt.indexOf('gecko') != -1);
if (is_win && !is_gecko) {
document.write("<FONT FACE=\"Symbol\">&#216;</FONT>");
} else {
document.write("&not;");
}
-->
[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."

## Summary

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

Next, we have a summary.

# Summary

## Introduction

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.

## Negative contexts

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

## Evenly enclosed, oddly enclosed

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.

## Dominating context

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

## The five rules

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.

# The end

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

Next, we have some exercises.