THEORY OF PEIRCE LOGIC

CHAPTER 1 – SYSTEM ALPHA

Basic Ideas

Charles Sanders Peirce invented several forms of notation for logic and these are documented elsewhere but the one that he settled on was his “Existential Graphs”. This system is a purely graphical notation which can express any logical relationship whatever and which has a set of very simple “inference rules” or operations that can be performed on the graphs. In addition there is only one axiom.

Existential Graphs was chosen by Sowa as the logical basis for Conceptual Graphs. This was because Existential Graphs maps most easily to the way logical relationships are expressed in most natural languages. This is also the reason why Peirce himself preferred Existential Graphs to his other systems, notably his “Entiative Graphs”.

Others have written about the “soundness” and “completeness” of existential graphs and so there is none of that here. Nevertheless where a new result is presented it is justified in terms of Existential Graphs with the assumption that Existential Graphs is sound and complete.

System Alpha deals with whole propositions – statements which stand by themselves and do not submit to any decomposition. It is therefore a form of “Propositional Calculus”. Propositional calculus is limited in applicability because it does not allow the decomposition of propositions but we discuss System Alpha here because it introduces the main logical primitives in a straightforward way, and because it exists.

System Alpha

The Sheet Of Assertion

Peirce always wrote in very ornate language and his terminology reflects that fact. The Sheet of Assertion is a notional sheet of paper on which graphs can be “scribed”. It could be seen as infinite in extent but many people would be uncomfortable with that idea and so we can also say that it is finite. Choose whichever assumption suits the purpose because for practical purposes it does not matter since all real systems are finite. We might view it as finite but big enough that it cannot be filled in a reasonable time.

The blank or empty sheet of assertion can be represented as space enclosed in braces { }. The similarity to the empty set may not be coincidence. Such a sheet of assertion represents the value TRUE. This is the single logical axiom of Existential Graphs: the blank sheet of assertion is the value TRUE. From this, along with the rules to be discussed later, every tautology can be generated.

Propositions can be written on the sheet of assertion, between the braces, if they are true. Examples of propositions might be:

“There is a cat sitting on the mat.”
“John is travelling to London by train.”
“The Prime Minister lives at No. 10 Downing Street.”

Such propositions are known as “proper axioms” and they are the true statements that describe a universe of discourse. The above examples are all simple propositions because there are not any logical relationships expressed within them. Propositions which express logical relationships are known as complex propositions or rules and are also proper axioms. From the propositions on the sheet of assertion other propositions can be constructed by use of the rules of inference. Such further propositions are guaranteed also to be true.

Propositions on the sheet of assertion represent relationships between entities and situations that are true and actually exist. This notion of existence is logically important and more will be said in the chapter on System Beta but we mention it here partly because it is the origin of the name of Existential Graphs and partly because it will help our reading and understanding of the more complex graphs to be illustrated later. The assumption that a proposition expresses existence is called existential quantification and in standard logic it has the symbol $.

Conjunction

If two propositions are written on the sheet of assertion there is and implicit logical AND relationship between them. If several propositions, p q r... are written then the logical relationship between any pair and indeed all of them is AND. Thus we would have p AND q AND r AND .... In standard logical notation AND is shown as .

Such a sequence of proposition logically connected by the connective or operator AND is known as a conjunction. The word “and” occurs in many natural languages to connect several phrases into a sentence. Another often used word is “or” (standard symbol )and it was this connective that formed the basis of Peirce's Entiative Graphs which he eventually rejected in favour of Existential Graphs because of the latter's more natural mapping to language and, presumably, the internal workings of the mind.

An example of a conjunction is:

“There is a cat sitting on the mat.” AND “John is travelling to London by train.” AND “The Prime Minister lives at No. 10 Downing Street.”

All these propositions are true at the same time, which is what is intended by including them on the same sheet of assertion. When a conjunction is written on the sheet of assertion the AND is assumed and therefore is omitted.

Negation

Consider the proposition “It is not raining.”. Assuming that this is a true statement it could be written on a sheet of assertion. However this proposition is not quite like those that we have consider so far because it contains some logical information – NOT. Such propositions must be decomposed to make all the logical relationships clear. We have already seen this with AND. In order to do this with other connectives we could provide some sort of notation for every possible logical relationship but, given that we already have conjunction, only one other operator is necessary – negation (NOT), shown in standard logic as ¬ or ~, because from AND and NOT every other logical operator can be constructed.

To show the negation of a proposition Peirce used what he called a cut. A cut is shown as a circle drawn around the proposition or propositions to be negated. Everything within the cut is false and so by enclosing it within the cut the consistency of the sheet of assertion is maintained. The area within the cut is called a negated context. With this device the proposition “It is not raining.” would be shown as:

Fig. 1.1

We could have written on the sheet of assertion “It is not raining.” but, as we shall see, the extraction of the logical content means that the resulting graph – cut with enclosed proposition – is much more useful. In this example the proposition is enclosed inside just one cut and is said to be nested or enclosed at a depth of 1, and since 1 is an odd number the proposition is oddly enclosed or is in an oddly enclosed context.

A slightly more complex example might be “It is not raining and the sun is shining.”. This sentence contains two propositions connected by AND and would be shown as:


Fig. 1.2

This diagram contains the two propositions from the sentence, the first being the positive statement that the sun is shining and the second being the statement that it is raining, the latter enclosed in a cut to preserve its truth value. The two propositions are written down on the sheet of assertion and so the logical connective between them is AND. Again the negated propositions is oddly enclosed, at depth 1.

Care must be taken in the construction of cuts from sentences containing more than one proposition. Consider the sentence: “The sun is not shining and it is not raining.”. In this case each proposition within the sentence is negated and so would translate into the following

:
Fig. 1.3

Here we have “neither ... nor ...”, which corresponds to logical NOR (NOT OR). This case was straightforward but the sentence “It is not sunny and raining.” needs more care. It could be interpreted as “It is not sunny and it is raining.” or it could be interpreted as “It is not: sunny and raining.”. The first interpretation would give rise to a graph such as Fig.1.2 whereas the second interpretation gives the graph:


Fig. 1.4

In cases such as this it is the conjunction of the propositions that is negated and not each proposition separately as in fig. 1.3. The graph in fig. 1.4 is true even if either, but not both, of the nested propositions is true. This graph corresponds to logical NAND (NOT AND).

Nested Cuts

Any cut could contain another cut nested within it. Consider the sentence “It is false that the sun is shining and it is not warm.”. Here we have “false” governing the whole sentence, therefore the conjunction is false, and we have “not” governing “warm”. The “not” is within the scope of the “false” and therefore the corresponding cut for the “not” must be within the cut for the “false”. We get the following:


Fig. 1.5

The proposition “The sun is shining” is enclosed at depth 1, oddly enclosed, whilst the proposition “It is warm” is enclosed within 2 cuts, at depth 2, and is therefore evenly enclosed. It is worth noting that the inner cut is itself at depth 1 and is therefore oddly enclosed. There are other readings of this graph and these are based on the idea that since it is false that it is not warm when the sun shines then it must be warm every time the sun shines. We get the following equivalent readings:

In standard logic this is known as implication and is shown by the => operator so that, in this example, “The sun is shining” => “It is warm”. Implication, which is also called “IF ... THEN ...”, is the basis of any rule based system and more will be said about this in the section on the OWLS system.

Other Logical Connectives

As stated earlier any of the standard logical connectives can be constructed from conjunction and negation. We have already seen three examples, NOR, NAND and implication. Here we consider two more common connectives: OR and XOR (exclusive-OR):

Fig. 1.6

The first example shows how OR is represented and the second shows how exclusive-OR is represented.

Summary Of Primitives

Primitives are those parts of a logical system which cannot be defined in terms of other parts and which form the basis of the system. We have already mentioned each primitive of System Alpha and here we list them:

From conjunction and negation it is possible to construct any other logical relationship whatever. In a sense, since system alpha cannot decompose propositions, the notion of existential quantification is only partly applicable. However, since the sheet of assertion contains propositions which are stated to be true of the universe of discourse then any proposition which asserts the existence of anything whatever has an implicit existential quantifier associated with it. More will be said about quantification in the next chapter.

Although not a primitive we will include the following terminology:

Inference Rules

The inference rules that operate on Existential Graphs are extremely simple and elegant. They are based on whether or not truth is maintained if information is added or removed and this depends solely on depth of nesting.

Evenly Enclosed Contexts

Consider the following two propositions written directly on the sheet of assertion, depth 0:

“The ball is blue” AND “The ball is inflated”

Since we have written these on the sheet of assertion we can assume that they are true. We could now do one of two things: add some information or take some away. If we add some information we might get:

“The ball is blue” AND “The ball is inflated” AND “The ball is large”

This is palpably plausible but the situation changes if instead we write:

“The ball is blue” AND “The ball is inflated” AND “The ball is red”

Here we have a ball that is both blue and red. It seems that it is possible to add information that produces a contradiction. This means that we cannot arbitrarily add information at depth 0. Suppose instead that we start with:

“The ball is blue” AND “The ball is inflated” AND “The ball is large”

We can remove any one, any two or all three of these propositions and the result remains true. In other words it seems that at depth 0 the removal of information does not and cannot make any proposition false. We say that the removal of propositions at depth 0 is truth preserving. It is therefore possible to arbitrarily remove information from depth 0.

If instead the propositions above were at depth 2 then we could make exactly the same arguments and produce the same result and we could do the same at any evenly enclosed depth. Therefore information can arbitrarily be removed from evenly enclosed contexts. A moment's thought will show that the information removed need not be a single proposition but could be any complex graph whatever.

Oddly Enclosed Contexts

Similar arguments can be made about oddly enclosed contexts. If we have at depth 1:

“The ball is blue” AND “The ball is red”

we clearly have a contradiction and so the conjunction is false. In this case if we add further information we might get:

“The ball is blue” AND “The ball is red” AND “The ball is inflated”

This still contains the contradiction and so is still false. Add as much information as you like and the contradiction will remain present. Therefore the addition of arbitrary information to depth 1 maintains its falsity and is therefore truth preserving.

On the other hand it is not possible to remove arbitrary information and guarantee to maintain the falsity. Starting with:

“The ball is blue” AND “The ball is red” AND “The ball is inflated”

it is of course possible to remove the last proposition to give:

“The ball is blue” AND “The ball is red”

and maintain the contradiction. But if, instead, we removed either of the other two propositions we would not know whether what remained was now false or true since we do not know the true colour of the ball. Therefore the removal of arbitrary information from depth 1 is not truth preserving.

Similar arguments can be made for propositions at depth 3 or any other oddly enclosed depths. Therefore we can say that information can arbitrarily be added to oddly enclosed contexts. Again, such information could be arbitrarily complex graphs.

The Rules

The above discussion, and some other points, can be summarised in the following rules:

The last two rules have not been formally justified. This will be done following fig. 1.8.

These rules can be used to generate from the contents of the sheet of assertion any graph that is implied by them. Any such generated graph is a theorem. Some simple examples are illustrated in the next diagram:

Fig. 1.7

We now illustrate the use of these rules to prove some standard results:

Fig. 1.8

Example 4 shows a problem with this approach to constructing graphs. After the 4th step there are two ways to proceed. This kind of combinatorial problem is addressed in the section on the OWLS system.

Justification Of Iteration And Deiteration.

Iteration takes place from some context into one either an even number of cuts deeper or an odd number of cuts deeper. This is obvious but the justification for iteration is different from each case.

Even Case:

Given P the result P P is trivial therefore iteration into the same context as the original graph is trivially sound. Given P P we can now put a double cut around the second P (or indeed the first but since we will perceive the second P as the copy we will consider that one). We could put as many double cuts around P as we like therefore the argument extends to any context at an even depth greater than the original P. Therefore, given P we can draw any number of nested double cuts and place a copy of P into the innermost since this would be equivalent to performing the trivial copying of P and placing the double cuts around the copy afterwards.

Odd Case:

Given P the result P => P is trivial, and indeed was proved in fig. 1.8 example 1. This being the case then any number of double cuts could be placed around the copy of P so that it was always an odd number of cuts more deeply nested than the original P. Therefore, given P we can draw any number of nested double cuts inside a single cut in the same context as P and place a copy of P into the innermost since this would be equivalent to performing the trivial writing of P => P and placing the double cuts around the copy afterwards.

Deiteration:

Since any iterated graph P has its truth value determined by the depth of its outermost occurrence removal of more deeply nested copies cannot alter the truth value of the graph as a whole. In other words, since P P is true because P is true then either P can be removed. Any double cuts around the copy of P to be removed are irrelevant because a double cut is equivalent to no cut at all. Similarly for the case where P => P, which is derivable from P without addition or removal of information and is always true, the implied P can be removed because the truth of P is determined by the depth of nesting of its outermost occurrence. Any copy of P which is surrounded by one of more additional double cuts can also be removed since a double cut is equivalent to no cut at all.



Return To Main Index

Next Chapter




Updated 27th December, 2006